lz_encoder.h

Go to the documentation of this file.

// SPDX-License-Identifier: 0BSD
 
//
//  Authors:    Igor Pavlov
//              Lasse Collin
//
 
#ifndef LZMA_LZ_ENCODER_H
#define LZMA_LZ_ENCODER_H
 
#include "common.h"
 
 
// For now, the dictionary size is limited to 1.5 GiB. This may grow
// in the future if needed, but it needs a little more work than just
// changing this check.
#define IS_ENC_DICT_SIZE_VALID(size) \
    ((size) >= LZMA_DICT_SIZE_MIN \
        && (size) <= (UINT32_C(1) << 30) + (UINT32_C(1) << 29))
 
 
typedef struct {
    uint32_t len;
    uint32_t dist;
} lzma_match;
 
 
typedef struct lzma_mf_s lzma_mf;
struct lzma_mf_s {
    // In Window //
 
    uint8_t *buffer;
 
    uint32_t size;
 
    uint32_t keep_size_before;
 
    uint32_t keep_size_after;
 
    uint32_t offset;
 
    uint32_t read_pos;
 
    uint32_t read_ahead;
 
    uint32_t read_limit;
 
    uint32_t write_pos;
 
    uint32_t pending;
 
    // Match Finder //
 
    uint32_t (*find)(lzma_mf *mf, lzma_match *matches);
 
    void (*skip)(lzma_mf *mf, uint32_t num);
 
    uint32_t *hash;
    uint32_t *son;
    uint32_t cyclic_pos;
    uint32_t cyclic_size; // Must be dictionary size + 1.
    uint32_t hash_mask;
 
    uint32_t depth;
 
    uint32_t nice_len;
 
    uint32_t match_len_max;
 
    lzma_action action;
 
    uint32_t hash_count;
 
    uint32_t sons_count;
};
 
 
typedef struct {
    size_t before_size;
 
    size_t dict_size;
 
    size_t after_size;
 
    size_t match_len_max;
 
    size_t nice_len;
 
    lzma_match_finder match_finder;
 
    uint32_t depth;
 
    const uint8_t *preset_dict;
 
    uint32_t preset_dict_size;
 
} lzma_lz_options;
 
 
// The total usable buffer space at any moment outside the match finder:
// before_size + dict_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 dict_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
// (mf_find() or mf_skip()) at most after_size times. In other words,
// a single encoder loop may increment lzma_mf.read_pos at most after_size
// times. Since matches are looked up to
// lzma_mf.buffer[lzma_mf.read_pos + match_len_max - 1], the total
// amount of extra buffer needed after dict_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.
//
// Algorithms 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 incompressible, 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 {
    void *coder;
 
    lzma_ret (*code)(void *coder,
            lzma_mf *restrict mf, uint8_t *restrict out,
            size_t *restrict out_pos, size_t out_size);
 
    void (*end)(void *coder, const lzma_allocator *allocator);
 
    lzma_ret (*options_update)(void *coder, const lzma_filter *filter);
 
    lzma_ret (*set_out_limit)(void *coder, uint64_t *uncomp_size,
            uint64_t out_limit);
 
} 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'.
 
 
static inline uint32_t
mf_get_hash_bytes(lzma_match_finder match_finder)
{
    return (uint32_t)match_finder & 0x0F;
}
 
 
static inline const uint8_t *
mf_ptr(const lzma_mf *mf)
{
    return mf->buffer + mf->read_pos;
}
 
 
static inline uint32_t
mf_avail(const lzma_mf *mf)
{
    return mf->write_pos - mf->read_pos;
}
 
 
static inline uint32_t
mf_unencoded(const lzma_mf *mf)
{
    return mf->write_pos - mf->read_pos + mf->read_ahead;
}
 
 
static inline uint32_t
mf_position(const lzma_mf *mf)
{
    return mf->read_pos - mf->read_ahead;
}
 
 
#define mf_find lzma_mf_find
 
 
static inline void
mf_skip(lzma_mf *mf, uint32_t amount)
{
    if (amount != 0) {
        mf->skip(mf, amount);
        mf->read_ahead += amount;
    }
}
 
 
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 = my_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, const lzma_allocator *allocator,
        const lzma_filter_info *filters,
        lzma_ret (*lz_init)(lzma_lz_encoder *lz,
            const lzma_allocator *allocator,
            lzma_vli id, 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);
 
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