[ceph.git] / ceph / src / isa-l / igzip / huff_codes.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.
**********************************************************************/

#ifndef HUFF_CODES_H
#define HUFF_CODES_H

#include <stdint.h>
#include <string.h>
#include <assert.h>
#include "igzip_lib.h"
#include "bitbuf2.h"

#if __x86_64__  || __i386__ || _M_X64 || _M_IX86
# include <immintrin.h>
#ifdef _MSC_VER
# include <intrin.h>
#else
# include <x86intrin.h>
#endif
#endif //__x86_64__  || __i386__ || _M_X64 || _M_IX86

#define LIT_LEN ISAL_DEF_LIT_LEN_SYMBOLS
#define DIST_LEN ISAL_DEF_DIST_SYMBOLS
#define CODE_LEN_CODES 19
#define HUFF_LEN 19
#ifdef LONGER_HUFFTABLE
# define DCODE_OFFSET 26
#else
# define DCODE_OFFSET 0
#endif
#define DYN_HDR_START_LEN 17
#define MAX_HISTHEAP_SIZE LIT_LEN
#define MAX_HUFF_TREE_DEPTH 15
#define D      IGZIP_HIST_SIZE	/* Amount of history */

#define MAX_DEFLATE_CODE_LEN 15
#define MAX_SAFE_LIT_CODE_LEN 13
#define MAX_SAFE_DIST_CODE_LEN 12

#define LONG_DIST_TABLE_SIZE 8192
#define SHORT_DIST_TABLE_SIZE 2
#define LEN_TABLE_SIZE 256
#define LIT_TABLE_SIZE 257
#define LAST_BLOCK 1

#define LEN_EXTRA_BITS_START 264
#define LEN_EXTRA_BITS_INTERVAL 4
#define DIST_EXTRA_BITS_START 3
#define DIST_EXTRA_BITS_INTERVAL 2

#define INVALID_LIT_LEN_HUFFCODE 1
#define INVALID_DIST_HUFFCODE 1
#define INVALID_HUFFCODE 1

#define HASH8K_HASH_MASK  (IGZIP_HASH8K_HASH_SIZE - 1)
#define HASH_HIST_HASH_MASK  (IGZIP_HASH_HIST_SIZE - 1)
#define HASH_MAP_HASH_MASK  (IGZIP_HASH_MAP_HASH_SIZE - 1)

#define LVL0_HASH_MASK  (IGZIP_LVL0_HASH_SIZE - 1)
#define LVL1_HASH_MASK  (IGZIP_LVL1_HASH_SIZE - 1)
#define LVL2_HASH_MASK  (IGZIP_LVL2_HASH_SIZE - 1)
#define LVL3_HASH_MASK  (IGZIP_LVL3_HASH_SIZE - 1)
#define SHORTEST_MATCH  4

#define LENGTH_BITS 5
#define FREQ_SHIFT 16
#define FREQ_MASK_HI (0xFFFFFFFFFFFF0000)
#define DEPTH_SHIFT 24
#define DEPTH_MASK 0x7F
#define DEPTH_MASK_HI (DEPTH_MASK << DEPTH_SHIFT)
#define DEPTH_1       (1 << DEPTH_SHIFT)
#define HEAP_TREE_SIZE (3*MAX_HISTHEAP_SIZE + 1)
#define HEAP_TREE_NODE_START (HEAP_TREE_SIZE-1)
#define MAX_BL_CODE_LEN 7

/**
 * @brief Structure used to store huffman codes
 */
struct huff_code {
	union {
                struct {
                        uint32_t code_and_extra:24;
                        uint32_t length2:8;
                };

		struct {
			uint16_t code;
			uint8_t extra_bit_count;
			uint8_t length;
		};

		uint32_t code_and_length;
	};
};

struct tree_node {
	uint32_t child;
	uint32_t depth;
};

