"Fossies" - the Fresh Open Source Software Archive

Member "rufus-3.13/src/bled/decompress_unlzma.c" (20 Nov 2020, 12473 Bytes) of package /linux/misc/rufus-3.13.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "decompress_unlzma.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 3.12_vs_3.13.

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