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