decompress_unlzma.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478
  1. /* vi: set sw=4 ts=4: */
  2. /*
  3. * Small lzma deflate implementation.
  4. * Copyright (C) 2006 Aurelien Jacobs <aurel@gnuage.org>
  5. *
  6. * Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)
  7. * Copyright (C) 1999-2005 Igor Pavlov
  8. *
  9. * Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
  10. */
  11. #include "libbb.h"
  12. #include "unarchive.h"
  13. #ifdef CONFIG_FEATURE_LZMA_FAST
  14. # define speed_inline ATTRIBUTE_ALWAYS_INLINE
  15. #else
  16. # define speed_inline
  17. #endif
  18. typedef struct {
  19. int fd;
  20. uint8_t *ptr;
  21. uint8_t *buffer;
  22. uint8_t *buffer_end;
  23. int buffer_size;
  24. uint32_t code;
  25. uint32_t range;
  26. uint32_t bound;
  27. } rc_t;
  28. #define RC_TOP_BITS 24
  29. #define RC_MOVE_BITS 5
  30. #define RC_MODEL_TOTAL_BITS 11
  31. /* Called twice: once at startup and once in rc_normalize() */
  32. static void rc_read(rc_t * rc)
  33. {
  34. rc->buffer_size = read(rc->fd, rc->buffer, rc->buffer_size);
  35. if (rc->buffer_size <= 0)
  36. bb_error_msg_and_die("unexpected EOF");
  37. rc->ptr = rc->buffer;
  38. rc->buffer_end = rc->buffer + rc->buffer_size;
  39. }
  40. /* Called once */
  41. static void rc_init(rc_t * rc, int fd, int buffer_size)
  42. {
  43. int i;
  44. rc->fd = fd;
  45. rc->buffer = xmalloc(buffer_size);
  46. rc->buffer_size = buffer_size;
  47. rc->buffer_end = rc->buffer + rc->buffer_size;
  48. rc->ptr = rc->buffer_end;
  49. rc->code = 0;
  50. rc->range = 0xFFFFFFFF;
  51. for (i = 0; i < 5; i++) {
  52. if (rc->ptr >= rc->buffer_end)
  53. rc_read(rc);
  54. rc->code = (rc->code << 8) | *rc->ptr++;
  55. }
  56. }
  57. /* Called once. TODO: bb_maybe_free() */
  58. static ATTRIBUTE_ALWAYS_INLINE void rc_free(rc_t * rc)
  59. {
  60. if (ENABLE_FEATURE_CLEAN_UP)
  61. free(rc->buffer);
  62. }
  63. /* Called twice, but one callsite is in speed_inline'd rc_is_bit_0_helper() */
  64. static void rc_do_normalize(rc_t * rc)
  65. {
  66. if (rc->ptr >= rc->buffer_end)
  67. rc_read(rc);
  68. rc->range <<= 8;
  69. rc->code = (rc->code << 8) | *rc->ptr++;
  70. }
  71. static ATTRIBUTE_ALWAYS_INLINE void rc_normalize(rc_t * rc)
  72. {
  73. if (rc->range < (1 << RC_TOP_BITS)) {
  74. rc_do_normalize(rc);
  75. }
  76. }
  77. /* Called 9 times */
  78. /* Why rc_is_bit_0_helper exists?
  79. * Because we want to always expose (rc->code < rc->bound) to optimizer
  80. */
  81. static speed_inline uint32_t rc_is_bit_0_helper(rc_t * rc, uint16_t * p)
  82. {
  83. rc_normalize(rc);
  84. rc->bound = *p * (rc->range >> RC_MODEL_TOTAL_BITS);
  85. return rc->bound;
  86. }
  87. static ATTRIBUTE_ALWAYS_INLINE int rc_is_bit_0(rc_t * rc, uint16_t * p)
  88. {
  89. uint32_t t = rc_is_bit_0_helper(rc, p);
  90. return rc->code < t;
  91. }
  92. /* Called ~10 times, but very small, thus inlined */
  93. static speed_inline void rc_update_bit_0(rc_t * rc, uint16_t * p)
  94. {
  95. rc->range = rc->bound;
  96. *p += ((1 << RC_MODEL_TOTAL_BITS) - *p) >> RC_MOVE_BITS;
  97. }
  98. static speed_inline void rc_update_bit_1(rc_t * rc, uint16_t * p)
  99. {
  100. rc->range -= rc->bound;
  101. rc->code -= rc->bound;
  102. *p -= *p >> RC_MOVE_BITS;
  103. }
  104. /* Called 4 times in unlzma loop */
  105. static int rc_get_bit(rc_t * rc, uint16_t * p, int *symbol)
  106. {
  107. if (rc_is_bit_0(rc, p)) {
  108. rc_update_bit_0(rc, p);
  109. *symbol *= 2;
  110. return 0;
  111. } else {
  112. rc_update_bit_1(rc, p);
  113. *symbol = *symbol * 2 + 1;
  114. return 1;
  115. }
  116. }
  117. /* Called once */
  118. static ATTRIBUTE_ALWAYS_INLINE int rc_direct_bit(rc_t * rc)
  119. {
  120. rc_normalize(rc);
  121. rc->range >>= 1;
  122. if (rc->code >= rc->range) {
  123. rc->code -= rc->range;
  124. return 1;
  125. }
  126. return 0;
  127. }
  128. /* Called twice */
  129. static speed_inline void
  130. rc_bit_tree_decode(rc_t * rc, uint16_t * p, int num_levels, int *symbol)
  131. {
  132. int i = num_levels;
  133. *symbol = 1;
  134. while (i--)
  135. rc_get_bit(rc, p + *symbol, symbol);
  136. *symbol -= 1 << num_levels;
  137. }
  138. typedef struct {
  139. uint8_t pos;
  140. uint32_t dict_size;
  141. uint64_t dst_size;
  142. } __attribute__ ((packed)) lzma_header_t;
  143. #define LZMA_BASE_SIZE 1846
  144. #define LZMA_LIT_SIZE 768
  145. #define LZMA_NUM_POS_BITS_MAX 4
  146. #define LZMA_LEN_NUM_LOW_BITS 3
  147. #define LZMA_LEN_NUM_MID_BITS 3
  148. #define LZMA_LEN_NUM_HIGH_BITS 8
  149. #define LZMA_LEN_CHOICE 0
  150. #define LZMA_LEN_CHOICE_2 (LZMA_LEN_CHOICE + 1)
  151. #define LZMA_LEN_LOW (LZMA_LEN_CHOICE_2 + 1)
  152. #define LZMA_LEN_MID (LZMA_LEN_LOW \
  153. + (1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_LOW_BITS)))
  154. #define LZMA_LEN_HIGH (LZMA_LEN_MID \
  155. +(1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_MID_BITS)))
  156. #define LZMA_NUM_LEN_PROBS (LZMA_LEN_HIGH + (1 << LZMA_LEN_NUM_HIGH_BITS))
  157. #define LZMA_NUM_STATES 12
  158. #define LZMA_NUM_LIT_STATES 7
  159. #define LZMA_START_POS_MODEL_INDEX 4
  160. #define LZMA_END_POS_MODEL_INDEX 14
  161. #define LZMA_NUM_FULL_DISTANCES (1 << (LZMA_END_POS_MODEL_INDEX >> 1))
  162. #define LZMA_NUM_POS_SLOT_BITS 6
  163. #define LZMA_NUM_LEN_TO_POS_STATES 4
  164. #define LZMA_NUM_ALIGN_BITS 4
  165. #define LZMA_MATCH_MIN_LEN 2
  166. #define LZMA_IS_MATCH 0
  167. #define LZMA_IS_REP (LZMA_IS_MATCH + (LZMA_NUM_STATES <<LZMA_NUM_POS_BITS_MAX))
  168. #define LZMA_IS_REP_G0 (LZMA_IS_REP + LZMA_NUM_STATES)
  169. #define LZMA_IS_REP_G1 (LZMA_IS_REP_G0 + LZMA_NUM_STATES)
  170. #define LZMA_IS_REP_G2 (LZMA_IS_REP_G1 + LZMA_NUM_STATES)
  171. #define LZMA_IS_REP_0_LONG (LZMA_IS_REP_G2 + LZMA_NUM_STATES)
  172. #define LZMA_POS_SLOT (LZMA_IS_REP_0_LONG \
  173. + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX))
  174. #define LZMA_SPEC_POS (LZMA_POS_SLOT \
  175. +(LZMA_NUM_LEN_TO_POS_STATES << LZMA_NUM_POS_SLOT_BITS))
  176. #define LZMA_ALIGN (LZMA_SPEC_POS \
  177. + LZMA_NUM_FULL_DISTANCES - LZMA_END_POS_MODEL_INDEX)
  178. #define LZMA_LEN_CODER (LZMA_ALIGN + (1 << LZMA_NUM_ALIGN_BITS))
  179. #define LZMA_REP_LEN_CODER (LZMA_LEN_CODER + LZMA_NUM_LEN_PROBS)
  180. #define LZMA_LITERAL (LZMA_REP_LEN_CODER + LZMA_NUM_LEN_PROBS)
  181. USE_DESKTOP(long long) int
  182. unlzma(int src_fd, int dst_fd)
  183. {
  184. USE_DESKTOP(long long total_written = 0;)
  185. lzma_header_t header;
  186. int lc, pb, lp;
  187. uint32_t pos_state_mask;
  188. uint32_t literal_pos_mask;
  189. uint32_t pos;
  190. uint16_t *p;
  191. uint16_t *prob;
  192. uint16_t *prob_lit;
  193. int num_bits;
  194. int num_probs;
  195. rc_t rc;
  196. int i, mi;
  197. uint8_t *buffer;
  198. uint8_t previous_byte = 0;
  199. size_t buffer_pos = 0, global_pos = 0;
  200. int len = 0;
  201. int state = 0;
  202. uint32_t rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
  203. if (read(src_fd, &header, sizeof(header)) != sizeof(header))
  204. bb_error_msg_and_die("can't read header");
  205. if (header.pos >= (9 * 5 * 5))
  206. bb_error_msg_and_die("bad header");
  207. mi = header.pos / 9;
  208. lc = header.pos % 9;
  209. pb = mi / 5;
  210. lp = mi % 5;
  211. pos_state_mask = (1 << pb) - 1;
  212. literal_pos_mask = (1 << lp) - 1;
  213. header.dict_size = SWAP_LE32(header.dict_size);
  214. header.dst_size = SWAP_LE64(header.dst_size);
  215. if (header.dict_size == 0)
  216. header.dict_size = 1;
  217. buffer = xmalloc(MIN(header.dst_size, header.dict_size));
  218. num_probs = LZMA_BASE_SIZE + (LZMA_LIT_SIZE << (lc + lp));
  219. p = xmalloc(num_probs * sizeof(*p));
  220. num_probs = LZMA_LITERAL + (LZMA_LIT_SIZE << (lc + lp));
  221. for (i = 0; i < num_probs; i++)
  222. p[i] = (1 << RC_MODEL_TOTAL_BITS) >> 1;
  223. rc_init(&rc, src_fd, 0x10000);
  224. while (global_pos + buffer_pos < header.dst_size) {
  225. int pos_state = (buffer_pos + global_pos) & pos_state_mask;
  226. prob =
  227. p + LZMA_IS_MATCH + (state << LZMA_NUM_POS_BITS_MAX) + pos_state;
  228. if (rc_is_bit_0(&rc, prob)) {
  229. mi = 1;
  230. rc_update_bit_0(&rc, prob);
  231. prob = (p + LZMA_LITERAL + (LZMA_LIT_SIZE
  232. * ((((buffer_pos + global_pos) & literal_pos_mask) << lc)
  233. + (previous_byte >> (8 - lc)))));
  234. if (state >= LZMA_NUM_LIT_STATES) {
  235. int match_byte;
  236. pos = buffer_pos - rep0;
  237. while (pos >= header.dict_size)
  238. pos += header.dict_size;
  239. match_byte = buffer[pos];
  240. do {
  241. int bit;
  242. match_byte <<= 1;
  243. bit = match_byte & 0x100;
  244. prob_lit = prob + 0x100 + bit + mi;
  245. if (rc_get_bit(&rc, prob_lit, &mi)) {
  246. if (!bit)
  247. break;
  248. } else {
  249. if (bit)
  250. break;
  251. }
  252. } while (mi < 0x100);
  253. }
  254. while (mi < 0x100) {
  255. prob_lit = prob + mi;
  256. rc_get_bit(&rc, prob_lit, &mi);
  257. }
  258. previous_byte = (uint8_t) mi;
  259. buffer[buffer_pos++] = previous_byte;
  260. if (buffer_pos == header.dict_size) {
  261. buffer_pos = 0;
  262. global_pos += header.dict_size;
  263. // FIXME: error check
  264. write(dst_fd, buffer, header.dict_size);
  265. USE_DESKTOP(total_written += header.dict_size;)
  266. }
  267. if (state < 4)
  268. state = 0;
  269. else if (state < 10)
  270. state -= 3;
  271. else
  272. state -= 6;
  273. } else {
  274. int offset;
  275. uint16_t *prob_len;
  276. rc_update_bit_1(&rc, prob);
  277. prob = p + LZMA_IS_REP + state;
  278. if (rc_is_bit_0(&rc, prob)) {
  279. rc_update_bit_0(&rc, prob);
  280. rep3 = rep2;
  281. rep2 = rep1;
  282. rep1 = rep0;
  283. state = state < LZMA_NUM_LIT_STATES ? 0 : 3;
  284. prob = p + LZMA_LEN_CODER;
  285. } else {
  286. rc_update_bit_1(&rc, prob);
  287. prob = p + LZMA_IS_REP_G0 + state;
  288. if (rc_is_bit_0(&rc, prob)) {
  289. rc_update_bit_0(&rc, prob);
  290. prob = (p + LZMA_IS_REP_0_LONG
  291. + (state << LZMA_NUM_POS_BITS_MAX) + pos_state);
  292. if (rc_is_bit_0(&rc, prob)) {
  293. rc_update_bit_0(&rc, prob);
  294. state = state < LZMA_NUM_LIT_STATES ? 9 : 11;
  295. pos = buffer_pos - rep0;
  296. while (pos >= header.dict_size)
  297. pos += header.dict_size;
  298. previous_byte = buffer[pos];
  299. buffer[buffer_pos++] = previous_byte;
  300. if (buffer_pos == header.dict_size) {
  301. buffer_pos = 0;
  302. global_pos += header.dict_size;
  303. // FIXME: error check
  304. write(dst_fd, buffer, header.dict_size);
  305. USE_DESKTOP(total_written += header.dict_size;)
  306. }
  307. continue;
  308. } else {
  309. rc_update_bit_1(&rc, prob);
  310. }
  311. } else {
  312. uint32_t distance;
  313. rc_update_bit_1(&rc, prob);
  314. prob = p + LZMA_IS_REP_G1 + state;
  315. if (rc_is_bit_0(&rc, prob)) {
  316. rc_update_bit_0(&rc, prob);
  317. distance = rep1;
  318. } else {
  319. rc_update_bit_1(&rc, prob);
  320. prob = p + LZMA_IS_REP_G2 + state;
  321. if (rc_is_bit_0(&rc, prob)) {
  322. rc_update_bit_0(&rc, prob);
  323. distance = rep2;
  324. } else {
  325. rc_update_bit_1(&rc, prob);
  326. distance = rep3;
  327. rep3 = rep2;
  328. }
  329. rep2 = rep1;
  330. }
  331. rep1 = rep0;
  332. rep0 = distance;
  333. }
  334. state = state < LZMA_NUM_LIT_STATES ? 8 : 11;
  335. prob = p + LZMA_REP_LEN_CODER;
  336. }
  337. prob_len = prob + LZMA_LEN_CHOICE;
  338. if (rc_is_bit_0(&rc, prob_len)) {
  339. rc_update_bit_0(&rc, prob_len);
  340. prob_len = (prob + LZMA_LEN_LOW
  341. + (pos_state << LZMA_LEN_NUM_LOW_BITS));
  342. offset = 0;
  343. num_bits = LZMA_LEN_NUM_LOW_BITS;
  344. } else {
  345. rc_update_bit_1(&rc, prob_len);
  346. prob_len = prob + LZMA_LEN_CHOICE_2;
  347. if (rc_is_bit_0(&rc, prob_len)) {
  348. rc_update_bit_0(&rc, prob_len);
  349. prob_len = (prob + LZMA_LEN_MID
  350. + (pos_state << LZMA_LEN_NUM_MID_BITS));
  351. offset = 1 << LZMA_LEN_NUM_LOW_BITS;
  352. num_bits = LZMA_LEN_NUM_MID_BITS;
  353. } else {
  354. rc_update_bit_1(&rc, prob_len);
  355. prob_len = prob + LZMA_LEN_HIGH;
  356. offset = ((1 << LZMA_LEN_NUM_LOW_BITS)
  357. + (1 << LZMA_LEN_NUM_MID_BITS));
  358. num_bits = LZMA_LEN_NUM_HIGH_BITS;
  359. }
  360. }
  361. rc_bit_tree_decode(&rc, prob_len, num_bits, &len);
  362. len += offset;
  363. if (state < 4) {
  364. int pos_slot;
  365. state += LZMA_NUM_LIT_STATES;
  366. prob =
  367. p + LZMA_POS_SLOT +
  368. ((len <
  369. LZMA_NUM_LEN_TO_POS_STATES ? len :
  370. LZMA_NUM_LEN_TO_POS_STATES - 1)
  371. << LZMA_NUM_POS_SLOT_BITS);
  372. rc_bit_tree_decode(&rc, prob, LZMA_NUM_POS_SLOT_BITS,
  373. &pos_slot);
  374. if (pos_slot >= LZMA_START_POS_MODEL_INDEX) {
  375. num_bits = (pos_slot >> 1) - 1;
  376. rep0 = 2 | (pos_slot & 1);
  377. if (pos_slot < LZMA_END_POS_MODEL_INDEX) {
  378. rep0 <<= num_bits;
  379. prob = p + LZMA_SPEC_POS + rep0 - pos_slot - 1;
  380. } else {
  381. num_bits -= LZMA_NUM_ALIGN_BITS;
  382. while (num_bits--)
  383. rep0 = (rep0 << 1) | rc_direct_bit(&rc);
  384. prob = p + LZMA_ALIGN;
  385. rep0 <<= LZMA_NUM_ALIGN_BITS;
  386. num_bits = LZMA_NUM_ALIGN_BITS;
  387. }
  388. i = 1;
  389. mi = 1;
  390. while (num_bits--) {
  391. if (rc_get_bit(&rc, prob + mi, &mi))
  392. rep0 |= i;
  393. i <<= 1;
  394. }
  395. } else
  396. rep0 = pos_slot;
  397. if (++rep0 == 0)
  398. break;
  399. }
  400. len += LZMA_MATCH_MIN_LEN;
  401. do {
  402. pos = buffer_pos - rep0;
  403. while (pos >= header.dict_size)
  404. pos += header.dict_size;
  405. previous_byte = buffer[pos];
  406. buffer[buffer_pos++] = previous_byte;
  407. if (buffer_pos == header.dict_size) {
  408. buffer_pos = 0;
  409. global_pos += header.dict_size;
  410. // FIXME: error check
  411. write(dst_fd, buffer, header.dict_size);
  412. USE_DESKTOP(total_written += header.dict_size;)
  413. }
  414. len--;
  415. } while (len != 0 && buffer_pos < header.dst_size);
  416. }
  417. }
  418. // FIXME: error check
  419. write(dst_fd, buffer, buffer_pos);
  420. USE_DESKTOP(total_written += buffer_pos;)
  421. rc_free(&rc);
  422. return USE_DESKTOP(total_written) + 0;
  423. }