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