Annotate yet another unaligned memory access

[wimlib] / src / lz_binary_trees.c

/*
 * lz_binary_trees.c
 *
 * Binary tree match-finder for Lempel-Ziv compression.
 *
 * 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.
 */

/*
 * Note: the binary tree search/update algorithm is based on LzFind.c from
 * 7-Zip, which was written by Igor Pavlov and released into the public domain.
 */

#ifdef HAVE_CONFIG_H
#  include "config.h"
#endif

#include "wimlib/lz_extend.h"
#include "wimlib/lz_hash3.h"
#include "wimlib/lz_mf.h"
#include "wimlib/util.h"

#include <string.h>

/* log2 of the number of buckets in the hash table.  This can be changed.  */
#define LZ_BT_HASH_ORDER 16

#define LZ_BT_HASH_LEN (1 << LZ_BT_HASH_ORDER)

/* Number of entries in the digram table.
 *
 * Note:  You rarely get length-2 matches if you use length-3 hashing.  But
 * since binary trees are typically used for higher compression ratios than hash
 * chains, it is helpful for this match-finder to find length-2 matches as well.
 * Therefore this match-finder also uses a digram table to find length-2 matches
 * when the minimum match length is 2.  */
#define LZ_BT_DIGRAM_TAB_LEN    (256 * 256)

struct lz_bt {
        struct lz_mf base;
        u32 *hash_tab;
        u32 *digram_tab;
        u32 *child_tab;
        u32 next_hash;
        u16 next_digram;
};

static inline u32
lz_bt_hash(const u8 *p)
{
        return lz_hash(p, LZ_BT_HASH_ORDER);
}

static void
lz_bt_set_default_params(struct lz_mf_params *params)
{
        if (params->min_match_len == 0)
                params->min_match_len = 2;

        if (params->max_match_len == 0)
                params->max_match_len = UINT32_MAX;

        if (params->max_search_depth == 0)
                params->max_search_depth = 50;

        if (params->nice_match_len == 0)
                params->nice_match_len = 24;

        if (params->nice_match_len < params->min_match_len)
                params->nice_match_len = params->min_match_len;

        if (params->nice_match_len > params->max_match_len)
                params->nice_match_len = params->max_match_len;
}

static bool
lz_bt_params_valid(const struct lz_mf_params *params)
{
        return true;
}

static u64
lz_bt_get_needed_memory(u32 max_window_size)
{
        u64 len = 0;

        len += LZ_BT_HASH_LEN;           /* hash_tab */
        len += LZ_BT_DIGRAM_TAB_LEN;     /* digram_tab */
        len += 2 * (u64)max_window_size; /* child_tab */

        return len * sizeof(u32);
}

static bool
lz_bt_init(struct lz_mf *_mf)
{
        struct lz_bt *mf = (struct lz_bt *)_mf;
        struct lz_mf_params *params = &mf->base.params;
        size_t len = 0;

        lz_bt_set_default_params(params);

        /* Allocate space for 'hash_tab', 'digram_tab', and 'child_tab'.  */

        len += LZ_BT_HASH_LEN;
        if (params->min_match_len == 2)
                len += LZ_BT_DIGRAM_TAB_LEN;
        len += 2 * params->max_window_size;

        mf->hash_tab = MALLOC(len * sizeof(u32));
        if (!mf->hash_tab)
                return false;

        if (params->min_match_len == 2) {
                mf->digram_tab = mf->hash_tab + LZ_BT_HASH_LEN;
                mf->child_tab = mf->digram_tab + LZ_BT_DIGRAM_TAB_LEN;
        } else {
                mf->child_tab = mf->hash_tab + LZ_BT_HASH_LEN;
        }

        return true;
}

static void
lz_bt_load_window(struct lz_mf *_mf, const u8 window[], u32 size)
{
        struct lz_bt *mf = (struct lz_bt *)_mf;
        size_t clear_len;

        /* Clear hash_tab and digram_tab.
         * Note: child_tab need not be cleared.  */
        clear_len = LZ_BT_HASH_LEN;
        if (mf->digram_tab)
                clear_len += LZ_BT_DIGRAM_TAB_LEN;
        memset(mf->hash_tab, 0, clear_len * sizeof(u32));
}

