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