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