aboutsummaryrefslogtreecommitdiff
path: root/src/liblzma/lz/lz_encoder.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/liblzma/lz/lz_encoder.h334
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