xz_dec_lzma2.c 29 KB

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