/*
 * Search the binary tree of the current hash code for matches.  At the same
 * time, update this tree to add the current position in the window.
 *
 * @window
 *      The window being searched.
 * @cur_pos
 *      The current position in the window.
 * @child_tab
 *      Table of child pointers for the binary tree.  The children of the node
 *      for position 'i' in the window are child_tab[i * 2] and child_tab[i*2 +
 *      1].  Zero is reserved for the 'null' value (no child).  Consequently, we
 *      don't recognize matches beginning at position 0.   In fact, the node for
 *      position 0 in the window will not be used at all, which is just as well
 *      because we use 0-based indices which don't work for position 0.
 * @cur_match
 *      The position in the window at which the binary tree for the current hash
 *      code is rooted.  This can be 0, which indicates that the binary tree for
 *      the current hash code is empty.
 * @min_len
 *      Ignore matches shorter than this length.  This must be at least 1.
 * @nice_len
 *      Stop searching if a match of this length or longer is found.  This must
 *      be less than or equal to @max_len.
 * @max_len
 *      Maximum length of matches to return.  This can be longer than @nice_len,
 *      in which case a match of length @nice_len will still cause the search to
 *      be terminated, but the match will be extended up to @max_len bytes
 *      first.
 * @max_search_depth
 *      Stop if we reach this depth in the binary tree.
 * @matches
 *      The array in which to produce the matches.  The matches will be produced
 *      in order of increasing length and increasing offset.  No more than one
 *      match shall have any given length, nor shall any match be shorter than
 *      @min_len, nor shall any match be longer than @max_len, nor shall any two
 *      matches have the same offset.
 *
 * Returns a pointer to the next free slot in @matches.
 */
static struct lz_match *
do_search(const u8 window[restrict],
          const u32 cur_pos,
          u32 child_tab[restrict],
          u32 cur_match,
          const u32 min_len,
          const u32 nice_len,
          const u32 max_len,
          const u32 max_search_depth,
          struct lz_match *lz_matchptr)
{
        /*
         * Here's my explanation of how this code actually works.  Beware: this
         * algorithm is a *lot* trickier than searching for matches via hash
         * chains.  But it can be significantly better, especially when doing
         * "optimal" parsing, which is why it gets used, e.g. in LZMA as well as
         * here.
         *
         * ---------------------------------------------------------------------
         *
         *                              Data structure
         *
         * Basically, there is not just one binary tree, but rather one binary
         * tree per hash code.  For a given hash code, the binary tree indexes
         * previous positions in the window that have that same hash code.  The
         * key for each node is the "string", or byte sequence, beginning at the
         * corresponding position in the window.
         *
         * Each tree maintains the invariant that if node C is a child of node
         * P, then the window position represented by node C is smaller than
         * ("left of") the window position represented by node P.  Equivalently,
         * while descending into a tree, the match distances ("offsets") from
         * the current position are non-decreasing --- actually strictly
         * increasing, because each node represents a unique position.
         *
         * In addition, not all previous positions sharing the same hash code
         * will necessarily be represented in each binary tree; see the
         * "Updating" section.
         *
         * ---------------------------------------------------------------------
         *
         *                                Searching
         *
         * Suppose we want to search for LZ77-style matches with the string
         * beginning at the current window position and extending for @max_len
         * bytes.  To do this, we can search for this string in the binary tree
         * for this string's hash code.  Each node visited during the search is
         * a potential match.  This method will find the matches efficiently
         * because they will converge on the current string, due to the nature
         * of the binary search.
         *
         * Naively, when visiting a node that represents a match of length N, we
         * must compare N + 1 bytes in order to determine the length of that
         * match and the lexicographic ordering of that match relative to the
         * current string (which determines whether we need to step left or
         * right into the next level of the tree, as per the standard binary
         * tree search algorithm).  However, as an optimization, we need not
         * explicitly examine the full length of the match at each node.  To see
         * that this is true, suppose that we examine a node during the search,
         * and we find that the corresponding match is less (alt. greater) than
         * the current string.  Then, because of how binary tree search
         * operates, the match must be lexicographically greater (alt. lesser)
         * than any ancestor node that corresponded to a match lexicographically
         * lesser (alt. greater) than the current string.  Therefore, the match
         * must be at least as long as the match for any such ancestor node.
         * Therefore, the lengths of lexicographically-lesser (alt. greater)
         * matches must be non-decreasing as they are encountered by the tree
         * search.
         *
         * Using this observation, we can maintain two variables, 'best_lt_len'
         * and 'best_gt_len', that represent the length of the longest
         * lexicographically lesser and greater, respectively, match that has
         * been examined so far.   Then, when examining a new match, we need
         * only start comparing at the index min(best_lt_len, best_gt_len) byte.
         * Note that we cannot know beforehand whether the match will be
         * lexicographically lesser or greater, hence the need for taking the
         * minimum of these two lengths.
         *
         * As noted earlier, as we descend into the tree, the potential matches
         * will have strictly increasing offsets.  To make things faster for
         * higher-level parsing / match-choosing code, we do not want to return
         * a shorter match that has a larger offset than a longer match.  This
         * is because a longer match can always be truncated to a shorter match
         * if needed, and smaller offsets usually (depending on the compression
         * format) take fewer bits to encode than larger offsets.
         * Consequently, we keep a potential match only if it is longer than the
         * previous longest match that has been found.  This has the added
         * advantage of producing the array of matches sorted by strictly
         * increasing lengths as well as strictly decreasing offsets.
         *
         * In degenerate cases, the binary tree might become severely
         * unbalanced.  To prevent excessive running times, we stop immediately
         * (and return any matches that happen to have been found so far) if the
         * current depth exceeds @max_search_depth.  Note that this cutoff can
         * occur before the longest match has been found, which is usually bad
         * for the compression ratio.
         *
         * ---------------------------------------------------------------------
         *
         *                              Updating
         *
         * I've explained how to find matches by searching the binary tree of
         * the current hash code.  But how do we get the binary tree in the
         * first place?  Since the tree is built incrementally, the real
         * question is how do we update the tree to "add" the current window
         * position.
         *
         * The tree maintains the invariant that a node's parent always has a
         * larger position (a.k.a. smaller match offset) than itself.
         * Therefore, the root node must always have the largest position; and
         * since the current position is larger than any previous position, the
         * current position must become the root of the tree.
         *
         * A correct, but silly, approach is to simply add the previous root as
         * a child of the new root, using either the left or right child pointer
         * depending on the lexicographic ordering of the strings.  This works,
         * but it really just produces a linked list, so it's not sufficient.
         *
         * Instead, we can initially mark the new root's left child pointer as
         * "pending (less than)" and its right child pointer as "pending
         * (greater than)".  Then, during the search, when we examine a match
         * that is lexicographically less than the current string, we link the
         * "pending (less than)" pointer to the node of that match, then set the
         * right child pointer of *that* node as "pending (less than)".
         * Similarly, when we examine a match that is lexicographically greater
         * than the current string, we link the "pending (greater than)" pointer
         * to the node of that match, then set the left child pointer of *that*
         * node as "pending (greater than)".
         *
         * If the search terminates before the current string is found (up to a
         * precision of @nice_len bytes), then we set "pending (less than)" and
         * "pending (greater than)" to point to nothing.  Alternatively, if the
         * search terminates due to finding the current string (up to a
         * precision of @nice_len bytes), then we set "pending (less than)" and
         * "pending (greater than)" to point to the appropriate children of that
         * match.
         *
         * Why does this work?  Well, we can think of it this way: the "pending
         * (less than)" pointer is reserved for the next match we find that is
         * lexicographically *less than* the current string, and the "pending
         * (greater than)" pointer is reserved for the next match we find that
         * is lexicographically *greater than* the current string.  This
         * explains why when we find a match that is lexicographically less than
         * the current string, we set the "pending (less than)" pointer to point
         * to that match.  And the reason we change "pending (less than)" to the
         * right pointer of the match in that case is because we're walking down
         * into that subtree, and the next match lexicographically *less than*
         * the current string is guaranteed to be lexicographically *greater
         * than* that match, so it should be set as the right subtree of that
         * match.  But the next match in that subtree that is lexicographically
         * *greater than* the current string will need to be moved to the
         * "pending (greater than)" pointer farther up the tree.
         *
         * It's complicated, but it should make sense if you think about it.
         * The algorithm basically just moves subtrees into the correct
         * locations as it walks down the tree for the search.  But also, if the
         * algorithm actually finds a match of length @nice_len with the current
         * string, it no longer needs that match node and can discard it.  The
         * algorithm also will discard nodes if the search terminates due to the
         * depth limit.  For these reasons, the binary tree might not, in fact,
         * contain all valid positions.
         */

