merge the formfield patch from ooo-build

[ooovba.git] / lotuswordpro / source / filter / explode.cxx

/*************************************************************************
 *
 *  The Contents of this file are made available subject to the terms of
 *  either of the following licenses
 *
 *         - GNU Lesser General Public License Version 2.1
 *         - Sun Industry Standards Source License Version 1.1
 *
 *  Sun Microsystems Inc., October, 2000
 *
 *  GNU Lesser General Public License Version 2.1
 *  =============================================
 *  Copyright 2000 by Sun Microsystems, Inc.
 *  901 San Antonio Road, Palo Alto, CA 94303, USA
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License version 2.1, as published by the Free Software Foundation.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston,
 *  MA  02111-1307  USA
 *
 *
 *  Sun Industry Standards Source License Version 1.1
 *  =================================================
 *  The contents of this file are subject to the Sun Industry Standards
 *  Source License Version 1.1 (the "License"); You may not use this file
 *  except in compliance with the License. You may obtain a copy of the
 *  License at http://www.openoffice.org/license.html.
 *
 *  Software provided under this License is provided on an "AS IS" basis,
 *  WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
 *  WITHOUT LIMITATION, WARRANTIES THAT THE SOFTWARE IS FREE OF DEFECTS,
 *  MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE, OR NON-INFRINGING.
 *  See the License for the specific provisions governing your rights and
 *  obligations concerning the Software.
 *
 *  The Initial Developer of the Original Code is: IBM Corporation
 *
 *  Copyright: 2008 by IBM Corporation
 *
 *  All Rights Reserved.
 *
 *  Contributor(s): _______________________________________
 *
 *
 ************************************************************************/
#include <assert.h>
#include "explode.hxx"
#include <math.h>
        const static char Tree1String[][32] = {
                "101",
                "11",
               "100", 
                "011", 
                "0101",
                "0100",
                "0011",
                "00101",
                "00100",
                "00011",
                "00010",
                "000011",
                "000010",
                "000001",
                "0000001",
                "0000000",
        };

        const static char Tree2String[][32] = {
                "11"    ,
                "1011"  ,
               "1010"  ,
                "10011"  ,
                "10010"  ,
                "10001"  ,
                "10000"  ,
                "011111"  ,
                "011110"  ,
                "011101"  ,
                "011100"  ,
                "011011"  ,
                "011010"  ,
                "011001"  ,
                "011000"  ,
                "010111"  ,
                "010110" ,
                "010101" ,
                "010100" ,
                "010011" ,
                "010010" ,
                "010001" ,
                "0100001" ,
                "0100000" ,
                "0011111" ,
                "0011110" ,
                "0011101" ,
                "0011100" ,
                "0011011" ,
                "0011010" ,
                "0011001" ,
                "0011000" ,
                "0010111" ,
                "0010110" ,
                "0010101" ,
                "0010100" ,
                "0010011" ,
                "0010010" ,
                "0010001" ,
                "0010000" ,
                "0001111" ,
                "0001110" ,
                "0001101" ,
                "0001100" ,
                "0001011" ,
                "0001010" ,
                "0001001" ,
                "0001000" ,
                "00001111",
                "00001110",
                "00001101",
                "00001100",
                "00001011",
                "00001010",
                "00001001",
                "00001000",
                "00000111",
                "00000110",
                "00000101",
                "00000100",
                "00000011",
                "00000010",
                "00000001",
                "00000000",
        };

Decompression::Decompression(SvStream * pInStream, SvStream * pOutStream):
        m_pInStream(pInStream), m_pOutStream(pOutStream), m_pBuffer(m_Buffer), m_nOutputBufferPos(0),
                m_nBitsLeft(0), m_nBytesLeft(0), m_nCurrent4Byte(0)
{
        if (!m_pInStream || !m_pOutStream )
        {
                assert(sal_False);
        }
        ConstructTree1();
        ConstructTree2();
        fillArray();
}
/**
 * @descr       read specified bits from input stream
 * @argument iCount - number of bits to be read, less than 31
 * @argument nBits - bits read
 * @return      0 - read OK, otherwise error
 */
