1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | |
16 | |
17 | |
18 | |
19 | |
20 | |
21 | |
22 | |
23 | |
24 | |
25 | |
26 | |
27 | |
28 | |
29 | |
30 | #include <stdint.h> |
31 | #include <stdlib.h> |
32 | #include <assert.h> |
33 | #include "igzip_lib.h" |
34 | |
35 | #ifdef _MSC_VER |
36 | # include <intrin.h> |
37 | # define inline __inline |
38 | #else |
39 | # include <x86intrin.h> |
40 | #endif |
41 | |
42 | static inline uint32_t bsr(uint32_t val) |
43 | { |
44 | uint32_t msb; |
45 | #ifdef __LZCNT__ |
46 | msb = 16 - __lzcnt16(val); |
47 | #else |
48 | for(msb = 0; val > 0; val >>= 1) |
49 | msb++; |
50 | #endif |
51 | return msb; |
52 | } |
53 | |
54 | static inline uint32_t tzcnt(uint64_t val) |
55 | { |
56 | uint32_t cnt; |
57 | |
58 | #ifdef __x86_64__1 |
59 | |
60 | cnt = __builtin_ctzll(val) / 8; |
61 | |
62 | #else |
63 | for(cnt = 8; val > 0; val <<= 8) |
64 | cnt -= 1; |
65 | #endif |
66 | return cnt; |
67 | } |
68 | |
69 | static void compute_dist_code(struct isal_hufftables *hufftables, uint16_t dist, uint64_t *p_code, uint64_t *p_len) |
70 | { |
71 | assert(dist > IGZIP_DIST_TABLE_SIZE)((void) (0)); |
72 | |
73 | dist -= 1; |
74 | uint32_t msb; |
75 | uint32_t num_extra_bits; |
76 | uint32_t extra_bits; |
77 | uint32_t sym; |
78 | uint32_t len; |
79 | uint32_t code; |
80 | |
81 | msb = bsr(dist); |
82 | assert(msb >= 1)((void) (0)); |
83 | num_extra_bits = msb - 2; |
84 | extra_bits = dist & ((1 << num_extra_bits) - 1); |
85 | dist >>= num_extra_bits; |
86 | sym = dist + 2 * num_extra_bits; |
87 | assert(sym < 30)((void) (0)); |
88 | code = hufftables->dcodes[sym - IGZIP_DECODE_OFFSET]; |
89 | len = hufftables->dcodes_sizes[sym - IGZIP_DECODE_OFFSET]; |
90 | *p_code = code | (extra_bits << len); |
91 | *p_len = len + num_extra_bits; |
92 | } |
93 | |
94 | static inline void get_dist_code(struct isal_hufftables *hufftables, uint32_t dist, uint64_t *code, uint64_t *len) |
95 | { |
96 | if (dist < 1) |
97 | dist = 0; |
98 | assert(dist >= 1)((void) (0)); |
99 | assert(dist <= 32768)((void) (0)); |
100 | if (dist <= IGZIP_DIST_TABLE_SIZE) { |
101 | uint64_t code_len; |
102 | code_len = hufftables->dist_table[dist - 1]; |
103 | *code = code_len >> 5; |
104 | *len = code_len & 0x1F; |
105 | } else { |
106 | compute_dist_code(hufftables, dist, code, len); |
107 | } |
108 | } |
109 | |
110 | static inline void get_len_code(struct isal_hufftables *hufftables, uint32_t length, uint64_t *code, uint64_t *len) |
111 | { |
112 | assert(length >= 3)((void) (0)); |
113 | assert(length <= 258)((void) (0)); |
114 | |
115 | uint64_t code_len; |
116 | code_len = hufftables->len_table[length - 3]; |
117 | *code = code_len >> 5; |
118 | *len = code_len & 0x1F; |
119 | } |
120 | |
121 | static inline void get_lit_code(struct isal_hufftables *hufftables, uint32_t lit, uint64_t *code, uint64_t *len) |
122 | { |
123 | assert(lit <= 256)((void) (0)); |
124 | |
125 | *code = hufftables->lit_table[lit]; |
126 | *len = hufftables->lit_table_sizes[lit]; |
127 | } |
128 | |
129 | static void compute_dist_icf_code(uint32_t dist, uint32_t *code, uint32_t *extra_bits) |
130 | { |
131 | uint32_t msb; |
132 | uint32_t num_extra_bits; |
133 | |
134 | dist -= 1; |
135 | msb = bsr(dist); |
136 | assert(msb >= 1)((void) (0)); |
137 | num_extra_bits = msb - 2; |
138 | *extra_bits = dist & ((1 << num_extra_bits) - 1); |
| 4 | | The result of the left shift is undefined due to shifting by '4294967295', which is greater or equal to the width of type 'int' |
|
139 | dist >>= num_extra_bits; |
140 | *code = dist + 2 * num_extra_bits; |
141 | assert(*code < 30)((void) (0)); |
142 | } |
143 | |
144 | static inline void get_dist_icf_code(uint32_t dist, uint32_t *code, uint32_t *extra_bits) |
145 | { |
146 | assert(dist >= 1)((void) (0)); |
147 | assert(dist <= 32768)((void) (0)); |
148 | if (dist <= 2) { |
| |
| |
149 | *code = dist - 1; |
150 | *extra_bits = 0; |
151 | } else { |
152 | compute_dist_icf_code(dist, code, extra_bits); |
| 3 | | Calling 'compute_dist_icf_code' | |
|
153 | } |
154 | } |
155 | |
156 | static inline void get_len_icf_code(uint32_t length, uint32_t *code) |
157 | { |
158 | assert(length >= 3)((void) (0)); |
159 | assert(length <= 258)((void) (0)); |
160 | |
161 | *code = length + 254; |
162 | } |
163 | |
164 | static inline void get_lit_icf_code(uint32_t lit, uint32_t *code) |
165 | { |
166 | assert(lit <= 256)((void) (0)); |
167 | |
168 | *code = lit; |
169 | } |
170 | |
171 | |
172 | |
173 | |
174 | static inline uint32_t compute_hash(uint32_t data) |
175 | { |
176 | #ifdef __SSE4_2__ |
177 | |
178 | return _mm_crc32_u32(0, data); |
179 | |
180 | #else |
181 | |
182 | return ((uint64_t)data * 0xB2D06057) >> 16; |
183 | |
184 | #endif /* __SSE4_2__ */ |
185 | } |
186 | |
187 | |
188 | |
189 | |
190 | |
191 | |
192 | |
193 | |
194 | static inline int compare258(uint8_t * str1, uint8_t * str2, uint32_t max_length) |
195 | { |
196 | uint32_t count; |
197 | uint64_t test; |
198 | uint64_t loop_length; |
199 | |
200 | if(max_length > 258) |
201 | max_length = 258; |
202 | |
203 | loop_length = max_length & ~0x7; |
204 | |
205 | for(count = 0; count < loop_length; count += 8){ |
206 | test = *(uint64_t *) str1; |
207 | test ^= *(uint64_t *) str2; |
208 | if(test != 0) |
209 | return count + tzcnt(test); |
210 | str1 += 8; |
211 | str2 += 8; |
212 | } |
213 | |
214 | switch(max_length % 8){ |
215 | |
216 | case 7: |
217 | if(*str1++ != *str2++) |
218 | return count; |
219 | count++; |
220 | case 6: |
221 | if(*str1++ != *str2++) |
222 | return count; |
223 | count++; |
224 | case 5: |
225 | if(*str1++ != *str2++) |
226 | return count; |
227 | count++; |
228 | case 4: |
229 | if(*str1++ != *str2++) |
230 | return count; |
231 | count++; |
232 | case 3: |
233 | if(*str1++ != *str2++) |
234 | return count; |
235 | count++; |
236 | case 2: |
237 | if(*str1++ != *str2++) |
238 | return count; |
239 | count++; |
240 | case 1: |
241 | if(*str1 != *str2) |
242 | return count; |
243 | count++; |
244 | } |
245 | |
246 | return count; |
247 | } |