lotuswordpro/source/filter/explode.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*************************************************************************
   3  *
   4  *  The Contents of this file are made available subject to the terms of
   5  *  either of the following licenses
   6  *
   7  *         - GNU Lesser General Public License Version 2.1
   8  *         - Sun Industry Standards Source License Version 1.1
   9  *
  10  *  Sun Microsystems Inc., October, 2000
  11  *
  12  *  GNU Lesser General Public License Version 2.1
  13  *  =============================================
  14  *  Copyright 2000 by Sun Microsystems, Inc.
  15  *  901 San Antonio Road, Palo Alto, CA 94303, USA
  16  *
  17  *  This library is free software; you can redistribute it and/or
  18  *  modify it under the terms of the GNU Lesser General Public
  19  *  License version 2.1, as published by the Free Software Foundation.
  20  *
  21  *  This library is distributed in the hope that it will be useful,
  22  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  23  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  24  *  Lesser General Public License for more details.
  25  *
  26  *  You should have received a copy of the GNU Lesser General Public
  27  *  License along with this library; if not, write to the Free Software
  28  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston,
  29  *  MA  02111-1307  USA
  30  *
  31  *
  32  *  Sun Industry Standards Source License Version 1.1
  33  *  =================================================
  34  *  The contents of this file are subject to the Sun Industry Standards
  35  *  Source License Version 1.1 (the "License"); You may not use this file
  36  *  except in compliance with the License. You may obtain a copy of the
  37  *  License at http://www.openoffice.org/license.html.
  38  *
  39  *  Software provided under this License is provided on an "AS IS" basis,
  40  *  WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
  41  *  WITHOUT LIMITATION, WARRANTIES THAT THE SOFTWARE IS FREE OF DEFECTS,
  42  *  MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE, OR NON-INFRINGING.
  43  *  See the License for the specific provisions governing your rights and
  44  *  obligations concerning the Software.
  45  *
  46  *  The Initial Developer of the Original Code is: IBM Corporation
  47  *
  48  *  Copyright: 2008 by IBM Corporation
  49  *
  50  *  All Rights Reserved.
  51  *
  52  *  Contributor(s): _______________________________________
  53  *
  54  *
  55  ************************************************************************/
  56 #include <assert.h>
  57 #include "explode.hxx"
  58 #include <math.h>
  59     const static char Tree1String[][32] = {
  60         "101",
  61         "11",
  62            "100",
  63         "011",
  64         "0101",
  65         "0100",
  66         "0011",
  67         "00101",
  68         "00100",
  69         "00011",
  70         "00010",
  71         "000011",
  72         "000010",
  73         "000001",
  74         "0000001",
  75         "0000000",
  76     };
  77
  78     const static char Tree2String[][32] = {
  79         "11"    ,
  80         "1011"  ,
  81            "1010"  ,
  82         "10011"  ,
  83         "10010"  ,
  84         "10001"  ,
  85         "10000"  ,
  86         "011111"  ,
  87         "011110"  ,
  88         "011101"  ,
  89         "011100"  ,
  90         "011011"  ,
  91         "011010"  ,
  92         "011001"  ,
  93         "011000"  ,
  94         "010111"  ,
  95         "010110" ,
  96         "010101" ,
  97         "010100" ,
  98         "010011" ,
  99         "010010" ,
 100         "010001" ,
 101         "0100001" ,
 102         "0100000" ,
 103         "0011111" ,
 104         "0011110" ,
 105         "0011101" ,
 106         "0011100" ,
 107         "0011011" ,
 108         "0011010" ,
 109         "0011001" ,
 110         "0011000" ,
 111         "0010111" ,
 112         "0010110" ,
 113         "0010101" ,
 114         "0010100" ,
 115         "0010011" ,
 116         "0010010" ,
 117         "0010001" ,
 118         "0010000" ,
 119         "0001111" ,
 120         "0001110" ,
 121         "0001101" ,
 122         "0001100" ,
 123         "0001011" ,
 124         "0001010" ,
 125         "0001001" ,
 126         "0001000" ,
 127         "00001111",
 128         "00001110",
 129         "00001101",
 130         "00001100",
 131         "00001011",
 132         "00001010",
 133         "00001001",
 134         "00001000",
 135         "00000111",
 136         "00000110",
 137         "00000101",
 138         "00000100",
 139         "00000011",
 140         "00000010",
 141         "00000001",
 142         "00000000",
 143     };
 144
 145 Decompression::Decompression(SvStream * pInStream, SvStream * pOutStream)
 146     : m_pInStream(pInStream)
 147     , m_pOutStream(pOutStream)
 148     , m_nCurrent4Byte(0)
 149     , m_nBitsLeft(0)
 150     , m_pBuffer(m_Buffer)
 151     , m_nBytesLeft(0)
 152     , m_nOutputBufferPos(0)
 153 {
 154     if (!m_pInStream || !m_pOutStream )
 155     {
 156         assert(false);
 157     }
 158     ConstructTree1();
 159     ConstructTree2();
 160     fillArray();
 161 }
 162 /**
 163  * @descr   read specified bits from input stream
 164  * @argument iCount - number of bits to be read, less than 31
 165  * @argument nBits - bits read
 166  * @return  0 - read OK, otherwise error
 167  */
 168 sal_uInt32 Decompression::ReadBits(sal_uInt16 iCount, sal_uInt32 & nBits)
 169 {
 170     if ( (iCount == 0) || (iCount > 31 ) )
 171     {
 172         return 1;
 173     }
 174
 175     sal_uInt32 val = 0;     /* bit accumulator */
 176
 177     /* load at least need bits into val */
 178     val = m_nCurrent4Byte;
 179     while (m_nBitsLeft < iCount)
 180     {
 181         if (m_nBytesLeft == 0)
 182         {
 183             m_nBytesLeft = m_pInStream->Read(m_Buffer, CHUNK);
 184             m_pBuffer = m_Buffer;
 185             if (m_nBytesLeft == 0)  return 1;
 186             }
 187         val |= (sal_uInt32)(*m_pBuffer++) << m_nBitsLeft;       /* load eight bits */
 188         m_nBytesLeft --;
 189         m_nBitsLeft += 8;
 190     }
 191
 192     /* drop need bits and update buffer, always zero to seven bits left */
 193     m_nCurrent4Byte = val >> iCount;
 194     m_nBitsLeft -= iCount;
 195
 196     /* return need bits, zeroing the bits above that */
 197     nBits = val & ((1 << iCount) - 1);
 198
 199     return 0;
 200 }
 201 /**
 202  * @descr   decompress input and write output
 203  * @return  0 - read OK, otherwise error
 204  */
 205 sal_Int32 Decompression::explode()
 206 {
 207     /* The first 2 bytes are parameters */
 208     sal_uInt32 P1;
 209     if (0 != ReadBits(8, P1))/* 0 or 1 */
 210         return -1;
 211
 212     /* I think this means 0=binary and 1=ascii file, but in RESOURCEs I saw always 0 */
 213     if (P1 >= 1) // changed per 's review comments
 214         return -1;
 215
 216     sal_uInt32 P2;
 217     if (0 != ReadBits(8, P2))
 218         return -1;
 219
 220     /* must be 4,5 or 6 and it is a parameter for the decompression algorithm */
 221     if (P2 < 4 || P2 > 6)
 222         return -2;
 223
 224     m_nOutputBufferPos = 0;
 225     /* Now, a bit stream follows, which is decoded as described below: */
 226     /*  The algorithm terminates as soon as it runs out of bits. */
 227     while(true)
 228     {
 229         // read 1 bit (take bits from the lowest value (LSB) to the MSB i.e. bit 0, bit 1 etc ...)
 230         sal_uInt32 iBit;
 231         if (0 != ReadBits(1, iBit))
 232             break;
 233         if ( 0 == (iBit & 0x01) )
 234         {
 235             //if the bit is 0 read 8 bits and write it to the output as it is.
 236             sal_uInt32 symbol;
 237             if (0 != ReadBits(8, symbol))
 238                 break;
 239             m_Output[m_nOutputBufferPos++] = (sal_uInt8)symbol;
 240             if (m_nOutputBufferPos == MAXWIN)
 241             {
 242                 m_pOutStream->Write(m_Output, m_nOutputBufferPos);
 243                 m_nOutputBufferPos = 0;
 244             }
 245             continue;
 246         }
 247         // if the bit is 1 we have here a length/distance pair:
 248         // -decode a number with Hufmman Tree #1; variable bit length, result is 0x00 .. 0x0F -> L1
 249         sal_uInt32 L1 = Decode(m_Tree1);
 250         sal_uInt32 Length;
 251         if (L1 <= 7)
 252         {
 253             //if L1 <= 7:
 254             //           LENGTH = L1 + 2
 255             Length = L1 + 2;
 256         }
 257         else
 258         {
 259             // if L1 > 7
 260             //            read more (L1-7) bits -> L2
 261             //             LENGTH = L2 + M[L1-7] + 2
 262             sal_uInt32 L2;
 263             if (0 != ReadBits((sal_uInt16)(L1 - 7), L2))
 264                 break;
 265             Length = L2 + 2 + m_iArrayOfM[L1 -7];
 266         }
 267         if (Length == 519)
 268         {
 269             // end of compressed data
 270             break;
 271         }
 272
 273         // - decode another number with Hufmann Tree #2 giving result 0x00..0x3F -> D1
 274         sal_uInt32 D1 = Decode(m_Tree2);
 275         sal_uInt32 D2;
 276         if (Length == 2)
 277         {
 278             //       if LENGTH == 2
 279             //              D1 = D1 << 2
 280             //              read 2 bits -> D2
 281             D1 = D1 << 2;
 282             if (0 != ReadBits(2, D2))
 283                 break;
 284         }
 285         else
 286         {
 287             //        else
 288             //               D1 = D1 << P2  // the parameter 2
 289             //               read P2 bits -> D2
 290             D1 = D1 << P2;
 291             if (0 != ReadBits((sal_uInt16)P2, D2))
 292                 break;
 293         }
 294         // DISTANCE = (D1 | D2) + 1
 295         sal_uInt32 distance = (D1 | D2) + 1;
 296
 297             // - now copy LENGTH bytes from (output_ptr-DISTANCE) to output_ptr
 298             // write current buffer to output
 299         m_pOutStream->Write(m_Output, m_nOutputBufferPos);
 300         m_nOutputBufferPos = 0;
 301
 302         // remember current position
 303         sal_uInt32 nOutputPos = m_pOutStream->Tell();
 304         if (distance > nOutputPos)
 305             return -3; // format error
 306
 307         m_pOutStream->Flush();
 308         // point back to copy position and read bytes
 309         m_pOutStream->SeekRel(-(long)distance);
 310         sal_uInt8 sTemp[MAXWIN];
 311         sal_uInt32 nRead = distance > Length? Length:distance;
 312         m_pOutStream->Read(sTemp, nRead);
 313         if (nRead != Length)
 314         {
 315             // fill the buffer with read content repeatly until full
 316             for (sal_uInt32 i=nRead; i<Length; i++)
 317             {
 318                 sTemp[i] = sTemp[i-nRead];
 319             }
 320         }
 321
 322         // restore output stream position
 323         m_pOutStream->Seek(nOutputPos);
 324
 325            // write current buffer to output
 326         m_pOutStream->Write(sTemp, Length);
 327     }
 328     return 0;
 329 }
 330 /**
 331  * @descr   bits to string
 332  * @return
 333  */
 334 void Decompression::ToString(sal_uInt32 nBits, sal_Char *pChar, sal_uInt32 nLen)
 335 {
 336     sal_uInt32 nBit;
 337     for (sal_uInt32 i=nLen; i > 0; i--)
 338     {
 339         nBit = (nBits >> (i -1) ) & 0x01;
 340         pChar[nLen - i]  = nBit ? '1':'0';
 341     }
 342     pChar[nLen] = '\0';
 343     return;
 344 }
 345
 346 /**
 347  * @descr   decode tree 1 for length
 348  * @return  the decoded value
 349  */
 350 sal_uInt32 Decompression::Decode(HuffmanTreeNode * pRoot)
 351 {
 352     sal_uInt32 nRet(0);
 353     sal_uInt32 nRead, nReadAlready;
 354
 355     if( 0 != ReadBits(1, nReadAlready))
 356         return 0; // something wrong
 357
 358     for (sal_uInt16 i=2; i <= 8; i++)
 359     {
 360         if ( 0 != ReadBits(1, nRead))
 361             return 0; // something wrong
 362
 363         nReadAlready  = (nReadAlready << 1) | (nRead & 0x01);
 364
 365         sal_Char sCode[16];
 366         ToString(nReadAlready, sCode, i);
 367         nRet = pRoot->QueryValue(sCode);
 368         if (nRet != 0xffffffff)
 369         {
 370             break;
 371         }
 372     }
 373     return nRet;
 374 }
 375 /**
 376  * @descr   construct tree 1 for length
 377  * @return
 378  */
 379 void Decompression::ConstructTree1()
 380 {   // Huffman Tree #1
 381     // The first huffman tree (the Section called Decompression algorithm HUFFMAN) contains the length values. It is described by the following table:
 382     // value (hex)  code (binary)
 383     // 0    101
 384     // 1    11
 385     // 2    100
 386     // 3    011
 387     // 4    0101
 388     // 5    0100
 389     // 6    0011
 390     // 7    0010 1
 391     // 8    0010 0
 392     // 9    0001 1
 393     // a    0001 0
 394     // b    0000 11
 395     // c    0000 10
 396     // d    0000 01
 397     // e    0000 001
 398     // f    0000 000
 399     m_Tree1 = new HuffmanTreeNode();
 400     for (sal_uInt32 i=0; i< 16; i++)
 401     {
 402         m_Tree1->InsertNode(i, Tree1String[i]);
 403     }
 404     /*
 405     m_Tree1->InsertNode(0,   "101");
 406     m_Tree1->InsertNode(1,   "11");
 407     m_Tree1->InsertNode(2,   "100");
 408     m_Tree1->InsertNode(3,   "011");
 409     m_Tree1->InsertNode(4,   "0101");
 410     m_Tree1->InsertNode(5,   "0100");
 411     m_Tree1->InsertNode(6,   "0011");
 412     m_Tree1->InsertNode(7,   "00101");
 413     m_Tree1->InsertNode(8,   "00100");
 414     m_Tree1->InsertNode(9,   "00011");
 415     m_Tree1->InsertNode(10, "00010");
 416     m_Tree1->InsertNode(11, "000011");
 417     m_Tree1->InsertNode(12, "000010");
 418     m_Tree1->InsertNode(13, "000001");
 419     m_Tree1->InsertNode(14, "0000001");
 420     m_Tree1->InsertNode(15, "0000000");
 421     */
 422 }
 423 /**
 424  * @descr   construct tree 2 for distance
 425  * @return
 426  */
 427 void Decompression::ConstructTree2()
 428 {
 429
 430     m_Tree2 = new HuffmanTreeNode();
 431     for (sal_uInt32 i=0; i< 64; i++)
 432     {
 433         m_Tree2->InsertNode(i, Tree2String[i]);
 434     }
 435     //where bits should be read from the left to the right.
 436 }
 437 /**
 438  * @descr
 439  * @return
 440  */
 441 void Decompression::fillArray()
 442 {
 443     m_iArrayOfM[0] = 7;
 444     for (int i=1; i < 16; i++)
 445     {
 446         double dR = 2.0;
 447         m_iArrayOfM[i]  = m_iArrayOfM[i - 1]+ (sal_uInt32)pow(dR, i-1);//2
 448     }
 449 }
 450
 451 HuffmanTreeNode::HuffmanTreeNode(sal_uInt32 nValue , HuffmanTreeNode * pLeft , HuffmanTreeNode * pRight )
 452 {
 453     value = nValue;
 454     left = pLeft;
 455     right = pRight;
 456 }
 457 HuffmanTreeNode::~HuffmanTreeNode()
 458 {
 459     if (left)
 460     {
 461         delete left;
 462         left = NULL;
 463     }
 464     if (right)
 465     {
 466         delete right;
 467         right = NULL;
 468     }
 469 }
 470
 471 HuffmanTreeNode * HuffmanTreeNode::InsertNode(sal_uInt32 nValue, const sal_Char * pInCode)
 472 {
 473     HuffmanTreeNode *pNew = new HuffmanTreeNode(nValue);
 474     sal_Char pCode[32];
 475         strcpy(pCode, pInCode );
 476
 477     // query its parents
 478     sal_Char cLast = pCode[strlen(pCode) - 1];
 479     pCode[strlen(pCode) - 1] = '\0';
 480     HuffmanTreeNode * pParent = QueryNode(pCode);
 481     if (!pParent)
 482     {
 483         pParent = InsertNode(0xffffffff, pCode);
 484     }
 485     if (cLast == '0')
 486         pParent->left = pNew;
 487     else // (cChar == '1')
 488         pParent->right = pNew;
 489
 490     return pNew;
 491 }
 492 HuffmanTreeNode * HuffmanTreeNode::QueryNode(const sal_Char * pCode)
 493 {
 494     sal_uInt32 nLen = strlen(pCode);
 495
 496     HuffmanTreeNode * pNode = this; // this is the root
 497     for(sal_uInt32 i=0; i<nLen && pNode; i++)
 498     {
 499         sal_Char cChar= pCode[i];
 500         if (cChar == '0')
 501         {
 502             pNode = pNode->left;
 503         }
 504         else // (cChar == '1')
 505         {
 506             pNode = pNode->right;
 507         }
 508     }
 509     return pNode;
 510 }
 511
 512 sal_uInt32 HuffmanTreeNode::QueryValue(const sal_Char * pCode)
 513 {
 514     HuffmanTreeNode * pNode =QueryNode(pCode);
 515     if (pNode)
 516         return pNode->value;
 517
 518     return 0xffffffff;
 519 }
 520
 521 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */