-/*
- * lz_brute_force.c
- *
- * Brute force 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.
- */
-
-#ifdef HAVE_CONFIG_H
-# include "config.h"
-#endif
-
-#include "wimlib/lz_mf.h"
-#include "wimlib/util.h"
-
-static bool
-lz_bf_params_valid(const struct lz_mf_params *params)
-{
- return true;
-}
-
-static u64
-lz_bf_get_needed_memory(u32 max_window_size)
-{
- return 0;
-}
-
-static bool
-lz_bf_init(struct lz_mf *mf)
-{
- if (mf->params.min_match_len == 0)
- mf->params.min_match_len = 2;
-
- if (mf->params.max_match_len == 0)
- mf->params.max_match_len = mf->params.max_window_size;
-
- if (mf->params.max_search_depth == 0)
- mf->params.max_search_depth = 32;
-
- mf->params.max_search_depth = DIV_ROUND_UP(mf->params.max_search_depth, 8);
-
- if (mf->params.nice_match_len == 0)
- mf->params.nice_match_len = 24;
-
- if (mf->params.nice_match_len < mf->params.min_match_len)
- mf->params.nice_match_len = mf->params.min_match_len;
-
- if (mf->params.nice_match_len > mf->params.max_match_len)
- mf->params.nice_match_len = mf->params.max_match_len;
-
- return true;
-}
-
-static void
-lz_bf_load_window(struct lz_mf *mf, const u8 window[], u32 size)
-{
-}
-
-static u32
-lz_bf_get_matches(struct lz_mf *mf, struct lz_match matches[])
-{
- const u8 * const strptr = lz_mf_get_window_ptr(mf);
- const u32 max_len = min(lz_mf_get_bytes_remaining(mf),
- mf->params.nice_match_len);
- u32 best_len = mf->params.min_match_len - 1;
- u32 num_matches = 0;
- const u8 *matchptr = strptr;
-
- if (best_len >= max_len)
- goto out;
-
- while (matchptr-- > mf->cur_window) {
-
- u32 len;
-
- if (matchptr[best_len] != strptr[best_len] ||
- matchptr[best_len - 1] != strptr[best_len - 1] ||
- matchptr[0] != strptr[0])
- goto next_match;
-
- for (len = 1; len < best_len - 1; len++)
- if (matchptr[len] != strptr[len])
- goto next_match;
-
- len = best_len;
-
- while (++len != max_len)
- if (matchptr[len] != strptr[len])
- break;
-
- matches[num_matches++] = (struct lz_match) {
- .len = len,
- .offset = strptr - matchptr,
- };
- best_len = len;
- if (best_len == max_len)
- break;
- if (num_matches == mf->params.max_search_depth)
- break;
- next_match:
- ;
- }
-
- /* If the longest match is @nice_match_len in length, it may have been
- * truncated. Try extending it up to the maximum match length. */
- if (num_matches != 0 &&
- matches[num_matches - 1].len == mf->params.nice_match_len)
- {
- const u8 * const matchptr = strptr - matches[num_matches - 1].offset;
- const u32 len_limit = min(lz_mf_get_bytes_remaining(mf),
- mf->params.max_match_len);
- u32 len;
-
- len = matches[num_matches - 1].len;
- while (len < len_limit && strptr[len] == matchptr[len])
- len++;
- matches[num_matches - 1].len = len;
- }
-
-out:
- mf->cur_window_pos++;
- return num_matches;
-}
-
-static void
-lz_bf_skip_positions(struct lz_mf *mf, u32 n)
-{
- mf->cur_window_pos += n;
-}
-
-static void
-lz_bf_destroy(struct lz_mf *mf)
-{
-}
-
-const struct lz_mf_ops lz_brute_force_ops = {
- .params_valid = lz_bf_params_valid,
- .get_needed_memory = lz_bf_get_needed_memory,
- .init = lz_bf_init,
- .load_window = lz_bf_load_window,
- .get_matches = lz_bf_get_matches,
- .skip_positions = lz_bf_skip_positions,
- .destroy = lz_bf_destroy,
- .struct_size = sizeof(struct lz_mf),
-};
git://wimlib.net / wimlib / commitdiff