1 #include <u.h>
2 #include <libc.h>
3 #include <bio.h>
4 #include "bzfs.h"
5
6 /*
7 * THIS FILE IS NOT IDENTICAL TO THE ORIGINAL
8 * FROM THE BZIP2 DISTRIBUTION.
9 *
10 * It has been modified, mainly to break the library
11 * into smaller pieces.
12 *
13 * Russ Cox
14 * rsc@plan9.bell-labs.com
15 * July 2000
16 */
17
18 /*---------------------------------------------*/
19 /*--
20 Place a 1 beside your platform, and 0 elsewhere.
21 Attempts to autosniff this even if you don't.
22 --*/
23
24
25 /*--
26 Plan 9 from Bell Labs
27 --*/
28 #define BZ_PLAN9 1
29 #define BZ_UNIX 0
30
31 #define exit(x) exits((x) ? "whoops" : nil)
32 #define size_t ulong
33
34 #ifdef __GNUC__
35 # define NORETURN __attribute__ ((noreturn))
36 #else
37 # define NORETURN /**/
38 #endif
39
40 /*--
41 Some more stuff for all platforms :-)
42 This might have to get moved into the platform-specific
43 header files if we encounter a machine with different sizes.
44 --*/
45
46 typedef char Char;
47 typedef unsigned char Bool;
48 typedef unsigned char UChar;
49 typedef int Int32;
50 typedef unsigned int UInt32;
51 typedef short Int16;
52 typedef unsigned short UInt16;
53
54 #define True ((Bool)1)
55 #define False ((Bool)0)
56
57 /*--
58 IntNative is your platform's `native' int size.
59 Only here to avoid probs with 64-bit platforms.
60 --*/
61 typedef int IntNative;
62
63 #include "bzfs.h"
64 #include "bzlib.h"
65 #include "bzlib_private.h"
66
67 static int
bunzip(int ofd,char * ofile,Biobuf * bin)68 bunzip(int ofd, char *ofile, Biobuf *bin)
69 {
70 int e, n, done, onemore;
71 char buf[8192];
72 char obuf[8192];
73 Biobuf bout;
74 bz_stream strm;
75
76 USED(ofile);
77
78 memset(&strm, 0, sizeof strm);
79 BZ2_bzDecompressInit(&strm, 0, 0);
80
81 strm.next_in = buf;
82 strm.avail_in = 0;
83 strm.next_out = obuf;
84 strm.avail_out = sizeof obuf;
85
86 done = 0;
87 Binit(&bout, ofd, OWRITE);
88
89 /*
90 * onemore is a crummy hack to go 'round the loop
91 * once after we finish, to flush the output buffer.
92 */
93 onemore = 1;
94 SET(e);
95 do {
96 if(!done && strm.avail_in < sizeof buf) {
97 if(strm.avail_in)
98 memmove(buf, strm.next_in, strm.avail_in);
99
100 n = Bread(bin, buf+strm.avail_in, sizeof(buf)-strm.avail_in);
101 if(n <= 0)
102 done = 1;
103 else
104 strm.avail_in += n;
105 strm.next_in = buf;
106 }
107 if(strm.avail_out < sizeof obuf) {
108 Bwrite(&bout, obuf, sizeof(obuf)-strm.avail_out);
109 strm.next_out = obuf;
110 strm.avail_out = sizeof obuf;
111 }
112
113 if(onemore == 0)
114 break;
115 } while((e=BZ2_bzDecompress(&strm)) == BZ_OK || onemore--);
116
117 if(e != BZ_STREAM_END) {
118 fprint(2, "bunzip2: decompress failed\n");
119 return 0;
120 }
121
122 if(BZ2_bzDecompressEnd(&strm) != BZ_OK) {
123 fprint(2, "bunzip2: decompress end failed (can't happen)\n");
124 return 0;
125 }
126
127 Bterm(&bout);
128
129 return 1;
130 }
131
132 void
_unbzip(int in,int out)133 _unbzip(int in, int out)
134 {
135 Biobuf bin;
136
137 Binit(&bin, in, OREAD);
138 if(bunzip(out, nil, &bin) != 1) {
139 fprint(2, "bunzip2 failed\n");
140 _exits("bunzip2");
141 }
142 }
143
144 int
unbzip(int in)145 unbzip(int in)
146 {
147 int rv, out, p[2];
148
149 if(pipe(p) < 0)
150 sysfatal("pipe: %r");
151
152 rv = p[0];
153 out = p[1];
154 switch(rfork(RFPROC|RFFDG|RFNOTEG|RFMEM)){
155 case -1:
156 sysfatal("fork: %r");
157 case 0:
158 close(rv);
159 break;
160 default:
161 close(in);
162 close(out);
163 return rv;
164 }
165
166 _unbzip(in, out);
167 _exits(0);
168 return -1; /* not reached */
169 }
170
bz_config_ok(void)171 int bz_config_ok ( void )
172 {
173 if (sizeof(int) != 4) return 0;
174 if (sizeof(short) != 2) return 0;
175 if (sizeof(char) != 1) return 0;
176 return 1;
177 }
178
default_bzalloc(void * o,int items,int size)179 void* default_bzalloc(void *o, int items, int size)
180 {
181 USED(o);
182 return sbrk(items*size);
183 }
184
default_bzfree(void *,void *)185 void default_bzfree(void*, void*)
186 {
187 }
188
189 void
bz_internal_error(int)190 bz_internal_error(int)
191 {
192 abort();
193 }
194
195 /*-------------------------------------------------------------*/
196 /*--- Decompression machinery ---*/
197 /*--- decompress.c ---*/
198 /*-------------------------------------------------------------*/
199
200 /*--
201 This file is a part of bzip2 and/or libbzip2, a program and
202 library for lossless, block-sorting data compression.
203
204 Copyright (C) 1996-2000 Julian R Seward. All rights reserved.
205
206 Redistribution and use in source and binary forms, with or without
207 modification, are permitted provided that the following conditions
208 are met:
209
210 1. Redistributions of source code must retain the above copyright
211 notice, this list of conditions and the following disclaimer.
212
213 2. The origin of this software must not be misrepresented; you must
214 not claim that you wrote the original software. If you use this
215 software in a product, an acknowledgment in the product
216 documentation would be appreciated but is not required.
217
218 3. Altered source versions must be plainly marked as such, and must
219 not be misrepresented as being the original software.
220
221 4. The name of the author may not be used to endorse or promote
222 products derived from this software without specific prior written
223 permission.
224
225 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
226 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
227 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
228 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
229 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
230 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
231 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
232 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
233 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
234 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
235 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
236
237 Julian Seward, Cambridge, UK.
238 jseward@acm.org
239 bzip2/libbzip2 version 1.0 of 21 March 2000
240
241 This program is based on (at least) the work of:
242 Mike Burrows
243 David Wheeler
244 Peter Fenwick
245 Alistair Moffat
246 Radford Neal
247 Ian H. Witten
248 Robert Sedgewick
249 Jon L. Bentley
250
251 For more information on these sources, see the manual.
252 --*/
253
254
255
256 /*---------------------------------------------------*/
257 static
makeMaps_d(DState * s)258 void makeMaps_d ( DState* s )
259 {
260 Int32 i;
261 s->nInUse = 0;
262 for (i = 0; i < 256; i++)
263 if (s->inUse[i]) {
264 s->seqToUnseq[s->nInUse] = i;
265 s->nInUse++;
266 }
267 }
268
269
270 /*---------------------------------------------------*/
271 #define RETURN(rrr) \
272 { retVal = rrr; goto save_state_and_return; };
273
274 #define GET_BITS(lll,vvv,nnn) \
275 case lll: \
276 { int x; if((retVal = getbits(s, lll, &x, nnn)) != 99) \
277 goto save_state_and_return; vvv=x; }\
278
279 int
getbits(DState * s,int lll,int * vvv,int nnn)280 getbits(DState *s, int lll, int *vvv, int nnn)
281 {
282 s->state = lll;
283
284 for(;;) {
285 if (s->bsLive >= nnn) {
286 UInt32 v;
287 v = (s->bsBuff >>
288 (s->bsLive-nnn)) & ((1 << nnn)-1);
289 s->bsLive -= nnn;
290 *vvv = v;
291 return 99;
292 }
293 if (s->strm->avail_in == 0) return BZ_OK;
294 s->bsBuff
295 = (s->bsBuff << 8) |
296 ((UInt32)
297 (*((UChar*)(s->strm->next_in))));
298 s->bsLive += 8;
299 s->strm->next_in++;
300 s->strm->avail_in--;
301 s->strm->total_in_lo32++;
302 if (s->strm->total_in_lo32 == 0)
303 s->strm->total_in_hi32++;
304 }
305 }
306
307 #define GET_UCHAR(lll,uuu) \
308 GET_BITS(lll,uuu,8)
309
310 #define GET_BIT(lll,uuu) \
311 GET_BITS(lll,uuu,1)
312
313 /*---------------------------------------------------*/
314 #define GET_MTF_VAL(label1,label2,lval) \
315 { \
316 if (groupPos == 0) { \
317 groupNo++; \
318 if (groupNo >= nSelectors) \
319 RETURN(BZ_DATA_ERROR); \
320 groupPos = BZ_G_SIZE; \
321 gSel = s->selector[groupNo]; \
322 gMinlen = s->minLens[gSel]; \
323 gLimit = &(s->limit[gSel][0]); \
324 gPerm = &(s->perm[gSel][0]); \
325 gBase = &(s->base[gSel][0]); \
326 } \
327 groupPos--; \
328 zn = gMinlen; \
329 GET_BITS(label1, zvec, zn); \
330 while (1) { \
331 if (zn > 20 /* the longest code */) \
332 RETURN(BZ_DATA_ERROR); \
333 if (zvec <= gLimit[zn]) break; \
334 zn++; \
335 GET_BIT(label2, zj); \
336 zvec = (zvec << 1) | zj; \
337 }; \
338 if (zvec - gBase[zn] < 0 \
339 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \
340 RETURN(BZ_DATA_ERROR); \
341 lval = gPerm[zvec - gBase[zn]]; \
342 }
343
344
345 /*---------------------------------------------------*/
BZ2_decompress(DState * s)346 Int32 BZ2_decompress ( DState* s )
347 {
348 UChar uc;
349 Int32 retVal;
350 Int32 minLen, maxLen;
351 bz_stream* strm = s->strm;
352
353 /* stuff that needs to be saved/restored */
354 Int32 i;
355 Int32 j;
356 Int32 t;
357 Int32 alphaSize;
358 Int32 nGroups;
359 Int32 nSelectors;
360 Int32 EOB;
361 Int32 groupNo;
362 Int32 groupPos;
363 Int32 nextSym;
364 Int32 nblockMAX;
365 Int32 nblock;
366 Int32 es;
367 Int32 N;
368 Int32 curr;
369 Int32 zt;
370 Int32 zn;
371 Int32 zvec;
372 Int32 zj;
373 Int32 gSel;
374 Int32 gMinlen;
375 Int32* gLimit;
376 Int32* gBase;
377 Int32* gPerm;
378
379 if (s->state == BZ_X_MAGIC_1) {
380 /*initialise the save area*/
381 s->save_i = 0;
382 s->save_j = 0;
383 s->save_t = 0;
384 s->save_alphaSize = 0;
385 s->save_nGroups = 0;
386 s->save_nSelectors = 0;
387 s->save_EOB = 0;
388 s->save_groupNo = 0;
389 s->save_groupPos = 0;
390 s->save_nextSym = 0;
391 s->save_nblockMAX = 0;
392 s->save_nblock = 0;
393 s->save_es = 0;
394 s->save_N = 0;
395 s->save_curr = 0;
396 s->save_zt = 0;
397 s->save_zn = 0;
398 s->save_zvec = 0;
399 s->save_zj = 0;
400 s->save_gSel = 0;
401 s->save_gMinlen = 0;
402 s->save_gLimit = NULL;
403 s->save_gBase = NULL;
404 s->save_gPerm = NULL;
405 }
406
407 /*restore from the save area*/
408 i = s->save_i;
409 j = s->save_j;
410 t = s->save_t;
411 alphaSize = s->save_alphaSize;
412 nGroups = s->save_nGroups;
413 nSelectors = s->save_nSelectors;
414 EOB = s->save_EOB;
415 groupNo = s->save_groupNo;
416 groupPos = s->save_groupPos;
417 nextSym = s->save_nextSym;
418 nblockMAX = s->save_nblockMAX;
419 nblock = s->save_nblock;
420 es = s->save_es;
421 N = s->save_N;
422 curr = s->save_curr;
423 zt = s->save_zt;
424 zn = s->save_zn;
425 zvec = s->save_zvec;
426 zj = s->save_zj;
427 gSel = s->save_gSel;
428 gMinlen = s->save_gMinlen;
429 gLimit = s->save_gLimit;
430 gBase = s->save_gBase;
431 gPerm = s->save_gPerm;
432
433 retVal = BZ_OK;
434
435 switch (s->state) {
436
437 GET_UCHAR(BZ_X_MAGIC_1, uc);
438 if (uc != 'B') RETURN(BZ_DATA_ERROR_MAGIC);
439
440 GET_UCHAR(BZ_X_MAGIC_2, uc);
441 if (uc != 'Z') RETURN(BZ_DATA_ERROR_MAGIC);
442
443 GET_UCHAR(BZ_X_MAGIC_3, uc)
444 if (uc != 'h') RETURN(BZ_DATA_ERROR_MAGIC);
445
446 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
447 if (s->blockSize100k < '1' ||
448 s->blockSize100k > '9') RETURN(BZ_DATA_ERROR_MAGIC);
449 s->blockSize100k -= '0';
450
451 if (0 && s->smallDecompress) {
452 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
453 s->ll4 = BZALLOC(
454 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
455 );
456 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
457 } else {
458 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
459 if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
460 }
461
462 GET_UCHAR(BZ_X_BLKHDR_1, uc);
463
464 if (uc == 0x17) goto endhdr_2;
465 if (uc != 0x31) RETURN(BZ_DATA_ERROR);
466 GET_UCHAR(BZ_X_BLKHDR_2, uc);
467 if (uc != 0x41) RETURN(BZ_DATA_ERROR);
468 GET_UCHAR(BZ_X_BLKHDR_3, uc);
469 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
470 GET_UCHAR(BZ_X_BLKHDR_4, uc);
471 if (uc != 0x26) RETURN(BZ_DATA_ERROR);
472 GET_UCHAR(BZ_X_BLKHDR_5, uc);
473 if (uc != 0x53) RETURN(BZ_DATA_ERROR);
474 GET_UCHAR(BZ_X_BLKHDR_6, uc);
475 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
476
477 s->currBlockNo++;
478 // if (s->verbosity >= 2)
479 // VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );
480
481 s->storedBlockCRC = 0;
482 GET_UCHAR(BZ_X_BCRC_1, uc);
483 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
484 GET_UCHAR(BZ_X_BCRC_2, uc);
485 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
486 GET_UCHAR(BZ_X_BCRC_3, uc);
487 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
488 GET_UCHAR(BZ_X_BCRC_4, uc);
489 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
490
491 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
492
493 s->origPtr = 0;
494 GET_UCHAR(BZ_X_ORIGPTR_1, uc);
495 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
496 GET_UCHAR(BZ_X_ORIGPTR_2, uc);
497 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
498 GET_UCHAR(BZ_X_ORIGPTR_3, uc);
499 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
500
501 if (s->origPtr < 0)
502 RETURN(BZ_DATA_ERROR);
503 if (s->origPtr > 10 + 100000*s->blockSize100k)
504 RETURN(BZ_DATA_ERROR);
505
506 /*--- Receive the mapping table ---*/
507 for (i = 0; i < 16; i++) {
508 GET_BIT(BZ_X_MAPPING_1, uc);
509 if (uc == 1)
510 s->inUse16[i] = True; else
511 s->inUse16[i] = False;
512 }
513
514 for (i = 0; i < 256; i++) s->inUse[i] = False;
515
516 for (i = 0; i < 16; i++)
517 if (s->inUse16[i])
518 for (j = 0; j < 16; j++) {
519 GET_BIT(BZ_X_MAPPING_2, uc);
520 if (uc == 1) s->inUse[i * 16 + j] = True;
521 }
522 makeMaps_d ( s );
523 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
524 alphaSize = s->nInUse+2;
525
526 /*--- Now the selectors ---*/
527 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
528 if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
529 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
530 if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
531 for (i = 0; i < nSelectors; i++) {
532 j = 0;
533 while (True) {
534 GET_BIT(BZ_X_SELECTOR_3, uc);
535 if (uc == 0) break;
536 j++;
537 if (j >= nGroups) RETURN(BZ_DATA_ERROR);
538 }
539 s->selectorMtf[i] = j;
540 }
541
542 /*--- Undo the MTF values for the selectors. ---*/
543 {
544 UChar pos[BZ_N_GROUPS], tmp, v;
545 for (v = 0; v < nGroups; v++) pos[v] = v;
546
547 for (i = 0; i < nSelectors; i++) {
548 v = s->selectorMtf[i];
549 tmp = pos[v];
550 while (v > 0) { pos[v] = pos[v-1]; v--; }
551 pos[0] = tmp;
552 s->selector[i] = tmp;
553 }
554 }
555
556 /*--- Now the coding tables ---*/
557 for (t = 0; t < nGroups; t++) {
558 GET_BITS(BZ_X_CODING_1, curr, 5);
559 for (i = 0; i < alphaSize; i++) {
560 while (True) {
561 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
562 GET_BIT(BZ_X_CODING_2, uc);
563 if (uc == 0) break;
564 GET_BIT(BZ_X_CODING_3, uc);
565 if (uc == 0) curr++; else curr--;
566 }
567 s->len[t][i] = curr;
568 }
569 }
570
571 /*--- Create the Huffman decoding tables ---*/
572 for (t = 0; t < nGroups; t++) {
573 minLen = 32;
574 maxLen = 0;
575 for (i = 0; i < alphaSize; i++) {
576 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
577 if (s->len[t][i] < minLen) minLen = s->len[t][i];
578 }
579 BZ2_hbCreateDecodeTables (
580 &(s->limit[t][0]),
581 &(s->base[t][0]),
582 &(s->perm[t][0]),
583 &(s->len[t][0]),
584 minLen, maxLen, alphaSize
585 );
586 s->minLens[t] = minLen;
587 }
588
589 /*--- Now the MTF values ---*/
590
591 EOB = s->nInUse+1;
592 nblockMAX = 100000 * s->blockSize100k;
593 groupNo = -1;
594 groupPos = 0;
595
596 for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
597
598 /*-- MTF init --*/
599 {
600 Int32 ii, jj, kk;
601 kk = MTFA_SIZE-1;
602 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
603 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
604 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
605 kk--;
606 }
607 s->mtfbase[ii] = kk + 1;
608 }
609 }
610 /*-- end MTF init --*/
611
612 nblock = 0;
613 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
614
615 while (True) {
616
617 if (nextSym == EOB) break;
618
619 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
620
621 es = -1;
622 N = 1;
623 do {
624 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
625 if (nextSym == BZ_RUNB) es = es + (1+1) * N;
626 N = N * 2;
627 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
628 }
629 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
630
631 es++;
632 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
633 s->unzftab[uc] += es;
634
635 if (0 && s->smallDecompress)
636 while (es > 0) {
637 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
638 s->ll16[nblock] = (UInt16)uc;
639 nblock++;
640 es--;
641 }
642 else
643 while (es > 0) {
644 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
645 s->tt[nblock] = (UInt32)uc;
646 nblock++;
647 es--;
648 };
649
650 continue;
651
652 } else {
653
654 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
655
656 /*-- uc = MTF ( nextSym-1 ) --*/
657 {
658 Int32 ii, jj, kk, pp, lno, off;
659 UInt32 nn;
660 nn = (UInt32)(nextSym - 1);
661
662 if (nn < MTFL_SIZE) {
663 /* avoid general-case expense */
664 pp = s->mtfbase[0];
665 uc = s->mtfa[pp+nn];
666 while (nn > 3) {
667 Int32 z = pp+nn;
668 s->mtfa[(z) ] = s->mtfa[(z)-1];
669 s->mtfa[(z)-1] = s->mtfa[(z)-2];
670 s->mtfa[(z)-2] = s->mtfa[(z)-3];
671 s->mtfa[(z)-3] = s->mtfa[(z)-4];
672 nn -= 4;
673 }
674 while (nn > 0) {
675 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
676 };
677 s->mtfa[pp] = uc;
678 } else {
679 /* general case */
680 lno = nn / MTFL_SIZE;
681 off = nn % MTFL_SIZE;
682 pp = s->mtfbase[lno] + off;
683 uc = s->mtfa[pp];
684 while (pp > s->mtfbase[lno]) {
685 s->mtfa[pp] = s->mtfa[pp-1]; pp--;
686 };
687 s->mtfbase[lno]++;
688 while (lno > 0) {
689 s->mtfbase[lno]--;
690 s->mtfa[s->mtfbase[lno]]
691 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
692 lno--;
693 }
694 s->mtfbase[0]--;
695 s->mtfa[s->mtfbase[0]] = uc;
696 if (s->mtfbase[0] == 0) {
697 kk = MTFA_SIZE-1;
698 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
699 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
700 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
701 kk--;
702 }
703 s->mtfbase[ii] = kk + 1;
704 }
705 }
706 }
707 }
708 /*-- end uc = MTF ( nextSym-1 ) --*/
709
710 s->unzftab[s->seqToUnseq[uc]]++;
711 if (0 && s->smallDecompress)
712 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
713 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]);
714 nblock++;
715
716 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
717 continue;
718 }
719 }
720
721 /* Now we know what nblock is, we can do a better sanity
722 check on s->origPtr.
723 */
724 if (s->origPtr < 0 || s->origPtr >= nblock)
725 RETURN(BZ_DATA_ERROR);
726
727 s->state_out_len = 0;
728 s->state_out_ch = 0;
729 BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
730 s->state = BZ_X_OUTPUT;
731 // if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
732
733 /*-- Set up cftab to facilitate generation of T^(-1) --*/
734 s->cftab[0] = 0;
735 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
736 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
737
738 if (0 && s->smallDecompress) {
739
740 /*-- Make a copy of cftab, used in generation of T --*/
741 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
742
743 /*-- compute the T vector --*/
744 for (i = 0; i < nblock; i++) {
745 uc = (UChar)(s->ll16[i]);
746 SET_LL(i, s->cftabCopy[uc]);
747 s->cftabCopy[uc]++;
748 }
749
750 /*-- Compute T^(-1) by pointer reversal on T --*/
751 i = s->origPtr;
752 j = GET_LL(i);
753 do {
754 Int32 tmp = GET_LL(j);
755 SET_LL(j, i);
756 i = j;
757 j = tmp;
758 }
759 while (i != s->origPtr);
760
761 s->tPos = s->origPtr;
762 s->nblock_used = 0;
763 if (s->blockRandomised) {
764 BZ_RAND_INIT_MASK;
765 BZ_GET_SMALL(s->k0); s->nblock_used++;
766 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
767 } else {
768 BZ_GET_SMALL(s->k0); s->nblock_used++;
769 }
770
771 } else {
772
773 /*-- compute the T^(-1) vector --*/
774 for (i = 0; i < nblock; i++) {
775 uc = (UChar)(s->tt[i] & 0xff);
776 s->tt[s->cftab[uc]] |= (i << 8);
777 s->cftab[uc]++;
778 }
779
780 s->tPos = s->tt[s->origPtr] >> 8;
781 s->nblock_used = 0;
782 if (s->blockRandomised) {
783 BZ_RAND_INIT_MASK;
784 BZ_GET_FAST(s->k0); s->nblock_used++;
785 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
786 } else {
787 BZ_GET_FAST(s->k0); s->nblock_used++;
788 }
789
790 }
791
792 RETURN(BZ_OK);
793
794
795
796 endhdr_2:
797
798 GET_UCHAR(BZ_X_ENDHDR_2, uc);
799 if (uc != 0x72) RETURN(BZ_DATA_ERROR);
800 GET_UCHAR(BZ_X_ENDHDR_3, uc);
801 if (uc != 0x45) RETURN(BZ_DATA_ERROR);
802 GET_UCHAR(BZ_X_ENDHDR_4, uc);
803 if (uc != 0x38) RETURN(BZ_DATA_ERROR);
804 GET_UCHAR(BZ_X_ENDHDR_5, uc);
805 if (uc != 0x50) RETURN(BZ_DATA_ERROR);
806 GET_UCHAR(BZ_X_ENDHDR_6, uc);
807 if (uc != 0x90) RETURN(BZ_DATA_ERROR);
808
809 s->storedCombinedCRC = 0;
810 GET_UCHAR(BZ_X_CCRC_1, uc);
811 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
812 GET_UCHAR(BZ_X_CCRC_2, uc);
813 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
814 GET_UCHAR(BZ_X_CCRC_3, uc);
815 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
816 GET_UCHAR(BZ_X_CCRC_4, uc);
817 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
818
819 s->state = BZ_X_IDLE;
820 RETURN(BZ_STREAM_END);
821
822 default: AssertH ( False, 4001 );
823 }
824
825 AssertH ( False, 4002 );
826
827 save_state_and_return:
828
829 s->save_i = i;
830 s->save_j = j;
831 s->save_t = t;
832 s->save_alphaSize = alphaSize;
833 s->save_nGroups = nGroups;
834 s->save_nSelectors = nSelectors;
835 s->save_EOB = EOB;
836 s->save_groupNo = groupNo;
837 s->save_groupPos = groupPos;
838 s->save_nextSym = nextSym;
839 s->save_nblockMAX = nblockMAX;
840 s->save_nblock = nblock;
841 s->save_es = es;
842 s->save_N = N;
843 s->save_curr = curr;
844 s->save_zt = zt;
845 s->save_zn = zn;
846 s->save_zvec = zvec;
847 s->save_zj = zj;
848 s->save_gSel = gSel;
849 s->save_gMinlen = gMinlen;
850 s->save_gLimit = gLimit;
851 s->save_gBase = gBase;
852 s->save_gPerm = gPerm;
853
854 return retVal;
855 }
856
857
858 /*-------------------------------------------------------------*/
859 /*--- end decompress.c ---*/
860 /*-------------------------------------------------------------*/
861