[wimlib] / include / wimlib / lz_mf.h

/*
 * lz_mf.h
 *
 * Interface for Lempel-Ziv match-finders.
 *
 * Copyright (c) 2014 Eric Biggers.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/*
 * Example usage of the match-finder API:
 *
 * ----------------------------------------------------------------------------
 *
 * Fill in a 'struct lz_mf_params'.
 * (Optional) Call lz_mf_params_valid() to validate the parameters.
 * Call lz_mf_alloc() to allocate the match-finder.
 * For each block of data to be compressed:
 *      Call lz_mf_load_window() to load the block into the match finder.
 *      While the block is not yet fully compressed:
 *              Call lz_mf_get_matches() to get matches at the current position.
 *              If matches were found:
 *                      Output the longest match.
 *                      Call lz_mf_skip_positions() to skip the remaining length of the match.
 *              Else:
 *                      Output a literal.
 *              End If
 *      End While
 * End For
 * Call lz_mf_free() to free the match-finder.
 *
 * ----------------------------------------------------------------------------
 *
 * That example did "greedy parsing" --- that is, always choosing the longest
 * match at each position.  However, this interface can be (and is intended to
 * be) used for "optimal parsing" as well.  It can also be used for in-between
 * strategies such as "lazy parsing" and "flexible parsing".  For the best
 * performance try different match-finding algorithms and parameters to see what
 * works best for your parsing strategy, and your typical data and block sizes.
 */

#ifndef _WIMLIB_LZ_MF_H
#define _WIMLIB_LZ_MF_H

#include "wimlib/types.h"

/* When ENABLE_LZ_DEBUG is defined, we check all matches for correctness and
 * perform other validations.  Use for debugging only, as it slows things down
 * significantly.  */

//#define ENABLE_LZ_DEBUG
#ifdef ENABLE_LZ_DEBUG
#  include <assert.h>
#  include <string.h>
#  define LZ_ASSERT assert
#else
#  define LZ_ASSERT(...)
#endif

struct lz_mf;

/* Representation of a Lempel-Ziv match.  */
struct lz_match {

        /* The number of bytes matched.  */
        u32 len;

        /* The offset back from the current position that was matched.  */
        u32 offset;
};

/*
 * Specifies a match-finding algorithm.
 */
enum lz_mf_algo {

        /*
         * Use the default algorithm for the specified maximum window size.
         */
        LZ_MF_DEFAULT = 0,

        /*
         * "Null" algorithm that never reports any matches.
         *
         * This algorithm exists for comparison, benchmarking, and testing
         * purposes only.  It is not intended to be used in real compressors.
         */
        LZ_MF_NULL = 1,

        /*
         * Brute Force match-finding algorithm.
         *
         * This algorithm exists for comparison, benchmarking, and testing
         * purposes only.  It is not intended to be used in real compressors.
         */
        LZ_MF_BRUTE_FORCE = 2,

        /*
         * Hash Chain match-finding algorithm.
         *
         * This works well on small windows.
         *
         * The memory usage is 4 bytes per position, plus 131072 bytes for a
         * hash table.
         *
         * lz_mf_skip_positions() with this algorithm is very fast, so it's good
         * if you're doing "greedy" rather than "optimal" parsing.  However, if
         * using large windows you might be better off with binary trees or
         * suffix arrays, even if doing greedy parsing.
         */
        LZ_MF_HASH_CHAINS = 3,

        /*
         * Binary Tree match-finding algorithm.
         *
         * This works well on small to medium-sized windows.
         *
         * The memory usage is 8 bytes per position, plus 262144 bytes for a
         * hash table.
         *
         * lz_mf_skip_positions() with this algorithm takes a significant amount
         * of time, almost as much as a call to lz_mf_get_matches().  This makes
         * this algorithm better suited for optimal parsing than for greedy
         * parsing.  However, if the window size becomes sufficiently large,
         * this algorithm can outperform hash chains, even when using greedy
         * parsing.
         */
        LZ_MF_BINARY_TREES = 4,

