Subversion Repositories Kolibri OS

Rev

Rev 5728 | Blame | Compare with Previous | Last modification | View Log | RSS feed

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