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