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