1 /////////////////////////////////////////////////////////////////////////////// 2 // 3 /// \file lz_encoder.h 4 /// \brief LZ in window and match finder API 5 /// 6 // Authors: Igor Pavlov 7 // Lasse Collin 8 // 9 // This file has been put into the public domain. 10 // You can do whatever you want with this file. 11 // 12 /////////////////////////////////////////////////////////////////////////////// 13 14 #ifndef LZMA_LZ_ENCODER_H 15 #define LZMA_LZ_ENCODER_H 16 17 #include "common.h" 18 19 20 // For now, the dictionary size is limited to 1.5 GiB. This may grow 21 // in the future if needed, but it needs a little more work than just 22 // changing this check. 23 #define IS_ENC_DICT_SIZE_VALID(size) \ 24 ((size) >= LZMA_DICT_SIZE_MIN \ 25 && (size) <= (UINT32_C(1) << 30) + (UINT32_C(1) << 29)) 26 27 28 /// A table of these is used by the LZ-based encoder to hold 29 /// the length-distance pairs found by the match finder. 30 typedef struct { 31 uint32_t len; 32 uint32_t dist; 33 } lzma_match; 34 35 36 typedef struct lzma_mf_s lzma_mf; 37 struct lzma_mf_s { 38 /////////////// 39 // In Window // 40 /////////////// 41 42 /// Pointer to buffer with data to be compressed 43 uint8_t *buffer; 44 45 /// Total size of the allocated buffer (that is, including all 46 /// the extra space) 47 uint32_t size; 48 49 /// Number of bytes that must be kept available in our input history. 50 /// That is, once keep_size_before bytes have been processed, 51 /// buffer[read_pos - keep_size_before] is the oldest byte that 52 /// must be available for reading. 53 uint32_t keep_size_before; 54 55 /// Number of bytes that must be kept in buffer after read_pos. 56 /// That is, read_pos <= write_pos - keep_size_after as long as 57 /// action is LZMA_RUN; when action != LZMA_RUN, read_pos is allowed 58 /// to reach write_pos so that the last bytes get encoded too. 59 uint32_t keep_size_after; 60 61 /// Match finders store locations of matches using 32-bit integers. 62 /// To avoid adjusting several megabytes of integers every time the 63 /// input window is moved with move_window, we only adjust the 64 /// offset of the buffer. Thus, buffer[value_in_hash_table - offset] 65 /// is the byte pointed by value_in_hash_table. 66 uint32_t offset; 67 68 /// buffer[read_pos] is the next byte to run through the match 69 /// finder. This is incremented in the match finder once the byte 70 /// has been processed. 71 uint32_t read_pos; 72 73 /// Number of bytes that have been ran through the match finder, but 74 /// which haven't been encoded by the LZ-based encoder yet. 75 uint32_t read_ahead; 76 77 /// As long as read_pos is less than read_limit, there is enough 78 /// input available in buffer for at least one encoding loop. 79 /// 80 /// Because of the stateful API, read_limit may and will get greater 81 /// than read_pos quite often. This is taken into account when 82 /// calculating the value for keep_size_after. 83 uint32_t read_limit; 84 85 /// buffer[write_pos] is the first byte that doesn't contain valid 86 /// uncompressed data; that is, the next input byte will be copied 87 /// to buffer[write_pos]. 88 uint32_t write_pos; 89 90 /// Number of bytes not hashed before read_pos. This is needed to 91 /// restart the match finder after LZMA_SYNC_FLUSH. 92 uint32_t pending; 93 94 ////////////////// 95 // Match Finder // 96 ////////////////// 97 98 /// Find matches. Returns the number of distance-length pairs written 99 /// to the matches array. This is called only via lzma_mf_find(). 100 uint32_t (*find)(lzma_mf *mf, lzma_match *matches); 101 102 /// Skips num bytes. This is like find() but doesn't make the 103 /// distance-length pairs available, thus being a little faster. 104 /// This is called only via mf_skip(). 105 void (*skip)(lzma_mf *mf, uint32_t num); 106 107 uint32_t *hash; 108 uint32_t *son; 109 uint32_t cyclic_pos; 110 uint32_t cyclic_size; // Must be dictionary size + 1. 111 uint32_t hash_mask; 112 113 /// Maximum number of loops in the match finder 114 uint32_t depth; 115 116 /// Maximum length of a match that the match finder will try to find. 117 uint32_t nice_len; 118 119 /// Maximum length of a match supported by the LZ-based encoder. 120 /// If the longest match found by the match finder is nice_len, 121 /// mf_find() tries to expand it up to match_len_max bytes. 122 uint32_t match_len_max; 123 124 /// When running out of input, binary tree match finders need to know 125 /// if it is due to flushing or finishing. The action is used also 126 /// by the LZ-based encoders themselves. 127 lzma_action action; 128 129 /// Number of elements in hash[] 130 uint32_t hash_count; 131 132 /// Number of elements in son[] 133 uint32_t sons_count; 134 }; 135 136 137 typedef struct { 138 /// Extra amount of data to keep available before the "actual" 139 /// dictionary. 140 size_t before_size; 141 142 /// Size of the history buffer 143 size_t dict_size; 144 145 /// Extra amount of data to keep available after the "actual" 146 /// dictionary. 147 size_t after_size; 148 149 /// Maximum length of a match that the LZ-based encoder can accept. 150 /// This is used to extend matches of length nice_len to the 151 /// maximum possible length. 152 size_t match_len_max; 153 154 /// Match finder will search matches up to this length. 155 /// This must be less than or equal to match_len_max. 156 size_t nice_len; 157 158 /// Type of the match finder to use 159 lzma_match_finder match_finder; 160 161 /// Maximum search depth 162 uint32_t depth; 163 164 /// TODO: Comment 165 const uint8_t *preset_dict; 166 167 uint32_t preset_dict_size; 168 169 } lzma_lz_options; 170 171 172 // The total usable buffer space at any moment outside the match finder: 173 // before_size + dict_size + after_size + match_len_max 174 // 175 // In reality, there's some extra space allocated to prevent the number of 176 // memmove() calls reasonable. The bigger the dict_size is, the bigger 177 // this extra buffer will be since with bigger dictionaries memmove() would 178 // also take longer. 179 // 180 // A single encoder loop in the LZ-based encoder may call the match finder 181 // (mf_find() or mf_skip()) at most after_size times. In other words, 182 // a single encoder loop may increment lzma_mf.read_pos at most after_size 183 // times. Since matches are looked up to 184 // lzma_mf.buffer[lzma_mf.read_pos + match_len_max - 1], the total 185 // amount of extra buffer needed after dict_size becomes 186 // after_size + match_len_max. 187 // 188 // before_size has two uses. The first one is to keep literals available 189 // in cases when the LZ-based encoder has made some read ahead. 190 // TODO: Maybe this could be changed by making the LZ-based encoders to 191 // store the actual literals as they do with length-distance pairs. 192 // 193 // Algorithms such as LZMA2 first try to compress a chunk, and then check 194 // if the encoded result is smaller than the uncompressed one. If the chunk 195 // was incompressible, it is better to store it in uncompressed form in 196 // the output stream. To do this, the whole uncompressed chunk has to be 197 // still available in the history buffer. before_size achieves that. 198 199 200 typedef struct { 201 /// Data specific to the LZ-based encoder 202 void *coder; 203 204 /// Function to encode from *dict to out[] 205 lzma_ret (*code)(void *coder, 206 lzma_mf *restrict mf, uint8_t *restrict out, 207 size_t *restrict out_pos, size_t out_size); 208 209 /// Free allocated resources 210 void (*end)(void *coder, const lzma_allocator *allocator); 211 212 /// Update the options in the middle of the encoding. 213 lzma_ret (*options_update)(void *coder, const lzma_filter *filter); 214 215 /// Set maximum allowed output size 216 lzma_ret (*set_out_limit)(void *coder, uint64_t *uncomp_size, 217 uint64_t out_limit); 218 219 } lzma_lz_encoder; 220 221 222 // Basic steps: 223 // 1. Input gets copied into the dictionary. 224 // 2. Data in dictionary gets run through the match finder byte by byte. 225 // 3. The literals and matches are encoded using e.g. LZMA. 226 // 227 // The bytes that have been ran through the match finder, but not encoded yet, 228 // are called `read ahead'. 229 230 231 /// Get how many bytes the match finder hashes in its initial step. 232 /// This is also the minimum nice_len value with the match finder. 233 static inline uint32_t 234 mf_get_hash_bytes(lzma_match_finder match_finder) 235 { 236 return (uint32_t)match_finder & 0x0F; 237 } 238 239 240 /// Get pointer to the first byte not ran through the match finder 241 static inline const uint8_t * 242 mf_ptr(const lzma_mf *mf) 243 { 244 return mf->buffer + mf->read_pos; 245 } 246 247 248 /// Get the number of bytes that haven't been ran through the match finder yet. 249 static inline uint32_t 250 mf_avail(const lzma_mf *mf) 251 { 252 return mf->write_pos - mf->read_pos; 253 } 254 255 256 /// Get the number of bytes that haven't been encoded yet (some of these 257 /// bytes may have been ran through the match finder though). 258 static inline uint32_t 259 mf_unencoded(const lzma_mf *mf) 260 { 261 return mf->write_pos - mf->read_pos + mf->read_ahead; 262 } 263 264 265 /// Calculate the absolute offset from the beginning of the most recent 266 /// dictionary reset. Only the lowest four bits are important, so there's no 267 /// problem that we don't know the 64-bit size of the data encoded so far. 268 /// 269 /// NOTE: When moving the input window, we need to do it so that the lowest 270 /// bits of dict->read_pos are not modified to keep this macro working 271 /// as intended. 272 static inline uint32_t 273 mf_position(const lzma_mf *mf) 274 { 275 return mf->read_pos - mf->read_ahead; 276 } 277 278 279 /// Since everything else begins with mf_, use it also for lzma_mf_find(). 280 #define mf_find lzma_mf_find 281 282 283 /// Skip the given number of bytes. This is used when a good match was found. 284 /// For example, if mf_find() finds a match of 200 bytes long, the first byte 285 /// of that match was already consumed by mf_find(), and the rest 199 bytes 286 /// have to be skipped with mf_skip(mf, 199). 287 static inline void 288 mf_skip(lzma_mf *mf, uint32_t amount) 289 { 290 if (amount != 0) { 291 mf->skip(mf, amount); 292 mf->read_ahead += amount; 293 } 294 } 295 296 297 /// Copies at most *left number of bytes from the history buffer 298 /// to out[]. This is needed by LZMA2 to encode uncompressed chunks. 299 static inline void 300 mf_read(lzma_mf *mf, uint8_t *out, size_t *out_pos, size_t out_size, 301 size_t *left) 302 { 303 const size_t out_avail = out_size - *out_pos; 304 const size_t copy_size = my_min(out_avail, *left); 305 306 assert(mf->read_ahead == 0); 307 assert(mf->read_pos >= *left); 308 309 memcpy(out + *out_pos, mf->buffer + mf->read_pos - *left, 310 copy_size); 311 312 *out_pos += copy_size; 313 *left -= copy_size; 314 return; 315 } 316 317 318 extern lzma_ret lzma_lz_encoder_init( 319 lzma_next_coder *next, const lzma_allocator *allocator, 320 const lzma_filter_info *filters, 321 lzma_ret (*lz_init)(lzma_lz_encoder *lz, 322 const lzma_allocator *allocator, 323 lzma_vli id, const void *options, 324 lzma_lz_options *lz_options)); 325 326 327 extern uint64_t lzma_lz_encoder_memusage(const lzma_lz_options *lz_options); 328 329 330 // These are only for LZ encoder's internal use. 331 extern uint32_t lzma_mf_find( 332 lzma_mf *mf, uint32_t *count, lzma_match *matches); 333 334 extern uint32_t lzma_mf_hc3_find(lzma_mf *dict, lzma_match *matches); 335 extern void lzma_mf_hc3_skip(lzma_mf *dict, uint32_t amount); 336 337 extern uint32_t lzma_mf_hc4_find(lzma_mf *dict, lzma_match *matches); 338 extern void lzma_mf_hc4_skip(lzma_mf *dict, uint32_t amount); 339 340 extern uint32_t lzma_mf_bt2_find(lzma_mf *dict, lzma_match *matches); 341 extern void lzma_mf_bt2_skip(lzma_mf *dict, uint32_t amount); 342 343 extern uint32_t lzma_mf_bt3_find(lzma_mf *dict, lzma_match *matches); 344 extern void lzma_mf_bt3_skip(lzma_mf *dict, uint32_t amount); 345 346 extern uint32_t lzma_mf_bt4_find(lzma_mf *dict, lzma_match *matches); 347 extern void lzma_mf_bt4_skip(lzma_mf *dict, uint32_t amount); 348 349 #endif 350