]>
git.proxmox.com Git - ceph.git/blob - ceph/src/isa-l/igzip/huffman.h
1 /**********************************************************************
2 Copyright(c) 2011-2016 Intel Corporation All rights reserved.
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions
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
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.
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 **********************************************************************/
33 #include "igzip_lib.h"
37 # define inline __inline
39 # include <x86intrin.h>
42 static inline uint32_t bsr(uint32_t val
)
46 msb
= 16 - __lzcnt16(val
);
48 for(msb
= 0; val
> 0; val
>>= 1)
54 static inline uint32_t tzcnt(uint64_t val
)
60 cnt
= __builtin_ctzll(val
) / 8;//__tzcnt_u64(val);
63 for(cnt
= 8; val
> 0; val
<<= 8)
69 static void compute_dist_code(struct isal_hufftables
*hufftables
, uint16_t dist
, uint64_t *p_code
, uint64_t *p_len
)
71 assert(dist
> IGZIP_DIST_TABLE_SIZE
);
75 uint32_t num_extra_bits
;
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
;
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
;
94 static inline void get_dist_code(struct isal_hufftables
*hufftables
, uint32_t dist
, uint64_t *code
, uint64_t *len
)
99 assert(dist
<= 32768);
100 if (dist
<= IGZIP_DIST_TABLE_SIZE
) {
102 code_len
= hufftables
->dist_table
[dist
- 1];
103 *code
= code_len
>> 5;
104 *len
= code_len
& 0x1F;
106 compute_dist_code(hufftables
, dist
, code
, len
);
110 static inline void get_len_code(struct isal_hufftables
*hufftables
, uint32_t length
, uint64_t *code
, uint64_t *len
)
113 assert(length
<= 258);
116 code_len
= hufftables
->len_table
[length
- 3];
117 *code
= code_len
>> 5;
118 *len
= code_len
& 0x1F;
121 static inline void get_lit_code(struct isal_hufftables
*hufftables
, uint32_t lit
, uint64_t *code
, uint64_t *len
)
125 *code
= hufftables
->lit_table
[lit
];
126 *len
= hufftables
->lit_table_sizes
[lit
];
129 static void compute_dist_icf_code(uint32_t dist
, uint32_t *code
, uint32_t *extra_bits
)
132 uint32_t num_extra_bits
;
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
;
144 static inline void get_dist_icf_code(uint32_t dist
, uint32_t *code
, uint32_t *extra_bits
)
147 assert(dist
<= 32768);
152 compute_dist_icf_code(dist
, code
, extra_bits
);
156 static inline void get_len_icf_code(uint32_t length
, uint32_t *code
)
159 assert(length
<= 258);
161 *code
= length
+ 254;
164 static inline void get_lit_icf_code(uint32_t lit
, uint32_t *code
)
172 * @brief Returns a hash of the first 3 bytes of input data.
174 static inline uint32_t compute_hash(uint32_t data
)
178 return _mm_crc32_u32(0, data
);
181 /* Use multiplication to create a hash, 0xBDD06057 is a prime number */
182 return ((uint64_t)data
* 0xB2D06057) >> 16;
184 #endif /* __SSE4_2__ */
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.
194 static inline int compare258(uint8_t * str1
, uint8_t * str2
, uint32_t max_length
)
198 uint64_t loop_length
;
203 loop_length
= max_length
& ~0x7;
205 for(count
= 0; count
< loop_length
; count
+= 8){
206 test
= *(uint64_t *) str1
;
207 test
^= *(uint64_t *) str2
;
209 return count
+ tzcnt(test
);
214 switch(max_length
% 8){
217 if(*str1
++ != *str2
++)
221 if(*str1
++ != *str2
++)
225 if(*str1
++ != *str2
++)
229 if(*str1
++ != *str2
++)
233 if(*str1
++ != *str2
++)
237 if(*str1
++ != *str2
++)