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