lz_sarray: Performance and memory usage optimizations
[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.
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.
155                          *
156                          * Later, during match-finding, after the corresponding
157                          * suffix has entered the LZ77 dictionary, this value
158                          * may be updated by lz_sarray_update_salink() to refer
159                          * instead to a lexicographically closer (but still
160                          * smaller) suffix that begins at a later position that
161                          * has entered the LZ77 dictionary.  */
162                         lz_sarray_len_t   lcpprev;
163
164                         /* Distance to the suffix referred to in the description
165                          * of "lcpnext" above, but capped to a maximum value to
166                          * save memory.  If the true distance was truncated,
167                          * this will give the distance to the rank of a suffix
168                          * that is lexicographically closer to the current
169                          * suffix than the desired suffix, but appears *later*
170                          * in the window and hence cannot be used as the basis
171                          * for a LZ77 match.  */
172                         lz_sarray_delta_t dist_to_next;
173
174                         /* Distance to the suffix referred to in the description
175                          * of "lcpprev" above, but capped to a maximum value to
176                          * save memory.  If the true distance was truncated,
177                          * this will give the distance to the rank of a suffix
178                          * that is lexicographically closer to the current
179                          * suffix than the desired suffix, but appears *later*
180                          * in the window and hence cannot be used as the basis
181                          * for a LZ77 match.  */
182                         lz_sarray_delta_t dist_to_prev;
183                 };
184         };
185 };
186
187
188 /*-----------------------------------*/
189 /* Functions defined in lz_sarray.c  */
190 /*-----------------------------------*/
191
192 extern bool
193 lz_sarray_init(struct lz_sarray *mf,
194                lz_sarray_pos_t max_window_size,
195                lz_sarray_len_t min_match_len,
196                lz_sarray_len_t max_match_len,
197                u32 max_matches_to_consider,
198                u32 max_matches_to_return);
199
200 extern u64
201 lz_sarray_get_needed_memory(lz_sarray_pos_t max_window_size);
202
203 extern void
204 lz_sarray_destroy(struct lz_sarray *mf);
205
206 extern void
207 lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], lz_sarray_pos_t n);
208
209 /*-------------------*/
210 /* Inline functions  */
211 /*-------------------*/
212
213 static _always_inline_attribute lz_sarray_pos_t
214 lz_sarray_get_pos(const struct lz_sarray *mf)
215 {
216         return mf->cur_pos;
217 }
218
219 /* Advance the suffix array match-finder to the next position.  */
220 static _always_inline_attribute void
221 lz_sarray_update_salink(const lz_sarray_pos_t r, struct salink link[])
222 {
223         const lz_sarray_pos_t next = r + link[r].dist_to_next;
224         const lz_sarray_pos_t prev = r - link[r].dist_to_prev;
225
226         if (next != r && link[r].dist_to_next < link[next].dist_to_prev) {
227                 link[next].dist_to_prev = link[r].dist_to_next;
228                 link[next].lcpprev = link[r].lcpnext;
229         }
230
231         if (prev != r && link[r].dist_to_prev < link[prev].dist_to_next) {
232                 link[prev].dist_to_next = link[r].dist_to_prev;
233                 link[prev].lcpnext = link[r].lcpprev;
234         }
235 }
236
237 /* Skip the current position in the suffix array match-finder.  */
238 static _always_inline_attribute void
239 lz_sarray_skip_position(struct lz_sarray *mf)
240 {
241         LZ_ASSERT(mf->cur_pos < mf->window_size);
242         lz_sarray_update_salink(mf->ISA[mf->cur_pos++], mf->salink);
243 }
244
245 /*
246  * Use the suffix array match-finder to retrieve a list of matches at the
247  * current position.
248  *
249  * Returns the number of matches written into @matches.  The matches are
250  * returned in decreasing order by length, and each will be of unique length
251  * between the minimum and maximum match lengths (inclusively) passed to
252  * lz_sarray_init().  Up to @max_matches_to_return (passed to lz_sarray_init())
253  * matches will be returned.
254  *
255  * @eval_match_cost is a function for evaluating the cost of a match when
256  * deciding which ones to return.  It needs to be fast, and need not be exact;
257  * an implementation might simply rank matches by their offset, for example,
258  * although implementations may choose to take into account additional
259  * information such as repeat offsets.
260  */
261 static _always_inline_attribute u32
262 lz_sarray_get_matches(struct lz_sarray *mf,
263                       struct raw_match matches[],
264                       lz_sarray_cost_t (*eval_match_cost)
265                                 (lz_sarray_pos_t length,
266                                  lz_sarray_pos_t offset,
267                                  const void *ctx),
268                       const void *eval_match_cost_ctx)
269 {
270         LZ_ASSERT(mf->cur_pos < mf->window_size);
271         const lz_sarray_pos_t i = mf->cur_pos++;
272
273         const lz_sarray_pos_t * const restrict SA = mf->SA;
274         const lz_sarray_pos_t * const restrict ISA = mf->ISA;
275         struct salink * const restrict link = mf->salink;
276         const u32 max_matches_to_consider = mf->max_matches_to_consider;
277         const u32 max_matches_to_return = mf->max_matches_to_return;
278
279         /* r = Rank of the suffix at the current position.  */
280         const lz_sarray_pos_t r = ISA[i];
281
282         /* Prepare for searching the current position.  */
283         lz_sarray_update_salink(r, link);
284
285         /* L = rank of next suffix to the left;
286          * R = rank of next suffix to the right;
287          * lenL = length of match between current position and the suffix with rank L;
288          * lenR = length of match between current position and the suffix with rank R.
289          *
290          * This is left and right relative to the rank of the current suffix.
291          * Since the suffixes in the suffix array are sorted, the longest
292          * matches are immediately to the left and right (using the linked list
293          * to ignore all suffixes that occur later in the window).  The match
294          * length decreases the farther left and right we go.  We shall keep the
295          * length on both sides in sync in order to choose the lowest-cost match
296          * of each length.
297          */
298         lz_sarray_pos_t L = r - link[r].dist_to_prev;
299         lz_sarray_pos_t R = r + link[r].dist_to_next;
300         lz_sarray_pos_t lenL = link[r].lcpprev;
301         lz_sarray_pos_t lenR = link[r].lcpnext;
302
303         /* nmatches = number of matches found so far.  */
304         u32 nmatches = 0;
305
306         /* best_cost = cost of lowest-cost match found so far.
307          *
308          * Shorter matches that do not have a lower cost than this are
309          * discarded, since presumably it would be cheaper to output the bytes
310          * from the longer match instead.  */
311         lz_sarray_cost_t best_cost = LZ_SARRAY_INFINITE_COST;
312
313         /* count_remaining = maximum number of possible matches remaining to be
314          * considered.  */
315         u32 count_remaining = max_matches_to_consider;
316
317         /* pending_offset = offset of lowest-cost match found for the current
318          * length, or 0 if no match has been found yet.  */
319         lz_sarray_pos_t pending_offset = 0;
320
321         /* Note: some 'goto' statements are used in the remainder of this
322          * function to remove unnecessary checks and create branches that the
323          * CPU may predict better.  (This function is performance critical.)  */
324
325         if (lenL != 0 && lenL >= lenR)
326                 goto extend_left;
327         else if (lenR != 0)
328                 goto extend_right;
329         else
330                 return 0;
331
332 extend_left:
333         /* Search suffixes on the left until the match length has decreased
334          * below the next match length on the right or to below the minimum
335          * match length.  */
336         for (;;) {
337                 lz_sarray_pos_t offset;
338                 lz_sarray_cost_t cost;
339                 lz_sarray_pos_t old_L;
340                 lz_sarray_pos_t old_lenL;
341
342                 /* Check for hard cutoff on amount of work done.  */
343                 if (count_remaining-- == 0) {
344                         if (pending_offset != 0) {
345                                 /* Save pending match.  */
346                                 matches[nmatches++] = (struct raw_match){
347                                         .len = lenL,
348                                         .offset = pending_offset,
349                                 };
350                         }
351                         return nmatches;
352                 }
353
354                 if (SA[L] < i) {
355                         /* Suffix is in LZ77 dictionary.  (Check was needed
356                          * because the salink array caps distances to save
357                          * memory.)  */
358
359                         offset = i - SA[L];
360
361                         /* Save match offset if it results in lower cost.  */
362                         cost = (*eval_match_cost)(lenL, offset,
363                                                   eval_match_cost_ctx);
364                         if (cost < best_cost) {
365                                 best_cost = cost;
366                                 pending_offset = offset;
367                         }
368                 }
369
370                 /* Advance left to next suffix.  */
371
372                 old_L = L;
373                 old_lenL = lenL;
374
375                 L -= link[L].dist_to_prev;
376
377                 if (link[old_L].lcpprev < old_lenL) {
378                         /* Match length decreased.  */
379
380                         lenL = link[old_L].lcpprev;
381
382                         if (old_lenL > lenR) {
383                                 /* Neither the right side nor the left size has
384                                  * any more matches of length @old_lenL.  If a
385                                  * pending match exists, save it.  */
386                                 if (pending_offset != 0) {
387                                         matches[nmatches++] = (struct raw_match){
388                                                 .len = old_lenL,
389                                                 .offset = pending_offset,
390                                         };
391                                         if (nmatches == max_matches_to_return)
392                                                 return nmatches;
393
394                                         pending_offset = 0;
395                                 }
396
397                                 if (lenL >= lenR) {
398                                         /* New match length on left is still at
399                                          * least as large as the next match
400                                          * length on the right:  Keep extending
401                                          * left, unless the minimum match length
402                                          * would be underrun.  */
403                                         if (lenL == 0)
404                                                 return nmatches;
405                                         goto extend_left;
406                                 }
407                         }
408
409                         /* Here we have lenL < lenR.  Extend right, unless the
410                          * minimum match length would be underrun.  */
411                         if (lenR == 0)
412                                 return nmatches;
413                         goto extend_right;
414                 }
415         }
416
417 extend_right:
418         /* Search suffixes on the right until the match length has decreased to
419          * the next match length on the left or to below the minimum match
420          * length.  */
421         for (;;) {
422                 lz_sarray_pos_t offset;
423                 lz_sarray_cost_t cost;
424                 lz_sarray_pos_t old_R;
425                 lz_sarray_pos_t old_lenR;
426
427                 /* Check for hard cutoff on amount of work done.  */
428                 if (count_remaining-- == 0) {
429                         if (pending_offset != 0) {
430                                 /* Save pending match.  */
431                                 matches[nmatches++] = (struct raw_match){
432                                         .len = lenR,
433                                         .offset = pending_offset,
434                                 };
435                         }
436                         return nmatches;
437                 }
438
439                 if (SA[R] < i) {
440                         /* Suffix is in LZ77 dictionary.  (Check was needed
441                          * because the salink array caps distances to save
442                          * memory.)  */
443
444                         offset = i - SA[R];
445
446                         /* Save match offset if it results in lower cost.  */
447                         cost = (*eval_match_cost)(lenR,
448                                                   offset,
449                                                   eval_match_cost_ctx);
450                         if (cost < best_cost) {
451                                 best_cost = cost;
452                                 pending_offset = offset;
453                         }
454                 }
455
456                 /* Advance right to next suffix.  */
457
458                 old_R = R;
459                 old_lenR = lenR;
460
461                 R += link[R].dist_to_next;
462
463                 if (link[old_R].lcpnext < lenR) {
464                         /* Match length decreased.  */
465
466                         lenR = link[old_R].lcpnext;
467
468                         /* Neither the right side nor the left size has any more
469                          * matches of length @old_lenR.  If a pending match
470                          * exists, save it.  */
471                         if (pending_offset != 0) {
472                                 matches[nmatches++] = (struct raw_match){
473                                         .len = old_lenR,
474                                         .offset = pending_offset,
475                                 };
476                                 if (nmatches == max_matches_to_return)
477                                         return nmatches;
478
479                                 pending_offset = 0;
480                         }
481
482                         if (lenR > lenL) {
483                                 /* lenR > lenL:  Keep extending right, unless
484                                  * the minimum match length would be underrun.
485                                  */
486                                 if (lenR == 0)
487                                         return nmatches;
488                         } else {
489                                 /* lenL >= lenR:  Extend left, unless the
490                                  * minimum match length would be underrun, in
491                                  * which case we are done.  */
492                                 if (lenL == 0)
493                                         return nmatches;
494
495                                 goto extend_left;
496                         }
497                 }
498         }
499 }
500
501 #endif /* _WIMLIB_LZ_SARRAY_H */