ReggeGribovPartonMCInterface/src/LzmaDec.cc

0001 /* LzmaDec.c -- LZMA Decoder

0002 2009-09-20 : Igor Pavlov : Public domain */
0003
0004 #include "LzmaDec.h"
0005
0006 #include <cstring>
0007
0008 #define kNumTopBits 24
0009 #define kTopValue ((UInt32)1 << kNumTopBits)
0010
0011 #define kNumBitModelTotalBits 11
0012 #define kBitModelTotal (1 << kNumBitModelTotalBits)
0013 #define kNumMoveBits 5
0014
0015 #define RC_INIT_SIZE 5
0016
0017 #define NORMALIZE                  \
0018   if (range < kTopValue) {         \
0019     range <<= 8;                   \
0020     code = (code << 8) | (*buf++); \
0021   }
0022
0023 #define IF_BIT_0(p)                               \
0024   ttt = *(p);                                     \
0025   NORMALIZE;                                      \
0026   bound = (range >> kNumBitModelTotalBits) * ttt; \
0027   if (code < bound)
0028 #define UPDATE_0(p) \
0029   range = bound;    \
0030   *(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));
0031 #define UPDATE_1(p) \
0032   range -= bound;   \
0033   code -= bound;    \
0034   *(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits));
0035 #define GET_BIT2(p, i, A0, A1) \
0036   IF_BIT_0(p) {                \
0037     UPDATE_0(p);               \
0038     i = (i + i);               \
0039     A0;                        \
0040   }                            \
0041   else {                       \
0042     UPDATE_1(p);               \
0043     i = (i + i) + 1;           \
0044     A1;                        \
0045   }
0046 #define GET_BIT(p, i) GET_BIT2(p, i, ;, ;)
0047
0048 #define TREE_GET_BIT(probs, i) \
0049   { GET_BIT((probs + i), i); }
0050 #define TREE_DECODE(probs, limit, i) \
0051   {                                  \
0052     i = 1;                           \
0053     do {                             \
0054       TREE_GET_BIT(probs, i);        \
0055     } while (i < limit);             \
0056     i -= limit;                      \
0057   }
0058
0059 /* #define _LZMA_SIZE_OPT */
0060
0061 #ifdef _LZMA_SIZE_OPT
0062 #define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i)
0063 #else
0064 #define TREE_6_DECODE(probs, i) \
0065   {                             \
0066     i = 1;                      \
0067     TREE_GET_BIT(probs, i);     \
0068     TREE_GET_BIT(probs, i);     \
0069     TREE_GET_BIT(probs, i);     \
0070     TREE_GET_BIT(probs, i);     \
0071     TREE_GET_BIT(probs, i);     \
0072     TREE_GET_BIT(probs, i);     \
0073     i -= 0x40;                  \
0074   }
0075 #endif
0076
0077 #define NORMALIZE_CHECK            \
0078   if (range < kTopValue) {         \
0079     if (buf >= bufLimit)           \
0080       return DUMMY_ERROR;          \
0081     range <<= 8;                   \
0082     code = (code << 8) | (*buf++); \
0083   }
0084
0085 #define IF_BIT_0_CHECK(p)                         \
0086   ttt = *(p);                                     \
0087   NORMALIZE_CHECK;                                \
0088   bound = (range >> kNumBitModelTotalBits) * ttt; \
0089   if (code < bound)
0090 #define UPDATE_0_CHECK range = bound;
0091 #define UPDATE_1_CHECK \
0092   range -= bound;      \
0093   code -= bound;
0094 #define GET_BIT2_CHECK(p, i, A0, A1) \
0095   IF_BIT_0_CHECK(p) {                \
0096     UPDATE_0_CHECK;                  \
0097     i = (i + i);                     \
0098     A0;                              \
0099   }                                  \
0100   else {                             \
0101     UPDATE_1_CHECK;                  \
0102     i = (i + i) + 1;                 \
0103     A1;                              \
0104   }
0105 #define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ;, ;)
0106 #define TREE_DECODE_CHECK(probs, limit, i) \
0107   {                                        \
0108     i = 1;                                 \
0109     do {                                   \
0110       GET_BIT_CHECK(probs + i, i)          \
0111     } while (i < limit);                   \
0112     i -= limit;                            \
0113   }
0114
0115 #define kNumPosBitsMax 4
0116 #define kNumPosStatesMax (1 << kNumPosBitsMax)
0117
0118 #define kLenNumLowBits 3
0119 #define kLenNumLowSymbols (1 << kLenNumLowBits)
0120 #define kLenNumMidBits 3
0121 #define kLenNumMidSymbols (1 << kLenNumMidBits)
0122 #define kLenNumHighBits 8
0123 #define kLenNumHighSymbols (1 << kLenNumHighBits)
0124
0125 #define LenChoice 0
0126 #define LenChoice2 (LenChoice + 1)
0127 #define LenLow (LenChoice2 + 1)
0128 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
0129 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
0130 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
0131
0132 #define kNumStates 12
0133 #define kNumLitStates 7
0134
0135 #define kStartPosModelIndex 4
0136 #define kEndPosModelIndex 14
0137 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
0138
0139 #define kNumPosSlotBits 6
0140 #define kNumLenToPosStates 4
0141
0142 #define kNumAlignBits 4
0143 #define kAlignTableSize (1 << kNumAlignBits)
0144
0145 #define kMatchMinLen 2
0146 #define kMatchSpecLenStart (kMatchMinLen + kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)
0147
0148 #define IsMatch 0
0149 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
0150 #define IsRepG0 (IsRep + kNumStates)
0151 #define IsRepG1 (IsRepG0 + kNumStates)
0152 #define IsRepG2 (IsRepG1 + kNumStates)
0153 #define IsRep0Long (IsRepG2 + kNumStates)
0154 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
0155 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
0156 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
0157 #define LenCoder (Align + kAlignTableSize)
0158 #define RepLenCoder (LenCoder + kNumLenProbs)
0159 #define Literal (RepLenCoder + kNumLenProbs)
0160
0161 #define LZMA_BASE_SIZE 1846
0162 #define LZMA_LIT_SIZE 768
0163
0164 #define LzmaProps_GetNumProbs(p) ((UInt32)LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))
0165
0166 #if Literal != LZMA_BASE_SIZE
0167 StopCompilingDueBUG
0168 #endif
0169
0170 #define LZMA_DIC_MIN (1 << 12)
0171
0172     /* First LZMA-symbol is always decoded.

0173 And it decodes new LZMA-symbols while (buf < bufLimit), but "buf" is without last normalization

0174 Out:

0175   Result:

0176     SZ_OK - OK

0177     SZ_ERROR_DATA - Error

0178   p->remainLen:

0179     < kMatchSpecLenStart : normal remain

0180     = kMatchSpecLenStart : finished

0181     = kMatchSpecLenStart + 1 : Flush marker

0182     = kMatchSpecLenStart + 2 : State Init Marker

0183 */
0184
0185     static int MY_FAST_CALL
0186     LzmaDec_DecodeReal(CLzmaDec *p, SizeT limit, const Byte *bufLimit) {
0187   CLzmaProb *probs = p->probs;
0188
0189   unsigned state = p->state;
0190   UInt32 rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3];
0191   unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1;
0192   unsigned lpMask = ((unsigned)1 << (p->prop.lp)) - 1;
0193   unsigned lc = p->prop.lc;
0194
0195   Byte *dic = p->dic;
0196   SizeT dicBufSize = p->dicBufSize;
0197   SizeT dicPos = p->dicPos;
0198
0199   UInt32 processedPos = p->processedPos;
0200   UInt32 checkDicSize = p->checkDicSize;
0201   unsigned len = 0;
0202
0203   const Byte *buf = p->buf;
0204   UInt32 range = p->range;
0205   UInt32 code = p->code;
0206
0207   do {
0208     CLzmaProb *prob;
0209     UInt32 bound;
0210     unsigned ttt;
0211     unsigned posState = processedPos & pbMask;
0212
0213     prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
0214     IF_BIT_0(prob) {
0215       unsigned symbol;
0216       UPDATE_0(prob);
0217       prob = probs + Literal;
0218       if (checkDicSize != 0 || processedPos != 0)
0219         prob += (LZMA_LIT_SIZE *
0220                  (((processedPos & lpMask) << lc) + (dic[(dicPos == 0 ? dicBufSize : dicPos) - 1] >> (8 - lc))));
0221
0222       if (state < kNumLitStates) {
0223         state -= (state < 4) ? state : 3;
0224         symbol = 1;
0225         do {
0226           GET_BIT(prob + symbol, symbol)
0227         } while (symbol < 0x100);
0228       } else {
0229         unsigned matchByte = p->dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
0230         unsigned offs = 0x100;
0231         state -= (state < 10) ? 3 : 6;
0232         symbol = 1;
0233         do {
0234           unsigned bit;
0235           CLzmaProb *probLit;
0236           matchByte <<= 1;
0237           bit = (matchByte & offs);
0238           probLit = prob + offs + bit + symbol;
0239           GET_BIT2(probLit, symbol, offs &= ~bit, offs &= bit)
0240         } while (symbol < 0x100);
0241       }
0242       dic[dicPos++] = (Byte)symbol;
0243       processedPos++;
0244       continue;
0245     }
0246     else {
0247       UPDATE_1(prob);
0248       prob = probs + IsRep + state;
0249       IF_BIT_0(prob) {
0250         UPDATE_0(prob);
0251         state += kNumStates;
0252         prob = probs + LenCoder;
0253       }
0254       else {
0255         UPDATE_1(prob);
0256         if (checkDicSize == 0 && processedPos == 0)
0257           return SZ_ERROR_DATA;
0258         prob = probs + IsRepG0 + state;
0259         IF_BIT_0(prob) {
0260           UPDATE_0(prob);
0261           prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
0262           IF_BIT_0(prob) {
0263             UPDATE_0(prob);
0264             dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
0265             dicPos++;
0266             processedPos++;
0267             state = state < kNumLitStates ? 9 : 11;
0268             continue;
0269           }
0270           UPDATE_1(prob);
0271         }
0272         else {
0273           UInt32 distance;
0274           UPDATE_1(prob);
0275           prob = probs + IsRepG1 + state;
0276           IF_BIT_0(prob) {
0277             UPDATE_0(prob);
0278             distance = rep1;
0279           }
0280           else {
0281             UPDATE_1(prob);
0282             prob = probs + IsRepG2 + state;
0283             IF_BIT_0(prob) {
0284               UPDATE_0(prob);
0285               distance = rep2;
0286             }
0287             else {
0288               UPDATE_1(prob);
0289               distance = rep3;
0290               rep3 = rep2;
0291             }
0292             rep2 = rep1;
0293           }
0294           rep1 = rep0;
0295           rep0 = distance;
0296         }
0297         state = state < kNumLitStates ? 8 : 11;
0298         prob = probs + RepLenCoder;
0299       }
0300       {
0301         unsigned limit, offset;
0302         CLzmaProb *probLen = prob + LenChoice;
0303         IF_BIT_0(probLen) {
0304           UPDATE_0(probLen);
0305           probLen = prob + LenLow + (posState << kLenNumLowBits);
0306           offset = 0;
0307           limit = (1 << kLenNumLowBits);
0308         }
0309         else {
0310           UPDATE_1(probLen);
0311           probLen = prob + LenChoice2;
0312           IF_BIT_0(probLen) {
0313             UPDATE_0(probLen);
0314             probLen = prob + LenMid + (posState << kLenNumMidBits);
0315             offset = kLenNumLowSymbols;
0316             limit = (1 << kLenNumMidBits);
0317           }
0318           else {
0319             UPDATE_1(probLen);
0320             probLen = prob + LenHigh;
0321             offset = kLenNumLowSymbols + kLenNumMidSymbols;
0322             limit = (1 << kLenNumHighBits);
0323           }
0324         }
0325         TREE_DECODE(probLen, limit, len);
0326         len += offset;
0327       }
0328
0329       if (state >= kNumStates) {
0330         UInt32 distance;
0331         prob = probs + PosSlot + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits);
0332         TREE_6_DECODE(prob, distance);
0333         if (distance >= kStartPosModelIndex) {
0334           unsigned posSlot = (unsigned)distance;
0335           int numDirectBits = (int)(((distance >> 1) - 1));
0336           distance = (2 | (distance & 1));
0337           if (posSlot < kEndPosModelIndex) {
0338             distance <<= numDirectBits;
0339             prob = probs + SpecPos + distance - posSlot - 1;
0340             {
0341               UInt32 mask = 1;
0342               unsigned i = 1;
0343               do {
0344                 GET_BIT2(prob + i, i, ;, distance |= mask);
0345                 mask <<= 1;
0346               } while (--numDirectBits != 0);
0347             }
0348           } else {
0349             numDirectBits -= kNumAlignBits;
0350             do {
0351               NORMALIZE
0352               range >>= 1;
0353
0354               {
0355                 UInt32 t;
0356                 code -= range;
0357                 t = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */
0358                 distance = (distance << 1) + (t + 1);
0359                 code += range & t;
0360               }
0361               /*

0362               distance <<= 1;

0363               if (code >= range)

0364               {

0365                 code -= range;

0366                 distance |= 1;

0367               }

0368               */
0369             } while (--numDirectBits != 0);
0370             prob = probs + Align;
0371             distance <<= kNumAlignBits;
0372             {
0373               unsigned i = 1;
0374               GET_BIT2(prob + i, i, ;, distance |= 1);
0375               GET_BIT2(prob + i, i, ;, distance |= 2);
0376               GET_BIT2(prob + i, i, ;, distance |= 4);
0377               GET_BIT2(prob + i, i, ;, distance |= 8);
0378             }
0379             if (distance == (UInt32)0xFFFFFFFF) {
0380               len += kMatchSpecLenStart;
0381               state -= kNumStates;
0382               break;
0383             }
0384           }
0385         }
0386         rep3 = rep2;
0387         rep2 = rep1;
0388         rep1 = rep0;
0389         rep0 = distance + 1;
0390         if (checkDicSize == 0) {
0391           if (distance >= processedPos)
0392             return SZ_ERROR_DATA;
0393         } else if (distance >= checkDicSize)
0394           return SZ_ERROR_DATA;
0395         state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3;
0396       }
0397
0398       len += kMatchMinLen;
0399
0400       if (limit == dicPos)
0401         return SZ_ERROR_DATA;
0402       {
0403         SizeT rem = limit - dicPos;
0404         unsigned curLen = ((rem < len) ? (unsigned)rem : len);
0405         SizeT pos = (dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0);
0406
0407         processedPos += curLen;
0408
0409         len -= curLen;
0410         if (pos + curLen <= dicBufSize) {
0411           Byte *dest = dic + dicPos;
0412           ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos;
0413           const Byte *lim = dest + curLen;
0414           dicPos += curLen;
0415           do
0416             *(dest) = (Byte) * (dest + src);
0417           while (++dest != lim);
0418         } else {
0419           do {
0420             dic[dicPos++] = dic[pos];
0421             if (++pos == dicBufSize)
0422               pos = 0;
0423           } while (--curLen != 0);
0424         }
0425       }
0426     }
0427   } while (dicPos < limit && buf < bufLimit);
0428   NORMALIZE;
0429   p->buf = buf;
0430   p->range = range;
0431   p->code = code;
0432   p->remainLen = len;
0433   p->dicPos = dicPos;
0434   p->processedPos = processedPos;
0435   p->reps[0] = rep0;
0436   p->reps[1] = rep1;
0437   p->reps[2] = rep2;
0438   p->reps[3] = rep3;
0439   p->state = state;
0440
0441   return SZ_OK;
0442 }
0443
0444 static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit) {
0445   if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart) {
0446     Byte *dic = p->dic;
0447     SizeT dicPos = p->dicPos;
0448     SizeT dicBufSize = p->dicBufSize;
0449     unsigned len = p->remainLen;
0450     UInt32 rep0 = p->reps[0];
0451     if (limit - dicPos < len)
0452       len = (unsigned)(limit - dicPos);
0453
0454     if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len)
0455       p->checkDicSize = p->prop.dicSize;
0456
0457     p->processedPos += len;
0458     p->remainLen -= len;
0459     while (len-- != 0) {
0460       dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
0461       dicPos++;
0462     }
0463     p->dicPos = dicPos;
0464   }
0465 }
0466
0467 static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit) {
0468   do {
0469     SizeT limit2 = limit;
0470     if (p->checkDicSize == 0) {
0471       UInt32 rem = p->prop.dicSize - p->processedPos;
0472       if (limit - p->dicPos > rem)
0473         limit2 = p->dicPos + rem;
0474     }
0475     RINOK(LzmaDec_DecodeReal(p, limit2, bufLimit));
0476     if (p->processedPos >= p->prop.dicSize)
0477       p->checkDicSize = p->prop.dicSize;
0478     LzmaDec_WriteRem(p, limit);
0479   } while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart);
0480
0481   if (p->remainLen > kMatchSpecLenStart) {
0482     p->remainLen = kMatchSpecLenStart;
0483   }
0484   return 0;
0485 }
0486
0487 typedef enum {
0488   DUMMY_ERROR, /* unexpected end of input stream */
0489   DUMMY_LIT,
0490   DUMMY_MATCH,
0491   DUMMY_REP
0492 } ELzmaDummy;
0493
0494 static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, SizeT inSize) {
0495   UInt32 range = p->range;
0496   UInt32 code = p->code;
0497   const Byte *bufLimit = buf + inSize;
0498   CLzmaProb *probs = p->probs;
0499   unsigned state = p->state;
0500   ELzmaDummy res;
0501
0502   {
0503     CLzmaProb *prob;
0504     UInt32 bound;
0505     unsigned ttt;
0506     unsigned posState = (p->processedPos) & ((1 << p->prop.pb) - 1);
0507
0508     prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
0509     IF_BIT_0_CHECK(prob) {
0510       UPDATE_0_CHECK
0511
0512       /* if (bufLimit - buf >= 7) return DUMMY_LIT; */
0513
0514       prob = probs + Literal;
0515       if (p->checkDicSize != 0 || p->processedPos != 0)
0516         prob += (LZMA_LIT_SIZE * ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) +
0517                                   (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc))));
0518
0519       if (state < kNumLitStates) {
0520         unsigned symbol = 1;
0521         do {
0522           GET_BIT_CHECK(prob + symbol, symbol)
0523         } while (symbol < 0x100);
0524       } else {
0525         unsigned matchByte = p->dic[p->dicPos - p->reps[0] + ((p->dicPos < p->reps[0]) ? p->dicBufSize : 0)];
0526         unsigned offs = 0x100;
0527         unsigned symbol = 1;
0528         do {
0529           unsigned bit;
0530           CLzmaProb *probLit;
0531           matchByte <<= 1;
0532           bit = (matchByte & offs);
0533           probLit = prob + offs + bit + symbol;
0534           GET_BIT2_CHECK(probLit, symbol, offs &= ~bit, offs &= bit)
0535         } while (symbol < 0x100);
0536       }
0537       res = DUMMY_LIT;
0538     }
0539     else {
0540       unsigned len;
0541       UPDATE_1_CHECK;
0542
0543       prob = probs + IsRep + state;
0544       IF_BIT_0_CHECK(prob) {
0545         UPDATE_0_CHECK;
0546         state = 0;
0547         prob = probs + LenCoder;
0548         res = DUMMY_MATCH;
0549       }
0550       else {
0551         UPDATE_1_CHECK;
0552         res = DUMMY_REP;
0553         prob = probs + IsRepG0 + state;
0554         IF_BIT_0_CHECK(prob) {
0555           UPDATE_0_CHECK;
0556           prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
0557           IF_BIT_0_CHECK(prob) {
0558             UPDATE_0_CHECK;
0559             NORMALIZE_CHECK;
0560             return DUMMY_REP;
0561           }
0562           else {
0563             UPDATE_1_CHECK;
0564           }
0565         }
0566         else {
0567           UPDATE_1_CHECK;
0568           prob = probs + IsRepG1 + state;
0569           IF_BIT_0_CHECK(prob) { UPDATE_0_CHECK; }
0570           else {
0571             UPDATE_1_CHECK;
0572             prob = probs + IsRepG2 + state;
0573             IF_BIT_0_CHECK(prob) { UPDATE_0_CHECK; }
0574             else {
0575               UPDATE_1_CHECK;
0576             }
0577           }
0578         }
0579         state = kNumStates;
0580         prob = probs + RepLenCoder;
0581       }
0582       {
0583         unsigned limit, offset;
0584         CLzmaProb *probLen = prob + LenChoice;
0585         IF_BIT_0_CHECK(probLen) {
0586           UPDATE_0_CHECK;
0587           probLen = prob + LenLow + (posState << kLenNumLowBits);
0588           offset = 0;
0589           limit = 1 << kLenNumLowBits;
0590         }
0591         else {
0592           UPDATE_1_CHECK;
0593           probLen = prob + LenChoice2;
0594           IF_BIT_0_CHECK(probLen) {
0595             UPDATE_0_CHECK;
0596             probLen = prob + LenMid + (posState << kLenNumMidBits);
0597             offset = kLenNumLowSymbols;
0598             limit = 1 << kLenNumMidBits;
0599           }
0600           else {
0601             UPDATE_1_CHECK;
0602             probLen = prob + LenHigh;
0603             offset = kLenNumLowSymbols + kLenNumMidSymbols;
0604             limit = 1 << kLenNumHighBits;
0605           }
0606         }
0607         TREE_DECODE_CHECK(probLen, limit, len);
0608         len += offset;
0609       }
0610
0611       if (state < 4) {
0612         unsigned posSlot;
0613         prob = probs + PosSlot + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits);
0614         TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot);
0615         if (posSlot >= kStartPosModelIndex) {
0616           int numDirectBits = ((posSlot >> 1) - 1);
0617
0618           /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */
0619
0620           if (posSlot < kEndPosModelIndex) {
0621             prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits) - posSlot - 1;
0622           } else {
0623             numDirectBits -= kNumAlignBits;
0624             do {
0625               NORMALIZE_CHECK
0626               range >>= 1;
0627               code -= range & (((code - range) >> 31) - 1);
0628               /* if (code >= range) code -= range; */
0629             } while (--numDirectBits != 0);
0630             prob = probs + Align;
0631             numDirectBits = kNumAlignBits;
0632           }
0633           {
0634             unsigned i = 1;
0635             do {
0636               GET_BIT_CHECK(prob + i, i);
0637             } while (--numDirectBits != 0);
0638           }
0639         }
0640       }
0641     }
0642   }
0643   NORMALIZE_CHECK;
0644   return res;
0645 }
0646
0647 static void LzmaDec_InitRc(CLzmaDec *p, const Byte *data) {
0648   p->code = ((UInt32)data[1] << 24) | ((UInt32)data[2] << 16) | ((UInt32)data[3] << 8) | ((UInt32)data[4]);
0649   p->range = 0xFFFFFFFF;
0650   p->needFlush = 0;
0651 }
0652
0653 void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState) {
0654   p->needFlush = 1;
0655   p->remainLen = 0;
0656   p->tempBufSize = 0;
0657
0658   if (initDic) {
0659     p->processedPos = 0;
0660     p->checkDicSize = 0;
0661     p->needInitState = 1;
0662   }
0663   if (initState)
0664     p->needInitState = 1;
0665 }
0666
0667 void LzmaDec_Init(CLzmaDec *p) {
0668   p->dicPos = 0;
0669   LzmaDec_InitDicAndState(p, True, True);
0670 }
0671
0672 static void LzmaDec_InitStateReal(CLzmaDec *p) {
0673   UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (p->prop.lc + p->prop.lp));
0674   UInt32 i;
0675   CLzmaProb *probs = p->probs;
0676   for (i = 0; i < numProbs; i++)
0677     probs[i] = kBitModelTotal >> 1;
0678   p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1;
0679   p->state = 0;
0680   p->needInitState = 0;
0681 }
0682
0683 SRes LzmaDec_DecodeToDic(
0684     CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status) {
0685   SizeT inSize = *srcLen;
0686   (*srcLen) = 0;
0687   LzmaDec_WriteRem(p, dicLimit);
0688
0689   *status = LZMA_STATUS_NOT_SPECIFIED;
0690
0691   while (p->remainLen != kMatchSpecLenStart) {
0692     int checkEndMarkNow;
0693
0694     if (p->needFlush != 0) {
0695       for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--)
0696         p->tempBuf[p->tempBufSize++] = *src++;
0697       if (p->tempBufSize < RC_INIT_SIZE) {
0698         *status = LZMA_STATUS_NEEDS_MORE_INPUT;
0699         return SZ_OK;
0700       }
0701       if (p->tempBuf[0] != 0)
0702         return SZ_ERROR_DATA;
0703
0704       LzmaDec_InitRc(p, p->tempBuf);
0705       p->tempBufSize = 0;
0706     }
0707
0708     checkEndMarkNow = 0;
0709     if (p->dicPos >= dicLimit) {
0710       if (p->remainLen == 0 && p->code == 0) {
0711         *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK;
0712         return SZ_OK;
0713       }
0714       if (finishMode == LZMA_FINISH_ANY) {
0715         *status = LZMA_STATUS_NOT_FINISHED;
0716         return SZ_OK;
0717       }
0718       if (p->remainLen != 0) {
0719         *status = LZMA_STATUS_NOT_FINISHED;
0720         return SZ_ERROR_DATA;
0721       }
0722       checkEndMarkNow = 1;
0723     }
0724
0725     if (p->needInitState)
0726       LzmaDec_InitStateReal(p);
0727
0728     if (p->tempBufSize == 0) {
0729       SizeT processed;
0730       const Byte *bufLimit;
0731       if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow) {
0732         int dummyRes = LzmaDec_TryDummy(p, src, inSize);
0733         if (dummyRes == DUMMY_ERROR) {
0734           memcpy(p->tempBuf, src, inSize);
0735           p->tempBufSize = (unsigned)inSize;
0736           (*srcLen) += inSize;
0737           *status = LZMA_STATUS_NEEDS_MORE_INPUT;
0738           return SZ_OK;
0739         }
0740         if (checkEndMarkNow && dummyRes != DUMMY_MATCH) {
0741           *status = LZMA_STATUS_NOT_FINISHED;
0742           return SZ_ERROR_DATA;
0743         }
0744         bufLimit = src;
0745       } else
0746         bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX;
0747       p->buf = src;
0748       if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0)
0749         return SZ_ERROR_DATA;
0750       processed = (SizeT)(p->buf - src);
0751       (*srcLen) += processed;
0752       src += processed;
0753       inSize -= processed;
0754     } else {
0755       unsigned rem = p->tempBufSize, lookAhead = 0;
0756       while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize)
0757         p->tempBuf[rem++] = src[lookAhead++];
0758       p->tempBufSize = rem;
0759       if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow) {
0760         int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem);
0761         if (dummyRes == DUMMY_ERROR) {
0762           (*srcLen) += lookAhead;
0763           *status = LZMA_STATUS_NEEDS_MORE_INPUT;
0764           return SZ_OK;
0765         }
0766         if (checkEndMarkNow && dummyRes != DUMMY_MATCH) {
0767           *status = LZMA_STATUS_NOT_FINISHED;
0768           return SZ_ERROR_DATA;
0769         }
0770       }
0771       p->buf = p->tempBuf;
0772       if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0)
0773         return SZ_ERROR_DATA;
0774       lookAhead -= (rem - (unsigned)(p->buf - p->tempBuf));
0775       (*srcLen) += lookAhead;
0776       src += lookAhead;
0777       inSize -= lookAhead;
0778       p->tempBufSize = 0;
0779     }
0780   }
0781   if (p->code == 0)
0782     *status = LZMA_STATUS_FINISHED_WITH_MARK;
0783   return (p->code == 0) ? SZ_OK : SZ_ERROR_DATA;
0784 }
0785
0786 SRes LzmaDec_DecodeToBuf(CLzmaDec *p,
0787                          Byte *dest,
0788                          SizeT *destLen,
0789                          const Byte *src,
0790                          SizeT *srcLen,
0791                          ELzmaFinishMode finishMode,
0792                          ELzmaStatus *status) {
0793   SizeT outSize = *destLen;
0794   SizeT inSize = *srcLen;
0795   *srcLen = *destLen = 0;
0796   for (;;) {
0797     SizeT inSizeCur = inSize, outSizeCur, dicPos;
0798     ELzmaFinishMode curFinishMode;
0799     SRes res;
0800     if (p->dicPos == p->dicBufSize)
0801       p->dicPos = 0;
0802     dicPos = p->dicPos;
0803     if (outSize > p->dicBufSize - dicPos) {
0804       outSizeCur = p->dicBufSize;
0805       curFinishMode = LZMA_FINISH_ANY;
0806     } else {
0807       outSizeCur = dicPos + outSize;
0808       curFinishMode = finishMode;
0809     }
0810
0811     res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status);
0812     src += inSizeCur;
0813     inSize -= inSizeCur;
0814     *srcLen += inSizeCur;
0815     outSizeCur = p->dicPos - dicPos;
0816     memcpy(dest, p->dic + dicPos, outSizeCur);
0817     dest += outSizeCur;
0818     outSize -= outSizeCur;
0819     *destLen += outSizeCur;
0820     if (res != 0)
0821       return res;
0822     if (outSizeCur == 0 || outSize == 0)
0823       return SZ_OK;
0824   }
0825 }
0826
0827 void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc) {
0828   alloc->Free(alloc, p->probs);
0829   p->probs = nullptr;
0830 }
0831
0832 static void LzmaDec_FreeDict(CLzmaDec *p, ISzAlloc *alloc) {
0833   alloc->Free(alloc, p->dic);
0834   p->dic = nullptr;
0835 }
0836
0837 void LzmaDec_Free(CLzmaDec *p, ISzAlloc *alloc) {
0838   LzmaDec_FreeProbs(p, alloc);
0839   LzmaDec_FreeDict(p, alloc);
0840 }
0841
0842 SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size) {
0843   UInt32 dicSize;
0844   Byte d;
0845
0846   if (size < LZMA_PROPS_SIZE)
0847     return SZ_ERROR_UNSUPPORTED;
0848   else
0849     dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24);
0850
0851   if (dicSize < LZMA_DIC_MIN)
0852     dicSize = LZMA_DIC_MIN;
0853   p->dicSize = dicSize;
0854
0855   d = data[0];
0856   if (d >= (9 * 5 * 5))
0857     return SZ_ERROR_UNSUPPORTED;
0858
0859   p->lc = d % 9;
0860   d /= 9;
0861   p->pb = d / 5;
0862   p->lp = d % 5;
0863
0864   return SZ_OK;
0865 }
0866
0867 static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAlloc *alloc) {
0868   UInt32 numProbs = LzmaProps_GetNumProbs(propNew);
0869   if (p->probs == nullptr || numProbs != p->numProbs) {
0870     LzmaDec_FreeProbs(p, alloc);
0871     p->probs = (CLzmaProb *)alloc->Alloc(alloc, numProbs * sizeof(CLzmaProb));
0872     p->numProbs = numProbs;
0873     if (p->probs == nullptr)
0874       return SZ_ERROR_MEM;
0875   }
0876   return SZ_OK;
0877 }
0878
0879 SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc) {
0880   CLzmaProps propNew;
0881   RINOK(LzmaProps_Decode(&propNew, props, propsSize));
0882   RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
0883   p->prop = propNew;
0884   return SZ_OK;
0885 }
0886
0887 SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc) {
0888   CLzmaProps propNew;
0889   SizeT dicBufSize;
0890   RINOK(LzmaProps_Decode(&propNew, props, propsSize));
0891   RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
0892   dicBufSize = propNew.dicSize;
0893   if (p->dic == nullptr || dicBufSize != p->dicBufSize) {
0894     LzmaDec_FreeDict(p, alloc);
0895     p->dic = (Byte *)alloc->Alloc(alloc, dicBufSize);
0896     if (p->dic == nullptr) {
0897       LzmaDec_FreeProbs(p, alloc);
0898       return SZ_ERROR_MEM;
0899     }
0900   }
0901   p->dicBufSize = dicBufSize;
0902   p->prop = propNew;
0903   return SZ_OK;
0904 }
0905
0906 SRes LzmaDecode(Byte *dest,
0907                 SizeT *destLen,
0908                 const Byte *src,
0909                 SizeT *srcLen,
0910                 const Byte *propData,
0911                 unsigned propSize,
0912                 ELzmaFinishMode finishMode,
0913                 ELzmaStatus *status,
0914                 ISzAlloc *alloc) {
0915   CLzmaDec p;
0916   SRes res;
0917   SizeT inSize = *srcLen;
0918   SizeT outSize = *destLen;
0919   *srcLen = *destLen = 0;
0920   if (inSize < RC_INIT_SIZE)
0921     return SZ_ERROR_INPUT_EOF;
0922
0923   LzmaDec_Construct(&p);
0924   res = LzmaDec_AllocateProbs(&p, propData, propSize, alloc);
0925   if (res != 0)
0926     return res;
0927   p.dic = dest;
0928   p.dicBufSize = outSize;
0929
0930   LzmaDec_Init(&p);
0931
0932   *srcLen = inSize;
0933   res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status);
0934
0935   if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT)
0936     res = SZ_ERROR_INPUT_EOF;
0937
0938   (*destLen) = p.dicPos;
0939   LzmaDec_FreeProbs(&p, alloc);
0940   return res;
0941 }