diff options
author | Julian Seward <jseward@acm.org> | 1998-08-23 22:13:13 +0200 |
---|---|---|
committer | Julian Seward <jseward@acm.org> | 1998-08-23 22:13:13 +0200 |
commit | 977101ad5f833f5c0a574bfeea408e5301a6b052 (patch) | |
tree | fc1e8fed202869c116cbf6b8c362456042494a0a /bzlib_private.h | |
parent | 1eb67a9d8f7f05ae310bc9ef297d176f3a3f8a37 (diff) | |
download | bzip2-0.9.0c.tar.gz bzip2-0.9.0c.tar.bz2 bzip2-0.9.0c.zip |
bzip2-0.9.0cbzip2-0.9.0c
Diffstat (limited to 'bzlib_private.h')
-rw-r--r-- | bzlib_private.h | 523 |
1 files changed, 523 insertions, 0 deletions
diff --git a/bzlib_private.h b/bzlib_private.h new file mode 100644 index 0000000..4044aef --- /dev/null +++ b/bzlib_private.h | |||
@@ -0,0 +1,523 @@ | |||
1 | |||
2 | /*-------------------------------------------------------------*/ | ||
3 | /*--- Private header file for the library. ---*/ | ||
4 | /*--- bzlib_private.h ---*/ | ||
5 | /*-------------------------------------------------------------*/ | ||
6 | |||
7 | /*-- | ||
8 | This file is a part of bzip2 and/or libbzip2, a program and | ||
9 | library for lossless, block-sorting data compression. | ||
10 | |||
11 | Copyright (C) 1996-1998 Julian R Seward. All rights reserved. | ||
12 | |||
13 | Redistribution and use in source and binary forms, with or without | ||
14 | modification, are permitted provided that the following conditions | ||
15 | are met: | ||
16 | |||
17 | 1. Redistributions of source code must retain the above copyright | ||
18 | notice, this list of conditions and the following disclaimer. | ||
19 | |||
20 | 2. The origin of this software must not be misrepresented; you must | ||
21 | not claim that you wrote the original software. If you use this | ||
22 | software in a product, an acknowledgment in the product | ||
23 | documentation would be appreciated but is not required. | ||
24 | |||
25 | 3. Altered source versions must be plainly marked as such, and must | ||
26 | not be misrepresented as being the original software. | ||
27 | |||
28 | 4. The name of the author may not be used to endorse or promote | ||
29 | products derived from this software without specific prior written | ||
30 | permission. | ||
31 | |||
32 | THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS | ||
33 | OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED | ||
34 | WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
35 | ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY | ||
36 | DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | ||
37 | DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE | ||
38 | GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | ||
39 | INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, | ||
40 | WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING | ||
41 | NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS | ||
42 | SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | ||
43 | |||
44 | Julian Seward, Guildford, Surrey, UK. | ||
45 | jseward@acm.org | ||
46 | bzip2/libbzip2 version 0.9.0c of 18 October 1998 | ||
47 | |||
48 | This program is based on (at least) the work of: | ||
49 | Mike Burrows | ||
50 | David Wheeler | ||
51 | Peter Fenwick | ||
52 | Alistair Moffat | ||
53 | Radford Neal | ||
54 | Ian H. Witten | ||
55 | Robert Sedgewick | ||
56 | Jon L. Bentley | ||
57 | |||
58 | For more information on these sources, see the manual. | ||
59 | --*/ | ||
60 | |||
61 | |||
62 | #ifndef _BZLIB_PRIVATE_H | ||
63 | #define _BZLIB_PRIVATE_H | ||
64 | |||
65 | #include <stdlib.h> | ||
66 | |||
67 | #ifndef BZ_NO_STDIO | ||
68 | #include <stdio.h> | ||
69 | #include <ctype.h> | ||
70 | #include <string.h> | ||
71 | #endif | ||
72 | |||
73 | #include "bzlib.h" | ||
74 | |||
75 | |||
76 | |||
77 | /*-- General stuff. --*/ | ||
78 | |||
79 | #define BZ_VERSION "0.9.0c" | ||
80 | |||
81 | typedef char Char; | ||
82 | typedef unsigned char Bool; | ||
83 | typedef unsigned char UChar; | ||
84 | typedef int Int32; | ||
85 | typedef unsigned int UInt32; | ||
86 | typedef short Int16; | ||
87 | typedef unsigned short UInt16; | ||
88 | |||
89 | #define True ((Bool)1) | ||
90 | #define False ((Bool)0) | ||
91 | |||
92 | #ifndef __GNUC__ | ||
93 | #define __inline__ /* */ | ||
94 | #endif | ||
95 | |||
96 | #ifndef BZ_NO_STDIO | ||
97 | extern void bz__AssertH__fail ( int errcode ); | ||
98 | #define AssertH(cond,errcode) \ | ||
99 | { if (!(cond)) bz__AssertH__fail ( errcode ); } | ||
100 | #if BZ_DEBUG | ||
101 | #define AssertD(cond,msg) \ | ||
102 | { if (!(cond)) { \ | ||
103 | fprintf ( stderr, \ | ||
104 | "\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\ | ||
105 | exit(1); \ | ||
106 | }} | ||
107 | #else | ||
108 | #define AssertD(cond,msg) /* */ | ||
109 | #endif | ||
110 | #define VPrintf0(zf) \ | ||
111 | fprintf(stderr,zf) | ||
112 | #define VPrintf1(zf,za1) \ | ||
113 | fprintf(stderr,zf,za1) | ||
114 | #define VPrintf2(zf,za1,za2) \ | ||
115 | fprintf(stderr,zf,za1,za2) | ||
116 | #define VPrintf3(zf,za1,za2,za3) \ | ||
117 | fprintf(stderr,zf,za1,za2,za3) | ||
118 | #define VPrintf4(zf,za1,za2,za3,za4) \ | ||
119 | fprintf(stderr,zf,za1,za2,za3,za4) | ||
120 | #define VPrintf5(zf,za1,za2,za3,za4,za5) \ | ||
121 | fprintf(stderr,zf,za1,za2,za3,za4,za5) | ||
122 | #else | ||
123 | extern void bz_internal_error ( int errcode ); | ||
124 | #define AssertH(cond,errcode) \ | ||
125 | { if (!(cond)) bz_internal_error ( errcode ); } | ||
126 | #define AssertD(cond,msg) /* */ | ||
127 | #define VPrintf0(zf) /* */ | ||
128 | #define VPrintf1(zf,za1) /* */ | ||
129 | #define VPrintf2(zf,za1,za2) /* */ | ||
130 | #define VPrintf3(zf,za1,za2,za3) /* */ | ||
131 | #define VPrintf4(zf,za1,za2,za3,za4) /* */ | ||
132 | #define VPrintf5(zf,za1,za2,za3,za4,za5) /* */ | ||
133 | #endif | ||
134 | |||
135 | |||
136 | #define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1) | ||
137 | #define BZFREE(ppp) (strm->bzfree)(strm->opaque,(ppp)) | ||
138 | |||
139 | |||
140 | /*-- Constants for the back end. --*/ | ||
141 | |||
142 | #define BZ_MAX_ALPHA_SIZE 258 | ||
143 | #define BZ_MAX_CODE_LEN 23 | ||
144 | |||
145 | #define BZ_RUNA 0 | ||
146 | #define BZ_RUNB 1 | ||
147 | |||
148 | #define BZ_N_GROUPS 6 | ||
149 | #define BZ_G_SIZE 50 | ||
150 | #define BZ_N_ITERS 4 | ||
151 | |||
152 | #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE)) | ||
153 | |||
154 | |||
155 | |||
156 | /*-- Stuff for randomising repetitive blocks. --*/ | ||
157 | |||
158 | extern Int32 rNums[512]; | ||
159 | |||
160 | #define BZ_RAND_DECLS \ | ||
161 | Int32 rNToGo; \ | ||
162 | Int32 rTPos \ | ||
163 | |||
164 | #define BZ_RAND_INIT_MASK \ | ||
165 | s->rNToGo = 0; \ | ||
166 | s->rTPos = 0 \ | ||
167 | |||
168 | #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0) | ||
169 | |||
170 | #define BZ_RAND_UPD_MASK \ | ||
171 | if (s->rNToGo == 0) { \ | ||
172 | s->rNToGo = rNums[s->rTPos]; \ | ||
173 | s->rTPos++; \ | ||
174 | if (s->rTPos == 512) s->rTPos = 0; \ | ||
175 | } \ | ||
176 | s->rNToGo--; | ||
177 | |||
178 | |||
179 | |||
180 | /*-- Stuff for doing CRCs. --*/ | ||
181 | |||
182 | extern UInt32 crc32Table[256]; | ||
183 | |||
184 | #define BZ_INITIALISE_CRC(crcVar) \ | ||
185 | { \ | ||
186 | crcVar = 0xffffffffL; \ | ||
187 | } | ||
188 | |||
189 | #define BZ_FINALISE_CRC(crcVar) \ | ||
190 | { \ | ||
191 | crcVar = ~(crcVar); \ | ||
192 | } | ||
193 | |||
194 | #define BZ_UPDATE_CRC(crcVar,cha) \ | ||
195 | { \ | ||
196 | crcVar = (crcVar << 8) ^ \ | ||
197 | crc32Table[(crcVar >> 24) ^ \ | ||
198 | ((UChar)cha)]; \ | ||
199 | } | ||
200 | |||
201 | |||
202 | |||
203 | /*-- States and modes for compression. --*/ | ||
204 | |||
205 | #define BZ_M_IDLE 1 | ||
206 | #define BZ_M_RUNNING 2 | ||
207 | #define BZ_M_FLUSHING 3 | ||
208 | #define BZ_M_FINISHING 4 | ||
209 | |||
210 | #define BZ_S_OUTPUT 1 | ||
211 | #define BZ_S_INPUT 2 | ||
212 | |||
213 | #define BZ_NUM_OVERSHOOT_BYTES 20 | ||
214 | |||
215 | |||
216 | |||
217 | /*-- Structure holding all the compression-side stuff. --*/ | ||
218 | |||
219 | typedef | ||
220 | struct { | ||
221 | /* pointer back to the struct bz_stream */ | ||
222 | bz_stream* strm; | ||
223 | |||
224 | /* mode this stream is in, and whether inputting */ | ||
225 | /* or outputting data */ | ||
226 | Int32 mode; | ||
227 | Int32 state; | ||
228 | |||
229 | /* remembers avail_in when flush/finish requested */ | ||
230 | UInt32 avail_in_expect; | ||
231 | |||
232 | /* for doing the block sorting */ | ||
233 | UChar* block; | ||
234 | UInt16* quadrant; | ||
235 | UInt32* zptr; | ||
236 | UInt16* szptr; | ||
237 | Int32* ftab; | ||
238 | Int32 workDone; | ||
239 | Int32 workLimit; | ||
240 | Int32 workFactor; | ||
241 | Bool firstAttempt; | ||
242 | Bool blockRandomised; | ||
243 | Int32 origPtr; | ||
244 | |||
245 | /* run-length-encoding of the input */ | ||
246 | UInt32 state_in_ch; | ||
247 | Int32 state_in_len; | ||
248 | BZ_RAND_DECLS; | ||
249 | |||
250 | /* input and output limits and current posns */ | ||
251 | Int32 nblock; | ||
252 | Int32 nblockMAX; | ||
253 | Int32 numZ; | ||
254 | Int32 state_out_pos; | ||
255 | |||
256 | /* map of bytes used in block */ | ||
257 | Int32 nInUse; | ||
258 | Bool inUse[256]; | ||
259 | UChar unseqToSeq[256]; | ||
260 | |||
261 | /* the buffer for bit stream creation */ | ||
262 | UInt32 bsBuff; | ||
263 | Int32 bsLive; | ||
264 | |||
265 | /* block and combined CRCs */ | ||
266 | UInt32 blockCRC; | ||
267 | UInt32 combinedCRC; | ||
268 | |||
269 | /* misc administratium */ | ||
270 | Int32 verbosity; | ||
271 | Int32 blockNo; | ||
272 | Int32 nBlocksRandomised; | ||
273 | Int32 blockSize100k; | ||
274 | |||
275 | /* stuff for coding the MTF values */ | ||
276 | Int32 nMTF; | ||
277 | Int32 mtfFreq [BZ_MAX_ALPHA_SIZE]; | ||
278 | UChar selector [BZ_MAX_SELECTORS]; | ||
279 | UChar selectorMtf[BZ_MAX_SELECTORS]; | ||
280 | |||
281 | UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
282 | Int32 code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
283 | Int32 rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
284 | |||
285 | } | ||
286 | EState; | ||
287 | |||
288 | |||
289 | |||
290 | /*-- externs for compression. --*/ | ||
291 | |||
292 | extern void | ||
293 | blockSort ( EState* ); | ||
294 | |||
295 | extern void | ||
296 | compressBlock ( EState*, Bool ); | ||
297 | |||
298 | extern void | ||
299 | bsInitWrite ( EState* ); | ||
300 | |||
301 | extern void | ||
302 | hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 ); | ||
303 | |||
304 | extern void | ||
305 | hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 ); | ||
306 | |||
307 | |||
308 | |||
309 | /*-- states for decompression. --*/ | ||
310 | |||
311 | #define BZ_X_IDLE 1 | ||
312 | #define BZ_X_OUTPUT 2 | ||
313 | |||
314 | #define BZ_X_MAGIC_1 10 | ||
315 | #define BZ_X_MAGIC_2 11 | ||
316 | #define BZ_X_MAGIC_3 12 | ||
317 | #define BZ_X_MAGIC_4 13 | ||
318 | #define BZ_X_BLKHDR_1 14 | ||
319 | #define BZ_X_BLKHDR_2 15 | ||
320 | #define BZ_X_BLKHDR_3 16 | ||
321 | #define BZ_X_BLKHDR_4 17 | ||
322 | #define BZ_X_BLKHDR_5 18 | ||
323 | #define BZ_X_BLKHDR_6 19 | ||
324 | #define BZ_X_BCRC_1 20 | ||
325 | #define BZ_X_BCRC_2 21 | ||
326 | #define BZ_X_BCRC_3 22 | ||
327 | #define BZ_X_BCRC_4 23 | ||
328 | #define BZ_X_RANDBIT 24 | ||
329 | #define BZ_X_ORIGPTR_1 25 | ||
330 | #define BZ_X_ORIGPTR_2 26 | ||
331 | #define BZ_X_ORIGPTR_3 27 | ||
332 | #define BZ_X_MAPPING_1 28 | ||
333 | #define BZ_X_MAPPING_2 29 | ||
334 | #define BZ_X_SELECTOR_1 30 | ||
335 | #define BZ_X_SELECTOR_2 31 | ||
336 | #define BZ_X_SELECTOR_3 32 | ||
337 | #define BZ_X_CODING_1 33 | ||
338 | #define BZ_X_CODING_2 34 | ||
339 | #define BZ_X_CODING_3 35 | ||
340 | #define BZ_X_MTF_1 36 | ||
341 | #define BZ_X_MTF_2 37 | ||
342 | #define BZ_X_MTF_3 38 | ||
343 | #define BZ_X_MTF_4 39 | ||
344 | #define BZ_X_MTF_5 40 | ||
345 | #define BZ_X_MTF_6 41 | ||
346 | #define BZ_X_ENDHDR_2 42 | ||
347 | #define BZ_X_ENDHDR_3 43 | ||
348 | #define BZ_X_ENDHDR_4 44 | ||
349 | #define BZ_X_ENDHDR_5 45 | ||
350 | #define BZ_X_ENDHDR_6 46 | ||
351 | #define BZ_X_CCRC_1 47 | ||
352 | #define BZ_X_CCRC_2 48 | ||
353 | #define BZ_X_CCRC_3 49 | ||
354 | #define BZ_X_CCRC_4 50 | ||
355 | |||
356 | |||
357 | |||
358 | /*-- Constants for the fast MTF decoder. --*/ | ||
359 | |||
360 | #define MTFA_SIZE 4096 | ||
361 | #define MTFL_SIZE 16 | ||
362 | |||
363 | |||
364 | |||
365 | /*-- Structure holding all the decompression-side stuff. --*/ | ||
366 | |||
367 | typedef | ||
368 | struct { | ||
369 | /* pointer back to the struct bz_stream */ | ||
370 | bz_stream* strm; | ||
371 | |||
372 | /* state indicator for this stream */ | ||
373 | Int32 state; | ||
374 | |||
375 | /* for doing the final run-length decoding */ | ||
376 | UChar state_out_ch; | ||
377 | Int32 state_out_len; | ||
378 | Bool blockRandomised; | ||
379 | BZ_RAND_DECLS; | ||
380 | |||
381 | /* the buffer for bit stream reading */ | ||
382 | UInt32 bsBuff; | ||
383 | Int32 bsLive; | ||
384 | |||
385 | /* misc administratium */ | ||
386 | Int32 blockSize100k; | ||
387 | Bool smallDecompress; | ||
388 | Int32 currBlockNo; | ||
389 | Int32 verbosity; | ||
390 | |||
391 | /* for undoing the Burrows-Wheeler transform */ | ||
392 | Int32 origPtr; | ||
393 | UInt32 tPos; | ||
394 | Int32 k0; | ||
395 | Int32 unzftab[256]; | ||
396 | Int32 nblock_used; | ||
397 | Int32 cftab[257]; | ||
398 | Int32 cftabCopy[257]; | ||
399 | |||
400 | /* for undoing the Burrows-Wheeler transform (FAST) */ | ||
401 | UInt32 *tt; | ||
402 | |||
403 | /* for undoing the Burrows-Wheeler transform (SMALL) */ | ||
404 | UInt16 *ll16; | ||
405 | UChar *ll4; | ||
406 | |||
407 | /* stored and calculated CRCs */ | ||
408 | UInt32 storedBlockCRC; | ||
409 | UInt32 storedCombinedCRC; | ||
410 | UInt32 calculatedBlockCRC; | ||
411 | UInt32 calculatedCombinedCRC; | ||
412 | |||
413 | /* map of bytes used in block */ | ||
414 | Int32 nInUse; | ||
415 | Bool inUse[256]; | ||
416 | Bool inUse16[16]; | ||
417 | UChar seqToUnseq[256]; | ||
418 | |||
419 | /* for decoding the MTF values */ | ||
420 | UChar mtfa [MTFA_SIZE]; | ||
421 | Int32 mtfbase[256 / MTFL_SIZE]; | ||
422 | UChar selector [BZ_MAX_SELECTORS]; | ||
423 | UChar selectorMtf[BZ_MAX_SELECTORS]; | ||
424 | UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
425 | |||
426 | Int32 limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
427 | Int32 base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
428 | Int32 perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
429 | Int32 minLens[BZ_N_GROUPS]; | ||
430 | |||
431 | /* save area for scalars in the main decompress code */ | ||
432 | Int32 save_i; | ||
433 | Int32 save_j; | ||
434 | Int32 save_t; | ||
435 | Int32 save_alphaSize; | ||
436 | Int32 save_nGroups; | ||
437 | Int32 save_nSelectors; | ||
438 | Int32 save_EOB; | ||
439 | Int32 save_groupNo; | ||
440 | Int32 save_groupPos; | ||
441 | Int32 save_nextSym; | ||
442 | Int32 save_nblockMAX; | ||
443 | Int32 save_nblock; | ||
444 | Int32 save_es; | ||
445 | Int32 save_N; | ||
446 | Int32 save_curr; | ||
447 | Int32 save_zt; | ||
448 | Int32 save_zn; | ||
449 | Int32 save_zvec; | ||
450 | Int32 save_zj; | ||
451 | Int32 save_gSel; | ||
452 | Int32 save_gMinlen; | ||
453 | Int32* save_gLimit; | ||
454 | Int32* save_gBase; | ||
455 | Int32* save_gPerm; | ||
456 | |||
457 | } | ||
458 | DState; | ||
459 | |||
460 | |||
461 | |||
462 | /*-- Macros for decompression. --*/ | ||
463 | |||
464 | #define BZ_GET_FAST(cccc) \ | ||
465 | s->tPos = s->tt[s->tPos]; \ | ||
466 | cccc = (UChar)(s->tPos & 0xff); \ | ||
467 | s->tPos >>= 8; | ||
468 | |||
469 | #define BZ_GET_FAST_C(cccc) \ | ||
470 | c_tPos = c_tt[c_tPos]; \ | ||
471 | cccc = (UChar)(c_tPos & 0xff); \ | ||
472 | c_tPos >>= 8; | ||
473 | |||
474 | #define SET_LL4(i,n) \ | ||
475 | { if (((i) & 0x1) == 0) \ | ||
476 | s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else \ | ||
477 | s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4); \ | ||
478 | } | ||
479 | |||
480 | #define GET_LL4(i) \ | ||
481 | (((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4) & 0xF) | ||
482 | |||
483 | #define SET_LL(i,n) \ | ||
484 | { s->ll16[i] = (UInt16)(n & 0x0000ffff); \ | ||
485 | SET_LL4(i, n >> 16); \ | ||
486 | } | ||
487 | |||
488 | #define GET_LL(i) \ | ||
489 | (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16)) | ||
490 | |||
491 | #define BZ_GET_SMALL(cccc) \ | ||
492 | cccc = indexIntoF ( s->tPos, s->cftab ); \ | ||
493 | s->tPos = GET_LL(s->tPos); | ||
494 | |||
495 | |||
496 | /*-- externs for decompression. --*/ | ||
497 | |||
498 | extern Int32 | ||
499 | indexIntoF ( Int32, Int32* ); | ||
500 | |||
501 | extern Int32 | ||
502 | decompress ( DState* ); | ||
503 | |||
504 | extern void | ||
505 | hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*, | ||
506 | Int32, Int32, Int32 ); | ||
507 | |||
508 | |||
509 | #endif | ||
510 | |||
511 | |||
512 | /*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/ | ||
513 | |||
514 | #ifdef BZ_NO_STDIO | ||
515 | #ifndef NULL | ||
516 | #define NULL 0 | ||
517 | #endif | ||
518 | #endif | ||
519 | |||
520 | |||
521 | /*-------------------------------------------------------------*/ | ||
522 | /*--- end bzlib_private.h ---*/ | ||
523 | /*-------------------------------------------------------------*/ | ||