4 * Copyright (c) 2014 Eric Biggers. All rights reserved.
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
24 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
25 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
26 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
27 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 #include "wimlib/lz_extend.h"
33 #include "wimlib/lz_hash3.h"
34 #include "wimlib/matchfinder_common.h"
35 #include "wimlib/unaligned.h"
37 #ifndef BT_MATCHFINDER_HASH_ORDER
38 # if MATCHFINDER_WINDOW_ORDER < 14
39 # define BT_MATCHFINDER_HASH_ORDER 14
41 # define BT_MATCHFINDER_HASH_ORDER 15
45 #define BT_MATCHFINDER_HASH_LENGTH (1UL << BT_MATCHFINDER_HASH_ORDER)
47 #define BT_MATCHFINDER_TOTAL_LENGTH \
48 (BT_MATCHFINDER_HASH_LENGTH + (2UL * MATCHFINDER_WINDOW_SIZE))
50 struct bt_matchfinder {
52 pos_t mf_data[BT_MATCHFINDER_TOTAL_LENGTH];
54 pos_t hash_tab[BT_MATCHFINDER_HASH_LENGTH];
55 pos_t child_tab[2UL * MATCHFINDER_WINDOW_SIZE];
58 } _aligned_attribute(MATCHFINDER_ALIGNMENT);
61 bt_matchfinder_init(struct bt_matchfinder *mf)
63 matchfinder_init(mf->hash_tab, BT_MATCHFINDER_HASH_LENGTH);
66 #if MATCHFINDER_IS_SLIDING
68 bt_matchfinder_slide_window(struct bt_matchfinder *mf)
70 matchfinder_rebase(mf->mf_data, BT_MATCHFINDER_TOTAL_LENGTH);
74 static inline unsigned
75 bt_matchfinder_get_matches(struct bt_matchfinder * const restrict mf,
76 const u8 * const in_base,
77 const u8 * const in_next,
78 const unsigned min_len,
79 const unsigned max_len,
80 const unsigned nice_len,
81 const unsigned max_search_depth,
82 unsigned long *prev_hash,
83 struct lz_match * const restrict matches)
85 struct lz_match *lz_matchptr = matches;
86 unsigned depth_remaining = max_search_depth;
91 pos_t *pending_lt_ptr, *pending_gt_ptr;
92 unsigned best_lt_len, best_gt_len;
96 if (unlikely(max_len < LZ_HASH_REQUIRED_NBYTES + 1))
100 *prev_hash = lz_hash(in_next + 1, BT_MATCHFINDER_HASH_ORDER);
101 prefetch(&mf->hash_tab[*prev_hash]);
102 cur_match = mf->hash_tab[hash];
103 mf->hash_tab[hash] = in_next - in_base;
105 best_len = min_len - 1;
106 pending_lt_ptr = &mf->child_tab[(in_next - in_base) << 1];
107 pending_gt_ptr = &mf->child_tab[((in_next - in_base) << 1) + 1];
111 if (!matchfinder_match_in_window(cur_match,
115 *pending_lt_ptr = MATCHFINDER_INITVAL;
116 *pending_gt_ptr = MATCHFINDER_INITVAL;
117 return lz_matchptr - matches;
120 matchptr = &in_base[cur_match];
121 len = min(best_lt_len, best_gt_len);
123 children = &mf->child_tab[(unsigned long)
124 matchfinder_slot_for_match(cur_match) << 1];
126 if (matchptr[len] == in_next[len]) {
128 len = lz_extend(in_next, matchptr, len + 1, max_len);
130 if (len > best_len) {
133 lz_matchptr->length = len;
134 lz_matchptr->offset = in_next - matchptr;
137 if (len >= nice_len) {
138 *pending_lt_ptr = children[0];
139 *pending_gt_ptr = children[1];
140 return lz_matchptr - matches;
145 if (matchptr[len] < in_next[len]) {
146 *pending_lt_ptr = cur_match;
147 pending_lt_ptr = &children[1];
148 cur_match = *pending_lt_ptr;
151 *pending_gt_ptr = cur_match;
152 pending_gt_ptr = &children[0];
153 cur_match = *pending_gt_ptr;
160 bt_matchfinder_skip_position(struct bt_matchfinder * const restrict mf,
161 const u8 * const in_base,
162 const u8 * const in_next,
163 const u8 * const in_end,
164 const unsigned nice_len,
165 const unsigned max_search_depth,
166 unsigned long *prev_hash)
168 unsigned depth_remaining = max_search_depth;
172 pos_t *pending_lt_ptr, *pending_gt_ptr;
173 unsigned best_lt_len, best_gt_len;
177 if (unlikely(in_end - in_next < LZ_HASH_REQUIRED_NBYTES + 1))
181 *prev_hash = lz_hash(in_next + 1, BT_MATCHFINDER_HASH_ORDER);
182 prefetch(&mf->hash_tab[*prev_hash]);
183 cur_match = mf->hash_tab[hash];
184 mf->hash_tab[hash] = in_next - in_base;
186 depth_remaining = max_search_depth;
187 pending_lt_ptr = &mf->child_tab[(in_next - in_base) << 1];
188 pending_gt_ptr = &mf->child_tab[((in_next - in_base) << 1) + 1];
192 if (!matchfinder_match_in_window(cur_match,
196 *pending_lt_ptr = MATCHFINDER_INITVAL;
197 *pending_gt_ptr = MATCHFINDER_INITVAL;
201 matchptr = &in_base[cur_match];
202 len = min(best_lt_len, best_gt_len);
204 children = &mf->child_tab[(unsigned long)
205 matchfinder_slot_for_match(cur_match) << 1];
207 if (matchptr[len] == in_next[len]) {
208 len = lz_extend(in_next, matchptr, len + 1, nice_len);
209 if (len == nice_len) {
210 *pending_lt_ptr = children[0];
211 *pending_gt_ptr = children[1];
216 if (matchptr[len] < in_next[len]) {
217 *pending_lt_ptr = cur_match;
218 pending_lt_ptr = &children[1];
219 cur_match = *pending_lt_ptr;
222 *pending_gt_ptr = cur_match;
223 pending_gt_ptr = &children[0];
224 cur_match = *pending_gt_ptr;