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  * Author:      Eric Biggers
   7  * Year:        2014, 2015
   8  *
   9  * The author dedicates this file to the public domain.
  10  * You can do whatever you want with this file.
  11  */
  12
  13 #ifndef _MATCHFINDER_COMMON_H
  14 #define _MATCHFINDER_COMMON_H
  15
  16 #include <string.h>
  17
  18 #include "wimlib/types.h"
  19
  20 #ifndef MATCHFINDER_MAX_WINDOW_ORDER
  21 #  error "MATCHFINDER_MAX_WINDOW_ORDER must be defined!"
  22 #endif
  23
  24 #if MATCHFINDER_MAX_WINDOW_ORDER <= 16
  25 typedef u16 pos_t;
  26 #else
  27 typedef u32 pos_t;
  28 #endif
  29
  30 #if MATCHFINDER_MAX_WINDOW_ORDER != 16 && MATCHFINDER_MAX_WINDOW_ORDER != 32
  31
  32 /* Not all the bits of the position type are needed, so the sign bit can be
  33  * reserved to mean "out of bounds".  */
  34 #define MATCHFINDER_NULL ((pos_t)-1)
  35
  36 static inline bool
  37 matchfinder_node_valid(pos_t node)
  38 {
  39         return !(node & ((pos_t)1 << (sizeof(pos_t) * 8 - 1)));
  40 }
  41
  42 #else
  43
  44 /* All bits of the position type are needed, so use 0 to mean "out of bounds".
  45  * This prevents the beginning of the buffer from matching anything; however,
  46  * this doesn't matter much.  */
  47
  48 #define MATCHFINDER_NULL ((pos_t)0)
  49
  50 static inline bool
  51 matchfinder_node_valid(pos_t node)
  52 {
  53         return node != 0;
  54 }
  55
  56 #endif
  57
  58 #define MATCHFINDER_ALIGNMENT 8
  59
  60 #ifdef __AVX2__
  61 #  include "matchfinder_avx2.h"
  62 #  if MATCHFINDER_ALIGNMENT < 32
  63 #    undef MATCHFINDER_ALIGNMENT
  64 #    define MATCHFINDER_ALIGNMENT 32
  65 #  endif
  66 #endif
  67
  68 #ifdef __SSE2__
  69 #  include "matchfinder_sse2.h"
  70 #  if MATCHFINDER_ALIGNMENT < 16
  71 #    undef MATCHFINDER_ALIGNMENT
  72 #    define MATCHFINDER_ALIGNMENT 16
  73 #  endif
  74 #endif
  75
  76 /*
  77  * Representation of a match.
  78  */
  79 struct lz_match {
  80
  81         /* The number of bytes matched.  */
  82         pos_t length;
  83
  84         /* The offset back from the current position that was matched.  */
  85         pos_t offset;
  86 };
  87
  88 static inline bool
  89 matchfinder_memset_init_okay(void)
  90 {
  91         /* All bytes must match in order to use memset.  */
  92         const pos_t v = MATCHFINDER_NULL;
  93         if (sizeof(pos_t) == 2)
  94                 return (u8)v == (u8)(v >> 8);
  95         if (sizeof(pos_t) == 4)
  96                 return (u8)v == (u8)(v >> 8) &&
  97                        (u8)v == (u8)(v >> 16) &&
  98                        (u8)v == (u8)(v >> 24);
  99         return false;
 100 }
 101
 102 /*
 103  * Initialize the hash table portion of the matchfinder.
 104  *
 105  * Essentially, this is an optimized memset().
 106  *
 107  * 'data' must be aligned to a MATCHFINDER_ALIGNMENT boundary.
 108  */
 109 static inline void
 110 matchfinder_init(pos_t *data, size_t num_entries)
 111 {
 112         const size_t size = num_entries * sizeof(data[0]);
 113
 114 #ifdef __AVX2__
 115         if (matchfinder_init_avx2(data, size))
 116                 return;
 117 #endif
 118
 119 #ifdef __SSE2__
 120         if (matchfinder_init_sse2(data, size))
 121                 return;
 122 #endif
 123
 124         if (matchfinder_memset_init_okay()) {
 125                 memset(data, (u8)MATCHFINDER_NULL, size);
 126                 return;
 127         }
 128
 129         for (size_t i = 0; i < num_entries; i++)
 130                 data[i] = MATCHFINDER_NULL;
 131 }
 132
 133 #endif /* _MATCHFINDER_COMMON_H */