        /*
         * Longest Common Prefix Interval Tree match-finding algorithm.
         *
         * This is a suffix array-based algorithm.  It works well on medium to
         * large windows.  However, due to an implementation detail, it is
         * currently limited to a maximum window size of 33554432 bytes.
         *
         * The memory usage is 12 bytes per position.
         *
         * Unlike the hash chain and binary tree algorithms, the LCP interval
         * tree algorithm performs most of its work in lz_mf_load_window().  The
         * calls to lz_mf_get_matches() and lz_mf_skip_positions() take
         * relatively little time, and lz_mf_skip_positions() is not much faster
         * than lz_mf_get_matches().  Therefore, if you're using this algorithm
         * you might as well be doing "optimal" rather than "greedy" parsing.
         */
        LZ_MF_LCP_INTERVAL_TREE = 5,

        /*
         * Linked Suffix Array match-finding algorithm.
         *
         * This can be used on very large windows.
         *
         * The memory usage is 14 bytes per position.
         *
         * Currently, this method usually performs slightly worse than the LCP
         * interval tree algorithm.  However, it can be used on windows
         * exceeding the 33554432 byte limit of the LCP interval tree algorithm.
         */
        LZ_MF_LINKED_SUFFIX_ARRAY = 6,
};

/* Parameters for Lempel-Ziv match-finding.  */
struct lz_mf_params {

        /*
         * The match-finding algorithm to use.  This must be one of the 'enum
         * lz_mf_algo' constants defined above.
         *
         * If this is LZ_MF_DEFAULT, the default algorithm for the specified
         * @max_window_size is used.
         */
        u32 algorithm;

        /*
         * The maximum window size, in bytes, that shall be supported by the
         * match-finder.  This is the maximum size that can be passed to
         * subsequent calls to lz_mf_load_window().
         *
         * Note: this interface is intended to be used for block compression, so
         * none of the match-finding algorithms support sliding windows.  It's
         * expected that the window for LZ match-finding simply be the block of
         * data being compressed.
         *
         * Match-finders generally require an amount of memory proportional to
         * this parameter.  Use lz_mf_get_needed_memory() to query the needed
         * memory size for a specific match-finding algorithm and maximum window
         * size.
         *
         * This parameter cannot be 0; there is no default value.
         *
         * Match-finding algorithms may place additional restrictions on this
         * parameter.  However, currently only the LCP interval tree
         * match-finding algorithm places such a restriction (it doesn't support
         * windows larger than 33554432 bytes).
         */
        u32 max_window_size;

        /*
         * The minimum length, in bytes, of matches that can be produced by the
         * match-finder (by a call to lz_mf_get_matches()).
         *
         * If this parameter is not 0, it must be 2 or greater.
         *
         * If this parameter is 0, the match-finding algorithm sets it to a
         * default value.  The default value will be at least 2 and at most 16.
         */
        u32 min_match_len;

        /*
         * The maximum length, in bytes, of matches that can be produced by the
         * match-finder (by a call to lz_mf_get_matches()).
         *
         * If this parameter is not 0, it must be greater than or equal to
         * @min_match_len, or the default value the match-finding algorithm
         * selected for @min_match_len in the case that @min_match_len was
         * specified as 0.
         *
         * If this parameter is 0, the match-finding algorithm sets it to a
         * default value.  In general, the caller must be prepared to handle
         * arbitrarily long matches (up to the window size minus 1) in this
         * case.
         */
        u32 max_match_len;

        /*
         * When using the hash chains or binary trees match-finding algorithm,
         * this parameter defines the maximum number of search steps at each
         * position.  A typical value to use is 32.  Higher values result in
         * better matches and slower performance.
         *
         * The suffix array-based match-finding algorithms treat this parameter
         * slightly differently because they find the longest matches first.
         * They still honor the intent of the parameter but may scale it down to
         * an appropriate value.
         *
         * If this parameter is 0, the match-finding algorithm sets it to a
         * default value.
         */
        u32 max_search_depth;

