OLD | NEW |
(Empty) | |
| 1 /////////////////////////////////////////////////////////////////////////////// |
| 2 // |
| 3 /// \file lzma_common.h |
| 4 /// \brief Private definitions common to LZMA encoder and decoder |
| 5 /// |
| 6 // Authors: Igor Pavlov |
| 7 // Lasse Collin |
| 8 // |
| 9 // This file has been put into the public domain. |
| 10 // You can do whatever you want with this file. |
| 11 // |
| 12 /////////////////////////////////////////////////////////////////////////////// |
| 13 |
| 14 #ifndef LZMA_LZMA_COMMON_H |
| 15 #define LZMA_LZMA_COMMON_H |
| 16 |
| 17 #include "common.h" |
| 18 #include "range_common.h" |
| 19 |
| 20 |
| 21 /////////////////// |
| 22 // Miscellaneous // |
| 23 /////////////////// |
| 24 |
| 25 /// Maximum number of position states. A position state is the lowest pos bits |
| 26 /// number of bits of the current uncompressed offset. In some places there |
| 27 /// are different sets of probabilities for different pos states. |
| 28 #define POS_STATES_MAX (1 << LZMA_PB_MAX) |
| 29 |
| 30 |
| 31 /// Validates lc, lp, and pb. |
| 32 static inline bool |
| 33 is_lclppb_valid(const lzma_options_lzma *options) |
| 34 { |
| 35 return options->lc <= LZMA_LCLP_MAX && options->lp <= LZMA_LCLP_MAX |
| 36 && options->lc + options->lp <= LZMA_LCLP_MAX |
| 37 && options->pb <= LZMA_PB_MAX; |
| 38 } |
| 39 |
| 40 |
| 41 /////////// |
| 42 // State // |
| 43 /////////// |
| 44 |
| 45 /// This enum is used to track which events have occurred most recently and |
| 46 /// in which order. This information is used to predict the next event. |
| 47 /// |
| 48 /// Events: |
| 49 /// - Literal: One 8-bit byte |
| 50 /// - Match: Repeat a chunk of data at some distance |
| 51 /// - Long repeat: Multi-byte match at a recently seen distance |
| 52 /// - Short repeat: One-byte repeat at a recently seen distance |
| 53 /// |
| 54 /// The event names are in from STATE_oldest_older_previous. REP means |
| 55 /// either short or long repeated match, and NONLIT means any non-literal. |
| 56 typedef enum { |
| 57 STATE_LIT_LIT, |
| 58 STATE_MATCH_LIT_LIT, |
| 59 STATE_REP_LIT_LIT, |
| 60 STATE_SHORTREP_LIT_LIT, |
| 61 STATE_MATCH_LIT, |
| 62 STATE_REP_LIT, |
| 63 STATE_SHORTREP_LIT, |
| 64 STATE_LIT_MATCH, |
| 65 STATE_LIT_LONGREP, |
| 66 STATE_LIT_SHORTREP, |
| 67 STATE_NONLIT_MATCH, |
| 68 STATE_NONLIT_REP, |
| 69 } lzma_lzma_state; |
| 70 |
| 71 |
| 72 /// Total number of states |
| 73 #define STATES 12 |
| 74 |
| 75 /// The lowest 7 states indicate that the previous state was a literal. |
| 76 #define LIT_STATES 7 |
| 77 |
| 78 |
| 79 /// Indicate that the latest state was a literal. |
| 80 #define update_literal(state) \ |
| 81 state = ((state) <= STATE_SHORTREP_LIT_LIT \ |
| 82 ? STATE_LIT_LIT \ |
| 83 : ((state) <= STATE_LIT_SHORTREP \ |
| 84 ? (state) - 3 \ |
| 85 : (state) - 6)) |
| 86 |
| 87 /// Indicate that the latest state was a match. |
| 88 #define update_match(state) \ |
| 89 state = ((state) < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH) |
| 90 |
| 91 /// Indicate that the latest state was a long repeated match. |
| 92 #define update_long_rep(state) \ |
| 93 state = ((state) < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP) |
| 94 |
| 95 /// Indicate that the latest state was a short match. |
| 96 #define update_short_rep(state) \ |
| 97 state = ((state) < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP) |
| 98 |
| 99 /// Test if the previous state was a literal. |
| 100 #define is_literal_state(state) \ |
| 101 ((state) < LIT_STATES) |
| 102 |
| 103 |
| 104 ///////////// |
| 105 // Literal // |
| 106 ///////////// |
| 107 |
| 108 /// Each literal coder is divided in three sections: |
| 109 /// - 0x001-0x0FF: Without match byte |
| 110 /// - 0x101-0x1FF: With match byte; match bit is 0 |
| 111 /// - 0x201-0x2FF: With match byte; match bit is 1 |
| 112 /// |
| 113 /// Match byte is used when the previous LZMA symbol was something else than |
| 114 /// a literal (that is, it was some kind of match). |
| 115 #define LITERAL_CODER_SIZE 0x300 |
| 116 |
| 117 /// Maximum number of literal coders |
| 118 #define LITERAL_CODERS_MAX (1 << LZMA_LCLP_MAX) |
| 119 |
| 120 /// Locate the literal coder for the next literal byte. The choice depends on |
| 121 /// - the lowest literal_pos_bits bits of the position of the current |
| 122 /// byte; and |
| 123 /// - the highest literal_context_bits bits of the previous byte. |
| 124 #define literal_subcoder(probs, lc, lp_mask, pos, prev_byte) \ |
| 125 ((probs)[(((pos) & lp_mask) << lc) + ((prev_byte) >> (8 - lc))]) |
| 126 |
| 127 |
| 128 static inline void |
| 129 literal_init(probability (*probs)[LITERAL_CODER_SIZE], |
| 130 uint32_t lc, uint32_t lp) |
| 131 { |
| 132 assert(lc + lp <= LZMA_LCLP_MAX); |
| 133 |
| 134 const uint32_t coders = 1U << (lc + lp); |
| 135 |
| 136 for (uint32_t i = 0; i < coders; ++i) |
| 137 for (uint32_t j = 0; j < LITERAL_CODER_SIZE; ++j) |
| 138 bit_reset(probs[i][j]); |
| 139 |
| 140 return; |
| 141 } |
| 142 |
| 143 |
| 144 ////////////////// |
| 145 // Match length // |
| 146 ////////////////// |
| 147 |
| 148 // Minimum length of a match is two bytes. |
| 149 #define MATCH_LEN_MIN 2 |
| 150 |
| 151 // Match length is encoded with 4, 5, or 10 bits. |
| 152 // |
| 153 // Length Bits |
| 154 // 2-9 4 = Choice=0 + 3 bits |
| 155 // 10-17 5 = Choice=1 + Choice2=0 + 3 bits |
| 156 // 18-273 10 = Choice=1 + Choice2=1 + 8 bits |
| 157 #define LEN_LOW_BITS 3 |
| 158 #define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS) |
| 159 #define LEN_MID_BITS 3 |
| 160 #define LEN_MID_SYMBOLS (1 << LEN_MID_BITS) |
| 161 #define LEN_HIGH_BITS 8 |
| 162 #define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS) |
| 163 #define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS) |
| 164 |
| 165 // Maximum length of a match is 273 which is a result of the encoding |
| 166 // described above. |
| 167 #define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1) |
| 168 |
| 169 |
| 170 //////////////////// |
| 171 // Match distance // |
| 172 //////////////////// |
| 173 |
| 174 // Different set of probabilities is used for match distances that have very |
| 175 // short match length: Lengths of 2, 3, and 4 bytes have a separate set of |
| 176 // probabilities for each length. The matches with longer length use a shared |
| 177 // set of probabilities. |
| 178 #define LEN_TO_POS_STATES 4 |
| 179 |
| 180 // Macro to get the index of the appropriate probability array. |
| 181 #define get_len_to_pos_state(len) \ |
| 182 ((len) < LEN_TO_POS_STATES + MATCH_LEN_MIN \ |
| 183 ? (len) - MATCH_LEN_MIN \ |
| 184 : LEN_TO_POS_STATES - 1) |
| 185 |
| 186 // The highest two bits of a match distance (pos slot) are encoded using six |
| 187 // bits. See fastpos.h for more explanation. |
| 188 #define POS_SLOT_BITS 6 |
| 189 #define POS_SLOTS (1 << POS_SLOT_BITS) |
| 190 |
| 191 // Match distances up to 127 are fully encoded using probabilities. Since |
| 192 // the highest two bits (pos slot) are always encoded using six bits, the |
| 193 // distances 0-3 don't need any additional bits to encode, since the pos |
| 194 // slot itself is the same as the actual distance. START_POS_MODEL_INDEX |
| 195 // indicates the first pos slot where at least one additional bit is needed. |
| 196 #define START_POS_MODEL_INDEX 4 |
| 197 |
| 198 // Match distances greater than 127 are encoded in three pieces: |
| 199 // - pos slot: the highest two bits |
| 200 // - direct bits: 2-26 bits below the highest two bits |
| 201 // - alignment bits: four lowest bits |
| 202 // |
| 203 // Direct bits don't use any probabilities. |
| 204 // |
| 205 // The pos slot value of 14 is for distances 128-191 (see the table in |
| 206 // fastpos.h to understand why). |
| 207 #define END_POS_MODEL_INDEX 14 |
| 208 |
| 209 // Pos slots that indicate a distance <= 127. |
| 210 #define FULL_DISTANCES_BITS (END_POS_MODEL_INDEX / 2) |
| 211 #define FULL_DISTANCES (1 << FULL_DISTANCES_BITS) |
| 212 |
| 213 // For match distances greater than 127, only the highest two bits and the |
| 214 // lowest four bits (alignment) is encoded using probabilities. |
| 215 #define ALIGN_BITS 4 |
| 216 #define ALIGN_TABLE_SIZE (1 << ALIGN_BITS) |
| 217 #define ALIGN_MASK (ALIGN_TABLE_SIZE - 1) |
| 218 |
| 219 // LZMA remembers the four most recent match distances. Reusing these distances |
| 220 // tends to take less space than re-encoding the actual distance value. |
| 221 #define REP_DISTANCES 4 |
| 222 |
| 223 #endif |
OLD | NEW |