FreeBSD/Linux Kernel Cross Reference
sys/contrib/xz-embedded/linux/lib/xz/xz_lzma2.h

     /*
      * LZMA2 definitions
      *
      * Authors: Lasse Collin <lasse.collin@tukaani.org>
      *          Igor Pavlov <https://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

Cache object: 36501d2f5864eb8dcb45d7f54f11a18f