]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /********************************************************************** |
2 | Copyright(c) 2011-2016 Intel Corporation All rights reserved. | |
3 | ||
4 | Redistribution and use in source and binary forms, with or without | |
5 | modification, are permitted provided that the following conditions | |
6 | are met: | |
7 | * Redistributions of source code must retain the above copyright | |
8 | notice, this list of conditions and the following disclaimer. | |
9 | * Redistributions in binary form must reproduce the above copyright | |
10 | notice, this list of conditions and the following disclaimer in | |
11 | the documentation and/or other materials provided with the | |
12 | distribution. | |
13 | * Neither the name of Intel Corporation nor the names of its | |
14 | contributors may be used to endorse or promote products derived | |
15 | from this software without specific prior written permission. | |
16 | ||
17 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
18 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
19 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
20 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
21 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
22 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
23 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
24 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
25 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
26 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
27 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
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 | ||
7c673cae FG |
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__ | |
59 | ||
60 | cnt = __builtin_ctzll(val) / 8;//__tzcnt_u64(val); | |
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 | { | |
224ce89b | 71 | assert(dist > IGZIP_DIST_TABLE_SIZE); |
7c673cae FG |
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); | |
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); | |
224ce89b WB |
88 | code = hufftables->dcodes[sym - IGZIP_DECODE_OFFSET]; |
89 | len = hufftables->dcodes_sizes[sym - IGZIP_DECODE_OFFSET]; | |
7c673cae FG |
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); | |
99 | assert(dist <= 32768); | |
224ce89b | 100 | if (dist <= IGZIP_DIST_TABLE_SIZE) { |
7c673cae FG |
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); | |
113 | assert(length <= 258); | |
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); | |
124 | ||
125 | *code = hufftables->lit_table[lit]; | |
126 | *len = hufftables->lit_table_sizes[lit]; | |
127 | } | |
128 | ||
224ce89b WB |
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); | |
137 | num_extra_bits = msb - 2; | |
138 | *extra_bits = dist & ((1 << num_extra_bits) - 1); | |
139 | dist >>= num_extra_bits; | |
140 | *code = dist + 2 * num_extra_bits; | |
141 | assert(*code < 30); | |
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); | |
147 | assert(dist <= 32768); | |
148 | if (dist <= 2) { | |
149 | *code = dist - 1; | |
150 | *extra_bits = 0; | |
151 | } else { | |
152 | compute_dist_icf_code(dist, code, extra_bits); | |
153 | } | |
154 | } | |
155 | ||
156 | static inline void get_len_icf_code(uint32_t length, uint32_t *code) | |
157 | { | |
158 | assert(length >= 3); | |
159 | assert(length <= 258); | |
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); | |
167 | ||
168 | *code = lit; | |
169 | } | |
170 | ||
7c673cae FG |
171 | /** |
172 | * @brief Returns a hash of the first 3 bytes of input data. | |
173 | */ | |
174 | static inline uint32_t compute_hash(uint32_t data) | |
175 | { | |
224ce89b | 176 | #ifdef __SSE4_2__ |
7c673cae FG |
177 | |
178 | return _mm_crc32_u32(0, data); | |
179 | ||
180 | #else | |
181 | /* Use multiplication to create a hash, 0xBDD06057 is a prime number */ | |
182 | return ((uint64_t)data * 0xB2D06057) >> 16; | |
183 | ||
224ce89b | 184 | #endif /* __SSE4_2__ */ |
7c673cae FG |
185 | } |
186 | ||
187 | ||
188 | /** | |
189 | * @brief Returns how long str1 and str2 have the same symbols. | |
190 | * @param str1: First input string. | |
191 | * @param str2: Second input string. | |
192 | * @param max_length: length of the smaller string. | |
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 | } |