sal_uInt32 Decompression::ReadBits(sal_uInt16 iCount, sal_uInt32 & nBits) 
{
        if ( (iCount == 0) || (iCount > 32 ) )
        {
                return 1;
        }
        
        sal_uInt32 val = 0;             /* bit accumulator */

        /* load at least need bits into val */
        val = m_nCurrent4Byte;
        while (m_nBitsLeft < iCount) 
        {
                if (m_nBytesLeft == 0) 
                {
                        m_nBytesLeft = m_pInStream->Read(m_Buffer, CHUNK);
                        m_pBuffer = m_Buffer;
                        if (m_nBytesLeft == 0)  return 1; 
                }
                val |= (sal_uInt32)(*m_pBuffer++) << m_nBitsLeft;               /* load eight bits */
                m_nBytesLeft --;
                m_nBitsLeft += 8;
        }

        /* drop need bits and update buffer, always zero to seven bits left */
        m_nCurrent4Byte = val >> iCount;
        m_nBitsLeft -= iCount;

        /* return need bits, zeroing the bits above that */
        nBits = val & ((1 << iCount) - 1);

        return 0;       
} 
/**
 * @descr       decompress input and write output
 * @return      0 - read OK, otherwise error
 */
sal_Int32 Decompression::explode()
{
        /* The first 2 bytes are parameters */
        sal_uInt32 P1;
        if (0 != ReadBits(8, P1))/* 0 or 1 */
                return -1;
        
        /* I think this means 0=binary and 1=ascii file, but in RESOURCEs I saw always 0 */
        if (P1 >= 1) // changed per 's review comments
                return -1;
        
        sal_uInt32 P2;
        if (0 != ReadBits(8, P2))
                return -1;
        
        /* must be 4,5 or 6 and it is a parameter for the decompression algorithm */
        if (P2 < 4 || P2 > 6) 
                return -2;

        m_nOutputBufferPos = 0;
        /* Now, a bit stream follows, which is decoded as described below: */
        /*  The algorithm terminates as soon as it runs out of bits. */
        while(sal_True)
        {
                // read 1 bit (take bits from the lowest value (LSB) to the MSB i.e. bit 0, bit 1 etc ...)
                sal_uInt32 iBit;
                if (0 != ReadBits(1, iBit))
                        break;
                if ( 0 == (iBit & 0x01) )
                {
                        //if the bit is 0 read 8 bits and write it to the output as it is.
                        sal_uInt32 symbol;
                        if (0 != ReadBits(8, symbol))
                                break;
                        m_Output[m_nOutputBufferPos++] = (sal_uInt8)symbol;
                        if (m_nOutputBufferPos == MAXWIN) 
                        {
                                m_pOutStream->Write(m_Output, m_nOutputBufferPos);
                                m_nOutputBufferPos = 0;
                        }
                        continue;
                }
                // if the bit is 1 we have here a length/distance pair:
                // -decode a number with Hufmman Tree #1; variable bit length, result is 0x00 .. 0x0F -> L1
                sal_uInt32 L1 = Decode(m_Tree1);
                sal_uInt32 Length;
                if (L1 <= 7)
                {
                        //if L1 <= 7:
                        //           LENGTH = L1 + 2
                        Length = L1 + 2;
                }
                else
                {
                        // if L1 > 7
                        //            read more (L1-7) bits -> L2
                        //             LENGTH = L2 + M[L1-7] + 2
                        sal_uInt32 L2;
                        if (0 != ReadBits((sal_uInt16)(L1 - 7), L2))
                                break;
                        Length = L2 + 2 + m_iArrayOfM[L1 -7];
                }
                if (Length == 519)
                {
                        // end of compressed data
                        break;
                }
                
                // - decode another number with Hufmann Tree #2 giving result 0x00..0x3F -> D1
                sal_uInt32 D1 = Decode(m_Tree2);
                sal_uInt32 D2;
                if (Length == 2)
                {
                        //       if LENGTH == 2
                        //              D1 = D1 << 2
                        //              read 2 bits -> D2
                        D1 = D1 << 2;
                        if (0 != ReadBits(2, D2))
                                break;
                }
                else
                {
                        //        else
                        //               D1 = D1 << P2  // the parameter 2
                        //               read P2 bits -> D2
                        D1 = D1 << P2;
                        if (0 != ReadBits((sal_uInt16)P2, D2))
                                break;
                }
                // DISTANCE = (D1 | D2) + 1                     
                sal_uInt32 distance = (D1 | D2) + 1;

                // - now copy LENGTH bytes from (output_ptr-DISTANCE) to output_ptr             
                // write current buffer to output
                m_pOutStream->Write(m_Output, m_nOutputBufferPos);
                m_nOutputBufferPos = 0;

                // remember current position
                sal_uInt32 nOutputPos = m_pOutStream->Tell();
                if (distance > nOutputPos)
                        return -3; // format error

                m_pOutStream->Flush();
                // point back to copy position and read bytes
                m_pOutStream->SeekRel((long)-distance);
                sal_uInt8 sTemp[MAXWIN];
                sal_uInt32 nRead = distance > Length? Length:distance;
                m_pOutStream->Read(sTemp, nRead);
                if (nRead != Length)
                {
                        // fill the buffer with read content repeatly until full
                        for (sal_uInt32 i=nRead; i<Length; i++)
                        {
                                sTemp[i] = sTemp[i-nRead];
                        }
                }

                // restore output stream position
                m_pOutStream->Seek(nOutputPos);
                
               // write current buffer to output
                m_pOutStream->Write(sTemp, Length);
        }
        return 0;
}
/**
 * @descr       bits to string
 * @return      
 */
