← Back to branch summary

~hamo/ubuntu/precise/grub2/grub2.hi_res

« back to all changes in this revision

Viewing changes to lib/LzmaDec.c

  • Committer: Bazaar Package Importer
  • Author(s): Colin Watson, Colin Watson, Robert Millan, Updated translations
  • Date: 2010-11-22 12:24:56 UTC
  • mfrom: (1.26.4 upstream) (17.3.36 sid)
  • mto: (17.3.43 sid)
  • mto: This revision was merged to the branch mainline in revision 89.
  • Revision ID: james.westby@ubuntu.com-20101122122456-y82z3sfb7k4zfdcc
Tags: 1.99~20101122-1
http://bugs.debian.org/550658
http://bugs.debian.org/550702
http://bugs.debian.org/591416
http://bugs.debian.org/593347
http://bugs.debian.org/551627
http://bugs.debian.org/589325
http://bugs.debian.org/543924
http://bugs.debian.org/603354
http://bugs.debian.org/604003
http://bugs.debian.org/604102
[ Colin Watson ]
* New Bazaar snapshot.  Too many changes to list in full, but some of the
  more user-visible ones are as follows:
  - GRUB script:
    + Function parameters, "break", "continue", "shift", "setparams",
      "return", and "!".
    + "export" command supports multiple variable names.
    + Multi-line quoted strings support.
    + Wildcard expansion.
  - sendkey support.
  - USB hotunplugging and USB serial support.
  - Rename CD-ROM to cd on BIOS.
  - Add new --boot-directory option to grub-install, grub-reboot, and
    grub-set-default; the old --root-directory option is still accepted
    but was often confusing.
  - Basic btrfs detection/UUID support (but no file reading yet).
  - bash-completion for utilities.
  - If a device is listed in device.map, always assume that it is
    BIOS-visible rather than using extra layers such as LVM or RAID.
  - Add grub-mknetdir script (closes: #550658).
  - Remove deprecated "root" command.
  - Handle RAID devices containing virtio components.
  - GRUB Legacy configuration file support (via grub-menulst2cfg).
  - Keyboard layout support (via grub-mklayout and grub-kbdcomp).
  - Check generated grub.cfg for syntax errors before saving.
  - Pause execution for at most ten seconds if any errors are displayed,
    so that the user has a chance to see them.
  - Support submenus.
  - Write embedding zone using Reed-Solomon, so that it's robust against
    being partially overwritten (closes: #550702, #591416, #593347).
  - GRUB_DISABLE_LINUX_RECOVERY and GRUB_DISABLE_NETBSD_RECOVERY merged
    into a single GRUB_DISABLE_RECOVERY variable.
  - Fix loader memory allocation failure (closes: #551627).
  - Don't call savedefault on recovery entries (closes: #589325).
  - Support triple-indirect blocks on ext2 (closes: #543924).
  - Recognise DDF1 fake RAID (closes: #603354).

[ Robert Millan ]
* Use dpkg architecture wildcards.

[ Updated translations ]
* Slovenian (Vanja Cvelbar).  Closes: #604003
* Dzongkha (dawa pemo via Tenzin Dendup).  Closes: #604102

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/LzmaDec.c
1
 
/*
2
 
 *  GRUB  --  GRand Unified Bootloader
3
 
 *  Copyright (c) 1999-2008 Igor Pavlov
4
 
 *  Copyright (C) 2008  Free Software Foundation, Inc.
5
 
 *
6
 
 *  GRUB is free software: you can redistribute it and/or modify
7
 
 *  it under the terms of the GNU General Public License as published by
8
 
 *  the Free Software Foundation, either version 3 of the License, or
9
 
 *  (at your option) any later version.
10
 
 *
11
 
 *  GRUB is distributed in the hope that it will be useful,
12
 
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13
 
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14
 
 *  GNU General Public License for more details.
15
 
 *
16
 
 *  You should have received a copy of the GNU General Public License
17
 
 *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
18
 
 */
19
 
 
20
 
/*
21
 
 * This code was taken from LZMA SDK 4.58 beta, and was slightly modified
22
 
 * to adapt it to GRUB's requirement.
23
 
 *
24
 
 * See <http://www.7-zip.org>, for more information about LZMA.
25
 
 */
26
 
 
27
 
#include <grub/lib/LzmaDec.h>
28
 
 
29
 
#include <string.h>
30
 
 
31
 
#define kNumTopBits 24
32
 
#define kTopValue ((UInt32)1 << kNumTopBits)
33
 
 
34
 
#define kNumBitModelTotalBits 11
35
 
#define kBitModelTotal (1 << kNumBitModelTotalBits)
36
 
#define kNumMoveBits 5
37
 
 
38
 
#define RC_INIT_SIZE 5
39
 
 
40
 
#define NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | (*buf++); }
41
 
 
42
 
#define IF_BIT_0(p) ttt = *(p); NORMALIZE; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)
43
 
#define UPDATE_0(p) range = bound; *(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));
44
 
#define UPDATE_1(p) range -= bound; code -= bound; *(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits));
45
 
#define GET_BIT2(p, i, A0, A1) IF_BIT_0(p) \
46
 
  { UPDATE_0(p); i = (i + i); A0; } else \
47
 
  { UPDATE_1(p); i = (i + i) + 1; A1; }
48
 
#define GET_BIT(p, i) GET_BIT2(p, i, ; , ;)
49
 
 
50
 
#define TREE_GET_BIT(probs, i) { GET_BIT((probs + i), i); }
51
 
#define TREE_DECODE(probs, limit, i) \
52
 
  { i = 1; do { TREE_GET_BIT(probs, i); } while (i < limit); i -= limit; }
53
 
 
54
 
/* #define _LZMA_SIZE_OPT */
55
 
 
56
 
#ifdef _LZMA_SIZE_OPT
57
 
#define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i)
58
 
#else
59
 
#define TREE_6_DECODE(probs, i) \
60
 
  { i = 1; \
61
 
  TREE_GET_BIT(probs, i); \
62
 
  TREE_GET_BIT(probs, i); \
63
 
  TREE_GET_BIT(probs, i); \
64
 
  TREE_GET_BIT(probs, i); \
65
 
  TREE_GET_BIT(probs, i); \
66
 
  TREE_GET_BIT(probs, i); \
67
 
  i -= 0x40; }
68
 
#endif
69
 
 
70
 
#define NORMALIZE_CHECK if (range < kTopValue) { if (buf >= bufLimit) return DUMMY_ERROR; range <<= 8; code = (code << 8) | (*buf++); }
71
 
 
72
 
#define IF_BIT_0_CHECK(p) ttt = *(p); NORMALIZE_CHECK; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)
73
 
#define UPDATE_0_CHECK range = bound;
74
 
#define UPDATE_1_CHECK range -= bound; code -= bound;
75
 
#define GET_BIT2_CHECK(p, i, A0, A1) IF_BIT_0_CHECK(p) \
76
 
  { UPDATE_0_CHECK; i = (i + i); A0; } else \
77
 
  { UPDATE_1_CHECK; i = (i + i) + 1; A1; }
78
 
#define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ; , ;)
79
 
#define TREE_DECODE_CHECK(probs, limit, i) \
80
 
  { i = 1; do { GET_BIT_CHECK(probs + i, i) } while(i < limit); i -= limit; }
81
 
 
82
 
 
83
 
#define kNumPosBitsMax 4
84
 
#define kNumPosStatesMax (1 << kNumPosBitsMax)
85
 
 
86
 
#define kLenNumLowBits 3
87
 
#define kLenNumLowSymbols (1 << kLenNumLowBits)
88
 
#define kLenNumMidBits 3
89
 
#define kLenNumMidSymbols (1 << kLenNumMidBits)
90
 
#define kLenNumHighBits 8
91
 
#define kLenNumHighSymbols (1 << kLenNumHighBits)
92
 
 
93
 
#define LenChoice 0
94
 
#define LenChoice2 (LenChoice + 1)
95
 
#define LenLow (LenChoice2 + 1)
96
 
#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
97
 
#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
98
 
#define kNumLenProbs (LenHigh + kLenNumHighSymbols)
99
 
 
100
 
 
101
 
#define kNumStates 12
102
 
#define kNumLitStates 7
103
 
 
104
 
#define kStartPosModelIndex 4
105
 
#define kEndPosModelIndex 14
106
 
#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
107
 
 
108
 
#define kNumPosSlotBits 6
109
 
#define kNumLenToPosStates 4
110
 
 
111
 
#define kNumAlignBits 4
112
 
#define kAlignTableSize (1 << kNumAlignBits)
113
 
 
114
 
#define kMatchMinLen 2
115
 
#define kMatchSpecLenStart (kMatchMinLen + kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)
116
 
 
117
 
#define IsMatch 0
118
 
#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
119
 
#define IsRepG0 (IsRep + kNumStates)
120
 
#define IsRepG1 (IsRepG0 + kNumStates)
121
 
#define IsRepG2 (IsRepG1 + kNumStates)
122
 
#define IsRep0Long (IsRepG2 + kNumStates)
123
 
#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
124
 
#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
125
 
#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
126
 
#define LenCoder (Align + kAlignTableSize)
127
 
#define RepLenCoder (LenCoder + kNumLenProbs)
128
 
#define Literal (RepLenCoder + kNumLenProbs)
129
 
 
130
 
#define LZMA_BASE_SIZE 1846
131
 
#define LZMA_LIT_SIZE 768
132
 
 
133
 
#define LzmaProps_GetNumProbs(p) ((UInt32)LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))
134
 
 
135
 
#if Literal != LZMA_BASE_SIZE
136
 
StopCompilingDueBUG
137
 
#endif
138
 
 
139
 
/*
140
 
#define LZMA_STREAM_WAS_FINISHED_ID (-1)
141
 
#define LZMA_SPEC_LEN_OFFSET (-3)
142
 
*/
143
 
 
144
 
Byte kLiteralNextStates[kNumStates * 2] =
145
 
{
146
 
  0, 0, 0, 0, 1, 2, 3,  4,  5,  6,  4,  5,
147
 
  7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10
148
 
};
149
 
 
150
 
#define LZMA_DIC_MIN (1 << 12)
151
 
 
152
 
/* First LZMA-symbol is always decoded.
153
 
And it decodes new LZMA-symbols while (buf < bufLimit), but "buf" is without last normalization
154
 
Out:
155
 
  Result:
156
 
    0 - OK
157
 
    1 - Error
158
 
  p->remainLen:
159
 
    < kMatchSpecLenStart : normal remain
160
 
    = kMatchSpecLenStart : finished
161
 
    = kMatchSpecLenStart + 1 : Flush marker
162
 
    = kMatchSpecLenStart + 2 : State Init Marker
163
 
*/
164
 
 
165
 
static int MY_FAST_CALL LzmaDec_DecodeReal(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
166
 
{
167
 
  CLzmaProb *probs = p->probs;
168
 
 
169
 
  unsigned state = p->state;
170
 
  UInt32 rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3];
171
 
  unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1;
172
 
  unsigned lpMask = ((unsigned)1 << (p->prop.lp)) - 1;
173
 
  unsigned lc = p->prop.lc;
174
 
 
175
 
  Byte *dic = p->dic;
176
 
  SizeT dicBufSize = p->dicBufSize;
177
 
  SizeT dicPos = p->dicPos;
178
 
 
179
 
  UInt32 processedPos = p->processedPos;
180
 
  UInt32 checkDicSize = p->checkDicSize;
181
 
  unsigned len = 0;
182
 
 
183
 
  const Byte *buf = p->buf;
184
 
  UInt32 range = p->range;
185
 
  UInt32 code = p->code;
186
 
 
187
 
  do
188
 
  {
189
 
    CLzmaProb *prob;
190
 
    UInt32 bound;
191
 
    unsigned ttt;
192
 
    unsigned posState = processedPos & pbMask;
193
 
 
194
 
    prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
195
 
    IF_BIT_0(prob)
196
 
    {
197
 
      unsigned symbol;
198
 
      UPDATE_0(prob);
199
 
      prob = probs + Literal;
200
 
      if (checkDicSize != 0 || processedPos != 0)
201
 
        prob += (LZMA_LIT_SIZE * (((processedPos & lpMask) << lc) +
202
 
        (dic[(dicPos == 0 ? dicBufSize : dicPos) - 1] >> (8 - lc))));
203
 
 
204
 
      if (state < kNumLitStates)
205
 
      {
206
 
        symbol = 1;
207
 
        do { GET_BIT(prob + symbol, symbol) } while (symbol < 0x100);
208
 
      }
209
 
      else
210
 
      {
211
 
        unsigned matchByte = p->dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
212
 
        unsigned offs = 0x100;
213
 
        symbol = 1;
214
 
        do
215
 
        {
216
 
          unsigned bit;
217
 
          CLzmaProb *probLit;
218
 
          matchByte <<= 1;
219
 
          bit = (matchByte & offs);
220
 
          probLit = prob + offs + bit + symbol;
221
 
          GET_BIT2(probLit, symbol, offs &= ~bit, offs &= bit)
222
 
        }
223
 
        while (symbol < 0x100);
224
 
      }
225
 
      dic[dicPos++] = (Byte)symbol;
226
 
      processedPos++;
227
 
 
228
 
      state = kLiteralNextStates[state];
229
 
      /* if (state < 4) state = 0; else if (state < 10) state -= 3; else state -= 6; */
230
 
      continue;
231
 
    }
232
 
    else
233
 
    {
234
 
      UPDATE_1(prob);
235
 
      prob = probs + IsRep + state;
236
 
      IF_BIT_0(prob)
237
 
      {
238
 
        UPDATE_0(prob);
239
 
        state += kNumStates;
240
 
        prob = probs + LenCoder;
241
 
      }
242
 
      else
243
 
      {
244
 
        UPDATE_1(prob);
245
 
        if (checkDicSize == 0 && processedPos == 0)
246
 
          return SZ_ERROR_DATA;
247
 
        prob = probs + IsRepG0 + state;
248
 
        IF_BIT_0(prob)
249
 
        {
250
 
          UPDATE_0(prob);
251
 
          prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
252
 
          IF_BIT_0(prob)
253
 
          {
254
 
            UPDATE_0(prob);
255
 
            dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
256
 
            dicPos++;
257
 
            processedPos++;
258
 
            state = state < kNumLitStates ? 9 : 11;
259
 
            continue;
260
 
          }
261
 
          UPDATE_1(prob);
262
 
        }
263
 
        else
264
 
        {
265
 
          UInt32 distance;
266
 
          UPDATE_1(prob);
267
 
          prob = probs + IsRepG1 + state;
268
 
          IF_BIT_0(prob)
269
 
          {
270
 
            UPDATE_0(prob);
271
 
            distance = rep1;
272
 
          }
273
 
          else
274
 
          {
275
 
            UPDATE_1(prob);
276
 
            prob = probs + IsRepG2 + state;
277
 
            IF_BIT_0(prob)
278
 
            {
279
 
              UPDATE_0(prob);
280
 
              distance = rep2;
281
 
            }
282
 
            else
283
 
            {
284
 
              UPDATE_1(prob);
285
 
              distance = rep3;
286
 
              rep3 = rep2;
287
 
            }
288
 
            rep2 = rep1;
289
 
          }
290
 
          rep1 = rep0;
291
 
          rep0 = distance;
292
 
        }
293
 
        state = state < kNumLitStates ? 8 : 11;
294
 
        prob = probs + RepLenCoder;
295
 
      }
296
 
      {
297
 
        unsigned limit, offset;
298
 
        CLzmaProb *probLen = prob + LenChoice;
299
 
        IF_BIT_0(probLen)
300
 
        {
301
 
          UPDATE_0(probLen);
302
 
          probLen = prob + LenLow + (posState << kLenNumLowBits);
303
 
          offset = 0;
304
 
          limit = (1 << kLenNumLowBits);
305
 
        }
306
 
        else
307
 
        {
308
 
          UPDATE_1(probLen);
309
 
          probLen = prob + LenChoice2;
310
 
          IF_BIT_0(probLen)
311
 
          {
312
 
            UPDATE_0(probLen);
313
 
            probLen = prob + LenMid + (posState << kLenNumMidBits);
314
 
            offset = kLenNumLowSymbols;
315
 
            limit = (1 << kLenNumMidBits);
316
 
          }
317
 
          else
318
 
          {
319
 
            UPDATE_1(probLen);
320
 
            probLen = prob + LenHigh;
321
 
            offset = kLenNumLowSymbols + kLenNumMidSymbols;
322
 
            limit = (1 << kLenNumHighBits);
323
 
          }
324
 
        }
325
 
        TREE_DECODE(probLen, limit, len);
326
 
        len += offset;
327
 
      }
328
 
 
329
 
      if (state >= kNumStates)
330
 
      {
331
 
        UInt32 distance;
332
 
        prob = probs + PosSlot +
333
 
            ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits);
334
 
        TREE_6_DECODE(prob, distance);
335
 
        if (distance >= kStartPosModelIndex)
336
 
        {
337
 
          unsigned posSlot = (unsigned)distance;
338
 
          int numDirectBits = (int)(((distance >> 1) - 1));
339
 
          distance = (2 | (distance & 1));
340
 
          if (posSlot < kEndPosModelIndex)
341
 
          {
342
 
            distance <<= numDirectBits;
343
 
            prob = probs + SpecPos + distance - posSlot - 1;
344
 
            {
345
 
              UInt32 mask = 1;
346
 
              unsigned i = 1;
347
 
              do
348
 
              {
349
 
                GET_BIT2(prob + i, i, ; , distance |= mask);
350
 
                mask <<= 1;
351
 
              }
352
 
              while(--numDirectBits != 0);
353
 
            }
354
 
          }
355
 
          else
356
 
          {
357
 
            numDirectBits -= kNumAlignBits;
358
 
            do
359
 
            {
360
 
              NORMALIZE
361
 
              range >>= 1;
362
 
 
363
 
              {
364
 
                UInt32 t;
365
 
                code -= range;
366
 
                t = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */
367
 
                distance = (distance << 1) + (t + 1);
368
 
                code += range & t;
369
 
              }
370
 
              /*
371
 
              distance <<= 1;
372
 
              if (code >= range)
373
 
              {
374
 
                code -= range;
375
 
                distance |= 1;
376
 
              }
377
 
              */
378
 
            }
379
 
            while (--numDirectBits != 0);
380
 
            prob = probs + Align;
381
 
            distance <<= kNumAlignBits;
382
 
            {
383
 
              unsigned i = 1;
384
 
              GET_BIT2(prob + i, i, ; , distance |= 1);
385
 
              GET_BIT2(prob + i, i, ; , distance |= 2);
386
 
              GET_BIT2(prob + i, i, ; , distance |= 4);
387
 
              GET_BIT2(prob + i, i, ; , distance |= 8);
388
 
            }
389
 
            if (distance == (UInt32)0xFFFFFFFF)
390
 
            {
391
 
              len += kMatchSpecLenStart;
392
 
              state -= kNumStates;
393
 
              break;
394
 
            }
395
 
          }
396
 
        }
397
 
        rep3 = rep2;
398
 
        rep2 = rep1;
399
 
        rep1 = rep0;
400
 
        rep0 = distance + 1;
401
 
        if (checkDicSize == 0)
402
 
        {
403
 
          if (distance >= processedPos)
404
 
            return SZ_ERROR_DATA;
405
 
        }
406
 
        else if (distance >= checkDicSize)
407
 
          return SZ_ERROR_DATA;
408
 
        state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3;
409
 
        /* state = kLiteralNextStates[state]; */
410
 
      }
411
 
 
412
 
      len += kMatchMinLen;
413
 
 
414
 
      {
415
 
        SizeT rem = limit - dicPos;
416
 
        unsigned curLen = ((rem < len) ? (unsigned)rem : len);
417
 
        SizeT pos = (dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0);
418
 
 
419
 
        processedPos += curLen;
420
 
 
421
 
        len -= curLen;
422
 
        if (pos + curLen <= dicBufSize)
423
 
        {
424
 
          Byte *dest = dic + dicPos;
425
 
          ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos;
426
 
          const Byte *lim = dest + curLen;
427
 
          dicPos += curLen;
428
 
          do
429
 
            *(dest) = (Byte)*(dest + src);
430
 
          while (++dest != lim);
431
 
        }
432
 
        else
433
 
        {
434
 
          do
435
 
          {
436
 
            dic[dicPos++] = dic[pos];
437
 
            if (++pos == dicBufSize)
438
 
              pos = 0;
439
 
          }
440
 
          while (--curLen != 0);
441
 
        }
442
 
      }
443
 
    }
444
 
  }
445
 
  while (dicPos < limit && buf < bufLimit);
446
 
  NORMALIZE;
447
 
  p->buf = buf;
448
 
  p->range = range;
449
 
  p->code = code;
450
 
  p->remainLen = len;
451
 
  p->dicPos = dicPos;
452
 
  p->processedPos = processedPos;
453
 
  p->reps[0] = rep0;
454
 
  p->reps[1] = rep1;
455
 
  p->reps[2] = rep2;
456
 
  p->reps[3] = rep3;
457
 
  p->state = state;
458
 
 
459
 
  return SZ_OK;
460
 
}
461
 
 
462
 
static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit)
463
 
{
464
 
  if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart)
465
 
  {
466
 
    Byte *dic = p->dic;
467
 
    SizeT dicPos = p->dicPos;
468
 
    SizeT dicBufSize = p->dicBufSize;
469
 
    unsigned len = p->remainLen;
470
 
    UInt32 rep0 = p->reps[0];
471
 
    if (limit - dicPos < len)
472
 
      len = (unsigned)(limit - dicPos);
473
 
 
474
 
    if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len)
475
 
      p->checkDicSize = p->prop.dicSize;
476
 
 
477
 
    p->processedPos += len;
478
 
    p->remainLen -= len;
479
 
    while (len-- != 0)
480
 
    {
481
 
      dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
482
 
      dicPos++;
483
 
    }
484
 
    p->dicPos = dicPos;
485
 
  }
486
 
}
487
 
 
488
 
/* LzmaDec_DecodeReal2 decodes LZMA-symbols and sets p->needFlush and p->needInit, if required. */
489
 
 
490
 
static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
491
 
{
492
 
  do
493
 
  {
494
 
    SizeT limit2 = limit;
495
 
    if (p->checkDicSize == 0)
496
 
    {
497
 
      UInt32 rem = p->prop.dicSize - p->processedPos;
498
 
      if (limit - p->dicPos > rem)
499
 
        limit2 = p->dicPos + rem;
500
 
    }
501
 
    RINOK(LzmaDec_DecodeReal(p, limit2, bufLimit));
502
 
    if (p->processedPos >= p->prop.dicSize)
503
 
      p->checkDicSize = p->prop.dicSize;
504
 
    LzmaDec_WriteRem(p, limit);
505
 
  }
506
 
  while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart);
507
 
 
508
 
  if (p->remainLen > kMatchSpecLenStart)
509
 
  {
510
 
    p->remainLen = kMatchSpecLenStart;
511
 
  }
512
 
  return 0;
513
 
}
514
 
 
515
 
