LzmaDec.c 27 KB

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