1207753Smm/////////////////////////////////////////////////////////////////////////////// 2207753Smm// 3207753Smm/// \file lz_encoder.h 4207753Smm/// \brief LZ in window and match finder API 5207753Smm/// 6207753Smm// Authors: Igor Pavlov 7207753Smm// Lasse Collin 8207753Smm// 9207753Smm// This file has been put into the public domain. 10207753Smm// You can do whatever you want with this file. 11207753Smm// 12207753Smm/////////////////////////////////////////////////////////////////////////////// 13207753Smm 14207753Smm#ifndef LZMA_LZ_ENCODER_H 15207753Smm#define LZMA_LZ_ENCODER_H 16207753Smm 17207753Smm#include "common.h" 18207753Smm 19207753Smm 20207753Smm/// A table of these is used by the LZ-based encoder to hold 21207753Smm/// the length-distance pairs found by the match finder. 22207753Smmtypedef struct { 23207753Smm uint32_t len; 24207753Smm uint32_t dist; 25207753Smm} lzma_match; 26207753Smm 27207753Smm 28207753Smmtypedef struct lzma_mf_s lzma_mf; 29207753Smmstruct lzma_mf_s { 30207753Smm /////////////// 31207753Smm // In Window // 32207753Smm /////////////// 33207753Smm 34207753Smm /// Pointer to buffer with data to be compressed 35207753Smm uint8_t *buffer; 36207753Smm 37207753Smm /// Total size of the allocated buffer (that is, including all 38207753Smm /// the extra space) 39207753Smm uint32_t size; 40207753Smm 41207753Smm /// Number of bytes that must be kept available in our input history. 42207753Smm /// That is, once keep_size_before bytes have been processed, 43207753Smm /// buffer[read_pos - keep_size_before] is the oldest byte that 44207753Smm /// must be available for reading. 45207753Smm uint32_t keep_size_before; 46207753Smm 47207753Smm /// Number of bytes that must be kept in buffer after read_pos. 48207753Smm /// That is, read_pos <= write_pos - keep_size_after as long as 49207753Smm /// action is LZMA_RUN; when action != LZMA_RUN, read_pos is allowed 50207753Smm /// to reach write_pos so that the last bytes get encoded too. 51207753Smm uint32_t keep_size_after; 52207753Smm 53207753Smm /// Match finders store locations of matches using 32-bit integers. 54207753Smm /// To avoid adjusting several megabytes of integers every time the 55207753Smm /// input window is moved with move_window, we only adjust the 56207753Smm /// offset of the buffer. Thus, buffer[value_in_hash_table - offset] 57207753Smm /// is the byte pointed by value_in_hash_table. 58207753Smm uint32_t offset; 59207753Smm 60207753Smm /// buffer[read_pos] is the next byte to run through the match 61207753Smm /// finder. This is incremented in the match finder once the byte 62207753Smm /// has been processed. 63207753Smm uint32_t read_pos; 64207753Smm 65207753Smm /// Number of bytes that have been ran through the match finder, but 66207753Smm /// which haven't been encoded by the LZ-based encoder yet. 67207753Smm uint32_t read_ahead; 68207753Smm 69207753Smm /// As long as read_pos is less than read_limit, there is enough 70207753Smm /// input available in buffer for at least one encoding loop. 71207753Smm /// 72207753Smm /// Because of the stateful API, read_limit may and will get greater 73207753Smm /// than read_pos quite often. This is taken into account when 74207753Smm /// calculating the value for keep_size_after. 75207753Smm uint32_t read_limit; 76207753Smm 77207753Smm /// buffer[write_pos] is the first byte that doesn't contain valid 78207753Smm /// uncompressed data; that is, the next input byte will be copied 79207753Smm /// to buffer[write_pos]. 80207753Smm uint32_t write_pos; 81207753Smm 82207753Smm /// Number of bytes not hashed before read_pos. This is needed to 83207753Smm /// restart the match finder after LZMA_SYNC_FLUSH. 84207753Smm uint32_t pending; 85207753Smm 86207753Smm ////////////////// 87207753Smm // Match Finder // 88207753Smm ////////////////// 89207753Smm 90207753Smm /// Find matches. Returns the number of distance-length pairs written 91207753Smm /// to the matches array. This is called only via lzma_mf_find(). 92207753Smm uint32_t (*find)(lzma_mf *mf, lzma_match *matches); 93207753Smm 94207753Smm /// Skips num bytes. This is like find() but doesn't make the 95207753Smm /// distance-length pairs available, thus being a little faster. 96207753Smm /// This is called only via mf_skip(). 97207753Smm void (*skip)(lzma_mf *mf, uint32_t num); 98207753Smm 99207753Smm uint32_t *hash; 100207753Smm uint32_t *son; 101207753Smm uint32_t cyclic_pos; 102207753Smm uint32_t cyclic_size; // Must be dictionary size + 1. 103207753Smm uint32_t hash_mask; 104207753Smm 105207753Smm /// Maximum number of loops in the match finder 106207753Smm uint32_t depth; 107207753Smm 108207753Smm /// Maximum length of a match that the match finder will try to find. 109207753Smm uint32_t nice_len; 110207753Smm 111207753Smm /// Maximum length of a match supported by the LZ-based encoder. 112207753Smm /// If the longest match found by the match finder is nice_len, 113207753Smm /// mf_find() tries to expand it up to match_len_max bytes. 114207753Smm uint32_t match_len_max; 115207753Smm 116207753Smm /// When running out of input, binary tree match finders need to know 117207753Smm /// if it is due to flushing or finishing. The action is used also 118207753Smm /// by the LZ-based encoders themselves. 119207753Smm lzma_action action; 120207753Smm 121207753Smm /// Number of elements in hash[] 122292588Sdelphij uint32_t hash_count; 123207753Smm 124207753Smm /// Number of elements in son[] 125207753Smm uint32_t sons_count; 126207753Smm}; 127207753Smm 128207753Smm 129207753Smmtypedef struct { 130207753Smm /// Extra amount of data to keep available before the "actual" 131207753Smm /// dictionary. 132207753Smm size_t before_size; 133207753Smm 134207753Smm /// Size of the history buffer 135207753Smm size_t dict_size; 136207753Smm 137207753Smm /// Extra amount of data to keep available after the "actual" 138207753Smm /// dictionary. 139207753Smm size_t after_size; 140207753Smm 141207753Smm /// Maximum length of a match that the LZ-based encoder can accept. 142207753Smm /// This is used to extend matches of length nice_len to the 143207753Smm /// maximum possible length. 144207753Smm size_t match_len_max; 145207753Smm 146207753Smm /// Match finder will search matches up to this length. 147207753Smm /// This must be less than or equal to match_len_max. 148207753Smm size_t nice_len; 149207753Smm 150207753Smm /// Type of the match finder to use 151207753Smm lzma_match_finder match_finder; 152207753Smm 153207753Smm /// Maximum search depth 154207753Smm uint32_t depth; 155207753Smm 156207753Smm /// TODO: Comment 157207753Smm const uint8_t *preset_dict; 158207753Smm 159207753Smm uint32_t preset_dict_size; 160207753Smm 161207753Smm} lzma_lz_options; 162207753Smm 163207753Smm 164207753Smm// The total usable buffer space at any moment outside the match finder: 165207753Smm// before_size + dict_size + after_size + match_len_max 166207753Smm// 167207753Smm// In reality, there's some extra space allocated to prevent the number of 168207753Smm// memmove() calls reasonable. The bigger the dict_size is, the bigger 169207753Smm// this extra buffer will be since with bigger dictionaries memmove() would 170207753Smm// also take longer. 171207753Smm// 172207753Smm// A single encoder loop in the LZ-based encoder may call the match finder 173207753Smm// (mf_find() or mf_skip()) at most after_size times. In other words, 174207753Smm// a single encoder loop may increment lzma_mf.read_pos at most after_size 175207753Smm// times. Since matches are looked up to 176207753Smm// lzma_mf.buffer[lzma_mf.read_pos + match_len_max - 1], the total 177207753Smm// amount of extra buffer needed after dict_size becomes 178207753Smm// after_size + match_len_max. 179207753Smm// 180207753Smm// before_size has two uses. The first one is to keep literals available 181207753Smm// in cases when the LZ-based encoder has made some read ahead. 182207753Smm// TODO: Maybe this could be changed by making the LZ-based encoders to 183207753Smm// store the actual literals as they do with length-distance pairs. 184207753Smm// 185207753Smm// Algorithms such as LZMA2 first try to compress a chunk, and then check 186207753Smm// if the encoded result is smaller than the uncompressed one. If the chunk 187207753Smm// was uncompressible, it is better to store it in uncompressed form in 188207753Smm// the output stream. To do this, the whole uncompressed chunk has to be 189207753Smm// still available in the history buffer. before_size achieves that. 190207753Smm 191207753Smm 192207753Smmtypedef struct { 193207753Smm /// Data specific to the LZ-based encoder 194312518Sdelphij void *coder; 195207753Smm 196207753Smm /// Function to encode from *dict to out[] 197312518Sdelphij lzma_ret (*code)(void *coder, 198207753Smm lzma_mf *restrict mf, uint8_t *restrict out, 199207753Smm size_t *restrict out_pos, size_t out_size); 200207753Smm 201207753Smm /// Free allocated resources 202312518Sdelphij void (*end)(void *coder, const lzma_allocator *allocator); 203207753Smm 204207753Smm /// Update the options in the middle of the encoding. 205312518Sdelphij lzma_ret (*options_update)(void *coder, const lzma_filter *filter); 206207753Smm 207207753Smm} lzma_lz_encoder; 208207753Smm 209207753Smm 210207753Smm// Basic steps: 211207753Smm// 1. Input gets copied into the dictionary. 212207753Smm// 2. Data in dictionary gets run through the match finder byte by byte. 213207753Smm// 3. The literals and matches are encoded using e.g. LZMA. 214207753Smm// 215207753Smm// The bytes that have been ran through the match finder, but not encoded yet, 216207753Smm// are called `read ahead'. 217207753Smm 218207753Smm 219207753Smm/// Get pointer to the first byte not ran through the match finder 220207753Smmstatic inline const uint8_t * 221207753Smmmf_ptr(const lzma_mf *mf) 222207753Smm{ 223207753Smm return mf->buffer + mf->read_pos; 224207753Smm} 225207753Smm 226207753Smm 227207753Smm/// Get the number of bytes that haven't been ran through the match finder yet. 228207753Smmstatic inline uint32_t 229207753Smmmf_avail(const lzma_mf *mf) 230207753Smm{ 231207753Smm return mf->write_pos - mf->read_pos; 232207753Smm} 233207753Smm 234207753Smm 235207753Smm/// Get the number of bytes that haven't been encoded yet (some of these 236207753Smm/// bytes may have been ran through the match finder though). 237207753Smmstatic inline uint32_t 238207753Smmmf_unencoded(const lzma_mf *mf) 239207753Smm{ 240207753Smm return mf->write_pos - mf->read_pos + mf->read_ahead; 241207753Smm} 242207753Smm 243207753Smm 244207753Smm/// Calculate the absolute offset from the beginning of the most recent 245207753Smm/// dictionary reset. Only the lowest four bits are important, so there's no 246207753Smm/// problem that we don't know the 64-bit size of the data encoded so far. 247207753Smm/// 248207753Smm/// NOTE: When moving the input window, we need to do it so that the lowest 249207753Smm/// bits of dict->read_pos are not modified to keep this macro working 250207753Smm/// as intended. 251207753Smmstatic inline uint32_t 252207753Smmmf_position(const lzma_mf *mf) 253207753Smm{ 254207753Smm return mf->read_pos - mf->read_ahead; 255207753Smm} 256207753Smm 257207753Smm 258207753Smm/// Since everything else begins with mf_, use it also for lzma_mf_find(). 259207753Smm#define mf_find lzma_mf_find 260207753Smm 261207753Smm 262207753Smm/// Skip the given number of bytes. This is used when a good match was found. 263207753Smm/// For example, if mf_find() finds a match of 200 bytes long, the first byte 264207753Smm/// of that match was already consumed by mf_find(), and the rest 199 bytes 265207753Smm/// have to be skipped with mf_skip(mf, 199). 266207753Smmstatic inline void 267207753Smmmf_skip(lzma_mf *mf, uint32_t amount) 268207753Smm{ 269207753Smm if (amount != 0) { 270207753Smm mf->skip(mf, amount); 271207753Smm mf->read_ahead += amount; 272207753Smm } 273207753Smm} 274207753Smm 275207753Smm 276207753Smm/// Copies at most *left number of bytes from the history buffer 277207753Smm/// to out[]. This is needed by LZMA2 to encode uncompressed chunks. 278207753Smmstatic inline void 279207753Smmmf_read(lzma_mf *mf, uint8_t *out, size_t *out_pos, size_t out_size, 280207753Smm size_t *left) 281207753Smm{ 282207753Smm const size_t out_avail = out_size - *out_pos; 283213700Smm const size_t copy_size = my_min(out_avail, *left); 284207753Smm 285207753Smm assert(mf->read_ahead == 0); 286207753Smm assert(mf->read_pos >= *left); 287207753Smm 288207753Smm memcpy(out + *out_pos, mf->buffer + mf->read_pos - *left, 289207753Smm copy_size); 290207753Smm 291207753Smm *out_pos += copy_size; 292207753Smm *left -= copy_size; 293207753Smm return; 294207753Smm} 295207753Smm 296207753Smm 297207753Smmextern lzma_ret lzma_lz_encoder_init( 298292588Sdelphij lzma_next_coder *next, const lzma_allocator *allocator, 299207753Smm const lzma_filter_info *filters, 300207753Smm lzma_ret (*lz_init)(lzma_lz_encoder *lz, 301292588Sdelphij const lzma_allocator *allocator, const void *options, 302207753Smm lzma_lz_options *lz_options)); 303207753Smm 304207753Smm 305207753Smmextern uint64_t lzma_lz_encoder_memusage(const lzma_lz_options *lz_options); 306207753Smm 307207753Smm 308207753Smm// These are only for LZ encoder's internal use. 309207753Smmextern uint32_t lzma_mf_find( 310207753Smm lzma_mf *mf, uint32_t *count, lzma_match *matches); 311207753Smm 312207753Smmextern uint32_t lzma_mf_hc3_find(lzma_mf *dict, lzma_match *matches); 313207753Smmextern void lzma_mf_hc3_skip(lzma_mf *dict, uint32_t amount); 314207753Smm 315207753Smmextern uint32_t lzma_mf_hc4_find(lzma_mf *dict, lzma_match *matches); 316207753Smmextern void lzma_mf_hc4_skip(lzma_mf *dict, uint32_t amount); 317207753Smm 318207753Smmextern uint32_t lzma_mf_bt2_find(lzma_mf *dict, lzma_match *matches); 319207753Smmextern void lzma_mf_bt2_skip(lzma_mf *dict, uint32_t amount); 320207753Smm 321207753Smmextern uint32_t lzma_mf_bt3_find(lzma_mf *dict, lzma_match *matches); 322207753Smmextern void lzma_mf_bt3_skip(lzma_mf *dict, uint32_t amount); 323207753Smm 324207753Smmextern uint32_t lzma_mf_bt4_find(lzma_mf *dict, lzma_match *matches); 325207753Smmextern void lzma_mf_bt4_skip(lzma_mf *dict, uint32_t amount); 326207753Smm 327207753Smm#endif 328