src/liblzma/lzma/lzma_common.h

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