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