typedef enum
516
 
{
517
 
  DUMMY_ERROR, /* unexpected end of input stream */
518
 
  DUMMY_LIT,
519
 
  DUMMY_MATCH,
520
 
  DUMMY_REP
521
 
} ELzmaDummy;
522
 
 
523
 
static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, SizeT inSize)
524
 
{
525
 
  UInt32 range = p->range;
526
 
  UInt32 code = p->code;
527
 
  const Byte *bufLimit = buf + inSize;
528
 
  CLzmaProb *probs = p->probs;
529
 
  unsigned state = p->state;
530
 
  ELzmaDummy res;
531
 
 
532
 
  {
533
 
    CLzmaProb *prob;
534
 
    UInt32 bound;
535
 
    unsigned ttt;
536
 
    unsigned posState = (p->processedPos) & ((1 << p->prop.pb) - 1);
537
 
 
538
 
    prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
539
 
    IF_BIT_0_CHECK(prob)
540
 
    {
541
 
      UPDATE_0_CHECK
542
 
 
543
 
      /* if (bufLimit - buf >= 7) return DUMMY_LIT; */
544
 
 
545
 
      prob = probs + Literal;
546
 
      if (p->checkDicSize != 0 || p->processedPos != 0)
547
 
        prob += (LZMA_LIT_SIZE *
548
 
          ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) +
549
 
          (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc))));
