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