Subversion Repositories Kolibri OS

Rev

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