550
 
 
551
 
      if (state < kNumLitStates)
552
 
      {
553
 
        unsigned symbol = 1;
554
 
        do { GET_BIT_CHECK(prob + symbol, symbol) } while (symbol < 0x100);
555
 
      }
556
 
      else
557
 
      {
558
 
        unsigned matchByte = p->dic[p->dicPos - p->reps[0] +
559
 
            ((p->dicPos < p->reps[0]) ? p->dicBufSize : 0)];
560
 
        unsigned offs = 0x100;
561
 
        unsigned symbol = 1;
562
 
        do
563
 
        {
564
 
          unsigned bit;
565
 
          CLzmaProb *probLit;
566
 
          matchByte <<= 1;
567
 
          bit = (matchByte & offs);
568
 
          probLit = prob + offs + bit + symbol;
569
 
          GET_BIT2_CHECK(probLit, symbol, offs &= ~bit, offs &= bit)
570
 
        }
571
 
        while (symbol < 0x100);
572
 
      }
573
 
      res = DUMMY_LIT;
574
 
    }
575
 
    else
576
 
    {
577
 
      unsigned len;
578
 
      UPDATE_1_CHECK;
579
 
 
580
 
      prob = probs + IsRep + state;
581
 
      IF_BIT_0_CHECK(prob)
582
 
      {
583
 
        UPDATE_0_CHECK;
584
 
        state = 0;
585
 
        prob = probs + LenCoder;
586
 
        res = DUMMY_MATCH;
587
 
      }
588
 
      else
589
 
      {
590
 
        UPDATE_1_CHECK;
591
 
        res = DUMMY_REP;
592
 
        prob = probs + IsRepG0 + state;
593
 
        IF_BIT_0_CHECK(prob)
594
 
        {
595
 
          UPDATE_0_CHECK;
596
 
          prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
597
 
          IF_BIT_0_CHECK(prob)
598
 
          {
599
 
            UPDATE_0_CHECK;
600
 
            NORMALIZE_CHECK;
601
 
            return DUMMY_REP;
602
 
          }
603
 
          else
604
 
          {
605
 
            UPDATE_1_CHECK;
606
 
          }
607
 
        }
608
 
        else
609
 
        {
610
 
          UPDATE_1_CHECK;
611
 
          prob = probs + IsRepG1 + state;
612
 
          IF_BIT_0_CHECK(prob)
613
 
          {
614
 
            UPDATE_0_CHECK;
615
 
          }
616
 
          else
617
 
          {
618
 
            UPDATE_1_CHECK;
619
 
            prob = probs + IsRepG2 + state;
620
 
            IF_BIT_0_CHECK(prob)
621
 
            {
622
 
              UPDATE_0_CHECK;
623
 
            }
624
 
            else
625
 
            {
626
 
              UPDATE_1_CHECK;
627
 
            }
628
 
          }
629
 
        }
630
 
        state = kNumStates;
631
 
        prob = probs + RepLenCoder;
632
 
      }
633
 
      {
634
 
        unsigned limit, offset;
635
 
        CLzmaProb *probLen = prob + LenChoice;
636
 
        IF_BIT_0_CHECK(probLen)
637
 
        {
638
 
          UPDATE_0_CHECK;
639
 
          probLen = prob + LenLow + (posState << kLenNumLowBits);
640
 
          offset = 0;
641
 
          limit = 1 << kLenNumLowBits;
642
 
        }
643
 
        else
644
 
        {
645
 
          UPDATE_1_CHECK;
646
 
          probLen = prob + LenChoice2;
647
 
          IF_BIT_0_CHECK(probLen)
648
 
          {
649
 
            UPDATE_0_CHECK;
650
 
            probLen = prob + LenMid + (posState << kLenNumMidBits);
651
 
            offset = kLenNumLowSymbols;
652
 
            limit = 1 << kLenNumMidBits;
653
 
          }
654
 
          else
655
 
          {
656
 
            UPDATE_1_CHECK;
657
 
            probLen = prob + LenHigh;
658
 
            offset = kLenNumLowSymbols + kLenNumMidSymbols;
659
 
            limit = 1 << kLenNumHighBits;
660
 
          }
661
 
        }
662
 
        TREE_DECODE_CHECK(probLen, limit, len);
663
 
        len += offset;
664
 
      }
665
 
 
666
 
      if (state < 4)
667
 
      {
668
 
        unsigned posSlot;
669
 
        prob = probs + PosSlot +
670
 
            ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
671
 
            kNumPosSlotBits);
672
 
        TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot);