        u32 best_lt_len = 0;
        u32 best_gt_len = 0;
        u32 best_len = min_len - 1;
        u32 *pending_lt_ptr = &child_tab[cur_pos * 2 + 0];
        u32 *pending_gt_ptr = &child_tab[cur_pos * 2 + 1];
        const u8 * const strptr = &window[cur_pos];
        u32 depth_remaining = max_search_depth;

        for (;;) {
                const u8 *matchptr;
                u32 len;

                if (cur_match == 0 || depth_remaining-- == 0) {
                        *pending_lt_ptr = 0;
                        *pending_gt_ptr = 0;
                        return lz_matchptr;
                }

                matchptr = &window[cur_match];
                len = min(best_lt_len, best_gt_len);

                if (matchptr[len] == strptr[len]) {

                        len = lz_extend(strptr, matchptr, len + 1, max_len);

                        if (len > best_len) {
                                best_len = len;

                                *lz_matchptr++ = (struct lz_match) {
                                        .len = len,
                                        .offset = strptr - matchptr,
                                };

                                if (len >= nice_len) {
                                        *pending_lt_ptr = child_tab[cur_match * 2 + 0];
                                        *pending_gt_ptr = child_tab[cur_match * 2 + 1];
                                        return lz_matchptr;
                                }
                        }
                }

                if (matchptr[len] < strptr[len]) {
                        *pending_lt_ptr = cur_match;
                        pending_lt_ptr = &child_tab[cur_match * 2 + 1];
                        cur_match = *pending_lt_ptr;
                        best_lt_len = len;
                } else {
                        *pending_gt_ptr = cur_match;
                        pending_gt_ptr = &child_tab[cur_match * 2 + 0];
                        cur_match = *pending_gt_ptr;
                        best_gt_len = len;
                }
        }
}

static u32
lz_bt_get_matches(struct lz_mf *_mf, struct lz_match matches[])
{
        struct lz_bt *mf = (struct lz_bt *)_mf;
        const u8 * const window = mf->base.cur_window;
        const u32 cur_pos = mf->base.cur_window_pos++;
        const u32 bytes_remaining = mf->base.cur_window_size - cur_pos;
        u32 min_len;
        const u32 max_len = min(bytes_remaining, mf->base.params.max_match_len);
        const u32 nice_len = min(max_len, mf->base.params.nice_match_len);
        u32 hash;
        u32 cur_match;
        struct lz_match *lz_matchptr = matches;

        if (unlikely(bytes_remaining < LZ_HASH_REQUIRED_NBYTES + 1))
                return 0;

        if (mf->digram_tab) {
                /* Search the digram table for a length 2 match.  */

                const u16 digram = mf->next_digram;
                mf->next_digram = load_u16_unaligned(&window[cur_pos + 1]);
                prefetch(&mf->digram_tab[mf->next_digram]);
                cur_match = mf->digram_tab[digram];
                mf->digram_tab[digram] = cur_pos;

                /* We're only interested in matches of length exactly 2, since
                 * those won't be found during the binary tree search.
                 *
                 * Note: it's possible to extend this match as much as possible,
                 * then use its length plus 1 as min_len for the binary tree
                 * search.  However I found this actually *reduced* performance
                 * slightly, evidently because the binary tree still needs to be
                 * searched/updated starting from the root in either case.  */
                if (cur_match != 0 && window[cur_match + 2] != window[cur_pos + 2]) {
                        *lz_matchptr++ = (struct lz_match) {
                                .len = 2,
                                .offset = cur_pos - cur_match,
                        };
                }
                min_len = 3;
        } else {
                min_len = mf->base.params.min_match_len;
        }

        hash = mf->next_hash;
        mf->next_hash = lz_bt_hash(&window[cur_pos + 1]);
        prefetch(&mf->hash_tab[mf->next_hash]);
        cur_match = mf->hash_tab[hash];
        mf->hash_tab[hash] = cur_pos;

        /* Search the binary tree of 'hash' for matches while re-rooting it at
         * the current position.  */
        lz_matchptr = do_search(window,
                                cur_pos,
                                mf->child_tab,
                                cur_match,
                                min_len,
                                nice_len,
                                max_len,
                                mf->base.params.max_search_depth,
                                lz_matchptr);

        /* Return the number of matches found.  */
        return lz_matchptr - matches;
}

/* This is very similar to do_search(), but it does not save any matches.
 * See do_search() for explanatory comments.  */
