unbzip.c 24 KB

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