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