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 <immintrin.h> 31 #include <stdint.h> 32 #include <string.h> 33 #include <assert.h> 34 #include "igzip_lib.h" 35 #include "huff_codes.h" 36 #include "huffman.h" 37 #include "bitbuf2.h" 38 #include "flatten_ll.h" 39 40 /* The order code length codes are written in the dynamic code header. This is 41 * defined in RFC 1951 page 13 */ 42 static const uint8_t code_length_code_order[] = 43 { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; 44 45 const uint32_t len_code_extra_bits[] = { 46 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 47 0x1, 0x1, 0x1, 0x1, 0x2, 0x2, 0x2, 0x2, 48 0x3, 0x3, 0x3, 0x3, 0x4, 0x4, 0x4, 0x4, 49 0x5, 0x5, 0x5, 0x5, 0x0 50 }; 51 52 const uint32_t dist_code_extra_bits[] = { 53 0x0, 0x0, 0x0, 0x0, 0x1, 0x1, 0x2, 0x2, 54 0x3, 0x3, 0x4, 0x4, 0x5, 0x5, 0x6, 0x6, 55 0x7, 0x7, 0x8, 0x8, 0x9, 0x9, 0xa, 0xa, 56 0xb, 0xb, 0xc, 0xc, 0xd, 0xd 57 }; 58 59 struct hufftables_icf static_hufftables = { 60 .lit_len_table = { 61 {{{.code_and_extra = 0x00c,.length2 = 0x8}}}, 62 {{{.code_and_extra = 0x08c,.length2 = 0x8}}}, 63 {{{.code_and_extra = 0x04c,.length2 = 0x8}}}, 64 {{{.code_and_extra = 0x0cc,.length2 = 0x8}}}, 65 {{{.code_and_extra = 0x02c,.length2 = 0x8}}}, 66 {{{.code_and_extra = 0x0ac,.length2 = 0x8}}}, 67 {{{.code_and_extra = 0x06c,.length2 = 0x8}}}, 68 {{{.code_and_extra = 0x0ec,.length2 = 0x8}}}, 69 {{{.code_and_extra = 0x01c,.length2 = 0x8}}}, 70 {{{.code_and_extra = 0x09c,.length2 = 0x8}}}, 71 {{{.code_and_extra = 0x05c,.length2 = 0x8}}}, 72 {{{.code_and_extra = 0x0dc,.length2 = 0x8}}}, 73 {{{.code_and_extra = 0x03c,.length2 = 0x8}}}, 74 {{{.code_and_extra = 0x0bc,.length2 = 0x8}}}, 75 {{{.code_and_extra = 0x07c,.length2 = 0x8}}}, 76 {{{.code_and_extra = 0x0fc,.length2 = 0x8}}}, 77 {{{.code_and_extra = 0x002,.length2 = 0x8}}}, 78 {{{.code_and_extra = 0x082,.length2 = 0x8}}}, 79 {{{.code_and_extra = 0x042,.length2 = 0x8}}}, 80 {{{.code_and_extra = 0x0c2,.length2 = 0x8}}}, 81 {{{.code_and_extra = 0x022,.length2 = 0x8}}}, 82 {{{.code_and_extra = 0x0a2,.length2 = 0x8}}}, 83 {{{.code_and_extra = 0x062,.length2 = 0x8}}}, 84 {{{.code_and_extra = 0x0e2,.length2 = 0x8}}}, 85 {{{.code_and_extra = 0x012,.length2 = 0x8}}}, 86 {{{.code_and_extra = 0x092,.length2 = 0x8}}}, 87 {{{.code_and_extra = 0x052,.length2 = 0x8}}}, 88 {{{.code_and_extra = 0x0d2,.length2 = 0x8}}}, 89 {{{.code_and_extra = 0x032,.length2 = 0x8}}}, 90 {{{.code_and_extra = 0x0b2,.length2 = 0x8}}}, 91 {{{.code_and_extra = 0x072,.length2 = 0x8}}}, 92 {{{.code_and_extra = 0x0f2,.length2 = 0x8}}}, 93 {{{.code_and_extra = 0x00a,.length2 = 0x8}}}, 94 {{{.code_and_extra = 0x08a,.length2 = 0x8}}}, 95 {{{.code_and_extra = 0x04a,.length2 = 0x8}}}, 96 {{{.code_and_extra = 0x0ca,.length2 = 0x8}}}, 97 {{{.code_and_extra = 0x02a,.length2 = 0x8}}}, 98 {{{.code_and_extra = 0x0aa,.length2 = 0x8}}}, 99 {{{.code_and_extra = 0x06a,.length2 = 0x8}}}, 100 {{{.code_and_extra = 0x0ea,.length2 = 0x8}}}, 101 {{{.code_and_extra = 0x01a,.length2 = 0x8}}}, 102 {{{.code_and_extra = 0x09a,.length2 = 0x8}}}, 103 {{{.code_and_extra = 0x05a,.length2 = 0x8}}}, 104 {{{.code_and_extra = 0x0da,.length2 = 0x8}}}, 105 {{{.code_and_extra = 0x03a,.length2 = 0x8}}}, 106 {{{.code_and_extra = 0x0ba,.length2 = 0x8}}}, 107 {{{.code_and_extra = 0x07a,.length2 = 0x8}}}, 108 {{{.code_and_extra = 0x0fa,.length2 = 0x8}}}, 109 {{{.code_and_extra = 0x006,.length2 = 0x8}}}, 110 {{{.code_and_extra = 0x086,.length2 = 0x8}}}, 111 {{{.code_and_extra = 0x046,.length2 = 0x8}}}, 112 {{{.code_and_extra = 0x0c6,.length2 = 0x8}}}, 113 {{{.code_and_extra = 0x026,.length2 = 0x8}}}, 114 {{{.code_and_extra = 0x0a6,.length2 = 0x8}}}, 115 {{{.code_and_extra = 0x066,.length2 = 0x8}}}, 116 {{{.code_and_extra = 0x0e6,.length2 = 0x8}}}, 117 {{{.code_and_extra = 0x016,.length2 = 0x8}}}, 118 {{{.code_and_extra = 0x096,.length2 = 0x8}}}, 119 {{{.code_and_extra = 0x056,.length2 = 0x8}}}, 120 {{{.code_and_extra = 0x0d6,.length2 = 0x8}}}, 121 {{{.code_and_extra = 0x036,.length2 = 0x8}}}, 122 {{{.code_and_extra = 0x0b6,.length2 = 0x8}}}, 123 {{{.code_and_extra = 0x076,.length2 = 0x8}}}, 124 {{{.code_and_extra = 0x0f6,.length2 = 0x8}}}, 125 {{{.code_and_extra = 0x00e,.length2 = 0x8}}}, 126 {{{.code_and_extra = 0x08e,.length2 = 0x8}}}, 127 {{{.code_and_extra = 0x04e,.length2 = 0x8}}}, 128 {{{.code_and_extra = 0x0ce,.length2 = 0x8}}}, 129 {{{.code_and_extra = 0x02e,.length2 = 0x8}}}, 130 {{{.code_and_extra = 0x0ae,.length2 = 0x8}}}, 131 {{{.code_and_extra = 0x06e,.length2 = 0x8}}}, 132 {{{.code_and_extra = 0x0ee,.length2 = 0x8}}}, 133 {{{.code_and_extra = 0x01e,.length2 = 0x8}}}, 134 {{{.code_and_extra = 0x09e,.length2 = 0x8}}}, 135 {{{.code_and_extra = 0x05e,.length2 = 0x8}}}, 136 {{{.code_and_extra = 0x0de,.length2 = 0x8}}}, 137 {{{.code_and_extra = 0x03e,.length2 = 0x8}}}, 138 {{{.code_and_extra = 0x0be,.length2 = 0x8}}}, 139 {{{.code_and_extra = 0x07e,.length2 = 0x8}}}, 140 {{{.code_and_extra = 0x0fe,.length2 = 0x8}}}, 141 {{{.code_and_extra = 0x001,.length2 = 0x8}}}, 142 {{{.code_and_extra = 0x081,.length2 = 0x8}}}, 143 {{{.code_and_extra = 0x041,.length2 = 0x8}}}, 144 {{{.code_and_extra = 0x0c1,.length2 = 0x8}}}, 145 {{{.code_and_extra = 0x021,.length2 = 0x8}}}, 146 {{{.code_and_extra = 0x0a1,.length2 = 0x8}}}, 147 {{{.code_and_extra = 0x061,.length2 = 0x8}}}, 148 {{{.code_and_extra = 0x0e1,.length2 = 0x8}}}, 149 {{{.code_and_extra = 0x011,.length2 = 0x8}}}, 150 {{{.code_and_extra = 0x091,.length2 = 0x8}}}, 151 {{{.code_and_extra = 0x051,.length2 = 0x8}}}, 152 {{{.code_and_extra = 0x0d1,.length2 = 0x8}}}, 153 {{{.code_and_extra = 0x031,.length2 = 0x8}}}, 154 {{{.code_and_extra = 0x0b1,.length2 = 0x8}}}, 155 {{{.code_and_extra = 0x071,.length2 = 0x8}}}, 156 {{{.code_and_extra = 0x0f1,.length2 = 0x8}}}, 157 {{{.code_and_extra = 0x009,.length2 = 0x8}}}, 158 {{{.code_and_extra = 0x089,.length2 = 0x8}}}, 159 {{{.code_and_extra = 0x049,.length2 = 0x8}}}, 160 {{{.code_and_extra = 0x0c9,.length2 = 0x8}}}, 161 {{{.code_and_extra = 0x029,.length2 = 0x8}}}, 162 {{{.code_and_extra = 0x0a9,.length2 = 0x8}}}, 163 {{{.code_and_extra = 0x069,.length2 = 0x8}}}, 164 {{{.code_and_extra = 0x0e9,.length2 = 0x8}}}, 165 {{{.code_and_extra = 0x019,.length2 = 0x8}}}, 166 {{{.code_and_extra = 0x099,.length2 = 0x8}}}, 167 {{{.code_and_extra = 0x059,.length2 = 0x8}}}, 168 {{{.code_and_extra = 0x0d9,.length2 = 0x8}}}, 169 {{{.code_and_extra = 0x039,.length2 = 0x8}}}, 170 {{{.code_and_extra = 0x0b9,.length2 = 0x8}}}, 171 {{{.code_and_extra = 0x079,.length2 = 0x8}}}, 172 {{{.code_and_extra = 0x0f9,.length2 = 0x8}}}, 173 {{{.code_and_extra = 0x005,.length2 = 0x8}}}, 174 {{{.code_and_extra = 0x085,.length2 = 0x8}}}, 175 {{{.code_and_extra = 0x045,.length2 = 0x8}}}, 176 {{{.code_and_extra = 0x0c5,.length2 = 0x8}}}, 177 {{{.code_and_extra = 0x025,.length2 = 0x8}}}, 178 {{{.code_and_extra = 0x0a5,.length2 = 0x8}}}, 179 {{{.code_and_extra = 0x065,.length2 = 0x8}}}, 180 {{{.code_and_extra = 0x0e5,.length2 = 0x8}}}, 181 {{{.code_and_extra = 0x015,.length2 = 0x8}}}, 182 {{{.code_and_extra = 0x095,.length2 = 0x8}}}, 183 {{{.code_and_extra = 0x055,.length2 = 0x8}}}, 184 {{{.code_and_extra = 0x0d5,.length2 = 0x8}}}, 185 {{{.code_and_extra = 0x035,.length2 = 0x8}}}, 186 {{{.code_and_extra = 0x0b5,.length2 = 0x8}}}, 187 {{{.code_and_extra = 0x075,.length2 = 0x8}}}, 188 {{{.code_and_extra = 0x0f5,.length2 = 0x8}}}, 189 {{{.code_and_extra = 0x00d,.length2 = 0x8}}}, 190 {{{.code_and_extra = 0x08d,.length2 = 0x8}}}, 191 {{{.code_and_extra = 0x04d,.length2 = 0x8}}}, 192 {{{.code_and_extra = 0x0cd,.length2 = 0x8}}}, 193 {{{.code_and_extra = 0x02d,.length2 = 0x8}}}, 194 {{{.code_and_extra = 0x0ad,.length2 = 0x8}}}, 195 {{{.code_and_extra = 0x06d,.length2 = 0x8}}}, 196 {{{.code_and_extra = 0x0ed,.length2 = 0x8}}}, 197 {{{.code_and_extra = 0x01d,.length2 = 0x8}}}, 198 {{{.code_and_extra = 0x09d,.length2 = 0x8}}}, 199 {{{.code_and_extra = 0x05d,.length2 = 0x8}}}, 200 {{{.code_and_extra = 0x0dd,.length2 = 0x8}}}, 201 {{{.code_and_extra = 0x03d,.length2 = 0x8}}}, 202 {{{.code_and_extra = 0x0bd,.length2 = 0x8}}}, 203 {{{.code_and_extra = 0x07d,.length2 = 0x8}}}, 204 {{{.code_and_extra = 0x0fd,.length2 = 0x8}}}, 205 {{{.code_and_extra = 0x013,.length2 = 0x9}}}, 206 {{{.code_and_extra = 0x113,.length2 = 0x9}}}, 207 {{{.code_and_extra = 0x093,.length2 = 0x9}}}, 208 {{{.code_and_extra = 0x193,.length2 = 0x9}}}, 209 {{{.code_and_extra = 0x053,.length2 = 0x9}}}, 210 {{{.code_and_extra = 0x153,.length2 = 0x9}}}, 211 {{{.code_and_extra = 0x0d3,.length2 = 0x9}}}, 212 {{{.code_and_extra = 0x1d3,.length2 = 0x9}}}, 213 {{{.code_and_extra = 0x033,.length2 = 0x9}}}, 214 {{{.code_and_extra = 0x133,.length2 = 0x9}}}, 215 {{{.code_and_extra = 0x0b3,.length2 = 0x9}}}, 216 {{{.code_and_extra = 0x1b3,.length2 = 0x9}}}, 217 {{{.code_and_extra = 0x073,.length2 = 0x9}}}, 218 {{{.code_and_extra = 0x173,.length2 = 0x9}}}, 219 {{{.code_and_extra = 0x0f3,.length2 = 0x9}}}, 220 {{{.code_and_extra = 0x1f3,.length2 = 0x9}}}, 221 {{{.code_and_extra = 0x00b,.length2 = 0x9}}}, 222 {{{.code_and_extra = 0x10b,.length2 = 0x9}}}, 223 {{{.code_and_extra = 0x08b,.length2 = 0x9}}}, 224 {{{.code_and_extra = 0x18b,.length2 = 0x9}}}, 225 {{{.code_and_extra = 0x04b,.length2 = 0x9}}}, 226 {{{.code_and_extra = 0x14b,.length2 = 0x9}}}, 227 {{{.code_and_extra = 0x0cb,.length2 = 0x9}}}, 228 {{{.code_and_extra = 0x1cb,.length2 = 0x9}}}, 229 {{{.code_and_extra = 0x02b,.length2 = 0x9}}}, 230 {{{.code_and_extra = 0x12b,.length2 = 0x9}}}, 231 {{{.code_and_extra = 0x0ab,.length2 = 0x9}}}, 232 {{{.code_and_extra = 0x1ab,.length2 = 0x9}}}, 233 {{{.code_and_extra = 0x06b,.length2 = 0x9}}}, 234 {{{.code_and_extra = 0x16b,.length2 = 0x9}}}, 235 {{{.code_and_extra = 0x0eb,.length2 = 0x9}}}, 236 {{{.code_and_extra = 0x1eb,.length2 = 0x9}}}, 237 {{{.code_and_extra = 0x01b,.length2 = 0x9}}}, 238 {{{.code_and_extra = 0x11b,.length2 = 0x9}}}, 239 {{{.code_and_extra = 0x09b,.length2 = 0x9}}}, 240 {{{.code_and_extra = 0x19b,.length2 = 0x9}}}, 241 {{{.code_and_extra = 0x05b,.length2 = 0x9}}}, 242 {{{.code_and_extra = 0x15b,.length2 = 0x9}}}, 243 {{{.code_and_extra = 0x0db,.length2 = 0x9}}}, 244 {{{.code_and_extra = 0x1db,.length2 = 0x9}}}, 245 {{{.code_and_extra = 0x03b,.length2 = 0x9}}}, 246 {{{.code_and_extra = 0x13b,.length2 = 0x9}}}, 247 {{{.code_and_extra = 0x0bb,.length2 = 0x9}}}, 248 {{{.code_and_extra = 0x1bb,.length2 = 0x9}}}, 249 {{{.code_and_extra = 0x07b,.length2 = 0x9}}}, 250 {{{.code_and_extra = 0x17b,.length2 = 0x9}}}, 251 {{{.code_and_extra = 0x0fb,.length2 = 0x9}}}, 252 {{{.code_and_extra = 0x1fb,.length2 = 0x9}}}, 253 {{{.code_and_extra = 0x007,.length2 = 0x9}}}, 254 {{{.code_and_extra = 0x107,.length2 = 0x9}}}, 255 {{{.code_and_extra = 0x087,.length2 = 0x9}}}, 256 {{{.code_and_extra = 0x187,.length2 = 0x9}}}, 257 {{{.code_and_extra = 0x047,.length2 = 0x9}}}, 258 {{{.code_and_extra = 0x147,.length2 = 0x9}}}, 259 {{{.code_and_extra = 0x0c7,.length2 = 0x9}}}, 260 {{{.code_and_extra = 0x1c7,.length2 = 0x9}}}, 261 {{{.code_and_extra = 0x027,.length2 = 0x9}}}, 262 {{{.code_and_extra = 0x127,.length2 = 0x9}}}, 263 {{{.code_and_extra = 0x0a7,.length2 = 0x9}}}, 264 {{{.code_and_extra = 0x1a7,.length2 = 0x9}}}, 265 {{{.code_and_extra = 0x067,.length2 = 0x9}}}, 266 {{{.code_and_extra = 0x167,.length2 = 0x9}}}, 267 {{{.code_and_extra = 0x0e7,.length2 = 0x9}}}, 268 {{{.code_and_extra = 0x1e7,.length2 = 0x9}}}, 269 {{{.code_and_extra = 0x017,.length2 = 0x9}}}, 270 {{{.code_and_extra = 0x117,.length2 = 0x9}}}, 271 {{{.code_and_extra = 0x097,.length2 = 0x9}}}, 272 {{{.code_and_extra = 0x197,.length2 = 0x9}}}, 273 {{{.code_and_extra = 0x057,.length2 = 0x9}}}, 274 {{{.code_and_extra = 0x157,.length2 = 0x9}}}, 275 {{{.code_and_extra = 0x0d7,.length2 = 0x9}}}, 276 {{{.code_and_extra = 0x1d7,.length2 = 0x9}}}, 277 {{{.code_and_extra = 0x037,.length2 = 0x9}}}, 278 {{{.code_and_extra = 0x137,.length2 = 0x9}}}, 279 {{{.code_and_extra = 0x0b7,.length2 = 0x9}}}, 280 {{{.code_and_extra = 0x1b7,.length2 = 0x9}}}, 281 {{{.code_and_extra = 0x077,.length2 = 0x9}}}, 282 {{{.code_and_extra = 0x177,.length2 = 0x9}}}, 283 {{{.code_and_extra = 0x0f7,.length2 = 0x9}}}, 284 {{{.code_and_extra = 0x1f7,.length2 = 0x9}}}, 285 {{{.code_and_extra = 0x00f,.length2 = 0x9}}}, 286 {{{.code_and_extra = 0x10f,.length2 = 0x9}}}, 287 {{{.code_and_extra = 0x08f,.length2 = 0x9}}}, 288 {{{.code_and_extra = 0x18f,.length2 = 0x9}}}, 289 {{{.code_and_extra = 0x04f,.length2 = 0x9}}}, 290 {{{.code_and_extra = 0x14f,.length2 = 0x9}}}, 291 {{{.code_and_extra = 0x0cf,.length2 = 0x9}}}, 292 {{{.code_and_extra = 0x1cf,.length2 = 0x9}}}, 293 {{{.code_and_extra = 0x02f,.length2 = 0x9}}}, 294 {{{.code_and_extra = 0x12f,.length2 = 0x9}}}, 295 {{{.code_and_extra = 0x0af,.length2 = 0x9}}}, 296 {{{.code_and_extra = 0x1af,.length2 = 0x9}}}, 297 {{{.code_and_extra = 0x06f,.length2 = 0x9}}}, 298 {{{.code_and_extra = 0x16f,.length2 = 0x9}}}, 299 {{{.code_and_extra = 0x0ef,.length2 = 0x9}}}, 300 {{{.code_and_extra = 0x1ef,.length2 = 0x9}}}, 301 {{{.code_and_extra = 0x01f,.length2 = 0x9}}}, 302 {{{.code_and_extra = 0x11f,.length2 = 0x9}}}, 303 {{{.code_and_extra = 0x09f,.length2 = 0x9}}}, 304 {{{.code_and_extra = 0x19f,.length2 = 0x9}}}, 305 {{{.code_and_extra = 0x05f,.length2 = 0x9}}}, 306 {{{.code_and_extra = 0x15f,.length2 = 0x9}}}, 307 {{{.code_and_extra = 0x0df,.length2 = 0x9}}}, 308 {{{.code_and_extra = 0x1df,.length2 = 0x9}}}, 309 {{{.code_and_extra = 0x03f,.length2 = 0x9}}}, 310 {{{.code_and_extra = 0x13f,.length2 = 0x9}}}, 311 {{{.code_and_extra = 0x0bf,.length2 = 0x9}}}, 312 {{{.code_and_extra = 0x1bf,.length2 = 0x9}}}, 313 {{{.code_and_extra = 0x07f,.length2 = 0x9}}}, 314 {{{.code_and_extra = 0x17f,.length2 = 0x9}}}, 315 {{{.code_and_extra = 0x0ff,.length2 = 0x9}}}, 316 {{{.code_and_extra = 0x1ff,.length2 = 0x9}}}, 317 {{{.code_and_extra = 0x000,.length2 = 0x7}}}, 318 {{{.code_and_extra = 0x040,.length2 = 0x7}}}, 319 {{{.code_and_extra = 0x020,.length2 = 0x7}}}, 320 {{{.code_and_extra = 0x060,.length2 = 0x7}}}, 321 {{{.code_and_extra = 0x010,.length2 = 0x7}}}, 322 {{{.code_and_extra = 0x050,.length2 = 0x7}}}, 323 {{{.code_and_extra = 0x030,.length2 = 0x7}}}, 324 {{{.code_and_extra = 0x070,.length2 = 0x7}}}, 325 {{{.code_and_extra = 0x008,.length2 = 0x7}}}, 326 {{{.code_and_extra = 0x048,.length2 = 0x7}}}, 327 {{{.code_and_extra = 0x028,.length2 = 0x7}}}, 328 {{{.code_and_extra = 0x068,.length2 = 0x7}}}, 329 {{{.code_and_extra = 0x018,.length2 = 0x7}}}, 330 {{{.code_and_extra = 0x058,.length2 = 0x7}}}, 331 {{{.code_and_extra = 0x038,.length2 = 0x7}}}, 332 {{{.code_and_extra = 0x078,.length2 = 0x7}}}, 333 {{{.code_and_extra = 0x004,.length2 = 0x7}}}, 334 {{{.code_and_extra = 0x044,.length2 = 0x7}}}, 335 {{{.code_and_extra = 0x024,.length2 = 0x7}}}, 336 {{{.code_and_extra = 0x064,.length2 = 0x7}}}, 337 {{{.code_and_extra = 0x014,.length2 = 0x7}}}, 338 {{{.code_and_extra = 0x054,.length2 = 0x7}}}, 339 {{{.code_and_extra = 0x034,.length2 = 0x7}}}, 340 {{{.code_and_extra = 0x074,.length2 = 0x7}}}, 341 {{{.code_and_extra = 0x003,.length2 = 0x8}}}, 342 {{{.code_and_extra = 0x083,.length2 = 0x8}}}, 343 {{{.code_and_extra = 0x043,.length2 = 0x8}}}, 344 {{{.code_and_extra = 0x0c3,.length2 = 0x8}}}, 345 {{{.code_and_extra = 0x023,.length2 = 0x8}}}, 346 {{{.code_and_extra = 0x0a3,.length2 = 0x8}}}, 347 {{{.code_and_extra = 0x063,.length2 = 0x8}}}, 348 {{{.code_and_extra = 0x0e3,.length2 = 0x8}}}, 349 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 350 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 351 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 352 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 353 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 354 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 355 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 356 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 357 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 358 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 359 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 360 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 361 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 362 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 363 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 364 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 365 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 366 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 367 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 368 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 369 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 370 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 371 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 372 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 373 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 374 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 375 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 376 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 377 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 378 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 379 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 380 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 381 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 382 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 383 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 384 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 385 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 386 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 387 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 388 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 389 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 390 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 391 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 392 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 393 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 394 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 395 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 396 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 397 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 398 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 399 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 400 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 401 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 402 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 403 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 404 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 405 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 406 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 407 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 408 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 409 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 410 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 411 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 412 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 413 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 414 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 415 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 416 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 417 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 418 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 419 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 420 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 421 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 422 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 423 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 424 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 425 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 426 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 427 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 428 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 429 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 430 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 431 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 432 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 433 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 434 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 435 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 436 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 437 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 438 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 439 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 440 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 441 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 442 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 443 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 444 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 445 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 446 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 447 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 448 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 449 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 450 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 451 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 452 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 453 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 454 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 455 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 456 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 457 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 458 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 459 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 460 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 461 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 462 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 463 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 464 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 465 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 466 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 467 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 468 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 469 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 470 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 471 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 472 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 473 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 474 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 475 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 476 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 477 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 478 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 479 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 480 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 481 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 482 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 483 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 484 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 485 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 486 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 487 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 488 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 489 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 490 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 491 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 492 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 493 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 494 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 495 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 496 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 497 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 498 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 499 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 500 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 501 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 502 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 503 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 504 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 505 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 506 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 507 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 508 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 509 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 510 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 511 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 512 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 513 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 514 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 515 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 516 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 517 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 518 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 519 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 520 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 521 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 522 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 523 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 524 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 525 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 526 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 527 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 528 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 529 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 530 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 531 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 532 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 533 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 534 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 535 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 536 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 537 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 538 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 539 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 540 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 541 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 542 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 543 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 544 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 545 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 546 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 547 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 548 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 549 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 550 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 551 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 552 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 553 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 554 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 555 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 556 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 557 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 558 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 559 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 560 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 561 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 562 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 563 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 564 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 565 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 566 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 567 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 568 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 569 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 570 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 571 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 572 {{{.code_and_extra = 0x000,.length2 = 0x0}}}, 573 {{{.code_and_extra = 0x000,.length2 = 0x0}}}}, 574 .dist_table = { 575 {{{.code_and_extra = 0x000,.length2 = 0x5}}}, 576 {{{.code_and_extra = 0x010,.length2 = 0x5}}}, 577 {{{.code_and_extra = 0x008,.length2 = 0x5}}}, 578 {{{.code_and_extra = 0x018,.length2 = 0x5}}}, 579 {{{.code_and_extra = 0x10004,.length2 = 0x5}}}, 580 {{{.code_and_extra = 0x10014,.length2 = 0x5}}}, 581 {{{.code_and_extra = 0x2000c,.length2 = 0x5}}}, 582 {{{.code_and_extra = 0x2001c,.length2 = 0x5}}}, 583 {{{.code_and_extra = 0x30002,.length2 = 0x5}}}, 584 {{{.code_and_extra = 0x30012,.length2 = 0x5}}}, 585 {{{.code_and_extra = 0x4000a,.length2 = 0x5}}}, 586 {{{.code_and_extra = 0x4001a,.length2 = 0x5}}}, 587 {{{.code_and_extra = 0x50006,.length2 = 0x5}}}, 588 {{{.code_and_extra = 0x50016,.length2 = 0x5}}}, 589 {{{.code_and_extra = 0x6000e,.length2 = 0x5}}}, 590 {{{.code_and_extra = 0x6001e,.length2 = 0x5}}}, 591 {{{.code_and_extra = 0x70001,.length2 = 0x5}}}, 592 {{{.code_and_extra = 0x70011,.length2 = 0x5}}}, 593 {{{.code_and_extra = 0x80009,.length2 = 0x5}}}, 594 {{{.code_and_extra = 0x80019,.length2 = 0x5}}}, 595 {{{.code_and_extra = 0x90005,.length2 = 0x5}}}, 596 {{{.code_and_extra = 0x90015,.length2 = 0x5}}}, 597 {{{.code_and_extra = 0xa000d,.length2 = 0x5}}}, 598 {{{.code_and_extra = 0xa001d,.length2 = 0x5}}}, 599 {{{.code_and_extra = 0xb0003,.length2 = 0x5}}}, 600 {{{.code_and_extra = 0xb0013,.length2 = 0x5}}}, 601 {{{.code_and_extra = 0xc000b,.length2 = 0x5}}}, 602 {{{.code_and_extra = 0xc001b,.length2 = 0x5}}}, 603 {{{.code_and_extra = 0xd0007,.length2 = 0x5}}}, 604 {{{.code_and_extra = 0xd0017,.length2 = 0x5}}}, 605 {{{.code_and_extra = 0x000,.length2 = 0x0}}}} 606 }; 607 608 struct slver { 609 uint16_t snum; 610 uint8_t ver; 611 uint8_t core; 612 }; 613 614 /* Version info */ 615 struct slver isal_update_histogram_slver_00010085; 616 struct slver isal_update_histogram_slver = { 0x0085, 0x01, 0x00 }; 617 618 struct slver isal_create_hufftables_slver_00010086; 619 struct slver isal_create_hufftables_slver = { 0x0086, 0x01, 0x00 }; 620 621 struct slver isal_create_hufftables_subset_slver_00010087; 622 struct slver isal_create_hufftables_subset_slver = { 0x0087, 0x01, 0x00 }; 623 624 extern uint32_t build_huff_tree(struct heap_tree *heap, uint64_t heap_size, uint64_t node_ptr); 625 extern void build_heap(uint64_t * heap, uint64_t heap_size); 626 627 static const uint8_t bitrev8[0x100] = { 628 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 629 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, 630 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 631 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, 632 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 633 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, 634 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 635 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC, 636 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 637 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, 638 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 639 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA, 640 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 641 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, 642 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 643 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE, 644 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 645 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1, 646 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 647 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, 648 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 649 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, 650 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 651 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD, 652 0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 653 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, 654 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 655 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB, 656 0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 657 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, 658 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 659 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF 660 }; 661 662 // bit reverse low order LENGTH bits in code, and return result in low order bits 663 static inline uint16_t bit_reverse(uint16_t code, uint32_t length) 664 { 665 code = (bitrev8[code & 0x00FF] << 8) | (bitrev8[code >> 8]); 666 return (code >> (16 - length)); 667 } 668 669 void isal_update_histogram_base(uint8_t * start_stream, int length, 670 struct isal_huff_histogram *histogram) 671 { 672 uint32_t literal = 0, hash; 673 uint16_t seen, *last_seen = histogram->hash_table; 674 uint8_t *current, *end_stream, *next_hash, *end; 675 uint32_t match_length; 676 uint32_t dist; 677 uint64_t *lit_len_histogram = histogram->lit_len_histogram; 678 uint64_t *dist_histogram = histogram->dist_histogram; 679 680 if (length <= 0) 681 return; 682 683 end_stream = start_stream + length; 684 memset(last_seen, 0, sizeof(histogram->hash_table)); /* Initialize last_seen to be 0. */ 685 for (current = start_stream; current < end_stream - 3; current++) { 686 literal = *(uint32_t *) current; 687 hash = compute_hash(literal) & HASH_MASK; 688 seen = last_seen[hash]; 689 last_seen[hash] = (current - start_stream) & 0xFFFF; 690 dist = (current - start_stream - seen) & 0xFFFF; 691 if (dist - 1 < D - 1) { 692 assert(start_stream <= current - dist); 693 match_length = 694 compare258(current - dist, current, end_stream - current); 695 if (match_length >= SHORTEST_MATCH) { 696 next_hash = current; 697 #ifdef ISAL_LIMIT_HASH_UPDATE 698 end = next_hash + 3; 699 #else 700 end = next_hash + match_length; 701 #endif 702 if (end > end_stream - 3) 703 end = end_stream - 3; 704 next_hash++; 705 for (; next_hash < end; next_hash++) { 706 literal = *(uint32_t *) next_hash; 707 hash = compute_hash(literal) & HASH_MASK; 708 last_seen[hash] = (next_hash - start_stream) & 0xFFFF; 709 } 710 711 dist_histogram[convert_dist_to_dist_sym(dist)] += 1; 712 lit_len_histogram[convert_length_to_len_sym(match_length)] += 713 1; 714 current += match_length - 1; 715 continue; 716 } 717 } 718 lit_len_histogram[literal & 0xFF] += 1; 719 } 720 literal = literal >> 8; 721 hash = compute_hash(literal) & HASH_MASK; 722 seen = last_seen[hash]; 723 last_seen[hash] = (current - start_stream) & 0xFFFF; 724 dist = (current - start_stream - seen) & 0xFFFF; 725 if (dist < D) { 726 match_length = compare258(current - dist, current, end_stream - current); 727 if (match_length >= SHORTEST_MATCH) { 728 dist_histogram[convert_dist_to_dist_sym(dist)] += 1; 729 lit_len_histogram[convert_length_to_len_sym(match_length)] += 1; 730 lit_len_histogram[256] += 1; 731 return; 732 } 733 } else 734 lit_len_histogram[literal & 0xFF] += 1; 735 lit_len_histogram[(literal >> 8) & 0xFF] += 1; 736 lit_len_histogram[(literal >> 16) & 0xFF] += 1; 737 lit_len_histogram[256] += 1; 738 return; 739 } 740 741 uint32_t convert_dist_to_dist_sym(uint32_t dist) 742 { 743 assert(dist <= 32768 && dist > 0); 744 if (dist <= 2) 745 return dist - 1; 746 else if (dist <= 4) 747 return 0 + (dist - 1) / 1; 748 else if (dist <= 8) 749 return 2 + (dist - 1) / 2; 750 else if (dist <= 16) 751 return 4 + (dist - 1) / 4; 752 else if (dist <= 32) 753 return 6 + (dist - 1) / 8; 754 else if (dist <= 64) 755 return 8 + (dist - 1) / 16; 756 else if (dist <= 128) 757 return 10 + (dist - 1) / 32; 758 else if (dist <= 256) 759 return 12 + (dist - 1) / 64; 760 else if (dist <= 512) 761 return 14 + (dist - 1) / 128; 762 else if (dist <= 1024) 763 return 16 + (dist - 1) / 256; 764 else if (dist <= 2048) 765 return 18 + (dist - 1) / 512; 766 else if (dist <= 4096) 767 return 20 + (dist - 1) / 1024; 768 else if (dist <= 8192) 769 return 22 + (dist - 1) / 2048; 770 else if (dist <= 16384) 771 return 24 + (dist - 1) / 4096; 772 else if (dist <= 32768) 773 return 26 + (dist - 1) / 8192; 774 else 775 return ~0; /* ~0 is an invalid distance code */ 776 777 } 778 779 uint32_t convert_length_to_len_sym(uint32_t length) 780 { 781 assert(length > 2 && length < 259); 782 783 /* Based on tables on page 11 in RFC 1951 */ 784 if (length < 11) 785 return 257 + length - 3; 786 else if (length < 19) 787 return 261 + (length - 3) / 2; 788 else if (length < 35) 789 return 265 + (length - 3) / 4; 790 else if (length < 67) 791 return 269 + (length - 3) / 8; 792 else if (length < 131) 793 return 273 + (length - 3) / 16; 794 else if (length < 258) 795 return 277 + (length - 3) / 32; 796 else 797 return 285; 798 } 799 800 // Upon return, codes[] contains the code lengths, 801 // and bl_count is the count of the lengths 802 803 /* Init heap with the histogram, and return the histogram size */ 804 static inline uint32_t init_heap32(struct heap_tree *heap_space, uint32_t * histogram, 805 uint32_t hist_size) 806 { 807 uint32_t heap_size, i; 808 809 memset(heap_space, 0, sizeof(struct heap_tree)); 810 811 heap_size = 0; 812 for (i = 0; i < hist_size; i++) { 813 if (histogram[i] != 0) 814 heap_space->heap[++heap_size] = 815 (((uint64_t) histogram[i]) << FREQ_SHIFT) | i; 816 } 817 818 // make sure heap has at least two elements in it 819 if (heap_size < 2) { 820 if (heap_size == 0) { 821 heap_space->heap[1] = 1ULL << FREQ_SHIFT; 822 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1; 823 heap_size = 2; 824 } else { 825 // heap size == 1 826 if (histogram[0] == 0) 827 heap_space->heap[2] = 1ULL << FREQ_SHIFT; 828 else 829 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1; 830 heap_size = 2; 831 } 832 } 833 834 build_heap(heap_space->heap, heap_size); 835 836 return heap_size; 837 } 838 839 static inline uint32_t init_heap64(struct heap_tree *heap_space, uint64_t * histogram, 840 uint64_t hist_size) 841 { 842 uint32_t heap_size, i; 843 844 memset(heap_space, 0, sizeof(struct heap_tree)); 845 846 heap_size = 0; 847 for (i = 0; i < hist_size; i++) { 848 if (histogram[i] != 0) 849 heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT) | i; 850 } 851 852 // make sure heap has at least two elements in it 853 if (heap_size < 2) { 854 if (heap_size == 0) { 855 heap_space->heap[1] = 1ULL << FREQ_SHIFT; 856 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1; 857 heap_size = 2; 858 } else { 859 // heap size == 1 860 if (histogram[0] == 0) 861 heap_space->heap[2] = 1ULL << FREQ_SHIFT; 862 else 863 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1; 864 heap_size = 2; 865 } 866 } 867 868 build_heap(heap_space->heap, heap_size); 869 870 return heap_size; 871 } 872 873 static inline uint32_t init_heap64_semi_complete(struct heap_tree *heap_space, 874 uint64_t * histogram, uint64_t hist_size, 875 uint64_t complete_start) 876 { 877 uint32_t heap_size, i; 878 879 memset(heap_space, 0, sizeof(struct heap_tree)); 880 881 heap_size = 0; 882 for (i = 0; i < complete_start; i++) { 883 if (histogram[i] != 0) 884 heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT) | i; 885 } 886 887 for (; i < hist_size; i++) 888 heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT) | i; 889 890 // make sure heap has at least two elements in it 891 if (heap_size < 2) { 892 if (heap_size == 0) { 893 heap_space->heap[1] = 1ULL << FREQ_SHIFT; 894 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1; 895 heap_size = 2; 896 } else { 897 // heap size == 1 898 if (histogram[0] == 0) 899 heap_space->heap[2] = 1ULL << FREQ_SHIFT; 900 else 901 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1; 902 heap_size = 2; 903 } 904 } 905 906 build_heap(heap_space->heap, heap_size); 907 908 return heap_size; 909 } 910 911 static inline uint32_t init_heap64_complete(struct heap_tree *heap_space, uint64_t * histogram, 912 uint64_t hist_size) 913 { 914 uint32_t heap_size, i; 915 916 memset(heap_space, 0, sizeof(struct heap_tree)); 917 918 heap_size = 0; 919 for (i = 0; i < hist_size; i++) 920 heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT) | i; 921 922 build_heap(heap_space->heap, heap_size); 923 924 return heap_size; 925 } 926 927 static inline uint32_t fix_code_lens(struct heap_tree *heap_space, uint32_t root_node, 928 uint32_t * bl_count, uint32_t max_code_len) 929 { 930 struct tree_node *tree = heap_space->tree; 931 uint64_t *code_len_count = heap_space->code_len_count; 932 uint32_t i, j, k, child, depth, code_len; 933 934 // compute code lengths and code length counts 935 code_len = 0; 936 j = root_node; 937 for (i = root_node; i <= HEAP_TREE_NODE_START; i++) { 938 child = tree[i].child; 939 if (child > MAX_HISTHEAP_SIZE) { 940 depth = 1 + tree[i].depth; 941 942 tree[child].depth = depth; 943 tree[child - 1].depth = depth; 944 } else { 945 tree[j++] = tree[i]; 946 depth = tree[i].depth; 947 while (code_len < depth) { 948 code_len++; 949 code_len_count[code_len] = 0; 950 } 951 code_len_count[depth]++; 952 } 953 } 954 955 if (code_len > max_code_len) { 956 while (code_len > max_code_len) { 957 assert(code_len_count[code_len] > 1); 958 for (i = max_code_len - 1; i != 0; i--) 959 if (code_len_count[i] != 0) 960 break; 961 assert(i != 0); 962 code_len_count[i]--; 963 code_len_count[i + 1] += 2; 964 code_len_count[code_len - 1]++; 965 code_len_count[code_len] -= 2; 966 if (code_len_count[code_len] == 0) 967 code_len--; 968 } 969 970 for (i = 1; i <= code_len; i++) 971 bl_count[i] = code_len_count[i]; 972 for (; i <= max_code_len; i++) 973 bl_count[i] = 0; 974 975 for (k = 1; code_len_count[k] == 0; k++) ; 976 for (i = root_node; i < j; i++) { 977 tree[i].depth = k; 978 code_len_count[k]--; 979 for (; code_len_count[k] == 0; k++) ; 980 } 981 } else { 982 for (i = 1; i <= code_len; i++) 983 bl_count[i] = code_len_count[i]; 984 for (; i <= max_code_len; i++) 985 bl_count[i] = 0; 986 } 987 988 return j; 989 990 } 991 992 static inline void 993 gen_huff_code_lens(struct heap_tree *heap_space, uint32_t heap_size, uint32_t * bl_count, 994 struct huff_code *codes, uint32_t codes_count, uint32_t max_code_len) 995 { 996 struct tree_node *tree = heap_space->tree; 997 uint32_t root_node = HEAP_TREE_NODE_START, node_ptr; 998 uint32_t end_node; 999 1000 root_node = build_huff_tree(heap_space, heap_size, root_node); 1001 1002 end_node = fix_code_lens(heap_space, root_node, bl_count, max_code_len); 1003 1004 memset(codes, 0, codes_count * sizeof(*codes)); 1005 for (node_ptr = root_node; node_ptr < end_node; node_ptr++) 1006 codes[tree[node_ptr].child].length = tree[node_ptr].depth; 1007 1008 } 1009 1010 inline uint32_t set_huff_codes(struct huff_code *huff_code_table, int table_length, 1011 uint32_t * count) 1012 { 1013 /* Uses the algorithm mentioned in the deflate standard, Rfc 1951. */ 1014 int i; 1015 uint16_t code = 0; 1016 uint16_t next_code[MAX_HUFF_TREE_DEPTH + 1]; 1017 uint32_t max_code = 0; 1018 1019 next_code[0] = code; 1020 1021 for (i = 1; i < MAX_HUFF_TREE_DEPTH + 1; i++) 1022 next_code[i] = (next_code[i - 1] + count[i - 1]) << 1; 1023 1024 for (i = 0; i < table_length; i++) { 1025 if (huff_code_table[i].length != 0) { 1026 huff_code_table[i].code = 1027 bit_reverse(next_code[huff_code_table[i].length], 1028 huff_code_table[i].length); 1029 next_code[huff_code_table[i].length] += 1; 1030 max_code = i; 1031 } 1032 } 1033 1034 return max_code; 1035 } 1036 1037 // on input, codes contain the code lengths 1038 // on output, code contains: 1039 // 23:16 code length 1040 // 15:0 code value in low order bits 1041 // returns max code value 1042 static inline uint32_t set_dist_huff_codes(struct huff_code *codes, uint32_t * bl_count) 1043 { 1044 uint32_t code, code_len, bits, i; 1045 uint32_t next_code[MAX_DEFLATE_CODE_LEN + 1]; 1046 uint32_t max_code = 0; 1047 const uint32_t num_codes = DIST_LEN; 1048 1049 code = bl_count[0] = 0; 1050 for (bits = 1; bits <= MAX_HUFF_TREE_DEPTH; bits++) { 1051 code = (code + bl_count[bits - 1]) << 1; 1052 next_code[bits] = code; 1053 } 1054 for (i = 0; i < num_codes; i++) { 1055 code_len = codes[i].length; 1056 if (code_len != 0) { 1057 codes[i].code = bit_reverse(next_code[code_len], code_len); 1058 codes[i].extra_bit_count = dist_code_extra_bits[i]; 1059 next_code[code_len] += 1; 1060 max_code = i; 1061 } 1062 } 1063 return max_code; 1064 } 1065 1066 int create_huffman_header(struct BitBuf2 *header_bitbuf, 1067 struct huff_code *lookup_table, 1068 struct rl_code *huffman_rep, 1069 uint16_t huffman_rep_length, uint32_t end_of_block, 1070 uint32_t hclen, uint32_t hlit, uint32_t hdist) 1071 { 1072 /* hlit, hdist, hclen are as defined in the deflate standard, head is the 1073 * first three deflate header bits.*/ 1074 int i; 1075 uint64_t bit_count; 1076 uint64_t data; 1077 struct huff_code huffman_value; 1078 const uint32_t extra_bits[3] = { 2, 3, 7 }; 1079 1080 bit_count = buffer_bits_used(header_bitbuf); 1081 1082 data = (end_of_block ? 5 : 4) | (hlit << 3) | (hdist << 8) | (hclen << 13); 1083 data |= ((lookup_table[code_length_code_order[0]].length) << DYN_HDR_START_LEN); 1084 write_bits(header_bitbuf, data, DYN_HDR_START_LEN + 3); 1085 data = 0; 1086 for (i = hclen + 3; i >= 1; i--) 1087 data = (data << 3) | lookup_table[code_length_code_order[i]].length; 1088 1089 write_bits(header_bitbuf, data, (hclen + 3) * 3); 1090 1091 for (i = 0; i < huffman_rep_length; i++) { 1092 huffman_value = lookup_table[huffman_rep[i].code]; 1093 1094 write_bits(header_bitbuf, (uint64_t) huffman_value.code, 1095 (uint32_t) huffman_value.length); 1096 1097 if (huffman_rep[i].code > 15) { 1098 write_bits(header_bitbuf, (uint64_t) huffman_rep[i].extra_bits, 1099 (uint32_t) extra_bits[huffman_rep[i].code - 16]); 1100 } 1101 } 1102 bit_count = buffer_bits_used(header_bitbuf) - bit_count; 1103 1104 return bit_count; 1105 } 1106 1107 inline int create_header(struct BitBuf2 *header_bitbuf, struct rl_code *huffman_rep, 1108 uint32_t length, uint64_t * histogram, uint32_t hlit, 1109 uint32_t hdist, uint32_t end_of_block) 1110 { 1111 int i; 1112 1113 uint32_t heap_size; 1114 struct heap_tree heap_space; 1115 uint32_t code_len_count[MAX_HUFF_TREE_DEPTH + 1]; 1116 struct huff_code lookup_table[HUFF_LEN]; 1117 1118 /* hlit, hdist, and hclen are defined in RFC 1951 page 13 */ 1119 uint32_t hclen; 1120 uint64_t bit_count; 1121 1122 /* Create a huffman tree to encode run length encoded representation. */ 1123 heap_size = init_heap64(&heap_space, histogram, HUFF_LEN); 1124 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1125 (struct huff_code *)lookup_table, HUFF_LEN, 7); 1126 set_huff_codes(lookup_table, HUFF_LEN, code_len_count); 1127 1128 /* Calculate hclen */ 1129 for (i = CODE_LEN_CODES - 1; i > 3; i--) /* i must be at least 4 */ 1130 if (lookup_table[code_length_code_order[i]].length != 0) 1131 break; 1132 1133 hclen = i - 3; 1134 1135 /* Generate actual header. */ 1136 bit_count = create_huffman_header(header_bitbuf, lookup_table, huffman_rep, 1137 length, end_of_block, hclen, hlit, hdist); 1138 1139 return bit_count; 1140 } 1141 1142 static inline 1143 struct rl_code *write_rl(struct rl_code *pout, uint16_t last_len, uint32_t run_len, 1144 uint64_t * counts) 1145 { 1146 if (last_len == 0) { 1147 while (run_len > 138) { 1148 pout->code = 18; 1149 pout->extra_bits = 138 - 11; 1150 pout++; 1151 run_len -= 138; 1152 counts[18]++; 1153 } 1154 // 1 <= run_len <= 138 1155 if (run_len > 10) { 1156 pout->code = 18; 1157 pout->extra_bits = run_len - 11; 1158 pout++; 1159 counts[18]++; 1160 } else if (run_len > 2) { 1161 pout->code = 17; 1162 pout->extra_bits = run_len - 3; 1163 pout++; 1164 counts[17]++; 1165 } else if (run_len == 1) { 1166 pout->code = 0; 1167 pout->extra_bits = 0; 1168 pout++; 1169 counts[0]++; 1170 } else { 1171 assert(run_len == 2); 1172 pout[0].code = 0; 1173 pout[0].extra_bits = 0; 1174 pout[1].code = 0; 1175 pout[1].extra_bits = 0; 1176 pout += 2; 1177 counts[0] += 2; 1178 } 1179 } else { 1180 // last_len != 0 1181 pout->code = last_len; 1182 pout->extra_bits = 0; 1183 pout++; 1184 counts[last_len]++; 1185 run_len--; 1186 if (run_len != 0) { 1187 while (run_len > 6) { 1188 pout->code = 16; 1189 pout->extra_bits = 6 - 3; 1190 pout++; 1191 run_len -= 6; 1192 counts[16]++; 1193 } 1194 // 1 <= run_len <= 6 1195 switch (run_len) { 1196 case 1: 1197 pout->code = last_len; 1198 pout->extra_bits = 0; 1199 pout++; 1200 counts[last_len]++; 1201 break; 1202 case 2: 1203 pout[0].code = last_len; 1204 pout[0].extra_bits = 0; 1205 pout[1].code = last_len; 1206 pout[1].extra_bits = 0; 1207 pout += 2; 1208 counts[last_len] += 2; 1209 break; 1210 default: // 3...6 1211 pout->code = 16; 1212 pout->extra_bits = run_len - 3; 1213 pout++; 1214 counts[16]++; 1215 } 1216 } 1217 } 1218 return pout; 1219 } 1220 1221 // convert codes into run-length symbols, write symbols into OUT 1222 // generate histogram into COUNTS (assumed to be initialized to 0) 1223 // Format of OUT: 1224 // 4:0 code (0...18) 1225 // 15:8 Extra bits (0...127) 1226 // returns number of symbols in out 1227 static inline uint32_t rl_encode(uint16_t * codes, uint32_t num_codes, uint64_t * counts, 1228 struct rl_code *out) 1229 { 1230 uint32_t i, run_len; 1231 uint16_t last_len, len; 1232 struct rl_code *pout; 1233 1234 pout = out; 1235 last_len = codes[0]; 1236 run_len = 1; 1237 for (i = 1; i < num_codes; i++) { 1238 len = codes[i]; 1239 if (len == last_len) { 1240 run_len++; 1241 continue; 1242 } 1243 pout = write_rl(pout, last_len, run_len, counts); 1244 last_len = len; 1245 run_len = 1; 1246 } 1247 pout = write_rl(pout, last_len, run_len, counts); 1248 1249 return (uint32_t) (pout - out); 1250 } 1251 1252 void create_code_tables(uint16_t * code_table, uint8_t * code_length_table, uint32_t length, 1253 struct huff_code *hufftable) 1254 { 1255 int i; 1256 for (i = 0; i < length; i++) { 1257 code_table[i] = hufftable[i].code; 1258 code_length_table[i] = hufftable[i].length; 1259 } 1260 } 1261 1262 void create_packed_len_table(uint32_t * packed_table, struct huff_code *lit_len_hufftable) 1263 { 1264 int i, count = 0; 1265 uint16_t extra_bits; 1266 uint16_t extra_bits_count = 0; 1267 1268 /* Gain extra bits is the next place where the number of extra bits in 1269 * lenght codes increases. */ 1270 uint16_t gain_extra_bits = LEN_EXTRA_BITS_START; 1271 1272 for (i = 257; i < LIT_LEN - 1; i++) { 1273 for (extra_bits = 0; extra_bits < (1 << extra_bits_count); extra_bits++) { 1274 if (count > 254) 1275 break; 1276 packed_table[count++] = 1277 (extra_bits << (lit_len_hufftable[i].length + LENGTH_BITS)) | 1278 (lit_len_hufftable[i].code << LENGTH_BITS) | 1279 (lit_len_hufftable[i].length + extra_bits_count); 1280 } 1281 1282 if (i == gain_extra_bits) { 1283 gain_extra_bits += LEN_EXTRA_BITS_INTERVAL; 1284 extra_bits_count += 1; 1285 } 1286 } 1287 1288 packed_table[count] = (lit_len_hufftable[LIT_LEN - 1].code << LENGTH_BITS) | 1289 (lit_len_hufftable[LIT_LEN - 1].length); 1290 } 1291 1292 void create_packed_dist_table(uint32_t * packed_table, uint32_t length, 1293 struct huff_code *dist_hufftable) 1294 { 1295 int i, count = 0; 1296 uint16_t extra_bits; 1297 uint16_t extra_bits_count = 0; 1298 1299 /* Gain extra bits is the next place where the number of extra bits in 1300 * distance codes increases. */ 1301 uint16_t gain_extra_bits = DIST_EXTRA_BITS_START; 1302 1303 for (i = 0; i < DIST_LEN; i++) { 1304 for (extra_bits = 0; extra_bits < (1 << extra_bits_count); extra_bits++) { 1305 if (count >= length) 1306 return; 1307 1308 packed_table[count++] = 1309 (extra_bits << (dist_hufftable[i].length + LENGTH_BITS)) | 1310 (dist_hufftable[i].code << LENGTH_BITS) | 1311 (dist_hufftable[i].length + extra_bits_count); 1312 1313 } 1314 1315 if (i == gain_extra_bits) { 1316 gain_extra_bits += DIST_EXTRA_BITS_INTERVAL; 1317 extra_bits_count += 1; 1318 } 1319 } 1320 } 1321 1322 int are_hufftables_useable(struct huff_code *lit_len_hufftable, 1323 struct huff_code *dist_hufftable) 1324 { 1325 int max_lit_code_len = 0, max_len_code_len = 0, max_dist_code_len = 0; 1326 int dist_extra_bits = 0, len_extra_bits = 0; 1327 int gain_dist_extra_bits = DIST_EXTRA_BITS_START; 1328 int gain_len_extra_bits = LEN_EXTRA_BITS_START; 1329 int max_code_len; 1330 int i; 1331 1332 for (i = 0; i < LIT_LEN; i++) 1333 if (lit_len_hufftable[i].length > max_lit_code_len) 1334 max_lit_code_len = lit_len_hufftable[i].length; 1335 1336 for (i = 257; i < LIT_LEN - 1; i++) { 1337 if (lit_len_hufftable[i].length + len_extra_bits > max_len_code_len) 1338 max_len_code_len = lit_len_hufftable[i].length + len_extra_bits; 1339 1340 if (i == gain_len_extra_bits) { 1341 gain_len_extra_bits += LEN_EXTRA_BITS_INTERVAL; 1342 len_extra_bits += 1; 1343 } 1344 } 1345 1346 for (i = 0; i < DIST_LEN; i++) { 1347 if (dist_hufftable[i].length + dist_extra_bits > max_dist_code_len) 1348 max_dist_code_len = dist_hufftable[i].length + dist_extra_bits; 1349 1350 if (i == gain_dist_extra_bits) { 1351 gain_dist_extra_bits += DIST_EXTRA_BITS_INTERVAL; 1352 dist_extra_bits += 1; 1353 } 1354 } 1355 1356 max_code_len = max_lit_code_len + max_len_code_len + max_dist_code_len; 1357 1358 /* Some versions of igzip can write upto one literal, one length and one 1359 * distance code at the same time. This checks to make sure that is 1360 * always writeable in bitbuf*/ 1361 return (max_code_len > MAX_BITBUF_BIT_WRITE); 1362 } 1363 1364 int isal_create_hufftables(struct isal_hufftables *hufftables, 1365 struct isal_huff_histogram *histogram) 1366 { 1367 struct huff_code lit_huff_table[LIT_LEN], dist_huff_table[DIST_LEN]; 1368 uint64_t bit_count; 1369 int max_dist = convert_dist_to_dist_sym(IGZIP_HIST_SIZE); 1370 struct heap_tree heap_space; 1371 uint32_t heap_size; 1372 uint32_t code_len_count[MAX_HUFF_TREE_DEPTH + 1]; 1373 struct BitBuf2 header_bitbuf; 1374 uint32_t max_lit_len_sym; 1375 uint32_t max_dist_sym; 1376 uint32_t hlit, hdist, i; 1377 uint16_t combined_table[LIT_LEN + DIST_LEN]; 1378 uint64_t count_histogram[HUFF_LEN]; 1379 struct rl_code rl_huff[LIT_LEN + DIST_LEN]; 1380 uint32_t rl_huff_len; 1381 1382 uint32_t *dist_table = hufftables->dist_table; 1383 uint32_t *len_table = hufftables->len_table; 1384 uint16_t *lit_table = hufftables->lit_table; 1385 uint16_t *dcodes = hufftables->dcodes; 1386 uint8_t *lit_table_sizes = hufftables->lit_table_sizes; 1387 uint8_t *dcodes_sizes = hufftables->dcodes_sizes; 1388 uint8_t *deflate_hdr = hufftables->deflate_hdr; 1389 uint64_t *lit_len_histogram = histogram->lit_len_histogram; 1390 uint64_t *dist_histogram = histogram->dist_histogram; 1391 1392 memset(hufftables, 0, sizeof(struct isal_hufftables)); 1393 1394 heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN); 1395 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1396 (struct huff_code *)lit_huff_table, LIT_LEN, MAX_DEFLATE_CODE_LEN); 1397 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count); 1398 1399 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN); 1400 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1401 (struct huff_code *)dist_huff_table, max_dist, 1402 MAX_DEFLATE_CODE_LEN); 1403 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count); 1404 1405 if (are_hufftables_useable(lit_huff_table, dist_huff_table)) { 1406 heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN); 1407 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1408 (struct huff_code *)lit_huff_table, LIT_LEN, 1409 MAX_SAFE_LIT_CODE_LEN); 1410 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count); 1411 1412 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN); 1413 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1414 (struct huff_code *)dist_huff_table, max_dist, 1415 MAX_SAFE_DIST_CODE_LEN); 1416 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count); 1417 1418 } 1419 1420 create_code_tables(dcodes, dcodes_sizes, DIST_LEN - DCODE_OFFSET, 1421 dist_huff_table + DCODE_OFFSET); 1422 1423 create_code_tables(lit_table, lit_table_sizes, IGZIP_LIT_TABLE_SIZE, lit_huff_table); 1424 1425 create_packed_len_table(len_table, lit_huff_table); 1426 create_packed_dist_table(dist_table, IGZIP_DIST_TABLE_SIZE, dist_huff_table); 1427 1428 set_buf(&header_bitbuf, deflate_hdr, sizeof(deflate_hdr)); 1429 init(&header_bitbuf); 1430 1431 hlit = max_lit_len_sym - 256; 1432 hdist = max_dist_sym; 1433 1434 /* Run length encode the length and distance huffman codes */ 1435 memset(count_histogram, 0, sizeof(count_histogram)); 1436 for (i = 0; i < 257 + hlit; i++) 1437 combined_table[i] = lit_huff_table[i].length; 1438 for (i = 0; i < 1 + hdist; i++) 1439 combined_table[i + hlit + 257] = dist_huff_table[i].length; 1440 rl_huff_len = 1441 rl_encode(combined_table, hlit + 257 + hdist + 1, count_histogram, rl_huff); 1442 1443 /* Create header */ 1444 bit_count = 1445 create_header(&header_bitbuf, rl_huff, rl_huff_len, 1446 count_histogram, hlit, hdist, LAST_BLOCK); 1447 flush(&header_bitbuf); 1448 1449 hufftables->deflate_hdr_count = bit_count / 8; 1450 hufftables->deflate_hdr_extra_bits = bit_count % 8; 1451 1452 return 0; 1453 } 1454 1455 int isal_create_hufftables_subset(struct isal_hufftables *hufftables, 1456 struct isal_huff_histogram *histogram) 1457 { 1458 struct huff_code lit_huff_table[LIT_LEN], dist_huff_table[DIST_LEN]; 1459 uint64_t bit_count; 1460 int max_dist = convert_dist_to_dist_sym(IGZIP_HIST_SIZE); 1461 struct heap_tree heap_space; 1462 uint32_t heap_size; 1463 uint32_t code_len_count[MAX_HUFF_TREE_DEPTH + 1]; 1464 struct BitBuf2 header_bitbuf; 1465 uint32_t max_lit_len_sym; 1466 uint32_t max_dist_sym; 1467 uint32_t hlit, hdist, i; 1468 uint16_t combined_table[LIT_LEN + DIST_LEN]; 1469 uint64_t count_histogram[HUFF_LEN]; 1470 struct rl_code rl_huff[LIT_LEN + DIST_LEN]; 1471 uint32_t rl_huff_len; 1472 1473 uint32_t *dist_table = hufftables->dist_table; 1474 uint32_t *len_table = hufftables->len_table; 1475 uint16_t *lit_table = hufftables->lit_table; 1476 uint16_t *dcodes = hufftables->dcodes; 1477 uint8_t *lit_table_sizes = hufftables->lit_table_sizes; 1478 uint8_t *dcodes_sizes = hufftables->dcodes_sizes; 1479 uint8_t *deflate_hdr = hufftables->deflate_hdr; 1480 uint64_t *lit_len_histogram = histogram->lit_len_histogram; 1481 uint64_t *dist_histogram = histogram->dist_histogram; 1482 1483 memset(hufftables, 0, sizeof(struct isal_hufftables)); 1484 1485 heap_size = 1486 init_heap64_semi_complete(&heap_space, lit_len_histogram, LIT_LEN, 1487 ISAL_DEF_LIT_SYMBOLS); 1488 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1489 (struct huff_code *)lit_huff_table, LIT_LEN, MAX_DEFLATE_CODE_LEN); 1490 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count); 1491 1492 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN); 1493 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1494 (struct huff_code *)dist_huff_table, max_dist, 1495 MAX_DEFLATE_CODE_LEN); 1496 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count); 1497 1498 if (are_hufftables_useable(lit_huff_table, dist_huff_table)) { 1499 heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN); 1500 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1501 (struct huff_code *)lit_huff_table, LIT_LEN, 1502 MAX_SAFE_LIT_CODE_LEN); 1503 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count); 1504 1505 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN); 1506 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1507 (struct huff_code *)dist_huff_table, max_dist, 1508 MAX_SAFE_DIST_CODE_LEN); 1509 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count); 1510 1511 } 1512 1513 create_code_tables(dcodes, dcodes_sizes, DIST_LEN - DCODE_OFFSET, 1514 dist_huff_table + DCODE_OFFSET); 1515 1516 create_code_tables(lit_table, lit_table_sizes, IGZIP_LIT_TABLE_SIZE, lit_huff_table); 1517 1518 create_packed_len_table(len_table, lit_huff_table); 1519 create_packed_dist_table(dist_table, IGZIP_DIST_TABLE_SIZE, dist_huff_table); 1520 1521 set_buf(&header_bitbuf, deflate_hdr, sizeof(deflate_hdr)); 1522 init(&header_bitbuf); 1523 1524 hlit = max_lit_len_sym - 256; 1525 hdist = max_dist_sym; 1526 1527 /* Run length encode the length and distance huffman codes */ 1528 memset(count_histogram, 0, sizeof(count_histogram)); 1529 for (i = 0; i < 257 + hlit; i++) 1530 combined_table[i] = lit_huff_table[i].length; 1531 for (i = 0; i < 1 + hdist; i++) 1532 combined_table[i + hlit + 257] = dist_huff_table[i].length; 1533 rl_huff_len = 1534 rl_encode(combined_table, hlit + 257 + hdist + 1, count_histogram, rl_huff); 1535 1536 /* Create header */ 1537 bit_count = 1538 create_header(&header_bitbuf, rl_huff, rl_huff_len, 1539 count_histogram, hlit, hdist, LAST_BLOCK); 1540 flush(&header_bitbuf); 1541 1542 hufftables->deflate_hdr_count = bit_count / 8; 1543 hufftables->deflate_hdr_extra_bits = bit_count % 8; 1544 1545 return 0; 1546 } 1547 1548 void expand_hufftables_icf(struct hufftables_icf *hufftables) 1549 { 1550 uint32_t i, eb, j, k, len, code; 1551 struct huff_code orig[21], *p_code; 1552 struct huff_code *lit_len_codes = hufftables->lit_len_table; 1553 struct huff_code *dist_codes = hufftables->dist_table; 1554 1555 for (i = 0; i < 21; i++) 1556 orig[i] = lit_len_codes[i + 265]; 1557 1558 p_code = &lit_len_codes[265]; 1559 1560 i = 0; 1561 for (eb = 1; eb < 6; eb++) { 1562 for (k = 0; k < 4; k++) { 1563 len = orig[i].length; 1564 code = orig[i++].code; 1565 for (j = 0; j < (1u << eb); j++) { 1566 p_code->code_and_extra = code | (j << len); 1567 p_code->length = len + eb; 1568 p_code++; 1569 } 1570 } // end for k 1571 } // end for eb 1572 // fix up last record 1573 p_code[-1] = orig[i]; 1574 1575 dist_codes[DIST_LEN].code_and_extra = 0; 1576 dist_codes[DIST_LEN].length = 0; 1577 } 1578 1579 uint64_t 1580 create_hufftables_icf(struct BitBuf2 *bb, struct hufftables_icf *hufftables, 1581 struct isal_mod_hist *hist, uint32_t end_of_block) 1582 { 1583 uint32_t bl_count[MAX_DEFLATE_CODE_LEN + 1]; 1584 uint32_t max_ll_code, max_d_code; 1585 struct heap_tree heap_space; 1586 uint32_t heap_size; 1587 struct rl_code cl_tokens[LIT_LEN + DIST_LEN]; 1588 uint32_t num_cl_tokens; 1589 uint64_t cl_counts[CODE_LEN_CODES]; 1590 uint16_t combined_table[LIT_LEN + DIST_LEN]; 1591 int i; 1592 uint64_t compressed_len = 0; 1593 uint64_t static_compressed_len = 3; /* The static header size */ 1594 struct BitBuf2 bb_tmp; 1595 1596 struct huff_code *ll_codes = hufftables->lit_len_table; 1597 struct huff_code *d_codes = hufftables->dist_table; 1598 uint32_t *ll_hist = hist->ll_hist; 1599 uint32_t *d_hist = hist->d_hist; 1600 struct huff_code *static_ll_codes = static_hufftables.lit_len_table; 1601 struct huff_code *static_d_codes = static_hufftables.dist_table; 1602 1603 memcpy(&bb_tmp, bb, sizeof(struct BitBuf2)); 1604 1605 flatten_ll(hist->ll_hist); 1606 1607 // make sure EOB is present 1608 if (ll_hist[256] == 0) 1609 ll_hist[256] = 1; 1610 1611 heap_size = init_heap32(&heap_space, ll_hist, LIT_LEN); 1612 gen_huff_code_lens(&heap_space, heap_size, bl_count, 1613 ll_codes, LIT_LEN, MAX_DEFLATE_CODE_LEN); 1614 max_ll_code = set_huff_codes(ll_codes, LIT_LEN, bl_count); 1615 1616 heap_size = init_heap32(&heap_space, d_hist, DIST_LEN); 1617 gen_huff_code_lens(&heap_space, heap_size, bl_count, d_codes, 1618 DIST_LEN, MAX_DEFLATE_CODE_LEN); 1619 max_d_code = set_dist_huff_codes(d_codes, bl_count); 1620 1621 assert(max_ll_code >= 256); // must be EOB code 1622 assert(max_d_code != 0); 1623 1624 /* Run length encode the length and distance huffman codes */ 1625 memset(cl_counts, 0, sizeof(cl_counts)); 1626 1627 for (i = 0; i <= 256; i++) { 1628 combined_table[i] = ll_codes[i].length; 1629 compressed_len += ll_codes[i].length * ll_hist[i]; 1630 static_compressed_len += static_ll_codes[i].length * ll_hist[i]; 1631 } 1632 1633 for (; i < max_ll_code + 1; i++) { 1634 combined_table[i] = ll_codes[i].length; 1635 compressed_len += 1636 (ll_codes[i].length + len_code_extra_bits[i - 257]) * ll_hist[i]; 1637 static_compressed_len += 1638 (static_ll_codes[i].length + len_code_extra_bits[i - 257]) * ll_hist[i]; 1639 } 1640 1641 for (i = 0; i < max_d_code + 1; i++) { 1642 combined_table[i + max_ll_code + 1] = d_codes[i].length; 1643 compressed_len += (d_codes[i].length + dist_code_extra_bits[i]) * d_hist[i]; 1644 static_compressed_len += 1645 (static_d_codes[i].length + dist_code_extra_bits[i]) * d_hist[i]; 1646 } 1647 1648 if (static_compressed_len > compressed_len) { 1649 num_cl_tokens = rl_encode(combined_table, max_ll_code + max_d_code + 2, 1650 cl_counts, cl_tokens); 1651 1652 /* Create header */ 1653 create_header(bb, cl_tokens, num_cl_tokens, cl_counts, max_ll_code - 256, 1654 max_d_code, end_of_block); 1655 compressed_len += 8 * buffer_used(bb) + bb->m_bit_count; 1656 } 1657 1658 /* Substitute in static block since it creates smaller block */ 1659 if (static_compressed_len <= compressed_len) { 1660 memcpy(hufftables, &static_hufftables, sizeof(struct hufftables_icf)); 1661 memcpy(bb, &bb_tmp, sizeof(struct BitBuf2)); 1662 end_of_block = end_of_block ? 1 : 0; 1663 write_bits(bb, 0x2 | end_of_block, 3); 1664 compressed_len = static_compressed_len; 1665 } 1666 1667 expand_hufftables_icf(hufftables); 1668 return compressed_len; 1669 } 1670