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