kernel / pub / scm / linux / kernel / git / jesse / openvswitch / refs/tags/v3.0-rc6 / . / lib / xz / xz_lzma2.h

/* | |

* LZMA2 definitions | |

* | |

* Authors: Lasse Collin <lasse.collin@tukaani.org> | |

* Igor Pavlov <http://7-zip.org/> | |

* | |

* This file has been put into the public domain. | |

* You can do whatever you want with this file. | |

*/ | |

#ifndef XZ_LZMA2_H | |

#define XZ_LZMA2_H | |

/* Range coder constants */ | |

#define RC_SHIFT_BITS 8 | |

#define RC_TOP_BITS 24 | |

#define RC_TOP_VALUE (1 << RC_TOP_BITS) | |

#define RC_BIT_MODEL_TOTAL_BITS 11 | |

#define RC_BIT_MODEL_TOTAL (1 << RC_BIT_MODEL_TOTAL_BITS) | |

#define RC_MOVE_BITS 5 | |

/* | |

* Maximum number of position states. A position state is the lowest pb | |

* number of bits of the current uncompressed offset. In some places there | |

* are different sets of probabilities for different position states. | |

*/ | |

#define POS_STATES_MAX (1 << 4) | |

/* | |

* This enum is used to track which LZMA symbols have occurred most recently | |

* and in which order. This information is used to predict the next symbol. | |

* | |

* Symbols: | |

* - Literal: One 8-bit byte | |

* - Match: Repeat a chunk of data at some distance | |

* - Long repeat: Multi-byte match at a recently seen distance | |

* - Short repeat: One-byte repeat at a recently seen distance | |

* | |

* The symbol names are in from STATE_oldest_older_previous. REP means | |

* either short or long repeated match, and NONLIT means any non-literal. | |

*/ | |

enum lzma_state { | |

STATE_LIT_LIT, | |

STATE_MATCH_LIT_LIT, | |

STATE_REP_LIT_LIT, | |

STATE_SHORTREP_LIT_LIT, | |

STATE_MATCH_LIT, | |

STATE_REP_LIT, | |

STATE_SHORTREP_LIT, | |

STATE_LIT_MATCH, | |

STATE_LIT_LONGREP, | |

STATE_LIT_SHORTREP, | |

STATE_NONLIT_MATCH, | |

STATE_NONLIT_REP | |

}; | |

/* Total number of states */ | |

#define STATES 12 | |

/* The lowest 7 states indicate that the previous state was a literal. */ | |

#define LIT_STATES 7 | |

/* Indicate that the latest symbol was a literal. */ | |

static inline void lzma_state_literal(enum lzma_state *state) | |

{ | |

if (*state <= STATE_SHORTREP_LIT_LIT) | |

*state = STATE_LIT_LIT; | |

else if (*state <= STATE_LIT_SHORTREP) | |

*state -= 3; | |

else | |

*state -= 6; | |

} | |

/* Indicate that the latest symbol was a match. */ | |

static inline void lzma_state_match(enum lzma_state *state) | |

{ | |

*state = *state < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH; | |

} | |

/* Indicate that the latest state was a long repeated match. */ | |

static inline void lzma_state_long_rep(enum lzma_state *state) | |

{ | |

*state = *state < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP; | |

} | |

/* Indicate that the latest symbol was a short match. */ | |

static inline void lzma_state_short_rep(enum lzma_state *state) | |

{ | |

*state = *state < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP; | |

} | |

/* Test if the previous symbol was a literal. */ | |

static inline bool lzma_state_is_literal(enum lzma_state state) | |

{ | |

return state < LIT_STATES; | |

} | |

/* Each literal coder is divided in three sections: | |

* - 0x001-0x0FF: Without match byte | |

* - 0x101-0x1FF: With match byte; match bit is 0 | |

* - 0x201-0x2FF: With match byte; match bit is 1 | |

* | |

* Match byte is used when the previous LZMA symbol was something else than | |

* a literal (that is, it was some kind of match). | |

*/ | |

#define LITERAL_CODER_SIZE 0x300 | |

/* Maximum number of literal coders */ | |

#define LITERAL_CODERS_MAX (1 << 4) | |

/* Minimum length of a match is two bytes. */ | |

#define MATCH_LEN_MIN 2 | |

/* Match length is encoded with 4, 5, or 10 bits. | |

* | |

* Length Bits | |

* 2-9 4 = Choice=0 + 3 bits | |

* 10-17 5 = Choice=1 + Choice2=0 + 3 bits | |

* 18-273 10 = Choice=1 + Choice2=1 + 8 bits | |

*/ | |

#define LEN_LOW_BITS 3 | |

#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS) | |

#define LEN_MID_BITS 3 | |

#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS) | |

#define LEN_HIGH_BITS 8 | |

#define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS) | |

#define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS) | |

/* | |

* Maximum length of a match is 273 which is a result of the encoding | |

* described above. | |

*/ | |

#define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1) | |

/* | |

* Different sets of probabilities are used for match distances that have | |

* very short match length: Lengths of 2, 3, and 4 bytes have a separate | |

* set of probabilities for each length. The matches with longer length | |

* use a shared set of probabilities. | |

*/ | |

#define DIST_STATES 4 | |

/* | |

* Get the index of the appropriate probability array for decoding | |

* the distance slot. | |

*/ | |

static inline uint32_t lzma_get_dist_state(uint32_t len) | |

{ | |

return len < DIST_STATES + MATCH_LEN_MIN | |

? len - MATCH_LEN_MIN : DIST_STATES - 1; | |

} | |

/* | |

* The highest two bits of a 32-bit match distance are encoded using six bits. | |

* This six-bit value is called a distance slot. This way encoding a 32-bit | |

* value takes 6-36 bits, larger values taking more bits. | |

*/ | |

#define DIST_SLOT_BITS 6 | |

#define DIST_SLOTS (1 << DIST_SLOT_BITS) | |

/* Match distances up to 127 are fully encoded using probabilities. Since | |

* the highest two bits (distance slot) are always encoded using six bits, | |

* the distances 0-3 don't need any additional bits to encode, since the | |

* distance slot itself is the same as the actual distance. DIST_MODEL_START | |

* indicates the first distance slot where at least one additional bit is | |

* needed. | |

*/ | |

#define DIST_MODEL_START 4 | |

/* | |

* Match distances greater than 127 are encoded in three pieces: | |

* - distance slot: the highest two bits | |

* - direct bits: 2-26 bits below the highest two bits | |

* - alignment bits: four lowest bits | |

* | |

* Direct bits don't use any probabilities. | |

* | |

* The distance slot value of 14 is for distances 128-191. | |

*/ | |

#define DIST_MODEL_END 14 | |

/* Distance slots that indicate a distance <= 127. */ | |

#define FULL_DISTANCES_BITS (DIST_MODEL_END / 2) | |

#define FULL_DISTANCES (1 << FULL_DISTANCES_BITS) | |

/* | |

* For match distances greater than 127, only the highest two bits and the | |

* lowest four bits (alignment) is encoded using probabilities. | |

*/ | |

#define ALIGN_BITS 4 | |

#define ALIGN_SIZE (1 << ALIGN_BITS) | |

#define ALIGN_MASK (ALIGN_SIZE - 1) | |

/* Total number of all probability variables */ | |

#define PROBS_TOTAL (1846 + LITERAL_CODERS_MAX * LITERAL_CODER_SIZE) | |

/* | |

* LZMA remembers the four most recent match distances. Reusing these | |

* distances tends to take less space than re-encoding the actual | |

* distance value. | |

*/ | |

#define REPS 4 | |

#endif |