afaab9cba01e61a5b1eab8a1b5fe461681e31c74
[wimlib] / 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 */