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 33 #include <stdint.h> 34 #include <string.h> 35 #include <assert.h> 36 #include "igzip_lib.h" 37 #include "bitbuf2.h" 38 39 #if __x86_64__ || __i386__ || _M_X64 || _M_IX86 40 #include <immintrin.h> 41 #ifdef _MSC_VER 42 #include <intrin.h> 43 #else 44 #include <x86intrin.h> 45 #endif 46 #endif //__x86_64__ || __i386__ || _M_X64 || _M_IX86 47 48 #define LIT_LEN ISAL_DEF_LIT_LEN_SYMBOLS 49 #define DIST_LEN ISAL_DEF_DIST_SYMBOLS 50 #define CODE_LEN_CODES 19 51 #define HUFF_LEN 19 52 #ifdef LONGER_HUFFTABLE 53 #define DCODE_OFFSET 26 54 #else 55 #define DCODE_OFFSET 0 56 #endif 57 #define DYN_HDR_START_LEN 17 58 #define MAX_HISTHEAP_SIZE LIT_LEN 59 #define MAX_HUFF_TREE_DEPTH 15 60 #define D IGZIP_HIST_SIZE /* Amount of history */ 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 67 #define SHORT_DIST_TABLE_SIZE 2 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 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) 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 102 /** 103 * @brief Structure used to store huffman codes 104 */ 105 struct huff_code { 106 union { 107 struct { 108 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ 109 uint32_t code_and_extra : 24; 110 uint32_t length2 : 8; 111 #else 112 uint32_t length2 : 8; 113 uint32_t code_and_extra : 24; 114 #endif 115 }; 116 117 struct { 118 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ 119 uint16_t code; 120 uint8_t extra_bit_count; 121 uint8_t length; 122 #else 123 uint8_t length; 124 uint8_t extra_bit_count; 125 uint16_t code; 126 #endif 127 }; 128 129 uint32_t code_and_length; 130 }; 131 }; 132 133 struct tree_node { 134 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ 135 uint32_t child; 136 uint32_t depth; 137 #else 138 uint32_t depth; 139 uint32_t child; 140 #endif 141 }; 142 143 struct heap_tree { 144 union { 145 uint64_t heap[HEAP_TREE_SIZE]; 146 uint64_t code_len_count[MAX_HUFF_TREE_DEPTH + 1]; 147 struct tree_node tree[HEAP_TREE_SIZE]; 148 }; 149 }; 150 151 struct rl_code { 152 uint8_t code; 153 uint8_t extra_bits; 154 }; 155 156 struct hufftables_icf { 157 union { 158 struct { 159 struct huff_code dist_lit_table[288]; 160 struct huff_code len_table[256]; 161 }; 162 163 struct { 164 struct huff_code dist_table[31]; 165 struct huff_code lit_len_table[513]; 166 }; 167 }; 168 }; 169 170 /** 171 * @brief Creates a representation of the huffman code from a histogram used to 172 * decompress the intermediate compression format. 173 * 174 * @param bb: bitbuf structure where the header huffman code header is written 175 * @param hufftables: output huffman code representation 176 * @param hist: histogram used to generate huffman code 177 * @param end_of_block: flag whether this is the final huffman code 178 * 179 * @returns Returns the length in bits of the block with histogram hist encoded 180 * with the set hufftable 181 */ 182 uint64_t 183 create_hufftables_icf(struct BitBuf2 *bb, struct hufftables_icf *hufftables, 184 struct isal_mod_hist *hist, uint32_t end_of_block); 185 186 #endif 187