← Back to branch summary

~ubuntu-branches/ubuntu/hardy/codeblocks/hardy-backports

« back to all changes in this revision

Viewing changes to src/plugins/contrib/help_plugin/bzip2/decompress.c

  • Committer: Bazaar Package Importer
  • Author(s): Michael Casadevall
  • Date: 2008-07-17 04:39:23 UTC
  • Revision ID: james.westby@ubuntu.com-20080717043923-gmsy5cwkdjswghkm
Tags: upstream-8.02
Import upstream version 8.02

Show diffs side-by-side

added added

removed removed

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