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

   1 /*
   2  * lz_brute_force.c
   3  *
   4  * Brute force match-finder for Lempel-Ziv compression.
   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/util.h"
  38
  39 static bool
  40 lz_bf_params_valid(const struct lz_mf_params *params)
  41 {
  42         return true;
  43 }
  44
  45 static u64
  46 lz_bf_get_needed_memory(u32 max_window_size)
  47 {
  48         return 0;
  49 }
  50
  51 static bool
  52 lz_bf_init(struct lz_mf *mf)
  53 {
  54         if (mf->params.min_match_len == 0)
  55                 mf->params.min_match_len = 2;
  56
  57         if (mf->params.max_match_len == 0)
  58                 mf->params.max_match_len = mf->params.max_window_size;
  59
  60         if (mf->params.max_search_depth == 0)
  61                 mf->params.max_search_depth = 32;
  62
  63         mf->params.max_search_depth = DIV_ROUND_UP(mf->params.max_search_depth, 8);
  64
  65         if (mf->params.nice_match_len == 0)
  66                 mf->params.nice_match_len = 24;
  67
  68         if (mf->params.nice_match_len < mf->params.min_match_len)
  69                 mf->params.nice_match_len = mf->params.min_match_len;
  70
  71         if (mf->params.nice_match_len > mf->params.max_match_len)
  72                 mf->params.nice_match_len = mf->params.max_match_len;
  73
  74         return true;
  75 }
  76
  77 static void
  78 lz_bf_load_window(struct lz_mf *mf, const u8 window[], u32 size)
  79 {
  80 }
  81
  82 static u32
  83 lz_bf_get_matches(struct lz_mf *mf, struct lz_match matches[])
  84 {
  85         const u8 * const strptr = lz_mf_get_window_ptr(mf);
  86         const u32 max_len = min(lz_mf_get_bytes_remaining(mf),
  87                                 mf->params.nice_match_len);
  88         u32 best_len = mf->params.min_match_len - 1;
  89         u32 num_matches = 0;
  90         const u8 *matchptr = strptr;
  91
  92         if (best_len >= max_len)
  93                 goto out;
  94
  95         while (matchptr-- > mf->cur_window) {
  96
  97                 u32 len;
  98
  99                 if (matchptr[best_len] != strptr[best_len] ||
 100                     matchptr[best_len - 1] != strptr[best_len - 1] ||
 101                     matchptr[0] != strptr[0])
 102                         goto next_match;
 103
 104                 for (len = 1; len < best_len - 1; len++)
 105                         if (matchptr[len] != strptr[len])
 106                                 goto next_match;
 107
 108                 len = best_len;
 109
 110                 while (++len != max_len)
 111                         if (matchptr[len] != strptr[len])
 112                                 break;
 113
 114                 matches[num_matches++] = (struct lz_match) {
 115                         .len = len,
 116                         .offset = strptr - matchptr,
 117                 };
 118                 best_len = len;
 119                 if (best_len == max_len)
 120                         break;
 121                 if (num_matches == mf->params.max_search_depth)
 122                         break;
 123         next_match:
 124                 ;
 125         }
 126
 127         /* If the longest match is @nice_match_len in length, it may have been
 128          * truncated.  Try extending it up to the maximum match length.  */
 129         if (num_matches != 0 &&
 130             matches[num_matches - 1].len == mf->params.nice_match_len)
 131         {
 132                 const u8 * const matchptr = strptr - matches[num_matches - 1].offset;
 133                 const u32 len_limit = min(lz_mf_get_bytes_remaining(mf),
 134                                           mf->params.max_match_len);
 135                 u32 len;
 136
 137                 len = matches[num_matches - 1].len;
 138                 while (len < len_limit && strptr[len] == matchptr[len])
 139                         len++;
 140                 matches[num_matches - 1].len = len;
 141         }
 142
 143 out:
 144         mf->cur_window_pos++;
 145         return num_matches;
 146 }
 147
 148 static void
 149 lz_bf_skip_positions(struct lz_mf *mf, u32 n)
 150 {
 151         mf->cur_window_pos += n;
 152 }
 153
 154 static void
 155 lz_bf_destroy(struct lz_mf *mf)
 156 {
 157 }
 158
 159 const struct lz_mf_ops lz_brute_force_ops = {
 160         .params_valid      = lz_bf_params_valid,
 161         .get_needed_memory = lz_bf_get_needed_memory,
 162         .init              = lz_bf_init,
 163         .load_window       = lz_bf_load_window,
 164         .get_matches       = lz_bf_get_matches,
 165         .skip_positions    = lz_bf_skip_positions,
 166         .destroy           = lz_bf_destroy,
 167         .struct_size       = sizeof(struct lz_mf),
 168 };