[3320] | 1 | /*
|
---|
| 2 | * LZMA2 definitions
|
---|
| 3 | *
|
---|
| 4 | * Authors: Lasse Collin <lasse.collin@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 XZ_FUNC 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 XZ_FUNC 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 XZ_FUNC 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 XZ_FUNC 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 XZ_FUNC 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 XZ_FUNC 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
|
---|