Branch data 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(sal_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 > 32 ) )
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 : 0 : while(sal_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 : : 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 : : 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 : : break;
265 : 0 : Length = L2 + 2 + m_iArrayOfM[L1 -7];
266 : : }
267 [ # # ]: 0 : 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 [ # # ]: 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 : : 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 : : 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 : : 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: */
|