void Decompression::ToString(sal_uInt32 nBits, sal_Char *pChar, sal_uInt32 nLen)
{
        sal_uInt32 nBit;
        for (sal_uInt32 i=nLen; i > 0; i--)
        {
                nBit = (nBits >> (i -1) ) & 0x01;
                pChar[nLen - i]  = nBit ? '1':'0';
        }
        pChar[nLen] = '\0';
        return;
}

/**
 * @descr       decode tree 1 for length
 * @return      the decoded value
 */
sal_uInt32 Decompression::Decode(HuffmanTreeNode * pRoot)
{
        sal_uInt32 nRet;
        sal_uInt32 nRead, nReadAlready;
        
        if( 0 != ReadBits(1, nReadAlready))
                return 0; // something wrong

        for (sal_uInt16 i=2; i <= 8; i++)
        {
                if ( 0 != ReadBits(1, nRead))
                        return 0; // something wrong
                        
                nReadAlready  = (nReadAlready << 1) | (nRead & 0x01);

                sal_Char sCode[16];
                ToString(nReadAlready, sCode, i);
                nRet = pRoot->QueryValue(sCode);        
                if (nRet != 0xffffffff)
                {
                        break;
                }
        }
        return nRet;
}
/**
 * @descr       construct tree 1 for length
 * @return      
 */
void Decompression::ConstructTree1()
{       // Huffman Tree #1
        // The first huffman tree (the Section called Decompression algorithm HUFFMAN) contains the length values. It is described by the following table: 
        // value (hex)  code (binary)
        // 0    101
        // 1    11
        // 2    100
        // 3    011
        // 4    0101
        // 5    0100
        // 6    0011
        // 7    0010 1
        // 8    0010 0
        // 9    0001 1
        // a    0001 0
        // b    0000 11
        // c    0000 10
        // d    0000 01
        // e    0000 001
        // f    0000 000
        m_Tree1 = new HuffmanTreeNode();
        for (sal_uInt32 i=0; i< 16; i++)
        {
            m_Tree1->InsertNode(i, Tree1String[i]);
        }
        /*
        m_Tree1->InsertNode(0,   "101");
        m_Tree1->InsertNode(1,   "11");
        m_Tree1->InsertNode(2,   "100");
        m_Tree1->InsertNode(3,   "011");
        m_Tree1->InsertNode(4,   "0101");
        m_Tree1->InsertNode(5,   "0100");
        m_Tree1->InsertNode(6,   "0011");
        m_Tree1->InsertNode(7,   "00101");
        m_Tree1->InsertNode(8,   "00100");
        m_Tree1->InsertNode(9,   "00011");
        m_Tree1->InsertNode(10, "00010");
        m_Tree1->InsertNode(11, "000011");
        m_Tree1->InsertNode(12, "000010");
        m_Tree1->InsertNode(13, "000001");
        m_Tree1->InsertNode(14, "0000001");
        m_Tree1->InsertNode(15, "0000000");
        */
}
/**
 * @descr       construct tree 2 for distance
 * @return      
 */
