]> wimlib.net Git - wimlib/blob - src/lz_hash_chains.c
2e6d6543029bc35691d99eeb36a896ceb248527c
[wimlib] / src / lz_hash_chains.c
1 /*
2  * lz_hash_chains.c
3  *
4  * Hash chain match-finder for Lempel-Ziv compression.
5  *
6  * Copyright (c) 2014 Eric Biggers.  All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  *    notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND
20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
23  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
26  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
28  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
29  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30  */
31
32 #ifdef HAVE_CONFIG_H
33 #  include "config.h"
34 #endif
35
36 #include "wimlib/lz_extend.h"
37 #include "wimlib/lz_hash3.h"
38 #include "wimlib/lz_mf.h"
39 #include "wimlib/util.h"
40
41 #include <string.h>
42
43 /* log2 of the number of buckets in the hash table.  This can be changed.  */
44 #define LZ_HC_HASH_ORDER 15
45
46 #define LZ_HC_HASH_LEN   (1 << LZ_HC_HASH_ORDER)
47
48 struct lz_hc {
49         struct lz_mf base;
50         u32 *hash_tab; /* followed by 'prev_tab' in memory */
51         u32 next_hash;
52 };
53
54 static inline u32
55 lz_hc_hash(const u8 *p)
56 {
57         return lz_hash(p, LZ_HC_HASH_ORDER);
58 }
59
60 static void
61 lz_hc_set_default_params(struct lz_mf_params *params)
62 {
63         if (params->min_match_len < LZ_HASH_NBYTES)
64                 params->min_match_len = LZ_HASH_NBYTES;
65
66         if (params->max_match_len == 0)
67                 params->max_match_len = params->max_window_size;
68
69         if (params->max_search_depth == 0)
70                 params->max_search_depth = 50;
71
72         if (params->nice_match_len == 0)
73                 params->nice_match_len = 24;
74
75         if (params->nice_match_len < params->min_match_len)
76                 params->nice_match_len = params->min_match_len;
77
78         if (params->nice_match_len > params->max_match_len)
79                 params->nice_match_len = params->max_match_len;
80 }
81
82 static bool
83 lz_hc_params_valid(const struct lz_mf_params *_params)
84 {
85         struct lz_mf_params params = *_params;
86
87         lz_hc_set_default_params(&params);
88
89         return (params.min_match_len <= params.max_match_len);
90 }
91
92 static u64
93 lz_hc_get_needed_memory(u32 max_window_size)
94 {
95         u64 len = 0;
96
97         len += LZ_HC_HASH_LEN;
98         len += max_window_size;
99
100         return len * sizeof(u32);
101 }
102
103 static bool
104 lz_hc_init(struct lz_mf *_mf)
105 {
106         struct lz_hc *mf = (struct lz_hc *)_mf;
107
108         lz_hc_set_default_params(&mf->base.params);
109
110         mf->hash_tab = MALLOC(lz_hc_get_needed_memory(mf->base.params.max_window_size));
111         if (!mf->hash_tab)
112                 return false;
113
114         return true;
115 }
116
117 static void
118 lz_hc_load_window(struct lz_mf *_mf, const u8 window[], u32 size)
119 {
120         struct lz_hc *mf = (struct lz_hc *)_mf;
121
122         memset(mf->hash_tab, 0, LZ_HC_HASH_LEN * sizeof(u32));
123 }
124
125 static u32
126 lz_hc_get_matches(struct lz_mf *_mf, struct lz_match matches[])
127 {
128         struct lz_hc *mf = (struct lz_hc *)_mf;
129         const u8 * const window = mf->base.cur_window;
130         const u32 cur_pos = mf->base.cur_window_pos++;
131         const u8 * const strptr = &window[cur_pos];
132         const u32 bytes_remaining = mf->base.cur_window_size - cur_pos;
133         u32 * const prev_tab = mf->hash_tab + LZ_HC_HASH_LEN;
134         const u32 max_len = min(bytes_remaining, mf->base.params.max_match_len);
135         const u32 nice_len = min(max_len, mf->base.params.nice_match_len);
136         u32 best_len = mf->base.params.min_match_len - 1;
137         u32 depth_remaining = mf->base.params.max_search_depth;
138         struct lz_match *lz_matchptr = matches;
139         u32 hash;
140         u32 cur_match;
141
142         if (unlikely(bytes_remaining < LZ_HASH_REQUIRED_NBYTES + 1))
143                 return 0;
144
145         /* Insert the current position into the appropriate hash chain and set
146          * 'cur_match' to the previous head.
147          *
148          * For a slight performance improvement, we do each hash calculation one
149          * position in advance and prefetch the necessary hash table entry.  */
150
151         hash = mf->next_hash;
152         mf->next_hash = lz_hc_hash(strptr + 1);
153         prefetch(&mf->hash_tab[mf->next_hash]);
154         cur_match = mf->hash_tab[hash];
155         mf->hash_tab[hash] = cur_pos;
156         prev_tab[cur_pos] = cur_match;
157
158         /* Ensure we can find a match of at least the requested length.  */
159         if (unlikely(best_len >= max_len))
160                 return 0;
161
162         /* Search the appropriate hash chain for matches.  */
163         for (; cur_match && depth_remaining--; cur_match = prev_tab[cur_match]) {
164
165                 const u8 * const matchptr = &window[cur_match];
166                 u32 len;
167
168                 /* Considering the potential match at 'matchptr':  is it longer
169                  * than 'best_len'?
170                  *
171                  * The bytes at index 'best_len' are the most likely to differ,
172                  * so check them first.  */
173                 if (matchptr[best_len] != strptr[best_len])
174                         goto next_match;
175
176         #if HAVE_FAST_LZ_EXTEND
177                 if ((*(const u32 *)strptr & 0xFFFFFF) !=
178                     (*(const u32 *)matchptr & 0xFFFFFF))
179                         goto next_match;
180
181                 len = lz_extend(strptr, matchptr, 3, max_len);
182
183                 if (len > best_len) {
184                         best_len = len;
185
186                         *lz_matchptr++ = (struct lz_match) {
187                                 .len = best_len,
188                                 .offset = strptr - matchptr,
189                         };
190
191                         if (best_len >= nice_len)
192                                 break;
193                 }
194
195         #else /* HAVE_FAST_LZ_EXTEND */
196
197                 /* The bytes at indices 'best_len - 1' and '0' are less
198                  * important to check separately.  But doing so still gives a
199                  * slight performance improvement, at least on x86_64, probably
200                  * because they create separate branches for the CPU to predict
201                  * independently of the branches in the main comparison loops.
202                  */
203                  if (matchptr[best_len - 1] != strptr[best_len - 1] ||
204                      matchptr[0] != strptr[0])
205                         goto next_match;
206
207                 for (len = 1; len < best_len - 1; len++)
208                         if (matchptr[len] != strptr[len])
209                                 goto next_match;
210
211                 /* The match is the longest found so far ---
212                  * at least 'best_len' + 1 bytes.  Continue extending it.  */
213
214                 if (++best_len != max_len && strptr[best_len] == matchptr[best_len])
215                         while (++best_len != max_len)
216                                 if (strptr[best_len] != matchptr[best_len])
217                                         break;
218
219                 /* Record the match.  */
220                 *lz_matchptr++ = (struct lz_match) {
221                         .len = best_len,
222                         .offset = strptr - matchptr,
223                 };
224
225                 /* Terminate the search if 'nice_len' was reached.  */
226                 if (best_len >= nice_len)
227                         break;
228         #endif /* !HAVE_FAST_LZ_EXTEND */
229
230         next_match:
231                 /* Continue to next match in the chain.  */
232                 ;
233         }
234
235         return lz_matchptr - matches;
236 }
237
238 static void
239 lz_hc_skip_positions(struct lz_mf *_mf, u32 n)
240 {
241         struct lz_hc *mf = (struct lz_hc *)_mf;
242         u32 * const hash_tab = mf->hash_tab;
243         u32 * const prev_tab = hash_tab + LZ_HC_HASH_LEN;
244         const u8 * const window = mf->base.cur_window;
245         u32 cur_pos = mf->base.cur_window_pos;
246         u32 end_pos = cur_pos + n;
247         const u32 bytes_remaining = mf->base.cur_window_size - cur_pos;
248         u32 hash;
249         u32 next_hash;
250
251         mf->base.cur_window_pos = end_pos;
252
253         if (unlikely(bytes_remaining < n + (LZ_HASH_REQUIRED_NBYTES + 1) - 1)) {
254                 /* Nearing end of window.  */
255                 if (unlikely(bytes_remaining < (LZ_HASH_REQUIRED_NBYTES + 1)))
256                         return;
257
258                 end_pos = cur_pos + bytes_remaining - (LZ_HASH_REQUIRED_NBYTES + 1) + 1;
259         }
260
261         next_hash = mf->next_hash;
262         do {
263                 hash = next_hash;
264                 next_hash = lz_hc_hash(&window[cur_pos + 1]);
265                 prev_tab[cur_pos] = hash_tab[hash];
266                 hash_tab[hash] = cur_pos;
267         } while (++cur_pos != end_pos);
268
269         prefetch(&hash_tab[next_hash]);
270         mf->next_hash = next_hash;
271 }
272
273 static void
274 lz_hc_destroy(struct lz_mf *_mf)
275 {
276         struct lz_hc *mf = (struct lz_hc *)_mf;
277
278         FREE(mf->hash_tab);
279 }
280
281 const struct lz_mf_ops lz_hash_chains_ops = {
282         .params_valid      = lz_hc_params_valid,
283         .get_needed_memory = lz_hc_get_needed_memory,
284         .init              = lz_hc_init,
285         .load_window       = lz_hc_load_window,
286         .get_matches       = lz_hc_get_matches,
287         .skip_positions    = lz_hc_skip_positions,
288         .destroy           = lz_hc_destroy,
289         .struct_size       = sizeof(struct lz_hc),
290 };