rpmio/LzmaDecode.c

Go to the documentation of this file.
00001 /*
00002   LzmaDecode.c
00003   LZMA Decoder (optimized for Speed version)
00004   
00005   LZMA SDK 4.22 Copyright (c) 1999-2005 Igor Pavlov (2005-06-10)
00006   http://www.7-zip.org/
00007 
00008   LZMA SDK is licensed under two licenses:
00009   1) GNU Lesser General Public License (GNU LGPL)
00010   2) Common Public License (CPL)
00011   It means that you can select one of these two licenses and 
00012   follow rules of that license.
00013 
00014   SPECIAL EXCEPTION:
00015   Igor Pavlov, as the author of this Code, expressly permits you to 
00016   statically or dynamically link your Code (or bind by name) to the 
00017   interfaces of this file without subjecting your linked Code to the 
00018   terms of the CPL or GNU LGPL. Any modifications or additions 
00019   to this file, however, are subject to the LGPL or CPL terms.
00020 */
00021 
00022 #include "LzmaDecode.h"
00023 
00024 #ifndef Byte
00025 #define Byte unsigned char
00026 #endif
00027 
00028 #define kNumTopBits 24
00029 #define kTopValue ((UInt32)1 << kNumTopBits)
00030 
00031 #define kNumBitModelTotalBits 11
00032 #define kBitModelTotal (1 << kNumBitModelTotalBits)
00033 #define kNumMoveBits 5
00034 
00035 #define RC_READ_BYTE (*Buffer++)
00036 
00037 #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
00038   { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}
00039 
00040 #ifdef _LZMA_IN_CB
00041 
00042 #define RC_TEST { if (Buffer == BufferLim) \
00043   { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \
00044   BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }}
00045 
00046 #define RC_INIT Buffer = BufferLim = 0; RC_INIT2
00047 
00048 #else
00049 
00050 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
00051 
00052 #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
00053  
00054 #endif
00055 
00056 #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
00057 
00058 #define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
00059 #define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
00060 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
00061 
00062 #define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
00063   { UpdateBit0(p); mi <<= 1; A0; } else \
00064   { UpdateBit1(p); mi = (mi + mi) + 1; A1; } 
00065   
00066 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)               
00067 
00068 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
00069   { int i = numLevels; res = 1; \
00070   do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \
00071   res -= (1 << numLevels); }
00072 
00073 
00074 #define kNumPosBitsMax 4
00075 #define kNumPosStatesMax (1 << kNumPosBitsMax)
00076 
00077 #define kLenNumLowBits 3
00078 #define kLenNumLowSymbols (1 << kLenNumLowBits)
00079 #define kLenNumMidBits 3
00080 #define kLenNumMidSymbols (1 << kLenNumMidBits)
00081 #define kLenNumHighBits 8
00082 #define kLenNumHighSymbols (1 << kLenNumHighBits)
00083 
00084 #define LenChoice 0
00085 #define LenChoice2 (LenChoice + 1)
00086 #define LenLow (LenChoice2 + 1)
00087 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
00088 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
00089 #define kNumLenProbs (LenHigh + kLenNumHighSymbols) 
00090 
00091 
00092 #define kNumStates 12
00093 #define kNumLitStates 7
00094 
00095 #define kStartPosModelIndex 4
00096 #define kEndPosModelIndex 14
00097 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
00098 
00099 #define kNumPosSlotBits 6
00100 #define kNumLenToPosStates 4
00101 
00102 #define kNumAlignBits 4
00103 #define kAlignTableSize (1 << kNumAlignBits)
00104 
00105 #define kMatchMinLen 2
00106 
00107 #define IsMatch 0
00108 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
00109 #define IsRepG0 (IsRep + kNumStates)
00110 #define IsRepG1 (IsRepG0 + kNumStates)
00111 #define IsRepG2 (IsRepG1 + kNumStates)
00112 #define IsRep0Long (IsRepG2 + kNumStates)
00113 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
00114 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
00115 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
00116 #define LenCoder (Align + kAlignTableSize)
00117 #define RepLenCoder (LenCoder + kNumLenProbs)
00118 #define Literal (RepLenCoder + kNumLenProbs)
00119 
00120 #if Literal != LZMA_BASE_SIZE
00121 StopCompilingDueBUG
00122 #endif
00123 
00124 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
00125 {
00126   unsigned char prop0;
00127   if (size < LZMA_PROPERTIES_SIZE)
00128     return LZMA_RESULT_DATA_ERROR;
00129   prop0 = propsData[0];
00130   if (prop0 >= (9 * 5 * 5))
00131     return LZMA_RESULT_DATA_ERROR;
00132   {
00133     for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
00134     for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
00135     propsRes->lc = prop0;
00136     /*
00137     unsigned char remainder = (unsigned char)(prop0 / 9);
00138     propsRes->lc = prop0 % 9;
00139     propsRes->pb = remainder / 5;
00140     propsRes->lp = remainder % 5;
00141     */
00142   }
00143 
00144   #ifdef _LZMA_OUT_READ
00145   {
00146     int i;
00147     propsRes->DictionarySize = 0;
00148     for (i = 0; i < 4; i++)
00149       propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
00150     if (propsRes->DictionarySize == 0)
00151       propsRes->DictionarySize = 1;
00152   }
00153   #endif
00154   return LZMA_RESULT_OK;
00155 }
00156 
00157 #define kLzmaStreamWasFinishedId (-1)
00158 
00159 int LzmaDecode(CLzmaDecoderState *vs,
00160     #ifdef _LZMA_IN_CB
00161     ILzmaInCallback *InCallback,
00162     #else
00163     const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
00164     #endif
00165     unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
00166 {
00167   CProb *p = vs->Probs;
00168   SizeT nowPos = 0;
00169   Byte previousByte = 0;
00170   UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
00171   UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
00172   int lc = vs->Properties.lc;
00173 
00174   #ifdef _LZMA_OUT_READ
00175   
00176   UInt32 Range = vs->Range;
00177   UInt32 Code = vs->Code;
00178   #ifdef _LZMA_IN_CB
00179   const Byte *Buffer = vs->Buffer;
00180   const Byte *BufferLim = vs->BufferLim;
00181   #else
00182   const Byte *Buffer = inStream;
00183   const Byte *BufferLim = inStream + inSize;
00184   #endif
00185   int state = vs->State;
00186   UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
00187   int len = vs->RemainLen;
00188   UInt32 globalPos = vs->GlobalPos;
00189   UInt32 distanceLimit = vs->DistanceLimit;
00190 
00191   Byte *dictionary = vs->Dictionary;
00192   UInt32 dictionarySize = vs->Properties.DictionarySize;
00193   UInt32 dictionaryPos = vs->DictionaryPos;
00194 
00195   Byte tempDictionary[4];
00196 
00197   #ifndef _LZMA_IN_CB
00198   *inSizeProcessed = 0;
00199   #endif
00200   *outSizeProcessed = 0;
00201   if (len == kLzmaStreamWasFinishedId)
00202     return LZMA_RESULT_OK;
00203 
00204   if (dictionarySize == 0)
00205   {
00206     dictionary = tempDictionary;
00207     dictionarySize = 1;
00208     tempDictionary[0] = vs->TempDictionary[0];
00209   }
00210 
00211   if (len == kLzmaNeedInitId)
00212   {
00213     {
00214       UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
00215       UInt32 i;
00216       for (i = 0; i < numProbs; i++)
00217         p[i] = kBitModelTotal >> 1; 
00218       rep0 = rep1 = rep2 = rep3 = 1;
00219       state = 0;
00220       globalPos = 0;
00221       distanceLimit = 0;
00222       dictionaryPos = 0;
00223       dictionary[dictionarySize - 1] = 0;
00224       #ifdef _LZMA_IN_CB
00225       RC_INIT;
00226       #else
00227       RC_INIT(inStream, inSize);
00228       #endif
00229     }
00230     len = 0;
00231   }
00232   while(len != 0 && nowPos < outSize)
00233   {
00234     UInt32 pos = dictionaryPos - rep0;
00235     if (pos >= dictionarySize)
00236       pos += dictionarySize;
00237     outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
00238     if (++dictionaryPos == dictionarySize)
00239       dictionaryPos = 0;
00240     len--;
00241   }
00242   if (dictionaryPos == 0)
00243     previousByte = dictionary[dictionarySize - 1];
00244   else
00245     previousByte = dictionary[dictionaryPos - 1];
00246 
00247   #else /* if !_LZMA_OUT_READ */
00248 
00249   int state = 0;
00250   UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
00251   int len = 0;
00252   const Byte *Buffer;
00253   const Byte *BufferLim;
00254   UInt32 Range;
00255   UInt32 Code;
00256 
00257   #ifndef _LZMA_IN_CB
00258   *inSizeProcessed = 0;
00259   #endif
00260   *outSizeProcessed = 0;
00261 
00262   {
00263     UInt32 i;
00264     UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
00265     for (i = 0; i < numProbs; i++)
00266       p[i] = kBitModelTotal >> 1;
00267   }
00268   
00269   #ifdef _LZMA_IN_CB
00270   RC_INIT;
00271   #else
00272   RC_INIT(inStream, inSize);
00273   #endif
00274 
00275   #endif /* _LZMA_OUT_READ */
00276 
00277   while(nowPos < outSize)
00278   {
00279     CProb *prob;
00280     UInt32 bound;
00281     int posState = (int)(
00282         (nowPos 
00283         #ifdef _LZMA_OUT_READ
00284         + globalPos
00285         #endif
00286         )
00287         & posStateMask);
00288 
00289     prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
00290     IfBit0(prob)
00291     {
00292       int symbol = 1;
00293       UpdateBit0(prob)
00294       prob = p + Literal + (LZMA_LIT_SIZE * 
00295         (((
00296         (nowPos 
00297         #ifdef _LZMA_OUT_READ
00298         + globalPos
00299         #endif
00300         )
00301         & literalPosMask) << lc) + (previousByte >> (8 - lc))));
00302 
00303       if (state >= kNumLitStates)
00304       {
00305         int matchByte;
00306         #ifdef _LZMA_OUT_READ
00307         UInt32 pos = dictionaryPos - rep0;
00308         if (pos >= dictionarySize)
00309           pos += dictionarySize;
00310         matchByte = dictionary[pos];
00311         #else
00312         matchByte = outStream[nowPos - rep0];
00313         #endif
00314         do
00315         {
00316           int bit;
00317           CProb *probLit;
00318           matchByte <<= 1;
00319           bit = (matchByte & 0x100);
00320           probLit = prob + 0x100 + bit + symbol;
00321           RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
00322         }
00323         while (symbol < 0x100);
00324       }
00325       while (symbol < 0x100)
00326       {
00327         CProb *probLit = prob + symbol;
00328         RC_GET_BIT(probLit, symbol)
00329       }
00330       previousByte = (Byte)symbol;
00331 
00332       outStream[nowPos++] = previousByte;
00333       #ifdef _LZMA_OUT_READ
00334       if (distanceLimit < dictionarySize)
00335         distanceLimit++;
00336 
00337       dictionary[dictionaryPos] = previousByte;
00338       if (++dictionaryPos == dictionarySize)
00339         dictionaryPos = 0;
00340       #endif
00341       if (state < 4) state = 0;
00342       else if (state < 10) state -= 3;
00343       else state -= 6;
00344     }
00345     else             
00346     {
00347       UpdateBit1(prob);
00348       prob = p + IsRep + state;
00349       IfBit0(prob)
00350       {
00351         UpdateBit0(prob);
00352         rep3 = rep2;
00353         rep2 = rep1;
00354         rep1 = rep0;
00355         state = state < kNumLitStates ? 0 : 3;
00356         prob = p + LenCoder;
00357       }
00358       else
00359       {
00360         UpdateBit1(prob);
00361         prob = p + IsRepG0 + state;
00362         IfBit0(prob)
00363         {
00364           UpdateBit0(prob);
00365           prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
00366           IfBit0(prob)
00367           {
00368             #ifdef _LZMA_OUT_READ
00369             UInt32 pos;
00370             #endif
00371             UpdateBit0(prob);
00372             
00373             #ifdef _LZMA_OUT_READ
00374             if (distanceLimit == 0)
00375             #else
00376             if (nowPos == 0)
00377             #endif
00378               return LZMA_RESULT_DATA_ERROR;
00379             
00380             state = state < kNumLitStates ? 9 : 11;
00381             #ifdef _LZMA_OUT_READ
00382             pos = dictionaryPos - rep0;
00383             if (pos >= dictionarySize)
00384               pos += dictionarySize;
00385             previousByte = dictionary[pos];
00386             dictionary[dictionaryPos] = previousByte;
00387             if (++dictionaryPos == dictionarySize)
00388               dictionaryPos = 0;
00389             #else
00390             previousByte = outStream[nowPos - rep0];
00391             #endif
00392             outStream[nowPos++] = previousByte;
00393             #ifdef _LZMA_OUT_READ
00394             if (distanceLimit < dictionarySize)
00395               distanceLimit++;
00396             #endif
00397 
00398             continue;
00399           }
00400           else
00401           {
00402             UpdateBit1(prob);
00403           }
00404         }
00405         else
00406         {
00407           UInt32 distance;
00408           UpdateBit1(prob);
00409           prob = p + IsRepG1 + state;
00410           IfBit0(prob)
00411           {
00412             UpdateBit0(prob);
00413             distance = rep1;
00414           }
00415           else 
00416           {
00417             UpdateBit1(prob);
00418             prob = p + IsRepG2 + state;
00419             IfBit0(prob)
00420             {
00421               UpdateBit0(prob);
00422               distance = rep2;
00423             }
00424             else
00425             {
00426               UpdateBit1(prob);
00427               distance = rep3;
00428               rep3 = rep2;
00429             }
00430             rep2 = rep1;
00431           }
00432           rep1 = rep0;
00433           rep0 = distance;
00434         }
00435         state = state < kNumLitStates ? 8 : 11;
00436         prob = p + RepLenCoder;
00437       }
00438       {
00439         int numBits, offset;
00440         CProb *probLen = prob + LenChoice;
00441         IfBit0(probLen)
00442         {
00443           UpdateBit0(probLen);
00444           probLen = prob + LenLow + (posState << kLenNumLowBits);
00445           offset = 0;
00446           numBits = kLenNumLowBits;
00447         }
00448         else
00449         {
00450           UpdateBit1(probLen);
00451           probLen = prob + LenChoice2;
00452           IfBit0(probLen)
00453           {
00454             UpdateBit0(probLen);
00455             probLen = prob + LenMid + (posState << kLenNumMidBits);
00456             offset = kLenNumLowSymbols;
00457             numBits = kLenNumMidBits;
00458           }
00459           else
00460           {
00461             UpdateBit1(probLen);
00462             probLen = prob + LenHigh;
00463             offset = kLenNumLowSymbols + kLenNumMidSymbols;
00464             numBits = kLenNumHighBits;
00465           }
00466         }
00467         RangeDecoderBitTreeDecode(probLen, numBits, len);
00468         len += offset;
00469       }
00470 
00471       if (state < 4)
00472       {
00473         int posSlot;
00474         state += kNumLitStates;
00475         prob = p + PosSlot +
00476             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << 
00477             kNumPosSlotBits);
00478         RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
00479         if (posSlot >= kStartPosModelIndex)
00480         {
00481           int numDirectBits = ((posSlot >> 1) - 1);
00482           rep0 = (2 | ((UInt32)posSlot & 1));
00483           if (posSlot < kEndPosModelIndex)
00484           {
00485             rep0 <<= numDirectBits;
00486             prob = p + SpecPos + rep0 - posSlot - 1;
00487           }
00488           else
00489           {
00490             numDirectBits -= kNumAlignBits;
00491             do
00492             {
00493               RC_NORMALIZE
00494               Range >>= 1;
00495               rep0 <<= 1;
00496               if (Code >= Range)
00497               {
00498                 Code -= Range;
00499                 rep0 |= 1;
00500               }
00501             }
00502             while (--numDirectBits != 0);
00503             prob = p + Align;
00504             rep0 <<= kNumAlignBits;
00505             numDirectBits = kNumAlignBits;
00506           }
00507           {
00508             int i = 1;
00509             int mi = 1;
00510             do
00511             {
00512               CProb *prob3 = prob + mi;
00513               RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
00514               i <<= 1;
00515             }
00516             while(--numDirectBits != 0);
00517           }
00518         }
00519         else
00520           rep0 = posSlot;
00521         if (++rep0 == (UInt32)(0))
00522         {
00523           /* it's for stream version */
00524           len = kLzmaStreamWasFinishedId;
00525           break;
00526         }
00527       }
00528 
00529       len += kMatchMinLen;
00530       #ifdef _LZMA_OUT_READ
00531       if (rep0 > distanceLimit) 
00532       #else
00533       if (rep0 > nowPos)
00534       #endif
00535         return LZMA_RESULT_DATA_ERROR;
00536 
00537       #ifdef _LZMA_OUT_READ
00538       if (dictionarySize - distanceLimit > (UInt32)len)
00539         distanceLimit += len;
00540       else
00541         distanceLimit = dictionarySize;
00542       #endif
00543 
00544       do
00545       {
00546         #ifdef _LZMA_OUT_READ
00547         UInt32 pos = dictionaryPos - rep0;
00548         if (pos >= dictionarySize)
00549           pos += dictionarySize;
00550         previousByte = dictionary[pos];
00551         dictionary[dictionaryPos] = previousByte;
00552         if (++dictionaryPos == dictionarySize)
00553           dictionaryPos = 0;
00554         #else
00555         previousByte = outStream[nowPos - rep0];
00556         #endif
00557         len--;
00558         outStream[nowPos++] = previousByte;
00559       }
00560       while(len != 0 && nowPos < outSize);
00561     }
00562   }
00563   RC_NORMALIZE;
00564 
00565   #ifdef _LZMA_OUT_READ
00566   vs->Range = Range;
00567   vs->Code = Code;
00568   vs->DictionaryPos = dictionaryPos;
00569   vs->GlobalPos = globalPos + (UInt32)nowPos;
00570   vs->DistanceLimit = distanceLimit;
00571   vs->Reps[0] = rep0;
00572   vs->Reps[1] = rep1;
00573   vs->Reps[2] = rep2;
00574   vs->Reps[3] = rep3;
00575   vs->State = state;
00576   vs->RemainLen = len;
00577   vs->TempDictionary[0] = tempDictionary[0];
00578   #endif
00579 
00580   #ifdef _LZMA_IN_CB
00581   vs->Buffer = Buffer;
00582   vs->BufferLim = BufferLim;
00583   #else
00584   *inSizeProcessed = (SizeT)(Buffer - inStream);
00585   #endif
00586   *outSizeProcessed = nowPos;
00587   return LZMA_RESULT_OK;
00588 }

Generated on Mon Mar 5 14:30:16 2007 for rpm by  doxygen 1.5.1