?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Clean and tiddy-up files.
[tomato.git] / release / src-rt / shared / bzip2_inflate.c
blobe3a75d40ccb534d749d39b70dfe3fc813507e999
1 /*-------------------------------------------------------------*/
2 /*
3
4 bzip2 stuff for linux kernel and ramdisk decompression.
5
6 This file was derived by Thomas Oehser, Tom@Toms.NET,
7 from bzlib.c from bzip2-1.0.2, to fit more with less.
8
9 The initial implementation is only tested to work with
10 kernel version 2.2.20 and only with bzImage (bz2bzImage).
11
12 Mostly I just chopped out compression stuff (leaving
13 only decompression) and the 'high-level' stuff, (that
14 expects stdio and libc), and chopped out any other bits
15 that required stuff that isn't around during kernel boot.
16
17 I crammed everything it needed together into this one
18 file, also. And not always in a logical order.
19
20 */
21
22 /*-------------------------------------------------------------*/
23
24 /*--
25 This file is a part of bzip2 and/or libbzip2, a program and
26 library for lossless, block-sorting data compression.
27
28 Copyright (C) 1996-2002 Julian R Seward. All rights reserved.
29
30 Redistribution and use in source and binary forms, with or without
31 modification, are permitted provided that the following conditions
32 are met:
33
34 1. Redistributions of source code must retain the above copyright
35 notice, this list of conditions and the following disclaimer.
36
37 2. The origin of this software must not be misrepresented; you must
38 not claim that you wrote the original software. If you use this
39 software in a product, an acknowledgment in the product
40 documentation would be appreciated but is not required.
41
42 3. Altered source versions must be plainly marked as such, and must
43 not be misrepresented as being the original software.
44
45 4. The name of the author may not be used to endorse or promote
46 products derived from this software without specific prior written
47 permission.
48
49 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
50 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
51 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
52 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
53 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
54 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
55 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
56 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
57 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
58 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
59 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
60
61 Julian Seward, Cambridge, UK.
62 jseward@acm.org
63 bzip2/libbzip2 version 1.0 of 21 March 2000
64
65 This program is based on (at least) the work of:
66 Mike Burrows
67 David Wheeler
68 Peter Fenwick
69 Alistair Moffat
70 Radford Neal
71 Ian H. Witten
72 Robert Sedgewick
73 Jon L. Bentley
74
75 For more information on these sources, see the manual.
76 --*/
77
78 /*-- General stuff. --*/
79 /* FILE-CSTYLED */
80 #define BZ_VERSION "1.0.2, 30-Dec-2001"
81
82 typedef char Char;
83 typedef unsigned char Bool;
84 typedef unsigned char UChar;
85 typedef int Int32;
86 typedef unsigned int UInt32;
87 typedef short Int16;
88 typedef unsigned short UInt16;
89
90 #define True ((Bool)1)
91 #define False ((Bool)0)
92
93 #ifndef __GNUC__
94 #define __inline__ /* */
95 #endif
96
97 extern void bz_internal_error ( int errcode );
98 __inline__ Int32 BZ2_indexIntoF ( Int32 indx, Int32 *cftab );
99 void BZ2_hbCreateDecodeTables ( Int32 *limit,
100 Int32 *base,
101 Int32 *perm,
102 UChar *length,
103 Int32 minLen,
104 Int32 maxLen,
105 Int32 alphaSize );
106 void BZ2_hbMakeCodeLengths ( UChar *len,
107 Int32 *freq,
108 Int32 alphaSize,
109 Int32 maxLen );
110 void BZ2_hbAssignCodes ( Int32 *code,
111 UChar *length,
112 Int32 minLen,
113 Int32 maxLen,
114 Int32 alphaSize );
115
116 #define AssertH(cond,errcode) \
117 { if (!(cond)) bz_internal_error ( errcode ); }
118 #define AssertD(cond,msg) /* */
119 #define VPrintf0(zf) /* */
120 #define VPrintf1(zf,za1) /* */
121 #define VPrintf2(zf,za1,za2) /* */
122 #define VPrintf3(zf,za1,za2,za3) /* */
123 #define VPrintf4(zf,za1,za2,za3,za4) /* */
124 #define VPrintf5(zf,za1,za2,za3,za4,za5) /* */
125
126 #define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1)
127 #define BZFREE(ppp) (strm->bzfree)(strm->opaque,(ppp))
128
129 /*-- Header bytes. --*/
130
131 #define BZ_HDR_B 0x42 /* 'B' */
132 #define BZ_HDR_Z 0x5a /* 'Z' */
133 #define BZ_HDR_h 0x68 /* 'h' */
134 #define BZ_HDR_0 0x30 /* '0' */
135
136 /*-- Constants for the back end. --*/
137
138 #define BZ_MAX_ALPHA_SIZE 258
139 #define BZ_MAX_CODE_LEN 23
140
141 #define BZ_RUNA 0
142 #define BZ_RUNB 1
143
144 #define BZ_N_GROUPS 6
145 #define BZ_G_SIZE 50
146 #define BZ_N_ITERS 4
147
148 #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
149
150
151
152 /*-- Stuff for randomising repetitive blocks. --*/
153
154 // extern Int32 BZ2_rNums[512];
155
156 #define BZ_RAND_DECLS \
157 Int32 rNToGo; \
158 Int32 rTPos \
159
160 #define BZ_RAND_INIT_MASK \
161 s->rNToGo = 0; \
162 s->rTPos = 0 \
163
164 #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)
165
166 #define BZ_RAND_UPD_MASK \
167 if (s->rNToGo == 0) { \
168 s->rNToGo = BZ2_rNums[s->rTPos]; \
169 s->rTPos++; \
170 if (s->rTPos == 512) s->rTPos = 0; \
171 } \
172 s->rNToGo--;
173
174 /*-- Stuff for doing CRCs. --*/
175
176 // extern UInt32 BZ2_crc32Table[256];
177
178 #define BZ_INITIALISE_CRC(crcVar) \
179 { \
180 crcVar = 0xffffffffL; \
181 }
182
183 #define BZ_FINALISE_CRC(crcVar) \
184 { \
185 crcVar = ~(crcVar); \
186 }
187
188 #define BZ_UPDATE_CRC(crcVar,cha) \
189 { \
190 crcVar = (crcVar << 8) ^ \
191 BZ2_crc32Table[(crcVar >> 24) ^ \
192 ((UChar)cha)]; \
193 }
194
195 /*-- states for decompression. --*/
196
197 #define BZ_X_IDLE 1
198 #define BZ_X_OUTPUT 2
199
200 #define BZ_X_MAGIC_1 10
201 #define BZ_X_MAGIC_2 11
202 #define BZ_X_MAGIC_3 12
203 #define BZ_X_MAGIC_4 13
204 #define BZ_X_BLKHDR_1 14
205 #define BZ_X_BLKHDR_2 15
206 #define BZ_X_BLKHDR_3 16
207 #define BZ_X_BLKHDR_4 17
208 #define BZ_X_BLKHDR_5 18
209 #define BZ_X_BLKHDR_6 19
210 #define BZ_X_BCRC_1 20
211 #define BZ_X_BCRC_2 21
212 #define BZ_X_BCRC_3 22
213 #define BZ_X_BCRC_4 23
214 #define BZ_X_RANDBIT 24
215 #define BZ_X_ORIGPTR_1 25
216 #define BZ_X_ORIGPTR_2 26
217 #define BZ_X_ORIGPTR_3 27
218 #define BZ_X_MAPPING_1 28
219 #define BZ_X_MAPPING_2 29
220 #define BZ_X_SELECTOR_1 30
221 #define BZ_X_SELECTOR_2 31
222 #define BZ_X_SELECTOR_3 32
223 #define BZ_X_CODING_1 33
224 #define BZ_X_CODING_2 34
225 #define BZ_X_CODING_3 35
226 #define BZ_X_MTF_1 36
227 #define BZ_X_MTF_2 37
228 #define BZ_X_MTF_3 38
229 #define BZ_X_MTF_4 39
230 #define BZ_X_MTF_5 40
231 #define BZ_X_MTF_6 41
232 #define BZ_X_ENDHDR_2 42
233 #define BZ_X_ENDHDR_3 43
234 #define BZ_X_ENDHDR_4 44
235 #define BZ_X_ENDHDR_5 45
236 #define BZ_X_ENDHDR_6 46
237 #define BZ_X_CCRC_1 47
238 #define BZ_X_CCRC_2 48
239 #define BZ_X_CCRC_3 49
240 #define BZ_X_CCRC_4 50
241
242 /*-- Constants for the fast MTF decoder. --*/
243
244 #define MTFA_SIZE 4096
245 #define MTFL_SIZE 16
246
247
248 #define BZ_RUN 0
249 #define BZ_FLUSH 1
250 #define BZ_FINISH 2
251
252 #define BZ_OK 0
253 #define BZ_RUN_OK 1
254 #define BZ_FLUSH_OK 2
255 #define BZ_FINISH_OK 3
256 #define BZ_STREAM_END 4
257 #define BZ_SEQUENCE_ERROR (-1)
258 #define BZ_PARAM_ERROR (-2)
259 #define BZ_MEM_ERROR (-3)
260 #define BZ_DATA_ERROR (-4)
261 #define BZ_DATA_ERROR_MAGIC (-5)
262 #define BZ_IO_ERROR (-6)
263 #define BZ_UNEXPECTED_EOF (-7)
264 #define BZ_OUTBUFF_FULL (-8)
265 #define BZ_CONFIG_ERROR (-9)
266
267 typedef
268 struct {
269 char *next_in;
270 unsigned int avail_in;
271 unsigned int total_in_lo32;
272 unsigned int total_in_hi32;
273
274 char *next_out;
275 unsigned int avail_out;
276 unsigned int total_out_lo32;
277 unsigned int total_out_hi32;
278
279 void *state;
280
281 void *(*bzalloc)(void *,int,int);
282 void (*bzfree)(void *,void *);
283 void *opaque;
284 }
285 bz_stream;
286
287 #ifndef BZ_IMPORT
288 #define BZ_EXPORT
289 #endif
290
291 # define BZ_API(func) func
292 # define BZ_EXTERN extern
293
294 /*-- Structure holding all the decompression-side stuff. --*/
295
296 typedef
297 struct {
298 /* pointer back to the struct bz_stream */
299 bz_stream* strm;
300
301 /* state indicator for this stream */
302 Int32 state;
303
304 /* for doing the final run-length decoding */
305 UChar state_out_ch;
306 Int32 state_out_len;
307 Bool blockRandomised;
308 BZ_RAND_DECLS;
309
310 /* the buffer for bit stream reading */
311 UInt32 bsBuff;
312 Int32 bsLive;
313
314 /* misc administratium */
315 Int32 blockSize100k;
316 Bool smallDecompress;
317 Int32 currBlockNo;
318 Int32 verbosity;
319
320 /* for undoing the Burrows-Wheeler transform */
321 Int32 origPtr;
322 UInt32 tPos;
323 Int32 k0;
324 Int32 unzftab[256];
325 Int32 nblock_used;
326 Int32 cftab[257];
327 Int32 cftabCopy[257];
328
329 /* for undoing the Burrows-Wheeler transform (FAST) */
330 UInt32 *tt;
331
332 /* for undoing the Burrows-Wheeler transform (SMALL) */
333 UInt16 *ll16;
334 UChar *ll4;
335
336 /* stored and calculated CRCs */
337 UInt32 storedBlockCRC;
338 UInt32 storedCombinedCRC;
339 UInt32 calculatedBlockCRC;
340 UInt32 calculatedCombinedCRC;
341
342 /* map of bytes used in block */
343 Int32 nInUse;
344 Bool inUse[256];
345 Bool inUse16[16];
346 UChar seqToUnseq[256];
347
348 /* for decoding the MTF values */
349 UChar mtfa [MTFA_SIZE];
350 Int32 mtfbase[256 / MTFL_SIZE];
351 UChar selector [BZ_MAX_SELECTORS];
352 UChar selectorMtf[BZ_MAX_SELECTORS];
353 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
354
355 Int32 limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
356 Int32 base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
357 Int32 perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
358 Int32 minLens[BZ_N_GROUPS];
359
360 /* save area for scalars in the main decompress code */
361 Int32 save_i;
362 Int32 save_j;
363 Int32 save_t;
364 Int32 save_alphaSize;
365 Int32 save_nGroups;
366 Int32 save_nSelectors;
367 Int32 save_EOB;
368 Int32 save_groupNo;
369 Int32 save_groupPos;
370 Int32 save_nextSym;
371 Int32 save_nblockMAX;
372 Int32 save_nblock;
373 Int32 save_es;
374 Int32 save_N;
375 Int32 save_curr;
376 Int32 save_zt;
377 Int32 save_zn;
378 Int32 save_zvec;
379 Int32 save_zj;
380 Int32 save_gSel;
381 Int32 save_gMinlen;
382 Int32* save_gLimit;
383 Int32* save_gBase;
384 Int32* save_gPerm;
385
386 }
387 DState;
388
389 /*-- Macros for decompression. --*/
390
391 #define BZ_GET_FAST(cccc) \
392 s->tPos = s->tt[s->tPos]; \
393 cccc = (UChar)(s->tPos & 0xff); \
394 s->tPos >>= 8;
395
396 #define BZ_GET_FAST_C(cccc) \
397 c_tPos = c_tt[c_tPos]; \
398 cccc = (UChar)(c_tPos & 0xff); \
399 c_tPos >>= 8;
400
401 #define SET_LL4(i,n) \
402 { if (((i) & 0x1) == 0) \
403 s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else \
404 s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4); \
405 }
406
407 #define GET_LL4(i) \
408 ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)
409
410 #define SET_LL(i,n) \
411 { s->ll16[i] = (UInt16)(n & 0x0000ffff); \
412 SET_LL4(i, n >> 16); \
413 }
414
415 #define GET_LL(i) \
416 (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16))
417
418 #define BZ_GET_SMALL(cccc) \
419 cccc = BZ2_indexIntoF ( s->tPos, s->cftab ); \
420 s->tPos = GET_LL(s->tPos);
421
422 /*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/
423
424 #ifndef NULL
425 #define NULL 0
426 #endif
427
428 /*-------------------------------------------------------------*/
429 /*--- Table for doing CRCs ---*/
430 /*--- crctable.c ---*/
431 /*-------------------------------------------------------------*/
432
433 /*--
434 I think this is an implementation of the AUTODIN-II,
435 Ethernet & FDDI 32-bit CRC standard. Vaguely derived
436 from code by Rob Warnock, in Section 51 of the
437 comp.compression FAQ.
438 --*/
439
440 UInt32 BZ2_crc32Table[256] = {
441
442 /*-- Ugly, innit? --*/
443
444 0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L,
445 0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L,
446 0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L,
447 0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL,
448 0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L,
449 0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L,
450 0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L,
451 0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL,
452 0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L,
453 0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L,
454 0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L,
455 0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL,
456 0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L,
457 0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L,
458 0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L,
459 0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL,
460 0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL,
461 0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L,
462 0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L,
463 0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL,
464 0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL,
465 0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L,
466 0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L,
467 0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL,
468 0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL,
469 0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L,
470 0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L,
471 0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL,
472 0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL,
473 0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L,
474 0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L,
475 0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL,
476 0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L,
477 0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL,
478 0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL,
479 0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L,
480 0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L,
481 0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL,
482 0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL,
483 0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L,
484 0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L,
485 0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL,
486 0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL,
487 0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L,
488 0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L,
489 0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL,
490 0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL,
491 0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L,
492 0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L,
493 0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL,
494 0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L,
495 0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L,
496 0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L,
497 0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL,
498 0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L,
499 0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L,
500 0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L,
501 0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL,
502 0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L,
503 0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L,
504 0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L,
505 0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL,
506 0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L,
507 0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L
508 };
509
510 /*-------------------------------------------------------------*/
511 /*--- Table for randomising repetitive blocks ---*/
512 /*--- randtable.c ---*/
513 /*-------------------------------------------------------------*/
514
515 Int32 BZ2_rNums[512] = {
516 619, 720, 127, 481, 931, 816, 813, 233, 566, 247,
517 985, 724, 205, 454, 863, 491, 741, 242, 949, 214,
518 733, 859, 335, 708, 621, 574, 73, 654, 730, 472,
519 419, 436, 278, 496, 867, 210, 399, 680, 480, 51,
520 878, 465, 811, 169, 869, 675, 611, 697, 867, 561,
521 862, 687, 507, 283, 482, 129, 807, 591, 733, 623,
522 150, 238, 59, 379, 684, 877, 625, 169, 643, 105,
523 170, 607, 520, 932, 727, 476, 693, 425, 174, 647,
524 73, 122, 335, 530, 442, 853, 695, 249, 445, 515,
525 909, 545, 703, 919, 874, 474, 882, 500, 594, 612,
526 641, 801, 220, 162, 819, 984, 589, 513, 495, 799,
527 161, 604, 958, 533, 221, 400, 386, 867, 600, 782,
528 382, 596, 414, 171, 516, 375, 682, 485, 911, 276,
529 98, 553, 163, 354, 666, 933, 424, 341, 533, 870,
530 227, 730, 475, 186, 263, 647, 537, 686, 600, 224,
531 469, 68, 770, 919, 190, 373, 294, 822, 808, 206,
532 184, 943, 795, 384, 383, 461, 404, 758, 839, 887,
533 715, 67, 618, 276, 204, 918, 873, 777, 604, 560,
534 951, 160, 578, 722, 79, 804, 96, 409, 713, 940,
535 652, 934, 970, 447, 318, 353, 859, 672, 112, 785,
536 645, 863, 803, 350, 139, 93, 354, 99, 820, 908,
537 609, 772, 154, 274, 580, 184, 79, 626, 630, 742,
538 653, 282, 762, 623, 680, 81, 927, 626, 789, 125,
539 411, 521, 938, 300, 821, 78, 343, 175, 128, 250,
540 170, 774, 972, 275, 999, 639, 495, 78, 352, 126,
541 857, 956, 358, 619, 580, 124, 737, 594, 701, 612,
542 669, 112, 134, 694, 363, 992, 809, 743, 168, 974,
543 944, 375, 748, 52, 600, 747, 642, 182, 862, 81,
544 344, 805, 988, 739, 511, 655, 814, 334, 249, 515,
545 897, 955, 664, 981, 649, 113, 974, 459, 893, 228,
546 433, 837, 553, 268, 926, 240, 102, 654, 459, 51,
547 686, 754, 806, 760, 493, 403, 415, 394, 687, 700,
548 946, 670, 656, 610, 738, 392, 760, 799, 887, 653,
549 978, 321, 576, 617, 626, 502, 894, 679, 243, 440,
550 680, 879, 194, 572, 640, 724, 926, 56, 204, 700,
551 707, 151, 457, 449, 797, 195, 791, 558, 945, 679,
552 297, 59, 87, 824, 713, 663, 412, 693, 342, 606,
553 134, 108, 571, 364, 631, 212, 174, 643, 304, 329,
554 343, 97, 430, 751, 497, 314, 983, 374, 822, 928,
555 140, 206, 73, 263, 980, 736, 876, 478, 430, 305,
556 170, 514, 364, 692, 829, 82, 855, 953, 676, 246,
557 369, 970, 294, 750, 807, 827, 150, 790, 288, 923,
558 804, 378, 215, 828, 592, 281, 565, 555, 710, 82,
559 896, 831, 547, 261, 524, 462, 293, 465, 502, 56,
560 661, 821, 976, 991, 658, 869, 905, 758, 745, 193,
561 768, 550, 608, 933, 378, 286, 215, 979, 792, 961,
562 61, 688, 793, 644, 986, 403, 106, 366, 905, 644,
563 372, 567, 466, 434, 645, 210, 389, 550, 919, 135,
564 780, 773, 635, 389, 707, 100, 626, 958, 165, 504,
565 920, 176, 193, 713, 857, 265, 203, 50, 668, 108,
566 645, 990, 626, 197, 510, 357, 358, 850, 858, 364,
567 936, 638
568 };
569
570
571 /*-- Core (low-level) library functions --*/
572
573 BZ_EXTERN int BZ_API(BZ2_bzCompressInit) (
574 bz_stream* strm,
575 int blockSize100k,
576 int verbosity,
577 int workFactor
578 );
579
580 BZ_EXTERN int BZ_API(BZ2_bzCompress) (
581 bz_stream* strm,
582 int action
583 );
584
585 BZ_EXTERN int BZ_API(BZ2_bzCompressEnd) (
586 bz_stream* strm
587 );
588
589 BZ_EXTERN int BZ_API(BZ2_bzDecompressInit) (
590 bz_stream *strm,
591 int verbosity,
592 int small
593 );
594
595 BZ_EXTERN int BZ_API(BZ2_bzDecompress) (
596 bz_stream* strm
597 );
598
599 BZ_EXTERN int BZ_API(BZ2_bzDecompressEnd) (
600 bz_stream *strm
601 );
602
603 /*-- Utility functions --*/
604
605 BZ_EXTERN int BZ_API(BZ2_bzBuffToBuffCompress) (
606 char* dest,
607 unsigned int* destLen,
608 char* source,
609 unsigned int sourceLen,
610 int blockSize100k,
611 int verbosity,
612 int workFactor
613 );
614
615 BZ_EXTERN int BZ_API(BZ2_bzBuffToBuffDecompress) (
616 char* dest,
617 unsigned int* destLen,
618 char* source,
619 unsigned int sourceLen,
620 int small,
621 int verbosity
622 );
623
624
625 /*--
626 Code contributed by Yoshioka Tsuneo
627 (QWF00133@niftyserve.or.jp/tsuneo-y@is.aist-nara.ac.jp),
628 to support better zlib compatibility.
629 This code is not _officially_ part of libbzip2 (yet);
630 I haven't tested it, documented it, or considered the
631 threading-safeness of it.
632 If this code breaks, please contact both Yoshioka and me.
633 --*/
634
635 BZ_EXTERN const char * BZ_API(BZ2_bzlibVersion) (
636 void
637 );
638
639
640
641 /*---------------------------------------------------*/
642
643 static
644 int bz_config_ok ( void )
645 {
646 if (sizeof(int) != 4) return 0;
647 if (sizeof(short) != 2) return 0;
648 if (sizeof(char) != 1) return 0;
649 return 1;
650 }
651
652 /*---------------------------------------------------*/
653 static
654 void* default_bzalloc ( void* opaque, Int32 items, Int32 size )
655 {
656 void* v = malloc ( items * size );
657 return v;
658 }
659
660 static
661 void default_bzfree ( void* opaque, void* addr )
662 {
663 if (addr != NULL) free ( addr );
664 }
665
666 /*---------------------------------------------------*/
667 int BZ_API(BZ2_bzDecompressInit)
668 ( bz_stream* strm,
669 int verbosity,
670 int small )
671 {
672 DState* s;
673
674 if (!bz_config_ok()) return BZ_CONFIG_ERROR;
675
676 if (strm == NULL) return BZ_PARAM_ERROR;
677 if (small != 0 && small != 1) return BZ_PARAM_ERROR;
678 if (verbosity < 0 || verbosity > 4) return BZ_PARAM_ERROR;
679
680 if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc;
681 if (strm->bzfree == NULL) strm->bzfree = default_bzfree;
682
683 s = BZALLOC( sizeof(DState) );
684 if (s == NULL) return BZ_MEM_ERROR;
685 s->strm = strm;
686 strm->state = s;
687 s->state = BZ_X_MAGIC_1;
688 s->bsLive = 0;
689 s->bsBuff = 0;
690 s->calculatedCombinedCRC = 0;
691 strm->total_in_lo32 = 0;
692 strm->total_in_hi32 = 0;
693 strm->total_out_lo32 = 0;
694 strm->total_out_hi32 = 0;
695 s->smallDecompress = (Bool)small;
696 s->ll4 = NULL;
697 s->ll16 = NULL;
698 s->tt = NULL;
699 s->currBlockNo = 0;
700 s->verbosity = verbosity;
701
702 return BZ_OK;
703 }
704
705
706 /*---------------------------------------------------*/
707 static
708 void unRLE_obuf_to_output_FAST ( DState* s )
709 {
710 UChar k1;
711
712 if (s->blockRandomised) {
713
714 while (True) {
715 /* try to finish existing run */
716 while (True) {
717 if (s->strm->avail_out == 0) return;
718 if (s->state_out_len == 0) break;
719 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
720 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
721 s->state_out_len--;
722 s->strm->next_out++;
723 s->strm->avail_out--;
724 s->strm->total_out_lo32++;
725 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
726 }
727
728 /* can a new run be started? */
729 if (s->nblock_used == s->save_nblock+1) return;
730
731
732 s->state_out_len = 1;
733 s->state_out_ch = s->k0;
734 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
735 k1 ^= BZ_RAND_MASK; s->nblock_used++;
736 if (s->nblock_used == s->save_nblock+1) continue;
737 if (k1 != s->k0) { s->k0 = k1; continue; };
738
739 s->state_out_len = 2;
740 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
741 k1 ^= BZ_RAND_MASK; s->nblock_used++;
742 if (s->nblock_used == s->save_nblock+1) continue;
743 if (k1 != s->k0) { s->k0 = k1; continue; };
744
745 s->state_out_len = 3;
746 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
747 k1 ^= BZ_RAND_MASK; s->nblock_used++;
748 if (s->nblock_used == s->save_nblock+1) continue;
749 if (k1 != s->k0) { s->k0 = k1; continue; };
750
751 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
752 k1 ^= BZ_RAND_MASK; s->nblock_used++;
753 s->state_out_len = ((Int32)k1) + 4;
754 BZ_GET_FAST(s->k0); BZ_RAND_UPD_MASK;
755 s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
756 }
757
758 } else {
759
760 /* restore */
761 UInt32 c_calculatedBlockCRC = s->calculatedBlockCRC;
762 UChar c_state_out_ch = s->state_out_ch;
763 Int32 c_state_out_len = s->state_out_len;
764 Int32 c_nblock_used = s->nblock_used;
765 Int32 c_k0 = s->k0;
766 UInt32* c_tt = s->tt;
767 UInt32 c_tPos = s->tPos;
768 char* cs_next_out = s->strm->next_out;
769 unsigned int cs_avail_out = s->strm->avail_out;
770 /* end restore */
771
772 UInt32 avail_out_INIT = cs_avail_out;
773 Int32 s_save_nblockPP = s->save_nblock+1;
774 unsigned int total_out_lo32_old;
775
776 while (True) {
777
778 /* try to finish existing run */
779 if (c_state_out_len > 0) {
780 while (True) {
781 if (cs_avail_out == 0) goto return_notr;
782 if (c_state_out_len == 1) break;
783 *( (UChar*)(cs_next_out) ) = c_state_out_ch;
784 BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
785 c_state_out_len--;
786 cs_next_out++;
787 cs_avail_out--;
788 }
789 s_state_out_len_eq_one:
790 {
791 if (cs_avail_out == 0) {
792 c_state_out_len = 1; goto return_notr;
793 };
794 *( (UChar*)(cs_next_out) ) = c_state_out_ch;
795 BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
796 cs_next_out++;
797 cs_avail_out--;
798 }
799 }
800 /* can a new run be started? */
801 if (c_nblock_used == s_save_nblockPP) {
802 c_state_out_len = 0; goto return_notr;
803 };
804 c_state_out_ch = c_k0;
805 BZ_GET_FAST_C(k1); c_nblock_used++;
806 if (k1 != c_k0) {
807 c_k0 = k1; goto s_state_out_len_eq_one;
808 };
809 if (c_nblock_used == s_save_nblockPP)
810 goto s_state_out_len_eq_one;
811
812 c_state_out_len = 2;
813 BZ_GET_FAST_C(k1); c_nblock_used++;
814 if (c_nblock_used == s_save_nblockPP) continue;
815 if (k1 != c_k0) { c_k0 = k1; continue; };
816
817 c_state_out_len = 3;
818 BZ_GET_FAST_C(k1); c_nblock_used++;
819 if (c_nblock_used == s_save_nblockPP) continue;
820 if (k1 != c_k0) { c_k0 = k1; continue; };
821
822 BZ_GET_FAST_C(k1); c_nblock_used++;
823 c_state_out_len = ((Int32)k1) + 4;
824 BZ_GET_FAST_C(c_k0); c_nblock_used++;
825 }
826
827 return_notr:
828 total_out_lo32_old = s->strm->total_out_lo32;
829 s->strm->total_out_lo32 += (avail_out_INIT - cs_avail_out);
830 if (s->strm->total_out_lo32 < total_out_lo32_old)
831 s->strm->total_out_hi32++;
832
833 /* save */
834 s->calculatedBlockCRC = c_calculatedBlockCRC;
835 s->state_out_ch = c_state_out_ch;
836 s->state_out_len = c_state_out_len;
837 s->nblock_used = c_nblock_used;
838 s->k0 = c_k0;
839 s->tt = c_tt;
840 s->tPos = c_tPos;
841 s->strm->next_out = cs_next_out;
842 s->strm->avail_out = cs_avail_out;
843 /* end save */
844 }
845 }
846
847 /*---------------------------------------------------*/
848 __inline__ Int32 BZ2_indexIntoF ( Int32 indx, Int32 *cftab )
849 {
850 Int32 nb, na, mid;
851 nb = 0;
852 na = 256;
853 do {
854 mid = (nb + na) >> 1;
855 if (indx >= cftab[mid]) nb = mid; else na = mid;
856 }
857 while (na - nb != 1);
858 return nb;
859 }
860
861 /*---------------------------------------------------*/
862 static
863 void unRLE_obuf_to_output_SMALL ( DState* s )
864 {
865 UChar k1;
866
867 if (s->blockRandomised) {
868
869 while (True) {
870 /* try to finish existing run */
871 while (True) {
872 if (s->strm->avail_out == 0) return;
873 if (s->state_out_len == 0) break;
874 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
875 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
876 s->state_out_len--;
877 s->strm->next_out++;
878 s->strm->avail_out--;
879 s->strm->total_out_lo32++;
880 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
881 }
882
883 /* can a new run be started? */
884 if (s->nblock_used == s->save_nblock+1) return;
885
886
887 s->state_out_len = 1;
888 s->state_out_ch = s->k0;
889 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
890 k1 ^= BZ_RAND_MASK; s->nblock_used++;
891 if (s->nblock_used == s->save_nblock+1) continue;
892 if (k1 != s->k0) { s->k0 = k1; continue; };
893
894 s->state_out_len = 2;
895 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
896 k1 ^= BZ_RAND_MASK; s->nblock_used++;
897 if (s->nblock_used == s->save_nblock+1) continue;
898 if (k1 != s->k0) { s->k0 = k1; continue; };
899
900 s->state_out_len = 3;
901 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
902 k1 ^= BZ_RAND_MASK; s->nblock_used++;
903 if (s->nblock_used == s->save_nblock+1) continue;
904 if (k1 != s->k0) { s->k0 = k1; continue; };
905
906 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
907 k1 ^= BZ_RAND_MASK; s->nblock_used++;
908 s->state_out_len = ((Int32)k1) + 4;
909 BZ_GET_SMALL(s->k0); BZ_RAND_UPD_MASK;
910 s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
911 }
912
913 } else {
914
915 while (True) {
916 /* try to finish existing run */
917 while (True) {
918 if (s->strm->avail_out == 0) return;
919 if (s->state_out_len == 0) break;
920 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
921 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
922 s->state_out_len--;
923 s->strm->next_out++;
924 s->strm->avail_out--;
925 s->strm->total_out_lo32++;
926 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
927 }
928
929 /* can a new run be started? */
930 if (s->nblock_used == s->save_nblock+1) return;
931
932 s->state_out_len = 1;
933 s->state_out_ch = s->k0;
934 BZ_GET_SMALL(k1); s->nblock_used++;
935 if (s->nblock_used == s->save_nblock+1) continue;
936 if (k1 != s->k0) { s->k0 = k1; continue; };
937
938 s->state_out_len = 2;
939 BZ_GET_SMALL(k1); s->nblock_used++;
940 if (s->nblock_used == s->save_nblock+1) continue;
941 if (k1 != s->k0) { s->k0 = k1; continue; };
942
943 s->state_out_len = 3;
944 BZ_GET_SMALL(k1); s->nblock_used++;
945 if (s->nblock_used == s->save_nblock+1) continue;
946 if (k1 != s->k0) { s->k0 = k1; continue; };
947
948 BZ_GET_SMALL(k1); s->nblock_used++;
949 s->state_out_len = ((Int32)k1) + 4;
950 BZ_GET_SMALL(s->k0); s->nblock_used++;
951 }
952
953 }
954 }
955
956 Int32 BZ2_decompress ( DState* s );
957
958 /*---------------------------------------------------*/
959 int BZ_API(BZ2_bzDecompress) ( bz_stream *strm )
960 {
961 DState* s;
962 if (strm == NULL) return BZ_PARAM_ERROR;
963 s = strm->state;
964 if (s == NULL) return BZ_PARAM_ERROR;
965 if (s->strm != strm) return BZ_PARAM_ERROR;
966
967 while (True) {
968 if (s->state == BZ_X_IDLE) return BZ_SEQUENCE_ERROR;
969 if (s->state == BZ_X_OUTPUT) {
970 if (s->smallDecompress)
971 unRLE_obuf_to_output_SMALL ( s ); else
972 unRLE_obuf_to_output_FAST ( s );
973 if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) {
974 BZ_FINALISE_CRC ( s->calculatedBlockCRC );
975 if (s->verbosity >= 3)
976 VPrintf2 ( " {0x%x, 0x%x}", s->storedBlockCRC,
977 s->calculatedBlockCRC );
978 if (s->verbosity >= 2) VPrintf0 ( "]" );
979 if (s->calculatedBlockCRC != s->storedBlockCRC)
980 return BZ_DATA_ERROR;
981 s->calculatedCombinedCRC
982 = (s->calculatedCombinedCRC << 1) |
983 (s->calculatedCombinedCRC >> 31);
984 s->calculatedCombinedCRC ^= s->calculatedBlockCRC;
985 s->state = BZ_X_BLKHDR_1;
986 } else {
987 return BZ_OK;
988 }
989 }
990 if (s->state >= BZ_X_MAGIC_1) {
991 Int32 r = BZ2_decompress ( s );
992 if (r == BZ_STREAM_END) {
993 if (s->verbosity >= 3)
994 VPrintf2 ( "\n combined CRCs: stored = 0x%x, computed = 0x%x",
995 s->storedCombinedCRC, s->calculatedCombinedCRC );
996 if (s->calculatedCombinedCRC != s->storedCombinedCRC)
997 return BZ_DATA_ERROR;
998 return r;
999 }
1000 if (s->state != BZ_X_OUTPUT) return r;
1001 }
1002 }
1003
1004 AssertH ( 0, 6001 );
1005
1006 return 0; /*NOTREACHED*/
1007 }
1008
1009 /*---------------------------------------------------*/
1010 int BZ_API(BZ2_bzDecompressEnd) ( bz_stream *strm )
1011 {
1012 DState* s;
1013 if (strm == NULL) return BZ_PARAM_ERROR;
1014 s = strm->state;
1015 if (s == NULL) return BZ_PARAM_ERROR;
1016 if (s->strm != strm) return BZ_PARAM_ERROR;
1017
1018 if (s->tt != NULL) BZFREE(s->tt);
1019 if (s->ll16 != NULL) BZFREE(s->ll16);
1020 if (s->ll4 != NULL) BZFREE(s->ll4);
1021
1022 BZFREE(strm->state);
1023 strm->state = NULL;
1024
1025 return BZ_OK;
1026 }
1027
1028 /*---------------------------------------------------*/
1029 int BZ_API(BZ2_bzBuffToBuffDecompress)
1030 ( char* dest,
1031 unsigned int* destLen,
1032 char* source,
1033 unsigned int sourceLen,
1034 int small,
1035 int verbosity )
1036 {
1037 bz_stream strm;
1038 int ret;
1039
1040 if (dest == NULL || destLen == NULL ||
1041 source == NULL ||
1042 (small != 0 && small != 1) ||
1043 verbosity < 0 || verbosity > 4)
1044 return BZ_PARAM_ERROR;
1045
1046 strm.bzalloc = NULL;
1047 strm.bzfree = NULL;
1048 strm.opaque = NULL;
1049 ret = BZ2_bzDecompressInit ( &strm, verbosity, small );
1050 if (ret != BZ_OK) return ret;
1051
1052 strm.next_in = source;
1053 strm.next_out = dest;
1054 strm.avail_in = sourceLen;
1055 strm.avail_out = *destLen;
1056
1057 ret = BZ2_bzDecompress ( &strm );
1058 if (ret == BZ_OK) goto output_overflow_or_eof;
1059 if (ret != BZ_STREAM_END) goto errhandler;
1060
1061 /* normal termination */
1062 *destLen -= strm.avail_out;
1063 BZ2_bzDecompressEnd ( &strm );
1064 return BZ_OK;
1065
1066 output_overflow_or_eof:
1067 if (strm.avail_out > 0) {
1068 BZ2_bzDecompressEnd ( &strm );
1069 return BZ_UNEXPECTED_EOF;
1070 } else {
1071 BZ2_bzDecompressEnd ( &strm );
1072 return BZ_OUTBUFF_FULL;
1073 };
1074
1075 errhandler:
1076 BZ2_bzDecompressEnd ( &strm );
1077 return ret;
1078 }
1079
1080 /*---------------------------------------------------*/
1081 static
1082 void makeMaps_d ( DState* s )
1083 {
1084 Int32 i;
1085 s->nInUse = 0;
1086 for (i = 0; i < 256; i++)
1087 if (s->inUse[i]) {
1088 s->seqToUnseq[s->nInUse] = i;
1089 s->nInUse++;
1090 }
1091 }
1092
1093 /*---------------------------------------------------*/
1094 #define RETURN(rrr) \
1095 { retVal = rrr; goto save_state_and_return; };
1096
1097 #define GET_BITS(lll,vvv,nnn) \
1098 case lll: s->state = lll; \
1099 while (True) { \
1100 if (s->bsLive >= nnn) { \
1101 UInt32 v; \
1102 v = (s->bsBuff >> \
1103 (s->bsLive-nnn)) & ((1 << nnn)-1); \
1104 s->bsLive -= nnn; \
1105 vvv = v; \
1106 break; \
1107 } \
1108 if (s->strm->avail_in == 0) RETURN(BZ_OK); \
1109 s->bsBuff \
1110 = (s->bsBuff << 8) | \
1111 ((UInt32) \
1112 (*((UChar*)(s->strm->next_in)))); \
1113 s->bsLive += 8; \
1114 s->strm->next_in++; \
1115 s->strm->avail_in--; \
1116 s->strm->total_in_lo32++; \
1117 if (s->strm->total_in_lo32 == 0) \
1118 s->strm->total_in_hi32++; \
1119 }
1120
1121 #define GET_UCHAR(lll,uuu) \
1122 GET_BITS(lll,uuu,8)
1123
1124 #define GET_BIT(lll,uuu) \
1125 GET_BITS(lll,uuu,1)
1126
1127 /*---------------------------------------------------*/
1128 #define GET_MTF_VAL(label1,label2,lval) \
1129 { \
1130 if (groupPos == 0) { \
1131 groupNo++; \
1132 if (groupNo >= nSelectors) \
1133 RETURN(BZ_DATA_ERROR); \
1134 groupPos = BZ_G_SIZE; \
1135 gSel = s->selector[groupNo]; \
1136 gMinlen = s->minLens[gSel]; \
1137 gLimit = &(s->limit[gSel][0]); \
1138 gPerm = &(s->perm[gSel][0]); \
1139 gBase = &(s->base[gSel][0]); \
1140 } \
1141 groupPos--; \
1142 zn = gMinlen; \
1143 GET_BITS(label1, zvec, zn); \
1144 while (1) { \
1145 if (zn > 20 /* the longest code */) \
1146 RETURN(BZ_DATA_ERROR); \
1147 if (zvec <= gLimit[zn]) break; \
1148 zn++; \
1149 GET_BIT(label2, zj); \
1150 zvec = (zvec << 1) | zj; \
1151 }; \
1152 if (zvec - gBase[zn] < 0 \
1153 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \
1154 RETURN(BZ_DATA_ERROR); \
1155 lval = gPerm[zvec - gBase[zn]]; \
1156 }
1157
1158 /*---------------------------------------------------*/
1159 void BZ2_hbCreateDecodeTables ( Int32 *limit,
1160 Int32 *base,
1161 Int32 *perm,
1162 UChar *length,
1163 Int32 minLen,
1164 Int32 maxLen,
1165 Int32 alphaSize )
1166 {
1167 Int32 pp, i, j, vec;
1168
1169 pp = 0;
1170 for (i = minLen; i <= maxLen; i++)
1171 for (j = 0; j < alphaSize; j++)
1172 if (length[j] == i) { perm[pp] = j; pp++; };
1173
1174 for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
1175 for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
1176
1177 for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
1178
1179 for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
1180 vec = 0;
1181
1182 for (i = minLen; i <= maxLen; i++) {
1183 vec += (base[i+1] - base[i]);
1184 limit[i] = vec-1;
1185 vec <<= 1;
1186 }
1187 for (i = minLen + 1; i <= maxLen; i++)
1188 base[i] = ((limit[i-1] + 1) << 1) - base[i];
1189 }
1190
1191
1192 /*---------------------------------------------------*/
1193 Int32 BZ2_decompress ( DState* s )
1194 {
1195 UChar uc;
1196 Int32 retVal;
1197 Int32 minLen, maxLen;
1198 bz_stream* strm = s->strm;
1199
1200 /* stuff that needs to be saved/restored */
1201 Int32 i;
1202 Int32 j;
1203 Int32 t;
1204 Int32 alphaSize;
1205 Int32 nGroups;
1206 Int32 nSelectors;
1207 Int32 EOB;
1208 Int32 groupNo;
1209 Int32 groupPos;
1210 Int32 nextSym;
1211 Int32 nblockMAX;
1212 Int32 nblock;
1213 Int32 es;
1214 Int32 N;
1215 Int32 curr;
1216 Int32 zt;
1217 Int32 zn;
1218 Int32 zvec;
1219 Int32 zj;
1220 Int32 gSel;
1221 Int32 gMinlen;
1222 Int32* gLimit;
1223 Int32* gBase;
1224 Int32* gPerm;
1225
1226 if (s->state == BZ_X_MAGIC_1) {
1227 /*initialise the save area*/
1228 s->save_i = 0;
1229 s->save_j = 0;
1230 s->save_t = 0;
1231 s->save_alphaSize = 0;
1232 s->save_nGroups = 0;
1233 s->save_nSelectors = 0;
1234 s->save_EOB = 0;
1235 s->save_groupNo = 0;
1236 s->save_groupPos = 0;
1237 s->save_nextSym = 0;
1238 s->save_nblockMAX = 0;
1239 s->save_nblock = 0;
1240 s->save_es = 0;
1241 s->save_N = 0;
1242 s->save_curr = 0;
1243 s->save_zt = 0;
1244 s->save_zn = 0;
1245 s->save_zvec = 0;
1246 s->save_zj = 0;
1247 s->save_gSel = 0;
1248 s->save_gMinlen = 0;
1249 s->save_gLimit = NULL;
1250 s->save_gBase = NULL;
1251 s->save_gPerm = NULL;
1252 }
1253
1254 /*restore from the save area*/
1255 i = s->save_i;
1256 j = s->save_j;
1257 t = s->save_t;
1258 alphaSize = s->save_alphaSize;
1259 nGroups = s->save_nGroups;
1260 nSelectors = s->save_nSelectors;
1261 EOB = s->save_EOB;
1262 groupNo = s->save_groupNo;
1263 groupPos = s->save_groupPos;
1264 nextSym = s->save_nextSym;
1265 nblockMAX = s->save_nblockMAX;
1266 nblock = s->save_nblock;
1267 es = s->save_es;
1268 N = s->save_N;
1269 curr = s->save_curr;
1270 zt = s->save_zt;
1271 zn = s->save_zn;
1272 zvec = s->save_zvec;
1273 zj = s->save_zj;
1274 gSel = s->save_gSel;
1275 gMinlen = s->save_gMinlen;
1276 gLimit = s->save_gLimit;
1277 gBase = s->save_gBase;
1278 gPerm = s->save_gPerm;
1279
1280 retVal = BZ_OK;
1281
1282 switch (s->state) {
1283
1284 GET_UCHAR(BZ_X_MAGIC_1, uc);
1285 if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);
1286
1287 GET_UCHAR(BZ_X_MAGIC_2, uc);
1288 if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);
1289
1290 GET_UCHAR(BZ_X_MAGIC_3, uc)
1291 if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);
1292
1293 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
1294 if (s->blockSize100k < (BZ_HDR_0 + 1) ||
1295 s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
1296 s->blockSize100k -= BZ_HDR_0;
1297
1298 if (s->smallDecompress) {
1299 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
1300 s->ll4 = BZALLOC(
1301 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
1302 );
1303 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
1304 } else {
1305 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
1306 if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
1307 }
1308
1309 GET_UCHAR(BZ_X_BLKHDR_1, uc);
1310
1311 if (uc == 0x17) goto endhdr_2;
1312 if (uc != 0x31) RETURN(BZ_DATA_ERROR);
1313 GET_UCHAR(BZ_X_BLKHDR_2, uc);
1314 if (uc != 0x41) RETURN(BZ_DATA_ERROR);
1315 GET_UCHAR(BZ_X_BLKHDR_3, uc);
1316 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
1317 GET_UCHAR(BZ_X_BLKHDR_4, uc);
1318 if (uc != 0x26) RETURN(BZ_DATA_ERROR);
1319 GET_UCHAR(BZ_X_BLKHDR_5, uc);
1320 if (uc != 0x53) RETURN(BZ_DATA_ERROR);
1321 GET_UCHAR(BZ_X_BLKHDR_6, uc);
1322 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
1323
1324 s->currBlockNo++;
1325 if (s->verbosity >= 2)
1326 VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );
1327
1328 s->storedBlockCRC = 0;
1329 GET_UCHAR(BZ_X_BCRC_1, uc);
1330 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1331 GET_UCHAR(BZ_X_BCRC_2, uc);
1332 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1333 GET_UCHAR(BZ_X_BCRC_3, uc);
1334 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1335 GET_UCHAR(BZ_X_BCRC_4, uc);
1336 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1337
1338 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
1339
1340 s->origPtr = 0;
1341 GET_UCHAR(BZ_X_ORIGPTR_1, uc);
1342 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
1343 GET_UCHAR(BZ_X_ORIGPTR_2, uc);
1344 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
1345 GET_UCHAR(BZ_X_ORIGPTR_3, uc);
1346 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
1347
1348 if (s->origPtr < 0)
1349 RETURN(BZ_DATA_ERROR);
1350 if (s->origPtr > 10 + 100000*s->blockSize100k)
1351 RETURN(BZ_DATA_ERROR);
1352
1353 /*--- Receive the mapping table ---*/
1354 for (i = 0; i < 16; i++) {
1355 GET_BIT(BZ_X_MAPPING_1, uc);
1356 if (uc == 1)
1357 s->inUse16[i] = True; else
1358 s->inUse16[i] = False;
1359 }
1360
1361 for (i = 0; i < 256; i++) s->inUse[i] = False;
1362
1363 for (i = 0; i < 16; i++)
1364 if (s->inUse16[i])
1365 for (j = 0; j < 16; j++) {
1366 GET_BIT(BZ_X_MAPPING_2, uc);
1367 if (uc == 1) s->inUse[i * 16 + j] = True;
1368 }
1369 makeMaps_d ( s );
1370 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
1371 alphaSize = s->nInUse+2;
1372
1373 /*--- Now the selectors ---*/
1374 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
1375 if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
1376 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
1377 if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
1378 for (i = 0; i < nSelectors; i++) {
1379 j = 0;
1380 while (True) {
1381 GET_BIT(BZ_X_SELECTOR_3, uc);
1382 if (uc == 0) break;
1383 j++;
1384 if (j >= nGroups) RETURN(BZ_DATA_ERROR);
1385 }
1386 s->selectorMtf[i] = j;
1387 }
1388
1389 /*--- Undo the MTF values for the selectors. ---*/
1390 {
1391 UChar pos[BZ_N_GROUPS], tmp, v;
1392 for (v = 0; v < nGroups; v++) pos[v] = v;
1393
1394 for (i = 0; i < nSelectors; i++) {
1395 v = s->selectorMtf[i];
1396 tmp = pos[v];
1397 while (v > 0) { pos[v] = pos[v-1]; v--; }
1398 pos[0] = tmp;
1399 s->selector[i] = tmp;
1400 }
1401 }
1402
1403 /*--- Now the coding tables ---*/
1404 for (t = 0; t < nGroups; t++) {
1405 GET_BITS(BZ_X_CODING_1, curr, 5);
1406 for (i = 0; i < alphaSize; i++) {
1407 while (True) {
1408 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
1409 GET_BIT(BZ_X_CODING_2, uc);
1410 if (uc == 0) break;
1411 GET_BIT(BZ_X_CODING_3, uc);
1412 if (uc == 0) curr++; else curr--;
1413 }
1414 s->len[t][i] = curr;
1415 }
1416 }
1417
1418 /*--- Create the Huffman decoding tables ---*/
1419 for (t = 0; t < nGroups; t++) {
1420 minLen = 32;
1421 maxLen = 0;
1422 for (i = 0; i < alphaSize; i++) {
1423 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
1424 if (s->len[t][i] < minLen) minLen = s->len[t][i];
1425 }
1426 BZ2_hbCreateDecodeTables (
1427 &(s->limit[t][0]),
1428 &(s->base[t][0]),
1429 &(s->perm[t][0]),
1430 &(s->len[t][0]),
1431 minLen, maxLen, alphaSize
1432 );
1433 s->minLens[t] = minLen;
1434 }
1435
1436 /*--- Now the MTF values ---*/
1437
1438 EOB = s->nInUse+1;
1439 nblockMAX = 100000 * s->blockSize100k;
1440 groupNo = -1;
1441 groupPos = 0;
1442
1443 for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
1444
1445 /*-- MTF init --*/
1446 {
1447 Int32 ii, jj, kk;
1448 kk = MTFA_SIZE-1;
1449 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
1450 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
1451 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
1452 kk--;
1453 }
1454 s->mtfbase[ii] = kk + 1;
1455 }
1456 }
1457 /*-- end MTF init --*/
1458
1459 nblock = 0;
1460 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
1461
1462 while (True) {
1463
1464 if (nextSym == EOB) break;
1465
1466 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
1467
1468 es = -1;
1469 N = 1;
1470 do {
1471 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
1472 if (nextSym == BZ_RUNB) es = es + (1+1) * N;
1473 N = N * 2;
1474 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
1475 }
1476 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
1477
1478 es++;
1479 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
1480 s->unzftab[uc] += es;
1481
1482 if (s->smallDecompress)
1483 while (es > 0) {
1484 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
1485 s->ll16[nblock] = (UInt16)uc;
1486 nblock++;
1487 es--;
1488 }
1489 else
1490 while (es > 0) {
1491 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
1492 s->tt[nblock] = (UInt32)uc;
1493 nblock++;
1494 es--;
1495 };
1496
1497 continue;
1498
1499 } else {
1500
1501 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
1502
1503 /*-- uc = MTF ( nextSym-1 ) --*/
1504 {
1505 Int32 ii, jj, kk, pp, lno, off;
1506 UInt32 nn;
1507 nn = (UInt32)(nextSym - 1);
1508
1509 if (nn < MTFL_SIZE) {
1510 /* avoid general-case expense */
1511 pp = s->mtfbase[0];
1512 uc = s->mtfa[pp+nn];
1513 while (nn > 3) {
1514 Int32 z = pp+nn;
1515 s->mtfa[(z) ] = s->mtfa[(z)-1];
1516 s->mtfa[(z)-1] = s->mtfa[(z)-2];
1517 s->mtfa[(z)-2] = s->mtfa[(z)-3];
1518 s->mtfa[(z)-3] = s->mtfa[(z)-4];
1519 nn -= 4;
1520 }
1521 while (nn > 0) {
1522 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
1523 };
1524 s->mtfa[pp] = uc;
1525 } else {
1526 /* general case */
1527 lno = nn / MTFL_SIZE;
1528 off = nn % MTFL_SIZE;
1529 pp = s->mtfbase[lno] + off;
1530 uc = s->mtfa[pp];
1531 while (pp > s->mtfbase[lno]) {
1532 s->mtfa[pp] = s->mtfa[pp-1]; pp--;
1533 };
1534 s->mtfbase[lno]++;
1535 while (lno > 0) {
1536 s->mtfbase[lno]--;
1537 s->mtfa[s->mtfbase[lno]]
1538 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
1539 lno--;
1540 }
1541 s->mtfbase[0]--;
1542 s->mtfa[s->mtfbase[0]] = uc;
1543 if (s->mtfbase[0] == 0) {
1544 kk = MTFA_SIZE-1;
1545 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
1546 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
1547 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
1548 kk--;
1549 }
1550 s->mtfbase[ii] = kk + 1;
1551 }
1552 }
1553 }
1554 }
1555 /*-- end uc = MTF ( nextSym-1 ) --*/
1556
1557 s->unzftab[s->seqToUnseq[uc]]++;
1558 if (s->smallDecompress)
1559 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
1560 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]);
1561 nblock++;
1562
1563 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
1564 continue;
1565 }
1566 }
1567
1568 /* Now we know what nblock is, we can do a better sanity
1569 check on s->origPtr.
1570 */
1571 if (s->origPtr < 0 || s->origPtr >= nblock)
1572 RETURN(BZ_DATA_ERROR);
1573
1574 s->state_out_len = 0;
1575 s->state_out_ch = 0;
1576 BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
1577 s->state = BZ_X_OUTPUT;
1578 if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
1579
1580 /*-- Set up cftab to facilitate generation of T^(-1) --*/
1581 s->cftab[0] = 0;
1582 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
1583 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
1584
1585 if (s->smallDecompress) {
1586
1587 /*-- Make a copy of cftab, used in generation of T --*/
1588 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
1589
1590 /*-- compute the T vector --*/
1591 for (i = 0; i < nblock; i++) {
1592 uc = (UChar)(s->ll16[i]);
1593 SET_LL(i, s->cftabCopy[uc]);
1594 s->cftabCopy[uc]++;
1595 }
1596
1597 /*-- Compute T^(-1) by pointer reversal on T --*/
1598 i = s->origPtr;
1599 j = GET_LL(i);
1600 do {
1601 Int32 tmp = GET_LL(j);
1602 SET_LL(j, i);
1603 i = j;
1604 j = tmp;
1605 }
1606 while (i != s->origPtr);
1607
1608 s->tPos = s->origPtr;
1609 s->nblock_used = 0;
1610 if (s->blockRandomised) {
1611 BZ_RAND_INIT_MASK;
1612 BZ_GET_SMALL(s->k0); s->nblock_used++;
1613 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
1614 } else {
1615 BZ_GET_SMALL(s->k0); s->nblock_used++;
1616 }
1617
1618 } else {
1619
1620 /*-- compute the T^(-1) vector --*/
1621 for (i = 0; i < nblock; i++) {
1622 uc = (UChar)(s->tt[i] & 0xff);
1623 s->tt[s->cftab[uc]] |= (i << 8);
1624 s->cftab[uc]++;
1625 }
1626
1627 s->tPos = s->tt[s->origPtr] >> 8;
1628 s->nblock_used = 0;
1629 if (s->blockRandomised) {
1630 BZ_RAND_INIT_MASK;
1631 BZ_GET_FAST(s->k0); s->nblock_used++;
1632 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
1633 } else {
1634 BZ_GET_FAST(s->k0); s->nblock_used++;
1635 }
1636
1637 }
1638
1639 RETURN(BZ_OK);
1640
1641
1642
1643 endhdr_2:
1644
1645 GET_UCHAR(BZ_X_ENDHDR_2, uc);
1646 if (uc != 0x72) RETURN(BZ_DATA_ERROR);
1647 GET_UCHAR(BZ_X_ENDHDR_3, uc);
1648 if (uc != 0x45) RETURN(BZ_DATA_ERROR);
1649 GET_UCHAR(BZ_X_ENDHDR_4, uc);
1650 if (uc != 0x38) RETURN(BZ_DATA_ERROR);
1651 GET_UCHAR(BZ_X_ENDHDR_5, uc);
1652 if (uc != 0x50) RETURN(BZ_DATA_ERROR);
1653 GET_UCHAR(BZ_X_ENDHDR_6, uc);
1654 if (uc != 0x90) RETURN(BZ_DATA_ERROR);
1655
1656 s->storedCombinedCRC = 0;
1657 GET_UCHAR(BZ_X_CCRC_1, uc);
1658 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1659 GET_UCHAR(BZ_X_CCRC_2, uc);
1660 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1661 GET_UCHAR(BZ_X_CCRC_3, uc);
1662 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1663 GET_UCHAR(BZ_X_CCRC_4, uc);
1664 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1665
1666 s->state = BZ_X_IDLE;
1667 RETURN(BZ_STREAM_END);
1668
1669 default: AssertH ( False, 4001 ); }
1670 AssertH ( False, 4002 );
1671
1672 save_state_and_return:
1673
1674 s->save_i = i;
1675 s->save_j = j;
1676 s->save_t = t;
1677 s->save_alphaSize = alphaSize;
1678 s->save_nGroups = nGroups;
1679 s->save_nSelectors = nSelectors;
1680 s->save_EOB = EOB;
1681 s->save_groupNo = groupNo;
1682 s->save_groupPos = groupPos;
1683 s->save_nextSym = nextSym;
1684 s->save_nblockMAX = nblockMAX;
1685 s->save_nblock = nblock;
1686 s->save_es = es;
1687 s->save_N = N;
1688 s->save_curr = curr;
1689 s->save_zt = zt;
1690 s->save_zn = zn;
1691 s->save_zvec = zvec;
1692 s->save_zj = zj;
1693 s->save_gSel = gSel;
1694 s->save_gMinlen = gMinlen;
1695 s->save_gLimit = gLimit;
1696 s->save_gBase = gBase;
1697 s->save_gPerm = gPerm;
1698
1699 return retVal;
1700 }
1701
1702 /*---------------------------------------------------*/
1703 #define WEIGHTOF(zz0) ((zz0) & 0xffffff00)
1704 #define DEPTHOF(zz1) ((zz1) & 0x000000ff)
1705 #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
1706
1707 #define ADDWEIGHTS(zw1,zw2) \
1708 (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \
1709 (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
1710
1711 #define UPHEAP(z) \
1712 { \
1713 Int32 zz, tmp; \
1714 zz = z; tmp = heap[zz]; \
1715 while (weight[tmp] < weight[heap[zz >> 1]]) { \
1716 heap[zz] = heap[zz >> 1]; \
1717 zz >>= 1; \
1718 } \
1719 heap[zz] = tmp; \
1720 }
1721
1722 #define DOWNHEAP(z) \
1723 { \
1724 Int32 zz, yy, tmp; \
1725 zz = z; tmp = heap[zz]; \
1726 while (True) { \
1727 yy = zz << 1; \
1728 if (yy > nHeap) break; \
1729 if (yy < nHeap && \
1730 weight[heap[yy+1]] < weight[heap[yy]]) \
1731 yy++; \
1732 if (weight[tmp] < weight[heap[yy]]) break; \
1733 heap[zz] = heap[yy]; \
1734 zz = yy; \
1735 } \
1736 heap[zz] = tmp; \
1737 }
1738
1739 /*---------------------------------------------------*/
1740 void BZ2_hbMakeCodeLengths ( UChar *len,
1741 Int32 *freq,
1742 Int32 alphaSize,
1743 Int32 maxLen )
1744 {
1745 /*--
1746 Nodes and heap entries run from 1. Entry 0
1747 for both the heap and nodes is a sentinel.
1748 --*/
1749 Int32 nNodes, nHeap, n1, n2, i, j, k;
1750 Bool tooLong;
1751
1752 Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ];
1753 Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
1754 Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
1755
1756 for (i = 0; i < alphaSize; i++)
1757 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
1758
1759 while (True) {
1760
1761 nNodes = alphaSize;
1762 nHeap = 0;
1763
1764 heap[0] = 0;
1765 weight[0] = 0;
1766 parent[0] = -2;
1767
1768 for (i = 1; i <= alphaSize; i++) {
1769 parent[i] = -1;
1770 nHeap++;
1771 heap[nHeap] = i;
1772 UPHEAP(nHeap);
1773 }
1774
1775 AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
1776
1777 while (nHeap > 1) {
1778 n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
1779 n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
1780 nNodes++;
1781 parent[n1] = parent[n2] = nNodes;
1782 weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
1783 parent[nNodes] = -1;
1784 nHeap++;
1785 heap[nHeap] = nNodes;
1786 UPHEAP(nHeap);
1787 }
1788
1789 AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
1790
1791 tooLong = False;
1792 for (i = 1; i <= alphaSize; i++) {
1793 j = 0;
1794 k = i;
1795 while (parent[k] >= 0) { k = parent[k]; j++; }
1796 len[i-1] = j;
1797 if (j > maxLen) tooLong = True;
1798 }
1799
1800 if (! tooLong) break;
1801
1802 for (i = 1; i < alphaSize; i++) {
1803 j = weight[i] >> 8;
1804 j = 1 + (j / 2);
1805 weight[i] = j << 8;
1806 }
1807 }
1808 }
1809
1810
1811 /*---------------------------------------------------*/
1812 void BZ2_hbAssignCodes ( Int32 *code,
1813 UChar *length,
1814 Int32 minLen,
1815 Int32 maxLen,
1816 Int32 alphaSize )
1817 {
1818 Int32 n, vec, i;
1819
1820 vec = 0;
1821 for (n = minLen; n <= maxLen; n++) {
1822 for (i = 0; i < alphaSize; i++)
1823 if (length[i] == n) { code[i] = vec; vec++; };
1824 vec <<= 1;
1825 }
1826 }
1827
1828 /* the-end. */
Tomato firmware and modifications.