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