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