xz_dec_lzma2.c 29 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193
  1. /*
  2. * LZMA2 decoder
  3. *
  4. * Authors: Lasse Collin <lasse.collin@tukaani.org>
  5. * Igor Pavlov <https://7-zip.org/>
  6. *
  7. * This file has been put into the public domain.
  8. * You can do whatever you want with this file.
  9. */
  10. #include "xz_private.h"
  11. #include "xz_lzma2.h"
  12. /*
  13. * Range decoder initialization eats the first five bytes of each LZMA chunk.
  14. */
  15. #define RC_INIT_BYTES 5
  16. /*
  17. * Minimum number of usable input buffer to safely decode one LZMA symbol.
  18. * The worst case is that we decode 22 bits using probabilities and 26
  19. * direct bits. This may decode at maximum of 20 bytes of input. However,
  20. * lzma_main() does an extra normalization before returning, thus we
  21. * need to put 21 here.
  22. */
  23. #define LZMA_IN_REQUIRED 21
  24. /*
  25. * Dictionary (history buffer)
  26. *
  27. * These are always true:
  28. * start <= pos <= full <= end
  29. * pos <= limit <= end
  30. *
  31. * In multi-call mode, also these are true:
  32. * end == size
  33. * size <= size_max
  34. * allocated <= size
  35. *
  36. * Most of these variables are size_t to support single-call mode,
  37. * in which the dictionary variables address the actual output
  38. * buffer directly.
  39. */
  40. struct dictionary {
  41. /* Beginning of the history buffer */
  42. uint8_t *buf;
  43. /* Old position in buf (before decoding more data) */
  44. size_t start;
  45. /* Position in buf */
  46. size_t pos;
  47. /*
  48. * How full dictionary is. This is used to detect corrupt input that
  49. * would read beyond the beginning of the uncompressed stream.
  50. */
  51. size_t full;
  52. /* Write limit; we don't write to buf[limit] or later bytes. */
  53. size_t limit;
  54. /*
  55. * End of the dictionary buffer. In multi-call mode, this is
  56. * the same as the dictionary size. In single-call mode, this
  57. * indicates the size of the output buffer.
  58. */
  59. size_t end;
  60. /*
  61. * Size of the dictionary as specified in Block Header. This is used
  62. * together with "full" to detect corrupt input that would make us
  63. * read beyond the beginning of the uncompressed stream.
  64. */
  65. uint32_t size;
  66. /*
  67. * Maximum allowed dictionary size in multi-call mode.
  68. * This is ignored in single-call mode.
  69. */
  70. uint32_t size_max;
  71. /*
  72. * Amount of memory currently allocated for the dictionary.
  73. * This is used only with XZ_DYNALLOC. (With XZ_PREALLOC,
  74. * size_max is always the same as the allocated size.)
  75. */
  76. uint32_t allocated;
  77. /* Operation mode */
  78. enum xz_mode mode;
  79. };
  80. /* Range decoder */
  81. struct rc_dec {
  82. uint32_t range;
  83. uint32_t code;
  84. /*
  85. * Number of initializing bytes remaining to be read
  86. * by rc_read_init().
  87. */
  88. uint32_t init_bytes_left;
  89. /*
  90. * Buffer from which we read our input. It can be either
  91. * temp.buf or the caller-provided input buffer.
  92. */
  93. const uint8_t *in;
  94. size_t in_pos;
  95. size_t in_limit;
  96. };
  97. /* Probabilities for a length decoder. */
  98. struct lzma_len_dec {
  99. /* Probability of match length being at least 10 */
  100. uint16_t choice;
  101. /* Probability of match length being at least 18 */
  102. uint16_t choice2;
  103. /* Probabilities for match lengths 2-9 */
  104. uint16_t low[POS_STATES_MAX][LEN_LOW_SYMBOLS];
  105. /* Probabilities for match lengths 10-17 */
  106. uint16_t mid[POS_STATES_MAX][LEN_MID_SYMBOLS];
  107. /* Probabilities for match lengths 18-273 */
  108. uint16_t high[LEN_HIGH_SYMBOLS];
  109. };
  110. struct lzma_dec {
  111. /* Distances of latest four matches */
  112. uint32_t rep0;
  113. uint32_t rep1;
  114. uint32_t rep2;
  115. uint32_t rep3;
  116. /* Types of the most recently seen LZMA symbols */
  117. enum lzma_state state;
  118. /*
  119. * Length of a match. This is updated so that dict_repeat can
  120. * be called again to finish repeating the whole match.
  121. */
  122. uint32_t len;
  123. /*
  124. * LZMA properties or related bit masks (number of literal
  125. * context bits, a mask dervied from the number of literal
  126. * position bits, and a mask dervied from the number
  127. * position bits)
  128. */
  129. uint32_t lc;
  130. uint32_t literal_pos_mask; /* (1 << lp) - 1 */
  131. uint32_t pos_mask; /* (1 << pb) - 1 */
  132. /* If 1, it's a match. Otherwise it's a single 8-bit literal. */
  133. uint16_t is_match[STATES][POS_STATES_MAX];
  134. /* If 1, it's a repeated match. The distance is one of rep0 .. rep3. */
  135. uint16_t is_rep[STATES];
  136. /*
  137. * If 0, distance of a repeated match is rep0.
  138. * Otherwise check is_rep1.
  139. */
  140. uint16_t is_rep0[STATES];
  141. /*
  142. * If 0, distance of a repeated match is rep1.
  143. * Otherwise check is_rep2.
  144. */
  145. uint16_t is_rep1[STATES];
  146. /* If 0, distance of a repeated match is rep2. Otherwise it is rep3. */
  147. uint16_t is_rep2[STATES];
  148. /*
  149. * If 1, the repeated match has length of one byte. Otherwise
  150. * the length is decoded from rep_len_decoder.
  151. */
  152. uint16_t is_rep0_long[STATES][POS_STATES_MAX];
  153. /*
  154. * Probability tree for the highest two bits of the match
  155. * distance. There is a separate probability tree for match
  156. * lengths of 2 (i.e. MATCH_LEN_MIN), 3, 4, and [5, 273].
  157. */
  158. uint16_t dist_slot[DIST_STATES][DIST_SLOTS];
  159. /*
  160. * Probility trees for additional bits for match distance
  161. * when the distance is in the range [4, 127].
  162. */
  163. uint16_t dist_special[FULL_DISTANCES - DIST_MODEL_END];
  164. /*
  165. * Probability tree for the lowest four bits of a match
  166. * distance that is equal to or greater than 128.
  167. */
  168. uint16_t dist_align[ALIGN_SIZE];
  169. /* Length of a normal match */
  170. struct lzma_len_dec match_len_dec;
  171. /* Length of a repeated match */
  172. struct lzma_len_dec rep_len_dec;
  173. /* Probabilities of literals */
  174. uint16_t literal[LITERAL_CODERS_MAX][LITERAL_CODER_SIZE];
  175. };
  176. struct lzma2_dec {
  177. /* Position in xz_dec_lzma2_run(). */
  178. enum lzma2_seq {
  179. SEQ_CONTROL,
  180. SEQ_UNCOMPRESSED_1,
  181. SEQ_UNCOMPRESSED_2,
  182. SEQ_COMPRESSED_0,
  183. SEQ_COMPRESSED_1,
  184. SEQ_PROPERTIES,
  185. SEQ_LZMA_PREPARE,
  186. SEQ_LZMA_RUN,
  187. SEQ_COPY
  188. } sequence;
  189. /* Next position after decoding the compressed size of the chunk. */
  190. enum lzma2_seq next_sequence;
  191. /* Uncompressed size of LZMA chunk (2 MiB at maximum) */
  192. uint32_t uncompressed;
  193. /*
  194. * Compressed size of LZMA chunk or compressed/uncompressed
  195. * size of uncompressed chunk (64 KiB at maximum)
  196. */
  197. uint32_t compressed;
  198. /*
  199. * True if dictionary reset is needed. This is false before
  200. * the first chunk (LZMA or uncompressed).
  201. */
  202. bool need_dict_reset;
  203. /*
  204. * True if new LZMA properties are needed. This is false
  205. * before the first LZMA chunk.
  206. */
  207. bool need_props;
  208. };
  209. struct xz_dec_lzma2 {
  210. /*
  211. * The order below is important on x86 to reduce code size and
  212. * it shouldn't hurt on other platforms. Everything up to and
  213. * including lzma.pos_mask are in the first 128 bytes on x86-32,
  214. * which allows using smaller instructions to access those
  215. * variables. On x86-64, fewer variables fit into the first 128
  216. * bytes, but this is still the best order without sacrificing
  217. * the readability by splitting the structures.
  218. */
  219. struct rc_dec rc;
  220. struct dictionary dict;
  221. struct lzma2_dec lzma2;
  222. struct lzma_dec lzma;
  223. /*
  224. * Temporary buffer which holds small number of input bytes between
  225. * decoder calls. See lzma2_lzma() for details.
  226. */
  227. struct {
  228. uint32_t size;
  229. uint8_t buf[3 * LZMA_IN_REQUIRED];
  230. } temp;
  231. };
  232. /**************
  233. * Dictionary *
  234. **************/
  235. /*
  236. * Reset the dictionary state. When in single-call mode, set up the beginning
  237. * of the dictionary to point to the actual output buffer.
  238. */
  239. static void dict_reset(struct dictionary *dict, struct xz_buf *b)
  240. {
  241. if (DEC_IS_SINGLE(dict->mode)) {
  242. dict->buf = b->out + b->out_pos;
  243. dict->end = b->out_size - b->out_pos;
  244. }
  245. dict->start = 0;
  246. dict->pos = 0;
  247. dict->limit = 0;
  248. dict->full = 0;
  249. }
  250. /* Set dictionary write limit */
  251. static void dict_limit(struct dictionary *dict, size_t out_max)
  252. {
  253. if (dict->end - dict->pos <= out_max)
  254. dict->limit = dict->end;
  255. else
  256. dict->limit = dict->pos + out_max;
  257. }
  258. /* Return true if at least one byte can be written into the dictionary. */
  259. static inline bool dict_has_space(const struct dictionary *dict)
  260. {
  261. return dict->pos < dict->limit;
  262. }
  263. /*
  264. * Get a byte from the dictionary at the given distance. The distance is
  265. * assumed to valid, or as a special case, zero when the dictionary is
  266. * still empty. This special case is needed for single-call decoding to
  267. * avoid writing a '\0' to the end of the destination buffer.
  268. */
  269. static inline uint32_t dict_get(const struct dictionary *dict, uint32_t dist)
  270. {
  271. size_t offset = dict->pos - dist - 1;
  272. if (dist >= dict->pos)
  273. offset += dict->end;
  274. return dict->full > 0 ? dict->buf[offset] : 0;
  275. }
  276. /*
  277. * Put one byte into the dictionary. It is assumed that there is space for it.
  278. */
  279. static inline void dict_put(struct dictionary *dict, uint8_t byte)
  280. {
  281. dict->buf[dict->pos++] = byte;
  282. if (dict->full < dict->pos)
  283. dict->full = dict->pos;
  284. }
  285. /*
  286. * Repeat given number of bytes from the given distance. If the distance is
  287. * invalid, false is returned. On success, true is returned and *len is
  288. * updated to indicate how many bytes were left to be repeated.
  289. */
  290. static bool dict_repeat(struct dictionary *dict, uint32_t *len, uint32_t dist)
  291. {
  292. size_t back;
  293. uint32_t left;
  294. if (dist >= dict->full || dist >= dict->size)
  295. return false;
  296. left = min_t(size_t, dict->limit - dict->pos, *len);
  297. *len -= left;
  298. back = dict->pos - dist - 1;
  299. if (dist >= dict->pos)
  300. back += dict->end;
  301. do {
  302. dict->buf[dict->pos++] = dict->buf[back++];
  303. if (back == dict->end)
  304. back = 0;
  305. } while (--left > 0);
  306. if (dict->full < dict->pos)
  307. dict->full = dict->pos;
  308. return true;
  309. }
  310. /* Copy uncompressed data as is from input to dictionary and output buffers. */
  311. static void dict_uncompressed(struct dictionary *dict, struct xz_buf *b,
  312. uint32_t *left)
  313. {
  314. size_t copy_size;
  315. while (*left > 0 && b->in_pos < b->in_size
  316. && b->out_pos < b->out_size) {
  317. copy_size = min(b->in_size - b->in_pos,
  318. b->out_size - b->out_pos);
  319. if (copy_size > dict->end - dict->pos)
  320. copy_size = dict->end - dict->pos;
  321. if (copy_size > *left)
  322. copy_size = *left;
  323. *left -= copy_size;
  324. /*
  325. * If doing in-place decompression in single-call mode and the
  326. * uncompressed size of the file is larger than the caller
  327. * thought (i.e. it is invalid input!), the buffers below may
  328. * overlap and cause undefined behavior with memcpy().
  329. * With valid inputs memcpy() would be fine here.
  330. */
  331. memmove(dict->buf + dict->pos, b->in + b->in_pos, copy_size);
  332. dict->pos += copy_size;
  333. if (dict->full < dict->pos)
  334. dict->full = dict->pos;
  335. if (DEC_IS_MULTI(dict->mode)) {
  336. if (dict->pos == dict->end)
  337. dict->pos = 0;
  338. /*
  339. * Like above but for multi-call mode: use memmove()
  340. * to avoid undefined behavior with invalid input.
  341. */
  342. memmove(b->out + b->out_pos, b->in + b->in_pos,
  343. copy_size);
  344. }
  345. dict->start = dict->pos;
  346. b->out_pos += copy_size;
  347. b->in_pos += copy_size;
  348. }
  349. }
  350. /*
  351. * Flush pending data from dictionary to b->out. It is assumed that there is
  352. * enough space in b->out. This is guaranteed because caller uses dict_limit()
  353. * before decoding data into the dictionary.
  354. */
  355. static uint32_t dict_flush(struct dictionary *dict, struct xz_buf *b)
  356. {
  357. size_t copy_size = dict->pos - dict->start;
  358. if (DEC_IS_MULTI(dict->mode)) {
  359. if (dict->pos == dict->end)
  360. dict->pos = 0;
  361. /*
  362. * These buffers cannot overlap even if doing in-place
  363. * decompression because in multi-call mode dict->buf
  364. * has been allocated by us in this file; it's not
  365. * provided by the caller like in single-call mode.
  366. */
  367. memcpy(b->out + b->out_pos, dict->buf + dict->start,
  368. copy_size);
  369. }
  370. dict->start = dict->pos;
  371. b->out_pos += copy_size;
  372. return copy_size;
  373. }
  374. /*****************
  375. * Range decoder *
  376. *****************/
  377. /* Reset the range decoder. */
  378. static void rc_reset(struct rc_dec *rc)
  379. {
  380. rc->range = (uint32_t)-1;
  381. rc->code = 0;
  382. rc->init_bytes_left = RC_INIT_BYTES;
  383. }
  384. /*
  385. * Read the first five initial bytes into rc->code if they haven't been
  386. * read already. (Yes, the first byte gets completely ignored.)
  387. */
  388. static bool rc_read_init(struct rc_dec *rc, struct xz_buf *b)
  389. {
  390. while (rc->init_bytes_left > 0) {
  391. if (b->in_pos == b->in_size)
  392. return false;
  393. rc->code = (rc->code << 8) + b->in[b->in_pos++];
  394. --rc->init_bytes_left;
  395. }
  396. return true;
  397. }
  398. /* Return true if there may not be enough input for the next decoding loop. */
  399. static inline bool rc_limit_exceeded(const struct rc_dec *rc)
  400. {
  401. return rc->in_pos > rc->in_limit;
  402. }
  403. /*
  404. * Return true if it is possible (from point of view of range decoder) that
  405. * we have reached the end of the LZMA chunk.
  406. */
  407. static inline bool rc_is_finished(const struct rc_dec *rc)
  408. {
  409. return rc->code == 0;
  410. }
  411. /* Read the next input byte if needed. */
  412. static __always_inline void rc_normalize(struct rc_dec *rc)
  413. {
  414. if (rc->range < RC_TOP_VALUE) {
  415. rc->range <<= RC_SHIFT_BITS;
  416. rc->code = (rc->code << RC_SHIFT_BITS) + rc->in[rc->in_pos++];
  417. }
  418. }
  419. /*
  420. * Decode one bit. In some versions, this function has been splitted in three
  421. * functions so that the compiler is supposed to be able to more easily avoid
  422. * an extra branch. In this particular version of the LZMA decoder, this
  423. * doesn't seem to be a good idea (tested with GCC 3.3.6, 3.4.6, and 4.3.3
  424. * on x86). Using a non-splitted version results in nicer looking code too.
  425. *
  426. * NOTE: This must return an int. Do not make it return a bool or the speed
  427. * of the code generated by GCC 3.x decreases 10-15 %. (GCC 4.3 doesn't care,
  428. * and it generates 10-20 % faster code than GCC 3.x from this file anyway.)
  429. */
  430. static __always_inline int rc_bit(struct rc_dec *rc, uint16_t *prob)
  431. {
  432. uint32_t bound;
  433. int bit;
  434. rc_normalize(rc);
  435. bound = (rc->range >> RC_BIT_MODEL_TOTAL_BITS) * *prob;
  436. if (rc->code < bound) {
  437. rc->range = bound;
  438. *prob += (RC_BIT_MODEL_TOTAL - *prob) >> RC_MOVE_BITS;
  439. bit = 0;
  440. } else {
  441. rc->range -= bound;
  442. rc->code -= bound;
  443. *prob -= *prob >> RC_MOVE_BITS;
  444. bit = 1;
  445. }
  446. return bit;
  447. }
  448. /* Decode a bittree starting from the most significant bit. */
  449. static __always_inline uint32_t rc_bittree(struct rc_dec *rc,
  450. uint16_t *probs, uint32_t limit)
  451. {
  452. uint32_t symbol = 1;
  453. do {
  454. if (rc_bit(rc, &probs[symbol]))
  455. symbol = (symbol << 1) + 1;
  456. else
  457. symbol <<= 1;
  458. } while (symbol < limit);
  459. return symbol;
  460. }
  461. /* Decode a bittree starting from the least significant bit. */
  462. static __always_inline void rc_bittree_reverse(struct rc_dec *rc,
  463. uint16_t *probs,
  464. uint32_t *dest, uint32_t limit)
  465. {
  466. uint32_t symbol = 1;
  467. uint32_t i = 0;
  468. do {
  469. if (rc_bit(rc, &probs[symbol])) {
  470. symbol = (symbol << 1) + 1;
  471. *dest += 1 << i;
  472. } else {
  473. symbol <<= 1;
  474. }
  475. } while (++i < limit);
  476. }
  477. /* Decode direct bits (fixed fifty-fifty probability) */
  478. static inline void rc_direct(struct rc_dec *rc, uint32_t *dest, uint32_t limit)
  479. {
  480. uint32_t mask;
  481. do {
  482. rc_normalize(rc);
  483. rc->range >>= 1;
  484. rc->code -= rc->range;
  485. mask = (uint32_t)0 - (rc->code >> 31);
  486. rc->code += rc->range & mask;
  487. *dest = (*dest << 1) + (mask + 1);
  488. } while (--limit > 0);
  489. }
  490. /********
  491. * LZMA *
  492. ********/
  493. /* Get pointer to literal coder probability array. */
  494. static uint16_t *lzma_literal_probs(struct xz_dec_lzma2 *s)
  495. {
  496. uint32_t prev_byte = dict_get(&s->dict, 0);
  497. uint32_t low = prev_byte >> (8 - s->lzma.lc);
  498. uint32_t high = (s->dict.pos & s->lzma.literal_pos_mask) << s->lzma.lc;
  499. return s->lzma.literal[low + high];
  500. }
  501. /* Decode a literal (one 8-bit byte) */
  502. static void lzma_literal(struct xz_dec_lzma2 *s)
  503. {
  504. uint16_t *probs;
  505. uint32_t symbol;
  506. uint32_t match_byte;
  507. uint32_t match_bit;
  508. uint32_t offset;
  509. uint32_t i;
  510. probs = lzma_literal_probs(s);
  511. if (lzma_state_is_literal(s->lzma.state)) {
  512. symbol = rc_bittree(&s->rc, probs, 0x100);
  513. } else {
  514. symbol = 1;
  515. match_byte = dict_get(&s->dict, s->lzma.rep0) << 1;
  516. offset = 0x100;
  517. do {
  518. match_bit = match_byte & offset;
  519. match_byte <<= 1;
  520. i = offset + match_bit + symbol;
  521. if (rc_bit(&s->rc, &probs[i])) {
  522. symbol = (symbol << 1) + 1;
  523. offset &= match_bit;
  524. } else {
  525. symbol <<= 1;
  526. offset &= ~match_bit;
  527. }
  528. } while (symbol < 0x100);
  529. }
  530. dict_put(&s->dict, (uint8_t)symbol);
  531. lzma_state_literal(&s->lzma.state);
  532. }
  533. /* Decode the length of the match into s->lzma.len. */
  534. static void lzma_len(struct xz_dec_lzma2 *s, struct lzma_len_dec *l,
  535. uint32_t pos_state)
  536. {
  537. uint16_t *probs;
  538. uint32_t limit;
  539. if (!rc_bit(&s->rc, &l->choice)) {
  540. probs = l->low[pos_state];
  541. limit = LEN_LOW_SYMBOLS;
  542. s->lzma.len = MATCH_LEN_MIN;
  543. } else {
  544. if (!rc_bit(&s->rc, &l->choice2)) {
  545. probs = l->mid[pos_state];
  546. limit = LEN_MID_SYMBOLS;
  547. s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS;
  548. } else {
  549. probs = l->high;
  550. limit = LEN_HIGH_SYMBOLS;
  551. s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS
  552. + LEN_MID_SYMBOLS;
  553. }
  554. }
  555. s->lzma.len += rc_bittree(&s->rc, probs, limit) - limit;
  556. }
  557. /* Decode a match. The distance will be stored in s->lzma.rep0. */
  558. static void lzma_match(struct xz_dec_lzma2 *s, uint32_t pos_state)
  559. {
  560. uint16_t *probs;
  561. uint32_t dist_slot;
  562. uint32_t limit;
  563. lzma_state_match(&s->lzma.state);
  564. s->lzma.rep3 = s->lzma.rep2;
  565. s->lzma.rep2 = s->lzma.rep1;
  566. s->lzma.rep1 = s->lzma.rep0;
  567. lzma_len(s, &s->lzma.match_len_dec, pos_state);
  568. probs = s->lzma.dist_slot[lzma_get_dist_state(s->lzma.len)];
  569. dist_slot = rc_bittree(&s->rc, probs, DIST_SLOTS) - DIST_SLOTS;
  570. if (dist_slot < DIST_MODEL_START) {
  571. s->lzma.rep0 = dist_slot;
  572. } else {
  573. limit = (dist_slot >> 1) - 1;
  574. s->lzma.rep0 = 2 + (dist_slot & 1);
  575. if (dist_slot < DIST_MODEL_END) {
  576. s->lzma.rep0 <<= limit;
  577. probs = s->lzma.dist_special + s->lzma.rep0
  578. - dist_slot - 1;
  579. rc_bittree_reverse(&s->rc, probs,
  580. &s->lzma.rep0, limit);
  581. } else {
  582. rc_direct(&s->rc, &s->lzma.rep0, limit - ALIGN_BITS);
  583. s->lzma.rep0 <<= ALIGN_BITS;
  584. rc_bittree_reverse(&s->rc, s->lzma.dist_align,
  585. &s->lzma.rep0, ALIGN_BITS);
  586. }
  587. }
  588. }
  589. /*
  590. * Decode a repeated match. The distance is one of the four most recently
  591. * seen matches. The distance will be stored in s->lzma.rep0.
  592. */
  593. static void lzma_rep_match(struct xz_dec_lzma2 *s, uint32_t pos_state)
  594. {
  595. uint32_t tmp;
  596. if (!rc_bit(&s->rc, &s->lzma.is_rep0[s->lzma.state])) {
  597. if (!rc_bit(&s->rc, &s->lzma.is_rep0_long[
  598. s->lzma.state][pos_state])) {
  599. lzma_state_short_rep(&s->lzma.state);
  600. s->lzma.len = 1;
  601. return;
  602. }
  603. } else {
  604. if (!rc_bit(&s->rc, &s->lzma.is_rep1[s->lzma.state])) {
  605. tmp = s->lzma.rep1;
  606. } else {
  607. if (!rc_bit(&s->rc, &s->lzma.is_rep2[s->lzma.state])) {
  608. tmp = s->lzma.rep2;
  609. } else {
  610. tmp = s->lzma.rep3;
  611. s->lzma.rep3 = s->lzma.rep2;
  612. }
  613. s->lzma.rep2 = s->lzma.rep1;
  614. }
  615. s->lzma.rep1 = s->lzma.rep0;
  616. s->lzma.rep0 = tmp;
  617. }
  618. lzma_state_long_rep(&s->lzma.state);
  619. lzma_len(s, &s->lzma.rep_len_dec, pos_state);
  620. }
  621. /* LZMA decoder core */
  622. static bool lzma_main(struct xz_dec_lzma2 *s)
  623. {
  624. uint32_t pos_state;
  625. /*
  626. * If the dictionary was reached during the previous call, try to
  627. * finish the possibly pending repeat in the dictionary.
  628. */
  629. if (dict_has_space(&s->dict) && s->lzma.len > 0)
  630. dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0);
  631. /*
  632. * Decode more LZMA symbols. One iteration may consume up to
  633. * LZMA_IN_REQUIRED - 1 bytes.
  634. */
  635. while (dict_has_space(&s->dict) && !rc_limit_exceeded(&s->rc)) {
  636. pos_state = s->dict.pos & s->lzma.pos_mask;
  637. if (!rc_bit(&s->rc, &s->lzma.is_match[
  638. s->lzma.state][pos_state])) {
  639. lzma_literal(s);
  640. } else {
  641. if (rc_bit(&s->rc, &s->lzma.is_rep[s->lzma.state]))
  642. lzma_rep_match(s, pos_state);
  643. else
  644. lzma_match(s, pos_state);
  645. if (!dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0))
  646. return false;
  647. }
  648. }
  649. /*
  650. * Having the range decoder always normalized when we are outside
  651. * this function makes it easier to correctly handle end of the chunk.
  652. */
  653. rc_normalize(&s->rc);
  654. return true;
  655. }
  656. /*
  657. * Reset the LZMA decoder and range decoder state. Dictionary is nore reset
  658. * here, because LZMA state may be reset without resetting the dictionary.
  659. */
  660. static void lzma_reset(struct xz_dec_lzma2 *s)
  661. {
  662. uint16_t *probs;
  663. size_t i;
  664. s->lzma.state = STATE_LIT_LIT;
  665. s->lzma.rep0 = 0;
  666. s->lzma.rep1 = 0;
  667. s->lzma.rep2 = 0;
  668. s->lzma.rep3 = 0;
  669. /*
  670. * All probabilities are initialized to the same value. This hack
  671. * makes the code smaller by avoiding a separate loop for each
  672. * probability array.
  673. *
  674. * This could be optimized so that only that part of literal
  675. * probabilities that are actually required. In the common case
  676. * we would write 12 KiB less.
  677. */
  678. probs = s->lzma.is_match[0];
  679. for (i = 0; i < PROBS_TOTAL; ++i)
  680. probs[i] = RC_BIT_MODEL_TOTAL / 2;
  681. rc_reset(&s->rc);
  682. }
  683. /*
  684. * Decode and validate LZMA properties (lc/lp/pb) and calculate the bit masks
  685. * from the decoded lp and pb values. On success, the LZMA decoder state is
  686. * reset and true is returned.
  687. */
  688. static bool lzma_props(struct xz_dec_lzma2 *s, uint8_t props)
  689. {
  690. if (props > (4 * 5 + 4) * 9 + 8)
  691. return false;
  692. s->lzma.pos_mask = 0;
  693. while (props >= 9 * 5) {
  694. props -= 9 * 5;
  695. ++s->lzma.pos_mask;
  696. }
  697. s->lzma.pos_mask = (1 << s->lzma.pos_mask) - 1;
  698. s->lzma.literal_pos_mask = 0;
  699. while (props >= 9) {
  700. props -= 9;
  701. ++s->lzma.literal_pos_mask;
  702. }
  703. s->lzma.lc = props;
  704. if (s->lzma.lc + s->lzma.literal_pos_mask > 4)
  705. return false;
  706. s->lzma.literal_pos_mask = (1 << s->lzma.literal_pos_mask) - 1;
  707. lzma_reset(s);
  708. return true;
  709. }
  710. /*********
  711. * LZMA2 *
  712. *********/
  713. /*
  714. * The LZMA decoder assumes that if the input limit (s->rc.in_limit) hasn't
  715. * been exceeded, it is safe to read up to LZMA_IN_REQUIRED bytes. This
  716. * wrapper function takes care of making the LZMA decoder's assumption safe.
  717. *
  718. * As long as there is plenty of input left to be decoded in the current LZMA
  719. * chunk, we decode directly from the caller-supplied input buffer until
  720. * there's LZMA_IN_REQUIRED bytes left. Those remaining bytes are copied into
  721. * s->temp.buf, which (hopefully) gets filled on the next call to this
  722. * function. We decode a few bytes from the temporary buffer so that we can
  723. * continue decoding from the caller-supplied input buffer again.
  724. */
  725. static bool lzma2_lzma(struct xz_dec_lzma2 *s, struct xz_buf *b)
  726. {
  727. size_t in_avail;
  728. uint32_t tmp;
  729. in_avail = b->in_size - b->in_pos;
  730. if (s->temp.size > 0 || s->lzma2.compressed == 0) {
  731. tmp = 2 * LZMA_IN_REQUIRED - s->temp.size;
  732. if (tmp > s->lzma2.compressed - s->temp.size)
  733. tmp = s->lzma2.compressed - s->temp.size;
  734. if (tmp > in_avail)
  735. tmp = in_avail;
  736. memcpy(s->temp.buf + s->temp.size, b->in + b->in_pos, tmp);
  737. if (s->temp.size + tmp == s->lzma2.compressed) {
  738. memzero(s->temp.buf + s->temp.size + tmp,
  739. sizeof(s->temp.buf)
  740. - s->temp.size - tmp);
  741. s->rc.in_limit = s->temp.size + tmp;
  742. } else if (s->temp.size + tmp < LZMA_IN_REQUIRED) {
  743. s->temp.size += tmp;
  744. b->in_pos += tmp;
  745. return true;
  746. } else {
  747. s->rc.in_limit = s->temp.size + tmp - LZMA_IN_REQUIRED;
  748. }
  749. s->rc.in = s->temp.buf;
  750. s->rc.in_pos = 0;
  751. if (!lzma_main(s) || s->rc.in_pos > s->temp.size + tmp)
  752. return false;
  753. s->lzma2.compressed -= s->rc.in_pos;
  754. if (s->rc.in_pos < s->temp.size) {
  755. s->temp.size -= s->rc.in_pos;
  756. memmove(s->temp.buf, s->temp.buf + s->rc.in_pos,
  757. s->temp.size);
  758. return true;
  759. }
  760. b->in_pos += s->rc.in_pos - s->temp.size;
  761. s->temp.size = 0;
  762. }
  763. in_avail = b->in_size - b->in_pos;
  764. if (in_avail >= LZMA_IN_REQUIRED) {
  765. s->rc.in = b->in;
  766. s->rc.in_pos = b->in_pos;
  767. if (in_avail >= s->lzma2.compressed + LZMA_IN_REQUIRED)
  768. s->rc.in_limit = b->in_pos + s->lzma2.compressed;
  769. else
  770. s->rc.in_limit = b->in_size - LZMA_IN_REQUIRED;
  771. if (!lzma_main(s))
  772. return false;
  773. in_avail = s->rc.in_pos - b->in_pos;
  774. if (in_avail > s->lzma2.compressed)
  775. return false;
  776. s->lzma2.compressed -= in_avail;
  777. b->in_pos = s->rc.in_pos;
  778. }
  779. in_avail = b->in_size - b->in_pos;
  780. if (in_avail < LZMA_IN_REQUIRED) {
  781. if (in_avail > s->lzma2.compressed)
  782. in_avail = s->lzma2.compressed;
  783. memcpy(s->temp.buf, b->in + b->in_pos, in_avail);
  784. s->temp.size = in_avail;
  785. b->in_pos += in_avail;
  786. }
  787. return true;
  788. }
  789. /*
  790. * Take care of the LZMA2 control layer, and forward the job of actual LZMA
  791. * decoding or copying of uncompressed chunks to other functions.
  792. */
  793. XZ_EXTERN enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s,
  794. struct xz_buf *b)
  795. {
  796. uint32_t tmp;
  797. while (b->in_pos < b->in_size || s->lzma2.sequence == SEQ_LZMA_RUN) {
  798. switch (s->lzma2.sequence) {
  799. case SEQ_CONTROL:
  800. /*
  801. * LZMA2 control byte
  802. *
  803. * Exact values:
  804. * 0x00 End marker
  805. * 0x01 Dictionary reset followed by
  806. * an uncompressed chunk
  807. * 0x02 Uncompressed chunk (no dictionary reset)
  808. *
  809. * Highest three bits (s->control & 0xE0):
  810. * 0xE0 Dictionary reset, new properties and state
  811. * reset, followed by LZMA compressed chunk
  812. * 0xC0 New properties and state reset, followed
  813. * by LZMA compressed chunk (no dictionary
  814. * reset)
  815. * 0xA0 State reset using old properties,
  816. * followed by LZMA compressed chunk (no
  817. * dictionary reset)
  818. * 0x80 LZMA chunk (no dictionary or state reset)
  819. *
  820. * For LZMA compressed chunks, the lowest five bits
  821. * (s->control & 1F) are the highest bits of the
  822. * uncompressed size (bits 16-20).
  823. *
  824. * A new LZMA2 stream must begin with a dictionary
  825. * reset. The first LZMA chunk must set new
  826. * properties and reset the LZMA state.
  827. *
  828. * Values that don't match anything described above
  829. * are invalid and we return XZ_DATA_ERROR.
  830. */
  831. tmp = b->in[b->in_pos++];
  832. if (tmp == 0x00)
  833. return XZ_STREAM_END;
  834. if (tmp >= 0xE0 || tmp == 0x01) {
  835. s->lzma2.need_props = true;
  836. s->lzma2.need_dict_reset = false;
  837. dict_reset(&s->dict, b);
  838. } else if (s->lzma2.need_dict_reset) {
  839. return XZ_DATA_ERROR;
  840. }
  841. if (tmp >= 0x80) {
  842. s->lzma2.uncompressed = (tmp & 0x1F) << 16;
  843. s->lzma2.sequence = SEQ_UNCOMPRESSED_1;
  844. if (tmp >= 0xC0) {
  845. /*
  846. * When there are new properties,
  847. * state reset is done at
  848. * SEQ_PROPERTIES.
  849. */
  850. s->lzma2.need_props = false;
  851. s->lzma2.next_sequence
  852. = SEQ_PROPERTIES;
  853. } else if (s->lzma2.need_props) {
  854. return XZ_DATA_ERROR;
  855. } else {
  856. s->lzma2.next_sequence
  857. = SEQ_LZMA_PREPARE;
  858. if (tmp >= 0xA0)
  859. lzma_reset(s);
  860. }
  861. } else {
  862. if (tmp > 0x02)
  863. return XZ_DATA_ERROR;
  864. s->lzma2.sequence = SEQ_COMPRESSED_0;
  865. s->lzma2.next_sequence = SEQ_COPY;
  866. }
  867. break;
  868. case SEQ_UNCOMPRESSED_1:
  869. s->lzma2.uncompressed
  870. += (uint32_t)b->in[b->in_pos++] << 8;
  871. s->lzma2.sequence = SEQ_UNCOMPRESSED_2;
  872. break;
  873. case SEQ_UNCOMPRESSED_2:
  874. s->lzma2.uncompressed
  875. += (uint32_t)b->in[b->in_pos++] + 1;
  876. s->lzma2.sequence = SEQ_COMPRESSED_0;
  877. break;
  878. case SEQ_COMPRESSED_0:
  879. s->lzma2.compressed
  880. = (uint32_t)b->in[b->in_pos++] << 8;
  881. s->lzma2.sequence = SEQ_COMPRESSED_1;
  882. break;
  883. case SEQ_COMPRESSED_1:
  884. s->lzma2.compressed
  885. += (uint32_t)b->in[b->in_pos++] + 1;
  886. s->lzma2.sequence = s->lzma2.next_sequence;
  887. break;
  888. case SEQ_PROPERTIES:
  889. if (!lzma_props(s, b->in[b->in_pos++]))
  890. return XZ_DATA_ERROR;
  891. s->lzma2.sequence = SEQ_LZMA_PREPARE;
  892. /* fall through */
  893. case SEQ_LZMA_PREPARE:
  894. if (s->lzma2.compressed < RC_INIT_BYTES)
  895. return XZ_DATA_ERROR;
  896. if (!rc_read_init(&s->rc, b))
  897. return XZ_OK;
  898. s->lzma2.compressed -= RC_INIT_BYTES;
  899. s->lzma2.sequence = SEQ_LZMA_RUN;
  900. /* fall through */
  901. case SEQ_LZMA_RUN:
  902. /*
  903. * Set dictionary limit to indicate how much we want
  904. * to be encoded at maximum. Decode new data into the
  905. * dictionary. Flush the new data from dictionary to
  906. * b->out. Check if we finished decoding this chunk.
  907. * In case the dictionary got full but we didn't fill
  908. * the output buffer yet, we may run this loop
  909. * multiple times without changing s->lzma2.sequence.
  910. */
  911. dict_limit(&s->dict, min_t(size_t,
  912. b->out_size - b->out_pos,
  913. s->lzma2.uncompressed));
  914. if (!lzma2_lzma(s, b))
  915. return XZ_DATA_ERROR;
  916. s->lzma2.uncompressed -= dict_flush(&s->dict, b);
  917. if (s->lzma2.uncompressed == 0) {
  918. if (s->lzma2.compressed > 0 || s->lzma.len > 0
  919. || !rc_is_finished(&s->rc))
  920. return XZ_DATA_ERROR;
  921. rc_reset(&s->rc);
  922. s->lzma2.sequence = SEQ_CONTROL;
  923. } else if (b->out_pos == b->out_size
  924. || (b->in_pos == b->in_size
  925. && s->temp.size
  926. < s->lzma2.compressed)) {
  927. return XZ_OK;
  928. }
  929. break;
  930. case SEQ_COPY:
  931. dict_uncompressed(&s->dict, b, &s->lzma2.compressed);
  932. if (s->lzma2.compressed > 0)
  933. return XZ_OK;
  934. s->lzma2.sequence = SEQ_CONTROL;
  935. break;
  936. }
  937. }
  938. return XZ_OK;
  939. }
  940. XZ_EXTERN struct xz_dec_lzma2 *xz_dec_lzma2_create(enum xz_mode mode,
  941. uint32_t dict_max)
  942. {
  943. struct xz_dec_lzma2 *s = kmalloc(sizeof(*s), GFP_KERNEL);
  944. if (s == NULL)
  945. return NULL;
  946. s->dict.mode = mode;
  947. s->dict.size_max = dict_max;
  948. if (DEC_IS_PREALLOC(mode)) {
  949. s->dict.buf = vmalloc(dict_max);
  950. if (s->dict.buf == NULL) {
  951. kfree(s);
  952. return NULL;
  953. }
  954. } else if (DEC_IS_DYNALLOC(mode)) {
  955. s->dict.buf = NULL;
  956. s->dict.allocated = 0;
  957. }
  958. return s;
  959. }
  960. XZ_EXTERN enum xz_ret xz_dec_lzma2_reset(struct xz_dec_lzma2 *s, uint8_t props)
  961. {
  962. /* This limits dictionary size to 3 GiB to keep parsing simpler. */
  963. if (props > 39)
  964. return XZ_OPTIONS_ERROR;
  965. s->dict.size = 2 + (props & 1);
  966. s->dict.size <<= (props >> 1) + 11;
  967. if (DEC_IS_MULTI(s->dict.mode)) {
  968. if (s->dict.size > s->dict.size_max)
  969. return XZ_MEMLIMIT_ERROR;
  970. s->dict.end = s->dict.size;
  971. if (DEC_IS_DYNALLOC(s->dict.mode)) {
  972. if (s->dict.allocated < s->dict.size) {
  973. s->dict.allocated = s->dict.size;
  974. vfree(s->dict.buf);
  975. s->dict.buf = vmalloc(s->dict.size);
  976. if (s->dict.buf == NULL) {
  977. s->dict.allocated = 0;
  978. return XZ_MEM_ERROR;
  979. }
  980. }
  981. }
  982. }
  983. s->lzma.len = 0;
  984. s->lzma2.sequence = SEQ_CONTROL;
  985. s->lzma2.need_dict_reset = true;
  986. s->temp.size = 0;
  987. return XZ_OK;
  988. }
  989. XZ_EXTERN void xz_dec_lzma2_end(struct xz_dec_lzma2 *s)
  990. {
  991. if (DEC_IS_MULTI(s->dict.mode))
  992. vfree(s->dict.buf);
  993. kfree(s);
  994. }