[ceph.git] / ceph / src / isa-l / igzip / huffman.h

/**********************************************************************
  Copyright(c) 2011-2016 Intel Corporation All rights reserved.

  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions
  are met:
    * Redistributions of source code must retain the above copyright
      notice, this list of conditions and the following disclaimer.
    * Redistributions in binary form must reproduce the above copyright
      notice, this list of conditions and the following disclaimer in
      the documentation and/or other materials provided with the
      distribution.
    * Neither the name of Intel Corporation nor the names of its
      contributors may be used to endorse or promote products derived
      from this software without specific prior written permission.

  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
**********************************************************************/

#include <stdint.h>
#include <stdlib.h>
#include <assert.h>
#include "igzip_lib.h"

#ifdef _MSC_VER
# include <intrin.h>
# define inline __inline
#else
# include <x86intrin.h>
#endif

static inline uint32_t bsr(uint32_t val)
{
	uint32_t msb;
#ifdef __LZCNT__
	msb = 16 - __lzcnt16(val);
#else
	for(msb = 0; val > 0; val >>= 1)
		msb++;
#endif
	return msb;
}

static inline uint32_t tzcnt(uint64_t val)
{
	uint32_t cnt;

#ifdef __x86_64__

	cnt = __builtin_ctzll(val) / 8;//__tzcnt_u64(val);

#else
	for(cnt = 8; val > 0; val <<= 8)
		cnt -= 1;
#endif
	return cnt;
}

static void compute_dist_code(struct isal_hufftables *hufftables, uint16_t dist, uint64_t *p_code, uint64_t *p_len)
{
	assert(dist > IGZIP_DIST_TABLE_SIZE);

	dist -= 1;
	uint32_t msb;
	uint32_t num_extra_bits;
	uint32_t extra_bits;
	uint32_t sym;
	uint32_t len;
	uint32_t code;

	msb = bsr(dist);
	assert(msb >= 1);
	num_extra_bits = msb - 2;
	extra_bits = dist & ((1 << num_extra_bits) - 1);
	dist >>= num_extra_bits;
	sym = dist + 2 * num_extra_bits;
	assert(sym < 30);
	code = hufftables->dcodes[sym - IGZIP_DECODE_OFFSET];
	len = hufftables->dcodes_sizes[sym - IGZIP_DECODE_OFFSET];
	*p_code = code | (extra_bits << len);
	*p_len = len + num_extra_bits;
}

static inline void get_dist_code(struct isal_hufftables *hufftables, uint32_t dist, uint64_t *code, uint64_t *len)
{
	if (dist < 1)
		dist = 0;
	assert(dist >= 1);
	assert(dist <= 32768);
	if (dist <= IGZIP_DIST_TABLE_SIZE) {
		uint64_t code_len;
		code_len = hufftables->dist_table[dist - 1];
		*code = code_len >> 5;
		*len = code_len & 0x1F;
	} else {
		compute_dist_code(hufftables, dist, code, len);
	}
}

static inline void get_len_code(struct isal_hufftables *hufftables, uint32_t length, uint64_t *code, uint64_t *len)
{
	assert(length >= 3);
	assert(length <= 258);

	uint64_t code_len;
	code_len = hufftables->len_table[length - 3];
	*code = code_len >> 5;
	*len = code_len & 0x1F;
}

static inline void get_lit_code(struct isal_hufftables *hufftables, uint32_t lit, uint64_t *code, uint64_t *len)
{
	assert(lit <= 256);

	*code = hufftables->lit_table[lit];
	*len = hufftables->lit_table_sizes[lit];
}

static void compute_dist_icf_code(uint32_t dist, uint32_t *code, uint32_t *extra_bits)
{
	uint32_t msb;
	uint32_t num_extra_bits;

	dist -= 1;
	msb = bsr(dist);
	assert(msb >= 1);
	num_extra_bits = msb - 2;
	*extra_bits = dist & ((1 << num_extra_bits) - 1);
	dist >>= num_extra_bits;
	*code = dist + 2 * num_extra_bits;
	assert(*code < 30);
}

static inline void get_dist_icf_code(uint32_t dist, uint32_t *code, uint32_t *extra_bits)
{
	assert(dist >= 1);
	assert(dist <= 32768);
	if (dist <= 2) {
		*code = dist - 1;
		*extra_bits = 0;
	} else {
		compute_dist_icf_code(dist, code, extra_bits);
	}
}

static inline void get_len_icf_code(uint32_t length, uint32_t *code)
{
	assert(length >= 3);
	assert(length <= 258);

	*code = length + 254;
}

static inline void get_lit_icf_code(uint32_t lit, uint32_t *code)
{
	assert(lit <= 256);

	*code = lit;
}

/**
 * @brief Returns a hash of the first 3 bytes of input data.
 */
static inline uint32_t compute_hash(uint32_t data)
{
#ifdef __SSE4_2__

	return _mm_crc32_u32(0, data);

#else
	/* Use multiplication to create a hash, 0xBDD06057 is a prime number */
	return ((uint64_t)data * 0xB2D06057) >> 16;

#endif /* __SSE4_2__ */
}


/**
 * @brief Returns how long str1 and str2 have the same symbols.
 * @param str1: First input string.
 * @param str2: Second input string.
 * @param max_length: length of the smaller string.
 */
static inline int compare258(uint8_t * str1, uint8_t * str2, uint32_t max_length)
{
	uint32_t count;
	uint64_t test;
	uint64_t loop_length;

	if(max_length > 258)
		max_length = 258;

	loop_length = max_length & ~0x7;

	for(count = 0; count < loop_length; count += 8){
		test = *(uint64_t *) str1;
		test ^= *(uint64_t *) str2;
		if(test != 0)
			return count + tzcnt(test);
		str1 += 8;
		str2 += 8;
	}

	switch(max_length % 8){

	case 7:
		if(*str1++ != *str2++)
			return count;
		count++;
	case 6:
		if(*str1++ != *str2++)
			return count;
		count++;
	case 5:
		if(*str1++ != *str2++)
			return count;
		count++;
	case 4:
		if(*str1++ != *str2++)
			return count;
		count++;
	case 3:
		if(*str1++ != *str2++)
			return count;
		count++;
	case 2:
		if(*str1++ != *str2++)
			return count;
		count++;
	case 1:
		if(*str1 != *str2)
			return count;
		count++;
	}

	return count;
}
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];
224ce89b WB	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	}