void Decompression::ConstructTree2()
{

        m_Tree2 = new HuffmanTreeNode();
        for (sal_uInt32 i=0; i< 64; i++)
        {
            m_Tree2->InsertNode(i, Tree2String[i]);
        }
#if 0
        m_Tree2 = new HuffmanTreeNode();
    //Huffman Tree #2
    //The second huffman code tree contains the distance values. It can be built from the following table:
    //value (hex) code (binary)
    //00  11
    //01  1011
    //02  1010
    //03  1001 1
    //04  1001 0
    //05  1000 1
    //06  1000 0
    //07  0111 11
    //08  0111 10
    //09  0111 01
    //0a  0111 00
    //0b  0110 11
    //0c  0110 10
    //0d  0110 01
    //0e  0110 00
    //0f  0101 11
        m_Tree2->InsertNode(0x0,   "11");
        m_Tree2->InsertNode(0x1,   "1011");
        m_Tree2->InsertNode(0x2,   "1010");
        m_Tree2->InsertNode(0x3,   "10011");
        m_Tree2->InsertNode(0x4,   "10010");
        m_Tree2->InsertNode(0x5,   "10001");
        m_Tree2->InsertNode(0x6,   "10000");
        m_Tree2->InsertNode(0x7,   "011111");
        m_Tree2->InsertNode(0x8,   "011110");
        m_Tree2->InsertNode(0x9,   "011101");
        m_Tree2->InsertNode(0x0a,  "011100");
        m_Tree2->InsertNode(0x0b,  "011011");
        m_Tree2->InsertNode(0x0c,  "011010");
        m_Tree2->InsertNode(0x0d,  "011001");
        m_Tree2->InsertNode(0x0e,  "011000");
        m_Tree2->InsertNode(0x0f,  "010111");
        //10  0101 10
        //11  0101 01
        //12  0101 00
        //13  0100 11
        //14  0100 10
        //15  0100 01
        //16  0100 001
        //17  0100 000
        //18  0011 111
        //19  0011 110
        // 1a  0011 101
        // 1b  0011 100
        // 1c  0011 011
        // 1d  0011 010
        // 1e  0011 001
        // 1f  0011 000
        m_Tree2->InsertNode(0x10,   "010110");
        m_Tree2->InsertNode(0x11,   "010101");
        m_Tree2->InsertNode(0x12,   "010100");
        m_Tree2->InsertNode(0x13,   "010011");
        m_Tree2->InsertNode(0x14,   "010010");
        m_Tree2->InsertNode(0x15,   "010001");
        m_Tree2->InsertNode(0x16,   "0100001");
        m_Tree2->InsertNode(0x17,   "0100000");
        m_Tree2->InsertNode(0x18,   "0011111");
        m_Tree2->InsertNode(0x19,   "0011110");
        m_Tree2->InsertNode(0x1a,   "0011101");
        m_Tree2->InsertNode(0x1b,   "0011100");
        m_Tree2->InsertNode(0x1c,   "0011011");
        m_Tree2->InsertNode(0x1d,   "0011010");
        m_Tree2->InsertNode(0x1e,   "0011001");
        m_Tree2->InsertNode(0x1f,   "0011000");
    //20  0010 111
    //21  0010 110
    //22  0010 101
    //23  0010 100
    //24  0010 011
    //25  0010 010
    //26  0010 001
    //27  0010 000
    //28  0001 111
    //29  0001 110
    // 2a  0001 101
    // 2b  0001 100
    // 2c  0001 011
    // 2d  0001 010
    // 2e  0001 001
    // 2f  0001 000
        m_Tree2->InsertNode(0x20,   "0010111");
        m_Tree2->InsertNode(0x21,   "0010110");
        m_Tree2->InsertNode(0x22,   "0010101");
        m_Tree2->InsertNode(0x23,   "0010100");
        m_Tree2->InsertNode(0x24,   "0010011");
        m_Tree2->InsertNode(0x25,   "0010010");
        m_Tree2->InsertNode(0x26,   "0010001");
        m_Tree2->InsertNode(0x27,   "0010000");
        m_Tree2->InsertNode(0x28,   "0001111");
        m_Tree2->InsertNode(0x29,   "0001110");
        m_Tree2->InsertNode(0x2a,   "0001101");
        m_Tree2->InsertNode(0x2b,   "0001100");
        m_Tree2->InsertNode(0x2c,   "0001011");
        m_Tree2->InsertNode(0x2d,   "0001010");
        m_Tree2->InsertNode(0x2e,   "0001001");
        m_Tree2->InsertNode(0x2f,   "0001000");
    //30  0000 1111
    //31  0000 1110
    //32  0000 1101
    //33  0000 1100
    //34  0000 1011
    //35  0000 1010
    //36  0000 1001
    //37  0000 1000
    //38  0000 0111
    //39  0000 0110
    // 3a  0000 0101
    // 3b  0000 0100
    // 3c  0000 0011
    // 3d  0000 0010
    // 3e  0000 0001
    // 3f  0000 0000
        m_Tree2->InsertNode(0x30,   "00001111");
        m_Tree2->InsertNode(0x31,   "00001110");
        m_Tree2->InsertNode(0x32,   "00001101");
        m_Tree2->InsertNode(0x33,   "00001100");
        m_Tree2->InsertNode(0x34,   "00001011");
        m_Tree2->InsertNode(0x35,   "00001010");
        m_Tree2->InsertNode(0x36,   "00001001");
        m_Tree2->InsertNode(0x37,   "00001000");
        m_Tree2->InsertNode(0x38,   "00000111");
        m_Tree2->InsertNode(0x39,   "00000110");
        m_Tree2->InsertNode(0x3a,   "00000101");
        m_Tree2->InsertNode(0x3b,   "00000100");
        m_Tree2->InsertNode(0x3c,   "00000011");
        m_Tree2->InsertNode(0x3d,   "00000010");
        m_Tree2->InsertNode(0x3e,   "00000001");
        m_Tree2->InsertNode(0x3f,   "00000000");
#endif  
    //where bits should be read from the left to the right.
}
/**
 * @descr       
 * @return      
 */
