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 #if __x86_64__ || __i386__ || _M_X64 || _M_IX86 36 #ifdef _MSC_VER 37 # include <intrin.h> 38 # define inline __inline 39 #else 40 # include <x86intrin.h> 41 #endif 42 #else 43 # define inline __inline 44 #endif //__x86_64__ || __i386__ || _M_X64 || _M_IX86 45 46 static inline uint32_t bsr(uint32_t val) 47 { 48 uint32_t msb; 49 #ifdef __LZCNT__ 50 msb = 16 - __lzcnt16(val); 51 #else 52 for(msb = 0; val > 0; val >>= 1) 53 msb++; 54 #endif 55 return msb; 56 } 57 58 static inline uint32_t tzbytecnt(uint64_t val) 59 { 60 uint32_t cnt; 61 62 #ifdef __BMI__ 63 cnt = __tzcnt_u64(val); 64 cnt = cnt / 8; 65 #elif defined(__x86_64__) 66 67 cnt = (val == 0)? 64 : __builtin_ctzll(val); 68 cnt = cnt / 8; 69 70 #else 71 for(cnt = 8; val > 0; val <<= 8) 72 cnt -= 1; 73 #endif 74 return cnt; 75 } 76 77 static void compute_dist_code(struct isal_hufftables *hufftables, uint16_t dist, uint64_t *p_code, uint64_t *p_len) 78 { 79 assert(dist > IGZIP_DIST_TABLE_SIZE); 80 81 dist -= 1; 82 uint32_t msb; 83 uint32_t num_extra_bits; 84 uint32_t extra_bits; 85 uint32_t sym; 86 uint32_t len; 87 uint32_t code; 88 89 msb = bsr(dist); 90 assert(msb >= 1); 91 num_extra_bits = msb - 2; 92 extra_bits = dist & ((1 << num_extra_bits) - 1); 93 dist >>= num_extra_bits; 94 sym = dist + 2 * num_extra_bits; 95 assert(sym < 30); 96 code = hufftables->dcodes[sym - IGZIP_DECODE_OFFSET]; 97 len = hufftables->dcodes_sizes[sym - IGZIP_DECODE_OFFSET]; 98 *p_code = code | (extra_bits << len); 99 *p_len = len + num_extra_bits; 100 } 101 102 static inline void get_dist_code(struct isal_hufftables *hufftables, uint32_t dist, uint64_t *code, uint64_t *len) 103 { 104 if (dist < 1) 105 dist = 0; 106 assert(dist >= 1); 107 assert(dist <= 32768); 108 if (dist <= IGZIP_DIST_TABLE_SIZE) { 109 uint64_t code_len; 110 code_len = hufftables->dist_table[dist - 1]; 111 *code = code_len >> 5; 112 *len = code_len & 0x1F; 113 } else { 114 compute_dist_code(hufftables, dist, code, len); 115 } 116 } 117 118 static inline void get_len_code(struct isal_hufftables *hufftables, uint32_t length, uint64_t *code, uint64_t *len) 119 { 120 assert(length >= 3); 121 assert(length <= 258); 122 123 uint64_t code_len; 124 code_len = hufftables->len_table[length - 3]; 125 *code = code_len >> 5; 126 *len = code_len & 0x1F; 127 } 128 129 static inline void get_lit_code(struct isal_hufftables *hufftables, uint32_t lit, uint64_t *code, uint64_t *len) 130 { 131 assert(lit <= 256); 132 133 *code = hufftables->lit_table[lit]; 134 *len = hufftables->lit_table_sizes[lit]; 135 } 136 137 static void compute_dist_icf_code(uint32_t dist, uint32_t *code, uint32_t *extra_bits) 138 { 139 uint32_t msb; 140 uint32_t num_extra_bits; 141 142 dist -= 1; 143 msb = bsr(dist); 144 assert(msb >= 1); 145 num_extra_bits = msb - 2; 146 *extra_bits = dist & ((1 << num_extra_bits) - 1); 147 dist >>= num_extra_bits; 148 *code = dist + 2 * num_extra_bits; 149 assert(*code < 30); 150 } 151 152 static inline void get_dist_icf_code(uint32_t dist, uint32_t *code, uint32_t *extra_bits) 153 { 154 assert(dist >= 1); 155 assert(dist <= 32768); 156 if (dist <= 2) { 157 *code = dist - 1; 158 *extra_bits = 0; 159 } else { 160 compute_dist_icf_code(dist, code, extra_bits); 161 } 162 } 163 164 static inline void get_len_icf_code(uint32_t length, uint32_t *code) 165 { 166 assert(length >= 3); 167 assert(length <= 258); 168 169 *code = length + 254; 170 } 171 172 static inline void get_lit_icf_code(uint32_t lit, uint32_t *code) 173 { 174 assert(lit <= 256); 175 176 *code = lit; 177 } 178 179 /** 180 * @brief Returns a hash of the first 3 bytes of input data. 181 */ 182 static inline uint32_t compute_hash(uint32_t data) 183 { 184 #ifdef __SSE4_2__ 185 186 return _mm_crc32_u32(0, data); 187 188 #else 189 uint64_t hash; 190 /* Use multiplication to create a hash, 0xBDD06057 is a prime number */ 191 hash = data; 192 hash *= 0xB2D06057; 193 hash >>= 16; 194 hash *= 0xB2D06057; 195 hash >>= 16; 196 197 return hash; 198 199 #endif /* __SSE4_2__ */ 200 } 201 202 #define PROD1 0xFFFFE84B 203 #define PROD2 0xFFFF97B1 204 static inline uint32_t compute_hash_mad(uint32_t data) 205 { 206 int16_t data_low; 207 int16_t data_high; 208 209 data_low = data; 210 data_high = data >> 16; 211 data = PROD1 * data_low + PROD2 * data_high; 212 213 data_low = data; 214 data_high = data >> 16; 215 data = PROD1 * data_low + PROD2 * data_high; 216 217 return data; 218 } 219 220 static inline uint32_t compute_long_hash(uint64_t data) { 221 222 return compute_hash(data >> 32)^compute_hash(data); 223 } 224 225 /** 226 * @brief Returns how long str1 and str2 have the same symbols. 227 * @param str1: First input string. 228 * @param str2: Second input string. 229 * @param max_length: length of the smaller string. 230 */ 231 static inline int compare258(uint8_t * str1, uint8_t * str2, uint32_t max_length) 232 { 233 uint32_t count; 234 uint64_t test; 235 uint64_t loop_length; 236 237 if(max_length > 258) 238 max_length = 258; 239 240 loop_length = max_length & ~0x7; 241 242 for(count = 0; count < loop_length; count += 8){ 243 test = *(uint64_t *) str1; 244 test ^= *(uint64_t *) str2; 245 if(test != 0) 246 return count + tzbytecnt(test); 247 str1 += 8; 248 str2 += 8; 249 } 250 251 switch(max_length % 8){ 252 253 case 7: 254 if(*str1++ != *str2++) 255 return count; 256 count++; 257 case 6: 258 if(*str1++ != *str2++) 259 return count; 260 count++; 261 case 5: 262 if(*str1++ != *str2++) 263 return count; 264 count++; 265 case 4: 266 if(*str1++ != *str2++) 267 return count; 268 count++; 269 case 3: 270 if(*str1++ != *str2++) 271 return count; 272 count++; 273 case 2: 274 if(*str1++ != *str2++) 275 return count; 276 count++; 277 case 1: 278 if(*str1 != *str2) 279 return count; 280 count++; 281 } 282 283 return count; 284 } 285