Line data Source code
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 0 : 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 0 : , m_nOutputBufferPos(0)
153 : {
154 0 : if (!m_pInStream || !m_pOutStream )
155 : {
156 : assert(false);
157 : }
158 0 : ConstructTree1();
159 0 : ConstructTree2();
160 0 : fillArray();
161 0 : }
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 0 : sal_uInt32 Decompression::ReadBits(sal_uInt16 iCount, sal_uInt32 & nBits)
169 : {
170 0 : if ( (iCount == 0) || (iCount > 31 ) )
171 : {
172 0 : return 1;
173 : }
174 :
175 0 : sal_uInt32 val = 0; /* bit accumulator */
176 :
177 : /* load at least need bits into val */
178 0 : val = m_nCurrent4Byte;
179 0 : while (m_nBitsLeft < iCount)
180 : {
181 0 : if (m_nBytesLeft == 0)
182 : {
183 0 : m_nBytesLeft = m_pInStream->Read(m_Buffer, CHUNK);
184 0 : m_pBuffer = m_Buffer;
185 0 : if (m_nBytesLeft == 0) return 1;
186 : }
187 0 : val |= (sal_uInt32)(*m_pBuffer++) << m_nBitsLeft; /* load eight bits */
188 0 : m_nBytesLeft --;
189 0 : m_nBitsLeft += 8;
190 : }
191 :
192 : /* drop need bits and update buffer, always zero to seven bits left */
193 0 : m_nCurrent4Byte = val >> iCount;
194 0 : m_nBitsLeft -= iCount;
195 :
196 : /* return need bits, zeroing the bits above that */
197 0 : nBits = val & ((1 << iCount) - 1);
198 :
199 0 : return 0;
200 : }
201 : /**
202 : * @descr decompress input and write output
203 : * @return 0 - read OK, otherwise error
204 : */
205 0 : sal_Int32 Decompression::explode()
206 : {
207 : /* The first 2 bytes are parameters */
208 : sal_uInt32 P1;
209 0 : if (0 != ReadBits(8, P1))/* 0 or 1 */
210 0 : return -1;
211 :
212 : /* I think this means 0=binary and 1=ascii file, but in RESOURCEs I saw always 0 */
213 0 : if (P1 >= 1) // changed per 's review comments
214 0 : return -1;
215 :
216 : sal_uInt32 P2;
217 0 : if (0 != ReadBits(8, P2))
218 0 : return -1;
219 :
220 : /* must be 4,5 or 6 and it is a parameter for the decompression algorithm */
221 0 : if (P2 < 4 || P2 > 6)
222 0 : return -2;
223 :
224 0 : 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 0 : if (0 != ReadBits(1, iBit))
232 0 : break;
233 0 : 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 0 : if (0 != ReadBits(8, symbol))
238 0 : break;
239 0 : m_Output[m_nOutputBufferPos++] = (sal_uInt8)symbol;
240 0 : if (m_nOutputBufferPos == MAXWIN)
241 : {
242 0 : m_pOutStream->Write(m_Output, m_nOutputBufferPos);
243 0 : m_nOutputBufferPos = 0;
244 : }
245 0 : 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 0 : sal_uInt32 L1 = Decode(m_Tree1);
250 : sal_uInt32 Length;
251 0 : if (L1 <= 7)
252 : {
253 : //if L1 <= 7:
254 : // LENGTH = L1 + 2
255 0 : 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 0 : if (0 != ReadBits((sal_uInt16)(L1 - 7), L2))
264 0 : break;
265 0 : Length = L2 + 2 + m_iArrayOfM[L1 -7];
266 : }
267 0 : if (Length == 519)
268 : {
269 : // end of compressed data
270 0 : break;
271 : }
272 :
273 : // - decode another number with Hufmann Tree #2 giving result 0x00..0x3F -> D1
274 0 : sal_uInt32 D1 = Decode(m_Tree2);
275 : sal_uInt32 D2;
276 0 : if (Length == 2)
277 : {
278 : // if LENGTH == 2
279 : // D1 = D1 << 2
280 : // read 2 bits -> D2
281 0 : D1 = D1 << 2;
282 0 : if (0 != ReadBits(2, D2))
283 0 : break;
284 : }
285 : else
286 : {
287 : // else
288 : // D1 = D1 << P2 // the parameter 2
289 : // read P2 bits -> D2
290 0 : D1 = D1 << P2;
291 0 : if (0 != ReadBits((sal_uInt16)P2, D2))
292 0 : break;
293 : }
294 : // DISTANCE = (D1 | D2) + 1
295 0 : 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 0 : m_pOutStream->Write(m_Output, m_nOutputBufferPos);
300 0 : m_nOutputBufferPos = 0;
301 :
302 : // remember current position
303 0 : sal_uInt32 nOutputPos = m_pOutStream->Tell();
304 0 : if (distance > nOutputPos)
305 0 : return -3; // format error
306 :
307 0 : m_pOutStream->Flush();
308 : // point back to copy position and read bytes
309 0 : m_pOutStream->SeekRel(-(long)distance);
310 : sal_uInt8 sTemp[MAXWIN];
311 0 : sal_uInt32 nRead = distance > Length? Length:distance;
312 0 : m_pOutStream->Read(sTemp, nRead);
313 0 : if (nRead != Length)
314 : {
315 : // fill the buffer with read content repeatly until full
316 0 : for (sal_uInt32 i=nRead; i<Length; i++)
317 : {
318 0 : sTemp[i] = sTemp[i-nRead];
319 : }
320 : }
321 :
322 : // restore output stream position
323 0 : m_pOutStream->Seek(nOutputPos);
324 :
325 : // write current buffer to output
326 0 : m_pOutStream->Write(sTemp, Length);
327 : }
328 0 : return 0;
329 : }
330 : /**
331 : * @descr bits to string
332 : * @return
333 : */
334 0 : void Decompression::ToString(sal_uInt32 nBits, sal_Char *pChar, sal_uInt32 nLen)
335 : {
336 : sal_uInt32 nBit;
337 0 : for (sal_uInt32 i=nLen; i > 0; i--)
338 : {
339 0 : nBit = (nBits >> (i -1) ) & 0x01;
340 0 : pChar[nLen - i] = nBit ? '1':'0';
341 : }
342 0 : pChar[nLen] = '\0';
343 0 : return;
344 : }
345 :
346 : /**
347 : * @descr decode tree 1 for length
348 : * @return the decoded value
349 : */
350 0 : sal_uInt32 Decompression::Decode(HuffmanTreeNode * pRoot)
351 : {
352 0 : sal_uInt32 nRet(0);
353 : sal_uInt32 nRead, nReadAlready;
354 :
355 0 : if( 0 != ReadBits(1, nReadAlready))
356 0 : return 0; // something wrong
357 :
358 0 : for (sal_uInt16 i=2; i <= 8; i++)
359 : {
360 0 : if ( 0 != ReadBits(1, nRead))
361 0 : return 0; // something wrong
362 :
363 0 : nReadAlready = (nReadAlready << 1) | (nRead & 0x01);
364 :
365 : sal_Char sCode[16];
366 0 : ToString(nReadAlready, sCode, i);
367 0 : nRet = pRoot->QueryValue(sCode);
368 0 : if (nRet != 0xffffffff)
369 : {
370 0 : break;
371 : }
372 : }
373 0 : return nRet;
374 : }
375 : /**
376 : * @descr construct tree 1 for length
377 : * @return
378 : */
379 0 : 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 0 : m_Tree1 = new HuffmanTreeNode();
400 0 : for (sal_uInt32 i=0; i< 16; i++)
401 : {
402 0 : 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 0 : }
423 : /**
424 : * @descr construct tree 2 for distance
425 : * @return
426 : */
427 0 : void Decompression::ConstructTree2()
428 : {
429 :
430 0 : m_Tree2 = new HuffmanTreeNode();
431 0 : for (sal_uInt32 i=0; i< 64; i++)
432 : {
433 0 : m_Tree2->InsertNode(i, Tree2String[i]);
434 : }
435 : //where bits should be read from the left to the right.
436 0 : }
437 : /**
438 : * @descr
439 : * @return
440 : */
441 0 : void Decompression::fillArray()
442 : {
443 0 : m_iArrayOfM[0] = 7;
444 0 : for (int i=1; i < 16; i++)
445 : {
446 0 : double dR = 2.0;
447 0 : m_iArrayOfM[i] = m_iArrayOfM[i - 1]+ (sal_uInt32)pow(dR, i-1);//2
448 : }
449 0 : }
450 :
451 0 : HuffmanTreeNode::HuffmanTreeNode(sal_uInt32 nValue , HuffmanTreeNode * pLeft , HuffmanTreeNode * pRight )
452 : {
453 0 : value = nValue;
454 0 : left = pLeft;
455 0 : right = pRight;
456 0 : }
457 0 : HuffmanTreeNode::~HuffmanTreeNode()
458 : {
459 0 : if (left)
460 : {
461 0 : delete left;
462 0 : left = NULL;
463 : }
464 0 : if (right)
465 : {
466 0 : delete right;
467 0 : right = NULL;
468 : }
469 0 : }
470 :
471 0 : HuffmanTreeNode * HuffmanTreeNode::InsertNode(sal_uInt32 nValue, const sal_Char * pInCode)
472 : {
473 0 : HuffmanTreeNode *pNew = new HuffmanTreeNode(nValue);
474 : sal_Char pCode[32];
475 0 : strcpy(pCode, pInCode );
476 :
477 : // query its parents
478 0 : sal_Char cLast = pCode[strlen(pCode) - 1];
479 0 : pCode[strlen(pCode) - 1] = '\0';
480 0 : HuffmanTreeNode * pParent = QueryNode(pCode);
481 0 : if (!pParent)
482 : {
483 0 : pParent = InsertNode(0xffffffff, pCode);
484 : }
485 0 : if (cLast == '0')
486 0 : pParent->left = pNew;
487 : else // (cChar == '1')
488 0 : pParent->right = pNew;
489 :
490 0 : return pNew;
491 : }
492 0 : HuffmanTreeNode * HuffmanTreeNode::QueryNode(const sal_Char * pCode)
493 : {
494 0 : sal_uInt32 nLen = strlen(pCode);
495 :
496 0 : HuffmanTreeNode * pNode = this; // this is the root
497 0 : for(sal_uInt32 i=0; i<nLen && pNode; i++)
498 : {
499 0 : sal_Char cChar= pCode[i];
500 0 : if (cChar == '0')
501 : {
502 0 : pNode = pNode->left;
503 : }
504 : else // (cChar == '1')
505 : {
506 0 : pNode = pNode->right;
507 : }
508 : }
509 0 : return pNode;
510 : }
511 :
512 0 : sal_uInt32 HuffmanTreeNode::QueryValue(const sal_Char * pCode)
513 : {
514 0 : HuffmanTreeNode * pNode =QueryNode(pCode);
515 0 : if (pNode)
516 0 : return pNode->value;
517 :
518 0 : return 0xffffffff;
519 : }
520 :
521 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
