src/liblzma/lzma/lzma_encoder_private.h

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       lzma_encoder_private.h
   4 /// \brief      Private definitions for LZMA encoder
   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_ENCODER_PRIVATE_H
  22 #define LZMA_LZMA_ENCODER_PRIVATE_H
  23
  24 #include "lzma_encoder.h"
  25 #include "lzma_common.h"
  26 #include "lz_encoder.h"
  27 #include "range_encoder.h"
  28
  29 // We need space for about two encoding loops, because there is no check
  30 // for available buffer space before end of payload marker gets written.
  31 // 2*26 bytes should be enough for this... but Lasse isn't very sure about
  32 // the exact value. 64 bytes certainly is enough. :-)
  33 #if LZMA_LZ_TEMP_SIZE < 64
  34 #       error LZMA_LZ_TEMP_SIZE is too small.
  35 #endif
  36
  37
  38 #define move_pos(num) \
  39 do { \
  40         assert((int32_t)(num) >= 0); \
  41         if ((num) != 0) { \
  42                 coder->additional_offset += num; \
  43                 coder->lz.skip(&coder->lz, num); \
  44         } \
  45 } while (0)
  46
  47
  48 #define get_pos_slot(pos) \
  49         ((pos) < (1 << 11) \
  50                 ? lzma_fastpos[pos] \
  51                 : ((pos) < (1 << 21) \
  52                         ? lzma_fastpos[(pos) >> 10] + 20 \
  53                         : lzma_fastpos[(pos) >> 20] + 40))
  54
  55
  56 #define get_pos_slot_2(pos) \
  57         ((pos) < (1 << 17) \
  58                 ? lzma_fastpos[(pos) >> 6] + 12 \
  59                 : ((pos) < (1 << 27) \
  60                         ? lzma_fastpos[(pos) >> 16] + 32 \
  61                         : lzma_fastpos[(pos) >> 26] + 52))
  62
  63
  64 /// This isn't modified once its contents have been
  65 /// initialized by lzma_fastpos_init().
  66 extern uint8_t lzma_fastpos[1 << 11];
  67
  68
  69 typedef struct {
  70         probability choice;
  71         probability choice2;
  72         probability low[POS_STATES_MAX][LEN_LOW_SYMBOLS];
  73         probability mid[POS_STATES_MAX][LEN_MID_SYMBOLS];
  74         probability high[LEN_HIGH_SYMBOLS];
  75
  76         uint32_t prices[POS_STATES_MAX][LEN_SYMBOLS];
  77         uint32_t table_size;
  78         uint32_t counters[POS_STATES_MAX];
  79
  80 } lzma_length_encoder;
  81
  82
  83 typedef struct {
  84         uint32_t state;
  85
  86         bool prev_1_is_char;
  87         bool prev_2;
  88
  89         uint32_t pos_prev_2;
  90         uint32_t back_prev_2;
  91
  92         uint32_t price;
  93         uint32_t pos_prev;  // pos_next;
  94         uint32_t back_prev;
  95
  96         uint32_t backs[4];
  97
  98 } lzma_optimal;
  99
 100
 101 struct lzma_coder_s {
 102         // Next coder in the chain
 103         lzma_next_coder next;
 104
 105         // In window and match finder
 106         lzma_lz_encoder lz;
 107
 108         // Range encoder
 109         lzma_range_encoder rc;
 110
 111         // State
 112         uint32_t state;
 113         uint8_t previous_byte;
 114         uint32_t rep_distances[REP_DISTANCES];
 115
 116         // Misc
 117         uint32_t match_distances[MATCH_MAX_LEN * 2 + 2 + 1];
 118         uint32_t num_distance_pairs;
 119         uint32_t additional_offset;
 120         uint32_t now_pos; // Lowest 32 bits are enough here.
 121         bool best_compression;           ///< True when LZMA_MODE_BEST is used
 122         bool is_initialized;
 123
 124         // Literal encoder
 125         lzma_literal_coder *literal_coder;
 126
 127         // Bit encoders
 128         probability is_match[STATES][POS_STATES_MAX];
 129         probability is_rep[STATES];
 130         probability is_rep0[STATES];
 131         probability is_rep1[STATES];
 132         probability is_rep2[STATES];
 133         probability is_rep0_long[STATES][POS_STATES_MAX];
 134         probability pos_encoders[FULL_DISTANCES - END_POS_MODEL_INDEX];
 135
 136         // Bit Tree Encoders
 137         probability pos_slot_encoder[LEN_TO_POS_STATES][1 << POS_SLOT_BITS];
 138         probability pos_align_encoder[1 << ALIGN_BITS];
 139
 140         // Length encoders
 141         lzma_length_encoder len_encoder;
 142         lzma_length_encoder rep_match_len_encoder;
 143
 144         // Optimal
 145         lzma_optimal optimum[OPTS];
 146         uint32_t optimum_end_index;
 147         uint32_t optimum_current_index;
 148         uint32_t longest_match_length;
 149         bool longest_match_was_found;
 150
 151         // Prices
 152         uint32_t pos_slot_prices[LEN_TO_POS_STATES][DIST_TABLE_SIZE_MAX];
 153         uint32_t distances_prices[LEN_TO_POS_STATES][FULL_DISTANCES];
 154         uint32_t align_prices[ALIGN_TABLE_SIZE];
 155         uint32_t align_price_count;
 156         uint32_t dist_table_size;
 157         uint32_t match_price_count;
 158
 159         // LZMA specific settings
 160         uint32_t dictionary_size;        ///< Size in bytes
 161         uint32_t fast_bytes;
 162         uint32_t pos_state_bits;
 163         uint32_t pos_mask;         ///< (1 << pos_state_bits) - 1
 164 };
 165
 166
 167 extern void lzma_length_encoder_update_table(lzma_length_encoder *lencoder,
 168                 const uint32_t pos_state);
 169
 170 extern bool lzma_lzma_encode(lzma_coder *coder, uint8_t *restrict out,
 171                 size_t *restrict out_pos, size_t out_size);
 172
 173 extern void lzma_get_optimum(lzma_coder *restrict coder,
 174                 uint32_t *restrict back_res, uint32_t *restrict len_res);
 175
 176 extern void lzma_get_optimum_fast(lzma_coder *restrict coder,
 177                 uint32_t *restrict back_res, uint32_t *restrict len_res);
 178
 179
 180 // NOTE: Don't add 'restrict'.
 181 static inline void
 182 lzma_read_match_distances(lzma_coder *coder,
 183                 uint32_t *len_res, uint32_t *num_distance_pairs)
 184 {
 185         *len_res = 0;
 186
 187         coder->lz.get_matches(&coder->lz, coder->match_distances);
 188
 189         *num_distance_pairs = coder->match_distances[0];
 190
 191         if (*num_distance_pairs > 0) {
 192                 *len_res = coder->match_distances[*num_distance_pairs - 1];
 193                 assert(*len_res <= MATCH_MAX_LEN);
 194
 195                 if (*len_res == coder->fast_bytes) {
 196                         uint32_t offset = *len_res - 1;
 197                         const uint32_t distance = coder->match_distances[
 198                                         *num_distance_pairs] + 1;
 199                         uint32_t limit = MATCH_MAX_LEN - *len_res;
 200
 201                         assert(offset + limit < coder->lz.keep_size_after);
 202                         assert(coder->lz.read_pos <= coder->lz.write_pos);
 203
 204                         // If we are close to end of the stream, we may need
 205                         // to limit the length of the match.
 206                         if (coder->lz.write_pos - coder->lz.read_pos
 207                                         < offset + limit)
 208                                 limit = coder->lz.write_pos
 209                                         - (coder->lz.read_pos + offset);
 210
 211                         offset += coder->lz.read_pos;
 212                         uint32_t i = 0;
 213                         while (i < limit && coder->lz.buffer[offset + i]
 214                                         == coder->lz.buffer[
 215                                                 offset + i - distance])
 216                                 ++i;
 217
 218                         *len_res += i;
 219                 }
 220         }
 221
 222         ++coder->additional_offset;
 223
 224         return;
 225 }
 226
 227 #endif