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