bzlib_private.h revision 78556 
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-2000 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.1, 23-June-2000"
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/*-- 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
158extern Int32 BZ2_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 = BZ2_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
182extern UInt32 BZ2_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            BZ2_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_N_RADIX 2
214#define BZ_N_QSORT 12
215#define BZ_N_SHELL 18
216#define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
217
218
219
220
221/*-- Structure holding all the compression-side stuff. --*/
222
223typedef
224   struct {
225      /* pointer back to the struct bz_stream */
226      bz_stream* strm;
227
228      /* mode this stream is in, and whether inputting */
229      /* or outputting data */
230      Int32    mode;
231      Int32    state;
232
233      /* remembers avail_in when flush/finish requested */
234      UInt32   avail_in_expect;
235
236      /* for doing the block sorting */
237      UInt32*  arr1;
238      UInt32*  arr2;
239      UInt32*  ftab;
240      Int32    origPtr;
241
242      /* aliases for arr1 and arr2 */
243      UInt32*  ptr;
244      UChar*   block;
245      UInt16*  mtfv;
246      UChar*   zbits;
247
248      /* for deciding when to use the fallback sorting algorithm */
249      Int32    workFactor;
250
251      /* run-length-encoding of the input */
252      UInt32   state_in_ch;
253      Int32    state_in_len;
254      BZ_RAND_DECLS;
255
256      /* input and output limits and current posns */
257      Int32    nblock;
258      Int32    nblockMAX;
259      Int32    numZ;
260      Int32    state_out_pos;
261
262      /* map of bytes used in block */
263      Int32    nInUse;
264      Bool     inUse[256];
265      UChar    unseqToSeq[256];
266
267      /* the buffer for bit stream creation */
268      UInt32   bsBuff;
269      Int32    bsLive;
270
271      /* block and combined CRCs */
272      UInt32   blockCRC;
273      UInt32   combinedCRC;
274
275      /* misc administratium */
276      Int32    verbosity;
277      Int32    blockNo;
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      /* second dimension: only 3 needed; 4 makes index calculations faster */
290      UInt32   len_pack[BZ_MAX_ALPHA_SIZE][4];
291
292   }
293   EState;
294
295
296
297/*-- externs for compression. --*/
298
299extern void
300BZ2_blockSort ( EState* );
301
302extern void
303BZ2_compressBlock ( EState*, Bool );
304
305extern void
306BZ2_bsInitWrite ( EState* );
307
308extern void
309BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 );
310
311extern void
312BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 );
313
314
315
316/*-- states for decompression. --*/
317
318#define BZ_X_IDLE        1
319#define BZ_X_OUTPUT      2
320
321#define BZ_X_MAGIC_1     10
322#define BZ_X_MAGIC_2     11
323#define BZ_X_MAGIC_3     12
324#define BZ_X_MAGIC_4     13
325#define BZ_X_BLKHDR_1    14
326#define BZ_X_BLKHDR_2    15
327#define BZ_X_BLKHDR_3    16
328#define BZ_X_BLKHDR_4    17
329#define BZ_X_BLKHDR_5    18
330#define BZ_X_BLKHDR_6    19
331#define BZ_X_BCRC_1      20
332#define BZ_X_BCRC_2      21
333#define BZ_X_BCRC_3      22
334#define BZ_X_BCRC_4      23
335#define BZ_X_RANDBIT     24
336#define BZ_X_ORIGPTR_1   25
337#define BZ_X_ORIGPTR_2   26
338#define BZ_X_ORIGPTR_3   27
339#define BZ_X_MAPPING_1   28
340#define BZ_X_MAPPING_2   29
341#define BZ_X_SELECTOR_1  30
342#define BZ_X_SELECTOR_2  31
343#define BZ_X_SELECTOR_3  32
344#define BZ_X_CODING_1    33
345#define BZ_X_CODING_2    34
346#define BZ_X_CODING_3    35
347#define BZ_X_MTF_1       36
348#define BZ_X_MTF_2       37
349#define BZ_X_MTF_3       38
350#define BZ_X_MTF_4       39
351#define BZ_X_MTF_5       40
352#define BZ_X_MTF_6       41
353#define BZ_X_ENDHDR_2    42
354#define BZ_X_ENDHDR_3    43
355#define BZ_X_ENDHDR_4    44
356#define BZ_X_ENDHDR_5    45
357#define BZ_X_ENDHDR_6    46
358#define BZ_X_CCRC_1      47
359#define BZ_X_CCRC_2      48
360#define BZ_X_CCRC_3      49
361#define BZ_X_CCRC_4      50
362
363
364
365/*-- Constants for the fast MTF decoder. --*/
366
367#define MTFA_SIZE 4096
368#define MTFL_SIZE 16
369
370
371
372/*-- Structure holding all the decompression-side stuff. --*/
373
374typedef
375   struct {
376      /* pointer back to the struct bz_stream */
377      bz_stream* strm;
378
379      /* state indicator for this stream */
380      Int32    state;
381
382      /* for doing the final run-length decoding */
383      UChar    state_out_ch;
384      Int32    state_out_len;
385      Bool     blockRandomised;
386      BZ_RAND_DECLS;
387
388      /* the buffer for bit stream reading */
389      UInt32   bsBuff;
390      Int32    bsLive;
391
392      /* misc administratium */
393      Int32    blockSize100k;
394      Bool     smallDecompress;
395      Int32    currBlockNo;
396      Int32    verbosity;
397
398      /* for undoing the Burrows-Wheeler transform */
399      Int32    origPtr;
400      UInt32   tPos;
401      Int32    k0;
402      Int32    unzftab[256];
403      Int32    nblock_used;
404      Int32    cftab[257];
405      Int32    cftabCopy[257];
406
407      /* for undoing the Burrows-Wheeler transform (FAST) */
408      UInt32   *tt;
409
410      /* for undoing the Burrows-Wheeler transform (SMALL) */
411      UInt16   *ll16;
412      UChar    *ll4;
413
414      /* stored and calculated CRCs */
415      UInt32   storedBlockCRC;
416      UInt32   storedCombinedCRC;
417      UInt32   calculatedBlockCRC;
418      UInt32   calculatedCombinedCRC;
419
420      /* map of bytes used in block */
421      Int32    nInUse;
422      Bool     inUse[256];
423      Bool     inUse16[16];
424      UChar    seqToUnseq[256];
425
426      /* for decoding the MTF values */
427      UChar    mtfa   [MTFA_SIZE];
428      Int32    mtfbase[256 / MTFL_SIZE];
429      UChar    selector   [BZ_MAX_SELECTORS];
430      UChar    selectorMtf[BZ_MAX_SELECTORS];
431      UChar    len  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
432
433      Int32    limit  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
434      Int32    base   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
435      Int32    perm   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
436      Int32    minLens[BZ_N_GROUPS];
437
438      /* save area for scalars in the main decompress code */
439      Int32    save_i;
440      Int32    save_j;
441      Int32    save_t;
442      Int32    save_alphaSize;
443      Int32    save_nGroups;
444      Int32    save_nSelectors;
445      Int32    save_EOB;
446      Int32    save_groupNo;
447      Int32    save_groupPos;
448      Int32    save_nextSym;
449      Int32    save_nblockMAX;
450      Int32    save_nblock;
451      Int32    save_es;
452      Int32    save_N;
453      Int32    save_curr;
454      Int32    save_zt;
455      Int32    save_zn;
456      Int32    save_zvec;
457      Int32    save_zj;
458      Int32    save_gSel;
459      Int32    save_gMinlen;
460      Int32*   save_gLimit;
461      Int32*   save_gBase;
462      Int32*   save_gPerm;
463
464   }
465   DState;
466
467
468
469/*-- Macros for decompression. --*/
470
471#define BZ_GET_FAST(cccc)                     \
472    s->tPos = s->tt[s->tPos];                 \
473    cccc = (UChar)(s->tPos & 0xff);           \
474    s->tPos >>= 8;
475
476#define BZ_GET_FAST_C(cccc)                   \
477    c_tPos = c_tt[c_tPos];                    \
478    cccc = (UChar)(c_tPos & 0xff);            \
479    c_tPos >>= 8;
480
481#define SET_LL4(i,n)                                          \
482   { if (((i) & 0x1) == 0)                                    \
483        s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else    \
484        s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4);  \
485   }
486
487#define GET_LL4(i)                             \
488   ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)
489
490#define SET_LL(i,n)                          \
491   { s->ll16[i] = (UInt16)(n & 0x0000ffff);  \
492     SET_LL4(i, n >> 16);                    \
493   }
494
495#define GET_LL(i) \
496   (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16))
497
498#define BZ_GET_SMALL(cccc)                            \
499      cccc = BZ2_indexIntoF ( s->tPos, s->cftab );    \
500      s->tPos = GET_LL(s->tPos);
501
502
503/*-- externs for decompression. --*/
504
505extern Int32
506BZ2_indexIntoF ( Int32, Int32* );
507
508extern Int32
509BZ2_decompress ( DState* );
510
511extern void
512BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*,
513                           Int32,  Int32, Int32 );
514
515
516#endif
517
518
519/*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/
520
521#ifdef BZ_NO_STDIO
522#ifndef NULL
523#define NULL 0
524#endif
525#endif
526
527
528/*-------------------------------------------------------------*/
529/*--- end                                   bzlib_private.h ---*/
530/*-------------------------------------------------------------*/
531