wimlib.net Git - wimlib/blob - include/wimlib/lz_sarray.h

   1 /*
   2  * lz_sarray.h
   3  *
   4  * Suffix array match-finder for LZ (Lempel-Ziv) compression.
   5  */
   6
   7 /*
   8  * Copyright (c) 2013 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"
  38 #include "wimlib/lz.h"
  39 #include "wimlib/types.h"
  40
  41 struct salink;
  42
  43 /* Suffix array LZ (Lempel-Ziv) match-finder.  */
  44 struct lz_sarray {
  45         /* Allocated window size for the match-finder.  */
  46         input_idx_t max_window_size;
  47
  48         /* Minimum match length to return.  */
  49         input_idx_t min_match_len;
  50
  51         /* Maximum match length to return.  */
  52         input_idx_t max_match_len;
  53
  54         /* Maximum matches to consider at each position (max search depth).  */
  55         u32 max_matches_to_consider;
  56
  57         /* Maximum number of matches to return at each position.  */
  58         u32 max_matches_to_return;
  59
  60         /* Current position in the window  */
  61         input_idx_t cur_pos;
  62
  63         /* Current window size.  */
  64         input_idx_t window_size;
  65
  66         /* Suffix array for window.
  67          * This is a mapping from suffix rank to suffix position.  */
  68         input_idx_t *SA;
  69
  70         /* Inverse suffix array for window.
  71          * This is a mapping from suffix position to suffix rank.
  72          * If 0 <= r < window_size, then ISA[SA[r]] == r.  */
  73         input_idx_t *ISA;
  74
  75         /* Longest common prefix array corresponding to the suffix array SA.
  76          * LCP[i] is the length of the longest common prefix between the
  77          * suffixes with positions SA[i - 1] and  SA[i].  LCP[0] is undefined.
  78          */
  79         input_idx_t *LCP;
  80
  81         /* Suffix array links.
  82          *
  83          * During a linear scan of the input string to find matches, this array
  84          * used to keep track of which rank suffixes in the suffix array appear
  85          * before the current position.  Instead of searching in the original
  86          * suffix array, scans for matches at a given position traverse a linked
  87          * list containing only suffixes that appear before that position.  */
  88         struct salink *salink;
  89 };
  90
  91 /* Suffix array link  */
  92 struct salink {
  93         /* Rank of highest ranked suffix that has rank lower than the suffix
  94          * corresponding to this structure and either has a lower position
  95          * (initially) or has a position lower than the highest position at
  96          * which matches have been searched for so far, or -1 if there is no
  97          * such suffix.  */
  98         input_idx_t prev;
  99
 100         /* Rank of lowest ranked suffix that has rank greater than the suffix
 101          * corresponding to this structure and either has a lower position
 102          * (intially) or has a position lower than the highest position at which
 103          * matches have been searched for so far, or -1 if there is no such
 104          * suffix.  */
 105         input_idx_t next;
 106
 107         /* Length of longest common prefix between the suffix corresponding to
 108          * this structure and the suffix with rank @prev, or 0 if @prev is -1.
 109          */
 110         input_idx_t lcpprev;
 111
 112         /* Length of longest common prefix between the suffix corresponding to
 113          * this structure and the suffix with rank @next, or 0 if @next is -1.
 114          */
 115         input_idx_t lcpnext;
 116 };
 117
 118 extern bool
 119 lz_sarray_init(struct lz_sarray *mf,
 120                 input_idx_t max_window_size,
 121                 input_idx_t min_match_len,
 122                 input_idx_t max_match_len,
 123                 u32 max_matches_to_consider,
 124                 u32 max_matches_to_return);
 125
 126 extern void
 127 lz_sarray_destroy(struct lz_sarray *mf);
 128
 129 extern void
 130 lz_sarray_load_window(struct lz_sarray *mf, const u8 window[],
 131                       input_idx_t window_size);
 132
 133 static inline input_idx_t
 134 lz_sarray_get_pos(const struct lz_sarray *mf)
 135 {
 136         return mf->cur_pos;
 137 }
 138
 139 /* Advance the suffix array match-finder to the next position.  */
 140 static _always_inline_attribute void
 141 lz_sarray_update_salink(const input_idx_t i,
 142                         const input_idx_t SA[const restrict],
 143                         const input_idx_t ISA[const restrict],
 144                         struct salink link[const restrict])
 145 {
 146         /* r = Rank of the suffix at the current position.  */
 147         const input_idx_t r = ISA[i];
 148
 149         /* next = rank of LOWEST ranked suffix that is ranked HIGHER than the
 150          * current suffix AND has a LOWER position, or -1 if none exists.  */
 151         const input_idx_t next = link[r].next;
 152
 153         /* prev = rank of HIGHEST ranked suffix that is ranked LOWER than the
 154          * current suffix AND has a LOWER position, or -1 if none exists.  */
 155         const input_idx_t prev = link[r].prev;
 156
 157         /* Link the suffix at the current position into the linked list that
 158          * contains all suffixes in the suffix array that are appear at or
 159          * before the current position, sorted by rank.
 160          *
 161          * Save the values of all fields we overwrite so that rollback is
 162          * possible.  */
 163         if (next != ~(input_idx_t)0) {
 164
 165                 link[next].prev = r;
 166                 link[next].lcpprev = link[r].lcpnext;
 167         }
 168
 169         if (prev != ~(input_idx_t)0) {
 170
 171                 link[prev].next = r;
 172                 link[prev].lcpnext = link[r].lcpprev;
 173         }
 174 }
 175
 176 /* Skip the current position in the suffix array match-finder.  */
 177 static _always_inline_attribute void
 178 lz_sarray_skip_position(struct lz_sarray *mf)
 179 {
 180         LZ_ASSERT(mf->cur_pos < mf->window_size);
 181         lz_sarray_update_salink(mf->cur_pos++, mf->SA, mf->ISA, mf->salink);
 182 }
 183
 184 typedef input_idx_t lz_sarray_cost_t;
 185 #define LZ_SARRAY_INFINITE_COST (~(lz_sarray_cost_t)0)
 186
 187 /*
 188  * Use the suffix array match-finder to retrieve a list of LZ matches at the
 189  * current position.
 190  *
 191  * Returns the number of matches written into @matches.  The matches are
 192  * returned in decreasing order by length, and each will be of unique length
 193  * between the minimum and maximum match lengths passed to lz_sarray_init().  Up
 194  * to @max_matches_to_return (passed to lz_sarray_init()) matches will be
 195  * returned.
 196  *
 197  * @eval_match_cost is a function for evaluating the cost of a match when
 198  * deciding which ones to return.  It is only used for comparing matches of the
 199  * same length.  It needs to be fast, and need not be exact; an implementation
 200  * might simply rank matches by their offset, for example, although
 201  * implementations may choose to take into account additional information such
 202  * as repeat offsets.
 203  */
 204 static _always_inline_attribute u32
 205 lz_sarray_get_matches(struct lz_sarray *mf,
 206                       struct raw_match matches[],
 207                       lz_sarray_cost_t (*eval_match_cost)
 208                                 (input_idx_t length,
 209                                  input_idx_t offset,
 210                                  const void *ctx),
 211                       const void *eval_match_cost_ctx)
 212 {
 213         LZ_ASSERT(mf->cur_pos < mf->window_size);
 214         const input_idx_t i = mf->cur_pos++;
 215
 216         const input_idx_t * const restrict SA = mf->SA;
 217         const input_idx_t * const restrict ISA = mf->ISA;
 218         struct salink * const restrict link = mf->salink;
 219         const input_idx_t min_match_len = mf->min_match_len;
 220         const u32 max_matches_to_consider = mf->max_matches_to_consider;
 221         const u32 max_matches_to_return = mf->max_matches_to_return;
 222
 223         /* r = Rank of the suffix at the current position.  */
 224         const input_idx_t r = ISA[i];
 225
 226         /* Prepare for searching the current position.  */
 227         lz_sarray_update_salink(i, SA, ISA, link);
 228
 229         /* L = rank of next suffix to the left;
 230          * R = rank of next suffix to the right;
 231          * lenL = length of match between current position and the suffix with rank L;
 232          * lenR = length of match between current position and the suffix with rank R.
 233          *
 234          * This is left and right relative to the rank of the current suffix.
 235          * Since the suffixes in the suffix array are sorted, the longest
 236          * matches are immediately to the left and right (using the linked list
 237          * to ignore all suffixes that occur later in the window).  The match
 238          * length decreases the farther left and right we go.  We shall keep the
 239          * length on both sides in sync in order to choose the lowest-cost match
 240          * of each length.
 241          */
 242         input_idx_t L = link[r].prev;
 243         input_idx_t R = link[r].next;
 244         input_idx_t lenL = link[r].lcpprev;
 245         input_idx_t lenR = link[r].lcpnext;
 246
 247         /* nmatches = number of matches found so far.  */
 248         u32 nmatches = 0;
 249
 250         /* best_cost = cost of lowest-cost match found so far.
 251          *
 252          * We keep track of this so that we can ignore shorter matches that do
 253          * not have lower costs than a longer matches already found.
 254          */
 255         lz_sarray_cost_t best_cost = LZ_SARRAY_INFINITE_COST;
 256
 257         /* count_remaining = maximum number of possible matches remaining to be
 258          * considered.  */
 259         u32 count_remaining = max_matches_to_consider;
 260
 261         /* pending = match currently being considered for a specific length.  */
 262         struct raw_match pending;
 263         lz_sarray_cost_t pending_cost;
 264
 265         while (lenL >= min_match_len || lenR >= min_match_len)
 266         {
 267                 pending.len = lenL;
 268                 pending_cost = LZ_SARRAY_INFINITE_COST;
 269                 lz_sarray_cost_t cost;
 270
 271                 /* Extend left.  */
 272                 if (lenL >= min_match_len && lenL >= lenR) {
 273                         for (;;) {
 274
 275                                 if (--count_remaining == 0)
 276                                         goto out_save_pending;
 277
 278                                 input_idx_t offset = i - SA[L];
 279
 280                                 /* Save match if it has smaller cost.  */
 281                                 cost = (*eval_match_cost)(lenL, offset,
 282                                                           eval_match_cost_ctx);
 283                                 if (cost < pending_cost) {
 284                                         pending.offset = offset;
 285                                         pending_cost = cost;
 286                                 }
 287
 288                                 if (link[L].lcpprev < lenL) {
 289                                         /* Match length decreased.  */
 290
 291                                         lenL = link[L].lcpprev;
 292
 293                                         /* Save the pending match unless the
 294                                          * right side still may have matches of
 295                                          * this length to be scanned, or if a
 296                                          * previous (longer) match had lower
 297                                          * cost.  */
 298                                         if (pending.len > lenR) {
 299                                                 if (pending_cost < best_cost) {
 300                                                         best_cost = pending_cost;
 301                                                         matches[nmatches++] = pending;
 302                                                         if (nmatches == max_matches_to_return)
 303                                                                 return nmatches;
 304                                                 }
 305                                                 pending.len = lenL;
 306                                                 pending_cost = LZ_SARRAY_INFINITE_COST;
 307                                         }
 308                                         if (lenL < min_match_len || lenL < lenR)
 309                                                 break;
 310                                 }
 311                                 L = link[L].prev;
 312                         }
 313                 }
 314
 315                 pending.len = lenR;
 316
 317                 /* Extend right.  */
 318                 if (lenR >= min_match_len && lenR > lenL) {
 319                         for (;;) {
 320
 321                                 if (--count_remaining == 0)
 322                                         goto out_save_pending;
 323
 324                                 input_idx_t offset = i - SA[R];
 325
 326                                 /* Save match if it has smaller cost.  */
 327                                 cost = (*eval_match_cost)(lenR,
 328                                                           offset,
 329                                                           eval_match_cost_ctx);
 330                                 if (cost < pending_cost) {
 331                                         pending.offset = offset;
 332                                         pending_cost = cost;
 333                                 }
 334
 335                                 if (link[R].lcpnext < lenR) {
 336                                         /* Match length decreased.  */
 337
 338                                         lenR = link[R].lcpnext;
 339
 340                                         /* Save the pending match unless a
 341                                          * previous (longer) match had lower
 342                                          * cost.  */
 343                                         if (pending_cost < best_cost) {
 344                                                 matches[nmatches++] = pending;
 345                                                 best_cost = pending_cost;
 346                                                 if (nmatches == max_matches_to_return)
 347                                                         return nmatches;
 348                                         }
 349
 350                                         if (lenR < min_match_len || lenR <= lenL)
 351                                                 break;
 352
 353                                         pending.len = lenR;
 354                                         pending_cost = LZ_SARRAY_INFINITE_COST;
 355                                 }
 356                                 R = link[R].next;
 357                         }
 358                 }
 359         }
 360         goto out;
 361
 362 out_save_pending:
 363         if (pending_cost != LZ_SARRAY_INFINITE_COST)
 364                 matches[nmatches++] = pending;
 365
 366 out:
 367         return nmatches;
 368 }
 369
 370 #endif /* _WIMLIB_LZ_SARRAY_H */