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