d880b2486d647ec40ec5b9d030826984e7b5eb4b
[wimlib] / include / wimlib / hc_matchfinder.h
1 /*
2  * hc_matchfinder.h
3  *
4  * Copyright (c) 2014 Eric Biggers.  All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  *
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.
16  *
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.
28  */
29
30 #pragma once
31
32 #include "wimlib/lz_extend.h"
33 #include "wimlib/lz_hash3.h"
34 #include "wimlib/matchfinder_common.h"
35 #include "wimlib/unaligned.h"
36
37 #ifndef HC_MATCHFINDER_HASH_ORDER
38 #  if MATCHFINDER_WINDOW_ORDER < 14
39 #    define HC_MATCHFINDER_HASH_ORDER 14
40 #  else
41 #    define HC_MATCHFINDER_HASH_ORDER 15
42 #  endif
43 #endif
44
45 #define HC_MATCHFINDER_HASH_LENGTH      (1UL << HC_MATCHFINDER_HASH_ORDER)
46
47 #define HC_MATCHFINDER_TOTAL_LENGTH     \
48         (HC_MATCHFINDER_HASH_LENGTH + MATCHFINDER_WINDOW_SIZE)
49
50 struct hc_matchfinder {
51         union {
52                 pos_t mf_data[HC_MATCHFINDER_TOTAL_LENGTH];
53                 struct {
54                         pos_t hash_tab[HC_MATCHFINDER_HASH_LENGTH];
55                         pos_t child_tab[MATCHFINDER_WINDOW_SIZE];
56                 };
57         };
58 } _aligned_attribute(MATCHFINDER_ALIGNMENT);
59
60 /*
61  * Call before running the first byte through the matchfinder.
62  */
63 static inline void
64 hc_matchfinder_init(struct hc_matchfinder *mf)
65 {
66         matchfinder_init(mf->hash_tab, HC_MATCHFINDER_HASH_LENGTH);
67 }
68
69 #if MATCHFINDER_IS_SLIDING
70 static inline void
71 hc_matchfinder_slide_window(struct hc_matchfinder *mf)
72 {
73         matchfinder_rebase(mf->mf_data, HC_MATCHFINDER_TOTAL_LENGTH);
74 }
75 #endif
76
77 /*
78  * Find the longest match longer than 'best_len'.
79  *
80  * @mf
81  *      The matchfinder structure.
82  * @in_base
83  *      Pointer to the next byte in the input buffer to process _at the last
84  *      time hc_matchfinder_init() or hc_matchfinder_slide_window() was called_.
85  * @in_next
86  *      Pointer to the next byte in the input buffer to process.  This is the
87  *      pointer to the bytes being matched against.
88  * @best_len
89  *      Require a match at least this long.
90  * @max_len
91  *      Maximum match length to return.
92  * @nice_len
93  *      Stop searching if a match of at least this length is found.
94  * @max_search_depth
95  *      Limit on the number of potential matches to consider.
96  * @offset_ret
97  *      The match offset is returned here.
98  *
99  * Return the length of the match found, or 'best_len' if no match longer than
100  * 'best_len' was found.
101  */
102 static inline unsigned
103 hc_matchfinder_longest_match(struct hc_matchfinder * const restrict mf,
104                              const u8 * const in_base,
105                              const u8 * const in_next,
106                              unsigned best_len,
107                              const unsigned max_len,
108                              const unsigned nice_len,
109                              const unsigned max_search_depth,
110                              unsigned *offset_ret)
111 {
112         unsigned depth_remaining = max_search_depth;
113         const u8 *best_matchptr = best_matchptr; /* uninitialized */
114         const u8 *matchptr;
115         unsigned len;
116         unsigned hash;
117         pos_t cur_match;
118         u32 first_3_bytes;
119
120         /* Insert the current sequence into the appropriate hash chain.  */
121         if (unlikely(max_len < LZ_HASH_REQUIRED_NBYTES))
122                 goto out;
123         first_3_bytes = load_u24_unaligned(in_next);
124         hash = lz_hash_u24(first_3_bytes, HC_MATCHFINDER_HASH_ORDER);
125         cur_match = mf->hash_tab[hash];
126         mf->child_tab[in_next - in_base] = cur_match;
127         mf->hash_tab[hash] = in_next - in_base;
128
129         if (unlikely(best_len >= max_len))
130                 goto out;
131
132         /* Search the appropriate hash chain for matches.  */
133
134         if (!(matchfinder_match_in_window(cur_match, in_base, in_next)))
135                 goto out;
136
137         if (best_len < 3) {
138                 for (;;) {
139                         /* No length 3 match found yet.
140                          * Check the first 3 bytes.  */
141                         matchptr = &in_base[cur_match];
142
143                         if (load_u24_unaligned(matchptr) == first_3_bytes)
144                                 break;
145
146                         /* Not a match; keep trying.  */
147                         cur_match = mf->child_tab[
148                                         matchfinder_slot_for_match(cur_match)];
149                         if (!matchfinder_match_in_window(cur_match,
150                                                          in_base, in_next))
151                                 goto out;
152                         if (!--depth_remaining)
153                                 goto out;
154                 }
155
156                 /* Found a length 3 match.  */
157                 best_matchptr = matchptr;
158                 best_len = lz_extend(in_next, best_matchptr, 3, max_len);
159                 if (best_len >= nice_len)
160                         goto out;
161                 cur_match = mf->child_tab[matchfinder_slot_for_match(cur_match)];
162                 if (!matchfinder_match_in_window(cur_match, in_base, in_next))
163                         goto out;
164                 if (!--depth_remaining)
165                         goto out;
166         }
167
168         for (;;) {
169                 for (;;) {
170                         matchptr = &in_base[cur_match];
171
172                         /* Already found a length 3 match.  Try for a longer match;
173                          * start by checking the last 2 bytes and the first 4 bytes.  */
174                 #if UNALIGNED_ACCESS_IS_FAST
175                         if ((load_u32_unaligned(matchptr + best_len - 3) ==
176                              load_u32_unaligned(in_next + best_len - 3)) &&
177                             (load_u32_unaligned(matchptr) ==
178                              load_u32_unaligned(in_next)))
179                 #else
180                         if (matchptr[best_len] == in_next[best_len])
181                 #endif
182                                 break;
183
184                         cur_match = mf->child_tab[matchfinder_slot_for_match(cur_match)];
185                         if (!matchfinder_match_in_window(cur_match, in_base, in_next))
186                                 goto out;
187                         if (!--depth_remaining)
188                                 goto out;
189                 }
190
191         #if UNALIGNED_ACCESS_IS_FAST
192                 len = 4;
193         #else
194                 len = 0;
195         #endif
196                 len = lz_extend(in_next, matchptr, len, max_len);
197                 if (len > best_len) {
198                         best_len = len;
199                         best_matchptr = matchptr;
200                         if (best_len >= nice_len)
201                                 goto out;
202                 }
203                 cur_match = mf->child_tab[matchfinder_slot_for_match(cur_match)];
204                 if (!matchfinder_match_in_window(cur_match, in_base, in_next))
205                         goto out;
206                 if (!--depth_remaining)
207                         goto out;
208         }
209 out:
210         *offset_ret = in_next - best_matchptr;
211         return best_len;
212 }
213
214 /*
215  * Advance the match-finder, but don't search for matches.
216  *
217  * @mf
218  *      The matchfinder structure.
219  * @in_base
220  *      Pointer to the next byte in the input buffer to process _at the last
221  *      time hc_matchfinder_init() or hc_matchfinder_slide_window() was called_.
222  * @in_next
223  *      Pointer to the next byte in the input buffer to process.
224  * @in_end
225  *      Pointer to the end of the input buffer.
226  * @count
227  *      Number of bytes to skip; must be > 0.
228  */
229 static inline void
230 hc_matchfinder_skip_positions(struct hc_matchfinder * restrict mf,
231                               const u8 *in_base,
232                               const u8 *in_next,
233                               const u8 *in_end,
234                               unsigned count)
235 {
236         unsigned hash;
237
238         if (unlikely(in_next + count >= in_end - LZ_HASH_REQUIRED_NBYTES))
239                 return;
240
241         do {
242                 hash = lz_hash(in_next, HC_MATCHFINDER_HASH_ORDER);
243                 mf->child_tab[in_next - in_base] = mf->hash_tab[hash];
244                 mf->hash_tab[hash] = in_next - in_base;
245                 in_next++;
246         } while (--count);
247 }