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