673
 
        if (posSlot >= kStartPosModelIndex)
674
 
        {
675
 
          int numDirectBits = ((posSlot >> 1) - 1);
676
 
 
677
 
          /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */
678
 
 
679
 
          if (posSlot < kEndPosModelIndex)
680
 
          {
681
 
            prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits) - posSlot - 1;
682
 
          }
683
 
          else
684
 
          {
685
 
            numDirectBits -= kNumAlignBits;
686
 
            do
687
 
            {
688
 
              NORMALIZE_CHECK
689
 
              range >>= 1;
690
 
              code -= range & (((code - range) >> 31) - 1);
691
 
              /* if (code >= range) code -= range; */
692
 
            }
693
 
            while (--numDirectBits != 0);
694
 
            prob = probs + Align;
695
 
            numDirectBits = kNumAlignBits;
696
 
          }
697
 
          {
698
 
            unsigned i = 1;
699
 
            do
700
 
            {
701
 
              GET_BIT_CHECK(prob + i, i);
702
 
            }
703
 
            while(--numDirectBits != 0);
704
 
          }
705
 
        }
706
 
      }
707
 
    }
708
 
  }
709
 
  NORMALIZE_CHECK;
710
 
  return res;
711
 
}
712
 
 
713
 
 
714
 
