Misc. cleanups
[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 #ifndef _HC_MATCHFINDER_H
31 #define _HC_MATCHFINDER_H
32
33 #include "wimlib/lz_extend.h"
34 #include "wimlib/lz_hash3.h"
35 #include "wimlib/matchfinder_common.h"
36 #include "wimlib/unaligned.h"
37
38 #ifndef HC_MATCHFINDER_HASH_ORDER
39 #  if MATCHFINDER_WINDOW_ORDER < 14
40 #    define HC_MATCHFINDER_HASH_ORDER 14
41 #  else
42 #    define HC_MATCHFINDER_HASH_ORDER 15
43 #  endif
44 #endif
45
46 #define HC_MATCHFINDER_HASH_LENGTH      (1UL << HC_MATCHFINDER_HASH_ORDER)
47
48 #define HC_MATCHFINDER_TOTAL_LENGTH     \
49         (HC_MATCHFINDER_HASH_LENGTH + MATCHFINDER_WINDOW_SIZE)
50
51 struct hc_matchfinder {
52         union {
53                 pos_t mf_data[HC_MATCHFINDER_TOTAL_LENGTH];
54                 struct {
55                         pos_t hash_tab[HC_MATCHFINDER_HASH_LENGTH];
56                         pos_t next_tab[MATCHFINDER_WINDOW_SIZE];
57                 };
58         };
59 } _aligned_attribute(MATCHFINDER_ALIGNMENT);
60
61 /*
62  * Call before running the first byte through the matchfinder.
63  */
64 static inline void
65 hc_matchfinder_init(struct hc_matchfinder *mf)
66 {
67         matchfinder_init(mf->hash_tab, HC_MATCHFINDER_HASH_LENGTH);
68 }
69
70 #if MATCHFINDER_IS_SLIDING
71 static inline void
72 hc_matchfinder_slide_window(struct hc_matchfinder *mf)
73 {
74         matchfinder_rebase(mf->mf_data, HC_MATCHFINDER_TOTAL_LENGTH);
75 }
76 #endif
77
78 /*
79  * Find the longest match longer than 'best_len'.
80  *
81  * @mf
82  *      The matchfinder structure.
83  * @in_base
84  *      Pointer to the next byte in the input buffer to process _at the last
85  *      time hc_matchfinder_init() or hc_matchfinder_slide_window() was called_.
86  * @in_next
87  *      Pointer to the next byte in the input buffer to process.  This is the
88  *      pointer to the bytes being matched against.
89  * @best_len
90  *      Require a match at least this long.
91  * @max_len
92  *      Maximum match length to return.
93  * @nice_len
94  *      Stop searching if a match of at least this length is found.
95  * @max_search_depth
96  *      Limit on the number of potential matches to consider.
97  * @offset_ret
98  *      The match offset is returned here.
99  *
100  * Return the length of the match found, or 'best_len' if no match longer than
101  * 'best_len' was found.
102  */
103 static inline unsigned
104 hc_matchfinder_longest_match(struct hc_matchfinder * const restrict mf,
105                              const u8 * const in_base,
106                              const u8 * const in_next,
107                              unsigned best_len,
108                              const unsigned max_len,
109                              const unsigned nice_len,
110                              const unsigned max_search_depth,
111                              unsigned *offset_ret)
112 {
113         unsigned depth_remaining = max_search_depth;
114         const u8 *best_matchptr = best_matchptr; /* uninitialized */
115         const u8 *matchptr;
116         unsigned len;
117         unsigned hash;
118         pos_t cur_match;
119         u32 first_3_bytes;
120
121         /* Insert the current sequence into the appropriate hash chain.  */
122         if (unlikely(max_len < LZ_HASH_REQUIRED_NBYTES))
123                 goto out;
124         first_3_bytes = load_u24_unaligned(in_next);
125         hash = lz_hash_u24(first_3_bytes, HC_MATCHFINDER_HASH_ORDER);
126         cur_match = mf->hash_tab[hash];
127         mf->next_tab[in_next - in_base] = cur_match;
128         mf->hash_tab[hash] = in_next - in_base;
129
130         if (unlikely(best_len >= max_len))
131                 goto out;
132
133         /* Search the appropriate hash chain for matches.  */
134
135         if (!(matchfinder_match_in_window(cur_match, in_base, in_next)))
136                 goto out;
137
138         if (best_len < 3) {
139                 for (;;) {
140                         /* No length 3 match found yet.
141                          * Check the first 3 bytes.  */
142                         matchptr = &in_base[cur_match];
143
144                         if (load_u24_unaligned(matchptr) == first_3_bytes)
145                                 break;
146
147                         /* Not a match; keep trying.  */
148                         cur_match = mf->next_tab[
149                                         matchfinder_slot_for_match(cur_match)];
150                         if (!matchfinder_match_in_window(cur_match,
151                                                          in_base, in_next))
152                                 goto out;
153                         if (!--depth_remaining)
154                                 goto out;
155                 }
156
157                 /* Found a length 3 match.  */
158                 best_matchptr = matchptr;
159                 best_len = lz_extend(in_next, best_matchptr, 3, max_len);
160                 if (best_len >= nice_len)
161                         goto out;
162                 cur_match = mf->next_tab[matchfinder_slot_for_match(cur_match)];
163                 if (!matchfinder_match_in_window(cur_match, in_base, in_next))
164                         goto out;
165                 if (!--depth_remaining)
166                         goto out;
167         }
168
169         for (;;) {
170                 for (;;) {
171                         matchptr = &in_base[cur_match];
172
173                         /* Already found a length 3 match.  Try for a longer match;
174                          * start by checking the last 2 bytes and the first 4 bytes.  */
175                 #if UNALIGNED_ACCESS_IS_FAST
176                         if ((load_u32_unaligned(matchptr + best_len - 3) ==
177                              load_u32_unaligned(in_next + best_len - 3)) &&
178                             (load_u32_unaligned(matchptr) ==
179                              load_u32_unaligned(in_next)))
180                 #else
181                         if (matchptr[best_len] == in_next[best_len])
182                 #endif
183                                 break;
184
185                         cur_match = mf->next_tab[matchfinder_slot_for_match(cur_match)];
186                         if (!matchfinder_match_in_window(cur_match, in_base, in_next))
187                                 goto out;
188                         if (!--depth_remaining)
189                                 goto out;
190                 }
191
192                 if (UNALIGNED_ACCESS_IS_FAST)
193                         len = 4;
194                 else
195                         len = 0;
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->next_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->next_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 }
248
249 #endif /* _HC_MATCHFINDER_H */