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