6e06e42bf54a98870cd036b5312d3157003f39bd
[wimlib] / include / wimlib / lz_sarray.h
1 /*
2  * lz_sarray.h
3  *
4  * Suffix array match-finder for Lempel-Ziv compression.
5  */
6
7 /*
8  * Copyright (c) 2013, 2014 Eric Biggers.  All rights reserved.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  *
14  * 1. Redistributions of source code must retain the above copyright
15  *    notice, this list of conditions and the following disclaimer.
16  *
17  * 2. Redistributions in binary form must reproduce the above copyright
18  *    notice, this list of conditions and the following disclaimer in the
19  *    documentation and/or other materials provided with the distribution.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND
22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
25  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
28  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
29  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
30  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
31  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32  */
33
34 #ifndef _WIMLIB_LZ_SARRAY_H
35 #define _WIMLIB_LZ_SARRAY_H
36
37 #include "wimlib/compiler.h" /* must define '_always_inline_attribute'  */
38 #include "wimlib/lz.h"       /* must define 'struct raw_match' and LZ_ASSERT()  */
39 #include "wimlib/types.h"    /* must define 'bool', 'u8', 'u16, and 'u32'  */
40
41 struct salink;
42
43 /* Position type --- must be an unsigned type large enough to hold the length of
44  * longest window for which the suffix array match-finder will be used.  */
45 typedef u32 lz_sarray_pos_t;
46
47 /* Length type --- must be an unsigned type large enough to hold the maximum
48  * match length.  */
49 typedef u16 lz_sarray_len_t;
50
51 /* Cost type, for the user-provided match cost evaluation function.  */
52 typedef lz_sarray_pos_t lz_sarray_cost_t;
53
54 #define LZ_SARRAY_LEN_MAX       ((lz_sarray_len_t)~0UL)
55 #define LZ_SARRAY_POS_MAX       ((lz_sarray_pos_t)~0UL)
56 #define LZ_SARRAY_INFINITE_COST ((lz_sarray_cost_t)~0UL)
57
58 /* State of the suffix array LZ (Lempel-Ziv) match-finder.
59  *
60  * This is defined here for benefit of the inlined code.  It's not intended for
61  * code outside the match-finder itself to read or write members from this
62  * structure.  */
63 struct lz_sarray {
64         /* Allocated window size for the match-finder.
65          *
66          * Note: this match-finder does not store the window itself, as the
67          * suffix array (@SA) and associated arrays (@ISA, @LCP, @salink) are
68          * sufficient to find matches.  This number is the maximum length of
69          * those arrays, or also the maximum window (block) size that can be
70          * passed to lz_sarray_load_window().  */
71         lz_sarray_pos_t max_window_size;
72
73         /* Minimum length of matches to return.  */
74         lz_sarray_len_t min_match_len;
75
76         /* Maximum length of matches to return.  */
77         lz_sarray_len_t max_match_len;
78
79         /* Maximum matches to consider at each position (max search depth).  */
80         u32 max_matches_to_consider;
81
82         /* Maximum number of matches to return at each position.  */
83         u32 max_matches_to_return;
84
85         /* Current position in the window.  */
86         lz_sarray_pos_t cur_pos;
87
88         /* Current window size.  */
89         lz_sarray_pos_t window_size;
90
91         /* Suffix array for the current window.
92          * This is a mapping from suffix rank to suffix position.  */
93         lz_sarray_pos_t *SA;
94
95         /* Inverse suffix array for the current window.
96          * This is a mapping from suffix position to suffix rank.
97          * If 0 <= r < window_size, then ISA[SA[r]] == r.  */
98         lz_sarray_pos_t *ISA;
99
100         /* Suffix array links.
101          *
102          * During a linear scan of the input string to find matches, this array
103          * used to keep track of which rank suffixes in the suffix array appear
104          * before the current position.  Instead of searching in the original
105          * suffix array, scans for matches at a given position traverse a linked
106          * list containing only suffixes that appear before that position.  */
107         struct salink *salink;
108 };
109
110 /* Suffix array link; one of these exists for each position in the suffix array.
111  */
112 struct salink {
113         /* Rank of highest ranked suffix that has rank lower than the suffix
114          * corresponding to this structure and either has a lower position
115          * (initially) or has a position lower than the highest position at
116          * which matches have been searched for so far, or LZ_SARRAY_POS_MAX if
117          * there is no such suffix.
118          *
119          * Think of this as a pointer to the closest position in the suffix
120          * array to the left that corresponds to a suffix that begins at a
121          * position in the current dictionary (i.e. before the current position
122          * in the window).  */
123         lz_sarray_pos_t prev;
124
125         /* Rank of lowest ranked suffix that has rank greater than the suffix
126          * corresponding to this structure and either has a lower position
127          * (intially) or has a position lower than the highest position at which
128          * matches have been searched for so far, or LZ_SARRAY_POS_MAX if there
129          * is no such suffix.
130
131          * Think of this as a pointer to the closest position in the suffix
132          * array to the right that corresponds to a suffix that begins at a
133          * position in the current dictionary (i.e. before the current position
134          * in the window).  */
135         lz_sarray_pos_t next;
136
137         /* Length of longest common prefix between the suffix corresponding to
138          * this structure and the suffix with rank @prev, or 0 if @prev is
139          * LZ_SARRAY_POS_MAX.  Capped to the maximum match length.  */
140         lz_sarray_len_t lcpprev;
141
142         /* Length of longest common prefix between the suffix corresponding to
143          * this structure and the suffix with rank @next, or 0 if @next is
144          * LZ_SARRAY_POS_MAX.  Capped to the maximum match length.  */
145         lz_sarray_len_t lcpnext;
146 };
147
148 /*-----------------------------------*/
149 /* Functions defined in lz_sarray.c  */
150 /*-----------------------------------*/
151
152 extern bool
153 lz_sarray_init(struct lz_sarray *mf,
154                lz_sarray_pos_t max_window_size,
155                lz_sarray_len_t min_match_len,
156                lz_sarray_len_t max_match_len,
157                u32 max_matches_to_consider,
158                u32 max_matches_to_return);
159
160 extern u64
161 lz_sarray_get_needed_memory(lz_sarray_pos_t max_window_size);
162
163 extern void
164 lz_sarray_destroy(struct lz_sarray *mf);
165
166 extern void
167 lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], lz_sarray_pos_t n);
168
169 /*-------------------*/
170 /* Inline functions  */
171 /*-------------------*/
172
173 static _always_inline_attribute lz_sarray_pos_t
174 lz_sarray_get_pos(const struct lz_sarray *mf)
175 {
176         return mf->cur_pos;
177 }
178
179 /* Advance the suffix array match-finder to the next position.  */
180 static _always_inline_attribute void
181 lz_sarray_update_salink(const lz_sarray_pos_t r, struct salink link[])
182 {
183         /* next = rank of LOWEST ranked suffix that is ranked HIGHER than the
184          * current suffix AND has a LOWER position, or LZ_SARRAY_POS_MAX if none
185          * exists.  */
186         const lz_sarray_pos_t next = link[r].next;
187
188         /* prev = rank of HIGHEST ranked suffix that is ranked LOWER than the
189          * current suffix AND has a LOWER position, or LZ_SARRAY_POS_MAX if none
190          * exists.  */
191         const lz_sarray_pos_t prev = link[r].prev;
192
193         /* Link the suffix at the current position into the linked list that
194          * contains all suffixes referenced by the suffix array that appear at
195          * or before the current position, sorted by rank.  */
196         if (next != LZ_SARRAY_POS_MAX) {
197                 link[next].prev = r;
198                 link[next].lcpprev = link[r].lcpnext;
199         }
200
201         if (prev != LZ_SARRAY_POS_MAX) {
202                 link[prev].next = r;
203                 link[prev].lcpnext = link[r].lcpprev;
204         }
205 }
206
207 /* Skip the current position in the suffix array match-finder.  */
208 static _always_inline_attribute void
209 lz_sarray_skip_position(struct lz_sarray *mf)
210 {
211         LZ_ASSERT(mf->cur_pos < mf->window_size);
212         lz_sarray_update_salink(mf->ISA[mf->cur_pos++], mf->salink);
213 }
214
215 /*
216  * Use the suffix array match-finder to retrieve a list of matches at the
217  * current position.
218  *
219  * Returns the number of matches written into @matches.  The matches are
220  * returned in decreasing order by length, and each will be of unique length
221  * between the minimum and maximum match lengths (inclusively) passed to
222  * lz_sarray_init().  Up to @max_matches_to_return (passed to lz_sarray_init())
223  * matches will be returned.
224  *
225  * @eval_match_cost is a function for evaluating the cost of a match when
226  * deciding which ones to return.  It needs to be fast, and need not be exact;
227  * an implementation might simply rank matches by their offset, for example,
228  * although implementations may choose to take into account additional
229  * information such as repeat offsets.
230  */
231 static _always_inline_attribute u32
232 lz_sarray_get_matches(struct lz_sarray *mf,
233                       struct raw_match matches[],
234                       lz_sarray_cost_t (*eval_match_cost)
235                                 (lz_sarray_pos_t length,
236                                  lz_sarray_pos_t offset,
237                                  const void *ctx),
238                       const void *eval_match_cost_ctx)
239 {
240         LZ_ASSERT(mf->cur_pos < mf->window_size);
241         const lz_sarray_pos_t i = mf->cur_pos++;
242
243         const lz_sarray_pos_t * const restrict SA = mf->SA;
244         const lz_sarray_pos_t * const restrict ISA = mf->ISA;
245         struct salink * const restrict link = mf->salink;
246         const lz_sarray_pos_t min_match_len = mf->min_match_len;
247         const u32 max_matches_to_consider = mf->max_matches_to_consider;
248         const u32 max_matches_to_return = mf->max_matches_to_return;
249
250         /* r = Rank of the suffix at the current position.  */
251         const lz_sarray_pos_t r = ISA[i];
252
253         /* Prepare for searching the current position.  */
254         lz_sarray_update_salink(r, link);
255
256         /* L = rank of next suffix to the left;
257          * R = rank of next suffix to the right;
258          * lenL = length of match between current position and the suffix with rank L;
259          * lenR = length of match between current position and the suffix with rank R.
260          *
261          * This is left and right relative to the rank of the current suffix.
262          * Since the suffixes in the suffix array are sorted, the longest
263          * matches are immediately to the left and right (using the linked list
264          * to ignore all suffixes that occur later in the window).  The match
265          * length decreases the farther left and right we go.  We shall keep the
266          * length on both sides in sync in order to choose the lowest-cost match
267          * of each length.
268          */
269         lz_sarray_pos_t L = link[r].prev;
270         lz_sarray_pos_t R = link[r].next;
271         lz_sarray_pos_t lenL = link[r].lcpprev;
272         lz_sarray_pos_t lenR = link[r].lcpnext;
273
274         /* nmatches = number of matches found so far.  */
275         u32 nmatches = 0;
276
277         /* best_cost = cost of lowest-cost match found so far.
278          *
279          * We keep track of this so that we can ignore shorter matches that do
280          * not have lower costs than longer matches already found.  */
281         lz_sarray_cost_t best_cost = LZ_SARRAY_INFINITE_COST;
282
283         /* count_remaining = maximum number of possible matches remaining to be
284          * considered.  */
285         u32 count_remaining = max_matches_to_consider;
286
287         /* pending = match currently being considered for a specific length.  */
288         struct raw_match pending;
289         lz_sarray_cost_t pending_cost;
290
291         while (lenL >= min_match_len || lenR >= min_match_len)
292         {
293                 pending.len = lenL;
294                 pending_cost = LZ_SARRAY_INFINITE_COST;
295                 lz_sarray_cost_t cost;
296
297                 /* Extend left.  */
298                 if (lenL >= min_match_len && lenL >= lenR) {
299                         for (;;) {
300
301                                 if (--count_remaining == 0)
302                                         goto out_save_pending;
303
304                                 lz_sarray_pos_t offset = i - SA[L];
305
306                                 /* Save match if it has smaller cost.  */
307                                 cost = (*eval_match_cost)(lenL, offset,
308                                                           eval_match_cost_ctx);
309                                 if (cost < pending_cost) {
310                                         pending.offset = offset;
311                                         pending_cost = cost;
312                                 }
313
314                                 if (link[L].lcpprev < lenL) {
315                                         /* Match length decreased.  */
316
317                                         lenL = link[L].lcpprev;
318
319                                         /* Save the pending match unless the
320                                          * right side still may have matches of
321                                          * this length to be scanned, or if a
322                                          * previous (longer) match had lower
323                                          * cost.  */
324                                         if (pending.len > lenR) {
325                                                 if (pending_cost < best_cost) {
326                                                         best_cost = pending_cost;
327                                                         matches[nmatches++] = pending;
328                                                         if (nmatches == max_matches_to_return)
329                                                                 return nmatches;
330                                                 }
331                                                 pending.len = lenL;
332                                                 pending_cost = LZ_SARRAY_INFINITE_COST;
333                                         }
334                                         if (lenL < min_match_len || lenL < lenR)
335                                                 break;
336                                 }
337                                 L = link[L].prev;
338                         }
339                 }
340
341                 pending.len = lenR;
342
343                 /* Extend right.  */
344                 if (lenR >= min_match_len && lenR > lenL) {
345                         for (;;) {
346
347                                 if (--count_remaining == 0)
348                                         goto out_save_pending;
349
350                                 lz_sarray_pos_t offset = i - SA[R];
351
352                                 /* Save match if it has smaller cost.  */
353                                 cost = (*eval_match_cost)(lenR,
354                                                           offset,
355                                                           eval_match_cost_ctx);
356                                 if (cost < pending_cost) {
357                                         pending.offset = offset;
358                                         pending_cost = cost;
359                                 }
360
361                                 if (link[R].lcpnext < lenR) {
362                                         /* Match length decreased.  */
363
364                                         lenR = link[R].lcpnext;
365
366                                         /* Save the pending match unless a
367                                          * previous (longer) match had lower
368                                          * cost.  */
369                                         if (pending_cost < best_cost) {
370                                                 matches[nmatches++] = pending;
371                                                 best_cost = pending_cost;
372                                                 if (nmatches == max_matches_to_return)
373                                                         return nmatches;
374                                         }
375
376                                         if (lenR < min_match_len || lenR <= lenL)
377                                                 break;
378
379                                         pending.len = lenR;
380                                         pending_cost = LZ_SARRAY_INFINITE_COST;
381                                 }
382                                 R = link[R].next;
383                         }
384                 }
385         }
386         goto out;
387
388 out_save_pending:
389         if (pending_cost != LZ_SARRAY_INFINITE_COST)
390                 matches[nmatches++] = pending;
391
392 out:
393         return nmatches;
394 }
395
396 #endif /* _WIMLIB_LZ_SARRAY_H */