static void LzmaDec_InitRc(CLzmaDec *p, const Byte *data)
715
 
{
716
 
  p->code = ((UInt32)data[1] << 24) | ((UInt32)data[2] << 16) | ((UInt32)data[3] << 8) | ((UInt32)data[4]);
717
 
  p->range = 0xFFFFFFFF;
718
 
  p->needFlush = 0;
719
 
}
720
 
 
721
 
void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState)
722
 
{
723
 
  p->needFlush = 1;
724
 
  p->remainLen = 0;
725
 
  p->tempBufSize = 0;
726
 
 
727
 
  if (initDic)
728
 
  {
729
 
    p->processedPos = 0;
730
 
    p->checkDicSize = 0;
731
 
    p->needInitState = 1;
732
 
  }
733
 
  if (initState)
734
 
    p->needInitState = 1;
735
 
}
736
 
 
737
 
void LzmaDec_Init(CLzmaDec *p)
738
 
{
739
 
  p->dicPos = 0;
740
 
  LzmaDec_InitDicAndState(p, True, True);
741
 
}
742
 
 
743
 
static void LzmaDec_InitStateReal(CLzmaDec *p)
744
 
{
745
 
  UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (p->prop.lc + p->prop.lp));
746
 
  UInt32 i;
747
 
  CLzmaProb *probs = p->probs;
