Home | History | Annotate | Download | only in xz-embedded
      1 /*
      2  * LZMA2 definitions
      3  *
      4  * Authors: Lasse Collin <lasse.collin (at) tukaani.org>
      5  *          Igor Pavlov <http://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 
     11 #ifndef XZ_LZMA2_H
     12 #define XZ_LZMA2_H
     13 
     14 /* Range coder constants */
     15 #define RC_SHIFT_BITS 8
     16 #define RC_TOP_BITS 24
     17 #define RC_TOP_VALUE (1 << RC_TOP_BITS)
     18 #define RC_BIT_MODEL_TOTAL_BITS 11
     19 #define RC_BIT_MODEL_TOTAL (1 << RC_BIT_MODEL_TOTAL_BITS)
     20 #define RC_MOVE_BITS 5
     21 
     22 /*
     23  * Maximum number of position states. A position state is the lowest pb
     24  * number of bits of the current uncompressed offset. In some places there
     25  * are different sets of probabilities for different position states.
     26  */
     27 #define POS_STATES_MAX (1 << 4)
     28 
     29 /*
     30  * This enum is used to track which LZMA symbols have occurred most recently
     31  * and in which order. This information is used to predict the next symbol.
     32  *
     33  * Symbols:
     34  *  - Literal: One 8-bit byte
     35  *  - Match: Repeat a chunk of data at some distance
     36  *  - Long repeat: Multi-byte match at a recently seen distance
     37  *  - Short repeat: One-byte repeat at a recently seen distance
     38  *
     39  * The symbol names are in from STATE_oldest_older_previous. REP means
     40  * either short or long repeated match, and NONLIT means any non-literal.
     41  */
     42 enum lzma_state {
     43 	STATE_LIT_LIT,
     44 	STATE_MATCH_LIT_LIT,
     45 	STATE_REP_LIT_LIT,
     46 	STATE_SHORTREP_LIT_LIT,
     47 	STATE_MATCH_LIT,
     48 	STATE_REP_LIT,
     49 	STATE_SHORTREP_LIT,
     50 	STATE_LIT_MATCH,
     51 	STATE_LIT_LONGREP,
     52 	STATE_LIT_SHORTREP,
     53 	STATE_NONLIT_MATCH,
     54 	STATE_NONLIT_REP
     55 };
     56 
     57 /* Total number of states */
     58 #define STATES 12
     59 
     60 /* The lowest 7 states indicate that the previous state was a literal. */
     61 #define LIT_STATES 7
     62 
     63 /* Indicate that the latest symbol was a literal. */
     64 static inline void lzma_state_literal(enum lzma_state *state)
     65 {
     66 	if (*state <= STATE_SHORTREP_LIT_LIT)
     67 		*state = STATE_LIT_LIT;
     68 	else if (*state <= STATE_LIT_SHORTREP)
     69 		*state -= 3;
     70 	else
     71 		*state -= 6;
     72 }
     73 
     74 /* Indicate that the latest symbol was a match. */
     75 static inline void lzma_state_match(enum lzma_state *state)
     76 {
     77 	*state = *state < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH;
     78 }
     79 
     80 /* Indicate that the latest state was a long repeated match. */
     81 static inline void lzma_state_long_rep(enum lzma_state *state)
     82 {
     83 	*state = *state < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP;
     84 }
     85 
     86 /* Indicate that the latest symbol was a short match. */
     87 static inline void lzma_state_short_rep(enum lzma_state *state)
     88 {
     89 	*state = *state < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP;
     90 }
     91 
     92 /* Test if the previous symbol was a literal. */
     93 static inline bool lzma_state_is_literal(enum lzma_state state)
     94 {
     95 	return state < LIT_STATES;
     96 }
     97 
     98 /* Each literal coder is divided in three sections:
     99  *   - 0x001-0x0FF: Without match byte
    100  *   - 0x101-0x1FF: With match byte; match bit is 0
    101  *   - 0x201-0x2FF: With match byte; match bit is 1
    102  *
    103  * Match byte is used when the previous LZMA symbol was something else than
    104  * a literal (that is, it was some kind of match).
    105  */
    106 #define LITERAL_CODER_SIZE 0x300
    107 
    108 /* Maximum number of literal coders */
    109 #define LITERAL_CODERS_MAX (1 << 4)
    110 
    111 /* Minimum length of a match is two bytes. */
    112 #define MATCH_LEN_MIN 2
    113 
    114 /* Match length is encoded with 4, 5, or 10 bits.
    115  *
    116  * Length   Bits
    117  *  2-9      4 = Choice=0 + 3 bits
    118  * 10-17     5 = Choice=1 + Choice2=0 + 3 bits
    119  * 18-273   10 = Choice=1 + Choice2=1 + 8 bits
    120  */
    121 #define LEN_LOW_BITS 3
    122 #define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS)
    123 #define LEN_MID_BITS 3
    124 #define LEN_MID_SYMBOLS (1 << LEN_MID_BITS)
    125 #define LEN_HIGH_BITS 8
    126 #define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS)
    127 #define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS)
    128 
    129 /*
    130  * Maximum length of a match is 273 which is a result of the encoding
    131  * described above.
    132  */
    133 #define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1)
    134 
    135 /*
    136  * Different sets of probabilities are used for match distances that have
    137  * very short match length: Lengths of 2, 3, and 4 bytes have a separate
    138  * set of probabilities for each length. The matches with longer length
    139  * use a shared set of probabilities.
    140  */
    141 #define DIST_STATES 4
    142 
    143 /*
    144  * Get the index of the appropriate probability array for decoding
    145  * the distance slot.
    146  */
    147 static inline uint32_t lzma_get_dist_state(uint32_t len)
    148 {
    149 	return len < DIST_STATES + MATCH_LEN_MIN
    150 			? len - MATCH_LEN_MIN : DIST_STATES - 1;
    151 }
    152 
    153 /*
    154  * The highest two bits of a 32-bit match distance are encoded using six bits.
    155  * This six-bit value is called a distance slot. This way encoding a 32-bit
    156  * value takes 6-36 bits, larger values taking more bits.
    157  */
    158 #define DIST_SLOT_BITS 6
    159 #define DIST_SLOTS (1 << DIST_SLOT_BITS)
    160 
    161 /* Match distances up to 127 are fully encoded using probabilities. Since
    162  * the highest two bits (distance slot) are always encoded using six bits,
    163  * the distances 0-3 don't need any additional bits to encode, since the
    164  * distance slot itself is the same as the actual distance. DIST_MODEL_START
    165  * indicates the first distance slot where at least one additional bit is
    166  * needed.
    167  */
    168 #define DIST_MODEL_START 4
    169 
    170 /*
    171  * Match distances greater than 127 are encoded in three pieces:
    172  *   - distance slot: the highest two bits
    173  *   - direct bits: 2-26 bits below the highest two bits
    174  *   - alignment bits: four lowest bits
    175  *
    176  * Direct bits don't use any probabilities.
    177  *
    178  * The distance slot value of 14 is for distances 128-191.
    179  */
    180 #define DIST_MODEL_END 14
    181 
    182 /* Distance slots that indicate a distance <= 127. */
    183 #define FULL_DISTANCES_BITS (DIST_MODEL_END / 2)
    184 #define FULL_DISTANCES (1 << FULL_DISTANCES_BITS)
    185 
    186 /*
    187  * For match distances greater than 127, only the highest two bits and the
    188  * lowest four bits (alignment) is encoded using probabilities.
    189  */
    190 #define ALIGN_BITS 4
    191 #define ALIGN_SIZE (1 << ALIGN_BITS)
    192 #define ALIGN_MASK (ALIGN_SIZE - 1)
    193 
    194 /* Total number of all probability variables */
    195 #define PROBS_TOTAL (1846 + LITERAL_CODERS_MAX * LITERAL_CODER_SIZE)
    196 
    197 /*
    198  * LZMA remembers the four most recent match distances. Reusing these
    199  * distances tends to take less space than re-encoding the actual
    200  * distance value.
    201  */
    202 #define REPS 4
    203 
    204 #endif
    205