struct heap_tree {
	union {
		uint64_t heap[HEAP_TREE_SIZE];
		uint64_t code_len_count[MAX_HUFF_TREE_DEPTH + 1];
		struct tree_node tree[HEAP_TREE_SIZE];
	};
};

struct rl_code {
	uint8_t code;
	uint8_t extra_bits;
};

struct hufftables_icf {
	union {
		struct {
			struct huff_code dist_lit_table[288];
			struct huff_code len_table[256];
		};

		struct {
			struct huff_code dist_table[31];
			struct huff_code lit_len_table[513];
		};
	};
};

/**
 * @brief Creates a representation of the huffman code from a histogram used to
 * decompress the intermediate compression format.
 *
 * @param bb: bitbuf structure where the header huffman code header is written
 * @param hufftables: output huffman code representation
 * @param hist: histogram used to generat huffman code
 * @param end_of_block: flag whether this is the final huffman code
 *
 * @returns Returns the length in bits of the block with histogram hist encoded
 * with the set hufftable
 */
uint64_t
create_hufftables_icf(struct BitBuf2 *bb, struct hufftables_icf * hufftables,
                  struct isal_mod_hist *hist, uint32_t end_of_block);

#endif
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	#ifndef HUFF_CODES_H
	31	#define HUFF_CODES_H
	32
7c673cae FG	33	#include <stdint.h>
	34	#include <string.h>
	35	#include <assert.h>
	36	#include "igzip_lib.h"
	37	#include "bitbuf2.h"
	38
f91f0fd5 TL	39	#if __x86_64__ \|\| __i386__ \|\| _M_X64 \|\| _M_IX86
f91f0fd5 TL	40	# include <immintrin.h>
7c673cae FG	41	#ifdef _MSC_VER
	42	# include <intrin.h>
	43	#else
	44	# include <x86intrin.h>
	45	#endif
f91f0fd5	46	#endif //__x86_64__ \|\| __i386__ \|\| _M_X64 \|\| _M_IX86
7c673cae	47
224ce89b WB	48	#define LIT_LEN ISAL_DEF_LIT_LEN_SYMBOLS
224ce89b WB	49	#define DIST_LEN ISAL_DEF_DIST_SYMBOLS
7c673cae FG	50	#define CODE_LEN_CODES 19
	51	#define HUFF_LEN 19
	52	#ifdef LONGER_HUFFTABLE
	53	# define DCODE_OFFSET 26
	54	#else
224ce89b	55	# define DCODE_OFFSET 0
7c673cae FG	56	#endif
	57	#define DYN_HDR_START_LEN 17
	58	#define MAX_HISTHEAP_SIZE LIT_LEN
	59	#define MAX_HUFF_TREE_DEPTH 15
224ce89b	60	#define D IGZIP_HIST_SIZE /* Amount of history */
7c673cae FG	61
	62	#define MAX_DEFLATE_CODE_LEN 15
	63	#define MAX_SAFE_LIT_CODE_LEN 13
	64	#define MAX_SAFE_DIST_CODE_LEN 12
	65
	66	#define LONG_DIST_TABLE_SIZE 8192
224ce89b	67	#define SHORT_DIST_TABLE_SIZE 2
7c673cae FG	68	#define LEN_TABLE_SIZE 256
	69	#define LIT_TABLE_SIZE 257
	70	#define LAST_BLOCK 1
	71
	72	#define LEN_EXTRA_BITS_START 264
	73	#define LEN_EXTRA_BITS_INTERVAL 4
	74	#define DIST_EXTRA_BITS_START 3
	75	#define DIST_EXTRA_BITS_INTERVAL 2
	76
	77	#define INVALID_LIT_LEN_HUFFCODE 1
	78	#define INVALID_DIST_HUFFCODE 1
	79	#define INVALID_HUFFCODE 1
	80
