4 * Common code for Lempel-Ziv matchfinding.
9 * The author dedicates this file to the public domain.
10 * You can do whatever you want with this file.
13 #ifndef _MATCHFINDER_COMMON_H
14 #define _MATCHFINDER_COMMON_H
18 #include "wimlib/types.h"
20 #ifndef MATCHFINDER_MAX_WINDOW_ORDER
21 # error "MATCHFINDER_MAX_WINDOW_ORDER must be defined!"
24 #if MATCHFINDER_MAX_WINDOW_ORDER <= 16
30 #if MATCHFINDER_MAX_WINDOW_ORDER != 16 && MATCHFINDER_MAX_WINDOW_ORDER != 32
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)
37 matchfinder_node_valid(pos_t node)
39 return !(node & ((pos_t)1 << (sizeof(pos_t) * 8 - 1)));
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. */
48 #define MATCHFINDER_NULL ((pos_t)0)
51 matchfinder_node_valid(pos_t node)
58 #define MATCHFINDER_ALIGNMENT 8
61 # include "matchfinder_avx2.h"
62 # if MATCHFINDER_ALIGNMENT < 32
63 # undef MATCHFINDER_ALIGNMENT
64 # define MATCHFINDER_ALIGNMENT 32
69 # include "matchfinder_sse2.h"
70 # if MATCHFINDER_ALIGNMENT < 16
71 # undef MATCHFINDER_ALIGNMENT
72 # define MATCHFINDER_ALIGNMENT 16
77 * Representation of a match.
81 /* The number of bytes matched. */
84 /* The offset back from the current position that was matched. */
89 matchfinder_memset_init_okay(void)
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);
103 * Initialize the hash table portion of the matchfinder.
105 * Essentially, this is an optimized memset().
107 * 'data' must be aligned to a MATCHFINDER_ALIGNMENT boundary.
110 matchfinder_init(pos_t *data, size_t num_entries)
112 const size_t size = num_entries * sizeof(data[0]);
115 if (matchfinder_init_avx2(data, size))
120 if (matchfinder_init_sse2(data, size))
124 if (matchfinder_memset_init_okay()) {
125 memset(data, (u8)MATCHFINDER_NULL, size);
129 for (size_t i = 0; i < num_entries; i++)
130 data[i] = MATCHFINDER_NULL;
133 #endif /* _MATCHFINDER_COMMON_H */