748
 
  for (i = 0; i < numProbs; i++)
749
 
    probs[i] = kBitModelTotal >> 1;
750
 
  p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1;
751
 
  p->state = 0;
752
 
  p->needInitState = 0;
753
 
}
754
 
 
755
 
SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen,
756
 
    ELzmaFinishMode finishMode, ELzmaStatus *status)
757
 
{
758
 
  SizeT inSize = *srcLen;
759
 
  (*srcLen) = 0;
760
 
  LzmaDec_WriteRem(p, dicLimit);
761
 
 
762
 
  *status = LZMA_STATUS_NOT_SPECIFIED;
763
 
 
764
 
  while (p->remainLen != kMatchSpecLenStart)
765
 
  {
766
 
      int checkEndMarkNow;
767
 
 
768
 
      if (p->needFlush != 0)
769
 
      {
770
 
        for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--)
771
 
          p->tempBuf[p->tempBufSize++] = *src++;
772
 
        if (p->tempBufSize < RC_INIT_SIZE)
773
 
        {
774
 
          *status = LZMA_STATUS_NEEDS_MORE_INPUT;
775
 
          return SZ_OK;
776
 
        }
777
 
        if (p->tempBuf[0] != 0)
778
 
          return SZ_ERROR_DATA;
779
 
 
780
 
        LzmaDec_InitRc(p, p->tempBuf);
781
 
        p->tempBufSize = 0;
782
 
      }
783
 
 
784
 
      checkEndMarkNow = 0;
785
 
      if (p->dicPos >= dicLimit)
786
 
      {
787
 
        if (p->remainLen == 0 && p->code == 0)
788
 
        {
789
 
          *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK;
790
 
          return SZ_OK;
791
 
        }
792
 
        if (finishMode == LZMA_FINISH_ANY)
793
 
        {
794
 
          *status = LZMA_STATUS_NOT_FINISHED;
795
 
          return SZ_OK;
796
 
        }
797
 
        if (p->remainLen != 0)
798
 
        {
799
 
          *status = LZMA_STATUS_NOT_FINISHED;
800
 
          return SZ_ERROR_DATA;
801
 
        }
802
 
        checkEndMarkNow = 1;
803
 
      }
804
 
 
805
 
      if (p->needInitState)
806
 
        LzmaDec_InitStateReal(p);
807
 
 
808
 
      if (p->tempBufSize == 0)
809
 
      {
810
 
        SizeT processed;
811
 
        const Byte *bufLimit;
812
 
        if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
813
 
        {
814
 
          int dummyRes = LzmaDec_TryDummy(p, src, inSize);
815
 
          if (dummyRes == DUMMY_ERROR)
816
 
          {
817
 
            memcpy(p->tempBuf, src, inSize);
818
 
            p->tempBufSize = (unsigned)inSize;
819
 
            (*srcLen) += inSize;
820
 
            *status = LZMA_STATUS_NEEDS_MORE_INPUT;
821
 
            return SZ_OK;
822
 
          }
823
 
          if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
824
 
          {
825
 
            *status = LZMA_STATUS_NOT_FINISHED;
826
 
            return SZ_ERROR_DATA;
827
 
          }
828
 
          bufLimit = src;
829
 
        }
830
 
        else
831
 
          bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX;
832
 
        p->buf = src;
833
 
        if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0)
834
 
          return SZ_ERROR_DATA;
835
 
        processed = p->buf - src;
836
 
        (*srcLen) += processed;
837
 
        src += processed;
838
 
        inSize -= processed;
839
 
      }
