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