Branch data     Line data    Source code

       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 lzma_state_literal(enum lzma_state *state)
      65                 :            : {
      66         [ #  # ]:          0 :         if (*state <= STATE_SHORTREP_LIT_LIT)
      67                 :          0 :                 *state = STATE_LIT_LIT;
      68         [ #  # ]:          0 :         else if (*state <= STATE_LIT_SHORTREP)
      69                 :          0 :                 *state -= 3;
      70                 :            :         else
      71                 :          0 :                 *state -= 6;
      72                 :            : }
      73                 :            : 
      74                 :            : /* Indicate that the latest symbol was a match. */
      75                 :            : static inline void lzma_state_match(enum lzma_state *state)
      76                 :            : {
      77         [ #  # ]:          0 :         *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 lzma_state_long_rep(enum lzma_state *state)
      82                 :            : {
      83         [ #  # ]:          0 :         *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 lzma_state_short_rep(enum lzma_state *state)
      88                 :            : {
      89         [ #  # ]:          0 :         *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 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 lzma_get_dist_state(uint32_t len)
     148                 :            : {
     149                 :            :         return len < DIST_STATES + MATCH_LEN_MIN
     150         [ #  # ]:          0 :                         ? 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