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