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