wimlib.net Git - wimlib/blob - src/lz_mf.c

   1 /*
   2  * lz_mf.c
   3  *
   4  * Interface for Lempel-Ziv match-finders.
   5  *
   6  * Copyright (c) 2014 Eric Biggers.  All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  *
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
  23  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  26  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  27  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  28  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  29  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 #ifdef HAVE_CONFIG_H
  33 #  include "config.h"
  34 #endif
  35
  36 #include "wimlib/lz_mf.h"
  37 #include "wimlib/lz_mf_ops.h"
  38 #include "wimlib/util.h"
  39
  40 /* Available match-finding algorithms.  */
  41 static const struct lz_mf_ops *mf_ops[] = {
  42         [LZ_MF_NULL]                    = &lz_null_ops,
  43         [LZ_MF_HASH_CHAINS]             = &lz_hash_chains_ops,
  44         [LZ_MF_BINARY_TREES]            = &lz_binary_trees_ops,
  45         [LZ_MF_LCP_INTERVAL_TREE]       = &lz_lcp_interval_tree_ops,
  46         [LZ_MF_LINKED_SUFFIX_ARRAY]     = &lz_linked_suffix_array_ops,
  47 };
  48
  49 /*
  50  * Automatically select a match-finding algorithm to use, in the case that the
  51  * user did not specify one.
  52  */
  53 static const struct lz_mf_ops *
  54 select_mf_ops(enum lz_mf_algo algorithm, u32 max_window_size)
  55 {
  56         if (algorithm == LZ_MF_DEFAULT) {
  57                 if (max_window_size <= 32768)
  58                         algorithm = LZ_MF_HASH_CHAINS;
  59                 else if (max_window_size <= 2097152)
  60                         algorithm = LZ_MF_BINARY_TREES;
  61                 else if (max_window_size <= 33554432)
  62                         algorithm = LZ_MF_LCP_INTERVAL_TREE;
  63                 else
  64                         algorithm = LZ_MF_LINKED_SUFFIX_ARRAY;
  65         }
  66         if ((int)algorithm < 0 || (int)algorithm >= ARRAY_LEN(mf_ops))
  67                 return NULL;
  68         return mf_ops[(int)algorithm];
  69 }
  70
  71 /*
  72  * Returns an upper bound on the number of bytes of memory that will be consumed
  73  * by a match-finder allocated with the specified algorithm and maximum window
  74  * size.
  75  *
  76  * The returned value does not include the size of the window itself.  The
  77  * caller must account for this separately if needed.
  78  *
  79  * If @algorithm is invalid, returns 0.
  80  */
  81 u64
  82 lz_mf_get_needed_memory(enum lz_mf_algo algorithm, u32 max_window_size)
  83 {
  84         const struct lz_mf_ops *ops;
  85
  86         ops = select_mf_ops(algorithm, max_window_size);
  87         if (!ops)
  88                 return 0;
  89         return ops->struct_size + ops->get_needed_memory(max_window_size);
  90 }
  91 /*
  92  * Returns %true if and only if the specified parameters can be validly used to
  93  * create a match-finder using lz_mf_alloc().
  94  */
  95 bool
  96 lz_mf_params_valid(const struct lz_mf_params *params)
  97 {
  98         const struct lz_mf_ops *ops;
  99
 100         /* Require that a valid algorithm, or LZ_MF_DEFAULT, be specified.  */
 101         ops = select_mf_ops(params->algorithm, params->max_window_size);
 102         if (!ops)
 103                 return false;
 104
 105         /* Don't allow empty windows.  Otherwise, some match-finding algorithms
 106          * might need special-case code to handle empty windows.  */
 107         if (params->max_window_size == 0)
 108                 return false;
 109
 110         /* Don't allow length-1 matches, so that match-finding algorithms don't
 111          * need to worry about this case.  Most LZ-based compression formats
 112          * don't allow length-1 matches, since they usually aren't helpful for
 113          * compression.  Also, if a compressor really does need length-1
 114          * matches, it can easily maintain its own table of length 256
 115          * containing the most-recently-seen position for each byte value.
 116          *
 117          * min_match_len == 0 is valid, since that means the match-finding
 118          * algorithm will fill in a default value.  */
 119         if (params->min_match_len == 1)
 120                 return false;
 121
 122         if (params->max_match_len != 0) {
 123
 124                 /* Don't allow length-1 matches (same reason as above).  */
 125                 if (params->max_match_len == 1)
 126                         return false;
 127
 128                 /* Don't allow the maximum match length to be shorter than the
 129                  * minimum match length.  */
 130                 if (params->max_match_len < params->min_match_len)
 131                         return false;
 132         }
 133
 134         /* Don't allow the needed memory size to overflow a 'size_t'.  */
 135         if (sizeof(size_t) < sizeof(u64)) {
 136                 u64 needed_mem = ops->get_needed_memory(params->max_window_size);
 137                 if ((size_t)needed_mem != needed_mem)
 138                         return false;
 139         }
 140
 141         /* Call the algorithm-specific routine to finish the validation.  */
 142         return ops->params_valid(params);
 143 }
 144
 145 /*
 146  * Allocate a new match-finder.
 147  *
 148  * @params
 149  *      The parameters for the match-finder.  See the declaration of 'struct
 150  *      lz_mf_params' for more information.
 151  *
 152  * Returns a pointer to the new match-finder, or NULL if out of memory or the
 153  * parameters are invalid.  Call lz_mf_params_valid() beforehand to test the
 154  * parameter validity separately.
 155  */
 156 struct lz_mf *
 157 lz_mf_alloc(const struct lz_mf_params *params)
 158 {
 159         struct lz_mf *mf;
 160         const struct lz_mf_ops *ops;
 161
 162         /* Validate the parameters.  */
 163         if (!lz_mf_params_valid(params))
 164                 return NULL;
 165
 166         /* Get the match-finder operations structure.  Since we just validated
 167          * the parameters, this is guaranteed to return a valid structure.  */
 168         ops = select_mf_ops(params->algorithm, params->max_window_size);
 169         LZ_ASSERT(ops != NULL);
 170
 171         /* Allocate memory for the match-finder structure.  */
 172         LZ_ASSERT(ops->struct_size >= sizeof(struct lz_mf));
 173         mf = CALLOC(1, ops->struct_size);
 174         if (!mf)
 175                 return NULL;
 176
 177         /* Set the parameters and operations fields.  */
 178         mf->params = *params;
 179         mf->ops = *ops;
 180
 181         /* Perform algorithm-specific initialization.  Normally this is where
 182          * most of the necessary memory is allocated.  */
 183         if (!mf->ops.init(mf)) {
 184                 FREE(mf);
 185                 return NULL;
 186         }
 187
 188         /* The algorithm must have set min_match_len and max_match_len if either
 189          * was 0.  */
 190         LZ_ASSERT(mf->params.min_match_len >= 2);
 191         LZ_ASSERT(mf->params.max_match_len >= mf->params.min_match_len);
 192
 193         return mf;
 194 }
 195
 196 /*
 197  * Load a window into the match-finder.
 198  *
 199  * @mf
 200  *      The match-finder into which to load the window.
 201  * @window
 202  *      Pointer to the window to load.  This memory must remain available,
 203  *      unmodified, while the match-finder is being used.
 204  * @size
 205  *      The size of the window, in bytes.  This can't be larger than the
 206  *      @max_window_size parameter.  In addition, this can't be 0.
 207  *
 208  * Note: this interface does not support sliding windows!
 209  */
 210 void
 211 lz_mf_load_window(struct lz_mf *mf, const u8 *window, u32 size)
 212 {
 213         /* Can't be an empty window, and can't be larger than the maximum window
 214          * size with which the match-finder was allocated.  */
 215         LZ_ASSERT(size > 0);
 216         LZ_ASSERT(size <= mf->params.max_window_size);
 217
 218         /* Save the window and initialize the current position.  */
 219         mf->cur_window = window;
 220         mf->cur_window_size = size;
 221         mf->cur_window_pos = 0;
 222
 223         /* Call into the algorithm-specific window load code.  */
 224         mf->ops.load_window(mf, window, size);
 225 }
 226
 227 /*
 228  * Retrieve a list of matches at the next position in the window.
 229  *
 230  * @mf
 231  *      The match-finder into which a window has been loaded using
 232  *      lz_mf_load_window().
 233  * @matches
 234  *      The array into which the matches will be returned.  The returned match
 235  *      count will not exceed the minimum of @max_search_depth and (@len_limit -
 236  *      @min_match_len + 1), where @len_limit is itself defined as
 237  *      min(@max_match_len, @nice_match_len).
 238  *
 239  * The return value is the number of matches that were found and stored in the
 240  * 'matches' array.  The matches will be ordered by strictly increasing length
 241  * and strictly increasing offset.  No match shall have length less than
 242  * @min_match_len, and no match shall have length greater than @max_match_len.
 243  * The return value may be 0, which indicates that no matches were found.
 244  *
 245  * On completion, the match-finder is advanced to the next position in the
 246  * window.
 247  *
 248  * Note: in-non-debug mode, the inline definition of this gets used instead.
 249  * They are the same, except that the non-inline version below validates the
 250  * results to help debug match-finding algorithms.
 251  */
 252 #ifdef ENABLE_LZ_DEBUG
 253 u32
 254 lz_mf_get_matches(struct lz_mf *mf, struct lz_match *matches)
 255 {
 256         LZ_ASSERT(mf->cur_window_pos < mf->cur_window_size);
 257
 258         const u32 orig_pos = mf->cur_window_pos;
 259         const u32 len_limit = min(mf->params.max_match_len,
 260                                   lz_mf_get_bytes_remaining(mf));
 261         const u8 * const strptr = lz_mf_get_window_ptr(mf);
 262
 263         const u32 num_matches = mf->ops.get_matches(mf, matches);
 264
 265         LZ_ASSERT(mf->cur_window_pos == orig_pos + 1);
 266
 267 #if 0
 268         fprintf(stderr, "Pos %"PRIu32"/%"PRIu32": %"PRIu32" matches\n",
 269                 orig_pos, mf->cur_window_size, num_matches);
 270         for (u32 i = 0; i < num_matches; i++) {
 271                 fprintf(stderr, "\tLen %"PRIu32" Offset %"PRIu32"\n",
 272                         matches[i].len, matches[i].offset);
 273         }
 274 #endif
 275
 276         /* Validate the matches.  */
 277         for (u32 i = 0; i < num_matches; i++) {
 278                 const u32 len = matches[i].len;
 279                 const u32 offset = matches[i].offset;
 280                 const u8 *matchptr;
 281
 282                 /* Length valid?  */
 283                 LZ_ASSERT(len >= mf->params.min_match_len);
 284                 LZ_ASSERT(len <= len_limit);
 285
 286                 /* Offset valid?  */
 287                 LZ_ASSERT(offset >= 1);
 288                 LZ_ASSERT(offset <= orig_pos);
 289
 290                 /* Lengths and offsets strictly increasing?  */
 291                 if (i > 0) {
 292                         LZ_ASSERT(len > matches[i - 1].len);
 293                         LZ_ASSERT(offset > matches[i - 1].offset);
 294                 }
 295
 296                 /* Actually a match?  */
 297                 matchptr = strptr - offset;
 298                 LZ_ASSERT(!memcmp(strptr, matchptr, len));
 299
 300                 /* Match can't be extended further?  */
 301                 LZ_ASSERT(len == len_limit || strptr[len] != matchptr[len]);
 302         }
 303
 304         return num_matches;
 305 }
 306 #endif /* ENABLE_LZ_DEBUG */
 307
 308 /*
 309  * Skip 'n' positions in the match-finder.  This is a faster alternative to
 310  * calling lz_mf_get_matches() at each position to advance the match-finder.
 311  *
 312  * 'n' must be greater than 0.
 313  *
 314  * Note: in-non-debug mode, the inline definition of this gets used instead.
 315  * They are the same, except the non-inline version below does extra checks.
 316  */
 317 #ifdef ENABLE_LZ_DEBUG
 318 void
 319 lz_mf_skip_positions(struct lz_mf *mf, const u32 n)
 320 {
 321         LZ_ASSERT(n > 0);
 322         LZ_ASSERT(n <= lz_mf_get_bytes_remaining(mf));
 323
 324         const u32 orig_pos = mf->cur_window_pos;
 325
 326         mf->ops.skip_positions(mf, n);
 327
 328         LZ_ASSERT(mf->cur_window_pos == orig_pos + n);
 329 }
 330 #endif
 331
 332 /*
 333  * Free the match-finder.
 334  *
 335  * This frees all memory that was allocated by the call to lz_mf_alloc().
 336  */
 337 void
 338 lz_mf_free(struct lz_mf *mf)
 339 {
 340         if (mf) {
 341                 mf->ops.destroy(mf);
 342         #ifdef ENABLE_LZ_DEBUG
 343                 memset(mf, 0, mf->ops.struct_size);
 344         #endif
 345                 FREE(mf);
 346         }
 347 }