LzmaDecode.c 9.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361
  1. /*
  2. LzmaDecode.c
  3. LZMA Decoder
  4. LZMA SDK 4.05 Copyright (c) 1999-2004 Igor Pavlov (2004-08-25)
  5. Modifications for TIGCC Copyright (C) 2004 Kevin Kofler
  6. http://www.7-zip.org/
  7. LZMA SDK is licensed under two licenses:
  8. 1) GNU Lesser General Public License (GNU LGPL)
  9. 2) Common Public License (CPL)
  10. It means that you can select one of these two licenses and
  11. follow rules of that license.
  12. SPECIAL EXCEPTION:
  13. Igor Pavlov, as the author of this code, expressly permits you to
  14. statically or dynamically link your code (or bind by name) to the
  15. interfaces of this file without subjecting your linked code to the
  16. terms of the CPL or GNU LGPL. Any modifications or additions
  17. to this file, however, are subject to the LGPL or CPL terms.
  18. */
  19. #include "LzmaDecode.h"
  20. #define Byte unsigned char
  21. #define kNumTopBits 24
  22. #define kTopValue ((UInt32)1 << kNumTopBits)
  23. #define kNumBitModelTotalBits 11
  24. #define kBitModelTotal (1 << kNumBitModelTotalBits)
  25. #define kNumMoveBits 5
  26. typedef struct _CRangeDecoder
  27. {
  28. Byte *Buffer;
  29. UInt32 Range;
  30. UInt32 Code;
  31. } CRangeDecoder;
  32. #define ReadByte (*rd->Buffer++)
  33. static inline void RangeDecoderInit(CRangeDecoder *rd,
  34. Byte *stream)
  35. {
  36. int i;
  37. rd->Buffer = stream;
  38. rd->Code = 0;
  39. rd->Range = (0xFFFFFFFF);
  40. for(i = 0; i < 5; i++)
  41. rd->Code = (rd->Code << 8) | ReadByte;
  42. }
  43. #define RC_INIT_VAR UInt32 range = rd->Range; UInt32 code = rd->Code;
  44. #define RC_FLUSH_VAR rd->Range = range; rd->Code = code;
  45. #define RC_NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | ReadByte; }
  46. static inline UInt32 RangeDecoderDecodeDirectBits(CRangeDecoder *rd, int numTotalBits)
  47. {
  48. RC_INIT_VAR
  49. UInt32 result = 0;
  50. int i;
  51. for (i = numTotalBits; i > 0; i--)
  52. {
  53. /* UInt32 t; */
  54. range >>= 1;
  55. result <<= 1;
  56. if (code >= range)
  57. {
  58. code -= range;
  59. result |= 1;
  60. }
  61. /*
  62. t = (code - range) >> 31;
  63. t &= 1;
  64. code -= range & (t - 1);
  65. result = (result + result) | (1 - t);
  66. */
  67. RC_NORMALIZE
  68. }
  69. RC_FLUSH_VAR
  70. return result;
  71. }
  72. static __attribute__((regparm)) int RangeDecoderBitDecode(CProb *prob, CRangeDecoder *rd)
  73. {
  74. UInt32 bound = (rd->Range >> kNumBitModelTotalBits) * *prob;
  75. if (rd->Code < bound)
  76. {
  77. rd->Range = bound;
  78. *prob += (kBitModelTotal - *prob) >> kNumMoveBits;
  79. if (rd->Range < kTopValue)
  80. {
  81. rd->Code = (rd->Code << 8) | ReadByte;
  82. rd->Range <<= 8;
  83. }
  84. return 0;
  85. }
  86. else
  87. {
  88. rd->Range -= bound;
  89. rd->Code -= bound;
  90. *prob -= (*prob) >> kNumMoveBits;
  91. if (rd->Range < kTopValue)
  92. {
  93. rd->Code = (rd->Code << 8) | ReadByte;
  94. rd->Range <<= 8;
  95. }
  96. return 1;
  97. }
  98. }
  99. static __attribute__((regparm)) int RangeDecoderBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd)
  100. {
  101. int mi = 1;
  102. int i;
  103. for(i = numLevels; i > 0; i--)
  104. {
  105. mi = (mi + mi) + RangeDecoderBitDecode(probs + mi, rd);
  106. }
  107. return mi - (1 << numLevels);
  108. }
  109. static inline int RangeDecoderReverseBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd)
  110. {
  111. int mi = 1;
  112. int i;
  113. int symbol = 0;
  114. for(i = 0; i < numLevels; i++)
  115. {
  116. int bit = RangeDecoderBitDecode(probs + mi, rd);
  117. mi = mi + mi + bit;
  118. symbol |= (bit << i);
  119. }
  120. return symbol;
  121. }
  122. static inline Byte LzmaLiteralDecode(CProb *probs, CRangeDecoder *rd)
  123. {
  124. int symbol = 1;
  125. do
  126. {
  127. symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd);
  128. }
  129. while (symbol < 0x100);
  130. return symbol;
  131. }
  132. static inline Byte LzmaLiteralDecodeMatch(CProb *probs, CRangeDecoder *rd, Byte matchByte)
  133. {
  134. int symbol = 1;
  135. do
  136. {
  137. int bit;
  138. int matchBit = (matchByte >> 7) & 1;
  139. matchByte <<= 1;
  140. bit = RangeDecoderBitDecode(probs + ((1 + matchBit) << 8) + symbol, rd);
  141. symbol = (symbol << 1) | bit;
  142. if (matchBit != bit)
  143. {
  144. while (symbol < 0x100)
  145. {
  146. symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd);
  147. }
  148. break;
  149. }
  150. }
  151. while (symbol < 0x100);
  152. return symbol;
  153. }
  154. #define kNumPosBitsMax 1
  155. #define kNumPosStatesMax (1 << kNumPosBitsMax)
  156. #define kLenNumLowBits 3
  157. #define kLenNumLowSymbols (1 << kLenNumLowBits)
  158. #define kLenNumMidBits 3
  159. #define kLenNumMidSymbols (1 << kLenNumMidBits)
  160. #define kLenNumHighBits 8
  161. #define kLenNumHighSymbols (1 << kLenNumHighBits)
  162. #define LenChoice 0
  163. #define LenChoice2 (LenChoice + 1)
  164. #define LenLow (LenChoice2 + 1)
  165. #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
  166. #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
  167. #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
  168. static __attribute__((regparm)) int LzmaLenDecode(CProb *p, CRangeDecoder *rd, int posState)
  169. {
  170. if(RangeDecoderBitDecode(p + LenChoice, rd) == 0)
  171. return RangeDecoderBitTreeDecode(p + LenLow +
  172. (posState << kLenNumLowBits), kLenNumLowBits, rd);
  173. if(RangeDecoderBitDecode(p + LenChoice2, rd) == 0)
  174. return kLenNumLowSymbols + RangeDecoderBitTreeDecode(p + LenMid +
  175. (posState << kLenNumMidBits), kLenNumMidBits, rd);
  176. return kLenNumLowSymbols + kLenNumMidSymbols +
  177. RangeDecoderBitTreeDecode(p + LenHigh, kLenNumHighBits, rd);
  178. }
  179. #define kNumStates 12
  180. #define kStartPosModelIndex 4
  181. #define kEndPosModelIndex 14
  182. #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
  183. #define kNumPosSlotBits 6
  184. #define kNumLenToPosStates 4
  185. #define kNumAlignBits 4
  186. #define kAlignTableSize (1 << kNumAlignBits)
  187. #define kMatchMinLen 2
  188. #define IsMatch 0
  189. #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
  190. #define IsRepG0 (IsRep + kNumStates)
  191. #define IsRepG1 (IsRepG0 + kNumStates)
  192. #define IsRepG2 (IsRepG1 + kNumStates)
  193. #define IsRep0Long (IsRepG2 + kNumStates)
  194. #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
  195. #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
  196. #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
  197. #define LenCoder (Align + kAlignTableSize)
  198. #define RepLenCoder (LenCoder + kNumLenProbs)
  199. #define Literal (RepLenCoder + kNumLenProbs)
  200. int LzmaDecode(
  201. unsigned char *inStream,
  202. unsigned char *outStream, UInt32 outSize)
  203. {
  204. UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE);
  205. CProb p[LZMA_BASE_SIZE+LZMA_LIT_SIZE];
  206. CRangeDecoder rd;
  207. UInt32 i;
  208. int state = 0;
  209. int previousIsMatch = 0;
  210. Byte previousByte = 0;
  211. UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
  212. UInt32 nowPos = 0;
  213. UInt32 posStateMask = 1;
  214. int len = 0;
  215. for (i = 0; i < numProbs; i++)
  216. p[i] = kBitModelTotal >> 1;
  217. RangeDecoderInit(&rd, inStream);
  218. while(nowPos < outSize)
  219. {
  220. int posState = (int)(nowPos & posStateMask);
  221. if (RangeDecoderBitDecode(p + IsMatch + (state << kNumPosBitsMax) + posState, &rd) == 0)
  222. {
  223. CProb *probs = p + Literal;
  224. if (state < 4) state = 0;
  225. else if (state < 10) state -= 3;
  226. else state -= 6;
  227. if (previousIsMatch)
  228. {
  229. Byte matchByte;
  230. matchByte = outStream[nowPos - rep0];
  231. previousByte = LzmaLiteralDecodeMatch(probs, &rd, matchByte);
  232. previousIsMatch = 0;
  233. }
  234. else
  235. previousByte = LzmaLiteralDecode(probs, &rd);
  236. outStream[nowPos++] = previousByte;
  237. }
  238. else
  239. {
  240. previousIsMatch = 1;
  241. if (RangeDecoderBitDecode(p + IsRep + state, &rd))
  242. {
  243. if (RangeDecoderBitDecode(p + IsRepG0 + state, &rd) == 0)
  244. {
  245. if (RangeDecoderBitDecode(p + IsRep0Long + (state << kNumPosBitsMax) + posState, &rd) == 0)
  246. {
  247. if (nowPos == 0)
  248. return LZMA_RESULT_DATA_ERROR;
  249. state = state < 7 ? 9 : 11;
  250. previousByte = outStream[nowPos - rep0];
  251. outStream[nowPos++] = previousByte;
  252. continue;
  253. }
  254. }
  255. else
  256. {
  257. UInt32 distance;
  258. if(RangeDecoderBitDecode(p + IsRepG1 + state, &rd) == 0)
  259. distance = rep1;
  260. else
  261. {
  262. if(RangeDecoderBitDecode(p + IsRepG2 + state, &rd) == 0)
  263. distance = rep2;
  264. else
  265. {
  266. distance = rep3;
  267. rep3 = rep2;
  268. }
  269. rep2 = rep1;
  270. }
  271. rep1 = rep0;
  272. rep0 = distance;
  273. }
  274. len = LzmaLenDecode(p + RepLenCoder, &rd, posState);
  275. state = state < 7 ? 8 : 11;
  276. }
  277. else
  278. {
  279. int posSlot;
  280. rep3 = rep2;
  281. rep2 = rep1;
  282. rep1 = rep0;
  283. state = state < 7 ? 7 : 10;
  284. len = LzmaLenDecode(p + LenCoder, &rd, posState);
  285. posSlot = RangeDecoderBitTreeDecode(p + PosSlot +
  286. ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
  287. kNumPosSlotBits), kNumPosSlotBits, &rd);
  288. if (posSlot >= kStartPosModelIndex)
  289. {
  290. int numDirectBits = ((posSlot >> 1) - 1);
  291. rep0 = ((2 | ((UInt32)posSlot & 1)) << numDirectBits);
  292. if (posSlot < kEndPosModelIndex)
  293. {
  294. rep0 += RangeDecoderReverseBitTreeDecode(
  295. p + SpecPos + rep0 - posSlot - 1, numDirectBits, &rd);
  296. }
  297. else
  298. {
  299. rep0 += RangeDecoderDecodeDirectBits(&rd,
  300. numDirectBits - kNumAlignBits) << kNumAlignBits;
  301. rep0 += RangeDecoderReverseBitTreeDecode(p + Align, kNumAlignBits, &rd);
  302. }
  303. }
  304. else
  305. rep0 = posSlot;
  306. rep0++;
  307. }
  308. if (rep0 == (UInt32)(0))
  309. {
  310. /* it's for stream version */
  311. /* len = -1; */
  312. break;
  313. }
  314. if (rep0 > nowPos)
  315. {
  316. return LZMA_RESULT_DATA_ERROR;
  317. }
  318. len += kMatchMinLen;
  319. do
  320. {
  321. previousByte = outStream[nowPos - rep0];
  322. outStream[nowPos++] = previousByte;
  323. len--;
  324. }
  325. while(len > 0 && nowPos < outSize);
  326. }
  327. }
  328. return LZMA_RESULT_OK;
  329. }