f91f0fd5 TL	81	#define HASH8K_HASH_MASK (IGZIP_HASH8K_HASH_SIZE - 1)
	82	#define HASH_HIST_HASH_MASK (IGZIP_HASH_HIST_SIZE - 1)
	83	#define HASH_MAP_HASH_MASK (IGZIP_HASH_MAP_HASH_SIZE - 1)
	84
	85	#define LVL0_HASH_MASK (IGZIP_LVL0_HASH_SIZE - 1)
	86	#define LVL1_HASH_MASK (IGZIP_LVL1_HASH_SIZE - 1)
	87	#define LVL2_HASH_MASK (IGZIP_LVL2_HASH_SIZE - 1)
	88	#define LVL3_HASH_MASK (IGZIP_LVL3_HASH_SIZE - 1)
224ce89b WB	89	#define SHORTEST_MATCH 4
	90
	91	#define LENGTH_BITS 5
	92	#define FREQ_SHIFT 16
	93	#define FREQ_MASK_HI (0xFFFFFFFFFFFF0000)
	94	#define DEPTH_SHIFT 24
	95	#define DEPTH_MASK 0x7F
	96	#define DEPTH_MASK_HI (DEPTH_MASK << DEPTH_SHIFT)
	97	#define DEPTH_1 (1 << DEPTH_SHIFT)
	98	#define HEAP_TREE_SIZE (3*MAX_HISTHEAP_SIZE + 1)
	99	#define HEAP_TREE_NODE_START (HEAP_TREE_SIZE-1)
	100	#define MAX_BL_CODE_LEN 7
	101
7c673cae FG	102	/**
	103	* @brief Structure used to store huffman codes
	104	*/
	105	struct huff_code {
224ce89b	106	union {
f91f0fd5 TL	107	struct {
	108	uint32_t code_and_extra:24;
	109	uint32_t length2:8;
	110	};
	111
224ce89b WB	112	struct {
	113	uint16_t code;
	114	uint8_t extra_bit_count;
	115	uint8_t length;
	116	};
f91f0fd5 TL	117
f91f0fd5 TL	118	uint32_t code_and_length;
224ce89b	119	};
7c673cae FG	120	};
7c673cae FG	121
224ce89b WB	122	struct tree_node {
	123	uint32_t child;
	124	uint32_t depth;
7c673cae FG	125	};
7c673cae FG	126
224ce89b WB	127	struct heap_tree {
	128	union {
	129	uint64_t heap[HEAP_TREE_SIZE];
	130	uint64_t code_len_count[MAX_HUFF_TREE_DEPTH + 1];
	131	struct tree_node tree[HEAP_TREE_SIZE];
	132	};
7c673cae FG	133	};
7c673cae FG	134
224ce89b WB	135	struct rl_code {
	136	uint8_t code;
	137	uint8_t extra_bits;
7c673cae FG	138	};
7c673cae FG	139
224ce89b	140	struct hufftables_icf {
f91f0fd5 TL	141	union {
	142	struct {
	143	struct huff_code dist_lit_table[288];
	144	struct huff_code len_table[256];
	145	};
7c673cae	146
f91f0fd5 TL	147	struct {
	148	struct huff_code dist_table[31];
	149	struct huff_code lit_len_table[513];
	150	};
	151	};
	152	};
224ce89b WB	153
	154	/**
	155	* @brief Creates a representation of the huffman code from a histogram used to
	156	* decompress the intermediate compression format.
	157	*
	158	* @param bb: bitbuf structure where the header huffman code header is written
	159	* @param hufftables: output huffman code representation
	160	* @param hist: histogram used to generat huffman code
	161	* @param end_of_block: flag whether this is the final huffman code
f91f0fd5 TL	162	*
	163	* @returns Returns the length in bits of the block with histogram hist encoded
	164	* with the set hufftable
224ce89b	165	*/
f91f0fd5	166	uint64_t
224ce89b WB	167	create_hufftables_icf(struct BitBuf2 bb, struct hufftables_icf hufftables,
	168	struct isal_mod_hist *hist, uint32_t end_of_block);
	169
7c673cae	170	#endif