static void
do_skip(const u8 window[restrict],
        const u32 cur_pos,
        u32 child_tab[restrict],
        u32 cur_match,
        const u32 nice_len,
        const u32 max_search_depth)
{
        u32 best_lt_len = 0;
        u32 best_gt_len = 0;
        u32 *pending_lt_ptr = &child_tab[cur_pos * 2 + 0];
        u32 *pending_gt_ptr = &child_tab[cur_pos * 2 + 1];
        const u8 * const strptr = &window[cur_pos];
        u32 depth_remaining = max_search_depth;
        for (;;) {
                const u8 *matchptr;
                u32 len;

                if (cur_match == 0 || depth_remaining-- == 0) {
                        *pending_lt_ptr = 0;
                        *pending_gt_ptr = 0;
                        return;
                }

                matchptr = &window[cur_match];
                len = min(best_lt_len, best_gt_len);

                if (matchptr[len] == strptr[len]) {
                        len = lz_extend(strptr, matchptr, len + 1, nice_len);
                        if (len == nice_len) {
                                *pending_lt_ptr = child_tab[cur_match * 2 + 0];
                                *pending_gt_ptr = child_tab[cur_match * 2 + 1];
                                return;
                        }
                }
                if (matchptr[len] < strptr[len]) {
                        *pending_lt_ptr = cur_match;
                        pending_lt_ptr = &child_tab[cur_match * 2 + 1];
                        cur_match = *pending_lt_ptr;
                        best_lt_len = len;
                } else {
                        *pending_gt_ptr = cur_match;
                        pending_gt_ptr = &child_tab[cur_match * 2 + 0];
                        cur_match = *pending_gt_ptr;
                        best_gt_len = len;
                }
        }
}

static void
lz_bt_skip_positions(struct lz_mf *_mf, u32 n)
{
        struct lz_bt *mf = (struct lz_bt *)_mf;
        const u8 * const window = mf->base.cur_window;
        u32 cur_pos = mf->base.cur_window_pos;
        u32 end_pos = cur_pos + n;
        u32 bytes_remaining = mf->base.cur_window_size - cur_pos;
        u32 hash;
        u32 next_hash;
        u32 cur_match;
        u16 digram;
        u16 next_digram;

        mf->base.cur_window_pos = end_pos;

        if (unlikely(bytes_remaining < n + (LZ_HASH_REQUIRED_NBYTES + 1) - 1)) {
                /* Nearing end of window.  */
                if (unlikely(bytes_remaining < (LZ_HASH_REQUIRED_NBYTES + 1)))
                        return;

                end_pos = cur_pos + bytes_remaining - (LZ_HASH_REQUIRED_NBYTES + 1) + 1;
        }

        next_hash = mf->next_hash;
        next_digram = mf->next_digram;
        do {
                if (mf->digram_tab) {
                        digram = next_digram;
                        next_digram = load_u16_unaligned(&window[cur_pos + 1]);
                        mf->digram_tab[digram] = cur_pos;
                }

                hash = next_hash;
                next_hash = lz_bt_hash(&window[cur_pos + 1]);
                cur_match = mf->hash_tab[hash];
                mf->hash_tab[hash] = cur_pos;

                /* Update the binary tree for the appropriate hash code.  */
                do_skip(window,
                        cur_pos,
                        mf->child_tab,
                        cur_match,
                        min(bytes_remaining, mf->base.params.nice_match_len),
                        mf->base.params.max_search_depth);

                bytes_remaining--;
        } while (++cur_pos != end_pos);

        if (mf->digram_tab) {
                prefetch(&mf->digram_tab[next_digram]);
                mf->next_digram = next_digram;
        }

        prefetch(&mf->hash_tab[next_hash]);
        mf->next_hash = next_hash;
}

static void
lz_bt_destroy(struct lz_mf *_mf)
{
        struct lz_bt *mf = (struct lz_bt *)_mf;

        FREE(mf->hash_tab);
        /* mf->hash_tab shares storage with mf->digram_tab and mf->child_tab. */
}

const struct lz_mf_ops lz_binary_trees_ops = {
        .params_valid      = lz_bt_params_valid,
        .get_needed_memory = lz_bt_get_needed_memory,
        .init              = lz_bt_init,
        .load_window       = lz_bt_load_window,
        .get_matches       = lz_bt_get_matches,
        .skip_positions    = lz_bt_skip_positions,
        .destroy           = lz_bt_destroy,
        .struct_size       = sizeof(struct lz_bt),
};