        /*
         * When using the hash chains, binary trees, or LCP interval tree
         * match-finding algorithm, this parameter defines the maximum match
         * length to which the full algorithm will be applied.  This can also be
         * thought of as the length above which the algorithm will not try to
         * search for additional matches.
         *
         * Usually, setting this parameter to a reasonable value (such as 24,
         * 32, or 48) will speed up match-finding but will not hurt the
         * compression ratio too much.  This is because these settings of this
         * parameter cause the match-finder to not waste too much time examining
         * very long matches, which are already highly compressible.
         *
         * In addition, if the longest match exceeds this length, the
         * match-finding algorithm will still report its full length.
         *
         * The linked suffix array match-finding algorithm ignores this
         * parameter.
         *
         * If this parameter is 0, the match-finding algorithm sets it to a
         * default value.
         */
        u32 nice_match_len;
};

/*
 * Lempel-Ziv match-finder operations structure.
 *
 * Match-finding algorithms must fill in all members.  None can be left as 0 or
 * NULL.
 *
 * Don't directly access any of the members outside of lz_mf.h and lz_mf.c.
 * Instead, use the lz_mf_*() wrappers.
 */
struct lz_mf_ops {
        bool (*params_valid)(const struct lz_mf_params *);

        u64 (*get_needed_memory)(u32 max_window_size);

        bool (*init)(struct lz_mf *);

        void (*load_window)(struct lz_mf *mf, const u8 *, u32);

        u32 (*get_matches)(struct lz_mf *, struct lz_match *);

        void (*skip_positions)(struct lz_mf *, u32);

        void (*destroy)(struct lz_mf *);

        size_t struct_size;
};

/*
 * Lempel-Ziv match-finder structure.
 *
 * Match-finding algorithms must embed this structure inside a private
 * structure.
 *
 * Don't directly access any of the members outside of lz_mf.h, lz_mf.c, and
 * match-finding algorithms.  Instead, use the lz_mf_*() wrappers.
 */
struct lz_mf {
        struct lz_mf_params params;
        struct lz_mf_ops ops;
        const u8 *cur_window;
        u32 cur_window_pos;
        u32 cur_window_size;
};

extern bool
lz_mf_params_valid(const struct lz_mf_params *params);

extern u64
lz_mf_get_needed_memory(enum lz_mf_algo algorithm, u32 max_window_size);

extern struct lz_mf *
lz_mf_alloc(const struct lz_mf_params *params);

extern void
lz_mf_load_window(struct lz_mf *mf, const u8 *window, u32 size);

#ifdef ENABLE_LZ_DEBUG
extern u32
lz_mf_get_matches(struct lz_mf *mf, struct lz_match *matches);
#else
/* See non-inline definition for comment  */
static inline u32
lz_mf_get_matches(struct lz_mf *mf, struct lz_match *matches)
{
        return mf->ops.get_matches(mf, matches);
}
#endif

#ifdef ENABLE_LZ_DEBUG
extern void
lz_mf_skip_positions(struct lz_mf *mf, u32 n);
#else
/* See non-inline definition for comment  */
static inline void
lz_mf_skip_positions(struct lz_mf *mf, u32 n)
{
        mf->ops.skip_positions(mf, n);
}
#endif

extern void
lz_mf_free(struct lz_mf *mf);

/*
 * Returns the match-finder's current position in the window.
 *
 * The current position begins at 0.  It increases by 1 when lz_mf_get_matches()
 * is called, and by 'n' when lz_mf_skip_positions() is called.
 *
 * Note: The behavior is undefined if the match-finder is advanced beyond the
 * end of the window.  (If this happens in ENABLE_LZ_DEBUG mode, an assertion
 * will be triggered.)
 */
static inline u32
lz_mf_get_position(const struct lz_mf *mf)
{
        return mf->cur_window_pos;
}

/*
 * Returns the number of bytes remaining in the window.
 */
static inline u32
lz_mf_get_bytes_remaining(const struct lz_mf *mf)
{
        return mf->cur_window_size - mf->cur_window_pos;
}

/*
 * Returns a pointer to the current window, offset by the current position.
 * Equivalently, this returns a pointer to the byte sequence that the next call
 * to lz_mf_get_matches() will match against.
 */
static inline const u8 *
lz_mf_get_window_ptr(const struct lz_mf *mf)
{
        return &mf->cur_window[mf->cur_window_pos];
}

#endif /* _WIMLIB_LZ_MF_H */