840
 
      else
841
 
      {
842
 
        unsigned rem = p->tempBufSize, lookAhead = 0;
843
 
        while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize)
844
 
          p->tempBuf[rem++] = src[lookAhead++];
845
 
        p->tempBufSize = rem;
846
 
        if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
847
 
        {
848
 
          int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem);
849
 
          if (dummyRes == DUMMY_ERROR)
850
 
          {
851
 
            (*srcLen) += lookAhead;
852
 
            *status = LZMA_STATUS_NEEDS_MORE_INPUT;
853
 
            return SZ_OK;
854
 
          }
855
 
          if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
856
 
          {
857
 
            *status = LZMA_STATUS_NOT_FINISHED;
858
 
            return SZ_ERROR_DATA;
859
 
          }
860
 
        }
861
 
        p->buf = p->tempBuf;
862
 
        if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0)
863
 
          return SZ_ERROR_DATA;
864
 
        lookAhead -= (rem - (unsigned)(p->buf - p->tempBuf));
865
 
        (*srcLen) += lookAhead;
866
 
        src += lookAhead;
867
 
        inSize -= lookAhead;
868
 
        p->tempBufSize = 0;
869
 
      }
870
 
  }
871
 
  if (p->code == 0)
872
 
    *status = LZMA_STATUS_FINISHED_WITH_MARK;
873
 
  return (p->code == 0) ? SZ_OK : SZ_ERROR_DATA;
874
 
}
875
 
 
876
 
SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status)
877
 
{
878
 
  SizeT outSize = *destLen;
879
 
  SizeT inSize = *srcLen;
880
 
  *srcLen = *destLen = 0;
881
 
  for (;;)
882
 
  {
883
 
    SizeT inSizeCur = inSize, outSizeCur, dicPos;
884
 
    ELzmaFinishMode curFinishMode;
885
 
    SRes res;
886
 
    if (p->dicPos == p->dicBufSize)
887
 
      p->dicPos = 0;
888
 
    dicPos = p->dicPos;
889
 
    if (outSize > p->dicBufSize - dicPos)
890
 
    {
891
 
      outSizeCur = p->dicBufSize;
892
 
      curFinishMode = LZMA_FINISH_ANY;
893
 
    }
894
 
    else
895
 
    {
896
 
      outSizeCur = dicPos + outSize;
897
 
      curFinishMode = finishMode;
898
 
    }
899
 
 
900
 
    res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status);
901
 
    src += inSizeCur;
902
 
    inSize -= inSizeCur;
903
 
    *srcLen += inSizeCur;
904
 
    outSizeCur = p->dicPos - dicPos;
905
 
    memcpy(dest, p->dic + dicPos, outSizeCur);
906
 
    dest += outSizeCur;
907
 
    outSize -= outSizeCur;
908
 
    *destLen += outSizeCur;
909
 
    if (res != 0)
910
 
      return res;
911
 
    if (outSizeCur == 0 || outSize == 0)
912
 
      return SZ_OK;
913
 
  }
