0c7007b704b855bf7799aae044f6ce4fbf1b49e1
[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 /* Type of distances in suffix array links.  A larger type would allow skipping
55  * irrelevant suffixes more quickly, which is especially helpful towards the
56  * start of the window.  However, even a single byte allows skipping 255 at a
57  * time, which where it matters is already a big improvement over the
58  * alternative of searching the suffixes consecutively.  */
59 typedef u8 lz_sarray_delta_t;
60
61 #define LZ_SARRAY_LEN_MAX       ((lz_sarray_len_t)~0UL)
62 #define LZ_SARRAY_POS_MAX       ((lz_sarray_pos_t)~0UL)
63 #define LZ_SARRAY_DELTA_MAX     ((lz_sarray_delta_t)~0UL)
64 #define LZ_SARRAY_INFINITE_COST ((lz_sarray_cost_t)~0UL)
65
66 /* State of the suffix array LZ (Lempel-Ziv) match-finder.
67  *
68  * This is defined here for benefit of the inlined code.  It's not intended for
69  * code outside the match-finder itself to read or write members from this
70  * structure.  */
71 struct lz_sarray {
72         /* Allocated window size for the match-finder.
73          *
74          * Note: this match-finder does not store the window itself, as the
75          * suffix array (@SA) and associated arrays (@ISA, @LCP, @salink) are
76          * sufficient to find matches.  This number is the maximum length of
77          * those arrays, or also the maximum window (block) size that can be
78          * passed to lz_sarray_load_window().  */
79         lz_sarray_pos_t max_window_size;
80
81         /* Minimum length of matches to return.  */
82         lz_sarray_len_t min_match_len;
83
84         /* Maximum length of matches to return.  */
85         lz_sarray_len_t max_match_len;
86
87         /* Maximum matches to consider at each position (max search depth).  */
88         u32 max_matches_to_consider;
89
90         /* Maximum number of matches to return at each position.  */
91         u32 max_matches_to_return;
92
93         /* Current position in the window.  */
94         lz_sarray_pos_t cur_pos;
95
96         /* Current window size.  */
97         lz_sarray_pos_t window_size;
98
99         /* Suffix array for the current window.
100          * This is a mapping from suffix rank to suffix position.  */
101         lz_sarray_pos_t *SA;
102
103         /* Inverse suffix array for the current window.
104          * This is a mapping from suffix position to suffix rank.
105          * If 0 <= r < window_size, then ISA[SA[r]] == r.  */
106         lz_sarray_pos_t *ISA;
107
108         /* Suffix array links.
109          *
110          * During a linear scan of the input string to find matches, this array
111          * used to keep track of which rank suffixes in the suffix array appear
112          * before the current position.  Instead of searching in the original
113          * suffix array, scans for matches at a given position traverse a linked
114          * list containing (usually) only suffixes that appear before that
115          * position.  */
116         struct salink *salink;
117 };
118
119 /* Suffix array link.  An array of these structures, one per suffix rank, is
120  * used as a replacement for the raw LCP (Longest Common Prefix) array to allow
121  * skipping over suffixes that appear later in the window and hence cannot be
122  * used as LZ77 matches.  */
123 struct salink {
124         union {
125                 /* Temporary fields used while this structure is being
126                  * initialized.
127                  *
128                  * Note: we want the entire `struct salink' to be only 6 bytes,
129                  * even though this makes "next_initial" unaligned.  */
130                 struct {
131                         lz_sarray_pos_t next_initial;
132                         lz_sarray_len_t lcpnext_initial;
133                 } _packed_attribute;
134
135                 struct {
136                         /* Intially, the length, in bytes, of the longest common
137                          * prefix (LCP) between the suffix having this rank and
138                          * the suffix with the the smallest larger rank that
139                          * starts earlier in the window than the suffix having
140                          * this rank.  If no such suffix exists, this will be 0.
141                          *
142                          * Later, during match-finding, after the corresponding
143                          * suffix has entered the LZ77 dictionary, this value
144                          * may be updated by lz_sarray_update_salink() to refer
145                          * instead to a lexicographically closer (but still
146                          * larger) suffix that begins at a later position that
147                          * has entered the LZ77 dictionary.  */
148                         lz_sarray_len_t   lcpnext;
149
150                         /* Initially, the length, in bytes, of the longest
151                          * common prefix (LCP) between the suffix having this
152                          * rank and the suffix with the the largest smaller rank
153                          * that starts earlier in the window than the suffix
154                          * having this rank.  If no such suffix exists, this
155                          * will be 0.
156                          *
157                          * Later, during match-finding, after the corresponding
158                          * suffix has entered the LZ77 dictionary, this value
159                          * may be updated by lz_sarray_update_salink() to refer
160                          * instead to a lexicographically closer (but still
161                          * smaller) suffix that begins at a later position that
162                          * has entered the LZ77 dictionary.  */
163                         lz_sarray_len_t   lcpprev;
164
165                         /* Distance to the suffix referred to in the description
166                          * of "lcpnext" above, but capped to a maximum value to
167                          * save memory; or, 0 if no such suffix exists.  If the
168                          * true distance was truncated, this will give the
169                          * distance to the rank of a suffix that is
170                          * lexicographically closer to the current suffix than
171                          * the desired suffix, but appears *later* in the window
172                          * and hence cannot be used as the basis for a LZ77
173                          * match.  */
174                         lz_sarray_delta_t dist_to_next;
175
176                         /* Distance to the suffix referred to in the description
177                          * of "lcpprev" above, but capped to a maximum value to
178                          * save memory; or, 0 if no such suffix exists.  If the
179                          * true distance was truncated, this will give the
180                          * distance to the rank of a suffix that is
181                          * lexicographically closer to the current suffix than
182                          * the desired suffix, but appears *later* in the window
183                          * and hence cannot be used as the basis for a LZ77
184                          * match.  */
185                         lz_sarray_delta_t dist_to_prev;
186                 };
187         };
188 };
189
190
191 /*-----------------------------------*/
192 /* Functions defined in lz_sarray.c  */
193 /*-----------------------------------*/
194
195 extern bool
196 lz_sarray_init(struct lz_sarray *mf,
197                lz_sarray_pos_t max_window_size,
198                lz_sarray_len_t min_match_len,
199                lz_sarray_len_t max_match_len,
200                u32 max_matches_to_consider,
201                u32 max_matches_to_return);
202
203 extern u64
204 lz_sarray_get_needed_memory(lz_sarray_pos_t max_window_size);
205
206 extern void
207 lz_sarray_destroy(struct lz_sarray *mf);
208
209 extern void
210 lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], lz_sarray_pos_t n);
211
212 /*-------------------*/
213 /* Inline functions  */
214 /*-------------------*/
215
216 static _always_inline_attribute lz_sarray_pos_t
217 lz_sarray_get_pos(const struct lz_sarray *mf)
218 {
219         return mf->cur_pos;
220 }
221
222 /* Advance the suffix array match-finder to the next position.  */
223 static _always_inline_attribute void
224 lz_sarray_update_salink(const lz_sarray_pos_t r, struct salink link[])
225 {
226         const lz_sarray_pos_t next = r + link[r].dist_to_next;
227         const lz_sarray_pos_t prev = r - link[r].dist_to_prev;
228
229         if (next != r && link[r].dist_to_next < link[next].dist_to_prev) {
230                 link[next].dist_to_prev = link[r].dist_to_next;
231                 link[next].lcpprev = link[r].lcpnext;
232         }
233
234         if (prev != r && link[r].dist_to_prev < link[prev].dist_to_next) {
235                 link[prev].dist_to_next = link[r].dist_to_prev;
236                 link[prev].lcpnext = link[r].lcpprev;
237         }
238 }
239
240 /* Skip the current position in the suffix array match-finder.  */
241 static _always_inline_attribute void
242 lz_sarray_skip_position(struct lz_sarray *mf)
243 {
244         LZ_ASSERT(mf->cur_pos < mf->window_size);
245         lz_sarray_update_salink(mf->ISA[mf->cur_pos++], mf->salink);
246 }
247
248 /*
249  * Use the suffix array match-finder to retrieve a list of matches at the
250  * current position.
251  *
252  * Returns the number of matches written into @matches.  The matches are
253  * returned in decreasing order by length, and each will be of unique length
254  * between the minimum and maximum match lengths (inclusively) passed to
255  * lz_sarray_init().  Up to @max_matches_to_return (passed to lz_sarray_init())
256  * matches will be returned.
257  *
258  * @eval_match_cost is a function for evaluating the cost of a match when
259  * deciding which ones to return.  It needs to be fast, and need not be exact;
260  * an implementation might simply rank matches by their offset, for example,
261  * although implementations may choose to take into account additional
262  * information such as repeat offsets.
263  */
264 static _always_inline_attribute u32
265 lz_sarray_get_matches(struct lz_sarray *mf,
266                       struct raw_match matches[],
267                       lz_sarray_cost_t (*eval_match_cost)
268                                 (lz_sarray_pos_t length,
269                                  lz_sarray_pos_t offset,
270                                  const void *ctx),
271                       const void *eval_match_cost_ctx)
272 {
273         LZ_ASSERT(mf->cur_pos < mf->window_size);
274         const lz_sarray_pos_t i = mf->cur_pos++;
275
276         const lz_sarray_pos_t * const restrict SA = mf->SA;
277         const lz_sarray_pos_t * const restrict ISA = mf->ISA;
278         struct salink * const restrict link = mf->salink;
279         const u32 max_matches_to_consider = mf->max_matches_to_consider;
280         const u32 max_matches_to_return = mf->max_matches_to_return;
281
282         /* r = Rank of the suffix at the current position.  */
283         const lz_sarray_pos_t r = ISA[i];
284
285         /* Prepare for searching the current position.  */
286         lz_sarray_update_salink(r, link);
287
288         /* L = rank of next suffix to the left;
289          * R = rank of next suffix to the right;
290          * lenL = length of match between current position and the suffix with rank L;
291          * lenR = length of match between current position and the suffix with rank R.
292          *
293          * This is left and right relative to the rank of the current suffix.
294          * Since the suffixes in the suffix array are sorted, the longest
295          * matches are immediately to the left and right (using the linked list
296          * to ignore all suffixes that occur later in the window).  The match
297          * length decreases the farther left and right we go.  We shall keep the
298          * length on both sides in sync in order to choose the lowest-cost match
299          * of each length.
300          */
301         lz_sarray_pos_t L = r - link[r].dist_to_prev;
302         lz_sarray_pos_t R = r + link[r].dist_to_next;
303         lz_sarray_pos_t lenL = link[r].lcpprev;
304         lz_sarray_pos_t lenR = link[r].lcpnext;
305
306         /* nmatches = number of matches found so far.  */
307         u32 nmatches = 0;
308
309         /* best_cost = cost of lowest-cost match found so far.
310          *
311          * Shorter matches that do not have a lower cost than this are
312          * discarded, since presumably it would be cheaper to output the bytes
313          * from the longer match instead.  */
314         lz_sarray_cost_t best_cost = LZ_SARRAY_INFINITE_COST;
315
316         /* count_remaining = maximum number of possible matches remaining to be
317          * considered.  */
318         u32 count_remaining = max_matches_to_consider;
319
320         /* pending_offset = offset of lowest-cost match found for the current
321          * length, or 0 if none found yet.  */
322         lz_sarray_pos_t pending_offset = 0;
323
324         /* Note: some 'goto' statements are used in the remainder of this
325          * function to remove unnecessary checks and create branches that the
326          * CPU may predict better.  (This function is performance critical.)  */
327
328         if (lenL != 0 && lenL >= lenR)
329                 goto extend_left;
330         else if (lenR != 0)
331                 goto extend_right;
332         else
333                 return 0;
334
335 extend_left:
336         /* Search suffixes on the left until the match length has decreased
337          * below the next match length on the right or to below the minimum
338          * match length.  */
339         for (;;) {
340                 lz_sarray_pos_t offset;
341                 lz_sarray_cost_t cost;
342                 lz_sarray_pos_t old_L;
343                 lz_sarray_pos_t old_lenL;
344
345                 /* Check for hard cutoff on amount of work done.  */
346                 if (count_remaining-- == 0) {
347                         if (pending_offset != 0) {
348                                 /* Save pending match.  */
349                                 matches[nmatches++] = (struct raw_match){
350                                         .len = lenL,
351                                         .offset = pending_offset,
352                                 };
353                         }
354                         return nmatches;
355                 }
356
357                 if (SA[L] < i) {
358                         /* Suffix is in LZ77 dictionary.  (Check was needed
359                          * because the salink array caps distances to save
360                          * memory.)  */
361
362                         offset = i - SA[L];
363
364                         /* Save match offset if it results in lower cost.  */
365                         cost = (*eval_match_cost)(lenL, offset,
366                                                   eval_match_cost_ctx);
367                         if (cost < best_cost) {
368                                 best_cost = cost;
369                                 pending_offset = offset;
370                         }
371                 }
372
373                 /* Advance left to previous suffix.  */
374
375                 old_L = L;
376                 old_lenL = lenL;
377
378                 L -= link[L].dist_to_prev;
379
380                 if (link[old_L].lcpprev < old_lenL) {
381                         /* Match length decreased.  */
382
383                         lenL = link[old_L].lcpprev;
384
385                         if (old_lenL > lenR) {
386                                 /* Neither the right side nor the left size has
387                                  * any more matches of length @old_lenL.  If a
388                                  * pending match exists, save it.  */
389                                 if (pending_offset != 0) {
390                                         matches[nmatches++] = (struct raw_match){
391                                                 .len = old_lenL,
392                                                 .offset = pending_offset,
393                                         };
394                                         if (nmatches == max_matches_to_return)
395                                                 return nmatches;
396
397                                         pending_offset = 0;
398                                 }
399
400                                 if (lenL >= lenR) {
401                                         /* New match length on left is still at
402                                          * least as large as the next match
403                                          * length on the right:  Keep extending
404                                          * left, unless the minimum match length
405                                          * would be underrun.  */
406                                         if (lenL == 0)
407                                                 return nmatches;
408                                         goto extend_left;
409                                 }
410                         }
411
412                         /* Here we have lenL < lenR.  Extend right, unless the
413                          * minimum match length would be underrun.  */
414                         if (lenR == 0)
415                                 return nmatches;
416                         goto extend_right;
417                 }
418         }
419
420 extend_right:
421         /* Search suffixes on the right until the match length has decreased to
422          * the next match length on the left or to below the minimum match
423          * length.  */
424         for (;;) {
425                 lz_sarray_pos_t offset;
426                 lz_sarray_cost_t cost;
427                 lz_sarray_pos_t old_R;
428                 lz_sarray_pos_t old_lenR;
429
430                 /* Check for hard cutoff on amount of work done.  */
431                 if (count_remaining-- == 0) {
432                         if (pending_offset != 0) {
433                                 /* Save pending match.  */
434                                 matches[nmatches++] = (struct raw_match){
435                                         .len = lenR,
436                                         .offset = pending_offset,
437                                 };
438                         }
439                         return nmatches;
440                 }
441
442                 if (SA[R] < i) {
443                         /* Suffix is in LZ77 dictionary.  (Check was needed
444                          * because the salink array caps distances to save
445                          * memory.)  */
446
447                         offset = i - SA[R];
448
449                         /* Save match offset if it results in lower cost.  */
450                         cost = (*eval_match_cost)(lenR,
451                                                   offset,
452                                                   eval_match_cost_ctx);
453                         if (cost < best_cost) {
454                                 best_cost = cost;
455                                 pending_offset = offset;
456                         }
457                 }
458
459                 /* Advance right to next suffix.  */
460
461                 old_R = R;
462                 old_lenR = lenR;
463
464                 R += link[R].dist_to_next;
465
466                 if (link[old_R].lcpnext < lenR) {
467                         /* Match length decreased.  */
468
469                         lenR = link[old_R].lcpnext;
470
471                         /* Neither the right side nor the left size has any more
472                          * matches of length @old_lenR.  If a pending match
473                          * exists, save it.  */
474                         if (pending_offset != 0) {
475                                 matches[nmatches++] = (struct raw_match){
476                                         .len = old_lenR,
477                                         .offset = pending_offset,
478                                 };
479                                 if (nmatches == max_matches_to_return)
480                                         return nmatches;
481
482                                 pending_offset = 0;
483                         }
484
485                         if (lenL >= lenR) {
486                                 /* lenL >= lenR:  Extend left, unless the
487                                  * minimum match length would be underrun, in
488                                  * which case we are done.  */
489                                 if (lenL == 0)
490                                         return nmatches;
491
492                                 goto extend_left;
493                         }
494                         /* lenR > lenL:  Keep extending right.
495                          * (No check for whether the minimum match length has
496                          * been underrun is needed, provided that such lengths
497                          * are marked as 0.)  */
498                 }
499         }
500 }
501
502 #endif /* _WIMLIB_LZ_SARRAY_H */