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