914
 
}
915
 
 
916
 
void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc)
917
 
{
918
 
  alloc->Free(alloc, p->probs);
919
 
  p->probs = 0;
920
 
}
921
 
 
922
 
static void LzmaDec_FreeDict(CLzmaDec *p, ISzAlloc *alloc)
923
 
{
924
 
  alloc->Free(alloc, p->dic);
925
 
  p->dic = 0;
926
 
}
927
 
 
928
 
void LzmaDec_Free(CLzmaDec *p, ISzAlloc *alloc)
929
 
{
930
 
  LzmaDec_FreeProbs(p, alloc);
931
 
  LzmaDec_FreeDict(p, alloc);
932
 
}
933
 
 
934
 
SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size)
935
 
{
936
 
  UInt32 dicSize;
937
 
  Byte d;
938
 
 
939
 
  if (size < LZMA_PROPS_SIZE)
940
 
    return SZ_ERROR_UNSUPPORTED;
941
 
  else
942
 
    dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24);
943
 
 
944
 
  if (dicSize < LZMA_DIC_MIN)
945
 
    dicSize = LZMA_DIC_MIN;
946
 
  p->dicSize = dicSize;
947
 
 
948
 
  d = data[0];
949
 
  if (d >= (9 * 5 * 5))
950
 
    return SZ_ERROR_UNSUPPORTED;
951
 
 
952
 
  p->lc = d % 9;
953
 
  d /= 9;
954
 
  p->pb = d / 5;
955
 
  p->lp = d % 5;
956
 
 
957
 
  return SZ_OK;
958
 
}
959
 
 
960
 
static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAlloc *alloc)
961
 
{
962
 
  UInt32 numProbs = LzmaProps_GetNumProbs(propNew);
963
 
  if (p->probs == 0 || numProbs != p->numProbs)
964
 
  {
965
 
    LzmaDec_FreeProbs(p, alloc);
966
 
    p->probs = (CLzmaProb *)alloc->Alloc(alloc, numProbs * sizeof(CLzmaProb));
967
 
    p->numProbs = numProbs;
968
 
    if (p->probs == 0)
969
 
      return SZ_ERROR_MEM;
970
 
  }
971
 
  return SZ_OK;
972
 
}
973
 
 
974
 
SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
975
 
{
976
 
  CLzmaProps propNew;
977
 
  RINOK(LzmaProps_Decode(&propNew, props, propsSize));
978
 
  RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
979
 
  p->prop = propNew;
980
 
  return SZ_OK;
981
 
}
982
 
 
983
 
SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
984
 
{
985
 
  CLzmaProps propNew;
986
 
  SizeT dicBufSize;
987
 
  RINOK(LzmaProps_Decode(&propNew, props, propsSize));
988
 
  RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
989
 
  dicBufSize = propNew.dicSize;
990
 
  if (p->dic == 0 || dicBufSize != p->dicBufSize)
991
 
  {
992
 
    LzmaDec_FreeDict(p, alloc);
993
 
    p->dic = (Byte *)alloc->Alloc(alloc, dicBufSize);
994
 
    if (p->dic == 0)
995
 
    {
996
 
      LzmaDec_FreeProbs(p, alloc);
997
 
      return SZ_ERROR_MEM;
998
 
    }
999
 
  }
1000
 
  p->dicBufSize = dicBufSize;
1001
 
  p->prop = propNew;
1002
 
  return SZ_OK;
1003
 
}
1004
 
 
1005
 
SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
1006
 
    const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,
1007
 
    ELzmaStatus *status, ISzAlloc *alloc)
1008
 
{
1009
 
  CLzmaDec p;
1010
 
  SRes res;
1011
 
  SizeT inSize = *srcLen;
1012
 
  SizeT outSize = *destLen;
1013
 
  *srcLen = *destLen = 0;
1014
 
  if (inSize < RC_INIT_SIZE)
1015
 
    return SZ_ERROR_INPUT_EOF;
1016
 
 
1017
 
  LzmaDec_Construct(&p);
1018
 
  res = LzmaDec_AllocateProbs(&p, propData, propSize, alloc);
1019
 
  if (res != 0)
1020
 
    return res;
1021
 
  p.dic = dest;
1022
 
  p.dicBufSize = outSize;
1023
 
 
1024
 
  LzmaDec_Init(&p);
1025
 
 
1026
 
  *srcLen = inSize;
1027
 
  res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status);
1028
 
 
1029
 
  if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT)
1030
 
    res = SZ_ERROR_INPUT_EOF;
1031
 
 
1032
 
  (*destLen) = p.dicPos;
1033
 
  LzmaDec_FreeProbs(&p, alloc);
1034
 
  return res;
1035
 
}