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
  57 #include "explode.hxx"
  58 #include <tools/stream.hxx>
  59
  60 #include <algorithm>
  61 #include <assert.h>
  62 #include <math.h>
  63
  64     const static char Tree1String[][32] = {
  65         "101",
  66         "11",
  67            "100",
  68         "011",
  69         "0101",
  70         "0100",
  71         "0011",
  72         "00101",
  73         "00100",
  74         "00011",
  75         "00010",
  76         "000011",
  77         "000010",
  78         "000001",
  79         "0000001",
  80         "0000000",
  81     };
  82
  83     const static char Tree2String[][32] = {
  84         "11"    ,
  85         "1011"  ,
  86            "1010"  ,
  87         "10011"  ,
  88         "10010"  ,
  89         "10001"  ,
  90         "10000"  ,
  91         "011111"  ,
  92         "011110"  ,
  93         "011101"  ,
  94         "011100"  ,
  95         "011011"  ,
  96         "011010"  ,
  97         "011001"  ,
  98         "011000"  ,
  99         "010111"  ,
 100         "010110" ,
 101         "010101" ,
 102         "010100" ,
 103         "010011" ,
 104         "010010" ,
 105         "010001" ,
 106         "0100001" ,
 107         "0100000" ,
 108         "0011111" ,
 109         "0011110" ,
 110         "0011101" ,
 111         "0011100" ,
 112         "0011011" ,
 113         "0011010" ,
 114         "0011001" ,
 115         "0011000" ,
 116         "0010111" ,
 117         "0010110" ,
 118         "0010101" ,
 119         "0010100" ,
 120         "0010011" ,
 121         "0010010" ,
 122         "0010001" ,
 123         "0010000" ,
 124         "0001111" ,
 125         "0001110" ,
 126         "0001101" ,
 127         "0001100" ,
 128         "0001011" ,
 129         "0001010" ,
 130         "0001001" ,
 131         "0001000" ,
 132         "00001111",
 133         "00001110",
 134         "00001101",
 135         "00001100",
 136         "00001011",
 137         "00001010",
 138         "00001001",
 139         "00001000",
 140         "00000111",
 141         "00000110",
 142         "00000101",
 143         "00000100",
 144         "00000011",
 145         "00000010",
 146         "00000001",
 147         "00000000",
 148     };
 149
 150 Decompression::Decompression(SvStream * pInStream, SvStream * pOutStream)
 151     : m_pInStream(pInStream)
 152     , m_pOutStream(pOutStream)
 153     , m_nCurrent4Byte(0)
 154     , m_nBitsLeft(0)
 155     , m_pBuffer(m_Buffer)
 156     , m_nBytesLeft(0)
 157     , m_nOutputBufferPos(0)
 158 {
 159     if (!m_pInStream || !m_pOutStream )
 160     {
 161         assert(false);
 162     }
 163     ConstructTree1();
 164     ConstructTree2();
 165     fillArray();
 166 }
 167 /**
 168  * @descr   read specified bits from input stream
 169  * @argument iCount - number of bits to be read, less than 31
 170  * @argument nBits - bits read
 171  * @return  0 - read OK, otherwise error
 172  */
 173 sal_uInt32 Decompression::ReadBits(sal_uInt16 iCount, sal_uInt32 & nBits)
 174 {
 175     if ( (iCount == 0) || (iCount > 31 ) )
 176     {
 177         return 1;
 178     }
 179
 180     sal_uInt32 val = 0;     /* bit accumulator */
 181
 182     /* load at least need bits into val */
 183     val = m_nCurrent4Byte;
 184     while (m_nBitsLeft < iCount)
 185     {
 186         if (m_nBytesLeft == 0)
 187         {
 188             m_nBytesLeft = m_pInStream->ReadBytes(m_Buffer, CHUNK);
 189             m_pBuffer = m_Buffer;
 190             if (m_nBytesLeft == 0)  return 1;
 191             }
 192         val |= static_cast<sal_uInt32>(*m_pBuffer++) << m_nBitsLeft;       /* load eight bits */
 193         m_nBytesLeft --;
 194         m_nBitsLeft += 8;
 195     }
 196
 197     /* drop need bits and update buffer, always zero to seven bits left */
 198     m_nCurrent4Byte = val >> iCount;
 199     m_nBitsLeft -= iCount;
 200
 201     /* return need bits, zeroing the bits above that */
 202     nBits = val & ((1 << iCount) - 1);
 203
 204     return 0;
 205 }
 206 /**
 207  * @descr   decompress input and write output
 208  * @return  0 - read OK, otherwise error
 209  */
 210 sal_Int32 Decompression::explode()
 211 {
 212     /* The first 2 bytes are parameters */
 213     sal_uInt32 P1;
 214     if (0 != ReadBits(8, P1))/* 0 or 1 */
 215         return -1;
 216
 217     /* I think this means 0=binary and 1=ascii file, but in RESOURCEs I saw always 0 */
 218     if (P1 >= 1) // changed per 's review comments
 219         return -1;
 220
 221     sal_uInt32 P2;
 222     if (0 != ReadBits(8, P2))
 223         return -1;
 224
 225     /* must be 4,5 or 6 and it is a parameter for the decompression algorithm */
 226     if (P2 < 4 || P2 > 6)
 227         return -2;
 228
 229     m_nOutputBufferPos = 0;
 230     /* Now, a bit stream follows, which is decoded as described below: */
 231     /*  The algorithm terminates as soon as it runs out of bits. */
 232     while(true)
 233     {
 234         // read 1 bit (take bits from the lowest value (LSB) to the MSB i.e. bit 0, bit 1 etc ...)
 235         sal_uInt32 iBit;
 236         if (0 != ReadBits(1, iBit))
 237             break;
 238         if ( 0 == (iBit & 0x01) )
 239         {
 240             //if the bit is 0 read 8 bits and write it to the output as it is.
 241             sal_uInt32 symbol;
 242             if (0 != ReadBits(8, symbol))
 243                 break;
 244             m_Output[m_nOutputBufferPos++] = static_cast<sal_uInt8>(symbol);
 245             if (m_nOutputBufferPos == MAXWIN)
 246             {
 247                 m_pOutStream->WriteBytes(m_Output, m_nOutputBufferPos);
 248                 m_nOutputBufferPos = 0;
 249             }
 250             continue;
 251         }
 252         // if the bit is 1 we have here a length/distance pair:
 253         // -decode a number with Hufmman Tree #1; variable bit length, result is 0x00 .. 0x0F -> L1
 254         sal_uInt32 L1 = Decode(m_Tree1.get());
 255         sal_uInt32 Length;
 256         if (L1 <= 7)
 257         {
 258             //if L1 <= 7:
 259             //           LENGTH = L1 + 2
 260             Length = L1 + 2;
 261         }
 262         else
 263         {
 264             // if L1 > 7
 265             //            read more (L1-7) bits -> L2
 266             //             LENGTH = L2 + M[L1-7] + 2
 267             sal_uInt32 L2;
 268             if (0 != ReadBits(static_cast<sal_uInt16>(L1 - 7), L2))
 269                 break;
 270             Length = L2 + 2 + m_iArrayOfM[L1 -7];
 271         }
 272         if (Length == 519)
 273         {
 274             // end of compressed data
 275             break;
 276         }
 277
 278         // - decode another number with Hufmann Tree #2 giving result 0x00..0x3F -> D1
 279         sal_uInt32 D1 = Decode(m_Tree2.get());
 280         sal_uInt32 D2;
 281         if (Length == 2)
 282         {
 283             //       if LENGTH == 2
 284             //              D1 = D1 << 2
 285             //              read 2 bits -> D2
 286             D1 = D1 << 2;
 287             if (0 != ReadBits(2, D2))
 288                 break;
 289         }
 290         else
 291         {
 292             //        else
 293             //               D1 = D1 << P2  // the parameter 2
 294             //               read P2 bits -> D2
 295             D1 = D1 << P2;
 296             if (0 != ReadBits(static_cast<sal_uInt16>(P2), D2))
 297                 break;
 298         }
 299         // DISTANCE = (D1 | D2) + 1
 300         sal_uInt32 distance = (D1 | D2) + 1;
 301
 302             // - now copy LENGTH bytes from (output_ptr-DISTANCE) to output_ptr
 303             // write current buffer to output
 304         m_pOutStream->WriteBytes(m_Output, m_nOutputBufferPos);
 305         m_nOutputBufferPos = 0;
 306
 307         // remember current position
 308         sal_uInt32 nOutputPos = m_pOutStream->Tell();
 309         if (distance > nOutputPos)
 310             return -3; // format error
 311
 312         m_pOutStream->Flush();
 313         // point back to copy position and read bytes
 314         m_pOutStream->SeekRel(-static_cast<long>(distance));
 315         sal_uInt8 sTemp[MAXWIN];
 316         sal_uInt32 nRead = std::min(distance, Length);
 317         m_pOutStream->ReadBytes(sTemp, nRead);
 318         if (nRead != Length)
 319         {
 320             // fill the buffer with read content repeatedly until full
 321             for (sal_uInt32 i=nRead; i<Length; i++)
 322             {
 323                 sTemp[i] = sTemp[i-nRead];
 324             }
 325         }
 326
 327         // restore output stream position
 328         m_pOutStream->Seek(nOutputPos);
 329
 330            // write current buffer to output
 331         m_pOutStream->WriteBytes(sTemp, Length);
 332     }
 333     return 0;
 334 }
 335 /**
 336  * @descr   bits to string
 337  * @return
 338  */
 339 void Decompression::ToString(sal_uInt32 nBits, sal_Char *pChar, sal_uInt32 nLen)
 340 {
 341     sal_uInt32 nBit;
 342     for (sal_uInt32 i=nLen; i > 0; i--)
 343     {
 344         nBit = (nBits >> (i -1) ) & 0x01;
 345         pChar[nLen - i]  = nBit ? '1':'0';
 346     }
 347     pChar[nLen] = '\0';
 348 }
 349
 350 /**
 351  * @descr   decode tree 1 for length
 352  * @return  the decoded value
 353  */
 354 sal_uInt32 Decompression::Decode(HuffmanTreeNode * pRoot)
 355 {
 356     sal_uInt32 nRet(0);
 357     sal_uInt32 nRead, nReadAlready;
 358
 359     if( 0 != ReadBits(1, nReadAlready))
 360         return 0; // something wrong
 361
 362     for (sal_uInt16 i=2; i <= 8; i++)
 363     {
 364         if ( 0 != ReadBits(1, nRead))
 365             return 0; // something wrong
 366
 367         nReadAlready  = (nReadAlready << 1) | (nRead & 0x01);
 368
 369         sal_Char sCode[16];
 370         ToString(nReadAlready, sCode, i);
 371         nRet = pRoot->QueryValue(sCode);
 372         if (nRet != 0xffffffff)
 373         {
 374             break;
 375         }
 376     }
 377     return nRet;
 378 }
 379 /**
 380  * @descr   construct tree 1 for length
 381  * @return
 382  */
 383 void Decompression::ConstructTree1()
 384 {   // Huffman Tree #1
 385     // The first huffman tree (the Section called Decompression algorithm HUFFMAN) contains the length values. It is described by the following table:
 386     // value (hex)  code (binary)
 387     // 0    101
 388     // 1    11
 389     // 2    100
 390     // 3    011
 391     // 4    0101
 392     // 5    0100
 393     // 6    0011
 394     // 7    0010 1
 395     // 8    0010 0
 396     // 9    0001 1
 397     // a    0001 0
 398     // b    0000 11
 399     // c    0000 10
 400     // d    0000 01
 401     // e    0000 001
 402     // f    0000 000
 403     m_Tree1.reset( new HuffmanTreeNode());
 404     for (sal_uInt32 i=0; i< 16; i++)
 405     {
 406         m_Tree1->InsertNode(i, Tree1String[i]);
 407     }
 408     /*
 409     m_Tree1->InsertNode(0,   "101");
 410     m_Tree1->InsertNode(1,   "11");
 411     m_Tree1->InsertNode(2,   "100");
 412     m_Tree1->InsertNode(3,   "011");
 413     m_Tree1->InsertNode(4,   "0101");
 414     m_Tree1->InsertNode(5,   "0100");
 415     m_Tree1->InsertNode(6,   "0011");
 416     m_Tree1->InsertNode(7,   "00101");
 417     m_Tree1->InsertNode(8,   "00100");
 418     m_Tree1->InsertNode(9,   "00011");
 419     m_Tree1->InsertNode(10, "00010");
 420     m_Tree1->InsertNode(11, "000011");
 421     m_Tree1->InsertNode(12, "000010");
 422     m_Tree1->InsertNode(13, "000001");
 423     m_Tree1->InsertNode(14, "0000001");
 424     m_Tree1->InsertNode(15, "0000000");
 425     */
 426 }
 427 /**
 428  * @descr   construct tree 2 for distance
 429  * @return
 430  */
 431 void Decompression::ConstructTree2()
 432 {
 433
 434     m_Tree2.reset(new HuffmanTreeNode());
 435     for (sal_uInt32 i=0; i< 64; i++)
 436     {
 437         m_Tree2->InsertNode(i, Tree2String[i]);
 438     }
 439     //where bits should be read from the left to the right.
 440 }
 441 /**
 442  * @descr
 443  * @return
 444  */
 445 void Decompression::fillArray()
 446 {
 447     m_iArrayOfM[0] = 7;
 448     for (int i=1; i < 16; i++)
 449     {
 450         m_iArrayOfM[i]  = m_iArrayOfM[i - 1]+ static_cast<sal_uInt32>(pow(2.0, i-1));//2
 451     }
 452 }
 453
 454 HuffmanTreeNode::HuffmanTreeNode(sal_uInt32 nValue):value(nValue)
 455 {
 456 }
 457 HuffmanTreeNode::~HuffmanTreeNode()
 458 {
 459 }
 460
 461 HuffmanTreeNode * HuffmanTreeNode::InsertNode(sal_uInt32 nValue, const sal_Char * pInCode)
 462 {
 463     HuffmanTreeNode *pNew = new HuffmanTreeNode(nValue);
 464     std::string aCode(pInCode);
 465
 466     // query its parents
 467     const sal_Char cLast = aCode.back();
 468     aCode.pop_back();
 469     HuffmanTreeNode * pParent = QueryNode(aCode.c_str());
 470     if (!pParent)
 471     {
 472         pParent = InsertNode(0xffffffff, aCode.c_str());
 473     }
 474     if (cLast == '0')
 475         pParent->left.reset(pNew);
 476     else // (cChar == '1')
 477         pParent->right.reset(pNew);
 478
 479     return pNew;
 480 }
 481
 482 HuffmanTreeNode * HuffmanTreeNode::QueryNode(const sal_Char * pCode)
 483 {
 484     sal_uInt32 nLen = strlen(pCode);
 485
 486     HuffmanTreeNode * pNode = this; // this is the root
 487     for(sal_uInt32 i=0; i<nLen && pNode; i++)
 488     {
 489         sal_Char cChar= pCode[i];
 490         if (cChar == '0')
 491         {
 492             pNode = pNode->left.get();
 493         }
 494         else // (cChar == '1')
 495         {
 496             pNode = pNode->right.get();
 497         }
 498     }
 499     return pNode;
 500 }
 501
 502 sal_uInt32 HuffmanTreeNode::QueryValue(const sal_Char * pCode)
 503 {
 504     HuffmanTreeNode * pNode =QueryNode(pCode);
 505     if (pNode)
 506         return pNode->value;
 507
 508     return 0xffffffff;
 509 }
 510
 511 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */