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