void Decompression::fillArray()
{
        m_iArrayOfM[0] = 7;
        for (int i=1; i < 16; i++)
        {
                double dR = 2.0;
                m_iArrayOfM[i]  = m_iArrayOfM[i - 1]+ (sal_uInt32)pow(dR, i-1);//2
        }
}

HuffmanTreeNode::HuffmanTreeNode(sal_uInt32 nValue , HuffmanTreeNode * pLeft , HuffmanTreeNode * pRight ) 
{
        value = nValue;
        left = pLeft; 
        right = pRight;
}
HuffmanTreeNode::~HuffmanTreeNode() 
{
        if (left)
        {
                delete left;
                left = NULL;
        }
        if (right)
        {
                delete right;
                right = NULL;
        }               
}

HuffmanTreeNode * HuffmanTreeNode::InsertNode(sal_uInt32 nValue, const sal_Char * pInCode)
{
        HuffmanTreeNode *pNew = new HuffmanTreeNode(nValue);
        sal_Char pCode[32];
                strcpy(pCode, pInCode );

        // query its parents
        sal_Char cLast = pCode[strlen(pCode) - 1];
        pCode[strlen(pCode) - 1] = '\0';
        HuffmanTreeNode * pParent = QueryNode(pCode);
        if (!pParent)
        {
                pParent = InsertNode(0xffffffff, pCode);
        }
        if (cLast == '0')
                pParent->left = pNew;
        else // (cChar == '1')
                pParent->right = pNew;

        return pNew;
}
HuffmanTreeNode * HuffmanTreeNode::QueryNode(const sal_Char * pCode)
{
        sal_uInt32 nLen = strlen(pCode);

        HuffmanTreeNode * pNode = this; // this is the root 
        for(sal_uInt32 i=0; i<nLen && pNode; i++)
        {
                sal_Char cChar= pCode[i];
                if (cChar == '0')
                {
                        pNode = pNode->left;
                }
                else // (cChar == '1')
                {
                        pNode = pNode->right;
                }
        }
        return pNode;
}

sal_uInt32 HuffmanTreeNode::QueryValue(const sal_Char * pCode)
{
        HuffmanTreeNode * pNode =QueryNode(pCode);
        if (pNode)
                return pNode->value;

        return 0xffffffff;
}