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                 if (matchptr[best_len] == strptr[best_len] &&
  97                     matchptr[best_len - 1] == strptr[best_len - 1] &&
  98                     matchptr[0] == strptr[0])
  99                 {
 100                         u32 len = 0;
 101
 102                         while (++len != max_len)
 103                                 if (matchptr[len] != strptr[len])
 104                                         break;
 105
 106                         if (len > best_len) {
 107                                 matches[num_matches++] = (struct lz_match) {
 108                                         .len = len,
 109                                         .offset = strptr - matchptr,
 110                                 };
 111                                 best_len = len;
 112                                 if (best_len == max_len)
 113                                         break;
 114                                 if (num_matches == mf->params.max_search_depth)
 115                                         break;
 116                         }
 117                 }
 118         }
 119
 120         /* If the longest match is @nice_match_len in length, it may have been
 121          * truncated.  Try extending it up to the maximum match length.  */
 122         if (num_matches != 0 &&
 123             matches[num_matches - 1].len == mf->params.nice_match_len)
 124         {
 125                 const u8 * const matchptr = strptr - matches[num_matches - 1].offset;
 126                 const u32 len_limit = min(lz_mf_get_bytes_remaining(mf),
 127                                           mf->params.max_match_len);
 128                 u32 len;
 129
 130                 len = matches[num_matches - 1].len;
 131                 while (len < len_limit && strptr[len] == matchptr[len])
 132                         len++;
 133                 matches[num_matches - 1].len = len;
 134         }
 135
 136 out:
 137         mf->cur_window_pos++;
 138         return num_matches;
 139 }
 140
 141 static void
 142 lz_bf_skip_positions(struct lz_mf *mf, u32 n)
 143 {
 144         mf->cur_window_pos += n;
 145 }
 146
 147 static void
 148 lz_bf_destroy(struct lz_mf *mf)
 149 {
 150 }
 151
 152 const struct lz_mf_ops lz_brute_force_ops = {
 153         .params_valid      = lz_bf_params_valid,
 154         .get_needed_memory = lz_bf_get_needed_memory,
 155         .init              = lz_bf_init,
 156         .load_window       = lz_bf_load_window,
 157         .get_matches       = lz_bf_get_matches,
 158         .skip_positions    = lz_bf_skip_positions,
 159         .destroy           = lz_bf_destroy,
 160         .struct_size       = sizeof(struct lz_mf),
 161 };