diff options
Diffstat (limited to '')
| -rw-r--r-- | src/liblzma/lz/lz_encoder.h | 334 |
1 files changed, 254 insertions, 80 deletions
diff --git a/src/liblzma/lz/lz_encoder.h b/src/liblzma/lz/lz_encoder.h index da0e0804..45bb8462 100644 --- a/src/liblzma/lz/lz_encoder.h +++ b/src/liblzma/lz/lz_encoder.h @@ -3,8 +3,8 @@ /// \file lz_encoder.h /// \brief LZ in window and match finder API // -// Copyright (C) 1999-2006 Igor Pavlov -// Copyright (C) 2007 Lasse Collin +// Copyright (C) 1999-2008 Igor Pavlov +// Copyright (C) 2008 Lasse Collin // // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public @@ -24,19 +24,16 @@ #include "common.h" -typedef struct lzma_lz_encoder_s lzma_lz_encoder; -struct lzma_lz_encoder_s { - enum { - SEQ_RUN, - SEQ_FLUSH, - SEQ_FINISH, - } sequence; +/// A table of these is used by the LZ-based encoder to hold +/// the length-distance pairs found by the match finder. +typedef struct { + uint32_t len; + uint32_t dist; +} lzma_match; - /// Function to do the actual encoding from the sliding input window - /// to the output stream. - bool (*process)(lzma_coder *coder, uint8_t *restrict out, - size_t *restrict out_pos, size_t out_size); +typedef struct lzma_mf_s lzma_mf; +struct lzma_mf_s { /////////////// // In Window // /////////////// @@ -46,17 +43,33 @@ struct lzma_lz_encoder_s { /// Total size of the allocated buffer (that is, including all /// the extra space) - size_t size; + uint32_t size; + + /// Number of bytes that must be kept available in our input history. + /// That is, once keep_size_before bytes have been processed, + /// buffer[read_pos - keep_size_before] is the oldest byte that + /// must be available for reading. + uint32_t keep_size_before; + + /// Number of bytes that must be kept in buffer after read_pos. + /// That is, read_pos <= write_pos - keep_size_after as long as + /// stream_end_was_reached is false (once it is true, read_pos + /// is allowed to reach write_pos). + uint32_t keep_size_after; /// Match finders store locations of matches using 32-bit integers. /// To avoid adjusting several megabytes of integers every time the /// input window is moved with move_window(), we only adjust the /// offset of the buffer. Thus, buffer[match_finder_pos - offset] /// is the byte pointed by match_finder_pos. - size_t offset; + uint32_t offset; /// buffer[read_pos] is the current byte. - size_t read_pos; + uint32_t read_pos; + + /// Number of bytes that have been ran through the match finder, but + /// which haven't been encoded by the LZ-based encoder yet. + uint32_t read_ahead; /// As long as read_pos is less than read_limit, there is enough /// input available in buffer for at least one encoding loop. @@ -64,92 +77,253 @@ struct lzma_lz_encoder_s { /// Because of the stateful API, read_limit may and will get greater /// than read_pos quite often. This is taken into account when /// calculating the value for keep_size_after. - size_t read_limit; + uint32_t read_limit; /// buffer[write_pos] is the first byte that doesn't contain valid /// uncompressed data; that is, the next input byte will be copied /// to buffer[write_pos]. - size_t write_pos; + uint32_t write_pos; /// Number of bytes not hashed before read_pos. This is needed to /// restart the match finder after LZMA_SYNC_FLUSH. - size_t pending; - - /// Number of bytes that must be kept available in our input history. - /// That is, once keep_size_before bytes have been processed, - /// buffer[read_pos - keep_size_before] is the oldest byte that - /// must be available for reading. - size_t keep_size_before; - - /// Number of bytes that must be kept in buffer after read_pos. - /// That is, read_pos <= write_pos - keep_size_after as long as - /// stream_end_was_reached is false (once it is true, read_pos - /// is allowed to reach write_pos). - size_t keep_size_after; + uint32_t pending; ////////////////// // Match Finder // ////////////////// - // Pointers to match finder functions - void (*get_matches)(lzma_lz_encoder *restrict lz, - uint32_t *restrict distances); - void (*skip)(lzma_lz_encoder *restrict lz, uint32_t num); + /// Find matches. Returns the number of distance-length pairs written + /// to the matches array. This is called only via lzma_mf_find. + uint32_t (*find)(lzma_mf *mf, lzma_match *matches); + + /// Skips num bytes. This is like find() but doesn't make the + /// distance-length pairs available, thus being a little faster. + /// This is called only via mf_skip function. + void (*skip)(lzma_mf *mf, uint32_t num); - // Match finder data - uint32_t *hash; // TODO: Check if hash aliases son - uint32_t *son; // and add 'restrict' if possible. + uint32_t *hash; + uint32_t *son; uint32_t cyclic_buffer_pos; uint32_t cyclic_buffer_size; // Must be dictionary_size + 1. uint32_t hash_mask; - uint32_t cut_value; + + /// Maximum number of loops in the match finder + uint32_t loops; + + /// Maximum length of a match that the match finder will try to find. + uint32_t find_len_max; + + /// Maximum length of a match supported by the LZ-based encoder. + /// If the longest match found by the match finder is find_len_max, + /// lz_dict_find() tries to expand it up to match_len_max bytes. + uint32_t match_len_max; + + /// When running out of input, binary tree match finders need to know + /// if it is due to flushing or finishing. The action is used also + /// by the LZ-based encoders themselves. + lzma_action action; + + /// Number of elements in hash[] uint32_t hash_size_sum; - uint32_t num_items; - uint32_t match_max_len; + + /// Number of elements in son[] + uint32_t sons_count; }; -#define LZMA_LZ_ENCODER_INIT \ - (lzma_lz_encoder){ \ - .buffer = NULL, \ - .size = 0, \ - .hash = NULL, \ - .num_items = 0, \ +typedef struct { + /// Extra amount of data to keep available before the "actual" + /// dictionary. + size_t before_size; + + /// Size of the history buffer + size_t dictionary_size; + + /// Extra amount of data to keep available after the "actual" + /// dictionary. + size_t after_size; + + /// Maximum length of a match that the LZ-based encoder can accept. + /// This is used to extend matches of length find_len_max to the + /// maximum possible length. + size_t match_len_max; + + /// Match finder will search matches of at maximum of this length. + /// This must be less than or equal to match_len_max. + size_t find_len_max; + + /// Type of the match finder to use + lzma_match_finder match_finder; + + /// TODO: Comment + uint32_t match_finder_cycles; + + /// TODO: Comment + const uint8_t *preset_dictionary; + + uint32_t preset_dictionary_size; + +} lzma_lz_options; + + +// The total usable buffer space at any moment outside the match finder: +// before_size + dictionary_size + after_size + match_len_max +// +// In reality, there's some extra space allocated to prevent the number of +// memmove() calls reasonable. The bigger the dictionary_size is, the bigger +// this extra buffer will be since with bigger dictionaries memmove() would +// also take longer. +// +// A single encoder loop in the LZ-based encoder may call the match finder +// (lz_dict_find() or lz_dict_skip()) at maximum of after_size times. +// In other words, a single encoder loop may advance lz_dict.read_pos at +// maximum of after_size times. Since matches are looked up to +// lz_dict.buffer[lz_dict.read_pos + match_len_max - 1], the total +// amount of extra buffer needed after dictionary_size becomes +// after_size + match_len_max. +// +// before_size has two uses. The first one is to keep literals available +// in cases when the LZ-based encoder has made some read ahead. +// TODO: Maybe this could be changed by making the LZ-based encoders to +// store the actual literals as they do with length-distance pairs. +// +// Alrogithms such as LZMA2 first try to compress a chunk, and then check +// if the encoded result is smaller than the uncompressed one. If the chunk +// was uncompressible, it is better to store it in uncompressed form in +// the output stream. To do this, the whole uncompressed chunk has to be +// still available in the history buffer. before_size achieves that. + + +typedef struct { + /// Data specific to the LZ-based encoder + lzma_coder *coder; + + /// Function to encode from *dict to out[] + lzma_ret (*code)(lzma_coder *restrict coder, + lzma_mf *restrict mf, uint8_t *restrict out, + size_t *restrict out_pos, size_t out_size); + + /// Free allocated resources + void (*end)(lzma_coder *coder, lzma_allocator *allocator); + +} lzma_lz_encoder; + + +// Basic steps: +// 1. Input gets copied into the dictionary. +// 2. Data in dictionary gets run through the match finder byte by byte. +// 3. The literals and matches are encoded using e.g. LZMA. +// +// The bytes that have been ran through the match finder, but not encoded yet, +// are called `read ahead'. + + +/// Get pointer to the first byte not ran through the match finder +static inline const uint8_t * +mf_ptr(const lzma_mf *mf) +{ + return mf->buffer + mf->read_pos; +} + + +/// Get the number of bytes that haven't been ran through the match finder yet. +static inline uint32_t +mf_avail(const lzma_mf *mf) +{ + return mf->write_pos - mf->read_pos; +} + + +/// Get the number of bytes that haven't been encoded yet (some of these +/// bytes may have been ran through the match finder though). +static inline uint32_t +mf_unencoded(const lzma_mf *mf) +{ + return mf->write_pos - mf->read_pos - mf->read_ahead; +} + + +/// Calculate the absolute offset from the beginning of the most recent +/// dictionary reset. Only the lowest four bits are important, so there's no +/// problem that we don't know the 64-bit size of the data encoded so far. +/// +/// NOTE: When moving the input window, we need to do it so that the lowest +/// bits of dict->read_pos are not modified to keep this macro working +/// as intended. +static inline uint32_t +mf_position(const lzma_mf *mf) +{ + return mf->read_pos - mf->read_ahead; +} + + +/// Since everything else begins with mf_, use it also for lzma_mf_find(). +#define mf_find lzma_mf_find + + +/// Skip the given number of bytes. This is used when a good match was found. +/// For example, if mf_find() finds a match of 200 bytes long, the first byte +/// of that match was already consumed by mf_find(), and the rest 199 bytes +/// have to be skipped with mf_skip(mf, 199). +static inline void +mf_skip(lzma_mf *mf, uint32_t amount) +{ + if (amount != 0) { + mf->skip(mf, amount); + mf->read_ahead += amount; } +} + + +/// Copies at maximum of *left amount of bytes from the history buffer +/// to out[]. This is needed by LZMA2 to encode uncompressed chunks. +static inline void +mf_read(lzma_mf *mf, uint8_t *out, size_t *out_pos, size_t out_size, + size_t *left) +{ + const size_t out_avail = out_size - *out_pos; + const size_t copy_size = MIN(out_avail, *left); + + assert(mf->read_ahead == 0); + assert(mf->read_pos >= *left); + + memcpy(out + *out_pos, mf->buffer + mf->read_pos - *left, + copy_size); + + *out_pos += copy_size; + *left -= copy_size; + return; +} + + +extern lzma_ret lzma_lz_encoder_init( + lzma_next_coder *next, lzma_allocator *allocator, + const lzma_filter_info *filters, + lzma_ret (*lz_init)(lzma_lz_encoder *lz, + lzma_allocator *allocator, const void *options, + lzma_lz_options *lz_options)); + + +extern uint64_t lzma_lz_encoder_memusage(const lzma_lz_options *lz_options); + + +// These are only for LZ encoder's internal use. +extern uint32_t lzma_mf_find( + lzma_mf *mf, uint32_t *count, lzma_match *matches); + +extern uint32_t lzma_mf_hc3_find(lzma_mf *dict, lzma_match *matches); +extern void lzma_mf_hc3_skip(lzma_mf *dict, uint32_t amount); + +extern uint32_t lzma_mf_hc4_find(lzma_mf *dict, lzma_match *matches); +extern void lzma_mf_hc4_skip(lzma_mf *dict, uint32_t amount); + +extern uint32_t lzma_mf_bt2_find(lzma_mf *dict, lzma_match *matches); +extern void lzma_mf_bt2_skip(lzma_mf *dict, uint32_t amount); +extern uint32_t lzma_mf_bt3_find(lzma_mf *dict, lzma_match *matches); +extern void lzma_mf_bt3_skip(lzma_mf *dict, uint32_t amount); -/// Calculates -extern bool lzma_lz_encoder_hash_properties(lzma_match_finder match_finder, - uint32_t history_size, uint32_t *restrict hash_mask, - uint32_t *restrict hash_size_sum, - uint32_t *restrict num_items); - -// NOTE: liblzma doesn't use callback API like LZMA SDK does. The caller -// must make sure that keep_size_after is big enough for single encoding pass -// i.e. keep_size_after >= maximum number of bytes possibly needed after -// the current position between calls to lzma_lz_read(). -extern lzma_ret lzma_lz_encoder_reset(lzma_lz_encoder *lz, - lzma_allocator *allocator, - bool (*process)(lzma_coder *coder, uint8_t *restrict out, - size_t *restrict out_pos, size_t out_size), - size_t history_size, size_t additional_buffer_before, - size_t match_max_len, size_t additional_buffer_after, - lzma_match_finder match_finder, uint32_t match_finder_cycles, - const uint8_t *preset_dictionary, - size_t preset_dictionary_size); - -/// Frees memory allocated for in window and match finder buffers. -extern void lzma_lz_encoder_end( - lzma_lz_encoder *lz, lzma_allocator *allocator); - -extern lzma_ret lzma_lz_encode(lzma_coder *coder, - lzma_allocator *allocator lzma_attribute((unused)), - const uint8_t *restrict in, size_t *restrict in_pos, - size_t in_size, uint8_t *restrict out, - size_t *restrict out_pos, size_t out_size, - lzma_action action); - -/// This should not be called directly, but only via move_pos() macro. -extern void lzma_lz_encoder_normalize(lzma_lz_encoder *lz); +extern uint32_t lzma_mf_bt4_find(lzma_mf *dict, lzma_match *matches); +extern void lzma_mf_bt4_skip(lzma_mf *dict, uint32_t amount); #endif |