Commit | Line | Data |
---|---|---|
bdb7fd9f RGS |
1 | |
2 | /*-------------------------------------------------------------*/ | |
3 | /*--- Private header file for the library. ---*/ | |
4 | /*--- bzlib_private.h ---*/ | |
5 | /*-------------------------------------------------------------*/ | |
6 | ||
7 | /* ------------------------------------------------------------------ | |
8 | This file is part of bzip2/libbzip2, a program and library for | |
9 | lossless, block-sorting data compression. | |
10 | ||
daec2498 CBW |
11 | bzip2/libbzip2 version 1.0.6 of 6 September 2010 |
12 | Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org> | |
bdb7fd9f RGS |
13 | |
14 | Please read the WARNING, DISCLAIMER and PATENTS sections in the | |
15 | README file. | |
16 | ||
17 | This program is released under the terms of the license contained | |
18 | in the file LICENSE. | |
19 | ------------------------------------------------------------------ */ | |
20 | ||
21 | ||
22 | #ifndef _BZLIB_PRIVATE_H | |
23 | #define _BZLIB_PRIVATE_H | |
24 | ||
25 | #include <stdlib.h> | |
26 | ||
27 | #ifndef BZ_NO_STDIO | |
28 | #include <stdio.h> | |
29 | #include <ctype.h> | |
30 | #include <string.h> | |
31 | #endif | |
32 | ||
33 | #include "bzlib.h" | |
34 | ||
35 | ||
36 | ||
37 | /*-- General stuff. --*/ | |
38 | ||
daec2498 | 39 | #define BZ_VERSION "1.0.6, 6-Sept-2010" |
bdb7fd9f RGS |
40 | |
41 | typedef char Char; | |
42 | typedef unsigned char Bool; | |
43 | typedef unsigned char UChar; | |
44 | typedef int Int32; | |
45 | typedef unsigned int UInt32; | |
46 | typedef short Int16; | |
47 | typedef unsigned short UInt16; | |
48 | ||
49 | #define True ((Bool)1) | |
50 | #define False ((Bool)0) | |
51 | ||
52 | #ifndef __GNUC__ | |
53 | #define __inline__ /* */ | |
54 | #endif | |
55 | ||
56 | #ifndef BZ_NO_STDIO | |
57 | ||
58 | extern void BZ2_bz__AssertH__fail ( int errcode ); | |
59 | #define AssertH(cond,errcode) \ | |
60 | { if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); } | |
61 | ||
62 | #if BZ_DEBUG | |
63 | #define AssertD(cond,msg) \ | |
64 | { if (!(cond)) { \ | |
65 | fprintf ( stderr, \ | |
66 | "\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\ | |
67 | exit(1); \ | |
68 | }} | |
69 | #else | |
70 | #define AssertD(cond,msg) /* */ | |
71 | #endif | |
72 | ||
73 | #define VPrintf0(zf) \ | |
74 | fprintf(stderr,zf) | |
75 | #define VPrintf1(zf,za1) \ | |
76 | fprintf(stderr,zf,za1) | |
77 | #define VPrintf2(zf,za1,za2) \ | |
78 | fprintf(stderr,zf,za1,za2) | |
79 | #define VPrintf3(zf,za1,za2,za3) \ | |
80 | fprintf(stderr,zf,za1,za2,za3) | |
81 | #define VPrintf4(zf,za1,za2,za3,za4) \ | |
82 | fprintf(stderr,zf,za1,za2,za3,za4) | |
83 | #define VPrintf5(zf,za1,za2,za3,za4,za5) \ | |
84 | fprintf(stderr,zf,za1,za2,za3,za4,za5) | |
85 | ||
86 | #else | |
87 | ||
88 | extern void bz_internal_error ( int errcode ); | |
89 | #define AssertH(cond,errcode) \ | |
90 | { if (!(cond)) bz_internal_error ( errcode ); } | |
91 | #define AssertD(cond,msg) do { } while (0) | |
92 | #define VPrintf0(zf) do { } while (0) | |
93 | #define VPrintf1(zf,za1) do { } while (0) | |
94 | #define VPrintf2(zf,za1,za2) do { } while (0) | |
95 | #define VPrintf3(zf,za1,za2,za3) do { } while (0) | |
96 | #define VPrintf4(zf,za1,za2,za3,za4) do { } while (0) | |
97 | #define VPrintf5(zf,za1,za2,za3,za4,za5) do { } while (0) | |
98 | ||
99 | #endif | |
100 | ||
101 | ||
102 | #define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1) | |
103 | #define BZFREE(ppp) (strm->bzfree)(strm->opaque,(ppp)) | |
104 | ||
105 | ||
106 | /*-- Header bytes. --*/ | |
107 | ||
108 | #define BZ_HDR_B 0x42 /* 'B' */ | |
109 | #define BZ_HDR_Z 0x5a /* 'Z' */ | |
110 | #define BZ_HDR_h 0x68 /* 'h' */ | |
111 | #define BZ_HDR_0 0x30 /* '0' */ | |
112 | ||
113 | /*-- Constants for the back end. --*/ | |
114 | ||
115 | #define BZ_MAX_ALPHA_SIZE 258 | |
116 | #define BZ_MAX_CODE_LEN 23 | |
117 | ||
118 | #define BZ_RUNA 0 | |
119 | #define BZ_RUNB 1 | |
120 | ||
121 | #define BZ_N_GROUPS 6 | |
122 | #define BZ_G_SIZE 50 | |
123 | #define BZ_N_ITERS 4 | |
124 | ||
125 | #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE)) | |
126 | ||
127 | ||
128 | ||
129 | /*-- Stuff for randomising repetitive blocks. --*/ | |
130 | ||
9e7c8eb7 | 131 | extern const Int32 BZ2_rNums[512]; |
bdb7fd9f RGS |
132 | |
133 | #define BZ_RAND_DECLS \ | |
134 | Int32 rNToGo; \ | |
135 | Int32 rTPos \ | |
136 | ||
137 | #define BZ_RAND_INIT_MASK \ | |
138 | s->rNToGo = 0; \ | |
139 | s->rTPos = 0 \ | |
140 | ||
141 | #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0) | |
142 | ||
143 | #define BZ_RAND_UPD_MASK \ | |
144 | if (s->rNToGo == 0) { \ | |
145 | s->rNToGo = BZ2_rNums[s->rTPos]; \ | |
146 | s->rTPos++; \ | |
147 | if (s->rTPos == 512) s->rTPos = 0; \ | |
148 | } \ | |
149 | s->rNToGo--; | |
150 | ||
151 | ||
152 | ||
153 | /*-- Stuff for doing CRCs. --*/ | |
154 | ||
9e7c8eb7 | 155 | extern const UInt32 BZ2_crc32Table[256]; |
bdb7fd9f RGS |
156 | |
157 | #define BZ_INITIALISE_CRC(crcVar) \ | |
158 | { \ | |
159 | crcVar = 0xffffffffL; \ | |
160 | } | |
161 | ||
162 | #define BZ_FINALISE_CRC(crcVar) \ | |
163 | { \ | |
164 | crcVar = ~(crcVar); \ | |
165 | } | |
166 | ||
167 | #define BZ_UPDATE_CRC(crcVar,cha) \ | |
168 | { \ | |
169 | crcVar = (crcVar << 8) ^ \ | |
170 | BZ2_crc32Table[(crcVar >> 24) ^ \ | |
171 | ((UChar)cha)]; \ | |
172 | } | |
173 | ||
174 | ||
175 | ||
176 | /*-- States and modes for compression. --*/ | |
177 | ||
178 | #define BZ_M_IDLE 1 | |
179 | #define BZ_M_RUNNING 2 | |
180 | #define BZ_M_FLUSHING 3 | |
181 | #define BZ_M_FINISHING 4 | |
182 | ||
183 | #define BZ_S_OUTPUT 1 | |
184 | #define BZ_S_INPUT 2 | |
185 | ||
186 | #define BZ_N_RADIX 2 | |
187 | #define BZ_N_QSORT 12 | |
188 | #define BZ_N_SHELL 18 | |
189 | #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2) | |
190 | ||
191 | ||
192 | ||
193 | ||
194 | /*-- Structure holding all the compression-side stuff. --*/ | |
195 | ||
196 | typedef | |
197 | struct { | |
198 | /* pointer back to the struct bz_stream */ | |
199 | bz_stream* strm; | |
200 | ||
201 | /* mode this stream is in, and whether inputting */ | |
202 | /* or outputting data */ | |
203 | Int32 mode; | |
204 | Int32 state; | |
205 | ||
206 | /* remembers avail_in when flush/finish requested */ | |
207 | UInt32 avail_in_expect; | |
208 | ||
209 | /* for doing the block sorting */ | |
210 | UInt32* arr1; | |
211 | UInt32* arr2; | |
212 | UInt32* ftab; | |
213 | Int32 origPtr; | |
214 | ||
215 | /* aliases for arr1 and arr2 */ | |
216 | UInt32* ptr; | |
217 | UChar* block; | |
218 | UInt16* mtfv; | |
219 | UChar* zbits; | |
220 | ||
221 | /* for deciding when to use the fallback sorting algorithm */ | |
222 | Int32 workFactor; | |
223 | ||
224 | /* run-length-encoding of the input */ | |
225 | UInt32 state_in_ch; | |
226 | Int32 state_in_len; | |
227 | BZ_RAND_DECLS; | |
228 | ||
229 | /* input and output limits and current posns */ | |
230 | Int32 nblock; | |
231 | Int32 nblockMAX; | |
232 | Int32 numZ; | |
233 | Int32 state_out_pos; | |
234 | ||
235 | /* map of bytes used in block */ | |
236 | Int32 nInUse; | |
237 | Bool inUse[256]; | |
238 | UChar unseqToSeq[256]; | |
239 | ||
240 | /* the buffer for bit stream creation */ | |
241 | UInt32 bsBuff; | |
242 | Int32 bsLive; | |
243 | ||
244 | /* block and combined CRCs */ | |
245 | UInt32 blockCRC; | |
246 | UInt32 combinedCRC; | |
247 | ||
248 | /* misc administratium */ | |
249 | Int32 verbosity; | |
250 | Int32 blockNo; | |
251 | Int32 blockSize100k; | |
252 | ||
253 | /* stuff for coding the MTF values */ | |
254 | Int32 nMTF; | |
255 | Int32 mtfFreq [BZ_MAX_ALPHA_SIZE]; | |
256 | UChar selector [BZ_MAX_SELECTORS]; | |
257 | UChar selectorMtf[BZ_MAX_SELECTORS]; | |
258 | ||
259 | UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | |
260 | Int32 code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | |
261 | Int32 rfreq [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | |
262 | /* second dimension: only 3 needed; 4 makes index calculations faster */ | |
263 | UInt32 len_pack[BZ_MAX_ALPHA_SIZE][4]; | |
264 | ||
265 | } | |
266 | EState; | |
267 | ||
268 | ||
269 | ||
270 | /*-- externs for compression. --*/ | |
271 | ||
272 | extern void | |
273 | BZ2_blockSort ( EState* ); | |
274 | ||
275 | extern void | |
276 | BZ2_compressBlock ( EState*, Bool ); | |
277 | ||
278 | extern void | |
279 | BZ2_bsInitWrite ( EState* ); | |
280 | ||
281 | extern void | |
282 | BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 ); | |
283 | ||
284 | extern void | |
285 | BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 ); | |
286 | ||
287 | ||
288 | ||
289 | /*-- states for decompression. --*/ | |
290 | ||
291 | #define BZ_X_IDLE 1 | |
292 | #define BZ_X_OUTPUT 2 | |
293 | ||
294 | #define BZ_X_MAGIC_1 10 | |
295 | #define BZ_X_MAGIC_2 11 | |
296 | #define BZ_X_MAGIC_3 12 | |
297 | #define BZ_X_MAGIC_4 13 | |
298 | #define BZ_X_BLKHDR_1 14 | |
299 | #define BZ_X_BLKHDR_2 15 | |
300 | #define BZ_X_BLKHDR_3 16 | |
301 | #define BZ_X_BLKHDR_4 17 | |
302 | #define BZ_X_BLKHDR_5 18 | |
303 | #define BZ_X_BLKHDR_6 19 | |
304 | #define BZ_X_BCRC_1 20 | |
305 | #define BZ_X_BCRC_2 21 | |
306 | #define BZ_X_BCRC_3 22 | |
307 | #define BZ_X_BCRC_4 23 | |
308 | #define BZ_X_RANDBIT 24 | |
309 | #define BZ_X_ORIGPTR_1 25 | |
310 | #define BZ_X_ORIGPTR_2 26 | |
311 | #define BZ_X_ORIGPTR_3 27 | |
312 | #define BZ_X_MAPPING_1 28 | |
313 | #define BZ_X_MAPPING_2 29 | |
314 | #define BZ_X_SELECTOR_1 30 | |
315 | #define BZ_X_SELECTOR_2 31 | |
316 | #define BZ_X_SELECTOR_3 32 | |
317 | #define BZ_X_CODING_1 33 | |
318 | #define BZ_X_CODING_2 34 | |
319 | #define BZ_X_CODING_3 35 | |
320 | #define BZ_X_MTF_1 36 | |
321 | #define BZ_X_MTF_2 37 | |
322 | #define BZ_X_MTF_3 38 | |
323 | #define BZ_X_MTF_4 39 | |
324 | #define BZ_X_MTF_5 40 | |
325 | #define BZ_X_MTF_6 41 | |
326 | #define BZ_X_ENDHDR_2 42 | |
327 | #define BZ_X_ENDHDR_3 43 | |
328 | #define BZ_X_ENDHDR_4 44 | |
329 | #define BZ_X_ENDHDR_5 45 | |
330 | #define BZ_X_ENDHDR_6 46 | |
331 | #define BZ_X_CCRC_1 47 | |
332 | #define BZ_X_CCRC_2 48 | |
333 | #define BZ_X_CCRC_3 49 | |
334 | #define BZ_X_CCRC_4 50 | |
335 | ||
336 | ||
337 | ||
338 | /*-- Constants for the fast MTF decoder. --*/ | |
339 | ||
340 | #define MTFA_SIZE 4096 | |
341 | #define MTFL_SIZE 16 | |
342 | ||
343 | ||
344 | ||
345 | /*-- Structure holding all the decompression-side stuff. --*/ | |
346 | ||
347 | typedef | |
348 | struct { | |
349 | /* pointer back to the struct bz_stream */ | |
350 | bz_stream* strm; | |
351 | ||
352 | /* state indicator for this stream */ | |
353 | Int32 state; | |
354 | ||
355 | /* for doing the final run-length decoding */ | |
356 | UChar state_out_ch; | |
357 | Int32 state_out_len; | |
358 | Bool blockRandomised; | |
359 | BZ_RAND_DECLS; | |
360 | ||
361 | /* the buffer for bit stream reading */ | |
362 | UInt32 bsBuff; | |
363 | Int32 bsLive; | |
364 | ||
365 | /* misc administratium */ | |
366 | Int32 blockSize100k; | |
367 | Bool smallDecompress; | |
368 | Int32 currBlockNo; | |
369 | Int32 verbosity; | |
370 | ||
371 | /* for undoing the Burrows-Wheeler transform */ | |
372 | Int32 origPtr; | |
373 | UInt32 tPos; | |
374 | Int32 k0; | |
375 | Int32 unzftab[256]; | |
376 | Int32 nblock_used; | |
377 | Int32 cftab[257]; | |
378 | Int32 cftabCopy[257]; | |
379 | ||
380 | /* for undoing the Burrows-Wheeler transform (FAST) */ | |
381 | UInt32 *tt; | |
382 | ||
383 | /* for undoing the Burrows-Wheeler transform (SMALL) */ | |
384 | UInt16 *ll16; | |
385 | UChar *ll4; | |
386 | ||
387 | /* stored and calculated CRCs */ | |
388 | UInt32 storedBlockCRC; | |
389 | UInt32 storedCombinedCRC; | |
390 | UInt32 calculatedBlockCRC; | |
391 | UInt32 calculatedCombinedCRC; | |
392 | ||
393 | /* map of bytes used in block */ | |
394 | Int32 nInUse; | |
395 | Bool inUse[256]; | |
396 | Bool inUse16[16]; | |
397 | UChar seqToUnseq[256]; | |
398 | ||
399 | /* for decoding the MTF values */ | |
400 | UChar mtfa [MTFA_SIZE]; | |
401 | Int32 mtfbase[256 / MTFL_SIZE]; | |
402 | UChar selector [BZ_MAX_SELECTORS]; | |
403 | UChar selectorMtf[BZ_MAX_SELECTORS]; | |
404 | UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | |
405 | ||
406 | Int32 limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | |
407 | Int32 base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | |
408 | Int32 perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | |
409 | Int32 minLens[BZ_N_GROUPS]; | |
410 | ||
411 | /* save area for scalars in the main decompress code */ | |
412 | Int32 save_i; | |
413 | Int32 save_j; | |
414 | Int32 save_t; | |
415 | Int32 save_alphaSize; | |
416 | Int32 save_nGroups; | |
417 | Int32 save_nSelectors; | |
418 | Int32 save_EOB; | |
419 | Int32 save_groupNo; | |
420 | Int32 save_groupPos; | |
421 | Int32 save_nextSym; | |
422 | Int32 save_nblockMAX; | |
423 | Int32 save_nblock; | |
424 | Int32 save_es; | |
425 | Int32 save_N; | |
426 | Int32 save_curr; | |
427 | Int32 save_zt; | |
428 | Int32 save_zn; | |
429 | Int32 save_zvec; | |
430 | Int32 save_zj; | |
431 | Int32 save_gSel; | |
432 | Int32 save_gMinlen; | |
433 | Int32* save_gLimit; | |
434 | Int32* save_gBase; | |
435 | Int32* save_gPerm; | |
436 | ||
437 | } | |
438 | DState; | |
439 | ||
440 | ||
441 | ||
442 | /*-- Macros for decompression. --*/ | |
443 | ||
444 | #define BZ_GET_FAST(cccc) \ | |
445 | /* c_tPos is unsigned, hence test < 0 is pointless. */ \ | |
446 | if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \ | |
447 | s->tPos = s->tt[s->tPos]; \ | |
448 | cccc = (UChar)(s->tPos & 0xff); \ | |
449 | s->tPos >>= 8; | |
450 | ||
451 | #define BZ_GET_FAST_C(cccc) \ | |
452 | /* c_tPos is unsigned, hence test < 0 is pointless. */ \ | |
453 | if (c_tPos >= (UInt32)100000 * (UInt32)ro_blockSize100k) return True; \ | |
454 | c_tPos = c_tt[c_tPos]; \ | |
455 | cccc = (UChar)(c_tPos & 0xff); \ | |
456 | c_tPos >>= 8; | |
457 | ||
458 | #define SET_LL4(i,n) \ | |
459 | { if (((i) & 0x1) == 0) \ | |
460 | s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else \ | |
461 | s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4); \ | |
462 | } | |
463 | ||
464 | #define GET_LL4(i) \ | |
465 | ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF) | |
466 | ||
467 | #define SET_LL(i,n) \ | |
468 | { s->ll16[i] = (UInt16)(n & 0x0000ffff); \ | |
469 | SET_LL4(i, n >> 16); \ | |
470 | } | |
471 | ||
472 | #define GET_LL(i) \ | |
473 | (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16)) | |
474 | ||
475 | #define BZ_GET_SMALL(cccc) \ | |
476 | /* c_tPos is unsigned, hence test < 0 is pointless. */ \ | |
477 | if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \ | |
478 | cccc = BZ2_indexIntoF ( s->tPos, s->cftab ); \ | |
479 | s->tPos = GET_LL(s->tPos); | |
480 | ||
481 | ||
482 | /*-- externs for decompression. --*/ | |
483 | ||
484 | extern Int32 | |
485 | BZ2_indexIntoF ( Int32, Int32* ); | |
486 | ||
487 | extern Int32 | |
488 | BZ2_decompress ( DState* ); | |
489 | ||
490 | extern void | |
491 | BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*, | |
492 | Int32, Int32, Int32 ); | |
493 | ||
494 | ||
495 | #endif | |
496 | ||
497 | ||
498 | /*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/ | |
499 | ||
500 | #ifdef BZ_NO_STDIO | |
501 | #ifndef NULL | |
502 | #define NULL 0 | |
503 | #endif | |
504 | #endif | |
505 | ||
506 | ||
507 | /*-------------------------------------------------------------*/ | |
508 | /*--- end bzlib_private.h ---*/ | |
509 | /*-------------------------------------------------------------*/ |