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] = ((uint64_t) current - (uint64_t) start_stream) & 0xFFFF; 690 dist = ((uint64_t) current - (uint64_t) 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] = 709 ((uint64_t) next_hash - 710 (uint64_t) start_stream) & 0xFFFF; 711 } 712 713 dist_histogram[convert_dist_to_dist_sym(dist)] += 1; 714 lit_len_histogram[convert_length_to_len_sym(match_length)] += 715 1; 716 current += match_length - 1; 717 continue; 718 } 719 } 720 lit_len_histogram[literal & 0xFF] += 1; 721 } 722 literal = literal >> 8; 723 hash = compute_hash(literal) & HASH_MASK; 724 seen = last_seen[hash]; 725 last_seen[hash] = ((uint64_t) current - (uint64_t) start_stream) & 0xFFFF; 726 dist = ((uint64_t) current - (uint64_t) start_stream - seen) & 0xFFFF; 727 if (dist < D) { 728 match_length = compare258(current - dist, current, end_stream - current); 729 if (match_length >= SHORTEST_MATCH) { 730 dist_histogram[convert_dist_to_dist_sym(dist)] += 1; 731 lit_len_histogram[convert_length_to_len_sym(match_length)] += 1; 732 lit_len_histogram[256] += 1; 733 return; 734 } 735 } else 736 lit_len_histogram[literal & 0xFF] += 1; 737 lit_len_histogram[(literal >> 8) & 0xFF] += 1; 738 lit_len_histogram[(literal >> 16) & 0xFF] += 1; 739 lit_len_histogram[256] += 1; 740 return; 741 } 742 743 uint32_t convert_dist_to_dist_sym(uint32_t dist) 744 { 745 assert(dist <= 32768 && dist > 0); 746 if (dist <= 2) 747 return dist - 1; 748 else if (dist <= 4) 749 return 0 + (dist - 1) / 1; 750 else if (dist <= 8) 751 return 2 + (dist - 1) / 2; 752 else if (dist <= 16) 753 return 4 + (dist - 1) / 4; 754 else if (dist <= 32) 755 return 6 + (dist - 1) / 8; 756 else if (dist <= 64) 757 return 8 + (dist - 1) / 16; 758 else if (dist <= 128) 759 return 10 + (dist - 1) / 32; 760 else if (dist <= 256) 761 return 12 + (dist - 1) / 64; 762 else if (dist <= 512) 763 return 14 + (dist - 1) / 128; 764 else if (dist <= 1024) 765 return 16 + (dist - 1) / 256; 766 else if (dist <= 2048) 767 return 18 + (dist - 1) / 512; 768 else if (dist <= 4096) 769 return 20 + (dist - 1) / 1024; 770 else if (dist <= 8192) 771 return 22 + (dist - 1) / 2048; 772 else if (dist <= 16384) 773 return 24 + (dist - 1) / 4096; 774 else if (dist <= 32768) 775 return 26 + (dist - 1) / 8192; 776 else 777 return ~0; /* ~0 is an invalid distance code */ 778 779 } 780 781 uint32_t convert_length_to_len_sym(uint32_t length) 782 { 783 assert(length > 2 && length < 259); 784 785 /* Based on tables on page 11 in RFC 1951 */ 786 if (length < 11) 787 return 257 + length - 3; 788 else if (length < 19) 789 return 261 + (length - 3) / 2; 790 else if (length < 35) 791 return 265 + (length - 3) / 4; 792 else if (length < 67) 793 return 269 + (length - 3) / 8; 794 else if (length < 131) 795 return 273 + (length - 3) / 16; 796 else if (length < 258) 797 return 277 + (length - 3) / 32; 798 else 799 return 285; 800 } 801 802 // Upon return, codes[] contains the code lengths, 803 // and bl_count is the count of the lengths 804 805 /* Init heap with the histogram, and return the histogram size */ 806 static inline uint32_t init_heap32(struct heap_tree *heap_space, uint32_t * histogram, 807 uint32_t hist_size) 808 { 809 uint32_t heap_size, i; 810 811 memset(heap_space, 0, sizeof(struct heap_tree)); 812 813 heap_size = 0; 814 for (i = 0; i < hist_size; i++) { 815 if (histogram[i] != 0) 816 heap_space->heap[++heap_size] = 817 (((uint64_t) histogram[i]) << FREQ_SHIFT) | i; 818 } 819 820 // make sure heap has at least two elements in it 821 if (heap_size < 2) { 822 if (heap_size == 0) { 823 heap_space->heap[1] = 1ULL << FREQ_SHIFT; 824 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1; 825 heap_size = 2; 826 } else { 827 // heap size == 1 828 if (histogram[0] == 0) 829 heap_space->heap[2] = 1ULL << FREQ_SHIFT; 830 else 831 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1; 832 heap_size = 2; 833 } 834 } 835 836 build_heap(heap_space->heap, heap_size); 837 838 return heap_size; 839 } 840 841 static inline uint32_t init_heap64(struct heap_tree *heap_space, uint64_t * histogram, 842 uint64_t hist_size) 843 { 844 uint32_t heap_size, i; 845 846 memset(heap_space, 0, sizeof(struct heap_tree)); 847 848 heap_size = 0; 849 for (i = 0; i < hist_size; i++) { 850 if (histogram[i] != 0) 851 heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT) | i; 852 } 853 854 // make sure heap has at least two elements in it 855 if (heap_size < 2) { 856 if (heap_size == 0) { 857 heap_space->heap[1] = 1ULL << FREQ_SHIFT; 858 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1; 859 heap_size = 2; 860 } else { 861 // heap size == 1 862 if (histogram[0] == 0) 863 heap_space->heap[2] = 1ULL << FREQ_SHIFT; 864 else 865 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1; 866 heap_size = 2; 867 } 868 } 869 870 build_heap(heap_space->heap, heap_size); 871 872 return heap_size; 873 } 874 875 static inline uint32_t init_heap64_complete(struct heap_tree *heap_space, uint64_t * histogram, 876 uint64_t hist_size) 877 { 878 uint32_t heap_size, i; 879 880 memset(heap_space, 0, sizeof(struct heap_tree)); 881 882 heap_size = 0; 883 for (i = 0; i < hist_size; i++) 884 heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT) | i; 885 886 build_heap(heap_space->heap, heap_size); 887 888 return heap_size; 889 } 890 891 static inline uint32_t fix_code_lens(struct heap_tree *heap_space, uint32_t root_node, 892 uint32_t * bl_count, uint32_t max_code_len) 893 { 894 struct tree_node *tree = heap_space->tree; 895 uint64_t *code_len_count = heap_space->code_len_count; 896 uint32_t i, j, k, child, depth, code_len; 897 898 // compute code lengths and code length counts 899 code_len = 0; 900 j = root_node; 901 for (i = root_node; i <= HEAP_TREE_NODE_START; i++) { 902 child = tree[i].child; 903 if (child > MAX_HISTHEAP_SIZE) { 904 depth = 1 + tree[i].depth; 905 906 tree[child].depth = depth; 907 tree[child - 1].depth = depth; 908 } else { 909 tree[j++] = tree[i]; 910 depth = tree[i].depth; 911 while (code_len < depth) { 912 code_len++; 913 code_len_count[code_len] = 0; 914 } 915 code_len_count[depth]++; 916 } 917 } 918 919 if (code_len > max_code_len) { 920 while (code_len > max_code_len) { 921 assert(code_len_count[code_len] > 1); 922 for (i = max_code_len - 1; i != 0; i--) 923 if (code_len_count[i] != 0) 924 break; 925 assert(i != 0); 926 code_len_count[i]--; 927 code_len_count[i + 1] += 2; 928 code_len_count[code_len - 1]++; 929 code_len_count[code_len] -= 2; 930 if (code_len_count[code_len] == 0) 931 code_len--; 932 } 933 934 for (i = 1; i <= code_len; i++) 935 bl_count[i] = code_len_count[i]; 936 for (; i <= max_code_len; i++) 937 bl_count[i] = 0; 938 939 for (k = 1; code_len_count[k] == 0; k++) ; 940 for (i = root_node; i < j; i++) { 941 tree[i].depth = k; 942 code_len_count[k]--; 943 for (; code_len_count[k] == 0; k++) ; 944 } 945 } else { 946 for (i = 1; i <= code_len; i++) 947 bl_count[i] = code_len_count[i]; 948 for (; i <= max_code_len; i++) 949 bl_count[i] = 0; 950 } 951 952 return j; 953 954 } 955 956 static inline void 957 gen_huff_code_lens(struct heap_tree *heap_space, uint32_t heap_size, uint32_t * bl_count, 958 struct huff_code *codes, uint32_t codes_count, uint32_t max_code_len) 959 { 960 struct tree_node *tree = heap_space->tree; 961 uint32_t root_node = HEAP_TREE_NODE_START, node_ptr; 962 uint32_t end_node; 963 964 root_node = build_huff_tree(heap_space, heap_size, root_node); 965 966 end_node = fix_code_lens(heap_space, root_node, bl_count, max_code_len); 967 968 memset(codes, 0, codes_count * sizeof(*codes)); 969 for (node_ptr = root_node; node_ptr < end_node; node_ptr++) 970 codes[tree[node_ptr].child].length = tree[node_ptr].depth; 971 972 } 973 974 inline uint32_t set_huff_codes(struct huff_code *huff_code_table, int table_length, 975 uint32_t * count) 976 { 977 /* Uses the algorithm mentioned in the deflate standard, Rfc 1951. */ 978 int i; 979 uint16_t code = 0; 980 uint16_t next_code[MAX_HUFF_TREE_DEPTH + 1]; 981 uint32_t max_code = 0; 982 983 next_code[0] = code; 984 985 for (i = 1; i < MAX_HUFF_TREE_DEPTH + 1; i++) 986 next_code[i] = (next_code[i - 1] + count[i - 1]) << 1; 987 988 for (i = 0; i < table_length; i++) { 989 if (huff_code_table[i].length != 0) { 990 huff_code_table[i].code = 991 bit_reverse(next_code[huff_code_table[i].length], 992 huff_code_table[i].length); 993 next_code[huff_code_table[i].length] += 1; 994 max_code = i; 995 } 996 } 997 998 return max_code; 999 } 1000 1001 // on input, codes contain the code lengths 1002 // on output, code contains: 1003 // 23:16 code length 1004 // 15:0 code value in low order bits 1005 // returns max code value 1006 static inline uint32_t set_dist_huff_codes(struct huff_code *codes, uint32_t * bl_count) 1007 { 1008 uint32_t code, code_len, bits, i; 1009 uint32_t next_code[MAX_DEFLATE_CODE_LEN + 1]; 1010 uint32_t max_code = 0; 1011 const uint32_t num_codes = DIST_LEN; 1012 1013 code = bl_count[0] = 0; 1014 for (bits = 1; bits <= MAX_HUFF_TREE_DEPTH; bits++) { 1015 code = (code + bl_count[bits - 1]) << 1; 1016 next_code[bits] = code; 1017 } 1018 for (i = 0; i < num_codes; i++) { 1019 code_len = codes[i].length; 1020 if (code_len != 0) { 1021 codes[i].code = bit_reverse(next_code[code_len], code_len); 1022 codes[i].extra_bit_count = dist_code_extra_bits[i]; 1023 next_code[code_len] += 1; 1024 max_code = i; 1025 } 1026 } 1027 return max_code; 1028 } 1029 1030 int create_huffman_header(struct BitBuf2 *header_bitbuf, 1031 struct huff_code *lookup_table, 1032 struct rl_code *huffman_rep, 1033 uint16_t huffman_rep_length, uint32_t end_of_block, 1034 uint32_t hclen, uint32_t hlit, uint32_t hdist) 1035 { 1036 /* hlit, hdist, hclen are as defined in the deflate standard, head is the 1037 * first three deflate header bits.*/ 1038 int i; 1039 uint64_t bit_count; 1040 uint64_t data; 1041 struct huff_code huffman_value; 1042 const uint32_t extra_bits[3] = { 2, 3, 7 }; 1043 1044 bit_count = buffer_bits_used(header_bitbuf); 1045 1046 data = (end_of_block ? 5 : 4) | (hlit << 3) | (hdist << 8) | (hclen << 13); 1047 data |= ((lookup_table[code_length_code_order[0]].length) << DYN_HDR_START_LEN); 1048 write_bits(header_bitbuf, data, DYN_HDR_START_LEN + 3); 1049 data = 0; 1050 for (i = hclen + 3; i >= 1; i--) 1051 data = (data << 3) | lookup_table[code_length_code_order[i]].length; 1052 1053 write_bits(header_bitbuf, data, (hclen + 3) * 3); 1054 1055 for (i = 0; i < huffman_rep_length; i++) { 1056 huffman_value = lookup_table[huffman_rep[i].code]; 1057 1058 write_bits(header_bitbuf, (uint64_t) huffman_value.code, 1059 (uint32_t) huffman_value.length); 1060 1061 if (huffman_rep[i].code > 15) { 1062 write_bits(header_bitbuf, (uint64_t) huffman_rep[i].extra_bits, 1063 (uint32_t) extra_bits[huffman_rep[i].code - 16]); 1064 } 1065 } 1066 bit_count = buffer_bits_used(header_bitbuf) - bit_count; 1067 1068 return bit_count; 1069 } 1070 1071 inline int create_header(struct BitBuf2 *header_bitbuf, struct rl_code *huffman_rep, 1072 uint32_t length, uint64_t * histogram, uint32_t hlit, 1073 uint32_t hdist, uint32_t end_of_block) 1074 { 1075 int i; 1076 1077 uint32_t heap_size; 1078 struct heap_tree heap_space; 1079 uint32_t code_len_count[MAX_HUFF_TREE_DEPTH + 1]; 1080 struct huff_code lookup_table[HUFF_LEN]; 1081 1082 /* hlit, hdist, and hclen are defined in RFC 1951 page 13 */ 1083 uint32_t hclen; 1084 uint64_t bit_count; 1085 1086 /* Create a huffman tree to encode run length encoded representation. */ 1087 heap_size = init_heap64(&heap_space, histogram, HUFF_LEN); 1088 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1089 (struct huff_code *)lookup_table, HUFF_LEN, 7); 1090 set_huff_codes(lookup_table, HUFF_LEN, code_len_count); 1091 1092 /* Calculate hclen */ 1093 for (i = CODE_LEN_CODES - 1; i > 3; i--) /* i must be at least 4 */ 1094 if (lookup_table[code_length_code_order[i]].length != 0) 1095 break; 1096 1097 hclen = i - 3; 1098 1099 /* Generate actual header. */ 1100 bit_count = create_huffman_header(header_bitbuf, lookup_table, huffman_rep, 1101 length, end_of_block, hclen, hlit, hdist); 1102 1103 return bit_count; 1104 } 1105 1106 static inline 1107 struct rl_code *write_rl(struct rl_code *pout, uint16_t last_len, uint32_t run_len, 1108 uint64_t * counts) 1109 { 1110 if (last_len == 0) { 1111 while (run_len > 138) { 1112 pout->code = 18; 1113 pout->extra_bits = 138 - 11; 1114 pout++; 1115 run_len -= 138; 1116 counts[18]++; 1117 } 1118 // 1 <= run_len <= 138 1119 if (run_len > 10) { 1120 pout->code = 18; 1121 pout->extra_bits = run_len - 11; 1122 pout++; 1123 counts[18]++; 1124 } else if (run_len > 2) { 1125 pout->code = 17; 1126 pout->extra_bits = run_len - 3; 1127 pout++; 1128 counts[17]++; 1129 } else if (run_len == 1) { 1130 pout->code = 0; 1131 pout->extra_bits = 0; 1132 pout++; 1133 counts[0]++; 1134 } else { 1135 assert(run_len == 2); 1136 pout[0].code = 0; 1137 pout[0].extra_bits = 0; 1138 pout[1].code = 0; 1139 pout[1].extra_bits = 0; 1140 pout += 2; 1141 counts[0] += 2; 1142 } 1143 } else { 1144 // last_len != 0 1145 pout->code = last_len; 1146 pout->extra_bits = 0; 1147 pout++; 1148 counts[last_len]++; 1149 run_len--; 1150 if (run_len != 0) { 1151 while (run_len > 6) { 1152 pout->code = 16; 1153 pout->extra_bits = 6 - 3; 1154 pout++; 1155 run_len -= 6; 1156 counts[16]++; 1157 } 1158 // 1 <= run_len <= 6 1159 switch (run_len) { 1160 case 1: 1161 pout->code = last_len; 1162 pout->extra_bits = 0; 1163 pout++; 1164 counts[last_len]++; 1165 break; 1166 case 2: 1167 pout[0].code = last_len; 1168 pout[0].extra_bits = 0; 1169 pout[1].code = last_len; 1170 pout[1].extra_bits = 0; 1171 pout += 2; 1172 counts[last_len] += 2; 1173 break; 1174 default: // 3...6 1175 pout->code = 16; 1176 pout->extra_bits = run_len - 3; 1177 pout++; 1178 counts[16]++; 1179 } 1180 } 1181 } 1182 return pout; 1183 } 1184 1185 // convert codes into run-length symbols, write symbols into OUT 1186 // generate histogram into COUNTS (assumed to be initialized to 0) 1187 // Format of OUT: 1188 // 4:0 code (0...18) 1189 // 15:8 Extra bits (0...127) 1190 // returns number of symbols in out 1191 static inline uint32_t rl_encode(uint16_t * codes, uint32_t num_codes, uint64_t * counts, 1192 struct rl_code *out) 1193 { 1194 uint32_t i, run_len; 1195 uint16_t last_len, len; 1196 struct rl_code *pout; 1197 1198 pout = out; 1199 last_len = codes[0]; 1200 run_len = 1; 1201 for (i = 1; i < num_codes; i++) { 1202 len = codes[i]; 1203 if (len == last_len) { 1204 run_len++; 1205 continue; 1206 } 1207 pout = write_rl(pout, last_len, run_len, counts); 1208 last_len = len; 1209 run_len = 1; 1210 } 1211 pout = write_rl(pout, last_len, run_len, counts); 1212 1213 return (uint32_t) (pout - out); 1214 } 1215 1216 void create_code_tables(uint16_t * code_table, uint8_t * code_length_table, uint32_t length, 1217 struct huff_code *hufftable) 1218 { 1219 int i; 1220 for (i = 0; i < length; i++) { 1221 code_table[i] = hufftable[i].code; 1222 code_length_table[i] = hufftable[i].length; 1223 } 1224 } 1225 1226 void create_packed_len_table(uint32_t * packed_table, struct huff_code *lit_len_hufftable) 1227 { 1228 int i, count = 0; 1229 uint16_t extra_bits; 1230 uint16_t extra_bits_count = 0; 1231 1232 /* Gain extra bits is the next place where the number of extra bits in 1233 * lenght codes increases. */ 1234 uint16_t gain_extra_bits = LEN_EXTRA_BITS_START; 1235 1236 for (i = 257; i < LIT_LEN - 1; i++) { 1237 for (extra_bits = 0; extra_bits < (1 << extra_bits_count); extra_bits++) { 1238 if (count > 254) 1239 break; 1240 packed_table[count++] = 1241 (extra_bits << (lit_len_hufftable[i].length + LENGTH_BITS)) | 1242 (lit_len_hufftable[i].code << LENGTH_BITS) | 1243 (lit_len_hufftable[i].length + extra_bits_count); 1244 } 1245 1246 if (i == gain_extra_bits) { 1247 gain_extra_bits += LEN_EXTRA_BITS_INTERVAL; 1248 extra_bits_count += 1; 1249 } 1250 } 1251 1252 packed_table[count] = (lit_len_hufftable[LIT_LEN - 1].code << LENGTH_BITS) | 1253 (lit_len_hufftable[LIT_LEN - 1].length); 1254 } 1255 1256 void create_packed_dist_table(uint32_t * packed_table, uint32_t length, 1257 struct huff_code *dist_hufftable) 1258 { 1259 int i, count = 0; 1260 uint16_t extra_bits; 1261 uint16_t extra_bits_count = 0; 1262 1263 /* Gain extra bits is the next place where the number of extra bits in 1264 * distance codes increases. */ 1265 uint16_t gain_extra_bits = DIST_EXTRA_BITS_START; 1266 1267 for (i = 0; i < DIST_LEN; i++) { 1268 for (extra_bits = 0; extra_bits < (1 << extra_bits_count); extra_bits++) { 1269 if (count >= length) 1270 return; 1271 1272 packed_table[count++] = 1273 (extra_bits << (dist_hufftable[i].length + LENGTH_BITS)) | 1274 (dist_hufftable[i].code << LENGTH_BITS) | 1275 (dist_hufftable[i].length + extra_bits_count); 1276 1277 } 1278 1279 if (i == gain_extra_bits) { 1280 gain_extra_bits += DIST_EXTRA_BITS_INTERVAL; 1281 extra_bits_count += 1; 1282 } 1283 } 1284 } 1285 1286 int are_hufftables_useable(struct huff_code *lit_len_hufftable, 1287 struct huff_code *dist_hufftable) 1288 { 1289 int max_lit_code_len = 0, max_len_code_len = 0, max_dist_code_len = 0; 1290 int dist_extra_bits = 0, len_extra_bits = 0; 1291 int gain_dist_extra_bits = DIST_EXTRA_BITS_START; 1292 int gain_len_extra_bits = LEN_EXTRA_BITS_START; 1293 int max_code_len; 1294 int i; 1295 1296 for (i = 0; i < LIT_LEN; i++) 1297 if (lit_len_hufftable[i].length > max_lit_code_len) 1298 max_lit_code_len = lit_len_hufftable[i].length; 1299 1300 for (i = 257; i < LIT_LEN - 1; i++) { 1301 if (lit_len_hufftable[i].length + len_extra_bits > max_len_code_len) 1302 max_len_code_len = lit_len_hufftable[i].length + len_extra_bits; 1303 1304 if (i == gain_len_extra_bits) { 1305 gain_len_extra_bits += LEN_EXTRA_BITS_INTERVAL; 1306 len_extra_bits += 1; 1307 } 1308 } 1309 1310 for (i = 0; i < DIST_LEN; i++) { 1311 if (dist_hufftable[i].length + dist_extra_bits > max_dist_code_len) 1312 max_dist_code_len = dist_hufftable[i].length + dist_extra_bits; 1313 1314 if (i == gain_dist_extra_bits) { 1315 gain_dist_extra_bits += DIST_EXTRA_BITS_INTERVAL; 1316 dist_extra_bits += 1; 1317 } 1318 } 1319 1320 max_code_len = max_lit_code_len + max_len_code_len + max_dist_code_len; 1321 1322 /* Some versions of igzip can write upto one literal, one length and one 1323 * distance code at the same time. This checks to make sure that is 1324 * always writeable in bitbuf*/ 1325 return (max_code_len > MAX_BITBUF_BIT_WRITE); 1326 } 1327 1328 int isal_create_hufftables(struct isal_hufftables *hufftables, 1329 struct isal_huff_histogram *histogram) 1330 { 1331 struct huff_code lit_huff_table[LIT_LEN], dist_huff_table[DIST_LEN]; 1332 uint64_t bit_count; 1333 int max_dist = convert_dist_to_dist_sym(IGZIP_HIST_SIZE); 1334 struct heap_tree heap_space; 1335 uint32_t heap_size; 1336 uint32_t code_len_count[MAX_HUFF_TREE_DEPTH + 1]; 1337 struct BitBuf2 header_bitbuf; 1338 uint32_t max_lit_len_sym; 1339 uint32_t max_dist_sym; 1340 uint32_t hlit, hdist, i; 1341 uint16_t combined_table[LIT_LEN + DIST_LEN]; 1342 uint64_t count_histogram[HUFF_LEN]; 1343 struct rl_code rl_huff[LIT_LEN + DIST_LEN]; 1344 uint32_t rl_huff_len; 1345 1346 uint32_t *dist_table = hufftables->dist_table; 1347 uint32_t *len_table = hufftables->len_table; 1348 uint16_t *lit_table = hufftables->lit_table; 1349 uint16_t *dcodes = hufftables->dcodes; 1350 uint8_t *lit_table_sizes = hufftables->lit_table_sizes; 1351 uint8_t *dcodes_sizes = hufftables->dcodes_sizes; 1352 uint8_t *deflate_hdr = hufftables->deflate_hdr; 1353 uint64_t *lit_len_histogram = histogram->lit_len_histogram; 1354 uint64_t *dist_histogram = histogram->dist_histogram; 1355 1356 memset(hufftables, 0, sizeof(struct isal_hufftables)); 1357 1358 heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN); 1359 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1360 (struct huff_code *)lit_huff_table, LIT_LEN, MAX_DEFLATE_CODE_LEN); 1361 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count); 1362 1363 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN); 1364 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1365 (struct huff_code *)dist_huff_table, max_dist, 1366 MAX_DEFLATE_CODE_LEN); 1367 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count); 1368 1369 if (are_hufftables_useable(lit_huff_table, dist_huff_table)) { 1370 heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN); 1371 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1372 (struct huff_code *)lit_huff_table, LIT_LEN, 1373 MAX_SAFE_LIT_CODE_LEN); 1374 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count); 1375 1376 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN); 1377 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1378 (struct huff_code *)dist_huff_table, max_dist, 1379 MAX_SAFE_DIST_CODE_LEN); 1380 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count); 1381 1382 } 1383 1384 create_code_tables(dcodes, dcodes_sizes, DIST_LEN - DCODE_OFFSET, 1385 dist_huff_table + DCODE_OFFSET); 1386 1387 create_code_tables(lit_table, lit_table_sizes, IGZIP_LIT_TABLE_SIZE, lit_huff_table); 1388 1389 create_packed_len_table(len_table, lit_huff_table); 1390 create_packed_dist_table(dist_table, IGZIP_DIST_TABLE_SIZE, dist_huff_table); 1391 1392 set_buf(&header_bitbuf, deflate_hdr, sizeof(deflate_hdr)); 1393 init(&header_bitbuf); 1394 1395 hlit = max_lit_len_sym - 256; 1396 hdist = max_dist_sym; 1397 1398 /* Run length encode the length and distance huffman codes */ 1399 memset(count_histogram, 0, sizeof(count_histogram)); 1400 for (i = 0; i < 257 + hlit; i++) 1401 combined_table[i] = lit_huff_table[i].length; 1402 for (i = 0; i < 1 + hdist; i++) 1403 combined_table[i + hlit + 257] = dist_huff_table[i].length; 1404 rl_huff_len = 1405 rl_encode(combined_table, hlit + 257 + hdist + 1, count_histogram, rl_huff); 1406 1407 /* Create header */ 1408 bit_count = 1409 create_header(&header_bitbuf, rl_huff, rl_huff_len, 1410 count_histogram, hlit, hdist, LAST_BLOCK); 1411 flush(&header_bitbuf); 1412 1413 hufftables->deflate_hdr_count = bit_count / 8; 1414 hufftables->deflate_hdr_extra_bits = bit_count % 8; 1415 1416 return 0; 1417 } 1418 1419 int isal_create_hufftables_subset(struct isal_hufftables *hufftables, 1420 struct isal_huff_histogram *histogram) 1421 { 1422 struct huff_code lit_huff_table[LIT_LEN], dist_huff_table[DIST_LEN]; 1423 uint64_t bit_count; 1424 int max_dist = convert_dist_to_dist_sym(IGZIP_HIST_SIZE); 1425 struct heap_tree heap_space; 1426 uint32_t heap_size; 1427 uint32_t code_len_count[MAX_HUFF_TREE_DEPTH + 1]; 1428 struct BitBuf2 header_bitbuf; 1429 uint32_t max_lit_len_sym; 1430 uint32_t max_dist_sym; 1431 uint32_t hlit, hdist, i; 1432 uint16_t combined_table[LIT_LEN + DIST_LEN]; 1433 uint64_t count_histogram[HUFF_LEN]; 1434 struct rl_code rl_huff[LIT_LEN + DIST_LEN]; 1435 uint32_t rl_huff_len; 1436 1437 uint32_t *dist_table = hufftables->dist_table; 1438 uint32_t *len_table = hufftables->len_table; 1439 uint16_t *lit_table = hufftables->lit_table; 1440 uint16_t *dcodes = hufftables->dcodes; 1441 uint8_t *lit_table_sizes = hufftables->lit_table_sizes; 1442 uint8_t *dcodes_sizes = hufftables->dcodes_sizes; 1443 uint8_t *deflate_hdr = hufftables->deflate_hdr; 1444 uint64_t *lit_len_histogram = histogram->lit_len_histogram; 1445 uint64_t *dist_histogram = histogram->dist_histogram; 1446 1447 memset(hufftables, 0, sizeof(struct isal_hufftables)); 1448 1449 heap_size = init_heap64(&heap_space, lit_len_histogram, LIT_LEN); 1450 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1451 (struct huff_code *)lit_huff_table, LIT_LEN, MAX_DEFLATE_CODE_LEN); 1452 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count); 1453 1454 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN); 1455 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1456 (struct huff_code *)dist_huff_table, max_dist, 1457 MAX_DEFLATE_CODE_LEN); 1458 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count); 1459 1460 if (are_hufftables_useable(lit_huff_table, dist_huff_table)) { 1461 heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN); 1462 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1463 (struct huff_code *)lit_huff_table, LIT_LEN, 1464 MAX_SAFE_LIT_CODE_LEN); 1465 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count); 1466 1467 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN); 1468 gen_huff_code_lens(&heap_space, heap_size, code_len_count, 1469 (struct huff_code *)dist_huff_table, max_dist, 1470 MAX_SAFE_DIST_CODE_LEN); 1471 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count); 1472 1473 } 1474 1475 create_code_tables(dcodes, dcodes_sizes, DIST_LEN - DCODE_OFFSET, 1476 dist_huff_table + DCODE_OFFSET); 1477 1478 create_code_tables(lit_table, lit_table_sizes, IGZIP_LIT_TABLE_SIZE, lit_huff_table); 1479 1480 create_packed_len_table(len_table, lit_huff_table); 1481 create_packed_dist_table(dist_table, IGZIP_DIST_TABLE_SIZE, dist_huff_table); 1482 1483 set_buf(&header_bitbuf, deflate_hdr, sizeof(deflate_hdr)); 1484 init(&header_bitbuf); 1485 1486 hlit = max_lit_len_sym - 256; 1487 hdist = max_dist_sym; 1488 1489 /* Run length encode the length and distance huffman codes */ 1490 memset(count_histogram, 0, sizeof(count_histogram)); 1491 for (i = 0; i < 257 + hlit; i++) 1492 combined_table[i] = lit_huff_table[i].length; 1493 for (i = 0; i < 1 + hdist; i++) 1494 combined_table[i + hlit + 257] = dist_huff_table[i].length; 1495 rl_huff_len = 1496 rl_encode(combined_table, hlit + 257 + hdist + 1, count_histogram, rl_huff); 1497 1498 /* Create header */ 1499 bit_count = 1500 create_header(&header_bitbuf, rl_huff, rl_huff_len, 1501 count_histogram, hlit, hdist, LAST_BLOCK); 1502 flush(&header_bitbuf); 1503 1504 hufftables->deflate_hdr_count = bit_count / 8; 1505 hufftables->deflate_hdr_extra_bits = bit_count % 8; 1506 1507 return 0; 1508 } 1509 1510 void expand_hufftables_icf(struct hufftables_icf *hufftables) 1511 { 1512 uint32_t i, eb, j, k, len, code; 1513 struct huff_code orig[21], *p_code; 1514 struct huff_code *lit_len_codes = hufftables->lit_len_table; 1515 struct huff_code *dist_codes = hufftables->dist_table; 1516 1517 for (i = 0; i < 21; i++) 1518 orig[i] = lit_len_codes[i + 265]; 1519 1520 p_code = &lit_len_codes[265]; 1521 1522 i = 0; 1523 for (eb = 1; eb < 6; eb++) { 1524 for (k = 0; k < 4; k++) { 1525 len = orig[i].length; 1526 code = orig[i++].code; 1527 for (j = 0; j < (1u << eb); j++) { 1528 p_code->code_and_extra = code | (j << len); 1529 p_code->length = len + eb; 1530 p_code++; 1531 } 1532 } // end for k 1533 } // end for eb 1534 // fix up last record 1535 p_code[-1] = orig[i]; 1536 1537 dist_codes[DIST_LEN].code_and_extra = 0; 1538 dist_codes[DIST_LEN].length = 0; 1539 } 1540 1541 void 1542 create_hufftables_icf(struct BitBuf2 *bb, struct hufftables_icf *hufftables, 1543 struct isal_mod_hist *hist, uint32_t end_of_block) 1544 { 1545 uint32_t bl_count[MAX_DEFLATE_CODE_LEN + 1]; 1546 uint32_t max_ll_code, max_d_code; 1547 struct heap_tree heap_space; 1548 uint32_t heap_size; 1549 struct rl_code cl_tokens[LIT_LEN + DIST_LEN]; 1550 uint32_t num_cl_tokens; 1551 uint64_t cl_counts[CODE_LEN_CODES]; 1552 uint16_t combined_table[LIT_LEN + DIST_LEN]; 1553 int i; 1554 uint64_t compressed_len = 0; 1555 uint64_t static_compressed_len = 3; /* The static header size */ 1556 struct BitBuf2 bb_tmp; 1557 1558 struct huff_code *ll_codes = hufftables->lit_len_table; 1559 struct huff_code *d_codes = hufftables->dist_table; 1560 uint32_t *ll_hist = hist->ll_hist; 1561 uint32_t *d_hist = hist->d_hist; 1562 struct huff_code *static_ll_codes = static_hufftables.lit_len_table; 1563 struct huff_code *static_d_codes = static_hufftables.dist_table; 1564 1565 memcpy(&bb_tmp, bb, sizeof(struct BitBuf2)); 1566 1567 flatten_ll(hist->ll_hist); 1568 1569 // make sure EOB is present 1570 if (ll_hist[256] == 0) 1571 ll_hist[256] = 1; 1572 1573 heap_size = init_heap32(&heap_space, ll_hist, LIT_LEN); 1574 gen_huff_code_lens(&heap_space, heap_size, bl_count, 1575 ll_codes, LIT_LEN, MAX_DEFLATE_CODE_LEN); 1576 max_ll_code = set_huff_codes(ll_codes, LIT_LEN, bl_count); 1577 1578 heap_size = init_heap32(&heap_space, d_hist, DIST_LEN); 1579 gen_huff_code_lens(&heap_space, heap_size, bl_count, d_codes, 1580 DIST_LEN, MAX_DEFLATE_CODE_LEN); 1581 max_d_code = set_dist_huff_codes(d_codes, bl_count); 1582 1583 assert(max_ll_code >= 256); // must be EOB code 1584 assert(max_d_code != 0); 1585 1586 /* Run length encode the length and distance huffman codes */ 1587 memset(cl_counts, 0, sizeof(cl_counts)); 1588 1589 for (i = 0; i <= 256; i++) { 1590 combined_table[i] = ll_codes[i].length; 1591 compressed_len += ll_codes[i].length * ll_hist[i]; 1592 static_compressed_len += static_ll_codes[i].length * ll_hist[i]; 1593 } 1594 1595 for (; i < max_ll_code + 1; i++) { 1596 combined_table[i] = ll_codes[i].length; 1597 compressed_len += 1598 (ll_codes[i].length + len_code_extra_bits[i - 257]) * ll_hist[i]; 1599 static_compressed_len += 1600 (static_ll_codes[i].length + len_code_extra_bits[i - 257]) * ll_hist[i]; 1601 } 1602 1603 for (i = 0; i < max_d_code + 1; i++) { 1604 combined_table[i + max_ll_code + 1] = d_codes[i].length; 1605 compressed_len += (d_codes[i].length + dist_code_extra_bits[i]) * d_hist[i]; 1606 static_compressed_len += 1607 (static_d_codes[i].length + dist_code_extra_bits[i]) * d_hist[i]; 1608 } 1609 1610 expand_hufftables_icf(hufftables); 1611 1612 num_cl_tokens = 1613 rl_encode(combined_table, max_ll_code + max_d_code + 2, cl_counts, cl_tokens); 1614 1615 /* Create header */ 1616 create_header(bb, cl_tokens, num_cl_tokens, cl_counts, max_ll_code - 256, max_d_code, 1617 end_of_block); 1618 compressed_len += 8 * buffer_used(bb) + bb->m_bit_count; 1619 1620 if (static_compressed_len < compressed_len) { 1621 memcpy(hufftables, &static_hufftables, sizeof(struct hufftables_icf)); 1622 expand_hufftables_icf(hufftables); 1623 memcpy(bb, &bb_tmp, sizeof(struct BitBuf2)); 1624 end_of_block = end_of_block ? 1 : 0; 1625 write_bits(bb, 0x2 | end_of_block, 3); 1626 } 1627 } 1628