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