wimlib.net Git - wimlib/blob - include/wimlib/matchfinder_common.h

   1 /*
   2  * matchfinder_common.h
   3  *
   4  * Common code for Lempel-Ziv matchfinding.
   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 #pragma once
  33
  34 #include "wimlib/types.h"
  35
  36 #include <string.h>
  37
  38 #ifndef MATCHFINDER_WINDOW_ORDER
  39 #  error "MATCHFINDER_WINDOW_ORDER must be defined!"
  40 #endif
  41
  42 #ifndef MATCHFINDER_IS_SLIDING
  43 #  error "MATCHFINDER_IS_SLIDING must be defined!"
  44 #endif
  45
  46 #define MATCHFINDER_WINDOW_SIZE ((size_t)1 << MATCHFINDER_WINDOW_ORDER)
  47
  48 #if MATCHFINDER_IS_SLIDING
  49 #  include "matchfinder_sliding.h"
  50 #else
  51 #  include "matchfinder_nonsliding.h"
  52 #endif
  53
  54 #define MATCHFINDER_ALIGNMENT 8
  55
  56 #ifdef __AVX2__
  57 #  include "matchfinder_avx2.h"
  58 #  if MATCHFINDER_ALIGNMENT < 32
  59 #    undef MATCHFINDER_ALIGNMENT
  60 #    define MATCHFINDER_ALIGNMENT 32
  61 #  endif
  62 #endif
  63
  64 #ifdef __SSE2__
  65 #  include "matchfinder_sse2.h"
  66 #  if MATCHFINDER_ALIGNMENT < 16
  67 #    undef MATCHFINDER_ALIGNMENT
  68 #    define MATCHFINDER_ALIGNMENT 16
  69 #  endif
  70 #endif
  71
  72 /*
  73  * Representation of a match.
  74  */
  75 struct lz_match {
  76
  77         /* The number of bytes matched.  */
  78         pos_t length;
  79
  80         /* The offset back from the current position that was matched.  */
  81         pos_t offset;
  82 };
  83
  84 static inline bool
  85 matchfinder_memset_init_okay(void)
  86 {
  87         /* All bytes must match in order to use memset.  */
  88         const pos_t v = MATCHFINDER_INITVAL;
  89         if (sizeof(pos_t) == 2)
  90                 return (u8)v == (u8)(v >> 8);
  91         if (sizeof(pos_t) == 4)
  92                 return (u8)v == (u8)(v >> 8) &&
  93                        (u8)v == (u8)(v >> 16) &&
  94                        (u8)v == (u8)(v >> 24);
  95         return false;
  96 }
  97
  98 /*
  99  * Initialize the hash table portion of the matchfinder.
 100  *
 101  * Essentially, this is an optimized memset().
 102  *
 103  * 'data' must be aligned to a MATCHFINDER_ALIGNMENT boundary.
 104  */
 105 static inline void
 106 matchfinder_init(pos_t *data, size_t num_entries)
 107 {
 108         const size_t size = num_entries * sizeof(data[0]);
 109
 110 #ifdef __AVX2__
 111         if (matchfinder_init_avx2(data, size))
 112                 return;
 113 #endif
 114
 115 #ifdef __SSE2__
 116         if (matchfinder_init_sse2(data, size))
 117                 return;
 118 #endif
 119
 120         if (matchfinder_memset_init_okay()) {
 121                 memset(data, (u8)MATCHFINDER_INITVAL, size);
 122                 return;
 123         }
 124
 125         for (size_t i = 0; i < num_entries; i++)
 126                 data[i] = MATCHFINDER_INITVAL;
 127 }
 128
 129 #if MATCHFINDER_IS_SLIDING
 130 /*
 131  * Slide the matchfinder by WINDOW_SIZE bytes.
 132  *
 133  * This must be called just after each WINDOW_SIZE bytes have been run through
 134  * the matchfinder.
 135  *
 136  * This will subtract WINDOW_SIZE bytes from each entry in the array specified.
 137  * The effect is that all entries are updated to be relative to the current
 138  * position, rather than the position WINDOW_SIZE bytes prior.
 139  *
 140  * Underflow is detected and replaced with signed saturation.  This ensures that
 141  * once the sliding window has passed over a position, that position forever
 142  * remains out of bounds.
 143  *
 144  * The array passed in must contain all matchfinder data that is
 145  * position-relative.  Concretely, this will include the hash table as well as
 146  * the table of positions that is used to link together the sequences in each
 147  * hash bucket.  Note that in the latter table, the links are 1-ary in the case
 148  * of "hash chains", and 2-ary in the case of "binary trees".  In either case,
 149  * the links need to be rebased in the same way.
 150  */
 151 static inline void
 152 matchfinder_rebase(pos_t *data, size_t num_entries)
 153 {
 154         const size_t size = num_entries * sizeof(data[0]);
 155
 156 #ifdef __AVX2__
 157         if (matchfinder_rebase_avx2(data, size))
 158                 return;
 159 #endif
 160
 161 #ifdef __SSE2__
 162         if (matchfinder_rebase_sse2(data, size))
 163                 return;
 164 #endif
 165
 166         if (MATCHFINDER_WINDOW_SIZE == 32768) {
 167                 /* Branchless version for 32768 byte windows.  If the value was
 168                  * already negative, clear all bits except the sign bit; this
 169                  * changes the value to -32768.  Otherwise, set the sign bit;
 170                  * this is equivalent to subtracting 32768.  */
 171                 for (size_t i = 0; i < num_entries; i++) {
 172                         u16 v = data[i];
 173                         u16 sign_bit = v & 0x8000;
 174                         v &= sign_bit - ((sign_bit >> 15) ^ 1);
 175                         v |= 0x8000;
 176                         data[i] = v;
 177                 }
 178                 return;
 179         }
 180
 181         for (size_t i = 0; i < num_entries; i++) {
 182                 if (data[i] >= 0)
 183                         data[i] -= (pos_t)-MATCHFINDER_WINDOW_SIZE;
 184                 else
 185                         data[i] = (pos_t)-MATCHFINDER_WINDOW_SIZE;
 186         }
 187 }
 188 #endif /* MATCHFINDER_IS_SLIDING */