l4/pkg/valgrind/src/valgrind-3.6.0-svn/memcheck/tests/varinfo6.c

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