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