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