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