1 
2 /* Test the variable identification machinery in a non-toy sized
3    program.  Also, the croak() call in BZ2_decompress causes Valgrind
4    to try to describe a local variable (i) that has at least a dozen
5    independent live ranges (hence, is really that many independent
6    variables).  Hence it tests the machinery's ability to correctly
7    handle a variable which has multiple live ranges and hence multiple
8    non-overlapping areas in which it actually exists.
9 */
10 
11 /* Relevant compile flags are:
12 
13    -Wall -g -I$prefix/include/valgrind
14 
15    eg -Wall -g -I`pwd`/Inst/include/valgrind
16 */
17 
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <assert.h>
21 #include "memcheck/memcheck.h"
22 
23 /* Cause memcheck to complain about the address "a" and so to print
24    its best guess as to what "a" actually is.  a must be
25    addressible. */
26 
croak(void * aV)27 void croak ( void* aV )
28 {
29   char* a = (char*)aV;
30   char* undefp = malloc(1);
31   char saved = *a;
32   assert(undefp);
33   *a = *undefp;
34   (void) VALGRIND_CHECK_MEM_IS_DEFINED(a, 1);
35   *a = saved;
36   free(undefp);
37 }
38 
39 // This benchmark is basically bzip2 (mashed to be a single file)
40 // compressing and decompressing some data.  It tests Valgrind's handling of
41 // realistic and "difficult" (ie. lots of branches and memory accesses)
42 // integer code.  Execution is spread out over quite a few basic blocks;
43 // --profile-flags indicates that to get to the top 90%th percentile of
44 // dynamic BB counts requires considering the top 51 basic blocks
45 
46 // This program can be used both as part of the performance test
47 // suite, in which case we want it to run for quite a while,
48 // and as part of the regression (correctness) test suite, in
49 // which case we want it to run quickly and be verbose.
50 // So it does the latter iff given a command line arg.
51 
52 // Licensing: the code within is mostly taken from bzip2, which has a BSD
53 // license.  There is a little code from VEX, which is licensed under GPLv2
54 // And it's all written by Julian Seward.
55 
56 #define BZ_NO_STDIO
57 
58 
59 /*-------------------------------------------------------------*/
60 /*--- Private header file for the library.                  ---*/
61 /*---                                       bzlib_private.h ---*/
62 /*-------------------------------------------------------------*/
63 
64 /*--
65   This file is a part of bzip2 and/or libbzip2, a program and
66   library for lossless, block-sorting data compression.
67 
68   Copyright (C) 1996-2004 Julian R Seward.  All rights reserved.
69 
70   Redistribution and use in source and binary forms, with or without
71   modification, are permitted provided that the following conditions
72   are met:
73 
74   1. Redistributions of source code must retain the above copyright
75      notice, this list of conditions and the following disclaimer.
76 
77   2. The origin of this software must not be misrepresented; you must
78      not claim that you wrote the original software.  If you use this
79      software in a product, an acknowledgment in the product
80      documentation would be appreciated but is not required.
81 
82   3. Altered source versions must be plainly marked as such, and must
83      not be misrepresented as being the original software.
84 
85   4. The name of the author may not be used to endorse or promote
86      products derived from this software without specific prior written
87      permission.
88 
89   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
90   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
91   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
92   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
93   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
94   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
95   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
96   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
97   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
98   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
99   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
100 
101   Julian Seward, Cambridge, UK.
102   jseward@bzip.org
103   bzip2/libbzip2 version 1.0 of 21 March 2000
104 
105   This program is based on (at least) the work of:
106      Mike Burrows
107      David Wheeler
108      Peter Fenwick
109      Alistair Moffat
110      Radford Neal
111      Ian H. Witten
112      Robert Sedgewick
113      Jon L. Bentley
114 
115   For more information on these sources, see the manual.
116 --*/
117 
118 
119 #ifndef _BZLIB_PRIVATE_H
120 #define _BZLIB_PRIVATE_H
121 
122 #include <stdlib.h>
123 
124 #ifndef BZ_NO_STDIO
125 #include <stdio.h>
126 #include <ctype.h>
127 #include <string.h>
128 #endif
129 
130 
131 /*-------------------------------------------------------------*/
132 /*--- Public header file for the library.                   ---*/
133 /*---                                               bzlib.h ---*/
134 /*-------------------------------------------------------------*/
135 
136 /*--
137   This file is a part of bzip2 and/or libbzip2, a program and
138   library for lossless, block-sorting data compression.
139 
140   Copyright (C) 1996-2004 Julian R Seward.  All rights reserved.
141 
142   Redistribution and use in source and binary forms, with or without
143   modification, are permitted provided that the following conditions
144   are met:
145 
146   1. Redistributions of source code must retain the above copyright
147      notice, this list of conditions and the following disclaimer.
148 
149   2. The origin of this software must not be misrepresented; you must
150      not claim that you wrote the original software.  If you use this
151      software in a product, an acknowledgment in the product
152      documentation would be appreciated but is not required.
153 
154   3. Altered source versions must be plainly marked as such, and must
155      not be misrepresented as being the original software.
156 
157   4. The name of the author may not be used to endorse or promote
158      products derived from this software without specific prior written
159      permission.
160 
161   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
162   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
163   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
164   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
165   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
166   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
167   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
168   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
169   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
170   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
171   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
172 
173   Julian Seward, Cambridge, UK.
174   jseward@bzip.org
175   bzip2/libbzip2 version 1.0 of 21 March 2000
176 
177   This program is based on (at least) the work of:
178      Mike Burrows
179      David Wheeler
180      Peter Fenwick
181      Alistair Moffat
182      Radford Neal
183      Ian H. Witten
184      Robert Sedgewick
185      Jon L. Bentley
186 
187   For more information on these sources, see the manual.
188 --*/
189 
190 
191 #ifndef _BZLIB_H
192 #define _BZLIB_H
193 
194 #ifdef __cplusplus
195 extern "C" {
196 #endif
197 
198 #define BZ_RUN               0
199 #define BZ_FLUSH             1
200 #define BZ_FINISH            2
201 
202 #define BZ_OK                0
203 #define BZ_RUN_OK            1
204 #define BZ_FLUSH_OK          2
205 #define BZ_FINISH_OK         3
206 #define BZ_STREAM_END        4
207 #define BZ_SEQUENCE_ERROR    (-1)
208 #define BZ_PARAM_ERROR       (-2)
209 #define BZ_MEM_ERROR         (-3)
210 #define BZ_DATA_ERROR        (-4)
211 #define BZ_DATA_ERROR_MAGIC  (-5)
212 #define BZ_IO_ERROR          (-6)
213 #define BZ_UNEXPECTED_EOF    (-7)
214 #define BZ_OUTBUFF_FULL      (-8)
215 #define BZ_CONFIG_ERROR      (-9)
216 
217 typedef
218    struct {
219       char *next_in;
220       unsigned int avail_in;
221       unsigned int total_in_lo32;
222       unsigned int total_in_hi32;
223 
224       char *next_out;
225       unsigned int avail_out;
226       unsigned int total_out_lo32;
227       unsigned int total_out_hi32;
228 
229       void *state;
230 
231       void *(*bzalloc)(void *,int,int);
232       void (*bzfree)(void *,void *);
233       void *opaque;
234    }
235    bz_stream;
236 
237 
238 #ifndef BZ_IMPORT
239 #define BZ_EXPORT
240 #endif
241 
242 #ifndef BZ_NO_STDIO
243 /* Need a definitition for FILE */
244 #include <stdio.h>
245 #endif
246 
247 #ifdef _WIN32
248 #   include <windows.h>
249 #   ifdef small
250       /* windows.h define small to char */
251 #      undef small
252 #   endif
253 #   ifdef BZ_EXPORT
254 #   define BZ_API(func) WINAPI func
255 #   define BZ_EXTERN extern
256 #   else
257    /* import windows dll dynamically */
258 #   define BZ_API(func) (WINAPI * func)
259 #   define BZ_EXTERN
260 #   endif
261 #else
262 #   define BZ_API(func) func
263 #   define BZ_EXTERN extern
264 #endif
265 
266 
267 /*-- Core (low-level) library functions --*/
268 
269 BZ_EXTERN int BZ_API(BZ2_bzCompressInit) (
270       bz_stream* strm,
271       int        blockSize100k,
272       int        verbosity,
273       int        workFactor
274    );
275 
276 BZ_EXTERN int BZ_API(BZ2_bzCompress) (
277       bz_stream* strm,
278       int action
279    );
280 
281 BZ_EXTERN int BZ_API(BZ2_bzCompressEnd) (
282       bz_stream* strm
283    );
284 
285 BZ_EXTERN int BZ_API(BZ2_bzDecompressInit) (
286       bz_stream *strm,
287       int       verbosity,
288       int       small
289    );
290 
291 BZ_EXTERN int BZ_API(BZ2_bzDecompress) (
292       bz_stream* strm
293    );
294 
295 BZ_EXTERN int BZ_API(BZ2_bzDecompressEnd) (
296       bz_stream *strm
297    );
298 
299 
300 
301 /*-- High(er) level library functions --*/
302 
303 #ifndef BZ_NO_STDIO
304 #define BZ_MAX_UNUSED 5000
305 
306 typedef void BZFILE;
307 
308 BZ_EXTERN BZFILE* BZ_API(BZ2_bzReadOpen) (
309       int*  bzerror,
310       FILE* f,
311       int   verbosity,
312       int   small,
313       void* unused,
314       int   nUnused
315    );
316 
317 BZ_EXTERN void BZ_API(BZ2_bzReadClose) (
318       int*    bzerror,
319       BZFILE* b
320    );
321 
322 BZ_EXTERN void BZ_API(BZ2_bzReadGetUnused) (
323       int*    bzerror,
324       BZFILE* b,
325       void**  unused,
326       int*    nUnused
327    );
328 
329 BZ_EXTERN int BZ_API(BZ2_bzRead) (
330       int*    bzerror,
331       BZFILE* b,
332       void*   buf,
333       int     len
334    );
335 
336 BZ_EXTERN BZFILE* BZ_API(BZ2_bzWriteOpen) (
337       int*  bzerror,
338       FILE* f,
339       int   blockSize100k,
340       int   verbosity,
341       int   workFactor
342    );
343 
344 BZ_EXTERN void BZ_API(BZ2_bzWrite) (
345       int*    bzerror,
346       BZFILE* b,
347       void*   buf,
348       int     len
349    );
350 
351 BZ_EXTERN void BZ_API(BZ2_bzWriteClose) (
352       int*          bzerror,
353       BZFILE*       b,
354       int           abandon,
355       unsigned int* nbytes_in,
356       unsigned int* nbytes_out
357    );
358 
359 BZ_EXTERN void BZ_API(BZ2_bzWriteClose64) (
360       int*          bzerror,
361       BZFILE*       b,
362       int           abandon,
363       unsigned int* nbytes_in_lo32,
364       unsigned int* nbytes_in_hi32,
365       unsigned int* nbytes_out_lo32,
366       unsigned int* nbytes_out_hi32
367    );
368 #endif
369 
370 
371 /*-- Utility functions --*/
372 
373 BZ_EXTERN int BZ_API(BZ2_bzBuffToBuffCompress) (
374       char*         dest,
375       unsigned int* destLen,
376       char*         source,
377       unsigned int  sourceLen,
378       int           blockSize100k,
379       int           verbosity,
380       int           workFactor
381    );
382 
383 BZ_EXTERN int BZ_API(BZ2_bzBuffToBuffDecompress) (
384       char*         dest,
385       unsigned int* destLen,
386       char*         source,
387       unsigned int  sourceLen,
388       int           small,
389       int           verbosity
390    );
391 
392 
393 /*--
394    Code contributed by Yoshioka Tsuneo
395    (QWF00133@niftyserve.or.jp/tsuneo-y@is.aist-nara.ac.jp),
396    to support better zlib compatibility.
397    This code is not _officially_ part of libbzip2 (yet);
398    I haven't tested it, documented it, or considered the
399    threading-safeness of it.
400    If this code breaks, please contact both Yoshioka and me.
401 --*/
402 
403 BZ_EXTERN const char * BZ_API(BZ2_bzlibVersion) (
404       void
405    );
406 
407 #ifndef BZ_NO_STDIO
408 BZ_EXTERN BZFILE * BZ_API(BZ2_bzopen) (
409       const char *path,
410       const char *mode
411    );
412 
413 BZ_EXTERN BZFILE * BZ_API(BZ2_bzdopen) (
414       int        fd,
415       const char *mode
416    );
417 
418 BZ_EXTERN int BZ_API(BZ2_bzread) (
419       BZFILE* b,
420       void* buf,
421       int len
422    );
423 
424 BZ_EXTERN int BZ_API(BZ2_bzwrite) (
425       BZFILE* b,
426       void*   buf,
427       int     len
428    );
429 
430 BZ_EXTERN int BZ_API(BZ2_bzflush) (
431       BZFILE* b
432    );
433 
434 BZ_EXTERN void BZ_API(BZ2_bzclose) (
435       BZFILE* b
436    );
437 
438 BZ_EXTERN const char * BZ_API(BZ2_bzerror) (
439       BZFILE *b,
440       int    *errnum
441    );
442 #endif
443 
444 #ifdef __cplusplus
445 }
446 #endif
447 
448 #endif
449 
450 /*-------------------------------------------------------------*/
451 /*--- end                                           bzlib.h ---*/
452 /*-------------------------------------------------------------*/
453 
454 
455 
456 
457 /*-- General stuff. --*/
458 
459 #define BZ_VERSION  "1.0.3, 17-Oct-2004"
460 
461 typedef char            Char;
462 typedef unsigned char   Bool;
463 typedef unsigned char   UChar;
464 typedef int             Int32;
465 typedef unsigned int    UInt32;
466 typedef short           Int16;
467 typedef unsigned short  UInt16;
468 
469 #define True  ((Bool)1)
470 #define False ((Bool)0)
471 
472 #ifndef __GNUC__
473 #define __inline__  /* */
474 #endif
475 
476 #ifndef BZ_NO_STDIO
477 extern void BZ2_bz__AssertH__fail ( int errcode );
478 #define AssertH(cond,errcode) \
479    { if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); }
480 #if BZ_DEBUG
481 #define AssertD(cond,msg) \
482    { if (!(cond)) {       \
483       fprintf ( stderr,   \
484         "\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\
485       exit(1); \
486    }}
487 #else
488 #define AssertD(cond,msg) /* */
489 #endif
490 #define VPrintf0(zf) \
491    fprintf(stderr,zf)
492 #define VPrintf1(zf,za1) \
493    fprintf(stderr,zf,za1)
494 #define VPrintf2(zf,za1,za2) \
495    fprintf(stderr,zf,za1,za2)
496 #define VPrintf3(zf,za1,za2,za3) \
497    fprintf(stderr,zf,za1,za2,za3)
498 #define VPrintf4(zf,za1,za2,za3,za4) \
499    fprintf(stderr,zf,za1,za2,za3,za4)
500 #define VPrintf5(zf,za1,za2,za3,za4,za5) \
501    fprintf(stderr,zf,za1,za2,za3,za4,za5)
502 #else
503 extern void bz_internal_error ( int errcode );
504 #define AssertH(cond,errcode) \
505    { if (!(cond)) bz_internal_error ( errcode ); }
506 #define AssertD(cond,msg) /* */
507 #define VPrintf0(zf) \
508    vex_printf(zf)
509 #define VPrintf1(zf,za1) \
510    vex_printf(zf,za1)
511 #define VPrintf2(zf,za1,za2) \
512    vex_printf(zf,za1,za2)
513 #define VPrintf3(zf,za1,za2,za3) \
514    vex_printf(zf,za1,za2,za3)
515 #define VPrintf4(zf,za1,za2,za3,za4) \
516    vex_printf(zf,za1,za2,za3,za4)
517 #define VPrintf5(zf,za1,za2,za3,za4,za5) \
518    vex_printf(zf,za1,za2,za3,za4,za5)
519 #endif
520 
521 
522 #define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1)
523 #define BZFREE(ppp)  (strm->bzfree)(strm->opaque,(ppp))
524 
525 
526 /*-- Header bytes. --*/
527 
528 #define BZ_HDR_B 0x42   /* 'B' */
529 #define BZ_HDR_Z 0x5a   /* 'Z' */
530 #define BZ_HDR_h 0x68   /* 'h' */
531 #define BZ_HDR_0 0x30   /* '0' */
532 
533 /*-- Constants for the back end. --*/
534 
535 #define BZ_MAX_ALPHA_SIZE 258
536 #define BZ_MAX_CODE_LEN    23
537 
538 #define BZ_RUNA 0
539 #define BZ_RUNB 1
540 
541 #define BZ_N_GROUPS 6
542 #define BZ_G_SIZE   50
543 #define BZ_N_ITERS  4
544 
545 #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
546 
547 
548 
549 /*-- Stuff for randomising repetitive blocks. --*/
550 
551 extern Int32 BZ2_rNums[512];
552 
553 #define BZ_RAND_DECLS                          \
554    Int32 rNToGo;                               \
555    Int32 rTPos                                 \
556 
557 #define BZ_RAND_INIT_MASK                      \
558    s->rNToGo = 0;                              \
559    s->rTPos  = 0                               \
560 
561 #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)
562 
563 #define BZ_RAND_UPD_MASK                       \
564    if (s->rNToGo == 0) {                       \
565       s->rNToGo = BZ2_rNums[s->rTPos];         \
566       s->rTPos++;                              \
567       if (s->rTPos == 512) s->rTPos = 0;       \
568    }                                           \
569    s->rNToGo--;
570 
571 
572 
573 /*-- Stuff for doing CRCs. --*/
574 
575 extern UInt32 BZ2_crc32Table[256];
576 
577 #define BZ_INITIALISE_CRC(crcVar)              \
578 {                                              \
579    crcVar = 0xffffffffL;                       \
580 }
581 
582 #define BZ_FINALISE_CRC(crcVar)                \
583 {                                              \
584    crcVar = ~(crcVar);                         \
585 }
586 
587 #define BZ_UPDATE_CRC(crcVar,cha)              \
588 {                                              \
589    crcVar = (crcVar << 8) ^                    \
590             BZ2_crc32Table[(crcVar >> 24) ^    \
591                            ((UChar)cha)];      \
592 }
593 
594 
595 
596 /*-- States and modes for compression. --*/
597 
598 #define BZ_M_IDLE      1
599 #define BZ_M_RUNNING   2
600 #define BZ_M_FLUSHING  3
601 #define BZ_M_FINISHING 4
602 
603 #define BZ_S_OUTPUT    1
604 #define BZ_S_INPUT     2
605 
606 #define BZ_N_RADIX 2
607 #define BZ_N_QSORT 12
608 #define BZ_N_SHELL 18
609 #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
610 
611 
612 
613 
614 /*-- Structure holding all the compression-side stuff. --*/
615 
616 typedef
617    struct {
618       /* pointer back to the struct bz_stream */
619       bz_stream* strm;
620 
621       /* mode this stream is in, and whether inputting */
622       /* or outputting data */
623       Int32    mode;
624       Int32    state;
625 
626       /* remembers avail_in when flush/finish requested */
627       UInt32   avail_in_expect;
628 
629       /* for doing the block sorting */
630       UInt32*  arr1;
631       UInt32*  arr2;
632       UInt32*  ftab;
633       Int32    origPtr;
634 
635       /* aliases for arr1 and arr2 */
636       UInt32*  ptr;
637       UChar*   block;
638       UInt16*  mtfv;
639       UChar*   zbits;
640 
641       /* for deciding when to use the fallback sorting algorithm */
642       Int32    workFactor;
643 
644       /* run-length-encoding of the input */
645       UInt32   state_in_ch;
646       Int32    state_in_len;
647       BZ_RAND_DECLS;
648 
649       /* input and output limits and current posns */
650       Int32    nblock;
651       Int32    nblockMAX;
652       Int32    numZ;
653       Int32    state_out_pos;
654 
655       /* map of bytes used in block */
656       Int32    nInUse;
657       Bool     inUse[256];
658       UChar    unseqToSeq[256];
659 
660       /* the buffer for bit stream creation */
661       UInt32   bsBuff;
662       Int32    bsLive;
663 
664       /* block and combined CRCs */
665       UInt32   blockCRC;
666       UInt32   combinedCRC;
667 
668       /* misc administratium */
669       Int32    verbosity;
670       Int32    blockNo;
671       Int32    blockSize100k;
672 
673       /* stuff for coding the MTF values */
674       Int32    nMTF;
675       Int32    mtfFreq    [BZ_MAX_ALPHA_SIZE];
676       UChar    selector   [BZ_MAX_SELECTORS];
677       UChar    selectorMtf[BZ_MAX_SELECTORS];
678 
679       UChar    len     [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
680       Int32    code    [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
681       Int32    rfreq   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
682       /* second dimension: only 3 needed; 4 makes index calculations faster */
683       UInt32   len_pack[BZ_MAX_ALPHA_SIZE][4];
684 
685    }
686    EState;
687 
688 
689 
690 /*-- externs for compression. --*/
691 
692 extern void
693 BZ2_blockSort ( EState* );
694 
695 extern void
696 BZ2_compressBlock ( EState*, Bool );
697 
698 extern void
699 BZ2_bsInitWrite ( EState* );
700 
701 extern void
702 BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 );
703 
704 extern void
705 BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 );
706 
707 
708 
709 /*-- states for decompression. --*/
710 
711 #define BZ_X_IDLE        1
712 #define BZ_X_OUTPUT      2
713 
714 #define BZ_X_MAGIC_1     10
715 #define BZ_X_MAGIC_2     11
716 #define BZ_X_MAGIC_3     12
717 #define BZ_X_MAGIC_4     13
718 #define BZ_X_BLKHDR_1    14
719 #define BZ_X_BLKHDR_2    15
720 #define BZ_X_BLKHDR_3    16
721 #define BZ_X_BLKHDR_4    17
722 #define BZ_X_BLKHDR_5    18
723 #define BZ_X_BLKHDR_6    19
724 #define BZ_X_BCRC_1      20
725 #define BZ_X_BCRC_2      21
726 #define BZ_X_BCRC_3      22
727 #define BZ_X_BCRC_4      23
728 #define BZ_X_RANDBIT     24
729 #define BZ_X_ORIGPTR_1   25
730 #define BZ_X_ORIGPTR_2   26
731 #define BZ_X_ORIGPTR_3   27
732 #define BZ_X_MAPPING_1   28
733 #define BZ_X_MAPPING_2   29
734 #define BZ_X_SELECTOR_1  30
735 #define BZ_X_SELECTOR_2  31
736 #define BZ_X_SELECTOR_3  32
737 #define BZ_X_CODING_1    33
738 #define BZ_X_CODING_2    34
739 #define BZ_X_CODING_3    35
740 #define BZ_X_MTF_1       36
741 #define BZ_X_MTF_2       37
742 #define BZ_X_MTF_3       38
743 #define BZ_X_MTF_4       39
744 #define BZ_X_MTF_5       40
745 #define BZ_X_MTF_6       41
746 #define BZ_X_ENDHDR_2    42
747 #define BZ_X_ENDHDR_3    43
748 #define BZ_X_ENDHDR_4    44
749 #define BZ_X_ENDHDR_5    45
750 #define BZ_X_ENDHDR_6    46
751 #define BZ_X_CCRC_1      47
752 #define BZ_X_CCRC_2      48
753 #define BZ_X_CCRC_3      49
754 #define BZ_X_CCRC_4      50
755 
756 
757 
758 /*-- Constants for the fast MTF decoder. --*/
759 
760 #define MTFA_SIZE 4096
761 #define MTFL_SIZE 16
762 
763 
764 
765 /*-- Structure holding all the decompression-side stuff. --*/
766 
767 typedef
768    struct {
769       /* pointer back to the struct bz_stream */
770       bz_stream* strm;
771 
772       /* state indicator for this stream */
773       Int32    state;
774 
775       /* for doing the final run-length decoding */
776       UChar    state_out_ch;
777       Int32    state_out_len;
778       Bool     blockRandomised;
779       BZ_RAND_DECLS;
780 
781       /* the buffer for bit stream reading */
782       UInt32   bsBuff;
783       Int32    bsLive;
784 
785       /* misc administratium */
786       Int32    blockSize100k;
787       Bool     smallDecompress;
788       Int32    currBlockNo;
789       Int32    verbosity;
790 
791       /* for undoing the Burrows-Wheeler transform */
792       Int32    origPtr;
793       UInt32   tPos;
794       Int32    k0;
795       Int32    unzftab[256];
796       Int32    nblock_used;
797       Int32    cftab[257];
798       Int32    cftabCopy[257];
799 
800       /* for undoing the Burrows-Wheeler transform (FAST) */
801       UInt32   *tt;
802 
803       /* for undoing the Burrows-Wheeler transform (SMALL) */
804       UInt16   *ll16;
805       UChar    *ll4;
806 
807       /* stored and calculated CRCs */
808       UInt32   storedBlockCRC;
809       UInt32   storedCombinedCRC;
810       UInt32   calculatedBlockCRC;
811       UInt32   calculatedCombinedCRC;
812 
813       /* map of bytes used in block */
814       Int32    nInUse;
815       Bool     inUse[256];
816       Bool     inUse16[16];
817       UChar    seqToUnseq[256];
818 
819       /* for decoding the MTF values */
820       UChar    mtfa   [MTFA_SIZE];
821       Int32    mtfbase[256 / MTFL_SIZE];
822       UChar    selector   [BZ_MAX_SELECTORS];
823       UChar    selectorMtf[BZ_MAX_SELECTORS];
824       UChar    len  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
825 
826       Int32    limit  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
827       Int32    base   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
828       Int32    perm   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
829       Int32    minLens[BZ_N_GROUPS];
830 
831       /* save area for scalars in the main decompress code */
832       Int32    save_i;
833       Int32    save_j;
834       Int32    save_t;
835       Int32    save_alphaSize;
836       Int32    save_nGroups;
837       Int32    save_nSelectors;
838       Int32    save_EOB;
839       Int32    save_groupNo;
840       Int32    save_groupPos;
841       Int32    save_nextSym;
842       Int32    save_nblockMAX;
843       Int32    save_nblock;
844       Int32    save_es;
845       Int32    save_N;
846       Int32    save_curr;
847       Int32    save_zt;
848       Int32    save_zn;
849       Int32    save_zvec;
850       Int32    save_zj;
851       Int32    save_gSel;
852       Int32    save_gMinlen;
853       Int32*   save_gLimit;
854       Int32*   save_gBase;
855       Int32*   save_gPerm;
856 
857    }
858    DState;
859 
860 
861 
862 /*-- Macros for decompression. --*/
863 
864 #define BZ_GET_FAST(cccc)                     \
865     s->tPos = s->tt[s->tPos];                 \
866     cccc = (UChar)(s->tPos & 0xff);           \
867     s->tPos >>= 8;
868 
869 #define BZ_GET_FAST_C(cccc)                   \
870     c_tPos = c_tt[c_tPos];                    \
871     cccc = (UChar)(c_tPos & 0xff);            \
872     c_tPos >>= 8;
873 
874 #define SET_LL4(i,n)                                          \
875    { if (((i) & 0x1) == 0)                                    \
876         s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else    \
877         s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4);  \
878    }
879 
880 #define GET_LL4(i)                             \
881    ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)
882 
883 #define SET_LL(i,n)                          \
884    { s->ll16[i] = (UInt16)(n & 0x0000ffff);  \
885      SET_LL4(i, n >> 16);                    \
886    }
887 
888 #define GET_LL(i) \
889    (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16))
890 
891 #define BZ_GET_SMALL(cccc)                            \
892       cccc = BZ2_indexIntoF ( s->tPos, s->cftab );    \
893       s->tPos = GET_LL(s->tPos);
894 
895 
896 /*-- externs for decompression. --*/
897 
898 extern Int32
899 BZ2_indexIntoF ( Int32, Int32* );
900 
901 extern Int32
902 BZ2_decompress ( DState* );
903 
904 extern void
905 BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*,
906                            Int32,  Int32, Int32 );
907 
908 
909 #endif
910 
911 
912 /*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/
913 
914 #ifdef BZ_NO_STDIO
915 #ifndef NULL
916 #define NULL 0
917 #endif
918 #endif
919 
920 
921 /*-------------------------------------------------------------*/
922 /*--- end                                   bzlib_private.h ---*/
923 /*-------------------------------------------------------------*/
924 
925 
926 /* Something which has the same size as void* on the host.  That is,
927    it is 32 bits on a 32-bit host and 64 bits on a 64-bit host, and so
928    it can safely be coerced to and from a pointer type on the host
929    machine. */
930 typedef  unsigned long HWord;
931 typedef  char          HChar;
932 typedef  signed int    Int;
933 typedef  unsigned int  UInt;
934 
935 typedef    signed long long int   Long;
936 typedef  unsigned long long int   ULong;
937 
938 
939 /////////////////////////////////////////////////////////////////////
940 /////////////////////////////////////////////////////////////////////
941 
942 static HWord (*serviceFn)(HWord,HWord) = 0;
943 
944 #if 0
945 static char* my_strcpy ( char* dest, const char* src )
946 {
947    char* dest_orig = dest;
948    while (*src) *dest++ = *src++;
949    *dest = 0;
950    return dest_orig;
951 }
952 
953 static void* my_memcpy ( void *dest, const void *src, int sz )
954 {
955    const char *s = (const char *)src;
956    char *d = (char *)dest;
957 
958    while (sz--)
959       *d++ = *s++;
960 
961    return dest;
962 }
963 
964 static void* my_memmove( void *dst, const void *src, unsigned int len )
965 {
966     register char *d;
967     register char *s;
968     if ( dst > src ) {
969         d = (char *)dst + len - 1;
970         s = (char *)src + len - 1;
971         while ( len >= 4 ) {
972             *d-- = *s--;
973             *d-- = *s--;
974             *d-- = *s--;
975             *d-- = *s--;
976             len -= 4;
977         }
978         while ( len-- ) {
979             *d-- = *s--;
980         }
981     } else if ( dst < src ) {
982         d = (char *)dst;
983         s = (char *)src;
984         while ( len >= 4 ) {
985             *d++ = *s++;
986             *d++ = *s++;
987             *d++ = *s++;
988             *d++ = *s++;
989             len -= 4;
990         }
991         while ( len-- ) {
992             *d++ = *s++;
993         }
994     }
995     return dst;
996 }
997 #endif
998 
my_strcat(char * dest,const char * src)999 char* my_strcat ( char* dest, const char* src )
1000 {
1001    char* dest_orig = dest;
1002    while (*dest) dest++;
1003    while (*src) *dest++ = *src++;
1004    *dest = 0;
1005    return dest_orig;
1006 }
1007 
1008 
1009 /////////////////////////////////////////////////////////////////////
1010 
vex_log_bytes(char * p,int n)1011 static void vex_log_bytes ( char* p, int n )
1012 {
1013    int i;
1014    for (i = 0; i < n; i++)
1015       (*serviceFn)( 1, (int)p[i] );
1016 }
1017 
1018 /*---------------------------------------------------------*/
1019 /*--- vex_printf                                        ---*/
1020 /*---------------------------------------------------------*/
1021 
1022 /* This should be the only <...> include in the entire VEX library.
1023    New code for vex_util.c should go above this point. */
1024 #include <stdarg.h>
1025 
vex_toupper(HChar c)1026 static HChar vex_toupper ( HChar c )
1027 {
1028    if (c >= 'a' && c <= 'z')
1029       return c + ('A' - 'a');
1030    else
1031       return c;
1032 }
1033 
vex_strlen(const HChar * str)1034 static Int vex_strlen ( const HChar* str )
1035 {
1036    Int i = 0;
1037    while (str[i] != 0) i++;
1038    return i;
1039 }
1040 
vex_streq(const HChar * s1,const HChar * s2)1041 Bool vex_streq ( const HChar* s1, const HChar* s2 )
1042 {
1043    while (True) {
1044       if (*s1 == 0 && *s2 == 0)
1045          return True;
1046       if (*s1 != *s2)
1047          return False;
1048       s1++;
1049       s2++;
1050    }
1051 }
1052 
1053 /* Some flags.  */
1054 #define VG_MSG_SIGNED    1 /* The value is signed. */
1055 #define VG_MSG_ZJUSTIFY  2 /* Must justify with '0'. */
1056 #define VG_MSG_LJUSTIFY  4 /* Must justify on the left. */
1057 #define VG_MSG_PAREN     8 /* Parenthesize if present (for %y) */
1058 #define VG_MSG_COMMA    16 /* Add commas to numbers (for %d, %u) */
1059 
1060 /* Copy a string into the buffer. */
1061 static UInt
myvprintf_str(void (* send)(HChar),Int flags,Int width,HChar * str,Bool capitalise)1062 myvprintf_str ( void(*send)(HChar), Int flags, Int width, HChar* str,
1063                 Bool capitalise )
1064 {
1065 #  define MAYBE_TOUPPER(ch) (capitalise ? vex_toupper(ch) : (ch))
1066    UInt ret = 0;
1067    Int i, extra;
1068    Int len = vex_strlen(str);
1069 
1070    if (width == 0) {
1071       ret += len;
1072       for (i = 0; i < len; i++)
1073          send(MAYBE_TOUPPER(str[i]));
1074       return ret;
1075    }
1076 
1077    if (len > width) {
1078       ret += width;
1079       for (i = 0; i < width; i++)
1080          send(MAYBE_TOUPPER(str[i]));
1081       return ret;
1082    }
1083 
1084    extra = width - len;
1085    if (flags & VG_MSG_LJUSTIFY) {
1086       ret += extra;
1087       for (i = 0; i < extra; i++)
1088          send(' ');
1089    }
1090    ret += len;
1091    for (i = 0; i < len; i++)
1092       send(MAYBE_TOUPPER(str[i]));
1093    if (!(flags & VG_MSG_LJUSTIFY)) {
1094       ret += extra;
1095       for (i = 0; i < extra; i++)
1096          send(' ');
1097    }
1098 
1099 #  undef MAYBE_TOUPPER
1100 
1101    return ret;
1102 }
1103 
1104 /* Write P into the buffer according to these args:
1105  *  If SIGN is true, p is a signed.
1106  *  BASE is the base.
1107  *  If WITH_ZERO is true, '0' must be added.
1108  *  WIDTH is the width of the field.
1109  */
1110 static UInt
myvprintf_int64(void (* send)(HChar),Int flags,Int base,Int width,ULong pL)1111 myvprintf_int64 ( void(*send)(HChar), Int flags, Int base, Int width, ULong pL)
1112 {
1113    HChar buf[40];
1114    Int   ind = 0;
1115    Int   i, nc = 0;
1116    Bool  neg = False;
1117    HChar *digits = "0123456789ABCDEF";
1118    UInt  ret = 0;
1119    UInt  p = (UInt)pL;
1120 
1121    if (base < 2 || base > 16)
1122       return ret;
1123 
1124    if ((flags & VG_MSG_SIGNED) && (Int)p < 0) {
1125       p   = - (Int)p;
1126       neg = True;
1127    }
1128 
1129    if (p == 0)
1130       buf[ind++] = '0';
1131    else {
1132       while (p > 0) {
1133          if ((flags & VG_MSG_COMMA) && 10 == base &&
1134              0 == (ind-nc) % 3 && 0 != ind)
1135          {
1136             buf[ind++] = ',';
1137             nc++;
1138          }
1139          buf[ind++] = digits[p % base];
1140          p /= base;
1141       }
1142    }
1143 
1144    if (neg)
1145       buf[ind++] = '-';
1146 
1147    if (width > 0 && !(flags & VG_MSG_LJUSTIFY)) {
1148       for(; ind < width; ind++) {
1149 	//vassert(ind < 39);
1150          buf[ind] = ((flags & VG_MSG_ZJUSTIFY) ? '0': ' ');
1151       }
1152    }
1153 
1154    /* Reverse copy to buffer.  */
1155    ret += ind;
1156    for (i = ind -1; i >= 0; i--) {
1157       send(buf[i]);
1158    }
1159    if (width > 0 && (flags & VG_MSG_LJUSTIFY)) {
1160       for(; ind < width; ind++) {
1161 	 ret++;
1162          send(' ');  // Never pad with zeroes on RHS -- changes the value!
1163       }
1164    }
1165    return ret;
1166 }
1167 
1168 
1169 /* A simple vprintf().  */
1170 static
vprintf_wrk(void (* send)(HChar),const HChar * format,va_list vargs)1171 UInt vprintf_wrk ( void(*send)(HChar), const HChar *format, va_list vargs )
1172 {
1173    UInt ret = 0;
1174    int i;
1175    int flags;
1176    int width;
1177    Bool is_long;
1178 
1179    /* We assume that vargs has already been initialised by the
1180       caller, using va_start, and that the caller will similarly
1181       clean up with va_end.
1182    */
1183 
1184    for (i = 0; format[i] != 0; i++) {
1185       if (format[i] != '%') {
1186          send(format[i]);
1187 	 ret++;
1188          continue;
1189       }
1190       i++;
1191       /* A '%' has been found.  Ignore a trailing %. */
1192       if (format[i] == 0)
1193          break;
1194       if (format[i] == '%') {
1195          /* `%%' is replaced by `%'. */
1196          send('%');
1197 	 ret++;
1198          continue;
1199       }
1200       flags = 0;
1201       is_long = False;
1202       width = 0; /* length of the field. */
1203       if (format[i] == '(') {
1204 	 flags |= VG_MSG_PAREN;
1205 	 i++;
1206       }
1207       /* If ',' follows '%', commas will be inserted. */
1208       if (format[i] == ',') {
1209          flags |= VG_MSG_COMMA;
1210          i++;
1211       }
1212       /* If '-' follows '%', justify on the left. */
1213       if (format[i] == '-') {
1214          flags |= VG_MSG_LJUSTIFY;
1215          i++;
1216       }
1217       /* If '0' follows '%', pads will be inserted. */
1218       if (format[i] == '0') {
1219          flags |= VG_MSG_ZJUSTIFY;
1220          i++;
1221       }
1222       /* Compute the field length. */
1223       while (format[i] >= '0' && format[i] <= '9') {
1224          width *= 10;
1225          width += format[i++] - '0';
1226       }
1227       while (format[i] == 'l') {
1228          i++;
1229          is_long = True;
1230       }
1231 
1232       switch (format[i]) {
1233          case 'd': /* %d */
1234             flags |= VG_MSG_SIGNED;
1235             if (is_long)
1236                ret += myvprintf_int64(send, flags, 10, width,
1237 				      (ULong)(va_arg (vargs, Long)));
1238             else
1239                ret += myvprintf_int64(send, flags, 10, width,
1240 				      (ULong)(va_arg (vargs, Int)));
1241             break;
1242          case 'u': /* %u */
1243             if (is_long)
1244                ret += myvprintf_int64(send, flags, 10, width,
1245 				      (ULong)(va_arg (vargs, ULong)));
1246             else
1247                ret += myvprintf_int64(send, flags, 10, width,
1248 				      (ULong)(va_arg (vargs, UInt)));
1249             break;
1250          case 'p': /* %p */
1251 	    ret += 2;
1252             send('0');
1253             send('x');
1254             ret += myvprintf_int64(send, flags, 16, width,
1255 				   (ULong)((HWord)va_arg (vargs, void *)));
1256             break;
1257          case 'x': /* %x */
1258             if (is_long)
1259                ret += myvprintf_int64(send, flags, 16, width,
1260 				      (ULong)(va_arg (vargs, ULong)));
1261             else
1262                ret += myvprintf_int64(send, flags, 16, width,
1263 				      (ULong)(va_arg (vargs, UInt)));
1264             break;
1265          case 'c': /* %c */
1266 	    ret++;
1267             send((va_arg (vargs, int)));
1268             break;
1269          case 's': case 'S': { /* %s */
1270             char *str = va_arg (vargs, char *);
1271             if (str == (char*) 0) str = "(null)";
1272             ret += myvprintf_str(send, flags, width, str,
1273                                  (format[i]=='S'));
1274             break;
1275 	 }
1276 #        if 0
1277 	 case 'y': { /* %y - print symbol */
1278 	    Addr a = va_arg(vargs, Addr);
1279 
1280 
1281 
1282             HChar *name;
1283 	    if (VG_(get_fnname_w_offset)(a, &name)) {
1284                HChar buf[1 + VG_strlen(name) + 1 + 1];
1285 	       if (flags & VG_MSG_PAREN) {
1286                   VG_(sprintf)(str, "(%s)", name):
1287 	       } else {
1288                   VG_(sprintf)(str, "%s", name):
1289                }
1290 	       ret += myvprintf_str(send, flags, width, buf, 0);
1291 	    }
1292 	    break;
1293 	 }
1294 #        endif
1295          default:
1296             break;
1297       }
1298    }
1299    return ret;
1300 }
1301 
1302 
1303 /* A general replacement for printf().  Note that only low-level
1304    debugging info should be sent via here.  The official route is to
1305    to use vg_message().  This interface is deprecated.
1306 */
1307 static HChar myprintf_buf[1000];
1308 static Int   n_myprintf_buf;
1309 
add_to_myprintf_buf(HChar c)1310 static void add_to_myprintf_buf ( HChar c )
1311 {
1312    if (c == '\n' || n_myprintf_buf >= 1000-10 /*paranoia*/ ) {
1313       (*vex_log_bytes)( myprintf_buf, vex_strlen(myprintf_buf) );
1314       n_myprintf_buf = 0;
1315       myprintf_buf[n_myprintf_buf] = 0;
1316    }
1317    myprintf_buf[n_myprintf_buf++] = c;
1318    myprintf_buf[n_myprintf_buf] = 0;
1319 }
1320 
vex_printf(const char * format,...)1321 static UInt vex_printf ( const char *format, ... )
1322 {
1323    UInt ret;
1324    va_list vargs;
1325    va_start(vargs,format);
1326 
1327    n_myprintf_buf = 0;
1328    myprintf_buf[n_myprintf_buf] = 0;
1329    ret = vprintf_wrk ( add_to_myprintf_buf, format, vargs );
1330 
1331    if (n_myprintf_buf > 0) {
1332       (*vex_log_bytes)( myprintf_buf, n_myprintf_buf );
1333    }
1334 
1335    va_end(vargs);
1336 
1337    return ret;
1338 }
1339 
1340 /*---------------------------------------------------------------*/
1341 /*--- end                                          vex_util.c ---*/
1342 /*---------------------------------------------------------------*/
1343 
1344 
1345 /////////////////////////////////////////////////////////////////////
1346 /////////////////////////////////////////////////////////////////////
1347 /////////////////////////////////////////////////////////////////////
1348 /////////////////////////////////////////////////////////////////////
1349 
1350 
1351 /*-------------------------------------------------------------*/
1352 /*--- Decompression machinery                               ---*/
1353 /*---                                          decompress.c ---*/
1354 /*-------------------------------------------------------------*/
1355 
1356 /*--
1357   This file is a part of bzip2 and/or libbzip2, a program and
1358   library for lossless, block-sorting data compression.
1359 
1360   Copyright (C) 1996-2004 Julian R Seward.  All rights reserved.
1361 
1362   Redistribution and use in source and binary forms, with or without
1363   modification, are permitted provided that the following conditions
1364   are met:
1365 
1366   1. Redistributions of source code must retain the above copyright
1367      notice, this list of conditions and the following disclaimer.
1368 
1369   2. The origin of this software must not be misrepresented; you must
1370      not claim that you wrote the original software.  If you use this
1371      software in a product, an acknowledgment in the product
1372      documentation would be appreciated but is not required.
1373 
1374   3. Altered source versions must be plainly marked as such, and must
1375      not be misrepresented as being the original software.
1376 
1377   4. The name of the author may not be used to endorse or promote
1378      products derived from this software without specific prior written
1379      permission.
1380 
1381   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
1382   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
1383   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1384   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
1385   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1386   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
1387   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1388   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
1389   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
1390   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
1391   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1392 
1393   Julian Seward, Cambridge, UK.
1394   jseward@bzip.org
1395   bzip2/libbzip2 version 1.0 of 21 March 2000
1396 
1397   This program is based on (at least) the work of:
1398      Mike Burrows
1399      David Wheeler
1400      Peter Fenwick
1401      Alistair Moffat
1402      Radford Neal
1403      Ian H. Witten
1404      Robert Sedgewick
1405      Jon L. Bentley
1406 
1407   For more information on these sources, see the manual.
1408 --*/
1409 
1410 
1411 
1412 
1413 /*---------------------------------------------------*/
1414 static
makeMaps_d(DState * s)1415 void makeMaps_d ( DState* s )
1416 {
1417    Int32 i;
1418    s->nInUse = 0;
1419    for (i = 0; i < 256; i++)
1420       if (s->inUse[i]) {
1421          s->seqToUnseq[s->nInUse] = i;
1422          s->nInUse++;
1423       }
1424 }
1425 
1426 
1427 /*---------------------------------------------------*/
1428 #define RETURN(rrr)                               \
1429    { retVal = rrr; goto save_state_and_return; };
1430 
1431 #define GET_BITS(lll,vvv,nnn)                     \
1432    case lll: s->state = lll;                      \
1433    while (True) {                                 \
1434       if (s->bsLive >= nnn) {                     \
1435          UInt32 v;                                \
1436          v = (s->bsBuff >>                        \
1437              (s->bsLive-nnn)) & ((1 << nnn)-1);   \
1438          s->bsLive -= nnn;                        \
1439          vvv = v;                                 \
1440          break;                                   \
1441       }                                           \
1442       if (s->strm->avail_in == 0) RETURN(BZ_OK);  \
1443       s->bsBuff                                   \
1444          = (s->bsBuff << 8) |                     \
1445            ((UInt32)                              \
1446               (*((UChar*)(s->strm->next_in))));   \
1447       s->bsLive += 8;                             \
1448       s->strm->next_in++;                         \
1449       s->strm->avail_in--;                        \
1450       s->strm->total_in_lo32++;                   \
1451       if (s->strm->total_in_lo32 == 0)            \
1452          s->strm->total_in_hi32++;                \
1453    }
1454 
1455 #define GET_UCHAR(lll,uuu)                        \
1456    GET_BITS(lll,uuu,8)
1457 
1458 #define GET_BIT(lll,uuu)                          \
1459    GET_BITS(lll,uuu,1)
1460 
1461 /*---------------------------------------------------*/
1462 #define GET_MTF_VAL(label1,label2,lval)           \
1463 {                                                 \
1464    if (groupPos == 0) {                           \
1465       groupNo++;                                  \
1466       if (groupNo >= nSelectors)                  \
1467          RETURN(BZ_DATA_ERROR);                   \
1468       groupPos = BZ_G_SIZE;                       \
1469       gSel = s->selector[groupNo];                \
1470       gMinlen = s->minLens[gSel];                 \
1471       gLimit = &(s->limit[gSel][0]);              \
1472       gPerm = &(s->perm[gSel][0]);                \
1473       gBase = &(s->base[gSel][0]);                \
1474    }                                              \
1475    groupPos--;                                    \
1476    zn = gMinlen;                                  \
1477    GET_BITS(label1, zvec, zn);                    \
1478    while (1) {                                    \
1479       if (zn > 20 /* the longest code */)         \
1480          RETURN(BZ_DATA_ERROR);                   \
1481       if (zvec <= gLimit[zn]) break;              \
1482       zn++;                                       \
1483       GET_BIT(label2, zj);                        \
1484       zvec = (zvec << 1) | zj;                    \
1485    };                                             \
1486    if (zvec - gBase[zn] < 0                       \
1487        || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE)  \
1488       RETURN(BZ_DATA_ERROR);                      \
1489    lval = gPerm[zvec - gBase[zn]];                \
1490 }
1491 
1492 
1493 
1494 /*---------------------------------------------------*/
BZ2_indexIntoF(Int32 indx,Int32 * cftab)1495 Int32 BZ2_indexIntoF ( Int32 indx, Int32 *cftab )
1496 {
1497    Int32 nb, na, mid;
1498    nb = 0;
1499    na = 256;
1500    do {
1501       mid = (nb + na) >> 1;
1502       if (indx >= cftab[mid]) nb = mid; else na = mid;
1503    }
1504    while (na - nb != 1);
1505    return nb;
1506 }
1507 
1508 /*---------------------------------------------------*/
BZ2_decompress(DState * s)1509 Int32 BZ2_decompress ( DState* s )
1510 {
1511    UChar      uc;
1512    Int32      retVal;
1513    Int32      minLen, maxLen;
1514    bz_stream* strm = s->strm;
1515 
1516    /* stuff that needs to be saved/restored */
1517    Int32  i;
1518    Int32  j;
1519    Int32  t;
1520    Int32  alphaSize;
1521    Int32  nGroups;
1522    Int32  nSelectors;
1523    Int32  EOB;
1524    Int32  groupNo;
1525    Int32  groupPos;
1526    Int32  nextSym;
1527    Int32  nblockMAX;
1528    Int32  nblock;
1529    Int32  es;
1530    Int32  N;
1531    Int32  curr;
1532    Int32  zt;
1533    Int32  zn;
1534    Int32  zvec;
1535    Int32  zj;
1536    Int32  gSel;
1537    Int32  gMinlen;
1538    Int32* gLimit;
1539    Int32* gBase;
1540    Int32* gPerm;
1541 
1542    if (s->state == BZ_X_MAGIC_1) {
1543       /*initialise the save area*/
1544       s->save_i           = 0;
1545       s->save_j           = 0;
1546       s->save_t           = 0;
1547       s->save_alphaSize   = 0;
1548       s->save_nGroups     = 0;
1549       s->save_nSelectors  = 0;
1550       s->save_EOB         = 0;
1551       s->save_groupNo     = 0;
1552       s->save_groupPos    = 0;
1553       s->save_nextSym     = 0;
1554       s->save_nblockMAX   = 0;
1555       s->save_nblock      = 0;
1556       s->save_es          = 0;
1557       s->save_N           = 0;
1558       s->save_curr        = 0;
1559       s->save_zt          = 0;
1560       s->save_zn          = 0;
1561       s->save_zvec        = 0;
1562       s->save_zj          = 0;
1563       s->save_gSel        = 0;
1564       s->save_gMinlen     = 0;
1565       s->save_gLimit      = NULL;
1566       s->save_gBase       = NULL;
1567       s->save_gPerm       = NULL;
1568    }
1569 
1570    /*restore from the save area*/
1571    i           = s->save_i;
1572    j           = s->save_j;
1573    t           = s->save_t;
1574    alphaSize   = s->save_alphaSize;
1575    nGroups     = s->save_nGroups;
1576    nSelectors  = s->save_nSelectors;
1577    EOB         = s->save_EOB;
1578    groupNo     = s->save_groupNo;
1579    groupPos    = s->save_groupPos;
1580    nextSym     = s->save_nextSym;
1581    nblockMAX   = s->save_nblockMAX;
1582    nblock      = s->save_nblock;
1583    es          = s->save_es;
1584    N           = s->save_N;
1585    curr        = s->save_curr;
1586    zt          = s->save_zt;
1587    zn          = s->save_zn;
1588    zvec        = s->save_zvec;
1589    zj          = s->save_zj;
1590    gSel        = s->save_gSel;
1591    gMinlen     = s->save_gMinlen;
1592    gLimit      = s->save_gLimit;
1593    gBase       = s->save_gBase;
1594    gPerm       = s->save_gPerm;
1595 
1596    retVal = BZ_OK;
1597 
1598    switch (s->state) {
1599 
1600       GET_UCHAR(BZ_X_MAGIC_1, uc);
1601       if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);
1602 
1603       GET_UCHAR(BZ_X_MAGIC_2, uc);
1604       if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);
1605 
1606       GET_UCHAR(BZ_X_MAGIC_3, uc)
1607       if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);
1608 
1609       GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
1610       if (s->blockSize100k < (BZ_HDR_0 + 1) ||
1611           s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
1612       s->blockSize100k -= BZ_HDR_0;
1613 
1614       if (s->smallDecompress) {
1615          s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
1616          s->ll4  = BZALLOC(
1617                       ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
1618                    );
1619          if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
1620       } else {
1621          s->tt  = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
1622          if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
1623       }
1624 
1625       GET_UCHAR(BZ_X_BLKHDR_1, uc);
1626 
1627       if (uc == 0x17) goto endhdr_2;
1628       if (uc != 0x31) RETURN(BZ_DATA_ERROR);
1629       GET_UCHAR(BZ_X_BLKHDR_2, uc);
1630       if (uc != 0x41) RETURN(BZ_DATA_ERROR);
1631       GET_UCHAR(BZ_X_BLKHDR_3, uc);
1632       if (uc != 0x59) RETURN(BZ_DATA_ERROR);
1633       GET_UCHAR(BZ_X_BLKHDR_4, uc);
1634       if (uc != 0x26) RETURN(BZ_DATA_ERROR);
1635       GET_UCHAR(BZ_X_BLKHDR_5, uc);
1636       if (uc != 0x53) RETURN(BZ_DATA_ERROR);
1637       GET_UCHAR(BZ_X_BLKHDR_6, uc);
1638       if (uc != 0x59) RETURN(BZ_DATA_ERROR);
1639 
1640       s->currBlockNo++;
1641       if (s->verbosity >= 2)
1642          VPrintf1 ( "\n    [%d: huff+mtf ", s->currBlockNo );
1643 
1644       s->storedBlockCRC = 0;
1645       GET_UCHAR(BZ_X_BCRC_1, uc);
1646       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1647       GET_UCHAR(BZ_X_BCRC_2, uc);
1648       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1649       GET_UCHAR(BZ_X_BCRC_3, uc);
1650       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1651       GET_UCHAR(BZ_X_BCRC_4, uc);
1652       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1653 
1654       GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
1655 
1656       s->origPtr = 0;
1657       GET_UCHAR(BZ_X_ORIGPTR_1, uc);
1658       s->origPtr = (s->origPtr << 8) | ((Int32)uc);
1659       GET_UCHAR(BZ_X_ORIGPTR_2, uc);
1660       s->origPtr = (s->origPtr << 8) | ((Int32)uc);
1661       GET_UCHAR(BZ_X_ORIGPTR_3, uc);
1662       s->origPtr = (s->origPtr << 8) | ((Int32)uc);
1663 
1664       if (s->origPtr < 0)
1665          RETURN(BZ_DATA_ERROR);
1666       if (s->origPtr > 10 + 100000*s->blockSize100k)
1667          RETURN(BZ_DATA_ERROR);
1668 
1669       /*--- Receive the mapping table ---*/
1670       for (i = 0; i < 16; i++) {
1671          GET_BIT(BZ_X_MAPPING_1, uc);
1672          if (uc == 1)
1673             s->inUse16[i] = True; else
1674             s->inUse16[i] = False;
1675       }
1676 
1677       for (i = 0; i < 256; i++) s->inUse[i] = False;
1678 
1679       for (i = 0; i < 16; i++)
1680          if (s->inUse16[i])
1681             for (j = 0; j < 16; j++) {
1682                GET_BIT(BZ_X_MAPPING_2, uc);
1683                if (uc == 1) s->inUse[i * 16 + j] = True;
1684             }
1685       makeMaps_d ( s );
1686       if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
1687       alphaSize = s->nInUse+2;
1688 
1689       /*--- Now the selectors ---*/
1690       GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
1691       if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
1692       GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
1693       if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
1694       for (i = 0; i < nSelectors; i++) {
1695          j = 0;
1696          while (True) {
1697             GET_BIT(BZ_X_SELECTOR_3, uc);
1698             if (uc == 0) break;
1699 croak( 2 + (char*)&i );
1700             j++;
1701             if (j >= nGroups) RETURN(BZ_DATA_ERROR);
1702          }
1703          s->selectorMtf[i] = j;
1704       }
1705 
1706       /*--- Undo the MTF values for the selectors. ---*/
1707       {
1708          UChar pos[BZ_N_GROUPS], tmp, v;
1709          for (v = 0; v < nGroups; v++) pos[v] = v;
1710 
1711          for (i = 0; i < nSelectors; i++) {
1712             v = s->selectorMtf[i];
1713             tmp = pos[v];
1714             while (v > 0) { pos[v] = pos[v-1]; v--; }
1715             pos[0] = tmp;
1716             s->selector[i] = tmp;
1717          }
1718       }
1719 
1720       /*--- Now the coding tables ---*/
1721       for (t = 0; t < nGroups; t++) {
1722          GET_BITS(BZ_X_CODING_1, curr, 5);
1723          for (i = 0; i < alphaSize; i++) {
1724             while (True) {
1725                if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
1726                GET_BIT(BZ_X_CODING_2, uc);
1727                if (uc == 0) break;
1728                GET_BIT(BZ_X_CODING_3, uc);
1729                if (uc == 0) curr++; else curr--;
1730             }
1731             s->len[t][i] = curr;
1732          }
1733       }
1734 
1735       /*--- Create the Huffman decoding tables ---*/
1736       for (t = 0; t < nGroups; t++) {
1737          minLen = 32;
1738          maxLen = 0;
1739          for (i = 0; i < alphaSize; i++) {
1740             if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
1741             if (s->len[t][i] < minLen) minLen = s->len[t][i];
1742          }
1743          BZ2_hbCreateDecodeTables (
1744             &(s->limit[t][0]),
1745             &(s->base[t][0]),
1746             &(s->perm[t][0]),
1747             &(s->len[t][0]),
1748             minLen, maxLen, alphaSize
1749          );
1750          s->minLens[t] = minLen;
1751       }
1752 
1753       /*--- Now the MTF values ---*/
1754 
1755       EOB      = s->nInUse+1;
1756       nblockMAX = 100000 * s->blockSize100k;
1757       groupNo  = -1;
1758       groupPos = 0;
1759 
1760       for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
1761 
1762       /*-- MTF init --*/
1763       {
1764          Int32 ii, jj, kk;
1765          kk = MTFA_SIZE-1;
1766          for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
1767             for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
1768                s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
1769                kk--;
1770             }
1771             s->mtfbase[ii] = kk + 1;
1772          }
1773       }
1774       /*-- end MTF init --*/
1775 
1776       nblock = 0;
1777       GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
1778 
1779       while (True) {
1780 
1781          if (nextSym == EOB) break;
1782 
1783          if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
1784 
1785             es = -1;
1786             N = 1;
1787             do {
1788                if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
1789                if (nextSym == BZ_RUNB) es = es + (1+1) * N;
1790                N = N * 2;
1791                GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
1792             }
1793                while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
1794 
1795             es++;
1796             uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
1797             s->unzftab[uc] += es;
1798 
1799             if (s->smallDecompress)
1800                while (es > 0) {
1801                   if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
1802                   s->ll16[nblock] = (UInt16)uc;
1803                   nblock++;
1804                   es--;
1805                }
1806             else
1807                while (es > 0) {
1808                   if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
1809                   s->tt[nblock] = (UInt32)uc;
1810                   nblock++;
1811                   es--;
1812                };
1813 
1814             continue;
1815 
1816          } else {
1817 
1818             if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
1819 
1820             /*-- uc = MTF ( nextSym-1 ) --*/
1821             {
1822                Int32 ii, jj, kk, pp, lno, off;
1823                UInt32 nn;
1824                nn = (UInt32)(nextSym - 1);
1825 
1826                if (nn < MTFL_SIZE) {
1827                   /* avoid general-case expense */
1828                   pp = s->mtfbase[0];
1829                   uc = s->mtfa[pp+nn];
1830                   while (nn > 3) {
1831                      Int32 z = pp+nn;
1832                      s->mtfa[(z)  ] = s->mtfa[(z)-1];
1833                      s->mtfa[(z)-1] = s->mtfa[(z)-2];
1834                      s->mtfa[(z)-2] = s->mtfa[(z)-3];
1835                      s->mtfa[(z)-3] = s->mtfa[(z)-4];
1836                      nn -= 4;
1837                   }
1838                   while (nn > 0) {
1839                      s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
1840                   };
1841                   s->mtfa[pp] = uc;
1842                } else {
1843                   /* general case */
1844                   lno = nn / MTFL_SIZE;
1845                   off = nn % MTFL_SIZE;
1846                   pp = s->mtfbase[lno] + off;
1847                   uc = s->mtfa[pp];
1848                   while (pp > s->mtfbase[lno]) {
1849                      s->mtfa[pp] = s->mtfa[pp-1]; pp--;
1850                   };
1851                   s->mtfbase[lno]++;
1852                   while (lno > 0) {
1853                      s->mtfbase[lno]--;
1854                      s->mtfa[s->mtfbase[lno]]
1855                         = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
1856                      lno--;
1857                   }
1858                   s->mtfbase[0]--;
1859                   s->mtfa[s->mtfbase[0]] = uc;
1860                   if (s->mtfbase[0] == 0) {
1861                      kk = MTFA_SIZE-1;
1862                      for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
1863                         for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
1864                            s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
1865                            kk--;
1866                         }
1867                         s->mtfbase[ii] = kk + 1;
1868                      }
1869                   }
1870                }
1871             }
1872             /*-- end uc = MTF ( nextSym-1 ) --*/
1873 
1874             s->unzftab[s->seqToUnseq[uc]]++;
1875             if (s->smallDecompress)
1876                s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
1877                s->tt[nblock]   = (UInt32)(s->seqToUnseq[uc]);
1878             nblock++;
1879 
1880             GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
1881             continue;
1882          }
1883       }
1884 
1885       /* Now we know what nblock is, we can do a better sanity
1886          check on s->origPtr.
1887       */
1888       if (s->origPtr < 0 || s->origPtr >= nblock)
1889          RETURN(BZ_DATA_ERROR);
1890 
1891       /*-- Set up cftab to facilitate generation of T^(-1) --*/
1892       s->cftab[0] = 0;
1893       for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
1894       for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
1895       for (i = 0; i <= 256; i++) {
1896          if (s->cftab[i] < 0 || s->cftab[i] > nblock) {
1897             /* s->cftab[i] can legitimately be == nblock */
1898             RETURN(BZ_DATA_ERROR);
1899          }
1900       }
1901 
1902       s->state_out_len = 0;
1903       s->state_out_ch  = 0;
1904       BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
1905       s->state = BZ_X_OUTPUT;
1906       if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
1907 
1908       if (s->smallDecompress) {
1909 
1910          /*-- Make a copy of cftab, used in generation of T --*/
1911          for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
1912 
1913          /*-- compute the T vector --*/
1914          for (i = 0; i < nblock; i++) {
1915             uc = (UChar)(s->ll16[i]);
1916             SET_LL(i, s->cftabCopy[uc]);
1917             s->cftabCopy[uc]++;
1918          }
1919 
1920          /*-- Compute T^(-1) by pointer reversal on T --*/
1921          i = s->origPtr;
1922          j = GET_LL(i);
1923          do {
1924             Int32 tmp = GET_LL(j);
1925             SET_LL(j, i);
1926             i = j;
1927             j = tmp;
1928          }
1929             while (i != s->origPtr);
1930 
1931          s->tPos = s->origPtr;
1932          s->nblock_used = 0;
1933          if (s->blockRandomised) {
1934             BZ_RAND_INIT_MASK;
1935             BZ_GET_SMALL(s->k0); s->nblock_used++;
1936             BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
1937          } else {
1938             BZ_GET_SMALL(s->k0); s->nblock_used++;
1939          }
1940 
1941       } else {
1942 
1943          /*-- compute the T^(-1) vector --*/
1944          for (i = 0; i < nblock; i++) {
1945             uc = (UChar)(s->tt[i] & 0xff);
1946             s->tt[s->cftab[uc]] |= (i << 8);
1947             s->cftab[uc]++;
1948          }
1949 
1950          s->tPos = s->tt[s->origPtr] >> 8;
1951          s->nblock_used = 0;
1952          if (s->blockRandomised) {
1953             BZ_RAND_INIT_MASK;
1954             BZ_GET_FAST(s->k0); s->nblock_used++;
1955             BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
1956          } else {
1957             BZ_GET_FAST(s->k0); s->nblock_used++;
1958          }
1959 
1960       }
1961 
1962       RETURN(BZ_OK);
1963 
1964 
1965 
1966     endhdr_2:
1967 
1968       GET_UCHAR(BZ_X_ENDHDR_2, uc);
1969       if (uc != 0x72) RETURN(BZ_DATA_ERROR);
1970       GET_UCHAR(BZ_X_ENDHDR_3, uc);
1971       if (uc != 0x45) RETURN(BZ_DATA_ERROR);
1972       GET_UCHAR(BZ_X_ENDHDR_4, uc);
1973       if (uc != 0x38) RETURN(BZ_DATA_ERROR);
1974       GET_UCHAR(BZ_X_ENDHDR_5, uc);
1975       if (uc != 0x50) RETURN(BZ_DATA_ERROR);
1976       GET_UCHAR(BZ_X_ENDHDR_6, uc);
1977       if (uc != 0x90) RETURN(BZ_DATA_ERROR);
1978 
1979       s->storedCombinedCRC = 0;
1980       GET_UCHAR(BZ_X_CCRC_1, uc);
1981       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1982       GET_UCHAR(BZ_X_CCRC_2, uc);
1983       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1984       GET_UCHAR(BZ_X_CCRC_3, uc);
1985       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1986       GET_UCHAR(BZ_X_CCRC_4, uc);
1987       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1988 
1989       s->state = BZ_X_IDLE;
1990       RETURN(BZ_STREAM_END);
1991 
1992       default: AssertH ( False, 4001 );
1993    }
1994 
1995    AssertH ( False, 4002 );
1996 
1997    save_state_and_return:
1998 
1999    s->save_i           = i;
2000    s->save_j           = j;
2001    s->save_t           = t;
2002    s->save_alphaSize   = alphaSize;
2003    s->save_nGroups     = nGroups;
2004    s->save_nSelectors  = nSelectors;
2005    s->save_EOB         = EOB;
2006    s->save_groupNo     = groupNo;
2007    s->save_groupPos    = groupPos;
2008    s->save_nextSym     = nextSym;
2009    s->save_nblockMAX   = nblockMAX;
2010    s->save_nblock      = nblock;
2011    s->save_es          = es;
2012    s->save_N           = N;
2013    s->save_curr        = curr;
2014    s->save_zt          = zt;
2015    s->save_zn          = zn;
2016    s->save_zvec        = zvec;
2017    s->save_zj          = zj;
2018    s->save_gSel        = gSel;
2019    s->save_gMinlen     = gMinlen;
2020    s->save_gLimit      = gLimit;
2021    s->save_gBase       = gBase;
2022    s->save_gPerm       = gPerm;
2023 
2024    return retVal;
2025 }
2026 
2027 
2028 /*-------------------------------------------------------------*/
2029 /*--- end                                      decompress.c ---*/
2030 /*-------------------------------------------------------------*/
2031 
2032 /*-------------------------------------------------------------*/
2033 /*--- Block sorting machinery                               ---*/
2034 /*---                                           blocksort.c ---*/
2035 /*-------------------------------------------------------------*/
2036 
2037 /*--
2038   This file is a part of bzip2 and/or libbzip2, a program and
2039   library for lossless, block-sorting data compression.
2040 
2041   Copyright (C) 1996-2004 Julian R Seward.  All rights reserved.
2042 
2043   Redistribution and use in source and binary forms, with or without
2044   modification, are permitted provided that the following conditions
2045   are met:
2046 
2047   1. Redistributions of source code must retain the above copyright
2048      notice, this list of conditions and the following disclaimer.
2049 
2050   2. The origin of this software must not be misrepresented; you must
2051      not claim that you wrote the original software.  If you use this
2052      software in a product, an acknowledgment in the product
2053      documentation would be appreciated but is not required.
2054 
2055   3. Altered source versions must be plainly marked as such, and must
2056      not be misrepresented as being the original software.
2057 
2058   4. The name of the author may not be used to endorse or promote
2059      products derived from this software without specific prior written
2060      permission.
2061 
2062   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
2063   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
2064   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
2065   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
2066   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
2067   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
2068   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
2069   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
2070   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
2071   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
2072   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2073 
2074   Julian Seward, Cambridge, UK.
2075   jseward@bzip.org
2076   bzip2/libbzip2 version 1.0 of 21 March 2000
2077 
2078   This program is based on (at least) the work of:
2079      Mike Burrows
2080      David Wheeler
2081      Peter Fenwick
2082      Alistair Moffat
2083      Radford Neal
2084      Ian H. Witten
2085      Robert Sedgewick
2086      Jon L. Bentley
2087 
2088   For more information on these sources, see the manual.
2089 
2090   To get some idea how the block sorting algorithms in this file
2091   work, read my paper
2092      On the Performance of BWT Sorting Algorithms
2093   in Proceedings of the IEEE Data Compression Conference 2000,
2094   Snowbird, Utah, USA, 27-30 March 2000.  The main sort in this
2095   file implements the algorithm called  cache  in the paper.
2096 --*/
2097 
2098 
2099 
2100 /*---------------------------------------------*/
2101 /*--- Fallback O(N log(N)^2) sorting        ---*/
2102 /*--- algorithm, for repetitive blocks      ---*/
2103 /*---------------------------------------------*/
2104 
2105 /*---------------------------------------------*/
2106 static
fallbackSimpleSort(UInt32 * fmap,UInt32 * eclass,Int32 lo,Int32 hi)2107 void fallbackSimpleSort ( UInt32* fmap,
2108                           UInt32* eclass,
2109                           Int32   lo,
2110                           Int32   hi )
2111 {
2112    Int32 i, j, tmp;
2113    UInt32 ec_tmp;
2114 
2115    if (lo == hi) return;
2116 
2117    if (hi - lo > 3) {
2118       for ( i = hi-4; i >= lo; i-- ) {
2119          tmp = fmap[i];
2120          ec_tmp = eclass[tmp];
2121          for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )
2122             fmap[j-4] = fmap[j];
2123          fmap[j-4] = tmp;
2124       }
2125    }
2126 
2127    for ( i = hi-1; i >= lo; i-- ) {
2128       tmp = fmap[i];
2129       ec_tmp = eclass[tmp];
2130       for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )
2131          fmap[j-1] = fmap[j];
2132       fmap[j-1] = tmp;
2133    }
2134 }
2135 
2136 
2137 /*---------------------------------------------*/
2138 #define fswap(zz1, zz2) \
2139    { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
2140 
2141 #define fvswap(zzp1, zzp2, zzn)       \
2142 {                                     \
2143    Int32 yyp1 = (zzp1);               \
2144    Int32 yyp2 = (zzp2);               \
2145    Int32 yyn  = (zzn);                \
2146    while (yyn > 0) {                  \
2147       fswap(fmap[yyp1], fmap[yyp2]);  \
2148       yyp1++; yyp2++; yyn--;          \
2149    }                                  \
2150 }
2151 
2152 
2153 #define fmin(a,b) ((a) < (b)) ? (a) : (b)
2154 
2155 #define fpush(lz,hz) { stackLo[sp] = lz; \
2156                        stackHi[sp] = hz; \
2157                        sp++; }
2158 
2159 #define fpop(lz,hz) { sp--;              \
2160                       lz = stackLo[sp];  \
2161                       hz = stackHi[sp]; }
2162 
2163 #define FALLBACK_QSORT_SMALL_THRESH 10
2164 #define FALLBACK_QSORT_STACK_SIZE   100
2165 
2166 
2167 static
fallbackQSort3(UInt32 * fmap,UInt32 * eclass,Int32 loSt,Int32 hiSt)2168 void fallbackQSort3 ( UInt32* fmap,
2169                       UInt32* eclass,
2170                       Int32   loSt,
2171                       Int32   hiSt )
2172 {
2173    Int32 unLo, unHi, ltLo, gtHi, n, m;
2174    Int32 sp, lo, hi;
2175    UInt32 med, r, r3;
2176    Int32 stackLo[FALLBACK_QSORT_STACK_SIZE];
2177    Int32 stackHi[FALLBACK_QSORT_STACK_SIZE];
2178 
2179    r = 0;
2180 
2181    sp = 0;
2182    fpush ( loSt, hiSt );
2183 
2184    while (sp > 0) {
2185 
2186       AssertH ( sp < FALLBACK_QSORT_STACK_SIZE, 1004 );
2187 
2188       fpop ( lo, hi );
2189       if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
2190          fallbackSimpleSort ( fmap, eclass, lo, hi );
2191          continue;
2192       }
2193 
2194       /* Random partitioning.  Median of 3 sometimes fails to
2195          avoid bad cases.  Median of 9 seems to help but
2196          looks rather expensive.  This too seems to work but
2197          is cheaper.  Guidance for the magic constants
2198          7621 and 32768 is taken from Sedgewick's algorithms
2199          book, chapter 35.
2200       */
2201       r = ((r * 7621) + 1) % 32768;
2202       r3 = r % 3;
2203       if (r3 == 0) med = eclass[fmap[lo]]; else
2204       if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else
2205                    med = eclass[fmap[hi]];
2206 
2207       unLo = ltLo = lo;
2208       unHi = gtHi = hi;
2209 
2210       while (1) {
2211          while (1) {
2212             if (unLo > unHi) break;
2213             n = (Int32)eclass[fmap[unLo]] - (Int32)med;
2214             if (n == 0) {
2215                fswap(fmap[unLo], fmap[ltLo]);
2216                ltLo++; unLo++;
2217                continue;
2218             };
2219             if (n > 0) break;
2220             unLo++;
2221          }
2222          while (1) {
2223             if (unLo > unHi) break;
2224             n = (Int32)eclass[fmap[unHi]] - (Int32)med;
2225             if (n == 0) {
2226                fswap(fmap[unHi], fmap[gtHi]);
2227                gtHi--; unHi--;
2228                continue;
2229             };
2230             if (n < 0) break;
2231             unHi--;
2232          }
2233          if (unLo > unHi) break;
2234          fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
2235       }
2236 
2237       AssertD ( unHi == unLo-1, "fallbackQSort3(2)" );
2238 
2239       if (gtHi < ltLo) continue;
2240 
2241       n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);
2242       m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);
2243 
2244       n = lo + unLo - ltLo - 1;
2245       m = hi - (gtHi - unHi) + 1;
2246 
2247       if (n - lo > hi - m) {
2248          fpush ( lo, n );
2249          fpush ( m, hi );
2250       } else {
2251          fpush ( m, hi );
2252          fpush ( lo, n );
2253       }
2254    }
2255 }
2256 
2257 #undef fmin
2258 #undef fpush
2259 #undef fpop
2260 #undef fswap
2261 #undef fvswap
2262 #undef FALLBACK_QSORT_SMALL_THRESH
2263 #undef FALLBACK_QSORT_STACK_SIZE
2264 
2265 
2266 /*---------------------------------------------*/
2267 /* Pre:
2268       nblock > 0
2269       eclass exists for [0 .. nblock-1]
2270       ((UChar*)eclass) [0 .. nblock-1] holds block
2271       ptr exists for [0 .. nblock-1]
2272 
2273    Post:
2274       ((UChar*)eclass) [0 .. nblock-1] holds block
2275       All other areas of eclass destroyed
2276       fmap [0 .. nblock-1] holds sorted order
2277       bhtab [ 0 .. 2+(nblock/32) ] destroyed
2278 */
2279 
2280 #define       SET_BH(zz)  bhtab[(zz) >> 5] |= (1 << ((zz) & 31))
2281 #define     CLEAR_BH(zz)  bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
2282 #define     ISSET_BH(zz)  (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
2283 #define      WORD_BH(zz)  bhtab[(zz) >> 5]
2284 #define UNALIGNED_BH(zz)  ((zz) & 0x01f)
2285 
2286 static
fallbackSort(UInt32 * fmap,UInt32 * eclass,UInt32 * bhtab,Int32 nblock,Int32 verb)2287 void fallbackSort ( UInt32* fmap,
2288                     UInt32* eclass,
2289                     UInt32* bhtab,
2290                     Int32   nblock,
2291                     Int32   verb )
2292 {
2293    Int32 ftab[257];
2294    Int32 ftabCopy[256];
2295    Int32 H, i, j, k, l, r, cc, cc1;
2296    Int32 nNotDone;
2297    Int32 nBhtab;
2298    UChar* eclass8 = (UChar*)eclass;
2299 
2300    /*--
2301       Initial 1-char radix sort to generate
2302       initial fmap and initial BH bits.
2303    --*/
2304    if (verb >= 4)
2305       VPrintf0 ( "        bucket sorting ...\n" );
2306    for (i = 0; i < 257;    i++) ftab[i] = 0;
2307    for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
2308    for (i = 0; i < 256;    i++) ftabCopy[i] = ftab[i];
2309    for (i = 1; i < 257;    i++) ftab[i] += ftab[i-1];
2310 
2311    for (i = 0; i < nblock; i++) {
2312       j = eclass8[i];
2313       k = ftab[j] - 1;
2314       ftab[j] = k;
2315       fmap[k] = i;
2316    }
2317 
2318    nBhtab = 2 + (nblock / 32);
2319    for (i = 0; i < nBhtab; i++) bhtab[i] = 0;
2320    for (i = 0; i < 256; i++) SET_BH(ftab[i]);
2321 
2322    /*--
2323       Inductively refine the buckets.  Kind-of an
2324       "exponential radix sort" (!), inspired by the
2325       Manber-Myers suffix array construction algorithm.
2326    --*/
2327 
2328    /*-- set sentinel bits for block-end detection --*/
2329    for (i = 0; i < 32; i++) {
2330       SET_BH(nblock + 2*i);
2331       CLEAR_BH(nblock + 2*i + 1);
2332    }
2333 
2334    /*-- the log(N) loop --*/
2335    H = 1;
2336    while (1) {
2337 
2338       if (verb >= 4)
2339          VPrintf1 ( "        depth %6d has ", H );
2340 
2341       j = 0;
2342       for (i = 0; i < nblock; i++) {
2343          if (ISSET_BH(i)) j = i;
2344          k = fmap[i] - H; if (k < 0) k += nblock;
2345          eclass[k] = j;
2346       }
2347 
2348       nNotDone = 0;
2349       r = -1;
2350       while (1) {
2351 
2352 	 /*-- find the next non-singleton bucket --*/
2353          k = r + 1;
2354          while (ISSET_BH(k) && UNALIGNED_BH(k)) k++;
2355          if (ISSET_BH(k)) {
2356             while (WORD_BH(k) == 0xffffffff) k += 32;
2357             while (ISSET_BH(k)) k++;
2358          }
2359          l = k - 1;
2360          if (l >= nblock) break;
2361          while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++;
2362          if (!ISSET_BH(k)) {
2363             while (WORD_BH(k) == 0x00000000) k += 32;
2364             while (!ISSET_BH(k)) k++;
2365          }
2366          r = k - 1;
2367          if (r >= nblock) break;
2368 
2369          /*-- now [l, r] bracket current bucket --*/
2370          if (r > l) {
2371             nNotDone += (r - l + 1);
2372             fallbackQSort3 ( fmap, eclass, l, r );
2373 
2374             /*-- scan bucket and generate header bits-- */
2375             cc = -1;
2376             for (i = l; i <= r; i++) {
2377                cc1 = eclass[fmap[i]];
2378                if (cc != cc1) { SET_BH(i); cc = cc1; };
2379             }
2380          }
2381       }
2382 
2383       if (verb >= 4)
2384          VPrintf1 ( "%6d unresolved strings\n", nNotDone );
2385 
2386       H *= 2;
2387       if (H > nblock || nNotDone == 0) break;
2388    }
2389 
2390    /*--
2391       Reconstruct the original block in
2392       eclass8 [0 .. nblock-1], since the
2393       previous phase destroyed it.
2394    --*/
2395    if (verb >= 4)
2396       VPrintf0 ( "        reconstructing block ...\n" );
2397    j = 0;
2398    for (i = 0; i < nblock; i++) {
2399       while (ftabCopy[j] == 0) j++;
2400       ftabCopy[j]--;
2401       eclass8[fmap[i]] = (UChar)j;
2402    }
2403    AssertH ( j < 256, 1005 );
2404 }
2405 
2406 #undef       SET_BH
2407 #undef     CLEAR_BH
2408 #undef     ISSET_BH
2409 #undef      WORD_BH
2410 #undef UNALIGNED_BH
2411 
2412 
2413 /*---------------------------------------------*/
2414 /*--- The main, O(N^2 log(N)) sorting       ---*/
2415 /*--- algorithm.  Faster for "normal"       ---*/
2416 /*--- non-repetitive blocks.                ---*/
2417 /*---------------------------------------------*/
2418 
2419 /*---------------------------------------------*/
2420 static
mainGtU(UInt32 i1,UInt32 i2,UChar * block,UInt16 * quadrant,UInt32 nblock,Int32 * budget)2421 Bool mainGtU ( UInt32  i1,
2422                UInt32  i2,
2423                UChar*  block,
2424                UInt16* quadrant,
2425                UInt32  nblock,
2426                Int32*  budget )
2427 {
2428    Int32  k;
2429    UChar  c1, c2;
2430    UInt16 s1, s2;
2431 
2432    AssertD ( i1 != i2, "mainGtU" );
2433    /* 1 */
2434    c1 = block[i1]; c2 = block[i2];
2435    if (c1 != c2) return (c1 > c2);
2436    i1++; i2++;
2437    /* 2 */
2438    c1 = block[i1]; c2 = block[i2];
2439    if (c1 != c2) return (c1 > c2);
2440    i1++; i2++;
2441    /* 3 */
2442    c1 = block[i1]; c2 = block[i2];
2443    if (c1 != c2) return (c1 > c2);
2444    i1++; i2++;
2445    /* 4 */
2446    c1 = block[i1]; c2 = block[i2];
2447    if (c1 != c2) return (c1 > c2);
2448    i1++; i2++;
2449    /* 5 */
2450    c1 = block[i1]; c2 = block[i2];
2451    if (c1 != c2) return (c1 > c2);
2452    i1++; i2++;
2453    /* 6 */
2454    c1 = block[i1]; c2 = block[i2];
2455    if (c1 != c2) return (c1 > c2);
2456    i1++; i2++;
2457    /* 7 */
2458    c1 = block[i1]; c2 = block[i2];
2459    if (c1 != c2) return (c1 > c2);
2460    i1++; i2++;
2461    /* 8 */
2462    c1 = block[i1]; c2 = block[i2];
2463    if (c1 != c2) return (c1 > c2);
2464    i1++; i2++;
2465    /* 9 */
2466    c1 = block[i1]; c2 = block[i2];
2467    if (c1 != c2) return (c1 > c2);
2468    i1++; i2++;
2469    /* 10 */
2470    c1 = block[i1]; c2 = block[i2];
2471    if (c1 != c2) return (c1 > c2);
2472    i1++; i2++;
2473    /* 11 */
2474    c1 = block[i1]; c2 = block[i2];
2475    if (c1 != c2) return (c1 > c2);
2476    i1++; i2++;
2477    /* 12 */
2478    c1 = block[i1]; c2 = block[i2];
2479    if (c1 != c2) return (c1 > c2);
2480    i1++; i2++;
2481 
2482    k = nblock + 8;
2483 
2484    do {
2485       /* 1 */
2486       c1 = block[i1]; c2 = block[i2];
2487       if (c1 != c2) return (c1 > c2);
2488       s1 = quadrant[i1]; s2 = quadrant[i2];
2489       if (s1 != s2) return (s1 > s2);
2490       i1++; i2++;
2491       /* 2 */
2492       c1 = block[i1]; c2 = block[i2];
2493       if (c1 != c2) return (c1 > c2);
2494       s1 = quadrant[i1]; s2 = quadrant[i2];
2495       if (s1 != s2) return (s1 > s2);
2496       i1++; i2++;
2497       /* 3 */
2498       c1 = block[i1]; c2 = block[i2];
2499       if (c1 != c2) return (c1 > c2);
2500       s1 = quadrant[i1]; s2 = quadrant[i2];
2501       if (s1 != s2) return (s1 > s2);
2502       i1++; i2++;
2503       /* 4 */
2504       c1 = block[i1]; c2 = block[i2];
2505       if (c1 != c2) return (c1 > c2);
2506       s1 = quadrant[i1]; s2 = quadrant[i2];
2507       if (s1 != s2) return (s1 > s2);
2508       i1++; i2++;
2509       /* 5 */
2510       c1 = block[i1]; c2 = block[i2];
2511       if (c1 != c2) return (c1 > c2);
2512       s1 = quadrant[i1]; s2 = quadrant[i2];
2513       if (s1 != s2) return (s1 > s2);
2514       i1++; i2++;
2515       /* 6 */
2516       c1 = block[i1]; c2 = block[i2];
2517       if (c1 != c2) return (c1 > c2);
2518       s1 = quadrant[i1]; s2 = quadrant[i2];
2519       if (s1 != s2) return (s1 > s2);
2520       i1++; i2++;
2521       /* 7 */
2522       c1 = block[i1]; c2 = block[i2];
2523       if (c1 != c2) return (c1 > c2);
2524       s1 = quadrant[i1]; s2 = quadrant[i2];
2525       if (s1 != s2) return (s1 > s2);
2526       i1++; i2++;
2527       /* 8 */
2528       c1 = block[i1]; c2 = block[i2];
2529       if (c1 != c2) return (c1 > c2);
2530       s1 = quadrant[i1]; s2 = quadrant[i2];
2531       if (s1 != s2) return (s1 > s2);
2532       i1++; i2++;
2533 
2534       if (i1 >= nblock) i1 -= nblock;
2535       if (i2 >= nblock) i2 -= nblock;
2536 
2537       k -= 8;
2538       (*budget)--;
2539    }
2540       while (k >= 0);
2541 
2542    return False;
2543 }
2544 
2545 
2546 /*---------------------------------------------*/
2547 /*--
2548    Knuth's increments seem to work better
2549    than Incerpi-Sedgewick here.  Possibly
2550    because the number of elems to sort is
2551    usually small, typically <= 20.
2552 --*/
2553 static
2554 Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
2555                    9841, 29524, 88573, 265720,
2556                    797161, 2391484 };
2557 
2558 static
mainSimpleSort(UInt32 * ptr,UChar * block,UInt16 * quadrant,Int32 nblock,Int32 lo,Int32 hi,Int32 d,Int32 * budget)2559 void mainSimpleSort ( UInt32* ptr,
2560                       UChar*  block,
2561                       UInt16* quadrant,
2562                       Int32   nblock,
2563                       Int32   lo,
2564                       Int32   hi,
2565                       Int32   d,
2566                       Int32*  budget )
2567 {
2568    Int32 i, j, h, bigN, hp;
2569    UInt32 v;
2570 
2571    bigN = hi - lo + 1;
2572    if (bigN < 2) return;
2573 
2574    hp = 0;
2575    while (incs[hp] < bigN) hp++;
2576    hp--;
2577 
2578    for (; hp >= 0; hp--) {
2579       h = incs[hp];
2580 
2581       i = lo + h;
2582       while (True) {
2583 
2584          /*-- copy 1 --*/
2585          if (i > hi) break;
2586          v = ptr[i];
2587          j = i;
2588          while ( mainGtU (
2589                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget
2590                  ) ) {
2591             ptr[j] = ptr[j-h];
2592             j = j - h;
2593             if (j <= (lo + h - 1)) break;
2594          }
2595          ptr[j] = v;
2596          i++;
2597 
2598          /*-- copy 2 --*/
2599          if (i > hi) break;
2600          v = ptr[i];
2601          j = i;
2602          while ( mainGtU (
2603                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget
2604                  ) ) {
2605             ptr[j] = ptr[j-h];
2606             j = j - h;
2607             if (j <= (lo + h - 1)) break;
2608          }
2609          ptr[j] = v;
2610          i++;
2611 
2612          /*-- copy 3 --*/
2613          if (i > hi) break;
2614          v = ptr[i];
2615          j = i;
2616          while ( mainGtU (
2617                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget
2618                  ) ) {
2619             ptr[j] = ptr[j-h];
2620             j = j - h;
2621             if (j <= (lo + h - 1)) break;
2622          }
2623          ptr[j] = v;
2624          i++;
2625 
2626          if (*budget < 0) return;
2627       }
2628    }
2629 }
2630 
2631 
2632 /*---------------------------------------------*/
2633 /*--
2634    The following is an implementation of
2635    an elegant 3-way quicksort for strings,
2636    described in a paper "Fast Algorithms for
2637    Sorting and Searching Strings", by Robert
2638    Sedgewick and Jon L. Bentley.
2639 --*/
2640 
2641 #define mswap(zz1, zz2) \
2642    { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
2643 
2644 #define mvswap(zzp1, zzp2, zzn)       \
2645 {                                     \
2646    Int32 yyp1 = (zzp1);               \
2647    Int32 yyp2 = (zzp2);               \
2648    Int32 yyn  = (zzn);                \
2649    while (yyn > 0) {                  \
2650       mswap(ptr[yyp1], ptr[yyp2]);    \
2651       yyp1++; yyp2++; yyn--;          \
2652    }                                  \
2653 }
2654 
2655 static
mmed3(UChar a,UChar b,UChar c)2656 UChar mmed3 ( UChar a, UChar b, UChar c )
2657 {
2658    UChar t;
2659    if (a > b) { t = a; a = b; b = t; };
2660    if (b > c) {
2661       b = c;
2662       if (a > b) b = a;
2663    }
2664    return b;
2665 }
2666 
2667 #define mmin(a,b) ((a) < (b)) ? (a) : (b)
2668 
2669 #define mpush(lz,hz,dz) { stackLo[sp] = lz; \
2670                           stackHi[sp] = hz; \
2671                           stackD [sp] = dz; \
2672                           sp++; }
2673 
2674 #define mpop(lz,hz,dz) { sp--;             \
2675                          lz = stackLo[sp]; \
2676                          hz = stackHi[sp]; \
2677                          dz = stackD [sp]; }
2678 
2679 
2680 #define mnextsize(az) (nextHi[az]-nextLo[az])
2681 
2682 #define mnextswap(az,bz)                                        \
2683    { Int32 tz;                                                  \
2684      tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
2685      tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
2686      tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }
2687 
2688 
2689 #define MAIN_QSORT_SMALL_THRESH 20
2690 #define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)
2691 #define MAIN_QSORT_STACK_SIZE 100
2692 
2693 static
mainQSort3(UInt32 * ptr,UChar * block,UInt16 * quadrant,Int32 nblock,Int32 loSt,Int32 hiSt,Int32 dSt,Int32 * budget)2694 void mainQSort3 ( UInt32* ptr,
2695                   UChar*  block,
2696                   UInt16* quadrant,
2697                   Int32   nblock,
2698                   Int32   loSt,
2699                   Int32   hiSt,
2700                   Int32   dSt,
2701                   Int32*  budget )
2702 {
2703    Int32 unLo, unHi, ltLo, gtHi, n, m, med;
2704    Int32 sp, lo, hi, d;
2705 
2706    Int32 stackLo[MAIN_QSORT_STACK_SIZE];
2707    Int32 stackHi[MAIN_QSORT_STACK_SIZE];
2708    Int32 stackD [MAIN_QSORT_STACK_SIZE];
2709 
2710    Int32 nextLo[3];
2711    Int32 nextHi[3];
2712    Int32 nextD [3];
2713 
2714    sp = 0;
2715    mpush ( loSt, hiSt, dSt );
2716 
2717    while (sp > 0) {
2718 
2719       AssertH ( sp < MAIN_QSORT_STACK_SIZE, 1001 );
2720 
2721       mpop ( lo, hi, d );
2722       if (hi - lo < MAIN_QSORT_SMALL_THRESH ||
2723           d > MAIN_QSORT_DEPTH_THRESH) {
2724          mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget );
2725          if (*budget < 0) return;
2726          continue;
2727       }
2728 
2729       med = (Int32)
2730             mmed3 ( block[ptr[ lo         ]+d],
2731                     block[ptr[ hi         ]+d],
2732                     block[ptr[ (lo+hi)>>1 ]+d] );
2733 
2734       unLo = ltLo = lo;
2735       unHi = gtHi = hi;
2736 
2737       while (True) {
2738          while (True) {
2739             if (unLo > unHi) break;
2740             n = ((Int32)block[ptr[unLo]+d]) - med;
2741             if (n == 0) {
2742                mswap(ptr[unLo], ptr[ltLo]);
2743                ltLo++; unLo++; continue;
2744             };
2745             if (n >  0) break;
2746             unLo++;
2747          }
2748          while (True) {
2749             if (unLo > unHi) break;
2750             n = ((Int32)block[ptr[unHi]+d]) - med;
2751             if (n == 0) {
2752                mswap(ptr[unHi], ptr[gtHi]);
2753                gtHi--; unHi--; continue;
2754             };
2755             if (n <  0) break;
2756             unHi--;
2757          }
2758          if (unLo > unHi) break;
2759          mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--;
2760       }
2761 
2762       AssertD ( unHi == unLo-1, "mainQSort3(2)" );
2763 
2764       if (gtHi < ltLo) {
2765          mpush(lo, hi, d+1 );
2766          continue;
2767       }
2768 
2769       n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);
2770       m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);
2771 
2772       n = lo + unLo - ltLo - 1;
2773       m = hi - (gtHi - unHi) + 1;
2774 
2775       nextLo[0] = lo;  nextHi[0] = n;   nextD[0] = d;
2776       nextLo[1] = m;   nextHi[1] = hi;  nextD[1] = d;
2777       nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
2778 
2779       if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
2780       if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);
2781       if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
2782 
2783       AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" );
2784       AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" );
2785 
2786       mpush (nextLo[0], nextHi[0], nextD[0]);
2787       mpush (nextLo[1], nextHi[1], nextD[1]);
2788       mpush (nextLo[2], nextHi[2], nextD[2]);
2789    }
2790 }
2791 
2792 #undef mswap
2793 #undef mvswap
2794 #undef mpush
2795 #undef mpop
2796 #undef mmin
2797 #undef mnextsize
2798 #undef mnextswap
2799 #undef MAIN_QSORT_SMALL_THRESH
2800 #undef MAIN_QSORT_DEPTH_THRESH
2801 #undef MAIN_QSORT_STACK_SIZE
2802 
2803 
2804 /*---------------------------------------------*/
2805 /* Pre:
2806       nblock > N_OVERSHOOT
2807       block32 exists for [0 .. nblock-1 +N_OVERSHOOT]
2808       ((UChar*)block32) [0 .. nblock-1] holds block
2809       ptr exists for [0 .. nblock-1]
2810 
2811    Post:
2812       ((UChar*)block32) [0 .. nblock-1] holds block
2813       All other areas of block32 destroyed
2814       ftab [0 .. 65536 ] destroyed
2815       ptr [0 .. nblock-1] holds sorted order
2816       if (*budget < 0), sorting was abandoned
2817 */
2818 
2819 #define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])
2820 #define SETMASK (1 << 21)
2821 #define CLEARMASK (~(SETMASK))
2822 
2823 /*static*/ __attribute__((noinline))
mainSort(UInt32 * ptr,UChar * block,UInt16 * quadrant,UInt32 * ftab,Int32 nblock,Int32 verb,Int32 * budget)2824 void mainSort ( UInt32* ptr,
2825                 UChar*  block,
2826                 UInt16* quadrant,
2827                 UInt32* ftab,
2828                 Int32   nblock,
2829                 Int32   verb,
2830                 Int32*  budget )
2831 {
2832    Int32  i, j, k, ss, sb;
2833    Int32  runningOrder[256];
2834    Bool   bigDone[256];
2835    Int32  copyStart[256];
2836    Int32  copyEnd  [256];
2837    UChar  c1;
2838    Int32  numQSorted;
2839    UInt16 s;
2840    if (verb >= 4) VPrintf0 ( "        main sort initialise ...\n" );
2841 
2842    /*-- set up the 2-byte frequency table --*/
2843    for (i = 65536; i >= 0; i--) ftab[i] = 0;
2844 
2845    j = block[0] << 8;
2846    i = nblock-1;
2847    for (; i >= 3; i -= 4) {
2848       quadrant[i] = 0;
2849       j = (j >> 8) | ( ((UInt16)block[i]) << 8);
2850       ftab[j]++;
2851       quadrant[i-1] = 0;
2852       j = (j >> 8) | ( ((UInt16)block[i-1]) << 8);
2853       ftab[j]++;
2854       quadrant[i-2] = 0;
2855       j = (j >> 8) | ( ((UInt16)block[i-2]) << 8);
2856       ftab[j]++;
2857       quadrant[i-3] = 0;
2858       j = (j >> 8) | ( ((UInt16)block[i-3]) << 8);
2859       ftab[j]++;
2860    }
2861    for (; i >= 0; i--) {
2862       quadrant[i] = 0;
2863       j = (j >> 8) | ( ((UInt16)block[i]) << 8);
2864       ftab[j]++;
2865    }
2866 
2867    /*-- (emphasises close relationship of block & quadrant) --*/
2868    for (i = 0; i < BZ_N_OVERSHOOT; i++) {
2869       block   [nblock+i] = block[i];
2870       quadrant[nblock+i] = 0;
2871    }
2872 
2873    if (verb >= 4) VPrintf0 ( "        bucket sorting ...\n" );
2874 
2875    /*-- Complete the initial radix sort --*/
2876    for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];
2877 
2878    s = block[0] << 8;
2879    i = nblock-1;
2880    for (; i >= 3; i -= 4) {
2881       s = (s >> 8) | (block[i] << 8);
2882       j = ftab[s] -1;
2883       ftab[s] = j;
2884       ptr[j] = i;
2885       s = (s >> 8) | (block[i-1] << 8);
2886       j = ftab[s] -1;
2887       ftab[s] = j;
2888       ptr[j] = i-1;
2889       s = (s >> 8) | (block[i-2] << 8);
2890       j = ftab[s] -1;
2891       ftab[s] = j;
2892       ptr[j] = i-2;
2893       s = (s >> 8) | (block[i-3] << 8);
2894       j = ftab[s] -1;
2895       ftab[s] = j;
2896       ptr[j] = i-3;
2897    }
2898    for (; i >= 0; i--) {
2899       s = (s >> 8) | (block[i] << 8);
2900       j = ftab[s] -1;
2901       ftab[s] = j;
2902       ptr[j] = i;
2903    }
2904 
2905    /*--
2906       Now ftab contains the first loc of every small bucket.
2907       Calculate the running order, from smallest to largest
2908       big bucket.
2909    --*/
2910    for (i = 0; i <= 255; i++) {
2911       bigDone     [i] = False;
2912       runningOrder[i] = i;
2913    }
2914 
2915    {
2916       Int32 vv;
2917       Int32 h = 1;
2918       do h = 3 * h + 1; while (h <= 256);
2919       do {
2920          h = h / 3;
2921          for (i = h; i <= 255; i++) {
2922             vv = runningOrder[i];
2923             j = i;
2924             while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) {
2925                runningOrder[j] = runningOrder[j-h];
2926                j = j - h;
2927                if (j <= (h - 1)) goto zero;
2928             }
2929             zero:
2930             runningOrder[j] = vv;
2931          }
2932       } while (h != 1);
2933    }
2934 
2935    /*--
2936       The main sorting loop.
2937    --*/
2938 
2939    numQSorted = 0;
2940 
2941    for (i = 0; i <= 255; i++) {
2942 
2943       /*--
2944          Process big buckets, starting with the least full.
2945          Basically this is a 3-step process in which we call
2946          mainQSort3 to sort the small buckets [ss, j], but
2947          also make a big effort to avoid the calls if we can.
2948       --*/
2949       ss = runningOrder[i];
2950 
2951       /*--
2952          Step 1:
2953          Complete the big bucket [ss] by quicksorting
2954          any unsorted small buckets [ss, j], for j != ss.
2955          Hopefully previous pointer-scanning phases have already
2956          completed many of the small buckets [ss, j], so
2957          we don't have to sort them at all.
2958       --*/
2959       for (j = 0; j <= 255; j++) {
2960          if (j != ss) {
2961             sb = (ss << 8) + j;
2962             if ( ! (ftab[sb] & SETMASK) ) {
2963                Int32 lo = ftab[sb]   & CLEARMASK;
2964                Int32 hi = (ftab[sb+1] & CLEARMASK) - 1;
2965                if (hi > lo) {
2966                   if (verb >= 4)
2967                      VPrintf4 ( "        qsort [0x%x, 0x%x]   "
2968                                 "done %d   this %d\n",
2969                                 ss, j, numQSorted, hi - lo + 1 );
2970                   mainQSort3 (
2971                      ptr, block, quadrant, nblock,
2972                      lo, hi, BZ_N_RADIX, budget
2973                   );
2974                   numQSorted += (hi - lo + 1);
2975                   if (*budget < 0) return;
2976                }
2977             }
2978             ftab[sb] |= SETMASK;
2979          }
2980       }
2981 
2982       AssertH ( !bigDone[ss], 1006 );
2983 
2984       /*--
2985          Step 2:
2986          Now scan this big bucket [ss] so as to synthesise the
2987          sorted order for small buckets [t, ss] for all t,
2988          including, magically, the bucket [ss,ss] too.
2989          This will avoid doing Real Work in subsequent Step 1's.
2990       --*/
2991       {
2992          for (j = 0; j <= 255; j++) {
2993             copyStart[j] =  ftab[(j << 8) + ss]     & CLEARMASK;
2994             copyEnd  [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1;
2995          }
2996          for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) {
2997             k = ptr[j]-1; if (k < 0) k += nblock;
2998             c1 = block[k];
2999 croak( 2 + (char*)budget ); /* should identify decl in calling frame */
3000             if (!bigDone[c1])
3001                ptr[ copyStart[c1]++ ] = k;
3002          }
3003          for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) {
3004             k = ptr[j]-1; if (k < 0) k += nblock;
3005             c1 = block[k];
3006             if (!bigDone[c1])
3007                ptr[ copyEnd[c1]-- ] = k;
3008          }
3009       }
3010 
3011       AssertH ( (copyStart[ss]-1 == copyEnd[ss])
3012                 ||
3013                 /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1.
3014                    Necessity for this case is demonstrated by compressing
3015                    a sequence of approximately 48.5 million of character
3016                    251; 1.0.0/1.0.1 will then die here. */
3017                 (copyStart[ss] == 0 && copyEnd[ss] == nblock-1),
3018                 1007 )
3019 
3020       for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK;
3021 
3022       /*--
3023          Step 3:
3024          The [ss] big bucket is now done.  Record this fact,
3025          and update the quadrant descriptors.  Remember to
3026          update quadrants in the overshoot area too, if
3027          necessary.  The "if (i < 255)" test merely skips
3028          this updating for the last bucket processed, since
3029          updating for the last bucket is pointless.
3030 
3031          The quadrant array provides a way to incrementally
3032          cache sort orderings, as they appear, so as to
3033          make subsequent comparisons in fullGtU() complete
3034          faster.  For repetitive blocks this makes a big
3035          difference (but not big enough to be able to avoid
3036          the fallback sorting mechanism, exponential radix sort).
3037 
3038          The precise meaning is: at all times:
3039 
3040             for 0 <= i < nblock and 0 <= j <= nblock
3041 
3042             if block[i] != block[j],
3043 
3044                then the relative values of quadrant[i] and
3045                     quadrant[j] are meaningless.
3046 
3047                else {
3048                   if quadrant[i] < quadrant[j]
3049                      then the string starting at i lexicographically
3050                      precedes the string starting at j
3051 
3052                   else if quadrant[i] > quadrant[j]
3053                      then the string starting at j lexicographically
3054                      precedes the string starting at i
3055 
3056                   else
3057                      the relative ordering of the strings starting
3058                      at i and j has not yet been determined.
3059                }
3060       --*/
3061       bigDone[ss] = True;
3062 
3063       if (i < 255) {
3064          Int32 bbStart  = ftab[ss << 8] & CLEARMASK;
3065          Int32 bbSize   = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
3066          Int32 shifts   = 0;
3067 
3068          while ((bbSize >> shifts) > 65534) shifts++;
3069 
3070          for (j = bbSize-1; j >= 0; j--) {
3071             Int32 a2update     = ptr[bbStart + j];
3072             UInt16 qVal        = (UInt16)(j >> shifts);
3073             quadrant[a2update] = qVal;
3074             if (a2update < BZ_N_OVERSHOOT)
3075                quadrant[a2update + nblock] = qVal;
3076          }
3077          AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 );
3078       }
3079 
3080    }
3081 
3082    if (verb >= 4)
3083       VPrintf3 ( "        %d pointers, %d sorted, %d scanned\n",
3084                  nblock, numQSorted, nblock - numQSorted );
3085 }
3086 
3087 #undef BIGFREQ
3088 #undef SETMASK
3089 #undef CLEARMASK
3090 
3091 
3092 /*---------------------------------------------*/
3093 /* Pre:
3094       nblock > 0
3095       arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]
3096       ((UChar*)arr2)  [0 .. nblock-1] holds block
3097       arr1 exists for [0 .. nblock-1]
3098 
3099    Post:
3100       ((UChar*)arr2) [0 .. nblock-1] holds block
3101       All other areas of block destroyed
3102       ftab [ 0 .. 65536 ] destroyed
3103       arr1 [0 .. nblock-1] holds sorted order
3104 */
3105 __attribute__((noinline))
BZ2_blockSort(EState * s)3106 void BZ2_blockSort ( EState* s )
3107 {
3108    UInt32* ptr    = s->ptr;
3109    UChar*  block  = s->block;
3110    UInt32* ftab   = s->ftab;
3111    Int32   nblock = s->nblock;
3112    Int32   verb   = s->verbosity;
3113    Int32   wfact  = s->workFactor;
3114    UInt16* quadrant;
3115    Int32   budget;
3116    Int32   budgetInit;
3117    Int32   i;
3118 
3119    if (nblock < /* 10000 */1000 ) {
3120       fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
3121    } else {
3122       /* Calculate the location for quadrant, remembering to get
3123          the alignment right.  Assumes that &(block[0]) is at least
3124          2-byte aligned -- this should be ok since block is really
3125          the first section of arr2.
3126       */
3127       i = nblock+BZ_N_OVERSHOOT;
3128       if (i & 1) i++;
3129       quadrant = (UInt16*)(&(block[i]));
3130 
3131       /* (wfact-1) / 3 puts the default-factor-30
3132          transition point at very roughly the same place as
3133          with v0.1 and v0.9.0.
3134          Not that it particularly matters any more, since the
3135          resulting compressed stream is now the same regardless
3136          of whether or not we use the main sort or fallback sort.
3137       */
3138       if (wfact < 1  ) wfact = 1;
3139       if (wfact > 100) wfact = 100;
3140       budgetInit = nblock * ((wfact-1) / 3);
3141       budget = budgetInit;
3142 
3143       mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget );
3144       if (0 && verb >= 3)
3145          VPrintf3 ( "      %d work, %d block, ratio %5.2f\n",
3146                     budgetInit - budget,
3147                     nblock,
3148                     (float)(budgetInit - budget) /
3149                     (float)(nblock==0 ? 1 : nblock) );
3150       if (budget < 0) {
3151          if (verb >= 2)
3152             VPrintf0 ( "    too repetitive; using fallback"
3153                        " sorting algorithm\n" );
3154          fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
3155       }
3156    }
3157 
3158    s->origPtr = -1;
3159    for (i = 0; i < s->nblock; i++)
3160       if (ptr[i] == 0)
3161          { s->origPtr = i; break; };
3162 
3163    AssertH( s->origPtr != -1, 1003 );
3164 }
3165 
3166 
3167 /*-------------------------------------------------------------*/
3168 /*--- end                                       blocksort.c ---*/
3169 /*-------------------------------------------------------------*/
3170 
3171 /*-------------------------------------------------------------*/
3172 /*--- Huffman coding low-level stuff                        ---*/
3173 /*---                                             huffman.c ---*/
3174 /*-------------------------------------------------------------*/
3175 
3176 /*--
3177   This file is a part of bzip2 and/or libbzip2, a program and
3178   library for lossless, block-sorting data compression.
3179 
3180   Copyright (C) 1996-2004 Julian R Seward.  All rights reserved.
3181 
3182   Redistribution and use in source and binary forms, with or without
3183   modification, are permitted provided that the following conditions
3184   are met:
3185 
3186   1. Redistributions of source code must retain the above copyright
3187      notice, this list of conditions and the following disclaimer.
3188 
3189   2. The origin of this software must not be misrepresented; you must
3190      not claim that you wrote the original software.  If you use this
3191      software in a product, an acknowledgment in the product
3192      documentation would be appreciated but is not required.
3193 
3194   3. Altered source versions must be plainly marked as such, and must
3195      not be misrepresented as being the original software.
3196 
3197   4. The name of the author may not be used to endorse or promote
3198      products derived from this software without specific prior written
3199      permission.
3200 
3201   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
3202   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
3203   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
3204   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
3205   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
3206   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
3207   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
3208   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
3209   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
3210   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
3211   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3212 
3213   Julian Seward, Cambridge, UK.
3214   jseward@bzip.org
3215   bzip2/libbzip2 version 1.0 of 21 March 2000
3216 
3217   This program is based on (at least) the work of:
3218      Mike Burrows
3219      David Wheeler
3220      Peter Fenwick
3221      Alistair Moffat
3222      Radford Neal
3223      Ian H. Witten
3224      Robert Sedgewick
3225      Jon L. Bentley
3226 
3227   For more information on these sources, see the manual.
3228 --*/
3229 
3230 
3231 
3232 /*---------------------------------------------------*/
3233 #define WEIGHTOF(zz0)  ((zz0) & 0xffffff00)
3234 #define DEPTHOF(zz1)   ((zz1) & 0x000000ff)
3235 #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
3236 
3237 #define ADDWEIGHTS(zw1,zw2)                           \
3238    (WEIGHTOF(zw1)+WEIGHTOF(zw2)) |                    \
3239    (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
3240 
3241 #define UPHEAP(z)                                     \
3242 {                                                     \
3243    Int32 zz, tmp;                                     \
3244    zz = z; tmp = heap[zz];                            \
3245    while (weight[tmp] < weight[heap[zz >> 1]]) {      \
3246       heap[zz] = heap[zz >> 1];                       \
3247       zz >>= 1;                                       \
3248    }                                                  \
3249    heap[zz] = tmp;                                    \
3250 }
3251 
3252 #define DOWNHEAP(z)                                   \
3253 {                                                     \
3254    Int32 zz, yy, tmp;                                 \
3255    zz = z; tmp = heap[zz];                            \
3256    while (True) {                                     \
3257       yy = zz << 1;                                   \
3258       if (yy > nHeap) break;                          \
3259       if (yy < nHeap &&                               \
3260           weight[heap[yy+1]] < weight[heap[yy]])      \
3261          yy++;                                        \
3262       if (weight[tmp] < weight[heap[yy]]) break;      \
3263       heap[zz] = heap[yy];                            \
3264       zz = yy;                                        \
3265    }                                                  \
3266    heap[zz] = tmp;                                    \
3267 }
3268 
3269 
3270 /*---------------------------------------------------*/
BZ2_hbMakeCodeLengths(UChar * len,Int32 * freq,Int32 alphaSize,Int32 maxLen)3271 void BZ2_hbMakeCodeLengths ( UChar *len,
3272                              Int32 *freq,
3273                              Int32 alphaSize,
3274                              Int32 maxLen )
3275 {
3276    /*--
3277       Nodes and heap entries run from 1.  Entry 0
3278       for both the heap and nodes is a sentinel.
3279    --*/
3280    Int32 nNodes, nHeap, n1, n2, i, j, k;
3281    Bool  tooLong;
3282 
3283    Int32 heap   [ BZ_MAX_ALPHA_SIZE + 2 ];
3284    Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
3285    Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
3286 
3287    for (i = 0; i < alphaSize; i++)
3288       weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
3289 
3290    while (True) {
3291 
3292       nNodes = alphaSize;
3293       nHeap = 0;
3294 
3295       heap[0] = 0;
3296       weight[0] = 0;
3297       parent[0] = -2;
3298 
3299       for (i = 1; i <= alphaSize; i++) {
3300          parent[i] = -1;
3301          nHeap++;
3302          heap[nHeap] = i;
3303          UPHEAP(nHeap);
3304       }
3305 
3306       AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
3307 
3308       while (nHeap > 1) {
3309          n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
3310          n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
3311          nNodes++;
3312          parent[n1] = parent[n2] = nNodes;
3313          weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
3314          parent[nNodes] = -1;
3315          nHeap++;
3316          heap[nHeap] = nNodes;
3317          UPHEAP(nHeap);
3318       }
3319 
3320       AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
3321 
3322       tooLong = False;
3323       for (i = 1; i <= alphaSize; i++) {
3324          j = 0;
3325          k = i;
3326          while (parent[k] >= 0) { k = parent[k]; j++; }
3327          len[i-1] = j;
3328          if (j > maxLen) tooLong = True;
3329       }
3330 
3331       if (! tooLong) break;
3332 
3333       /* 17 Oct 04: keep-going condition for the following loop used
3334          to be 'i < alphaSize', which missed the last element,
3335          theoretically leading to the possibility of the compressor
3336          looping.  However, this count-scaling step is only needed if
3337          one of the generated Huffman code words is longer than
3338          maxLen, which up to and including version 1.0.2 was 20 bits,
3339          which is extremely unlikely.  In version 1.0.3 maxLen was
3340          changed to 17 bits, which has minimal effect on compression
3341          ratio, but does mean this scaling step is used from time to
3342          time, enough to verify that it works.
3343 
3344          This means that bzip2-1.0.3 and later will only produce
3345          Huffman codes with a maximum length of 17 bits.  However, in
3346          order to preserve backwards compatibility with bitstreams
3347          produced by versions pre-1.0.3, the decompressor must still
3348          handle lengths of up to 20. */
3349 
3350       for (i = 1; i <= alphaSize; i++) {
3351          j = weight[i] >> 8;
3352          j = 1 + (j / 2);
3353          weight[i] = j << 8;
3354       }
3355    }
3356 }
3357 
3358 
3359 /*---------------------------------------------------*/
BZ2_hbAssignCodes(Int32 * code,UChar * length,Int32 minLen,Int32 maxLen,Int32 alphaSize)3360 void BZ2_hbAssignCodes ( Int32 *code,
3361                          UChar *length,
3362                          Int32 minLen,
3363                          Int32 maxLen,
3364                          Int32 alphaSize )
3365 {
3366    Int32 n, vec, i;
3367 
3368    vec = 0;
3369    for (n = minLen; n <= maxLen; n++) {
3370       for (i = 0; i < alphaSize; i++)
3371          if (length[i] == n) { code[i] = vec; vec++; };
3372       vec <<= 1;
3373    }
3374 }
3375 
3376 
3377 /*---------------------------------------------------*/
BZ2_hbCreateDecodeTables(Int32 * limit,Int32 * base,Int32 * perm,UChar * length,Int32 minLen,Int32 maxLen,Int32 alphaSize)3378 void BZ2_hbCreateDecodeTables ( Int32 *limit,
3379                                 Int32 *base,
3380                                 Int32 *perm,
3381                                 UChar *length,
3382                                 Int32 minLen,
3383                                 Int32 maxLen,
3384                                 Int32 alphaSize )
3385 {
3386    Int32 pp, i, j, vec;
3387 
3388    pp = 0;
3389    for (i = minLen; i <= maxLen; i++)
3390       for (j = 0; j < alphaSize; j++)
3391          if (length[j] == i) { perm[pp] = j; pp++; };
3392 
3393    for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
3394    for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
3395 
3396    for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
3397 
3398    for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
3399    vec = 0;
3400 
3401    for (i = minLen; i <= maxLen; i++) {
3402       vec += (base[i+1] - base[i]);
3403       limit[i] = vec-1;
3404       vec <<= 1;
3405    }
3406    for (i = minLen + 1; i <= maxLen; i++)
3407       base[i] = ((limit[i-1] + 1) << 1) - base[i];
3408 }
3409 
3410 
3411 /*-------------------------------------------------------------*/
3412 /*--- end                                         huffman.c ---*/
3413 /*-------------------------------------------------------------*/
3414 
3415 /*-------------------------------------------------------------*/
3416 /*--- Compression machinery (not incl block sorting)        ---*/
3417 /*---                                            compress.c ---*/
3418 /*-------------------------------------------------------------*/
3419 
3420 /*--
3421   This file is a part of bzip2 and/or libbzip2, a program and
3422   library for lossless, block-sorting data compression.
3423 
3424   Copyright (C) 1996-2004 Julian R Seward.  All rights reserved.
3425 
3426   Redistribution and use in source and binary forms, with or without
3427   modification, are permitted provided that the following conditions
3428   are met:
3429 
3430   1. Redistributions of source code must retain the above copyright
3431      notice, this list of conditions and the following disclaimer.
3432 
3433   2. The origin of this software must not be misrepresented; you must
3434      not claim that you wrote the original software.  If you use this
3435      software in a product, an acknowledgment in the product
3436      documentation would be appreciated but is not required.
3437 
3438   3. Altered source versions must be plainly marked as such, and must
3439      not be misrepresented as being the original software.
3440 
3441   4. The name of the author may not be used to endorse or promote
3442      products derived from this software without specific prior written
3443      permission.
3444 
3445   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
3446   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
3447   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
3448   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
3449   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
3450   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
3451   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
3452   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
3453   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
3454   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
3455   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3456 
3457   Julian Seward, Cambridge, UK.
3458   jseward@bzip.org
3459   bzip2/libbzip2 version 1.0 of 21 March 2000
3460 
3461   This program is based on (at least) the work of:
3462      Mike Burrows
3463      David Wheeler
3464      Peter Fenwick
3465      Alistair Moffat
3466      Radford Neal
3467      Ian H. Witten
3468      Robert Sedgewick
3469      Jon L. Bentley
3470 
3471   For more information on these sources, see the manual.
3472 --*/
3473 
3474 /*--
3475    CHANGES
3476    ~~~~~~~
3477    0.9.0 -- original version.
3478 
3479    0.9.0a/b -- no changes in this file.
3480 
3481    0.9.0c
3482       * changed setting of nGroups in sendMTFValues() so as to
3483         do a bit better on small files
3484 --*/
3485 
3486 
3487 
3488 /*---------------------------------------------------*/
3489 /*--- Bit stream I/O                              ---*/
3490 /*---------------------------------------------------*/
3491 
3492 /*---------------------------------------------------*/
BZ2_bsInitWrite(EState * s)3493 void BZ2_bsInitWrite ( EState* s )
3494 {
3495    s->bsLive = 0;
3496    s->bsBuff = 0;
3497 }
3498 
3499 
3500 /*---------------------------------------------------*/
3501 static
bsFinishWrite(EState * s)3502 void bsFinishWrite ( EState* s )
3503 {
3504    while (s->bsLive > 0) {
3505       s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24);
3506       s->numZ++;
3507       s->bsBuff <<= 8;
3508       s->bsLive -= 8;
3509    }
3510 }
3511 
3512 
3513 /*---------------------------------------------------*/
3514 #define bsNEEDW(nz)                           \
3515 {                                             \
3516    while (s->bsLive >= 8) {                   \
3517       s->zbits[s->numZ]                       \
3518          = (UChar)(s->bsBuff >> 24);          \
3519       s->numZ++;                              \
3520       s->bsBuff <<= 8;                        \
3521       s->bsLive -= 8;                         \
3522    }                                          \
3523 }
3524 
3525 
3526 /*---------------------------------------------------*/
3527 static
bsW(EState * s,Int32 n,UInt32 v)3528 void bsW ( EState* s, Int32 n, UInt32 v )
3529 {
3530    bsNEEDW ( n );
3531    s->bsBuff |= (v << (32 - s->bsLive - n));
3532    s->bsLive += n;
3533 }
3534 
3535 
3536 /*---------------------------------------------------*/
3537 static
bsPutUInt32(EState * s,UInt32 u)3538 void bsPutUInt32 ( EState* s, UInt32 u )
3539 {
3540    bsW ( s, 8, (u >> 24) & 0xffL );
3541    bsW ( s, 8, (u >> 16) & 0xffL );
3542    bsW ( s, 8, (u >>  8) & 0xffL );
3543    bsW ( s, 8,  u        & 0xffL );
3544 }
3545 
3546 
3547 /*---------------------------------------------------*/
3548 static
bsPutUChar(EState * s,UChar c)3549 void bsPutUChar ( EState* s, UChar c )
3550 {
3551    bsW( s, 8, (UInt32)c );
3552 }
3553 
3554 
3555 /*---------------------------------------------------*/
3556 /*--- The back end proper                         ---*/
3557 /*---------------------------------------------------*/
3558 
3559 /*---------------------------------------------------*/
3560 static
makeMaps_e(EState * s)3561 void makeMaps_e ( EState* s )
3562 {
3563    Int32 i;
3564    s->nInUse = 0;
3565    for (i = 0; i < 256; i++)
3566       if (s->inUse[i]) {
3567          s->unseqToSeq[i] = s->nInUse;
3568          s->nInUse++;
3569       }
3570 }
3571 
3572 
3573 /*---------------------------------------------------*/
3574 static
generateMTFValues(EState * s)3575 void generateMTFValues ( EState* s )
3576 {
3577    UChar   yy[256];
3578    Int32   i, j;
3579    Int32   zPend;
3580    Int32   wr;
3581    Int32   EOB;
3582 
3583    /*
3584       After sorting (eg, here),
3585          s->arr1 [ 0 .. s->nblock-1 ] holds sorted order,
3586          and
3587          ((UChar*)s->arr2) [ 0 .. s->nblock-1 ]
3588          holds the original block data.
3589 
3590       The first thing to do is generate the MTF values,
3591       and put them in
3592          ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ].
3593       Because there are strictly fewer or equal MTF values
3594       than block values, ptr values in this area are overwritten
3595       with MTF values only when they are no longer needed.
3596 
3597       The final compressed bitstream is generated into the
3598       area starting at
3599          (UChar*) (&((UChar*)s->arr2)[s->nblock])
3600 
3601       These storage aliases are set up in bzCompressInit(),
3602       except for the last one, which is arranged in
3603       compressBlock().
3604    */
3605    UInt32* ptr   = s->ptr;
3606    UChar* block  = s->block;
3607    UInt16* mtfv  = s->mtfv;
3608 
3609    makeMaps_e ( s );
3610    EOB = s->nInUse+1;
3611 
3612    for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0;
3613 
3614    wr = 0;
3615    zPend = 0;
3616    for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i;
3617 
3618    for (i = 0; i < s->nblock; i++) {
3619       UChar ll_i;
3620       AssertD ( wr <= i, "generateMTFValues(1)" );
3621       j = ptr[i]-1; if (j < 0) j += s->nblock;
3622       ll_i = s->unseqToSeq[block[j]];
3623       AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" );
3624 
3625       if (yy[0] == ll_i) {
3626          zPend++;
3627       } else {
3628 
3629          if (zPend > 0) {
3630             zPend--;
3631             while (True) {
3632                if (zPend & 1) {
3633                   mtfv[wr] = BZ_RUNB; wr++;
3634                   s->mtfFreq[BZ_RUNB]++;
3635                } else {
3636                   mtfv[wr] = BZ_RUNA; wr++;
3637                   s->mtfFreq[BZ_RUNA]++;
3638                }
3639                if (zPend < 2) break;
3640                zPend = (zPend - 2) / 2;
3641             };
3642             zPend = 0;
3643          }
3644          {
3645             register UChar  rtmp;
3646             register UChar* ryy_j;
3647             register UChar  rll_i;
3648             rtmp  = yy[1];
3649             yy[1] = yy[0];
3650             ryy_j = &(yy[1]);
3651             rll_i = ll_i;
3652             while ( rll_i != rtmp ) {
3653                register UChar rtmp2;
3654                ryy_j++;
3655                rtmp2  = rtmp;
3656                rtmp   = *ryy_j;
3657                *ryy_j = rtmp2;
3658             };
3659             yy[0] = rtmp;
3660             j = ryy_j - &(yy[0]);
3661             mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++;
3662          }
3663 
3664       }
3665    }
3666 
3667    if (zPend > 0) {
3668       zPend--;
3669       while (True) {
3670          if (zPend & 1) {
3671             mtfv[wr] = BZ_RUNB; wr++;
3672             s->mtfFreq[BZ_RUNB]++;
3673          } else {
3674             mtfv[wr] = BZ_RUNA; wr++;
3675             s->mtfFreq[BZ_RUNA]++;
3676          }
3677          if (zPend < 2) break;
3678          zPend = (zPend - 2) / 2;
3679       };
3680       zPend = 0;
3681    }
3682 
3683    mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++;
3684 
3685    s->nMTF = wr;
3686 }
3687 
3688 
3689 /*---------------------------------------------------*/
3690 #define BZ_LESSER_ICOST  0
3691 #define BZ_GREATER_ICOST 15
3692 
3693 static
sendMTFValues(EState * s)3694 void sendMTFValues ( EState* s )
3695 {
3696    Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;
3697    Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;
3698    Int32 nGroups, nBytes;
3699 
3700    /*--
3701    UChar  len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
3702    is a global since the decoder also needs it.
3703 
3704    Int32  code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
3705    Int32  rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
3706    are also globals only used in this proc.
3707    Made global to keep stack frame size small.
3708    --*/
3709 
3710 
3711    UInt16 cost[BZ_N_GROUPS];
3712    Int32  fave[BZ_N_GROUPS];
3713 
3714    UInt16* mtfv = s->mtfv;
3715 
3716    if (s->verbosity >= 3)
3717       VPrintf3( "      %d in block, %d after MTF & 1-2 coding, "
3718                 "%d+2 syms in use\n",
3719                 s->nblock, s->nMTF, s->nInUse );
3720 
3721    alphaSize = s->nInUse+2;
3722    for (t = 0; t < BZ_N_GROUPS; t++)
3723       for (v = 0; v < alphaSize; v++)
3724          s->len[t][v] = BZ_GREATER_ICOST;
3725 
3726    /*--- Decide how many coding tables to use ---*/
3727    AssertH ( s->nMTF > 0, 3001 );
3728    if (s->nMTF < 200)  nGroups = 2; else
3729    if (s->nMTF < 600)  nGroups = 3; else
3730    if (s->nMTF < 1200) nGroups = 4; else
3731    if (s->nMTF < 2400) nGroups = 5; else
3732                        nGroups = 6;
3733 
3734    /*--- Generate an initial set of coding tables ---*/
3735    {
3736       Int32 nPart, remF, tFreq, aFreq;
3737 
3738       nPart = nGroups;
3739       remF  = s->nMTF;
3740       gs = 0;
3741       while (nPart > 0) {
3742          tFreq = remF / nPart;
3743          ge = gs-1;
3744          aFreq = 0;
3745          while (aFreq < tFreq && ge < alphaSize-1) {
3746             ge++;
3747             aFreq += s->mtfFreq[ge];
3748          }
3749 
3750          if (ge > gs
3751              && nPart != nGroups && nPart != 1
3752              && ((nGroups-nPart) % 2 == 1)) {
3753             aFreq -= s->mtfFreq[ge];
3754             ge--;
3755          }
3756 
3757          if (0 && s->verbosity >= 3)
3758             VPrintf5( "      initial group %d, [%d .. %d], "
3759                       "has %d syms (%4.1f%%)\n",
3760                       nPart, gs, ge, aFreq,
3761                       (100.0 * (float)aFreq) / (float)(s->nMTF) );
3762 
3763          for (v = 0; v < alphaSize; v++)
3764             if (v >= gs && v <= ge)
3765                s->len[nPart-1][v] = BZ_LESSER_ICOST; else
3766                s->len[nPart-1][v] = BZ_GREATER_ICOST;
3767 
3768          nPart--;
3769          gs = ge+1;
3770          remF -= aFreq;
3771       }
3772    }
3773 
3774    /*---
3775       Iterate up to BZ_N_ITERS times to improve the tables.
3776    ---*/
3777    for (iter = 0; iter < BZ_N_ITERS; iter++) {
3778 
3779       for (t = 0; t < nGroups; t++) fave[t] = 0;
3780 
3781       for (t = 0; t < nGroups; t++)
3782          for (v = 0; v < alphaSize; v++)
3783             s->rfreq[t][v] = 0;
3784 
3785       /*---
3786         Set up an auxiliary length table which is used to fast-track
3787 	the common case (nGroups == 6).
3788       ---*/
3789       if (nGroups == 6) {
3790          for (v = 0; v < alphaSize; v++) {
3791             s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
3792             s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
3793             s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
3794 	 }
3795       }
3796 
3797       nSelectors = 0;
3798       totc = 0;
3799       gs = 0;
3800       while (True) {
3801 
3802          /*--- Set group start & end marks. --*/
3803          if (gs >= s->nMTF) break;
3804          ge = gs + BZ_G_SIZE - 1;
3805          if (ge >= s->nMTF) ge = s->nMTF-1;
3806 
3807          /*--
3808             Calculate the cost of this group as coded
3809             by each of the coding tables.
3810          --*/
3811          for (t = 0; t < nGroups; t++) cost[t] = 0;
3812 
3813          if (nGroups == 6 && 50 == ge-gs+1) {
3814             /*--- fast track the common case ---*/
3815             register UInt32 cost01, cost23, cost45;
3816             register UInt16 icv;
3817             cost01 = cost23 = cost45 = 0;
3818 
3819 #           define BZ_ITER(nn)                \
3820                icv = mtfv[gs+(nn)];           \
3821                cost01 += s->len_pack[icv][0]; \
3822                cost23 += s->len_pack[icv][1]; \
3823                cost45 += s->len_pack[icv][2]; \
3824 
3825             BZ_ITER(0);  BZ_ITER(1);  BZ_ITER(2);  BZ_ITER(3);  BZ_ITER(4);
3826             BZ_ITER(5);  BZ_ITER(6);  BZ_ITER(7);  BZ_ITER(8);  BZ_ITER(9);
3827             BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
3828             BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
3829             BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
3830             BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
3831             BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
3832             BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
3833             BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
3834             BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
3835 
3836 #           undef BZ_ITER
3837 
3838             cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
3839             cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
3840             cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
3841 
3842          } else {
3843 	    /*--- slow version which correctly handles all situations ---*/
3844             for (i = gs; i <= ge; i++) {
3845                UInt16 icv = mtfv[i];
3846                for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv];
3847             }
3848          }
3849 
3850          /*--
3851             Find the coding table which is best for this group,
3852             and record its identity in the selector table.
3853          --*/
3854          bc = 999999999; bt = -1;
3855          for (t = 0; t < nGroups; t++)
3856             if (cost[t] < bc) { bc = cost[t]; bt = t; };
3857          totc += bc;
3858          fave[bt]++;
3859          s->selector[nSelectors] = bt;
3860          nSelectors++;
3861 
3862          /*--
3863             Increment the symbol frequencies for the selected table.
3864           --*/
3865          if (nGroups == 6 && 50 == ge-gs+1) {
3866             /*--- fast track the common case ---*/
3867 
3868 #           define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++
3869 
3870             BZ_ITUR(0);  BZ_ITUR(1);  BZ_ITUR(2);  BZ_ITUR(3);  BZ_ITUR(4);
3871             BZ_ITUR(5);  BZ_ITUR(6);  BZ_ITUR(7);  BZ_ITUR(8);  BZ_ITUR(9);
3872             BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
3873             BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
3874             BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
3875             BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
3876             BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
3877             BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
3878             BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
3879             BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
3880 
3881 #           undef BZ_ITUR
3882 
3883          } else {
3884 	    /*--- slow version which correctly handles all situations ---*/
3885             for (i = gs; i <= ge; i++)
3886                s->rfreq[bt][ mtfv[i] ]++;
3887          }
3888 
3889          gs = ge+1;
3890       }
3891       if (s->verbosity >= 3) {
3892          VPrintf2 ( "      pass %d: size is %d, grp uses are ",
3893                    iter+1, totc/8 );
3894          for (t = 0; t < nGroups; t++)
3895             VPrintf1 ( "%d ", fave[t] );
3896          VPrintf0 ( "\n" );
3897       }
3898 
3899       /*--
3900         Recompute the tables based on the accumulated frequencies.
3901       --*/
3902       /* maxLen was changed from 20 to 17 in bzip2-1.0.3.  See
3903          comment in huffman.c for details. */
3904       for (t = 0; t < nGroups; t++)
3905          BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]),
3906                                  alphaSize, 17 /*20*/ );
3907    }
3908 
3909 
3910    AssertH( nGroups < 8, 3002 );
3911    AssertH( nSelectors < 32768 &&
3912             nSelectors <= (2 + (900000 / BZ_G_SIZE)),
3913             3003 );
3914 
3915 
3916    /*--- Compute MTF values for the selectors. ---*/
3917    {
3918       UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
3919       for (i = 0; i < nGroups; i++) pos[i] = i;
3920       for (i = 0; i < nSelectors; i++) {
3921          ll_i = s->selector[i];
3922          j = 0;
3923          tmp = pos[j];
3924          while ( ll_i != tmp ) {
3925             j++;
3926             tmp2 = tmp;
3927             tmp = pos[j];
3928             pos[j] = tmp2;
3929          };
3930          pos[0] = tmp;
3931          s->selectorMtf[i] = j;
3932       }
3933    };
3934 
3935    /*--- Assign actual codes for the tables. --*/
3936    for (t = 0; t < nGroups; t++) {
3937       minLen = 32;
3938       maxLen = 0;
3939       for (i = 0; i < alphaSize; i++) {
3940          if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
3941          if (s->len[t][i] < minLen) minLen = s->len[t][i];
3942       }
3943       AssertH ( !(maxLen > 17 /*20*/ ), 3004 );
3944       AssertH ( !(minLen < 1),  3005 );
3945       BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]),
3946                           minLen, maxLen, alphaSize );
3947    }
3948 
3949    /*--- Transmit the mapping table. ---*/
3950    {
3951       Bool inUse16[16];
3952       for (i = 0; i < 16; i++) {
3953           inUse16[i] = False;
3954           for (j = 0; j < 16; j++)
3955              if (s->inUse[i * 16 + j]) inUse16[i] = True;
3956       }
3957 
3958       nBytes = s->numZ;
3959       for (i = 0; i < 16; i++)
3960          if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
3961 
3962       for (i = 0; i < 16; i++)
3963          if (inUse16[i])
3964             for (j = 0; j < 16; j++) {
3965                if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
3966             }
3967 
3968       if (s->verbosity >= 3)
3969          VPrintf1( "      bytes: mapping %d, ", s->numZ-nBytes );
3970    }
3971 
3972    /*--- Now the selectors. ---*/
3973    nBytes = s->numZ;
3974    bsW ( s, 3, nGroups );
3975    bsW ( s, 15, nSelectors );
3976    for (i = 0; i < nSelectors; i++) {
3977       for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
3978       bsW(s,1,0);
3979    }
3980    if (s->verbosity >= 3)
3981       VPrintf1( "selectors %d, ", s->numZ-nBytes );
3982 
3983    /*--- Now the coding tables. ---*/
3984    nBytes = s->numZ;
3985 
3986    for (t = 0; t < nGroups; t++) {
3987       Int32 curr = s->len[t][0];
3988       bsW ( s, 5, curr );
3989       for (i = 0; i < alphaSize; i++) {
3990          while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };
3991          while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
3992          bsW ( s, 1, 0 );
3993       }
3994    }
3995 
3996    if (s->verbosity >= 3)
3997       VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
3998 
3999    /*--- And finally, the block data proper ---*/
4000    nBytes = s->numZ;
4001    selCtr = 0;
4002    gs = 0;
4003    while (True) {
4004       if (gs >= s->nMTF) break;
4005       ge = gs + BZ_G_SIZE - 1;
4006       if (ge >= s->nMTF) ge = s->nMTF-1;
4007       AssertH ( s->selector[selCtr] < nGroups, 3006 );
4008 
4009       if (nGroups == 6 && 50 == ge-gs+1) {
4010             /*--- fast track the common case ---*/
4011             UInt16 mtfv_i;
4012             UChar* s_len_sel_selCtr
4013                = &(s->len[s->selector[selCtr]][0]);
4014             Int32* s_code_sel_selCtr
4015                = &(s->code[s->selector[selCtr]][0]);
4016 
4017 #           define BZ_ITAH(nn)                      \
4018                mtfv_i = mtfv[gs+(nn)];              \
4019                bsW ( s,                             \
4020                      s_len_sel_selCtr[mtfv_i],      \
4021                      s_code_sel_selCtr[mtfv_i] )
4022 
4023             BZ_ITAH(0);  BZ_ITAH(1);  BZ_ITAH(2);  BZ_ITAH(3);  BZ_ITAH(4);
4024             BZ_ITAH(5);  BZ_ITAH(6);  BZ_ITAH(7);  BZ_ITAH(8);  BZ_ITAH(9);
4025             BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
4026             BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
4027             BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
4028             BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
4029             BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
4030             BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
4031             BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
4032             BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
4033 
4034 #           undef BZ_ITAH
4035 
4036       } else {
4037 	 /*--- slow version which correctly handles all situations ---*/
4038          for (i = gs; i <= ge; i++) {
4039             bsW ( s,
4040                   s->len  [s->selector[selCtr]] [mtfv[i]],
4041                   s->code [s->selector[selCtr]] [mtfv[i]] );
4042          }
4043       }
4044 
4045 
4046       gs = ge+1;
4047       selCtr++;
4048    }
4049    AssertH( selCtr == nSelectors, 3007 );
4050 
4051    if (s->verbosity >= 3)
4052       VPrintf1( "codes %d\n", s->numZ-nBytes );
4053 }
4054 
4055 
4056 /*---------------------------------------------------*/
4057 __attribute__((noinline))
BZ2_compressBlock(EState * s,Bool is_last_block)4058 void BZ2_compressBlock ( EState* s, Bool is_last_block )
4059 {
4060    if (s->nblock > 0) {
4061 
4062       BZ_FINALISE_CRC ( s->blockCRC );
4063       s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
4064       s->combinedCRC ^= s->blockCRC;
4065       if (s->blockNo > 1) s->numZ = 0;
4066 
4067       if (s->verbosity >= 2)
4068          VPrintf4( "    block %d: crc = 0x%08x, "
4069                    "combined CRC = 0x%08x, size = %d\n",
4070                    s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
4071 
4072       BZ2_blockSort ( s );
4073    }
4074 
4075    s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
4076 
4077    /*-- If this is the first block, create the stream header. --*/
4078    if (s->blockNo == 1) {
4079       BZ2_bsInitWrite ( s );
4080       bsPutUChar ( s, BZ_HDR_B );
4081       bsPutUChar ( s, BZ_HDR_Z );
4082       bsPutUChar ( s, BZ_HDR_h );
4083       bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
4084    }
4085 
4086    if (s->nblock > 0) {
4087 
4088       bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
4089       bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
4090       bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
4091 
4092       /*-- Now the block's CRC, so it is in a known place. --*/
4093       bsPutUInt32 ( s, s->blockCRC );
4094 
4095       /*--
4096          Now a single bit indicating (non-)randomisation.
4097          As of version 0.9.5, we use a better sorting algorithm
4098          which makes randomisation unnecessary.  So always set
4099          the randomised bit to 'no'.  Of course, the decoder
4100          still needs to be able to handle randomised blocks
4101          so as to maintain backwards compatibility with
4102          older versions of bzip2.
4103       --*/
4104       bsW(s,1,0);
4105 
4106       bsW ( s, 24, s->origPtr );
4107       generateMTFValues ( s );
4108       sendMTFValues ( s );
4109    }
4110 
4111 
4112    /*-- If this is the last block, add the stream trailer. --*/
4113    if (is_last_block) {
4114 
4115       bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
4116       bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
4117       bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
4118       bsPutUInt32 ( s, s->combinedCRC );
4119       if (s->verbosity >= 2)
4120          VPrintf1( "    final combined CRC = 0x%08x\n   ", s->combinedCRC );
4121       bsFinishWrite ( s );
4122    }
4123 }
4124 
4125 
4126 /*-------------------------------------------------------------*/
4127 /*--- end                                        compress.c ---*/
4128 /*-------------------------------------------------------------*/
4129 
4130 
4131 /*-------------------------------------------------------------*/
4132 /*--- Table for randomising repetitive blocks               ---*/
4133 /*---                                           randtable.c ---*/
4134 /*-------------------------------------------------------------*/
4135 
4136 /*--
4137   This file is a part of bzip2 and/or libbzip2, a program and
4138   library for lossless, block-sorting data compression.
4139 
4140   Copyright (C) 1996-2004 Julian R Seward.  All rights reserved.
4141 
4142   Redistribution and use in source and binary forms, with or without
4143   modification, are permitted provided that the following conditions
4144   are met:
4145 
4146   1. Redistributions of source code must retain the above copyright
4147      notice, this list of conditions and the following disclaimer.
4148 
4149   2. The origin of this software must not be misrepresented; you must
4150      not claim that you wrote the original software.  If you use this
4151      software in a product, an acknowledgment in the product
4152      documentation would be appreciated but is not required.
4153 
4154   3. Altered source versions must be plainly marked as such, and must
4155      not be misrepresented as being the original software.
4156 
4157   4. The name of the author may not be used to endorse or promote
4158      products derived from this software without specific prior written
4159      permission.
4160 
4161   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
4162   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
4163   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
4164   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
4165   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
4166   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
4167   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
4168   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
4169   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
4170   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
4171   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
4172 
4173   Julian Seward, Cambridge, UK.
4174   jseward@bzip.org
4175   bzip2/libbzip2 version 1.0 of 21 March 2000
4176 
4177   This program is based on (at least) the work of:
4178      Mike Burrows
4179      David Wheeler
4180      Peter Fenwick
4181      Alistair Moffat
4182      Radford Neal
4183      Ian H. Witten
4184      Robert Sedgewick
4185      Jon L. Bentley
4186 
4187   For more information on these sources, see the manual.
4188 --*/
4189 
4190 
4191 
4192 
4193 /*---------------------------------------------*/
4194 Int32 BZ2_rNums[512] = {
4195    619, 720, 127, 481, 931, 816, 813, 233, 566, 247,
4196    985, 724, 205, 454, 863, 491, 741, 242, 949, 214,
4197    733, 859, 335, 708, 621, 574, 73, 654, 730, 472,
4198    419, 436, 278, 496, 867, 210, 399, 680, 480, 51,
4199    878, 465, 811, 169, 869, 675, 611, 697, 867, 561,
4200    862, 687, 507, 283, 482, 129, 807, 591, 733, 623,
4201    150, 238, 59, 379, 684, 877, 625, 169, 643, 105,
4202    170, 607, 520, 932, 727, 476, 693, 425, 174, 647,
4203    73, 122, 335, 530, 442, 853, 695, 249, 445, 515,
4204    909, 545, 703, 919, 874, 474, 882, 500, 594, 612,
4205    641, 801, 220, 162, 819, 984, 589, 513, 495, 799,
4206    161, 604, 958, 533, 221, 400, 386, 867, 600, 782,
4207    382, 596, 414, 171, 516, 375, 682, 485, 911, 276,
4208    98, 553, 163, 354, 666, 933, 424, 341, 533, 870,
4209    227, 730, 475, 186, 263, 647, 537, 686, 600, 224,
4210    469, 68, 770, 919, 190, 373, 294, 822, 808, 206,
4211    184, 943, 795, 384, 383, 461, 404, 758, 839, 887,
4212    715, 67, 618, 276, 204, 918, 873, 777, 604, 560,
4213    951, 160, 578, 722, 79, 804, 96, 409, 713, 940,
4214    652, 934, 970, 447, 318, 353, 859, 672, 112, 785,
4215    645, 863, 803, 350, 139, 93, 354, 99, 820, 908,
4216    609, 772, 154, 274, 580, 184, 79, 626, 630, 742,
4217    653, 282, 762, 623, 680, 81, 927, 626, 789, 125,
4218    411, 521, 938, 300, 821, 78, 343, 175, 128, 250,
4219    170, 774, 972, 275, 999, 639, 495, 78, 352, 126,
4220    857, 956, 358, 619, 580, 124, 737, 594, 701, 612,
4221    669, 112, 134, 694, 363, 992, 809, 743, 168, 974,
4222    944, 375, 748, 52, 600, 747, 642, 182, 862, 81,
4223    344, 805, 988, 739, 511, 655, 814, 334, 249, 515,
4224    897, 955, 664, 981, 649, 113, 974, 459, 893, 228,
4225    433, 837, 553, 268, 926, 240, 102, 654, 459, 51,
4226    686, 754, 806, 760, 493, 403, 415, 394, 687, 700,
4227    946, 670, 656, 610, 738, 392, 760, 799, 887, 653,
4228    978, 321, 576, 617, 626, 502, 894, 679, 243, 440,
4229    680, 879, 194, 572, 640, 724, 926, 56, 204, 700,
4230    707, 151, 457, 449, 797, 195, 791, 558, 945, 679,
4231    297, 59, 87, 824, 713, 663, 412, 693, 342, 606,
4232    134, 108, 571, 364, 631, 212, 174, 643, 304, 329,
4233    343, 97, 430, 751, 497, 314, 983, 374, 822, 928,
4234    140, 206, 73, 263, 980, 736, 876, 478, 430, 305,
4235    170, 514, 364, 692, 829, 82, 855, 953, 676, 246,
4236    369, 970, 294, 750, 807, 827, 150, 790, 288, 923,
4237    804, 378, 215, 828, 592, 281, 565, 555, 710, 82,
4238    896, 831, 547, 261, 524, 462, 293, 465, 502, 56,
4239    661, 821, 976, 991, 658, 869, 905, 758, 745, 193,
4240    768, 550, 608, 933, 378, 286, 215, 979, 792, 961,
4241    61, 688, 793, 644, 986, 403, 106, 366, 905, 644,
4242    372, 567, 466, 434, 645, 210, 389, 550, 919, 135,
4243    780, 773, 635, 389, 707, 100, 626, 958, 165, 504,
4244    920, 176, 193, 713, 857, 265, 203, 50, 668, 108,
4245    645, 990, 626, 197, 510, 357, 358, 850, 858, 364,
4246    936, 638
4247 };
4248 
4249 
4250 /*-------------------------------------------------------------*/
4251 /*--- end                                       randtable.c ---*/
4252 /*-------------------------------------------------------------*/
4253 
4254 /*-------------------------------------------------------------*/
4255 /*--- Table for doing CRCs                                  ---*/
4256 /*---                                            crctable.c ---*/
4257 /*-------------------------------------------------------------*/
4258 
4259 /*--
4260   This file is a part of bzip2 and/or libbzip2, a program and
4261   library for lossless, block-sorting data compression.
4262 
4263   Copyright (C) 1996-2004 Julian R Seward.  All rights reserved.
4264 
4265   Redistribution and use in source and binary forms, with or without
4266   modification, are permitted provided that the following conditions
4267   are met:
4268 
4269   1. Redistributions of source code must retain the above copyright
4270      notice, this list of conditions and the following disclaimer.
4271 
4272   2. The origin of this software must not be misrepresented; you must
4273      not claim that you wrote the original software.  If you use this
4274      software in a product, an acknowledgment in the product
4275      documentation would be appreciated but is not required.
4276 
4277   3. Altered source versions must be plainly marked as such, and must
4278      not be misrepresented as being the original software.
4279 
4280   4. The name of the author may not be used to endorse or promote
4281      products derived from this software without specific prior written
4282      permission.
4283 
4284   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
4285   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
4286   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
4287   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
4288   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
4289   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
4290   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
4291   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
4292   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
4293   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
4294   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
4295 
4296   Julian Seward, Cambridge, UK.
4297   jseward@bzip.org
4298   bzip2/libbzip2 version 1.0 of 21 March 2000
4299 
4300   This program is based on (at least) the work of:
4301      Mike Burrows
4302      David Wheeler
4303      Peter Fenwick
4304      Alistair Moffat
4305      Radford Neal
4306      Ian H. Witten
4307      Robert Sedgewick
4308      Jon L. Bentley
4309 
4310   For more information on these sources, see the manual.
4311 --*/
4312 
4313 
4314 
4315 
4316 
4317 /*--
4318   I think this is an implementation of the AUTODIN-II,
4319   Ethernet & FDDI 32-bit CRC standard.  Vaguely derived
4320   from code by Rob Warnock, in Section 51 of the
4321   comp.compression FAQ.
4322 --*/
4323 
4324 UInt32 BZ2_crc32Table[256] = {
4325 
4326    /*-- Ugly, innit? --*/
4327 
4328    0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L,
4329    0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L,
4330    0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L,
4331    0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL,
4332    0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L,
4333    0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L,
4334    0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L,
4335    0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL,
4336    0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L,
4337    0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L,
4338    0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L,
4339    0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL,
4340    0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L,
4341    0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L,
4342    0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L,
4343    0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL,
4344    0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL,
4345    0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L,
4346    0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L,
4347    0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL,
4348    0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL,
4349    0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L,
4350    0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L,
4351    0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL,
4352    0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL,
4353    0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L,
4354    0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L,
4355    0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL,
4356    0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL,
4357    0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L,
4358    0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L,
4359    0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL,
4360    0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L,
4361    0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL,
4362    0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL,
4363    0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L,
4364    0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L,
4365    0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL,
4366    0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL,
4367    0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L,
4368    0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L,
4369    0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL,
4370    0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL,
4371    0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L,
4372    0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L,
4373    0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL,
4374    0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL,
4375    0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L,
4376    0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L,
4377    0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL,
4378    0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L,
4379    0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L,
4380    0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L,
4381    0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL,
4382    0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L,
4383    0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L,
4384    0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L,
4385    0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL,
4386    0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L,
4387    0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L,
4388    0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L,
4389    0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL,
4390    0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L,
4391    0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L
4392 };
4393 
4394 
4395 /*-------------------------------------------------------------*/
4396 /*--- end                                        crctable.c ---*/
4397 /*-------------------------------------------------------------*/
4398 
4399 /*-------------------------------------------------------------*/
4400 /*--- Library top-level functions.                          ---*/
4401 /*---                                               bzlib.c ---*/
4402 /*-------------------------------------------------------------*/
4403 
4404 /*--
4405   This file is a part of bzip2 and/or libbzip2, a program and
4406   library for lossless, block-sorting data compression.
4407 
4408   Copyright (C) 1996-2004 Julian R Seward.  All rights reserved.
4409 
4410   Redistribution and use in source and binary forms, with or without
4411   modification, are permitted provided that the following conditions
4412   are met:
4413 
4414   1. Redistributions of source code must retain the above copyright
4415      notice, this list of conditions and the following disclaimer.
4416 
4417   2. The origin of this software must not be misrepresented; you must
4418      not claim that you wrote the original software.  If you use this
4419      software in a product, an acknowledgment in the product
4420      documentation would be appreciated but is not required.
4421 
4422   3. Altered source versions must be plainly marked as such, and must
4423      not be misrepresented as being the original software.
4424 
4425   4. The name of the author may not be used to endorse or promote
4426      products derived from this software without specific prior written
4427      permission.
4428 
4429   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
4430   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
4431   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
4432   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
4433   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
4434   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
4435   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
4436   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
4437   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
4438   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
4439   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
4440 
4441   Julian Seward, Cambridge, UK.
4442   jseward@bzip.org
4443   bzip2/libbzip2 version 1.0 of 21 March 2000
4444 
4445   This program is based on (at least) the work of:
4446      Mike Burrows
4447      David Wheeler
4448      Peter Fenwick
4449      Alistair Moffat
4450      Radford Neal
4451      Ian H. Witten
4452      Robert Sedgewick
4453      Jon L. Bentley
4454 
4455   For more information on these sources, see the manual.
4456 --*/
4457 
4458 /*--
4459    CHANGES
4460    ~~~~~~~
4461    0.9.0 -- original version.
4462 
4463    0.9.0a/b -- no changes in this file.
4464 
4465    0.9.0c
4466       * made zero-length BZ_FLUSH work correctly in bzCompress().
4467       * fixed bzWrite/bzRead to ignore zero-length requests.
4468       * fixed bzread to correctly handle read requests after EOF.
4469       * wrong parameter order in call to bzDecompressInit in
4470         bzBuffToBuffDecompress.  Fixed.
4471 --*/
4472 
4473 
4474 
4475 /*---------------------------------------------------*/
4476 /*--- Compression stuff                           ---*/
4477 /*---------------------------------------------------*/
4478 
4479 
4480 /*---------------------------------------------------*/
BZ2_bz__AssertH__fail(int errcode)4481 void BZ2_bz__AssertH__fail ( int errcode )
4482 {
4483    vex_printf("BZ2_bz__AssertH__fail(%d) called, exiting\n", errcode);
4484    (*serviceFn)(0,0);
4485 }
4486 
bz_internal_error(int errcode)4487 void bz_internal_error ( int errcode )
4488 {
4489    vex_printf("bz_internal_error called, exiting\n", errcode);
4490    (*serviceFn)(0,0);
4491 }
4492 
4493 /*---------------------------------------------------*/
4494 static
bz_config_ok(void)4495 int bz_config_ok ( void )
4496 {
4497    if (sizeof(int)   != 4) return 0;
4498    if (sizeof(short) != 2) return 0;
4499    if (sizeof(char)  != 1) return 0;
4500    return 1;
4501 }
4502 
4503 
4504 /*---------------------------------------------------*/
4505 static
default_bzalloc(void * opaque,Int32 items,Int32 size)4506 void* default_bzalloc ( void* opaque, Int32 items, Int32 size )
4507 {
4508    void* v = (void*) (*serviceFn)(2, items * size );
4509    return v;
4510 }
4511 
4512 static
default_bzfree(void * opaque,void * addr)4513 void default_bzfree ( void* opaque, void* addr )
4514 {
4515    if (addr != NULL) (*serviceFn)( 3, (HWord)addr );
4516 }
4517 
4518 
4519 /*---------------------------------------------------*/
4520 static
prepare_new_block(EState * s)4521 void prepare_new_block ( EState* s )
4522 {
4523    Int32 i;
4524    s->nblock = 0;
4525    s->numZ = 0;
4526    s->state_out_pos = 0;
4527    BZ_INITIALISE_CRC ( s->blockCRC );
4528    for (i = 0; i < 256; i++) s->inUse[i] = False;
4529    s->blockNo++;
4530 }
4531 
4532 
4533 /*---------------------------------------------------*/
4534 static
init_RL(EState * s)4535 void init_RL ( EState* s )
4536 {
4537    s->state_in_ch  = 256;
4538    s->state_in_len = 0;
4539 }
4540 
4541 
4542 static
isempty_RL(EState * s)4543 Bool isempty_RL ( EState* s )
4544 {
4545    if (s->state_in_ch < 256 && s->state_in_len > 0)
4546       return False; else
4547       return True;
4548 }
4549 
4550 
4551 /*---------------------------------------------------*/
BZ_API(BZ2_bzCompressInit)4552 int BZ_API(BZ2_bzCompressInit)
4553                     ( bz_stream* strm,
4554                      int        blockSize100k,
4555                      int        verbosity,
4556                      int        workFactor )
4557 {
4558    Int32   n;
4559    EState* s;
4560 
4561    if (!bz_config_ok()) return BZ_CONFIG_ERROR;
4562 
4563    if (strm == NULL ||
4564        blockSize100k < 1 || blockSize100k > 9 ||
4565        workFactor < 0 || workFactor > 250)
4566      return BZ_PARAM_ERROR;
4567 
4568    if (workFactor == 0) workFactor = 30;
4569    if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc;
4570    if (strm->bzfree == NULL) strm->bzfree = default_bzfree;
4571 
4572    s = BZALLOC( sizeof(EState) );
4573    if (s == NULL) return BZ_MEM_ERROR;
4574    s->strm = strm;
4575 
4576    s->arr1 = NULL;
4577    s->arr2 = NULL;
4578    s->ftab = NULL;
4579 
4580    n       = 100000 * blockSize100k;
4581    s->arr1 = BZALLOC( n                  * sizeof(UInt32) );
4582    s->arr2 = BZALLOC( (n+BZ_N_OVERSHOOT) * sizeof(UInt32) );
4583    s->ftab = BZALLOC( 65537              * sizeof(UInt32) );
4584 
4585    if (s->arr1 == NULL || s->arr2 == NULL || s->ftab == NULL) {
4586       if (s->arr1 != NULL) BZFREE(s->arr1);
4587       if (s->arr2 != NULL) BZFREE(s->arr2);
4588       if (s->ftab != NULL) BZFREE(s->ftab);
4589       if (s       != NULL) BZFREE(s);
4590       return BZ_MEM_ERROR;
4591    }
4592 
4593    s->blockNo           = 0;
4594    s->state             = BZ_S_INPUT;
4595    s->mode              = BZ_M_RUNNING;
4596    s->combinedCRC       = 0;
4597    s->blockSize100k     = blockSize100k;
4598    s->nblockMAX         = 100000 * blockSize100k - 19;
4599    s->verbosity         = verbosity;
4600    s->workFactor        = workFactor;
4601 
4602    s->block             = (UChar*)s->arr2;
4603    s->mtfv              = (UInt16*)s->arr1;
4604    s->zbits             = NULL;
4605    s->ptr               = (UInt32*)s->arr1;
4606 
4607    strm->state          = s;
4608    strm->total_in_lo32  = 0;
4609    strm->total_in_hi32  = 0;
4610    strm->total_out_lo32 = 0;
4611    strm->total_out_hi32 = 0;
4612    init_RL ( s );
4613    prepare_new_block ( s );
4614    return BZ_OK;
4615 }
4616 
4617 
4618 /*---------------------------------------------------*/
4619 static
add_pair_to_block(EState * s)4620 void add_pair_to_block ( EState* s )
4621 {
4622    Int32 i;
4623    UChar ch = (UChar)(s->state_in_ch);
4624    for (i = 0; i < s->state_in_len; i++) {
4625       BZ_UPDATE_CRC( s->blockCRC, ch );
4626    }
4627    s->inUse[s->state_in_ch] = True;
4628    switch (s->state_in_len) {
4629       case 1:
4630          s->block[s->nblock] = (UChar)ch; s->nblock++;
4631          break;
4632       case 2:
4633          s->block[s->nblock] = (UChar)ch; s->nblock++;
4634          s->block[s->nblock] = (UChar)ch; s->nblock++;
4635          break;
4636       case 3:
4637          s->block[s->nblock] = (UChar)ch; s->nblock++;
4638          s->block[s->nblock] = (UChar)ch; s->nblock++;
4639          s->block[s->nblock] = (UChar)ch; s->nblock++;
4640          break;
4641       default:
4642          s->inUse[s->state_in_len-4] = True;
4643          s->block[s->nblock] = (UChar)ch; s->nblock++;
4644          s->block[s->nblock] = (UChar)ch; s->nblock++;
4645          s->block[s->nblock] = (UChar)ch; s->nblock++;
4646          s->block[s->nblock] = (UChar)ch; s->nblock++;
4647          s->block[s->nblock] = ((UChar)(s->state_in_len-4));
4648          s->nblock++;
4649          break;
4650    }
4651 }
4652 
4653 
4654 /*---------------------------------------------------*/
4655 static
flush_RL(EState * s)4656 void flush_RL ( EState* s )
4657 {
4658    if (s->state_in_ch < 256) add_pair_to_block ( s );
4659    init_RL ( s );
4660 }
4661 
4662 
4663 /*---------------------------------------------------*/
4664 #define ADD_CHAR_TO_BLOCK(zs,zchh0)               \
4665 {                                                 \
4666    UInt32 zchh = (UInt32)(zchh0);                 \
4667    /*-- fast track the common case --*/           \
4668    if (zchh != zs->state_in_ch &&                 \
4669        zs->state_in_len == 1) {                   \
4670       UChar ch = (UChar)(zs->state_in_ch);        \
4671       BZ_UPDATE_CRC( zs->blockCRC, ch );          \
4672       zs->inUse[zs->state_in_ch] = True;          \
4673       zs->block[zs->nblock] = (UChar)ch;          \
4674       zs->nblock++;                               \
4675       zs->state_in_ch = zchh;                     \
4676    }                                              \
4677    else                                           \
4678    /*-- general, uncommon cases --*/              \
4679    if (zchh != zs->state_in_ch ||                 \
4680       zs->state_in_len == 255) {                  \
4681       if (zs->state_in_ch < 256)                  \
4682          add_pair_to_block ( zs );                \
4683       zs->state_in_ch = zchh;                     \
4684       zs->state_in_len = 1;                       \
4685    } else {                                       \
4686       zs->state_in_len++;                         \
4687    }                                              \
4688 }
4689 
4690 
4691 /*---------------------------------------------------*/
4692 static
copy_input_until_stop(EState * s)4693 Bool copy_input_until_stop ( EState* s )
4694 {
4695    Bool progress_in = False;
4696 
4697    if (s->mode == BZ_M_RUNNING) {
4698 
4699       /*-- fast track the common case --*/
4700       while (True) {
4701          /*-- block full? --*/
4702          if (s->nblock >= s->nblockMAX) break;
4703          /*-- no input? --*/
4704          if (s->strm->avail_in == 0) break;
4705          progress_in = True;
4706          ADD_CHAR_TO_BLOCK ( s, (UInt32)(*((UChar*)(s->strm->next_in))) );
4707          s->strm->next_in++;
4708          s->strm->avail_in--;
4709          s->strm->total_in_lo32++;
4710          if (s->strm->total_in_lo32 == 0) s->strm->total_in_hi32++;
4711       }
4712 
4713    } else {
4714 
4715       /*-- general, uncommon case --*/
4716       while (True) {
4717          /*-- block full? --*/
4718          if (s->nblock >= s->nblockMAX) break;
4719          /*-- no input? --*/
4720          if (s->strm->avail_in == 0) break;
4721          /*-- flush/finish end? --*/
4722          if (s->avail_in_expect == 0) break;
4723          progress_in = True;
4724          ADD_CHAR_TO_BLOCK ( s, (UInt32)(*((UChar*)(s->strm->next_in))) );
4725          s->strm->next_in++;
4726          s->strm->avail_in--;
4727          s->strm->total_in_lo32++;
4728          if (s->strm->total_in_lo32 == 0) s->strm->total_in_hi32++;
4729          s->avail_in_expect--;
4730       }
4731    }
4732    return progress_in;
4733 }
4734 
4735 
4736 /*---------------------------------------------------*/
4737 static
copy_output_until_stop(EState * s)4738 Bool copy_output_until_stop ( EState* s )
4739 {
4740    Bool progress_out = False;
4741 
4742    while (True) {
4743 
4744       /*-- no output space? --*/
4745       if (s->strm->avail_out == 0) break;
4746 
4747       /*-- block done? --*/
4748       if (s->state_out_pos >= s->numZ) break;
4749 
4750       progress_out = True;
4751       *(s->strm->next_out) = s->zbits[s->state_out_pos];
4752       s->state_out_pos++;
4753       s->strm->avail_out--;
4754       s->strm->next_out++;
4755       s->strm->total_out_lo32++;
4756       if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
4757    }
4758 
4759    return progress_out;
4760 }
4761 
4762 
4763 /*---------------------------------------------------*/
4764 static
handle_compress(bz_stream * strm)4765 Bool handle_compress ( bz_stream* strm )
4766 {
4767    Bool progress_in  = False;
4768    Bool progress_out = False;
4769    EState* s = strm->state;
4770 
4771    while (True) {
4772 
4773       if (s->state == BZ_S_OUTPUT) {
4774          progress_out |= copy_output_until_stop ( s );
4775          if (s->state_out_pos < s->numZ) break;
4776          if (s->mode == BZ_M_FINISHING &&
4777              s->avail_in_expect == 0 &&
4778              isempty_RL(s)) break;
4779          prepare_new_block ( s );
4780          s->state = BZ_S_INPUT;
4781          if (s->mode == BZ_M_FLUSHING &&
4782              s->avail_in_expect == 0 &&
4783              isempty_RL(s)) break;
4784       }
4785 
4786       if (s->state == BZ_S_INPUT) {
4787          progress_in |= copy_input_until_stop ( s );
4788          if (s->mode != BZ_M_RUNNING && s->avail_in_expect == 0) {
4789             flush_RL ( s );
4790             BZ2_compressBlock ( s, (Bool)(s->mode == BZ_M_FINISHING) );
4791             s->state = BZ_S_OUTPUT;
4792          }
4793          else
4794          if (s->nblock >= s->nblockMAX) {
4795             BZ2_compressBlock ( s, False );
4796             s->state = BZ_S_OUTPUT;
4797          }
4798          else
4799          if (s->strm->avail_in == 0) {
4800             break;
4801          }
4802       }
4803 
4804    }
4805 
4806    return progress_in || progress_out;
4807 }
4808 
4809 
4810 /*---------------------------------------------------*/
BZ_API(BZ2_bzCompress)4811 int BZ_API(BZ2_bzCompress) ( bz_stream *strm, int action )
4812 {
4813    Bool progress;
4814    EState* s;
4815    if (strm == NULL) return BZ_PARAM_ERROR;
4816    s = strm->state;
4817    if (s == NULL) return BZ_PARAM_ERROR;
4818    if (s->strm != strm) return BZ_PARAM_ERROR;
4819 
4820    preswitch:
4821    switch (s->mode) {
4822 
4823       case BZ_M_IDLE:
4824          return BZ_SEQUENCE_ERROR;
4825 
4826       case BZ_M_RUNNING:
4827          if (action == BZ_RUN) {
4828             progress = handle_compress ( strm );
4829             return progress ? BZ_RUN_OK : BZ_PARAM_ERROR;
4830          }
4831          else
4832 	 if (action == BZ_FLUSH) {
4833             s->avail_in_expect = strm->avail_in;
4834             s->mode = BZ_M_FLUSHING;
4835             goto preswitch;
4836          }
4837          else
4838          if (action == BZ_FINISH) {
4839             s->avail_in_expect = strm->avail_in;
4840             s->mode = BZ_M_FINISHING;
4841             goto preswitch;
4842          }
4843          else
4844             return BZ_PARAM_ERROR;
4845 
4846       case BZ_M_FLUSHING:
4847          if (action != BZ_FLUSH) return BZ_SEQUENCE_ERROR;
4848          if (s->avail_in_expect != s->strm->avail_in)
4849             return BZ_SEQUENCE_ERROR;
4850          progress = handle_compress ( strm );
4851          if (s->avail_in_expect > 0 || !isempty_RL(s) ||
4852              s->state_out_pos < s->numZ) return BZ_FLUSH_OK;
4853          s->mode = BZ_M_RUNNING;
4854          return BZ_RUN_OK;
4855 
4856       case BZ_M_FINISHING:
4857          if (action != BZ_FINISH) return BZ_SEQUENCE_ERROR;
4858          if (s->avail_in_expect != s->strm->avail_in)
4859             return BZ_SEQUENCE_ERROR;
4860          progress = handle_compress ( strm );
4861          if (!progress) return BZ_SEQUENCE_ERROR;
4862          if (s->avail_in_expect > 0 || !isempty_RL(s) ||
4863              s->state_out_pos < s->numZ) return BZ_FINISH_OK;
4864          s->mode = BZ_M_IDLE;
4865          return BZ_STREAM_END;
4866    }
4867    return BZ_OK; /*--not reached--*/
4868 }
4869 
4870 
4871 /*---------------------------------------------------*/
BZ_API(BZ2_bzCompressEnd)4872 int BZ_API(BZ2_bzCompressEnd)  ( bz_stream *strm )
4873 {
4874    EState* s;
4875    if (strm == NULL) return BZ_PARAM_ERROR;
4876    s = strm->state;
4877    if (s == NULL) return BZ_PARAM_ERROR;
4878    if (s->strm != strm) return BZ_PARAM_ERROR;
4879 
4880    if (s->arr1 != NULL) BZFREE(s->arr1);
4881    if (s->arr2 != NULL) BZFREE(s->arr2);
4882    if (s->ftab != NULL) BZFREE(s->ftab);
4883    BZFREE(strm->state);
4884 
4885    strm->state = NULL;
4886 
4887    return BZ_OK;
4888 }
4889 
4890 
4891 /*---------------------------------------------------*/
4892 /*--- Decompression stuff                         ---*/
4893 /*---------------------------------------------------*/
4894 
4895 /*---------------------------------------------------*/
BZ_API(BZ2_bzDecompressInit)4896 int BZ_API(BZ2_bzDecompressInit)
4897                      ( bz_stream* strm,
4898                        int        verbosity,
4899                        int        small )
4900 {
4901    DState* s;
4902 
4903    if (!bz_config_ok()) return BZ_CONFIG_ERROR;
4904 
4905    if (strm == NULL) return BZ_PARAM_ERROR;
4906    if (small != 0 && small != 1) return BZ_PARAM_ERROR;
4907    if (verbosity < 0 || verbosity > 4) return BZ_PARAM_ERROR;
4908 
4909    if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc;
4910    if (strm->bzfree == NULL) strm->bzfree = default_bzfree;
4911 
4912    s = BZALLOC( sizeof(DState) );
4913    if (s == NULL) return BZ_MEM_ERROR;
4914    s->strm                  = strm;
4915    strm->state              = s;
4916    s->state                 = BZ_X_MAGIC_1;
4917    s->bsLive                = 0;
4918    s->bsBuff                = 0;
4919    s->calculatedCombinedCRC = 0;
4920    strm->total_in_lo32      = 0;
4921    strm->total_in_hi32      = 0;
4922    strm->total_out_lo32     = 0;
4923    strm->total_out_hi32     = 0;
4924    s->smallDecompress       = (Bool)small;
4925    s->ll4                   = NULL;
4926    s->ll16                  = NULL;
4927    s->tt                    = NULL;
4928    s->currBlockNo           = 0;
4929    s->verbosity             = verbosity;
4930 
4931    return BZ_OK;
4932 }
4933 
4934 
4935 /*---------------------------------------------------*/
4936 /* Return  True iff data corruption is discovered.
4937    Returns False if there is no problem.
4938 */
4939 static
unRLE_obuf_to_output_FAST(DState * s)4940 Bool unRLE_obuf_to_output_FAST ( DState* s )
4941 {
4942    UChar k1;
4943 
4944    if (s->blockRandomised) {
4945 
4946       while (True) {
4947          /* try to finish existing run */
4948          while (True) {
4949             if (s->strm->avail_out == 0) return False;
4950             if (s->state_out_len == 0) break;
4951             *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
4952             BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
4953             s->state_out_len--;
4954             s->strm->next_out++;
4955             s->strm->avail_out--;
4956             s->strm->total_out_lo32++;
4957             if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
4958          }
4959 
4960          /* can a new run be started? */
4961          if (s->nblock_used == s->save_nblock+1) return False;
4962 
4963          /* Only caused by corrupt data stream? */
4964          if (s->nblock_used > s->save_nblock+1)
4965             return True;
4966 
4967          s->state_out_len = 1;
4968          s->state_out_ch = s->k0;
4969          BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
4970          k1 ^= BZ_RAND_MASK; s->nblock_used++;
4971          if (s->nblock_used == s->save_nblock+1) continue;
4972          if (k1 != s->k0) { s->k0 = k1; continue; };
4973 
4974          s->state_out_len = 2;
4975          BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
4976          k1 ^= BZ_RAND_MASK; s->nblock_used++;
4977          if (s->nblock_used == s->save_nblock+1) continue;
4978          if (k1 != s->k0) { s->k0 = k1; continue; };
4979 
4980          s->state_out_len = 3;
4981          BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
4982          k1 ^= BZ_RAND_MASK; s->nblock_used++;
4983          if (s->nblock_used == s->save_nblock+1) continue;
4984          if (k1 != s->k0) { s->k0 = k1; continue; };
4985 
4986          BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
4987          k1 ^= BZ_RAND_MASK; s->nblock_used++;
4988          s->state_out_len = ((Int32)k1) + 4;
4989          BZ_GET_FAST(s->k0); BZ_RAND_UPD_MASK;
4990          s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
4991       }
4992 
4993    } else {
4994 
4995       /* restore */
4996       UInt32        c_calculatedBlockCRC = s->calculatedBlockCRC;
4997       UChar         c_state_out_ch       = s->state_out_ch;
4998       Int32         c_state_out_len      = s->state_out_len;
4999       Int32         c_nblock_used        = s->nblock_used;
5000       Int32         c_k0                 = s->k0;
5001       UInt32*       c_tt                 = s->tt;
5002       UInt32        c_tPos               = s->tPos;
5003       char*         cs_next_out          = s->strm->next_out;
5004       unsigned int  cs_avail_out         = s->strm->avail_out;
5005       /* end restore */
5006 
5007       UInt32       avail_out_INIT = cs_avail_out;
5008       Int32        s_save_nblockPP = s->save_nblock+1;
5009       unsigned int total_out_lo32_old;
5010 
5011       while (True) {
5012 
5013          /* try to finish existing run */
5014          if (c_state_out_len > 0) {
5015             while (True) {
5016                if (cs_avail_out == 0) goto return_notr;
5017                if (c_state_out_len == 1) break;
5018                *( (UChar*)(cs_next_out) ) = c_state_out_ch;
5019                BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
5020                c_state_out_len--;
5021                cs_next_out++;
5022                cs_avail_out--;
5023             }
5024             s_state_out_len_eq_one:
5025             {
5026                if (cs_avail_out == 0) {
5027                   c_state_out_len = 1; goto return_notr;
5028                };
5029                *( (UChar*)(cs_next_out) ) = c_state_out_ch;
5030                BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
5031                cs_next_out++;
5032                cs_avail_out--;
5033             }
5034          }
5035          /* Only caused by corrupt data stream? */
5036          if (c_nblock_used > s_save_nblockPP)
5037             return True;
5038 
5039          /* can a new run be started? */
5040          if (c_nblock_used == s_save_nblockPP) {
5041             c_state_out_len = 0; goto return_notr;
5042          };
5043          c_state_out_ch = c_k0;
5044          BZ_GET_FAST_C(k1); c_nblock_used++;
5045          if (k1 != c_k0) {
5046             c_k0 = k1; goto s_state_out_len_eq_one;
5047          };
5048          if (c_nblock_used == s_save_nblockPP)
5049             goto s_state_out_len_eq_one;
5050 
5051          c_state_out_len = 2;
5052          BZ_GET_FAST_C(k1); c_nblock_used++;
5053          if (c_nblock_used == s_save_nblockPP) continue;
5054          if (k1 != c_k0) { c_k0 = k1; continue; };
5055 
5056          c_state_out_len = 3;
5057          BZ_GET_FAST_C(k1); c_nblock_used++;
5058          if (c_nblock_used == s_save_nblockPP) continue;
5059          if (k1 != c_k0) { c_k0 = k1; continue; };
5060 
5061          BZ_GET_FAST_C(k1); c_nblock_used++;
5062          c_state_out_len = ((Int32)k1) + 4;
5063          BZ_GET_FAST_C(c_k0); c_nblock_used++;
5064       }
5065 
5066       return_notr:
5067       total_out_lo32_old = s->strm->total_out_lo32;
5068       s->strm->total_out_lo32 += (avail_out_INIT - cs_avail_out);
5069       if (s->strm->total_out_lo32 < total_out_lo32_old)
5070          s->strm->total_out_hi32++;
5071 
5072       /* save */
5073       s->calculatedBlockCRC = c_calculatedBlockCRC;
5074       s->state_out_ch       = c_state_out_ch;
5075       s->state_out_len      = c_state_out_len;
5076       s->nblock_used        = c_nblock_used;
5077       s->k0                 = c_k0;
5078       s->tt                 = c_tt;
5079       s->tPos               = c_tPos;
5080       s->strm->next_out     = cs_next_out;
5081       s->strm->avail_out    = cs_avail_out;
5082       /* end save */
5083    }
5084    return False;
5085 }
5086 
5087 
5088 
5089 /*---------------------------------------------------*/
5090 /* Return  True iff data corruption is discovered.
5091    Returns False if there is no problem.
5092 */
5093 static
unRLE_obuf_to_output_SMALL(DState * s)5094 Bool unRLE_obuf_to_output_SMALL ( DState* s )
5095 {
5096    UChar k1;
5097 
5098    if (s->blockRandomised) {
5099 
5100       while (True) {
5101          /* try to finish existing run */
5102          while (True) {
5103             if (s->strm->avail_out == 0) return False;
5104             if (s->state_out_len == 0) break;
5105             *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
5106             BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
5107             s->state_out_len--;
5108             s->strm->next_out++;
5109             s->strm->avail_out--;
5110             s->strm->total_out_lo32++;
5111             if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
5112          }
5113 
5114          /* can a new run be started? */
5115          if (s->nblock_used == s->save_nblock+1) return False;
5116 
5117          /* Only caused by corrupt data stream? */
5118          if (s->nblock_used > s->save_nblock+1)
5119             return True;
5120 
5121          s->state_out_len = 1;
5122          s->state_out_ch = s->k0;
5123          BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
5124          k1 ^= BZ_RAND_MASK; s->nblock_used++;
5125          if (s->nblock_used == s->save_nblock+1) continue;
5126          if (k1 != s->k0) { s->k0 = k1; continue; };
5127 
5128          s->state_out_len = 2;
5129          BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
5130          k1 ^= BZ_RAND_MASK; s->nblock_used++;
5131          if (s->nblock_used == s->save_nblock+1) continue;
5132          if (k1 != s->k0) { s->k0 = k1; continue; };
5133 
5134          s->state_out_len = 3;
5135          BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
5136          k1 ^= BZ_RAND_MASK; s->nblock_used++;
5137          if (s->nblock_used == s->save_nblock+1) continue;
5138          if (k1 != s->k0) { s->k0 = k1; continue; };
5139 
5140          BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
5141          k1 ^= BZ_RAND_MASK; s->nblock_used++;
5142          s->state_out_len = ((Int32)k1) + 4;
5143          BZ_GET_SMALL(s->k0); BZ_RAND_UPD_MASK;
5144          s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
5145       }
5146 
5147    } else {
5148 
5149       while (True) {
5150          /* try to finish existing run */
5151          while (True) {
5152             if (s->strm->avail_out == 0) return False;
5153             if (s->state_out_len == 0) break;
5154             *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
5155             BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
5156             s->state_out_len--;
5157             s->strm->next_out++;
5158             s->strm->avail_out--;
5159             s->strm->total_out_lo32++;
5160             if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
5161          }
5162 
5163          /* can a new run be started? */
5164          if (s->nblock_used == s->save_nblock+1) return False;
5165 
5166          /* Only caused by corrupt data stream? */
5167          if (s->nblock_used > s->save_nblock+1)
5168             return True;
5169 
5170          s->state_out_len = 1;
5171          s->state_out_ch = s->k0;
5172          BZ_GET_SMALL(k1); s->nblock_used++;
5173          if (s->nblock_used == s->save_nblock+1) continue;
5174          if (k1 != s->k0) { s->k0 = k1; continue; };
5175 
5176          s->state_out_len = 2;
5177          BZ_GET_SMALL(k1); s->nblock_used++;
5178          if (s->nblock_used == s->save_nblock+1) continue;
5179          if (k1 != s->k0) { s->k0 = k1; continue; };
5180 
5181          s->state_out_len = 3;
5182          BZ_GET_SMALL(k1); s->nblock_used++;
5183          if (s->nblock_used == s->save_nblock+1) continue;
5184          if (k1 != s->k0) { s->k0 = k1; continue; };
5185 
5186          BZ_GET_SMALL(k1); s->nblock_used++;
5187          s->state_out_len = ((Int32)k1) + 4;
5188          BZ_GET_SMALL(s->k0); s->nblock_used++;
5189       }
5190 
5191    }
5192 }
5193 
5194 
5195 /*---------------------------------------------------*/
BZ_API(BZ2_bzDecompress)5196 int BZ_API(BZ2_bzDecompress) ( bz_stream *strm )
5197 {
5198    Bool    corrupt;
5199    DState* s;
5200    if (strm == NULL) return BZ_PARAM_ERROR;
5201    s = strm->state;
5202    if (s == NULL) return BZ_PARAM_ERROR;
5203    if (s->strm != strm) return BZ_PARAM_ERROR;
5204 
5205    while (True) {
5206       if (s->state == BZ_X_IDLE) return BZ_SEQUENCE_ERROR;
5207       if (s->state == BZ_X_OUTPUT) {
5208          if (s->smallDecompress)
5209             corrupt = unRLE_obuf_to_output_SMALL ( s ); else
5210             corrupt = unRLE_obuf_to_output_FAST  ( s );
5211          if (corrupt) return BZ_DATA_ERROR;
5212          if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) {
5213             BZ_FINALISE_CRC ( s->calculatedBlockCRC );
5214             if (s->verbosity >= 3)
5215                VPrintf2 ( " {0x%08x, 0x%08x}", s->storedBlockCRC,
5216                           s->calculatedBlockCRC );
5217             if (s->verbosity >= 2) VPrintf0 ( "]" );
5218             if (s->calculatedBlockCRC != s->storedBlockCRC)
5219                return BZ_DATA_ERROR;
5220             s->calculatedCombinedCRC
5221                = (s->calculatedCombinedCRC << 1) |
5222                     (s->calculatedCombinedCRC >> 31);
5223             s->calculatedCombinedCRC ^= s->calculatedBlockCRC;
5224             s->state = BZ_X_BLKHDR_1;
5225          } else {
5226             return BZ_OK;
5227          }
5228       }
5229       if (s->state >= BZ_X_MAGIC_1) {
5230          Int32 r = BZ2_decompress ( s );
5231          if (r == BZ_STREAM_END) {
5232             if (s->verbosity >= 3)
5233                VPrintf2 ( "\n    combined CRCs: stored = 0x%08x, computed = 0x%08x",
5234                           s->storedCombinedCRC, s->calculatedCombinedCRC );
5235             if (s->calculatedCombinedCRC != s->storedCombinedCRC)
5236                return BZ_DATA_ERROR;
5237             return r;
5238          }
5239          if (s->state != BZ_X_OUTPUT) return r;
5240       }
5241    }
5242 
5243    AssertH ( 0, 6001 );
5244 
5245    return 0;  /*NOTREACHED*/
5246 }
5247 
5248 
5249 /*---------------------------------------------------*/
BZ_API(BZ2_bzDecompressEnd)5250 int BZ_API(BZ2_bzDecompressEnd)  ( bz_stream *strm )
5251 {
5252    DState* s;
5253    if (strm == NULL) return BZ_PARAM_ERROR;
5254    s = strm->state;
5255    if (s == NULL) return BZ_PARAM_ERROR;
5256    if (s->strm != strm) return BZ_PARAM_ERROR;
5257 
5258    if (s->tt   != NULL) BZFREE(s->tt);
5259    if (s->ll16 != NULL) BZFREE(s->ll16);
5260    if (s->ll4  != NULL) BZFREE(s->ll4);
5261 
5262    BZFREE(strm->state);
5263    strm->state = NULL;
5264 
5265    return BZ_OK;
5266 }
5267 
5268 
5269 #ifndef BZ_NO_STDIO
5270 /*---------------------------------------------------*/
5271 /*--- File I/O stuff                              ---*/
5272 /*---------------------------------------------------*/
5273 
5274 #define BZ_SETERR(eee)                    \
5275 {                                         \
5276    if (bzerror != NULL) *bzerror = eee;   \
5277    if (bzf != NULL) bzf->lastErr = eee;   \
5278 }
5279 
5280 typedef
5281    struct {
5282       FILE*     handle;
5283       Char      buf[BZ_MAX_UNUSED];
5284       Int32     bufN;
5285       Bool      writing;
5286       bz_stream strm;
5287       Int32     lastErr;
5288       Bool      initialisedOk;
5289    }
5290    bzFile;
5291 
5292 
5293 /*---------------------------------------------*/
myfeof(FILE * f)5294 static Bool myfeof ( FILE* f )
5295 {
5296    Int32 c = fgetc ( f );
5297    if (c == EOF) return True;
5298    ungetc ( c, f );
5299    return False;
5300 }
5301 
5302 
5303 /*---------------------------------------------------*/
BZ_API(BZ2_bzWriteOpen)5304 BZFILE* BZ_API(BZ2_bzWriteOpen)
5305                     ( int*  bzerror,
5306                       FILE* f,
5307                       int   blockSize100k,
5308                       int   verbosity,
5309                       int   workFactor )
5310 {
5311    Int32   ret;
5312    bzFile* bzf = NULL;
5313 
5314    BZ_SETERR(BZ_OK);
5315 
5316    if (f == NULL ||
5317        (blockSize100k < 1 || blockSize100k > 9) ||
5318        (workFactor < 0 || workFactor > 250) ||
5319        (verbosity < 0 || verbosity > 4))
5320       { BZ_SETERR(BZ_PARAM_ERROR); return NULL; };
5321 
5322    if (ferror(f))
5323       { BZ_SETERR(BZ_IO_ERROR); return NULL; };
5324 
5325    bzf = malloc ( sizeof(bzFile) );
5326    if (bzf == NULL)
5327       { BZ_SETERR(BZ_MEM_ERROR); return NULL; };
5328 
5329    BZ_SETERR(BZ_OK);
5330    bzf->initialisedOk = False;
5331    bzf->bufN          = 0;
5332    bzf->handle        = f;
5333    bzf->writing       = True;
5334    bzf->strm.bzalloc  = NULL;
5335    bzf->strm.bzfree   = NULL;
5336    bzf->strm.opaque   = NULL;
5337 
5338    if (workFactor == 0) workFactor = 30;
5339    ret = BZ2_bzCompressInit ( &(bzf->strm), blockSize100k,
5340                               verbosity, workFactor );
5341    if (ret != BZ_OK)
5342       { BZ_SETERR(ret); free(bzf); return NULL; };
5343 
5344    bzf->strm.avail_in = 0;
5345    bzf->initialisedOk = True;
5346    return bzf;
5347 }
5348 
5349 
5350 
5351 /*---------------------------------------------------*/
BZ_API(BZ2_bzWrite)5352 void BZ_API(BZ2_bzWrite)
5353              ( int*    bzerror,
5354                BZFILE* b,
5355                void*   buf,
5356                int     len )
5357 {
5358    Int32 n, n2, ret;
5359    bzFile* bzf = (bzFile*)b;
5360 
5361    BZ_SETERR(BZ_OK);
5362    if (bzf == NULL || buf == NULL || len < 0)
5363       { BZ_SETERR(BZ_PARAM_ERROR); return; };
5364    if (!(bzf->writing))
5365       { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };
5366    if (ferror(bzf->handle))
5367       { BZ_SETERR(BZ_IO_ERROR); return; };
5368 
5369    if (len == 0)
5370       { BZ_SETERR(BZ_OK); return; };
5371 
5372    bzf->strm.avail_in = len;
5373    bzf->strm.next_in  = buf;
5374 
5375    while (True) {
5376       bzf->strm.avail_out = BZ_MAX_UNUSED;
5377       bzf->strm.next_out = bzf->buf;
5378       ret = BZ2_bzCompress ( &(bzf->strm), BZ_RUN );
5379       if (ret != BZ_RUN_OK)
5380          { BZ_SETERR(ret); return; };
5381 
5382       if (bzf->strm.avail_out < BZ_MAX_UNUSED) {
5383          n = BZ_MAX_UNUSED - bzf->strm.avail_out;
5384          n2 = fwrite ( (void*)(bzf->buf), sizeof(UChar),
5385                        n, bzf->handle );
5386          if (n != n2 || ferror(bzf->handle))
5387             { BZ_SETERR(BZ_IO_ERROR); return; };
5388       }
5389 
5390       if (bzf->strm.avail_in == 0)
5391          { BZ_SETERR(BZ_OK); return; };
5392    }
5393 }
5394 
5395 
5396 /*---------------------------------------------------*/
BZ_API(BZ2_bzWriteClose)5397 void BZ_API(BZ2_bzWriteClose)
5398                   ( int*          bzerror,
5399                     BZFILE*       b,
5400                     int           abandon,
5401                     unsigned int* nbytes_in,
5402                     unsigned int* nbytes_out )
5403 {
5404    BZ2_bzWriteClose64 ( bzerror, b, abandon,
5405                         nbytes_in, NULL, nbytes_out, NULL );
5406 }
5407 
5408 
BZ_API(BZ2_bzWriteClose64)5409 void BZ_API(BZ2_bzWriteClose64)
5410                   ( int*          bzerror,
5411                     BZFILE*       b,
5412                     int           abandon,
5413                     unsigned int* nbytes_in_lo32,
5414                     unsigned int* nbytes_in_hi32,
5415                     unsigned int* nbytes_out_lo32,
5416                     unsigned int* nbytes_out_hi32 )
5417 {
5418    Int32   n, n2, ret;
5419    bzFile* bzf = (bzFile*)b;
5420 
5421    if (bzf == NULL)
5422       { BZ_SETERR(BZ_OK); return; };
5423    if (!(bzf->writing))
5424       { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };
5425    if (ferror(bzf->handle))
5426       { BZ_SETERR(BZ_IO_ERROR); return; };
5427 
5428    if (nbytes_in_lo32 != NULL) *nbytes_in_lo32 = 0;
5429    if (nbytes_in_hi32 != NULL) *nbytes_in_hi32 = 0;
5430    if (nbytes_out_lo32 != NULL) *nbytes_out_lo32 = 0;
5431    if (nbytes_out_hi32 != NULL) *nbytes_out_hi32 = 0;
5432 
5433    if ((!abandon) && bzf->lastErr == BZ_OK) {
5434       while (True) {
5435          bzf->strm.avail_out = BZ_MAX_UNUSED;
5436          bzf->strm.next_out = bzf->buf;
5437          ret = BZ2_bzCompress ( &(bzf->strm), BZ_FINISH );
5438          if (ret != BZ_FINISH_OK && ret != BZ_STREAM_END)
5439             { BZ_SETERR(ret); return; };
5440 
5441          if (bzf->strm.avail_out < BZ_MAX_UNUSED) {
5442             n = BZ_MAX_UNUSED - bzf->strm.avail_out;
5443             n2 = fwrite ( (void*)(bzf->buf), sizeof(UChar),
5444                           n, bzf->handle );
5445             if (n != n2 || ferror(bzf->handle))
5446                { BZ_SETERR(BZ_IO_ERROR); return; };
5447          }
5448 
5449          if (ret == BZ_STREAM_END) break;
5450       }
5451    }
5452 
5453    if ( !abandon && !ferror ( bzf->handle ) ) {
5454       fflush ( bzf->handle );
5455       if (ferror(bzf->handle))
5456          { BZ_SETERR(BZ_IO_ERROR); return; };
5457    }
5458 
5459    if (nbytes_in_lo32 != NULL)
5460       *nbytes_in_lo32 = bzf->strm.total_in_lo32;
5461    if (nbytes_in_hi32 != NULL)
5462       *nbytes_in_hi32 = bzf->strm.total_in_hi32;
5463    if (nbytes_out_lo32 != NULL)
5464       *nbytes_out_lo32 = bzf->strm.total_out_lo32;
5465    if (nbytes_out_hi32 != NULL)
5466       *nbytes_out_hi32 = bzf->strm.total_out_hi32;
5467 
5468    BZ_SETERR(BZ_OK);
5469    BZ2_bzCompressEnd ( &(bzf->strm) );
5470    free ( bzf );
5471 }
5472 
5473 
5474 /*---------------------------------------------------*/
BZ_API(BZ2_bzReadOpen)5475 BZFILE* BZ_API(BZ2_bzReadOpen)
5476                    ( int*  bzerror,
5477                      FILE* f,
5478                      int   verbosity,
5479                      int   small,
5480                      void* unused,
5481                      int   nUnused )
5482 {
5483    bzFile* bzf = NULL;
5484    int     ret;
5485 
5486    BZ_SETERR(BZ_OK);
5487 
5488    if (f == NULL ||
5489        (small != 0 && small != 1) ||
5490        (verbosity < 0 || verbosity > 4) ||
5491        (unused == NULL && nUnused != 0) ||
5492        (unused != NULL && (nUnused < 0 || nUnused > BZ_MAX_UNUSED)))
5493       { BZ_SETERR(BZ_PARAM_ERROR); return NULL; };
5494 
5495    if (ferror(f))
5496       { BZ_SETERR(BZ_IO_ERROR); return NULL; };
5497 
5498    bzf = malloc ( sizeof(bzFile) );
5499    if (bzf == NULL)
5500       { BZ_SETERR(BZ_MEM_ERROR); return NULL; };
5501 
5502    BZ_SETERR(BZ_OK);
5503 
5504    bzf->initialisedOk = False;
5505    bzf->handle        = f;
5506    bzf->bufN          = 0;
5507    bzf->writing       = False;
5508    bzf->strm.bzalloc  = NULL;
5509    bzf->strm.bzfree   = NULL;
5510    bzf->strm.opaque   = NULL;
5511 
5512    while (nUnused > 0) {
5513       bzf->buf[bzf->bufN] = *((UChar*)(unused)); bzf->bufN++;
5514       unused = ((void*)( 1 + ((UChar*)(unused))  ));
5515       nUnused--;
5516    }
5517 
5518    ret = BZ2_bzDecompressInit ( &(bzf->strm), verbosity, small );
5519    if (ret != BZ_OK)
5520       { BZ_SETERR(ret); free(bzf); return NULL; };
5521 
5522    bzf->strm.avail_in = bzf->bufN;
5523    bzf->strm.next_in  = bzf->buf;
5524 
5525    bzf->initialisedOk = True;
5526    return bzf;
5527 }
5528 
5529 
5530 /*---------------------------------------------------*/
BZ_API(BZ2_bzReadClose)5531 void BZ_API(BZ2_bzReadClose) ( int *bzerror, BZFILE *b )
5532 {
5533    bzFile* bzf = (bzFile*)b;
5534 
5535    BZ_SETERR(BZ_OK);
5536    if (bzf == NULL)
5537       { BZ_SETERR(BZ_OK); return; };
5538 
5539    if (bzf->writing)
5540       { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };
5541 
5542    if (bzf->initialisedOk)
5543       (void)BZ2_bzDecompressEnd ( &(bzf->strm) );
5544    free ( bzf );
5545 }
5546 
5547 
5548 /*---------------------------------------------------*/
BZ_API(BZ2_bzRead)5549 int BZ_API(BZ2_bzRead)
5550            ( int*    bzerror,
5551              BZFILE* b,
5552              void*   buf,
5553              int     len )
5554 {
5555    Int32   n, ret;
5556    bzFile* bzf = (bzFile*)b;
5557 
5558    BZ_SETERR(BZ_OK);
5559 
5560    if (bzf == NULL || buf == NULL || len < 0)
5561       { BZ_SETERR(BZ_PARAM_ERROR); return 0; };
5562 
5563    if (bzf->writing)
5564       { BZ_SETERR(BZ_SEQUENCE_ERROR); return 0; };
5565 
5566    if (len == 0)
5567       { BZ_SETERR(BZ_OK); return 0; };
5568 
5569    bzf->strm.avail_out = len;
5570    bzf->strm.next_out = buf;
5571 
5572    while (True) {
5573 
5574       if (ferror(bzf->handle))
5575          { BZ_SETERR(BZ_IO_ERROR); return 0; };
5576 
5577       if (bzf->strm.avail_in == 0 && !myfeof(bzf->handle)) {
5578          n = fread ( bzf->buf, sizeof(UChar),
5579                      BZ_MAX_UNUSED, bzf->handle );
5580          if (ferror(bzf->handle))
5581             { BZ_SETERR(BZ_IO_ERROR); return 0; };
5582          bzf->bufN = n;
5583          bzf->strm.avail_in = bzf->bufN;
5584          bzf->strm.next_in = bzf->buf;
5585       }
5586 
5587       ret = BZ2_bzDecompress ( &(bzf->strm) );
5588 
5589       if (ret != BZ_OK && ret != BZ_STREAM_END)
5590          { BZ_SETERR(ret); return 0; };
5591 
5592       if (ret == BZ_OK && myfeof(bzf->handle) &&
5593           bzf->strm.avail_in == 0 && bzf->strm.avail_out > 0)
5594          { BZ_SETERR(BZ_UNEXPECTED_EOF); return 0; };
5595 
5596       if (ret == BZ_STREAM_END)
5597          { BZ_SETERR(BZ_STREAM_END);
5598            return len - bzf->strm.avail_out; };
5599       if (bzf->strm.avail_out == 0)
5600          { BZ_SETERR(BZ_OK); return len; };
5601 
5602    }
5603 
5604    return 0; /*not reached*/
5605 }
5606 
5607 
5608 /*---------------------------------------------------*/
BZ_API(BZ2_bzReadGetUnused)5609 void BZ_API(BZ2_bzReadGetUnused)
5610                      ( int*    bzerror,
5611                        BZFILE* b,
5612                        void**  unused,
5613                        int*    nUnused )
5614 {
5615    bzFile* bzf = (bzFile*)b;
5616    if (bzf == NULL)
5617       { BZ_SETERR(BZ_PARAM_ERROR); return; };
5618    if (bzf->lastErr != BZ_STREAM_END)
5619       { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };
5620    if (unused == NULL || nUnused == NULL)
5621       { BZ_SETERR(BZ_PARAM_ERROR); return; };
5622 
5623    BZ_SETERR(BZ_OK);
5624    *nUnused = bzf->strm.avail_in;
5625    *unused = bzf->strm.next_in;
5626 }
5627 #endif
5628 
5629 
5630 /*---------------------------------------------------*/
5631 /*--- Misc convenience stuff                      ---*/
5632 /*---------------------------------------------------*/
5633 
5634 /*---------------------------------------------------*/
BZ_API(BZ2_bzBuffToBuffCompress)5635 int BZ_API(BZ2_bzBuffToBuffCompress)
5636                          ( char*         dest,
5637                            unsigned int* destLen,
5638                            char*         source,
5639                            unsigned int  sourceLen,
5640                            int           blockSize100k,
5641                            int           verbosity,
5642                            int           workFactor )
5643 {
5644    bz_stream strm;
5645    int ret;
5646 
5647    if (dest == NULL || destLen == NULL ||
5648        source == NULL ||
5649        blockSize100k < 1 || blockSize100k > 9 ||
5650        verbosity < 0 || verbosity > 4 ||
5651        workFactor < 0 || workFactor > 250)
5652       return BZ_PARAM_ERROR;
5653 
5654    if (workFactor == 0) workFactor = 30;
5655    strm.bzalloc = NULL;
5656    strm.bzfree = NULL;
5657    strm.opaque = NULL;
5658    ret = BZ2_bzCompressInit ( &strm, blockSize100k,
5659                               verbosity, workFactor );
5660    if (ret != BZ_OK) return ret;
5661 
5662    strm.next_in = source;
5663    strm.next_out = dest;
5664    strm.avail_in = sourceLen;
5665    strm.avail_out = *destLen;
5666 
5667    ret = BZ2_bzCompress ( &strm, BZ_FINISH );
5668    if (ret == BZ_FINISH_OK) goto output_overflow;
5669    if (ret != BZ_STREAM_END) goto errhandler;
5670 
5671    /* normal termination */
5672    *destLen -= strm.avail_out;
5673    BZ2_bzCompressEnd ( &strm );
5674    return BZ_OK;
5675 
5676    output_overflow:
5677    BZ2_bzCompressEnd ( &strm );
5678    return BZ_OUTBUFF_FULL;
5679 
5680    errhandler:
5681    BZ2_bzCompressEnd ( &strm );
5682    return ret;
5683 }
5684 
5685 
5686 /*---------------------------------------------------*/
BZ_API(BZ2_bzBuffToBuffDecompress)5687 int BZ_API(BZ2_bzBuffToBuffDecompress)
5688                            ( char*         dest,
5689                              unsigned int* destLen,
5690                              char*         source,
5691                              unsigned int  sourceLen,
5692                              int           small,
5693                              int           verbosity )
5694 {
5695    bz_stream strm;
5696    int ret;
5697 
5698    if (dest == NULL || destLen == NULL ||
5699        source == NULL ||
5700        (small != 0 && small != 1) ||
5701        verbosity < 0 || verbosity > 4)
5702           return BZ_PARAM_ERROR;
5703 
5704    strm.bzalloc = NULL;
5705    strm.bzfree = NULL;
5706    strm.opaque = NULL;
5707    ret = BZ2_bzDecompressInit ( &strm, verbosity, small );
5708    if (ret != BZ_OK) return ret;
5709 
5710    strm.next_in = source;
5711    strm.next_out = dest;
5712    strm.avail_in = sourceLen;
5713    strm.avail_out = *destLen;
5714 
5715    ret = BZ2_bzDecompress ( &strm );
5716    if (ret == BZ_OK) goto output_overflow_or_eof;
5717    if (ret != BZ_STREAM_END) goto errhandler;
5718 
5719    /* normal termination */
5720    *destLen -= strm.avail_out;
5721    BZ2_bzDecompressEnd ( &strm );
5722    return BZ_OK;
5723 
5724    output_overflow_or_eof:
5725    if (strm.avail_out > 0) {
5726       BZ2_bzDecompressEnd ( &strm );
5727       return BZ_UNEXPECTED_EOF;
5728    } else {
5729       BZ2_bzDecompressEnd ( &strm );
5730       return BZ_OUTBUFF_FULL;
5731    };
5732 
5733    errhandler:
5734    BZ2_bzDecompressEnd ( &strm );
5735    return ret;
5736 }
5737 
5738 
5739 /*---------------------------------------------------*/
5740 /*--
5741    Code contributed by Yoshioka Tsuneo
5742    (QWF00133@niftyserve.or.jp/tsuneo-y@is.aist-nara.ac.jp),
5743    to support better zlib compatibility.
5744    This code is not _officially_ part of libbzip2 (yet);
5745    I haven't tested it, documented it, or considered the
5746    threading-safeness of it.
5747    If this code breaks, please contact both Yoshioka and me.
5748 --*/
5749 /*---------------------------------------------------*/
5750 
5751 /*---------------------------------------------------*/
5752 /*--
5753    return version like "0.9.0c".
5754 --*/
BZ_API(BZ2_bzlibVersion)5755 const char * BZ_API(BZ2_bzlibVersion)(void)
5756 {
5757    return BZ_VERSION;
5758 }
5759 
5760 
5761 #ifndef BZ_NO_STDIO
5762 /*---------------------------------------------------*/
5763 
5764 #if defined(_WIN32) || defined(OS2) || defined(MSDOS)
5765 #   include <fcntl.h>
5766 #   include <io.h>
5767 #   define SET_BINARY_MODE(file) setmode(fileno(file),O_BINARY)
5768 #else
5769 #   define SET_BINARY_MODE(file)
5770 #endif
5771 static
bzopen_or_bzdopen(const char * path,int fd,const char * mode,int open_mode)5772 BZFILE * bzopen_or_bzdopen
5773                ( const char *path,   /* no use when bzdopen */
5774                  int fd,             /* no use when bzdopen */
5775                  const char *mode,
5776                  int open_mode)      /* bzopen: 0, bzdopen:1 */
5777 {
5778    int    bzerr;
5779    char   unused[BZ_MAX_UNUSED];
5780    int    blockSize100k = 9;
5781    int    writing       = 0;
5782    char   mode2[10]     = "";
5783    FILE   *fp           = NULL;
5784    BZFILE *bzfp         = NULL;
5785    int    verbosity     = 0;
5786    int    workFactor    = 30;
5787    int    smallMode     = 0;
5788    int    nUnused       = 0;
5789 
5790    if (mode == NULL) return NULL;
5791    while (*mode) {
5792       switch (*mode) {
5793       case 'r':
5794          writing = 0; break;
5795       case 'w':
5796          writing = 1; break;
5797       case 's':
5798          smallMode = 1; break;
5799       default:
5800          if (isdigit((int)(*mode))) {
5801             blockSize100k = *mode-BZ_HDR_0;
5802          }
5803       }
5804       mode++;
5805    }
5806    strcat(mode2, writing ? "w" : "r" );
5807    strcat(mode2,"b");   /* binary mode */
5808 
5809    if (open_mode==0) {
5810       if (path==NULL || strcmp(path,"")==0) {
5811         fp = (writing ? stdout : stdin);
5812         SET_BINARY_MODE(fp);
5813       } else {
5814         fp = fopen(path,mode2);
5815       }
5816    } else {
5817 #ifdef BZ_STRICT_ANSI
5818       fp = NULL;
5819 #else
5820       fp = fdopen(fd,mode2);
5821 #endif
5822    }
5823    if (fp == NULL) return NULL;
5824 
5825    if (writing) {
5826       /* Guard against total chaos and anarchy -- JRS */
5827       if (blockSize100k < 1) blockSize100k = 1;
5828       if (blockSize100k > 9) blockSize100k = 9;
5829       bzfp = BZ2_bzWriteOpen(&bzerr,fp,blockSize100k,
5830                              verbosity,workFactor);
5831    } else {
5832       bzfp = BZ2_bzReadOpen(&bzerr,fp,verbosity,smallMode,
5833                             unused,nUnused);
5834    }
5835    if (bzfp == NULL) {
5836       if (fp != stdin && fp != stdout) fclose(fp);
5837       return NULL;
5838    }
5839    return bzfp;
5840 }
5841 
5842 
5843 /*---------------------------------------------------*/
5844 /*--
5845    open file for read or write.
5846       ex) bzopen("file","w9")
5847       case path="" or NULL => use stdin or stdout.
5848 --*/
BZ_API(BZ2_bzopen)5849 BZFILE * BZ_API(BZ2_bzopen)
5850                ( const char *path,
5851                  const char *mode )
5852 {
5853    return bzopen_or_bzdopen(path,-1,mode,/*bzopen*/0);
5854 }
5855 
5856 
5857 /*---------------------------------------------------*/
BZ_API(BZ2_bzdopen)5858 BZFILE * BZ_API(BZ2_bzdopen)
5859                ( int fd,
5860                  const char *mode )
5861 {
5862    return bzopen_or_bzdopen(NULL,fd,mode,/*bzdopen*/1);
5863 }
5864 
5865 
5866 /*---------------------------------------------------*/
BZ_API(BZ2_bzread)5867 int BZ_API(BZ2_bzread) (BZFILE* b, void* buf, int len )
5868 {
5869    int bzerr, nread;
5870    if (((bzFile*)b)->lastErr == BZ_STREAM_END) return 0;
5871    nread = BZ2_bzRead(&bzerr,b,buf,len);
5872    if (bzerr == BZ_OK || bzerr == BZ_STREAM_END) {
5873       return nread;
5874    } else {
5875       return -1;
5876    }
5877 }
5878 
5879 
5880 /*---------------------------------------------------*/
BZ_API(BZ2_bzwrite)5881 int BZ_API(BZ2_bzwrite) (BZFILE* b, void* buf, int len )
5882 {
5883    int bzerr;
5884 
5885    BZ2_bzWrite(&bzerr,b,buf,len);
5886    if(bzerr == BZ_OK){
5887       return len;
5888    }else{
5889       return -1;
5890    }
5891 }
5892 
5893 
5894 /*---------------------------------------------------*/
BZ_API(BZ2_bzflush)5895 int BZ_API(BZ2_bzflush) (BZFILE *b)
5896 {
5897    /* do nothing now... */
5898    return 0;
5899 }
5900 
5901 
5902 /*---------------------------------------------------*/
BZ_API(BZ2_bzclose)5903 void BZ_API(BZ2_bzclose) (BZFILE* b)
5904 {
5905    int bzerr;
5906    FILE *fp = ((bzFile *)b)->handle;
5907 
5908    if (b==NULL) {return;}
5909    if(((bzFile*)b)->writing){
5910       BZ2_bzWriteClose(&bzerr,b,0,NULL,NULL);
5911       if(bzerr != BZ_OK){
5912          BZ2_bzWriteClose(NULL,b,1,NULL,NULL);
5913       }
5914    }else{
5915       BZ2_bzReadClose(&bzerr,b);
5916    }
5917    if(fp!=stdin && fp!=stdout){
5918       fclose(fp);
5919    }
5920 }
5921 
5922 
5923 /*---------------------------------------------------*/
5924 /*--
5925    return last error code
5926 --*/
5927 static char *bzerrorstrings[] = {
5928        "OK"
5929       ,"SEQUENCE_ERROR"
5930       ,"PARAM_ERROR"
5931       ,"MEM_ERROR"
5932       ,"DATA_ERROR"
5933       ,"DATA_ERROR_MAGIC"
5934       ,"IO_ERROR"
5935       ,"UNEXPECTED_EOF"
5936       ,"OUTBUFF_FULL"
5937       ,"CONFIG_ERROR"
5938       ,"???"   /* for future */
5939       ,"???"   /* for future */
5940       ,"???"   /* for future */
5941       ,"???"   /* for future */
5942       ,"???"   /* for future */
5943       ,"???"   /* for future */
5944 };
5945 
5946 
BZ_API(BZ2_bzerror)5947 const char * BZ_API(BZ2_bzerror) (BZFILE *b, int *errnum)
5948 {
5949    int err = ((bzFile *)b)->lastErr;
5950 
5951    if(err>0) err = 0;
5952    *errnum = err;
5953    return bzerrorstrings[err*-1];
5954 }
5955 #endif
5956 
5957 
5958 /*-------------------------------------------------------------*/
5959 /*--- end                                           bzlib.c ---*/
5960 /*-------------------------------------------------------------*/
5961 
5962 
5963 /////////////////////////////////////////////////////////////////////
5964 /////////////////////////////////////////////////////////////////////
5965 
5966 
5967 /* A test program written to test robustness to decompression of
5968    corrupted data.  Usage is
5969        unzcrash filename
5970    and the program will read the specified file, compress it (in memory),
5971    and then repeatedly decompress it, each time with a different bit of
5972    the compressed data inverted, so as to test all possible one-bit errors.
5973    This should not cause any invalid memory accesses.  If it does,
5974    I want to know about it!
5975 
5976    p.s.  As you can see from the above description, the process is
5977    incredibly slow.  A file of size eg 5KB will cause it to run for
5978    many hours.
5979 */
5980 
5981 //#include <stdio.h>
5982 //#include <assert.h>
5983 //#include "bzlib.h"
5984 
5985 #define M_BLOCK 1000000
5986 
5987 
5988 #define M_BLOCK_OUT (M_BLOCK + 1000000)
5989  char inbuf[M_BLOCK];
5990  char outbuf[M_BLOCK_OUT];
5991  char zbuf[M_BLOCK + 600 + (M_BLOCK / 100)];
5992 
5993 int nIn;
5994 unsigned int nOut;
5995 unsigned int nZ;
5996 
5997 #if 0
5998 static char *bzerrorstrings[] = {
5999        "OK"
6000       ,"SEQUENCE_ERROR"
6001       ,"PARAM_ERROR"
6002       ,"MEM_ERROR"
6003       ,"DATA_ERROR"
6004       ,"DATA_ERROR_MAGIC"
6005       ,"IO_ERROR"
6006       ,"UNEXPECTED_EOF"
6007       ,"OUTBUFF_FULL"
6008       ,"???"   /* for future */
6009       ,"???"   /* for future */
6010       ,"???"   /* for future */
6011       ,"???"   /* for future */
6012       ,"???"   /* for future */
6013       ,"???"   /* for future */
6014 };
6015 #endif
6016 
flip_bit(int bit)6017 void flip_bit ( int bit )
6018 {
6019    int byteno = bit / 8;
6020    int bitno  = bit % 8;
6021    UChar mask = 1 << bitno;
6022    //fprintf ( stderr, "(byte %d  bit %d  mask %d)",
6023    //          byteno, bitno, (int)mask );
6024    zbuf[byteno] ^= mask;
6025 }
6026 
set_inbuf(void)6027 void set_inbuf ( void )
6028 {
6029   inbuf[0] = 0;
6030   my_strcat(inbuf, "At her sixtieth birthday party, Margaret Thatcher ");
6031   my_strcat(inbuf, "blew on the cake to light the candles.\n");
6032   my_strcat(inbuf, "This program, bzip2, the associated library libbzip2, and all\n");
6033   my_strcat(inbuf, "documentation, are copyright (C) 1996-2004 Julian R Seward.  All\n");
6034   my_strcat(inbuf, "rights reserved.\n");
6035   my_strcat(inbuf, "\n");
6036   my_strcat(inbuf, "Redistribution and use in source and binary forms, with or without\n");
6037   my_strcat(inbuf, "modification, are permitted provided that the following conditions\n");
6038   my_strcat(inbuf, "are met:\n");
6039   my_strcat(inbuf, "\n");
6040   my_strcat(inbuf, "1. Redistributions of source code must retain the above copyright\n");
6041   my_strcat(inbuf, "   notice, this list of conditions and the following disclaimer.\n");
6042   my_strcat(inbuf, "\n");
6043   my_strcat(inbuf, "2. The origin of this software must not be misrepresented; you must\n");
6044   my_strcat(inbuf, "   not claim that you wrote the original software.  If you use this\n");
6045   my_strcat(inbuf, "   software in a product, an acknowledgment in the product\n");
6046   my_strcat(inbuf, "   documentation would be appreciated but is not required.\n");
6047   my_strcat(inbuf, "\n");
6048   my_strcat(inbuf, "3. Altered source versions must be plainly marked as such, and must\n");
6049   my_strcat(inbuf, "   not be misrepresented as being the original software.\n");
6050   my_strcat(inbuf, "\n");
6051   my_strcat(inbuf, "4. The name of the author may not be used to endorse or promote\n");
6052   my_strcat(inbuf, "   products derived from this software without specific prior written\n");
6053   my_strcat(inbuf, "   permission.\n");
6054   my_strcat(inbuf, "\n");
6055   my_strcat(inbuf, "THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS\n");
6056   my_strcat(inbuf, "OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED\n");
6057   my_strcat(inbuf, "WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n");
6058   my_strcat(inbuf, "ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY\n");
6059   my_strcat(inbuf, "DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL\n");
6060   my_strcat(inbuf, "DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE\n");
6061   my_strcat(inbuf, "GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS\n");
6062   my_strcat(inbuf, "INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,\n");
6063   my_strcat(inbuf, "WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING\n");
6064   my_strcat(inbuf, "NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS\n");
6065   my_strcat(inbuf, "SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n");
6066   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6067   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6068   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6069   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6070   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6071   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6072   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6073   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6074   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6075   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6076   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6077   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6078   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6079   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6080   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6081   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6082   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6083   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6084   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6085   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6086   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6087   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6088   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6089   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6090   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6091   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6092   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6093   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6094   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6095   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6096   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6097   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6098   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6099   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6100   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6101   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6102   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6103   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6104   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6105   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6106   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6107   my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6108   my_strcat(inbuf, "		    GNU GENERAL PUBLIC LICENSE\n");
6109   my_strcat(inbuf, "		       Version 2, June 1991\n");
6110   my_strcat(inbuf, "\n");
6111   my_strcat(inbuf, " Copyright (C) 1989, 1991 Free Software Foundation, Inc.\n");
6112   my_strcat(inbuf, "     59 Temple Place, Suite 330, Boston, MA  02111-1307  USA\n");
6113   my_strcat(inbuf, " Everyone is permitted to copy and distribute verbatim copies\n");
6114   my_strcat(inbuf, " of this license document, but changing it is not allowed.\n");
6115   my_strcat(inbuf, "\n");
6116   my_strcat(inbuf, "			    Preamble\n");
6117   my_strcat(inbuf, "\n");
6118   my_strcat(inbuf, "  The licenses for most software are designed to take away your\n");
6119   my_strcat(inbuf, "freedom to share and change it.  By contrast, the GNU General Public\n");
6120   my_strcat(inbuf, "License is intended to guarantee your freedom to share and change free\n");
6121   my_strcat(inbuf, "software--to make sure the software is free for all its users.  This\n");
6122   my_strcat(inbuf, "General Public License applies to most of the Free Software\n");
6123   my_strcat(inbuf, "Foundation's software and to any other program whose authors commit to\n");
6124   my_strcat(inbuf, "using it.  (Some other Free Software Foundation software is covered by\n");
6125   my_strcat(inbuf, "the GNU Library General Public License instead.)  You can apply it to\n");
6126   my_strcat(inbuf, "your programs, too.\n");
6127   my_strcat(inbuf, "\n");
6128   my_strcat(inbuf, "  When we speak of free software, we are referring to freedom, not\n");
6129   my_strcat(inbuf, "price.  Our General Public Licenses are designed to make sure that you\n");
6130   my_strcat(inbuf, "have the freedom to distribute copies of free software (and charge for\n");
6131   my_strcat(inbuf, "this service if you wish), that you receive source code or can get it\n");
6132   my_strcat(inbuf, "if you want it, that you can change the software or use pieces of it\n");
6133   my_strcat(inbuf, "in new free programs; and that you know you can do these things.\n");
6134   my_strcat(inbuf, "\n");
6135   my_strcat(inbuf, "  To protect your rights, we need to make restrictions that forbid\n");
6136   my_strcat(inbuf, "anyone to deny you these rights or to ask you to surrender the rights.\n");
6137   my_strcat(inbuf, "These restrictions translate to certain responsibilities for you if you\n");
6138   my_strcat(inbuf, "distribute copies of the software, or if you modify it.\n");
6139   my_strcat(inbuf, "\n");
6140   my_strcat(inbuf, "  For example, if you distribute copies of such a program, whether\n");
6141   my_strcat(inbuf, "gratis or for a fee, you must give the recipients all the rights that\n");
6142   my_strcat(inbuf, "you have.  You must make sure that they, too, receive or can get the\n");
6143   my_strcat(inbuf, "source code.  And you must show them these terms so they know their\n");
6144   my_strcat(inbuf, "rights.\n");
6145   my_strcat(inbuf, "\n");
6146   my_strcat(inbuf, "  We protect your rights with two steps: (1) copyright the software, and\n");
6147   my_strcat(inbuf, "(2) offer you this license which gives you legal permission to copy,\n");
6148   my_strcat(inbuf, "distribute and/or modify the software.\n");
6149   my_strcat(inbuf, "\n");
6150   my_strcat(inbuf, "  Also, for each author's protection and ours, we want to make certain\n");
6151   my_strcat(inbuf, "that everyone understands that there is no warranty for this free\n");
6152   my_strcat(inbuf, "software.  If the software is modified by someone else and passed on, we\n");
6153   my_strcat(inbuf, "want its recipients to know that what they have is not the original, so\n");
6154   my_strcat(inbuf, "that any problems introduced by others will not reflect on the original\n");
6155   my_strcat(inbuf, "authors' reputations.\n");
6156   my_strcat(inbuf, "\n");
6157   my_strcat(inbuf, "  Finally, any free program is threatened constantly by software\n");
6158   my_strcat(inbuf, "patents.  We wish to avoid the danger that redistributors of a free\n");
6159   my_strcat(inbuf, "program will individually obtain patent licenses, in effect making the\n");
6160   my_strcat(inbuf, "program proprietary.  To prevent this, we have made it clear that any\n");
6161   my_strcat(inbuf, "patent must be licensed for everyone's free use or not licensed at all.\n");
6162   my_strcat(inbuf, "\n");
6163   my_strcat(inbuf, "  The precise terms and conditions for copying, distribution and\n");
6164   my_strcat(inbuf, "modification follow.\n");
6165   my_strcat(inbuf, "\n");
6166   my_strcat(inbuf, "		    GNU GENERAL PUBLIC LICENSE\n");
6167   my_strcat(inbuf, "   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION\n");
6168   my_strcat(inbuf, "\n");
6169   my_strcat(inbuf, "  0. This License applies to any program or other work which contains\n");
6170   my_strcat(inbuf, "a notice placed by the copyright holder saying it may be distributed\n");
6171   my_strcat(inbuf, "under the terms of this General Public License.  The Program, below,\n");
6172   my_strcat(inbuf, "refers to any such program or work, and a work based on the Program\n");
6173   my_strcat(inbuf, "means either the Program or any derivative work under copyright law:\n");
6174   my_strcat(inbuf, "that is to say, a work containing the Program or a portion of it,\n");
6175   my_strcat(inbuf, "either verbatim or with modifications and/or translated into another\n");
6176   my_strcat(inbuf, "language.  (Hereinafter, translation is included without limitation in\n");
6177   my_strcat(inbuf, "the term modification.)  Each licensee is addressed as you.\n");
6178   my_strcat(inbuf, "\n");
6179   my_strcat(inbuf, "Activities other than copying, distribution and modification are not\n");
6180   my_strcat(inbuf, "covered by this License; they are outside its scope.  The act of\n");
6181   my_strcat(inbuf, "running the Program is not restricted, and the output from the Program\n");
6182   my_strcat(inbuf, "is covered only if its contents constitute a work based on the\n");
6183   my_strcat(inbuf, "Program (independent of having been made by running the Program).\n");
6184   my_strcat(inbuf, "Whether that is true depends on what the Program does.\n");
6185   my_strcat(inbuf, "\n");
6186   my_strcat(inbuf, "  1. You may copy and distribute verbatim copies of the Program's\n");
6187   my_strcat(inbuf, "source code as you receive it, in any medium, provided that you\n");
6188   my_strcat(inbuf, "conspicuously and appropriately publish on each copy an appropriate\n");
6189   my_strcat(inbuf, "copyright notice and disclaimer of warranty; keep intact all the\n");
6190   my_strcat(inbuf, "notices that refer to this License and to the absence of any warranty;\n");
6191   my_strcat(inbuf, "and give any other recipients of the Program a copy of this License\n");
6192   my_strcat(inbuf, "along with the Program.\n");
6193   my_strcat(inbuf, "\n");
6194   my_strcat(inbuf, "You may charge a fee for the physical act of transferring a copy, and\n");
6195   my_strcat(inbuf, "you may at your option offer warranty protection in exchange for a fee.\n");
6196   my_strcat(inbuf, "\n");
6197   my_strcat(inbuf, "  2. You may modify your copy or copies of the Program or any portion\n");
6198   my_strcat(inbuf, "of it, thus forming a work based on the Program, and copy and\n");
6199   my_strcat(inbuf, "distribute such modifications or work under the terms of Section 1\n");
6200   my_strcat(inbuf, "above, provided that you also meet all of these conditions:\n");
6201   my_strcat(inbuf, "\n");
6202   my_strcat(inbuf, "    a) You must cause the modified files to carry prominent notices\n");
6203   my_strcat(inbuf, "    stating that you changed the files and the date of any change.\n");
6204   my_strcat(inbuf, "\n");
6205   my_strcat(inbuf, "    b) You must cause any work that you distribute or publish, that in\n");
6206   my_strcat(inbuf, "    whole or in part contains or is derived from the Program or any\n");
6207   my_strcat(inbuf, "    part thereof, to be licensed as a whole at no charge to all third\n");
6208   my_strcat(inbuf, "    parties under the terms of this License.\n");
6209   my_strcat(inbuf, "\n");
6210   my_strcat(inbuf, "    c) If the modified program normally reads commands interactively\n");
6211   my_strcat(inbuf, "    when run, you must cause it, when started running for such\n");
6212   my_strcat(inbuf, "    interactive use in the most ordinary way, to print or display an\n");
6213   my_strcat(inbuf, "    announcement including an appropriate copyright notice and a\n");
6214   my_strcat(inbuf, "    notice that there is no warranty (or else, saying that you provide\n");
6215   my_strcat(inbuf, "    a warranty) and that users may redistribute the program under\n");
6216   my_strcat(inbuf, "    these conditions, and telling the user how to view a copy of this\n");
6217   my_strcat(inbuf, "    License.  (Exception: if the Program itself is interactive but\n");
6218   my_strcat(inbuf, "    does not normally print such an announcement, your work based on\n");
6219   my_strcat(inbuf, "    the Program is not required to print an announcement.)\n");
6220   my_strcat(inbuf, "\n");
6221   my_strcat(inbuf, "These requirements apply to the modified work as a whole.  If\n");
6222   my_strcat(inbuf, "identifiable sections of that work are not derived from the Program,\n");
6223   my_strcat(inbuf, "and can be reasonably considered independent and separate works in\n");
6224   my_strcat(inbuf, "themselves, then this License, and its terms, do not apply to those\n");
6225   my_strcat(inbuf, "sections when you distribute them as separate works.  But when you\n");
6226   my_strcat(inbuf, "distribute the same sections as part of a whole which is a work based\n");
6227   my_strcat(inbuf, "on the Program, the distribution of the whole must be on the terms of\n");
6228   my_strcat(inbuf, "this License, whose permissions for other licensees extend to the\n");
6229   my_strcat(inbuf, "entire whole, and thus to each and every part regardless of who wrote it.\n");
6230   my_strcat(inbuf, "\n");
6231   my_strcat(inbuf, "Thus, it is not the intent of this section to claim rights or contest\n");
6232   my_strcat(inbuf, "your rights to work written entirely by you; rather, the intent is to\n");
6233   my_strcat(inbuf, "exercise the right to control the distribution of derivative or\n");
6234   my_strcat(inbuf, "collective works based on the Program.\n");
6235   my_strcat(inbuf, "\n");
6236   my_strcat(inbuf, "In addition, mere aggregation of another work not based on the Program\n");
6237   my_strcat(inbuf, "with the Program (or with a work based on the Program) on a volume of\n");
6238   my_strcat(inbuf, "a storage or distribution medium does not bring the other work under\n");
6239   my_strcat(inbuf, "the scope of this License.\n");
6240   my_strcat(inbuf, "\n");
6241   my_strcat(inbuf, "  3. You may copy and distribute the Program (or a work based on it,\n");
6242   my_strcat(inbuf, "under Section 2) in object code or executable form under the terms of\n");
6243   my_strcat(inbuf, "Sections 1 and 2 above provided that you also do one of the following:\n");
6244   my_strcat(inbuf, "\n");
6245   my_strcat(inbuf, "    a) Accompany it with the complete corresponding machine-readable\n");
6246   my_strcat(inbuf, "    source code, which must be distributed under the terms of Sections\n");
6247   my_strcat(inbuf, "    1 and 2 above on a medium customarily used for software interchange; or,\n");
6248   my_strcat(inbuf, "\n");
6249   my_strcat(inbuf, "    b) Accompany it with a written offer, valid for at least three\n");
6250   my_strcat(inbuf, "    years, to give any third party, for a charge no more than your\n");
6251   my_strcat(inbuf, "    cost of physically performing source distribution, a complete\n");
6252   my_strcat(inbuf, "    machine-readable copy of the corresponding source code, to be\n");
6253   my_strcat(inbuf, "    distributed under the terms of Sections 1 and 2 above on a medium\n");
6254   my_strcat(inbuf, "    customarily used for software interchange; or,\n");
6255   my_strcat(inbuf, "\n");
6256   my_strcat(inbuf, "    c) Accompany it with the information you received as to the offer\n");
6257   my_strcat(inbuf, "    to distribute corresponding source code.  (This alternative is\n");
6258   my_strcat(inbuf, "    allowed only for noncommercial distribution and only if you\n");
6259   my_strcat(inbuf, "    received the program in object code or executable form with such\n");
6260   my_strcat(inbuf, "    an offer, in accord with Subsection b above.)\n");
6261   my_strcat(inbuf, "\n");
6262   my_strcat(inbuf, "The source code for a work means the preferred form of the work for\n");
6263   my_strcat(inbuf, "making modifications to it.  For an executable work, complete source\n");
6264   my_strcat(inbuf, "code means all the source code for all modules it contains, plus any\n");
6265   my_strcat(inbuf, "associated interface definition files, plus the scripts used to\n");
6266   my_strcat(inbuf, "control compilation and installation of the executable.  However, as a\n");
6267   my_strcat(inbuf, "special exception, the source code distributed need not include\n");
6268   my_strcat(inbuf, "anything that is normally distributed (in either source or binary\n");
6269   my_strcat(inbuf, "form) with the major components (compiler, kernel, and so on) of the\n");
6270   my_strcat(inbuf, "operating system on which the executable runs, unless that component\n");
6271   my_strcat(inbuf, "itself accompanies the executable.\n");
6272   my_strcat(inbuf, "\n");
6273   my_strcat(inbuf, "If distribution of executable or object code is made by offering\n");
6274   my_strcat(inbuf, "access to copy from a designated place, then offering equivalent\n");
6275   my_strcat(inbuf, "access to copy the source code from the same place counts as\n");
6276   my_strcat(inbuf, "distribution of the source code, even though third parties are not\n");
6277   my_strcat(inbuf, "compelled to copy the source along with the object code.\n");
6278   my_strcat(inbuf, "\n");
6279   my_strcat(inbuf, "  4. You may not copy, modify, sublicense, or distribute the Program\n");
6280   my_strcat(inbuf, "except as expressly provided under this License.  Any attempt\n");
6281   my_strcat(inbuf, "otherwise to copy, modify, sublicense or distribute the Program is\n");
6282   my_strcat(inbuf, "void, and will automatically terminate your rights under this License.\n");
6283   my_strcat(inbuf, "However, parties who have received copies, or rights, from you under\n");
6284   my_strcat(inbuf, "this License will not have their licenses terminated so long as such\n");
6285   my_strcat(inbuf, "parties remain in full compliance.\n");
6286   my_strcat(inbuf, "\n");
6287   my_strcat(inbuf, "  5. You are not required to accept this License, since you have not\n");
6288   my_strcat(inbuf, "signed it.  However, nothing else grants you permission to modify or\n");
6289   my_strcat(inbuf, "distribute the Program or its derivative works.  These actions are\n");
6290   my_strcat(inbuf, "prohibited by law if you do not accept this License.  Therefore, by\n");
6291   my_strcat(inbuf, "modifying or distributing the Program (or any work based on the\n");
6292   my_strcat(inbuf, "Program), you indicate your acceptance of this License to do so, and\n");
6293   my_strcat(inbuf, "all its terms and conditions for copying, distributing or modifying\n");
6294   my_strcat(inbuf, "the Program or works based on it.\n");
6295   my_strcat(inbuf, "\n");
6296   my_strcat(inbuf, "  6. Each time you redistribute the Program (or any work based on the\n");
6297   my_strcat(inbuf, "Program), the recipient automatically receives a license from the\n");
6298   my_strcat(inbuf, "original licensor to copy, distribute or modify the Program subject to\n");
6299   my_strcat(inbuf, "these terms and conditions.  You may not impose any further\n");
6300   my_strcat(inbuf, "restrictions on the recipients' exercise of the rights granted herein.\n");
6301   my_strcat(inbuf, "You are not responsible for enforcing compliance by third parties to\n");
6302   my_strcat(inbuf, "this License.\n");
6303   my_strcat(inbuf, "\n");
6304   my_strcat(inbuf, "  7. If, as a consequence of a court judgment or allegation of patent\n");
6305   my_strcat(inbuf, "infringement or for any other reason (not limited to patent issues),\n");
6306   my_strcat(inbuf, "conditions are imposed on you (whether by court order, agreement or\n");
6307   my_strcat(inbuf, "otherwise) that contradict the conditions of this License, they do not\n");
6308   my_strcat(inbuf, "excuse you from the conditions of this License.  If you cannot\n");
6309   my_strcat(inbuf, "distribute so as to satisfy simultaneously your obligations under this\n");
6310   my_strcat(inbuf, "License and any other pertinent obligations, then as a consequence you\n");
6311   my_strcat(inbuf, "may not distribute the Program at all.  For example, if a patent\n");
6312   my_strcat(inbuf, "license would not permit royalty-free redistribution of the Program by\n");
6313   my_strcat(inbuf, "all those who receive copies directly or indirectly through you, then\n");
6314   my_strcat(inbuf, "the only way you could satisfy both it and this License would be to\n");
6315   my_strcat(inbuf, "refrain entirely from distribution of the Program.\n");
6316   my_strcat(inbuf, "\n");
6317   my_strcat(inbuf, "If any portion of this section is held invalid or unenforceable under\n");
6318   my_strcat(inbuf, "any particular circumstance, the balance of the section is intended to\n");
6319   my_strcat(inbuf, "apply and the section as a whole is intended to apply in other\n");
6320   my_strcat(inbuf, "circumstances.\n");
6321   my_strcat(inbuf, "\n");
6322   my_strcat(inbuf, "It is not the purpose of this section to induce you to infringe any\n");
6323   my_strcat(inbuf, "patents or other property right claims or to contest validity of any\n");
6324   my_strcat(inbuf, "such claims; this section has the sole purpose of protecting the\n");
6325   my_strcat(inbuf, "integrity of the free software distribution system, which is\n");
6326   my_strcat(inbuf, "implemented by public license practices.  Many people have made\n");
6327   my_strcat(inbuf, "generous contributions to the wide range of software distributed\n");
6328   my_strcat(inbuf, "through that system in reliance on consistent application of that\n");
6329   my_strcat(inbuf, "system; it is up to the author/donor to decide if he or she is willing\n");
6330   my_strcat(inbuf, "to distribute software through any other system and a licensee cannot\n");
6331   my_strcat(inbuf, "impose that choice.\n");
6332   my_strcat(inbuf, "\n");
6333   my_strcat(inbuf, "This section is intended to make thoroughly clear what is believed to\n");
6334   my_strcat(inbuf, "be a consequence of the rest of this License.\n");
6335   my_strcat(inbuf, "\n");
6336   my_strcat(inbuf, "  8. If the distribution and/or use of the Program is restricted in\n");
6337   my_strcat(inbuf, "certain countries either by patents or by copyrighted interfaces, the\n");
6338   my_strcat(inbuf, "original copyright holder who places the Program under this License\n");
6339   my_strcat(inbuf, "may add an explicit geographical distribution limitation excluding\n");
6340   my_strcat(inbuf, "those countries, so that distribution is permitted only in or among\n");
6341   my_strcat(inbuf, "countries not thus excluded.  In such case, this License incorporates\n");
6342   my_strcat(inbuf, "the limitation as if written in the body of this License.\n");
6343   my_strcat(inbuf, "\n");
6344   my_strcat(inbuf, "  9. The Free Software Foundation may publish revised and/or new versions\n");
6345   my_strcat(inbuf, "of the General Public License from time to time.  Such new versions will\n");
6346   my_strcat(inbuf, "be similar in spirit to the present version, but may differ in detail to\n");
6347   my_strcat(inbuf, "address new problems or concerns.\n");
6348   my_strcat(inbuf, "\n");
6349   my_strcat(inbuf, "Each version is given a distinguishing version number.  If the Program\n");
6350   my_strcat(inbuf, "specifies a version number of this License which applies to it and any\n");
6351   my_strcat(inbuf, "later version, you have the option of following the terms and conditions\n");
6352   my_strcat(inbuf, "either of that version or of any later version published by the Free\n");
6353   my_strcat(inbuf, "Software Foundation.  If the Program does not specify a version number of\n");
6354   my_strcat(inbuf, "this License, you may choose any version ever published by the Free Software\n");
6355   my_strcat(inbuf, "Foundation.\n");
6356   my_strcat(inbuf, "\n");
6357   my_strcat(inbuf, "  10. If you wish to incorporate parts of the Program into other free\n");
6358   my_strcat(inbuf, "programs whose distribution conditions are different, write to the author\n");
6359   my_strcat(inbuf, "to ask for permission.  For software which is copyrighted by the Free\n");
6360   my_strcat(inbuf, "Software Foundation, write to the Free Software Foundation; we sometimes\n");
6361   my_strcat(inbuf, "make exceptions for this.  Our decision will be guided by the two goals\n");
6362   my_strcat(inbuf, "of preserving the free status of all derivatives of our free software and\n");
6363   my_strcat(inbuf, "of promoting the sharing and reuse of software generally.\n");
6364   my_strcat(inbuf, "\n");
6365   my_strcat(inbuf, "			    NO WARRANTY\n");
6366   my_strcat(inbuf, "\n");
6367   my_strcat(inbuf, "  11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY\n");
6368   my_strcat(inbuf, "FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW.  EXCEPT WHEN\n");
6369   my_strcat(inbuf, "OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES\n");
6370   my_strcat(inbuf, "PROVIDE THE PROGRAM AS IS WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED\n");
6371   my_strcat(inbuf, "OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF\n");
6372   my_strcat(inbuf, "MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS\n");
6373   my_strcat(inbuf, "TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE\n");
6374   my_strcat(inbuf, "PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,\n");
6375   my_strcat(inbuf, "REPAIR OR CORRECTION.\n");
6376   my_strcat(inbuf, "\n");
6377   my_strcat(inbuf, "  12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING\n");
6378   my_strcat(inbuf, "WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR\n");
6379   my_strcat(inbuf, "REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,\n");
6380   my_strcat(inbuf, "INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING\n");
6381   my_strcat(inbuf, "OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED\n");
6382   my_strcat(inbuf, "TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY\n");
6383   my_strcat(inbuf, "YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER\n");
6384   my_strcat(inbuf, "PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE\n");
6385   my_strcat(inbuf, "POSSIBILITY OF SUCH DAMAGES.\n");
6386   my_strcat(inbuf, "\n");
6387   my_strcat(inbuf, "		     END OF TERMS AND CONDITIONS\n");
6388   my_strcat(inbuf, "\n");
6389   my_strcat(inbuf, "	    How to Apply These Terms to Your New Programs\n");
6390   my_strcat(inbuf, "\n");
6391   my_strcat(inbuf, "  If you develop a new program, and you want it to be of the greatest\n");
6392   my_strcat(inbuf, "possible use to the public, the best way to achieve this is to make it\n");
6393   my_strcat(inbuf, "free software which everyone can redistribute and change under these terms.\n");
6394   my_strcat(inbuf, "\n");
6395   my_strcat(inbuf, "  To do so, attach the following notices to the program.  It is safest\n");
6396   my_strcat(inbuf, "to attach them to the start of each source file to most effectively\n");
6397   my_strcat(inbuf, "convey the exclusion of warranty; and each file should have at least\n");
6398   my_strcat(inbuf, "the copyright line and a pointer to where the full notice is found.\n");
6399   my_strcat(inbuf, "\n");
6400   my_strcat(inbuf, "    <one line to give the program's name and a brief idea of what it does.>\n");
6401   my_strcat(inbuf, "    Copyright (C) <year>  <name of author>\n");
6402   my_strcat(inbuf, "\n");
6403   my_strcat(inbuf, "    This program is free software; you can redistribute it and/or modify\n");
6404   my_strcat(inbuf, "    it under the terms of the GNU General Public License as published by\n");
6405   my_strcat(inbuf, "    the Free Software Foundation; either version 2 of the License, or\n");
6406   my_strcat(inbuf, "    (at your option) any later version.\n");
6407   my_strcat(inbuf, "\n");
6408   my_strcat(inbuf, "    This program is distributed in the hope that it will be useful,\n");
6409   my_strcat(inbuf, "    but WITHOUT ANY WARRANTY; without even the implied warranty of\n");
6410   my_strcat(inbuf, "    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n");
6411   my_strcat(inbuf, "    GNU General Public License for more details.\n");
6412   my_strcat(inbuf, "\n");
6413   my_strcat(inbuf, "    You should have received a copy of the GNU General Public License\n");
6414   my_strcat(inbuf, "    along with this program; if not, write to the Free Software\n");
6415   my_strcat(inbuf, "    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA\n");
6416   my_strcat(inbuf, "\n");
6417   my_strcat(inbuf, "\n");
6418   my_strcat(inbuf, "Also add information on how to contact you by electronic and paper mail.\n");
6419   my_strcat(inbuf, "\n");
6420   my_strcat(inbuf, "If the program is interactive, make it output a short notice like this\n");
6421   my_strcat(inbuf, "when it starts in an interactive mode:\n");
6422   my_strcat(inbuf, "\n");
6423   my_strcat(inbuf, "    Gnomovision version 69, Copyright (C) year  name of author\n");
6424   my_strcat(inbuf, "    Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.\n");
6425   my_strcat(inbuf, "    This is free software, and you are welcome to redistribute it\n");
6426   my_strcat(inbuf, "    under certain conditions; type `show c' for details.\n");
6427   my_strcat(inbuf, "\n");
6428   my_strcat(inbuf, "The hypothetical commands `show w' and `show c' should show the appropriate\n");
6429   my_strcat(inbuf, "parts of the General Public License.  Of course, the commands you use may\n");
6430   my_strcat(inbuf, "be called something other than `show w' and `show c'; they could even be\n");
6431   my_strcat(inbuf, "mouse-clicks or menu items--whatever suits your program.\n");
6432   my_strcat(inbuf, "\n");
6433   my_strcat(inbuf, "You should also get your employer (if you work as a programmer) or your\n");
6434   my_strcat(inbuf, "school, if any, to sign a copyright disclaimer for the program, if\n");
6435   my_strcat(inbuf, "necessary.  Here is a sample; alter the names:\n");
6436   my_strcat(inbuf, "\n");
6437   my_strcat(inbuf, "  Yoyodyne, Inc., hereby disclaims all copyright interest in the program\n");
6438   my_strcat(inbuf, "  `Gnomovision' (which makes passes at compilers) written by James Hacker.\n");
6439   my_strcat(inbuf, "\n");
6440   my_strcat(inbuf, "  <signature of Ty Coon>, 1 April 1989\n");
6441   my_strcat(inbuf, "  Ty Coon, President of Vice\n");
6442   my_strcat(inbuf, "\n");
6443   my_strcat(inbuf, "This General Public License does not permit incorporating your program into\n");
6444   my_strcat(inbuf, "proprietary programs.  If your program is a subroutine library, you may\n");
6445   my_strcat(inbuf, "consider it more useful to permit linking proprietary applications with the\n");
6446   my_strcat(inbuf, "library.  If this is what you want to do, use the GNU Library General\n");
6447   my_strcat(inbuf, "Public License instead of this License.\n");
6448 
6449   my_strcat(inbuf, "\n");
6450 }
6451 
6452 
6453 #include <stdio.h>
6454 #include <assert.h>
6455 
6456 /* For providing services. */
g_serviceFn(HWord arg1,HWord arg2)6457 static HWord g_serviceFn ( HWord arg1, HWord arg2 )
6458 {
6459    switch (arg1) {
6460       case 0: /* EXIT */
6461          exit(0);
6462       case 1: /* PUTC */
6463          putchar(arg2);
6464          return 0;
6465       case 2: /* MALLOC */
6466          return (HWord)malloc(arg2);
6467       case 3: /* FREE */
6468          free((void*)arg2);
6469          return 0;
6470       default:
6471          assert(0);
6472    }
6473    return 0;
6474 }
6475 static char *bzerrorstrings[] = {
6476        "OK"
6477        ,"SEQUENCE_ERROR"
6478        ,"PARAM_ERROR"
6479        ,"MEM_ERROR"
6480        ,"DATA_ERROR"
6481        ,"DATA_ERROR_MAGIC"
6482        ,"IO_ERROR"
6483        ,"UNEXPECTED_EOF"
6484        ,"OUTBUFF_FULL"
6485        ,"CONFIG_ERROR"
6486        ,"???"   /* for future */
6487        ,"???"   /* for future */
6488        ,"???"   /* for future */
6489        ,"???"   /* for future */
6490        ,"???"   /* for future */
6491        ,"???"   /* for future */
6492 };
6493 
6494 // If given a cmd line arg, behave as a correctness regtest
6495 // (run fast and be verbose).  If not, run for a long time
6496 // which is what is needed for the performance suite.
main(int argc,char ** argv)6497 int main ( int argc, char** argv )
6498 {
6499    int   r;
6500    int   bit;
6501    int   i;
6502 
6503    int regtest;
6504    assert(argc == 1 || argc == 2);
6505    regtest = argc==2;
6506 
6507    /* hardwire one particular behaviour */
6508    regtest = 1;
6509 
6510    serviceFn = g_serviceFn;
6511 
6512    set_inbuf();
6513    nIn = vex_strlen(inbuf)+1;
6514    vex_printf( "%d bytes read\n", nIn );
6515 
6516    nZ = M_BLOCK;
6517    r = BZ2_bzBuffToBuffCompress (
6518           zbuf, &nZ, inbuf, nIn, 9, 3/*verb*/, 30 );
6519 
6520    if (r != BZ_OK) {
6521      vex_printf("initial compress failed!\n");
6522      (*serviceFn)(0,0);
6523    }
6524    vex_printf( "%d after compression\n", nZ );
6525 
6526    for (bit = 0; bit < nZ*8; bit += (bit < 35 ? 3 : (regtest?2377:137))) {
6527      if (bit >= 11920) break;
6528       if (regtest)
6529          vex_printf( "bit %d  ", bit );
6530       flip_bit ( bit );
6531       nOut = M_BLOCK_OUT;
6532       r = BZ2_bzBuffToBuffDecompress (
6533              outbuf, &nOut, zbuf, nZ, 1/*small*/, 0 );
6534       if (regtest)
6535          vex_printf( " %d  %s ", r, bzerrorstrings[-r] );
6536 
6537       if (r != BZ_OK) {
6538 	 if (regtest)
6539             vex_printf( "\n" );
6540       } else {
6541          if (nOut != nIn) {
6542            vex_printf(  "nIn/nOut mismatch %d %d\n", nIn, nOut );
6543            (*serviceFn)(0,0);
6544          } else {
6545            for (i = 0; i < nOut; i++)
6546              if (inbuf[i] != outbuf[i]) {
6547                 vex_printf(  "mismatch at %d\n", i );
6548                 (*serviceFn)(0,0);
6549            }
6550            if (i == nOut) vex_printf( "really ok!\n" );
6551          }
6552       }
6553 
6554       flip_bit ( bit );
6555    }
6556 
6557 #if 0
6558    assert (nOut == nIn);
6559    for (i = 0; i < nOut; i++) {
6560      if (inbuf[i] != outbuf[i]) {
6561         vex_printf( "difference at %d !\n", i );
6562         return 1;
6563      }
6564    }
6565 #endif
6566 
6567    vex_printf( "all ok\n" );
6568    (*serviceFn)(0,0);
6569    /*NOTREACHED*/
6570    return 0;
6571 }
6572