2016-06-02 22:52:23 +02:00
|
|
|
/**********************************************************************
|
|
|
|
|
Copyright(c) 2011-2016 Intel Corporation All rights reserved.
|
|
|
|
|
|
|
|
|
|
Redistribution and use in source and binary forms, with or without
|
|
|
|
|
modification, are permitted provided that the following conditions
|
|
|
|
|
are met:
|
|
|
|
|
* Redistributions of source code must retain the above copyright
|
|
|
|
|
notice, this list of conditions and the following disclaimer.
|
|
|
|
|
* Redistributions in binary form must reproduce the above copyright
|
|
|
|
|
notice, this list of conditions and the following disclaimer in
|
|
|
|
|
the documentation and/or other materials provided with the
|
|
|
|
|
distribution.
|
|
|
|
|
* Neither the name of Intel Corporation nor the names of its
|
|
|
|
|
contributors may be used to endorse or promote products derived
|
|
|
|
|
from this software without specific prior written permission.
|
|
|
|
|
|
|
|
|
|
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
|
|
|
|
|
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
|
|
|
|
|
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
|
|
|
|
|
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
|
|
|
|
|
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
|
|
|
|
|
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
|
|
|
|
|
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
|
|
|
|
|
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
|
|
|
|
|
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
|
|
|
|
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
|
|
|
|
|
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
|
|
|
**********************************************************************/
|
|
|
|
|
|
|
|
|
|
#include "huff_codes.h"
|
|
|
|
|
#include "huffman.h"
|
2016-10-03 23:50:52 +02:00
|
|
|
#include "flatten_ll.h"
|
2016-06-02 22:52:23 +02:00
|
|
|
|
|
|
|
|
/* The order code length codes are written in the dynamic code header. This is
|
|
|
|
|
* defined in RFC 1951 page 13 */
|
2024-04-19 18:09:21 +02:00
|
|
|
static const uint8_t code_length_code_order[] = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5,
|
|
|
|
|
11, 4, 12, 3, 13, 2, 14, 1, 15 };
|
2017-03-16 01:27:02 +01:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
static const uint32_t len_code_extra_bits[] = { 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x1, 0x1,
|
|
|
|
|
0x1, 0x1, 0x2, 0x2, 0x2, 0x2, 0x3, 0x3, 0x3, 0x3,
|
|
|
|
|
0x4, 0x4, 0x4, 0x4, 0x5, 0x5, 0x5, 0x5, 0x0 };
|
|
|
|
|
|
|
|
|
|
static const uint32_t dist_code_extra_bits[] = { 0x0, 0x0, 0x0, 0x0, 0x1, 0x1, 0x2, 0x2, 0x3, 0x3,
|
|
|
|
|
0x4, 0x4, 0x5, 0x5, 0x6, 0x6, 0x7, 0x7, 0x8, 0x8,
|
|
|
|
|
0x9, 0x9, 0xa, 0xa, 0xb, 0xb, 0xc, 0xc, 0xd, 0xd };
|
2017-03-16 01:27:02 +01:00
|
|
|
|
2018-03-12 16:28:10 +01:00
|
|
|
static struct hufftables_icf static_hufftables = {
|
2024-04-19 18:09:21 +02:00
|
|
|
.lit_len_table = { { { { .code_and_extra = 0x00c, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x08c, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x04c, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0cc, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x02c, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0ac, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x06c, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0ec, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x01c, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x09c, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x05c, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0dc, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x03c, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0bc, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x07c, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0fc, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x002, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x082, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x042, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0c2, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x022, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0a2, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x062, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0e2, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x012, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x092, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x052, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0d2, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x032, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0b2, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x072, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0f2, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x00a, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x08a, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x04a, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0ca, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x02a, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0aa, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x06a, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0ea, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x01a, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x09a, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x05a, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0da, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x03a, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0ba, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x07a, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0fa, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x006, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x086, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x046, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0c6, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x026, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0a6, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x066, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0e6, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x016, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x096, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x056, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0d6, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x036, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0b6, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x076, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0f6, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x00e, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x08e, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x04e, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0ce, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x02e, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0ae, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x06e, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0ee, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x01e, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x09e, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x05e, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0de, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x03e, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0be, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x07e, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0fe, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x001, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x081, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x041, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0c1, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x021, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0a1, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x061, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0e1, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x011, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x091, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x051, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0d1, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x031, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0b1, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x071, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0f1, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x009, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x089, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x049, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0c9, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x029, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0a9, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x069, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0e9, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x019, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x099, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x059, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0d9, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x039, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0b9, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x079, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0f9, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x005, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x085, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x045, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0c5, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x025, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0a5, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x065, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0e5, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x015, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x095, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x055, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0d5, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x035, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0b5, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x075, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0f5, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x00d, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x08d, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x04d, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0cd, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x02d, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0ad, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x06d, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0ed, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x01d, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x09d, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x05d, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0dd, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x03d, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0bd, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x07d, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0fd, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x013, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x113, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x093, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x193, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x053, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x153, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0d3, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1d3, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x033, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x133, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0b3, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1b3, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x073, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x173, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0f3, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1f3, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x00b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x10b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x08b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x18b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x04b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x14b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0cb, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1cb, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x02b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x12b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0ab, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1ab, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x06b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x16b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0eb, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1eb, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x01b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x11b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x09b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x19b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x05b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x15b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0db, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1db, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x03b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x13b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0bb, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1bb, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x07b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x17b, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0fb, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1fb, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x007, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x107, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x087, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x187, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x047, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x147, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0c7, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1c7, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x027, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x127, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0a7, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1a7, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x067, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x167, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0e7, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1e7, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x017, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x117, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x097, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x197, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x057, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x157, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0d7, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1d7, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x037, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x137, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0b7, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1b7, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x077, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x177, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0f7, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1f7, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x00f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x10f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x08f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x18f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x04f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x14f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0cf, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1cf, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x02f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x12f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0af, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1af, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x06f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x16f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0ef, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1ef, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x01f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x11f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x09f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x19f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x05f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x15f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0df, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1df, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x03f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x13f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0bf, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1bf, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x07f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x17f, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0ff, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x1ff, .length2 = 0x9 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x040, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x020, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x060, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x010, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x050, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x030, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x070, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x008, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x048, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x028, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x068, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x018, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x058, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x038, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x078, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x004, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x044, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x024, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x064, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x014, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x054, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x034, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x074, .length2 = 0x7 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x003, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x083, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x043, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0c3, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x023, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0a3, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x063, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x0e3, .length2 = 0x8 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } } },
|
|
|
|
|
.dist_table = { { { { .code_and_extra = 0x000, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x010, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x008, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x018, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x10004, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x10014, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x2000c, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x2001c, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x30002, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x30012, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x4000a, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x4001a, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x50006, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x50016, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x6000e, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x6001e, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x70001, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x70011, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x80009, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x80019, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x90005, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x90015, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0xa000d, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0xa001d, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0xb0003, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0xb0013, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0xc000b, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0xc001b, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0xd0007, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0xd0017, .length2 = 0x5 } } },
|
|
|
|
|
{ { { .code_and_extra = 0x000, .length2 = 0x0 } } } }
|
2017-03-16 01:27:02 +01:00
|
|
|
};
|
|
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
extern uint32_t
|
|
|
|
|
build_huff_tree(struct heap_tree *heap, uint64_t heap_size, uint64_t node_ptr);
|
|
|
|
|
extern void
|
|
|
|
|
build_heap(uint64_t *heap, uint64_t heap_size);
|
2016-10-03 23:50:52 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
static uint32_t
|
|
|
|
|
convert_dist_to_dist_sym(uint32_t dist);
|
|
|
|
|
static uint32_t
|
|
|
|
|
convert_length_to_len_sym(uint32_t length);
|
2018-03-12 19:19:25 +01:00
|
|
|
|
2016-10-03 23:50:52 +02:00
|
|
|
static const uint8_t bitrev8[0x100] = {
|
2024-04-19 18:09:21 +02:00
|
|
|
0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70,
|
|
|
|
|
0xF0, 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8,
|
|
|
|
|
0x78, 0xF8, 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34,
|
|
|
|
|
0xB4, 0x74, 0xF4, 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC,
|
|
|
|
|
0x3C, 0xBC, 0x7C, 0xFC, 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52,
|
|
|
|
|
0xD2, 0x32, 0xB2, 0x72, 0xF2, 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A,
|
|
|
|
|
0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA, 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16,
|
|
|
|
|
0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE,
|
|
|
|
|
0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE, 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61,
|
|
|
|
|
0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1, 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9,
|
|
|
|
|
0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, 0x05, 0x85, 0x45, 0xC5, 0x25,
|
|
|
|
|
0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, 0x0D, 0x8D, 0x4D, 0xCD,
|
|
|
|
|
0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD, 0x03, 0x83, 0x43,
|
|
|
|
|
0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, 0x0B, 0x8B,
|
|
|
|
|
0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB, 0x07,
|
|
|
|
|
0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
|
|
|
|
|
0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F,
|
|
|
|
|
0xFF
|
2016-10-03 23:50:52 +02:00
|
|
|
};
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2016-10-03 23:50:52 +02:00
|
|
|
// bit reverse low order LENGTH bits in code, and return result in low order bits
|
2024-04-19 18:09:21 +02:00
|
|
|
static inline uint16_t
|
|
|
|
|
bit_reverse(uint16_t code, uint32_t length)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
code = (bitrev8[code & 0x00FF] << 8) | (bitrev8[code >> 8]);
|
|
|
|
|
return (code >> (16 - length));
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
void
|
|
|
|
|
isal_update_histogram_base(uint8_t *start_stream, int length, struct isal_huff_histogram *histogram)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
uint32_t literal = 0, hash;
|
|
|
|
|
uint16_t seen, *last_seen = histogram->hash_table;
|
|
|
|
|
uint8_t *current, *end_stream, *next_hash, *end;
|
|
|
|
|
uint32_t match_length;
|
|
|
|
|
uint32_t dist;
|
|
|
|
|
uint64_t *lit_len_histogram = histogram->lit_len_histogram;
|
|
|
|
|
uint64_t *dist_histogram = histogram->dist_histogram;
|
|
|
|
|
|
|
|
|
|
if (length <= 0)
|
|
|
|
|
return;
|
|
|
|
|
|
|
|
|
|
end_stream = start_stream + length;
|
|
|
|
|
memset(last_seen, 0, sizeof(histogram->hash_table)); /* Initialize last_seen to be 0. */
|
|
|
|
|
for (current = start_stream; current < end_stream - 3; current++) {
|
|
|
|
|
literal = load_le_u32(current);
|
|
|
|
|
hash = compute_hash(literal) & LVL0_HASH_MASK;
|
|
|
|
|
seen = last_seen[hash];
|
|
|
|
|
last_seen[hash] = (current - start_stream) & 0xFFFF;
|
|
|
|
|
dist = (current - start_stream - seen) & 0xFFFF;
|
|
|
|
|
if (dist - 1 < D - 1) {
|
|
|
|
|
assert(start_stream <= current - dist);
|
|
|
|
|
match_length = compare258(current - dist, current, end_stream - current);
|
|
|
|
|
if (match_length >= SHORTEST_MATCH) {
|
|
|
|
|
next_hash = current;
|
2016-08-05 20:11:25 +02:00
|
|
|
#ifdef ISAL_LIMIT_HASH_UPDATE
|
2024-04-19 18:09:21 +02:00
|
|
|
end = next_hash + 3;
|
2016-06-02 22:52:23 +02:00
|
|
|
#else
|
2024-04-19 18:09:21 +02:00
|
|
|
end = next_hash + match_length;
|
2016-06-02 22:52:23 +02:00
|
|
|
#endif
|
2024-04-19 18:09:21 +02:00
|
|
|
if (end > end_stream - 3)
|
|
|
|
|
end = end_stream - 3;
|
|
|
|
|
next_hash++;
|
|
|
|
|
for (; next_hash < end; next_hash++) {
|
|
|
|
|
literal = load_le_u32(next_hash);
|
|
|
|
|
hash = compute_hash(literal) & LVL0_HASH_MASK;
|
|
|
|
|
last_seen[hash] = (next_hash - start_stream) & 0xFFFF;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
dist_histogram[convert_dist_to_dist_sym(dist)] += 1;
|
|
|
|
|
lit_len_histogram[convert_length_to_len_sym(match_length)] += 1;
|
|
|
|
|
current += match_length - 1;
|
|
|
|
|
continue;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
lit_len_histogram[literal & 0xFF] += 1;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
for (; current < end_stream; current++)
|
|
|
|
|
lit_len_histogram[*current] += 1;
|
|
|
|
|
|
|
|
|
|
lit_len_histogram[256] += 1;
|
|
|
|
|
return;
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2018-03-12 19:19:25 +01:00
|
|
|
/**
|
|
|
|
|
* @brief Returns the deflate symbol value for a look back distance.
|
|
|
|
|
*/
|
2024-04-19 18:09:21 +02:00
|
|
|
static uint32_t
|
|
|
|
|
convert_dist_to_dist_sym(uint32_t dist)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
assert(dist <= 32768 && dist > 0);
|
|
|
|
|
if (dist <= 32768) {
|
|
|
|
|
uint32_t msb = dist > 4 ? bsr(dist - 1) - 2 : 0;
|
|
|
|
|
return (msb * 2) + ((dist - 1) >> msb);
|
|
|
|
|
} else {
|
|
|
|
|
return ~0;
|
|
|
|
|
}
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2018-03-12 19:19:25 +01:00
|
|
|
/**
|
|
|
|
|
* @brief Returns the deflate symbol value for a repeat length.
|
|
|
|
|
*/
|
2024-04-19 18:09:21 +02:00
|
|
|
static uint32_t
|
|
|
|
|
convert_length_to_len_sym(uint32_t length)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
assert(length > 2 && length < 259);
|
|
|
|
|
|
|
|
|
|
/* Based on tables on page 11 in RFC 1951 */
|
|
|
|
|
if (length < 11)
|
|
|
|
|
return 257 + length - 3;
|
|
|
|
|
else if (length < 19)
|
|
|
|
|
return 261 + (length - 3) / 2;
|
|
|
|
|
else if (length < 35)
|
|
|
|
|
return 265 + (length - 3) / 4;
|
|
|
|
|
else if (length < 67)
|
|
|
|
|
return 269 + (length - 3) / 8;
|
|
|
|
|
else if (length < 131)
|
|
|
|
|
return 273 + (length - 3) / 16;
|
|
|
|
|
else if (length < 258)
|
|
|
|
|
return 277 + (length - 3) / 32;
|
|
|
|
|
else
|
|
|
|
|
return 285;
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2016-10-03 23:50:52 +02:00
|
|
|
// Upon return, codes[] contains the code lengths,
|
|
|
|
|
// and bl_count is the count of the lengths
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2016-10-03 23:50:52 +02:00
|
|
|
/* Init heap with the histogram, and return the histogram size */
|
2024-04-19 18:09:21 +02:00
|
|
|
static inline uint32_t
|
|
|
|
|
init_heap32(struct heap_tree *heap_space, uint32_t *histogram, uint32_t hist_size)
|
2016-10-03 23:50:52 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
uint32_t heap_size, i;
|
|
|
|
|
|
|
|
|
|
memset(heap_space, 0, sizeof(struct heap_tree));
|
|
|
|
|
|
|
|
|
|
heap_size = 0;
|
|
|
|
|
for (i = 0; i < hist_size; i++) {
|
|
|
|
|
if (histogram[i] != 0)
|
|
|
|
|
heap_space->heap[++heap_size] =
|
|
|
|
|
(((uint64_t) histogram[i]) << FREQ_SHIFT) | i;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// make sure heap has at least two elements in it
|
|
|
|
|
if (heap_size < 2) {
|
|
|
|
|
if (heap_size == 0) {
|
|
|
|
|
heap_space->heap[1] = 1ULL << FREQ_SHIFT;
|
|
|
|
|
heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1;
|
|
|
|
|
heap_size = 2;
|
|
|
|
|
} else {
|
|
|
|
|
// heap size == 1
|
|
|
|
|
if (histogram[0] == 0)
|
|
|
|
|
heap_space->heap[2] = 1ULL << FREQ_SHIFT;
|
|
|
|
|
else
|
|
|
|
|
heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1;
|
|
|
|
|
heap_size = 2;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
build_heap(heap_space->heap, heap_size);
|
|
|
|
|
|
|
|
|
|
return heap_size;
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
static inline uint32_t
|
|
|
|
|
init_heap64(struct heap_tree *heap_space, uint64_t *histogram, uint64_t hist_size)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
uint32_t heap_size, i;
|
|
|
|
|
|
|
|
|
|
memset(heap_space, 0, sizeof(struct heap_tree));
|
|
|
|
|
|
|
|
|
|
heap_size = 0;
|
|
|
|
|
for (i = 0; i < hist_size; i++) {
|
|
|
|
|
if (histogram[i] != 0)
|
|
|
|
|
heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT) | i;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// make sure heap has at least two elements in it
|
|
|
|
|
if (heap_size < 2) {
|
|
|
|
|
if (heap_size == 0) {
|
|
|
|
|
heap_space->heap[1] = 1ULL << FREQ_SHIFT;
|
|
|
|
|
heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1;
|
|
|
|
|
heap_size = 2;
|
|
|
|
|
} else {
|
|
|
|
|
// heap size == 1
|
|
|
|
|
if (histogram[0] == 0)
|
|
|
|
|
heap_space->heap[2] = 1ULL << FREQ_SHIFT;
|
|
|
|
|
else
|
|
|
|
|
heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1;
|
|
|
|
|
heap_size = 2;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
build_heap(heap_space->heap, heap_size);
|
|
|
|
|
|
|
|
|
|
return heap_size;
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
static inline uint32_t
|
|
|
|
|
init_heap64_semi_complete(struct heap_tree *heap_space, uint64_t *histogram, uint64_t hist_size,
|
|
|
|
|
uint64_t complete_start)
|
2017-09-21 23:29:52 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
uint32_t heap_size, i;
|
|
|
|
|
|
|
|
|
|
memset(heap_space, 0, sizeof(struct heap_tree));
|
|
|
|
|
|
|
|
|
|
heap_size = 0;
|
|
|
|
|
for (i = 0; i < complete_start; i++) {
|
|
|
|
|
if (histogram[i] != 0)
|
|
|
|
|
heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT) | i;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
for (; i < hist_size; i++)
|
|
|
|
|
heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT) | i;
|
|
|
|
|
|
|
|
|
|
// make sure heap has at least two elements in it
|
|
|
|
|
if (heap_size < 2) {
|
|
|
|
|
if (heap_size == 0) {
|
|
|
|
|
heap_space->heap[1] = 1ULL << FREQ_SHIFT;
|
|
|
|
|
heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1;
|
|
|
|
|
heap_size = 2;
|
|
|
|
|
} else {
|
|
|
|
|
// heap size == 1
|
|
|
|
|
if (histogram[0] == 0)
|
|
|
|
|
heap_space->heap[2] = 1ULL << FREQ_SHIFT;
|
|
|
|
|
else
|
|
|
|
|
heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1;
|
|
|
|
|
heap_size = 2;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
build_heap(heap_space->heap, heap_size);
|
|
|
|
|
|
|
|
|
|
return heap_size;
|
2017-09-21 23:29:52 +02:00
|
|
|
}
|
|
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
static inline uint32_t
|
|
|
|
|
init_heap64_complete(struct heap_tree *heap_space, uint64_t *histogram, uint64_t hist_size)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
uint32_t heap_size, i;
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
memset(heap_space, 0, sizeof(struct heap_tree));
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
heap_size = 0;
|
|
|
|
|
for (i = 0; i < hist_size; i++)
|
|
|
|
|
heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT) | i;
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
build_heap(heap_space->heap, heap_size);
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
return heap_size;
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
static inline uint32_t
|
|
|
|
|
fix_code_lens(struct heap_tree *heap_space, uint32_t root_node, uint32_t *bl_count,
|
|
|
|
|
uint32_t max_code_len)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
struct tree_node *tree = heap_space->tree;
|
|
|
|
|
uint64_t *code_len_count = heap_space->code_len_count;
|
|
|
|
|
uint32_t i, j, k, child, depth, code_len;
|
|
|
|
|
|
|
|
|
|
// compute code lengths and code length counts
|
|
|
|
|
code_len = 0;
|
|
|
|
|
j = root_node;
|
|
|
|
|
for (i = root_node; i <= HEAP_TREE_NODE_START; i++) {
|
|
|
|
|
child = tree[i].child;
|
|
|
|
|
if (child > MAX_HISTHEAP_SIZE) {
|
|
|
|
|
depth = 1 + tree[i].depth;
|
|
|
|
|
|
|
|
|
|
tree[child].depth = depth;
|
|
|
|
|
tree[child - 1].depth = depth;
|
|
|
|
|
} else {
|
|
|
|
|
tree[j++] = tree[i];
|
|
|
|
|
depth = tree[i].depth;
|
|
|
|
|
while (code_len < depth) {
|
|
|
|
|
code_len++;
|
|
|
|
|
code_len_count[code_len] = 0;
|
|
|
|
|
}
|
|
|
|
|
code_len_count[depth]++;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
if (code_len > max_code_len) {
|
|
|
|
|
while (code_len > max_code_len) {
|
|
|
|
|
assert(code_len_count[code_len] > 1);
|
|
|
|
|
for (i = max_code_len - 1; i != 0; i--)
|
|
|
|
|
if (code_len_count[i] != 0)
|
|
|
|
|
break;
|
|
|
|
|
assert(i != 0);
|
|
|
|
|
code_len_count[i]--;
|
|
|
|
|
code_len_count[i + 1] += 2;
|
|
|
|
|
code_len_count[code_len - 1]++;
|
|
|
|
|
code_len_count[code_len] -= 2;
|
|
|
|
|
if (code_len_count[code_len] == 0)
|
|
|
|
|
code_len--;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
bl_count[0] = 0;
|
|
|
|
|
for (i = 1; i <= code_len; i++)
|
|
|
|
|
bl_count[i] = code_len_count[i];
|
|
|
|
|
for (; i <= max_code_len; i++)
|
|
|
|
|
bl_count[i] = 0;
|
|
|
|
|
|
|
|
|
|
for (k = 1; code_len_count[k] == 0; k++)
|
|
|
|
|
;
|
|
|
|
|
for (i = root_node; i < j; i++) {
|
|
|
|
|
tree[i].depth = k;
|
|
|
|
|
code_len_count[k]--;
|
|
|
|
|
for (; code_len_count[k] == 0; k++)
|
|
|
|
|
;
|
|
|
|
|
}
|
|
|
|
|
} else {
|
|
|
|
|
bl_count[0] = 0;
|
|
|
|
|
for (i = 1; i <= code_len; i++)
|
|
|
|
|
bl_count[i] = code_len_count[i];
|
|
|
|
|
for (; i <= max_code_len; i++)
|
|
|
|
|
bl_count[i] = 0;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
return j;
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2016-10-03 23:50:52 +02:00
|
|
|
static inline void
|
2024-04-19 18:09:21 +02:00
|
|
|
gen_huff_code_lens(struct heap_tree *heap_space, uint32_t heap_size, uint32_t *bl_count,
|
|
|
|
|
struct huff_code *codes, uint32_t codes_count, uint32_t max_code_len)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
struct tree_node *tree = heap_space->tree;
|
|
|
|
|
uint32_t root_node = HEAP_TREE_NODE_START, node_ptr;
|
|
|
|
|
uint32_t end_node;
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
root_node = build_huff_tree(heap_space, heap_size, root_node);
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
end_node = fix_code_lens(heap_space, root_node, bl_count, max_code_len);
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
memset(codes, 0, codes_count * sizeof(*codes));
|
|
|
|
|
for (node_ptr = root_node; node_ptr < end_node; node_ptr++)
|
|
|
|
|
codes[tree[node_ptr].child].length = tree[node_ptr].depth;
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2018-03-12 19:19:25 +01:00
|
|
|
/**
|
|
|
|
|
* @brief Determines the code each element of a deflate compliant huffman tree and stores
|
|
|
|
|
* it in a lookup table
|
|
|
|
|
* @requires table has been initialized to already contain the code length for each element.
|
|
|
|
|
* @param table: A lookup table used to store the codes.
|
|
|
|
|
* @param table_length: The length of table.
|
2024-01-23 12:05:40 +01:00
|
|
|
* @param count: a histogram representing the number of occurrences of codes of a given length
|
2018-03-12 19:19:25 +01:00
|
|
|
*/
|
2024-04-19 18:09:21 +02:00
|
|
|
static inline uint32_t
|
|
|
|
|
set_huff_codes(struct huff_code *huff_code_table, int table_length, uint32_t *count)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
/* Uses the algorithm mentioned in the deflate standard, Rfc 1951. */
|
|
|
|
|
int i;
|
|
|
|
|
uint16_t code = 0;
|
|
|
|
|
uint16_t next_code[MAX_HUFF_TREE_DEPTH + 1];
|
|
|
|
|
uint32_t max_code = 0;
|
|
|
|
|
|
|
|
|
|
next_code[0] = code;
|
|
|
|
|
|
|
|
|
|
for (i = 1; i < MAX_HUFF_TREE_DEPTH + 1; i++)
|
|
|
|
|
next_code[i] = (next_code[i - 1] + count[i - 1]) << 1;
|
|
|
|
|
|
|
|
|
|
for (i = 0; i < table_length; i++) {
|
|
|
|
|
if (huff_code_table[i].length != 0) {
|
|
|
|
|
huff_code_table[i].code = bit_reverse(next_code[huff_code_table[i].length],
|
|
|
|
|
huff_code_table[i].length);
|
|
|
|
|
next_code[huff_code_table[i].length] += 1;
|
|
|
|
|
max_code = i;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
return max_code;
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2016-10-03 23:50:52 +02:00
|
|
|
// on input, codes contain the code lengths
|
|
|
|
|
// on output, code contains:
|
|
|
|
|
// 23:16 code length
|
|
|
|
|
// 15:0 code value in low order bits
|
|
|
|
|
// returns max code value
|
2024-04-19 18:09:21 +02:00
|
|
|
static inline uint32_t
|
|
|
|
|
set_dist_huff_codes(struct huff_code *codes, uint32_t *bl_count)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
uint32_t code, code_len, bits, i;
|
|
|
|
|
uint32_t next_code[MAX_DEFLATE_CODE_LEN + 1];
|
|
|
|
|
uint32_t max_code = 0;
|
|
|
|
|
const uint32_t num_codes = DIST_LEN;
|
|
|
|
|
|
|
|
|
|
code = bl_count[0] = 0;
|
|
|
|
|
for (bits = 1; bits <= MAX_HUFF_TREE_DEPTH; bits++) {
|
|
|
|
|
code = (code + bl_count[bits - 1]) << 1;
|
|
|
|
|
next_code[bits] = code;
|
|
|
|
|
}
|
|
|
|
|
for (i = 0; i < num_codes; i++) {
|
|
|
|
|
code_len = codes[i].length;
|
|
|
|
|
if (code_len != 0) {
|
|
|
|
|
codes[i].code = bit_reverse(next_code[code_len], code_len);
|
|
|
|
|
codes[i].extra_bit_count = dist_code_extra_bits[i];
|
|
|
|
|
next_code[code_len] += 1;
|
|
|
|
|
max_code = i;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
return max_code;
|
2016-10-03 23:50:52 +02:00
|
|
|
}
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2018-03-12 19:19:25 +01:00
|
|
|
/**
|
|
|
|
|
* @brief Creates the header for run length encoded huffman trees.
|
|
|
|
|
* @param header: the output header.
|
|
|
|
|
* @param lookup_table: a huffman lookup table.
|
|
|
|
|
* @param huffman_rep: a run length encoded huffman tree.
|
|
|
|
|
* @extra_bits: extra bits associated with the corresponding spot in huffman_rep
|
|
|
|
|
* @param huffman_rep_length: the length of huffman_rep.
|
|
|
|
|
* @param end_of_block: Value determining whether end of block header is produced or not;
|
|
|
|
|
* 0 corresponds to not end of block and all other inputs correspond to end of block.
|
|
|
|
|
* @param hclen: Length of huffman code for huffman codes minus 4.
|
|
|
|
|
* @param hlit: Length of literal/length table minus 257.
|
2024-01-23 12:05:40 +01:00
|
|
|
* @param hdist: Length of distance table minus 1.
|
2018-03-12 19:19:25 +01:00
|
|
|
*/
|
2024-04-19 18:09:21 +02:00
|
|
|
static int
|
|
|
|
|
create_huffman_header(struct BitBuf2 *header_bitbuf, struct huff_code *lookup_table,
|
|
|
|
|
struct rl_code *huffman_rep, uint16_t huffman_rep_length,
|
|
|
|
|
uint32_t end_of_block, uint32_t hclen, uint32_t hlit, uint32_t hdist)
|
2016-10-03 23:50:52 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
/* hlit, hdist, hclen are as defined in the deflate standard, head is the
|
|
|
|
|
* first three deflate header bits.*/
|
|
|
|
|
int i;
|
|
|
|
|
uint64_t bit_count;
|
|
|
|
|
uint64_t data;
|
|
|
|
|
struct huff_code huffman_value;
|
|
|
|
|
const uint32_t extra_bits[3] = { 2, 3, 7 };
|
|
|
|
|
|
|
|
|
|
bit_count = buffer_bits_used(header_bitbuf);
|
|
|
|
|
|
|
|
|
|
data = (end_of_block ? 5 : 4) | (hlit << 3) | (hdist << 8) | (hclen << 13);
|
|
|
|
|
data |= ((lookup_table[code_length_code_order[0]].length) << DYN_HDR_START_LEN);
|
|
|
|
|
write_bits(header_bitbuf, data, DYN_HDR_START_LEN + 3);
|
|
|
|
|
data = 0;
|
|
|
|
|
for (i = hclen + 3; i >= 1; i--)
|
|
|
|
|
data = (data << 3) | lookup_table[code_length_code_order[i]].length;
|
|
|
|
|
|
|
|
|
|
write_bits(header_bitbuf, data, (hclen + 3) * 3);
|
|
|
|
|
|
|
|
|
|
for (i = 0; i < huffman_rep_length; i++) {
|
|
|
|
|
huffman_value = lookup_table[huffman_rep[i].code];
|
|
|
|
|
|
|
|
|
|
write_bits(header_bitbuf, (uint64_t) huffman_value.code,
|
|
|
|
|
(uint32_t) huffman_value.length);
|
|
|
|
|
|
|
|
|
|
if (huffman_rep[i].code > 15) {
|
|
|
|
|
write_bits(header_bitbuf, (uint64_t) huffman_rep[i].extra_bits,
|
|
|
|
|
(uint32_t) extra_bits[huffman_rep[i].code - 16]);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
bit_count = buffer_bits_used(header_bitbuf) - bit_count;
|
|
|
|
|
|
|
|
|
|
return bit_count;
|
2016-10-03 23:50:52 +02:00
|
|
|
}
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2018-03-12 19:19:25 +01:00
|
|
|
/**
|
|
|
|
|
* @brief Creates the dynamic huffman deflate header.
|
|
|
|
|
* @returns Returns the length of header in bits.
|
|
|
|
|
* @requires This function requires header is large enough to store the whole header.
|
|
|
|
|
* @param header: The output header.
|
|
|
|
|
* @param lit_huff_table: A literal/length code huffman lookup table.\
|
|
|
|
|
* @param dist_huff_table: A distance huffman code lookup table.
|
|
|
|
|
* @param end_of_block: Value determining whether end of block header is produced or not;
|
|
|
|
|
* 0 corresponds to not end of block and all other inputs correspond to end of block.
|
|
|
|
|
*/
|
2024-04-19 18:09:21 +02:00
|
|
|
static inline int
|
|
|
|
|
create_header(struct BitBuf2 *header_bitbuf, struct rl_code *huffman_rep, uint32_t length,
|
|
|
|
|
uint64_t *histogram, uint32_t hlit, uint32_t hdist, uint32_t end_of_block)
|
2016-10-03 23:50:52 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
int i;
|
2016-10-03 23:50:52 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
uint32_t heap_size;
|
|
|
|
|
struct heap_tree heap_space;
|
|
|
|
|
uint32_t code_len_count[MAX_HUFF_TREE_DEPTH + 1];
|
|
|
|
|
struct huff_code lookup_table[HUFF_LEN];
|
2016-10-03 23:50:52 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
/* hlit, hdist, and hclen are defined in RFC 1951 page 13 */
|
|
|
|
|
uint32_t hclen;
|
|
|
|
|
uint64_t bit_count;
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
/* Create a huffman tree to encode run length encoded representation. */
|
|
|
|
|
heap_size = init_heap64(&heap_space, histogram, HUFF_LEN);
|
|
|
|
|
gen_huff_code_lens(&heap_space, heap_size, code_len_count,
|
|
|
|
|
(struct huff_code *) lookup_table, HUFF_LEN, 7);
|
|
|
|
|
set_huff_codes(lookup_table, HUFF_LEN, code_len_count);
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
/* Calculate hclen */
|
|
|
|
|
for (i = CODE_LEN_CODES - 1; i > 3; i--) /* i must be at least 4 */
|
|
|
|
|
if (lookup_table[code_length_code_order[i]].length != 0)
|
|
|
|
|
break;
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
hclen = i - 3;
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
/* Generate actual header. */
|
|
|
|
|
bit_count = create_huffman_header(header_bitbuf, lookup_table, huffman_rep, length,
|
|
|
|
|
end_of_block, hclen, hlit, hdist);
|
2016-06-02 22:52:23 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
return bit_count;
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
static inline struct rl_code *
|
|
|
|
|
write_rl(struct rl_code *pout, uint16_t last_len, uint32_t run_len, uint64_t *counts)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
if (last_len == 0) {
|
|
|
|
|
while (run_len > 138) {
|
|
|
|
|
pout->code = 18;
|
|
|
|
|
pout->extra_bits = 138 - 11;
|
|
|
|
|
pout++;
|
|
|
|
|
run_len -= 138;
|
|
|
|
|
counts[18]++;
|
|
|
|
|
}
|
|
|
|
|
// 1 <= run_len <= 138
|
|
|
|
|
if (run_len > 10) {
|
|
|
|
|
pout->code = 18;
|
|
|
|
|
pout->extra_bits = run_len - 11;
|
|
|
|
|
pout++;
|
|
|
|
|
counts[18]++;
|
|
|
|
|
} else if (run_len > 2) {
|
|
|
|
|
pout->code = 17;
|
|
|
|
|
pout->extra_bits = run_len - 3;
|
|
|
|
|
pout++;
|
|
|
|
|
counts[17]++;
|
|
|
|
|
} else if (run_len == 1) {
|
|
|
|
|
pout->code = 0;
|
|
|
|
|
pout->extra_bits = 0;
|
|
|
|
|
pout++;
|
|
|
|
|
counts[0]++;
|
|
|
|
|
} else {
|
|
|
|
|
assert(run_len == 2);
|
|
|
|
|
pout[0].code = 0;
|
|
|
|
|
pout[0].extra_bits = 0;
|
|
|
|
|
pout[1].code = 0;
|
|
|
|
|
pout[1].extra_bits = 0;
|
|
|
|
|
pout += 2;
|
|
|
|
|
counts[0] += 2;
|
|
|
|
|
}
|
|
|
|
|
} else {
|
|
|
|
|
// last_len != 0
|
|
|
|
|
pout->code = last_len;
|
|
|
|
|
pout->extra_bits = 0;
|
|
|
|
|
pout++;
|
|
|
|
|
counts[last_len]++;
|
|
|
|
|
run_len--;
|
|
|
|
|
if (run_len != 0) {
|
|
|
|
|
while (run_len > 6) {
|
|
|
|
|
pout->code = 16;
|
|
|
|
|
pout->extra_bits = 6 - 3;
|
|
|
|
|
pout++;
|
|
|
|
|
run_len -= 6;
|
|
|
|
|
counts[16]++;
|
|
|
|
|
}
|
|
|
|
|
// 1 <= run_len <= 6
|
|
|
|
|
switch (run_len) {
|
|
|
|
|
case 1:
|
|
|
|
|
pout->code = last_len;
|
|
|
|
|
pout->extra_bits = 0;
|
|
|
|
|
pout++;
|
|
|
|
|
counts[last_len]++;
|
|
|
|
|
break;
|
|
|
|
|
case 2:
|
|
|
|
|
pout[0].code = last_len;
|
|
|
|
|
pout[0].extra_bits = 0;
|
|
|
|
|
pout[1].code = last_len;
|
|
|
|
|
pout[1].extra_bits = 0;
|
|
|
|
|
pout += 2;
|
|
|
|
|
counts[last_len] += 2;
|
|
|
|
|
break;
|
|
|
|
|
default: // 3...6
|
|
|
|
|
pout->code = 16;
|
|
|
|
|
pout->extra_bits = run_len - 3;
|
|
|
|
|
pout++;
|
|
|
|
|
counts[16]++;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
return pout;
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2016-10-03 23:50:52 +02:00
|
|
|
// convert codes into run-length symbols, write symbols into OUT
|
|
|
|
|
// generate histogram into COUNTS (assumed to be initialized to 0)
|
|
|
|
|
// Format of OUT:
|
|
|
|
|
// 4:0 code (0...18)
|
|
|
|
|
// 15:8 Extra bits (0...127)
|
|
|
|
|
// returns number of symbols in out
|
2024-04-19 18:09:21 +02:00
|
|
|
static inline uint32_t
|
|
|
|
|
rl_encode(uint16_t *codes, uint32_t num_codes, uint64_t *counts, struct rl_code *out)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
uint32_t i, run_len;
|
|
|
|
|
uint16_t last_len, len;
|
|
|
|
|
struct rl_code *pout;
|
|
|
|
|
|
|
|
|
|
pout = out;
|
|
|
|
|
last_len = codes[0];
|
|
|
|
|
run_len = 1;
|
|
|
|
|
for (i = 1; i < num_codes; i++) {
|
|
|
|
|
len = codes[i];
|
|
|
|
|
if (len == last_len) {
|
|
|
|
|
run_len++;
|
|
|
|
|
continue;
|
|
|
|
|
}
|
|
|
|
|
pout = write_rl(pout, last_len, run_len, counts);
|
|
|
|
|
last_len = len;
|
|
|
|
|
run_len = 1;
|
|
|
|
|
}
|
|
|
|
|
pout = write_rl(pout, last_len, run_len, counts);
|
|
|
|
|
|
|
|
|
|
return (uint32_t) (pout - out);
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2018-03-12 19:19:25 +01:00
|
|
|
/**
|
|
|
|
|
* @brief Creates a two table representation of huffman codes.
|
|
|
|
|
* @param code_table: output table containing the code
|
|
|
|
|
* @param code_size_table: output table containing the code length
|
2024-01-23 12:05:40 +01:00
|
|
|
* @param length: the length of hufftable
|
2018-03-12 19:19:25 +01:00
|
|
|
* @param hufftable: a huffman lookup table
|
|
|
|
|
*/
|
2024-04-19 18:09:21 +02:00
|
|
|
static void
|
|
|
|
|
create_code_tables(uint16_t *code_table, uint8_t *code_length_table, uint32_t length,
|
|
|
|
|
struct huff_code *hufftable)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
int i;
|
|
|
|
|
for (i = 0; i < length; i++) {
|
|
|
|
|
code_table[i] = hufftable[i].code;
|
|
|
|
|
code_length_table[i] = hufftable[i].length;
|
|
|
|
|
}
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2018-03-12 19:19:25 +01:00
|
|
|
/**
|
|
|
|
|
* @brief Creates a packed representation of length huffman codes.
|
|
|
|
|
* @details In packed_table, bits 32:8 contain the extra bits appended to the huffman
|
|
|
|
|
* code and bits 8:0 contain the code length.
|
|
|
|
|
* @param packed_table: the output table
|
|
|
|
|
* @param length: the length of lit_len_hufftable
|
|
|
|
|
* @param lit_len_hufftable: a literal/length huffman lookup table
|
|
|
|
|
*/
|
2024-04-19 18:09:21 +02:00
|
|
|
static void
|
|
|
|
|
create_packed_len_table(uint32_t *packed_table, struct huff_code *lit_len_hufftable)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
int i, count = 0;
|
|
|
|
|
uint16_t extra_bits;
|
|
|
|
|
uint16_t extra_bits_count = 0;
|
|
|
|
|
|
|
|
|
|
/* Gain extra bits is the next place where the number of extra bits in
|
|
|
|
|
* length codes increases. */
|
|
|
|
|
uint16_t gain_extra_bits = LEN_EXTRA_BITS_START;
|
|
|
|
|
|
|
|
|
|
for (i = 257; i < LIT_LEN - 1; i++) {
|
|
|
|
|
for (extra_bits = 0; extra_bits < (1 << extra_bits_count); extra_bits++) {
|
|
|
|
|
if (count > 254)
|
|
|
|
|
break;
|
|
|
|
|
packed_table[count++] =
|
|
|
|
|
(extra_bits << (lit_len_hufftable[i].length + LENGTH_BITS)) |
|
|
|
|
|
(lit_len_hufftable[i].code << LENGTH_BITS) |
|
|
|
|
|
(lit_len_hufftable[i].length + extra_bits_count);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
if (i == gain_extra_bits) {
|
|
|
|
|
gain_extra_bits += LEN_EXTRA_BITS_INTERVAL;
|
|
|
|
|
extra_bits_count += 1;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
packed_table[count] = (lit_len_hufftable[LIT_LEN - 1].code << LENGTH_BITS) |
|
|
|
|
|
(lit_len_hufftable[LIT_LEN - 1].length);
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2018-03-12 19:19:25 +01:00
|
|
|
/**
|
|
|
|
|
* @brief Creates a packed representation of distance huffman codes.
|
|
|
|
|
* @details In packed_table, bits 32:8 contain the extra bits appended to the huffman
|
|
|
|
|
* code and bits 8:0 contain the code length.
|
|
|
|
|
* @param packed_table: the output table
|
|
|
|
|
* @param length: the length of lit_len_hufftable
|
|
|
|
|
* @param dist_hufftable: a distance huffman lookup table
|
|
|
|
|
*/
|
2024-04-19 18:09:21 +02:00
|
|
|
static void
|
|
|
|
|
create_packed_dist_table(uint32_t *packed_table, uint32_t length, struct huff_code *dist_hufftable)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
int i, count = 0;
|
|
|
|
|
uint16_t extra_bits;
|
|
|
|
|
uint16_t extra_bits_count = 0;
|
|
|
|
|
|
|
|
|
|
/* Gain extra bits is the next place where the number of extra bits in
|
|
|
|
|
* distance codes increases. */
|
|
|
|
|
uint16_t gain_extra_bits = DIST_EXTRA_BITS_START;
|
|
|
|
|
|
|
|
|
|
for (i = 0; i < DIST_LEN; i++) {
|
|
|
|
|
for (extra_bits = 0; extra_bits < (1 << extra_bits_count); extra_bits++) {
|
|
|
|
|
if (count >= length)
|
|
|
|
|
return;
|
|
|
|
|
|
|
|
|
|
packed_table[count++] =
|
|
|
|
|
(extra_bits << (dist_hufftable[i].length + LENGTH_BITS)) |
|
|
|
|
|
(dist_hufftable[i].code << LENGTH_BITS) |
|
|
|
|
|
(dist_hufftable[i].length + extra_bits_count);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
if (i == gain_extra_bits) {
|
|
|
|
|
gain_extra_bits += DIST_EXTRA_BITS_INTERVAL;
|
|
|
|
|
extra_bits_count += 1;
|
|
|
|
|
}
|
|
|
|
|
}
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2018-03-12 19:19:25 +01:00
|
|
|
/**
|
|
|
|
|
* @brief Checks to see if the hufftable is usable by igzip
|
|
|
|
|
*
|
|
|
|
|
* @param lit_len_hufftable: literal/length huffman code
|
|
|
|
|
* @param dist_hufftable: distance huffman code
|
|
|
|
|
* @returns Returns 0 if the table is usable
|
|
|
|
|
*/
|
2024-04-19 18:09:21 +02:00
|
|
|
static int
|
|
|
|
|
are_hufftables_useable(struct huff_code *lit_len_hufftable, struct huff_code *dist_hufftable)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
int max_lit_code_len = 0, max_len_code_len = 0, max_dist_code_len = 0;
|
|
|
|
|
int dist_extra_bits = 0, len_extra_bits = 0;
|
|
|
|
|
int gain_dist_extra_bits = DIST_EXTRA_BITS_START;
|
|
|
|
|
int gain_len_extra_bits = LEN_EXTRA_BITS_START;
|
|
|
|
|
int max_code_len;
|
|
|
|
|
int i;
|
|
|
|
|
|
|
|
|
|
for (i = 0; i < LIT_LEN; i++)
|
|
|
|
|
if (lit_len_hufftable[i].length > max_lit_code_len)
|
|
|
|
|
max_lit_code_len = lit_len_hufftable[i].length;
|
|
|
|
|
|
|
|
|
|
for (i = 257; i < LIT_LEN - 1; i++) {
|
|
|
|
|
if (lit_len_hufftable[i].length + len_extra_bits > max_len_code_len)
|
|
|
|
|
max_len_code_len = lit_len_hufftable[i].length + len_extra_bits;
|
|
|
|
|
|
|
|
|
|
if (i == gain_len_extra_bits) {
|
|
|
|
|
gain_len_extra_bits += LEN_EXTRA_BITS_INTERVAL;
|
|
|
|
|
len_extra_bits += 1;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
for (i = 0; i < DIST_LEN; i++) {
|
|
|
|
|
if (dist_hufftable[i].length + dist_extra_bits > max_dist_code_len)
|
|
|
|
|
max_dist_code_len = dist_hufftable[i].length + dist_extra_bits;
|
|
|
|
|
|
|
|
|
|
if (i == gain_dist_extra_bits) {
|
|
|
|
|
gain_dist_extra_bits += DIST_EXTRA_BITS_INTERVAL;
|
|
|
|
|
dist_extra_bits += 1;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
max_code_len = max_lit_code_len + max_len_code_len + max_dist_code_len;
|
|
|
|
|
|
|
|
|
|
/* Some versions of igzip can write up to one literal, one length and one
|
|
|
|
|
* distance code at the same time. This checks to make sure that is
|
|
|
|
|
* always writeable in bitbuf*/
|
|
|
|
|
return (max_code_len > MAX_BITBUF_BIT_WRITE);
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
int
|
|
|
|
|
isal_create_hufftables(struct isal_hufftables *hufftables, struct isal_huff_histogram *histogram)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
struct huff_code lit_huff_table[LIT_LEN], dist_huff_table[DIST_LEN];
|
|
|
|
|
uint64_t bit_count;
|
|
|
|
|
int max_dist = convert_dist_to_dist_sym(IGZIP_HIST_SIZE);
|
|
|
|
|
struct heap_tree heap_space;
|
|
|
|
|
uint32_t heap_size;
|
|
|
|
|
uint32_t code_len_count[MAX_HUFF_TREE_DEPTH + 1];
|
|
|
|
|
struct BitBuf2 header_bitbuf;
|
|
|
|
|
uint32_t max_lit_len_sym;
|
|
|
|
|
uint32_t max_dist_sym;
|
|
|
|
|
uint32_t hlit, hdist, i;
|
|
|
|
|
uint16_t combined_table[LIT_LEN + DIST_LEN];
|
|
|
|
|
uint64_t count_histogram[HUFF_LEN];
|
|
|
|
|
struct rl_code rl_huff[LIT_LEN + DIST_LEN];
|
|
|
|
|
uint32_t rl_huff_len;
|
|
|
|
|
|
|
|
|
|
uint32_t *dist_table = hufftables->dist_table;
|
|
|
|
|
uint32_t *len_table = hufftables->len_table;
|
|
|
|
|
uint16_t *lit_table = hufftables->lit_table;
|
|
|
|
|
uint16_t *dcodes = hufftables->dcodes;
|
|
|
|
|
uint8_t *lit_table_sizes = hufftables->lit_table_sizes;
|
|
|
|
|
uint8_t *dcodes_sizes = hufftables->dcodes_sizes;
|
|
|
|
|
uint64_t *lit_len_histogram = histogram->lit_len_histogram;
|
|
|
|
|
uint64_t *dist_histogram = histogram->dist_histogram;
|
|
|
|
|
|
|
|
|
|
memset(hufftables, 0, sizeof(struct isal_hufftables));
|
|
|
|
|
|
|
|
|
|
heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN);
|
|
|
|
|
gen_huff_code_lens(&heap_space, heap_size, code_len_count,
|
|
|
|
|
(struct huff_code *) lit_huff_table, LIT_LEN, MAX_DEFLATE_CODE_LEN);
|
|
|
|
|
max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count);
|
|
|
|
|
|
|
|
|
|
heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN);
|
|
|
|
|
gen_huff_code_lens(&heap_space, heap_size, code_len_count,
|
|
|
|
|
(struct huff_code *) dist_huff_table, max_dist, MAX_DEFLATE_CODE_LEN);
|
|
|
|
|
max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count);
|
|
|
|
|
|
|
|
|
|
if (are_hufftables_useable(lit_huff_table, dist_huff_table)) {
|
|
|
|
|
heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN);
|
|
|
|
|
gen_huff_code_lens(&heap_space, heap_size, code_len_count,
|
|
|
|
|
(struct huff_code *) lit_huff_table, LIT_LEN,
|
|
|
|
|
MAX_SAFE_LIT_CODE_LEN);
|
|
|
|
|
max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count);
|
|
|
|
|
|
|
|
|
|
heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN);
|
|
|
|
|
gen_huff_code_lens(&heap_space, heap_size, code_len_count,
|
|
|
|
|
(struct huff_code *) dist_huff_table, max_dist,
|
|
|
|
|
MAX_SAFE_DIST_CODE_LEN);
|
|
|
|
|
max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
create_code_tables(dcodes, dcodes_sizes, DIST_LEN - DCODE_OFFSET,
|
|
|
|
|
dist_huff_table + DCODE_OFFSET);
|
|
|
|
|
|
|
|
|
|
create_code_tables(lit_table, lit_table_sizes, IGZIP_LIT_TABLE_SIZE, lit_huff_table);
|
|
|
|
|
|
|
|
|
|
create_packed_len_table(len_table, lit_huff_table);
|
|
|
|
|
create_packed_dist_table(dist_table, IGZIP_DIST_TABLE_SIZE, dist_huff_table);
|
|
|
|
|
|
|
|
|
|
set_buf(&header_bitbuf, hufftables->deflate_hdr, sizeof(hufftables->deflate_hdr));
|
|
|
|
|
init(&header_bitbuf);
|
|
|
|
|
|
|
|
|
|
hlit = max_lit_len_sym - 256;
|
|
|
|
|
hdist = max_dist_sym;
|
|
|
|
|
|
|
|
|
|
/* Run length encode the length and distance huffman codes */
|
|
|
|
|
memset(count_histogram, 0, sizeof(count_histogram));
|
|
|
|
|
for (i = 0; i < 257 + hlit; i++)
|
|
|
|
|
combined_table[i] = lit_huff_table[i].length;
|
|
|
|
|
for (i = 0; i < 1 + hdist; i++)
|
|
|
|
|
combined_table[i + hlit + 257] = dist_huff_table[i].length;
|
|
|
|
|
rl_huff_len = rl_encode(combined_table, hlit + 257 + hdist + 1, count_histogram, rl_huff);
|
|
|
|
|
|
|
|
|
|
/* Create header */
|
|
|
|
|
bit_count = create_header(&header_bitbuf, rl_huff, rl_huff_len, count_histogram, hlit,
|
|
|
|
|
hdist, LAST_BLOCK);
|
|
|
|
|
flush(&header_bitbuf);
|
|
|
|
|
|
|
|
|
|
hufftables->deflate_hdr_count = bit_count / 8;
|
|
|
|
|
hufftables->deflate_hdr_extra_bits = bit_count % 8;
|
|
|
|
|
|
|
|
|
|
return 0;
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
|
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
int
|
|
|
|
|
isal_create_hufftables_subset(struct isal_hufftables *hufftables,
|
|
|
|
|
struct isal_huff_histogram *histogram)
|
2016-06-02 22:52:23 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
struct huff_code lit_huff_table[LIT_LEN], dist_huff_table[DIST_LEN];
|
|
|
|
|
uint64_t bit_count;
|
|
|
|
|
int max_dist = convert_dist_to_dist_sym(IGZIP_HIST_SIZE);
|
|
|
|
|
struct heap_tree heap_space;
|
|
|
|
|
uint32_t heap_size;
|
|
|
|
|
uint32_t code_len_count[MAX_HUFF_TREE_DEPTH + 1];
|
|
|
|
|
struct BitBuf2 header_bitbuf;
|
|
|
|
|
uint32_t max_lit_len_sym;
|
|
|
|
|
uint32_t max_dist_sym;
|
|
|
|
|
uint32_t hlit, hdist, i;
|
|
|
|
|
uint16_t combined_table[LIT_LEN + DIST_LEN];
|
|
|
|
|
uint64_t count_histogram[HUFF_LEN];
|
|
|
|
|
struct rl_code rl_huff[LIT_LEN + DIST_LEN];
|
|
|
|
|
uint32_t rl_huff_len;
|
|
|
|
|
|
|
|
|
|
uint32_t *dist_table = hufftables->dist_table;
|
|
|
|
|
uint32_t *len_table = hufftables->len_table;
|
|
|
|
|
uint16_t *lit_table = hufftables->lit_table;
|
|
|
|
|
uint16_t *dcodes = hufftables->dcodes;
|
|
|
|
|
uint8_t *lit_table_sizes = hufftables->lit_table_sizes;
|
|
|
|
|
uint8_t *dcodes_sizes = hufftables->dcodes_sizes;
|
|
|
|
|
uint64_t *lit_len_histogram = histogram->lit_len_histogram;
|
|
|
|
|
uint64_t *dist_histogram = histogram->dist_histogram;
|
|
|
|
|
|
|
|
|
|
memset(hufftables, 0, sizeof(struct isal_hufftables));
|
|
|
|
|
|
|
|
|
|
heap_size = init_heap64_semi_complete(&heap_space, lit_len_histogram, LIT_LEN,
|
|
|
|
|
ISAL_DEF_LIT_SYMBOLS);
|
|
|
|
|
gen_huff_code_lens(&heap_space, heap_size, code_len_count,
|
|
|
|
|
(struct huff_code *) lit_huff_table, LIT_LEN, MAX_DEFLATE_CODE_LEN);
|
|
|
|
|
max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count);
|
|
|
|
|
|
|
|
|
|
heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN);
|
|
|
|
|
gen_huff_code_lens(&heap_space, heap_size, code_len_count,
|
|
|
|
|
(struct huff_code *) dist_huff_table, max_dist, MAX_DEFLATE_CODE_LEN);
|
|
|
|
|
max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count);
|
|
|
|
|
|
|
|
|
|
if (are_hufftables_useable(lit_huff_table, dist_huff_table)) {
|
|
|
|
|
heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN);
|
|
|
|
|
gen_huff_code_lens(&heap_space, heap_size, code_len_count,
|
|
|
|
|
(struct huff_code *) lit_huff_table, LIT_LEN,
|
|
|
|
|
MAX_SAFE_LIT_CODE_LEN);
|
|
|
|
|
max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count);
|
|
|
|
|
|
|
|
|
|
heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN);
|
|
|
|
|
gen_huff_code_lens(&heap_space, heap_size, code_len_count,
|
|
|
|
|
(struct huff_code *) dist_huff_table, max_dist,
|
|
|
|
|
MAX_SAFE_DIST_CODE_LEN);
|
|
|
|
|
max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
create_code_tables(dcodes, dcodes_sizes, DIST_LEN - DCODE_OFFSET,
|
|
|
|
|
dist_huff_table + DCODE_OFFSET);
|
|
|
|
|
|
|
|
|
|
create_code_tables(lit_table, lit_table_sizes, IGZIP_LIT_TABLE_SIZE, lit_huff_table);
|
|
|
|
|
|
|
|
|
|
create_packed_len_table(len_table, lit_huff_table);
|
|
|
|
|
create_packed_dist_table(dist_table, IGZIP_DIST_TABLE_SIZE, dist_huff_table);
|
|
|
|
|
|
|
|
|
|
set_buf(&header_bitbuf, hufftables->deflate_hdr, sizeof(hufftables->deflate_hdr));
|
|
|
|
|
init(&header_bitbuf);
|
|
|
|
|
|
|
|
|
|
hlit = max_lit_len_sym - 256;
|
|
|
|
|
hdist = max_dist_sym;
|
|
|
|
|
|
|
|
|
|
/* Run length encode the length and distance huffman codes */
|
|
|
|
|
memset(count_histogram, 0, sizeof(count_histogram));
|
|
|
|
|
for (i = 0; i < 257 + hlit; i++)
|
|
|
|
|
combined_table[i] = lit_huff_table[i].length;
|
|
|
|
|
for (i = 0; i < 1 + hdist; i++)
|
|
|
|
|
combined_table[i + hlit + 257] = dist_huff_table[i].length;
|
|
|
|
|
rl_huff_len = rl_encode(combined_table, hlit + 257 + hdist + 1, count_histogram, rl_huff);
|
|
|
|
|
|
|
|
|
|
/* Create header */
|
|
|
|
|
bit_count = create_header(&header_bitbuf, rl_huff, rl_huff_len, count_histogram, hlit,
|
|
|
|
|
hdist, LAST_BLOCK);
|
|
|
|
|
flush(&header_bitbuf);
|
|
|
|
|
|
|
|
|
|
hufftables->deflate_hdr_count = bit_count / 8;
|
|
|
|
|
hufftables->deflate_hdr_extra_bits = bit_count % 8;
|
|
|
|
|
|
|
|
|
|
return 0;
|
2016-06-02 22:52:23 +02:00
|
|
|
}
|
2016-10-03 23:50:52 +02:00
|
|
|
|
2024-04-19 18:09:21 +02:00
|
|
|
static void
|
|
|
|
|
expand_hufftables_icf(struct hufftables_icf *hufftables)
|
2016-10-03 23:50:52 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
uint32_t i, eb, j, k, len, code;
|
|
|
|
|
struct huff_code orig[21], *p_code;
|
|
|
|
|
struct huff_code *lit_len_codes = hufftables->lit_len_table;
|
|
|
|
|
struct huff_code *dist_codes = hufftables->dist_table;
|
|
|
|
|
|
|
|
|
|
for (i = 0; i < 21; i++)
|
|
|
|
|
orig[i] = lit_len_codes[i + 265];
|
|
|
|
|
|
|
|
|
|
p_code = &lit_len_codes[265];
|
|
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
for (eb = 1; eb < 6; eb++) {
|
|
|
|
|
for (k = 0; k < 4; k++) {
|
|
|
|
|
len = orig[i].length;
|
|
|
|
|
code = orig[i++].code;
|
|
|
|
|
for (j = 0; j < (1u << eb); j++) {
|
|
|
|
|
p_code->code_and_extra = code | (j << len);
|
|
|
|
|
p_code->length = len + eb;
|
|
|
|
|
p_code++;
|
|
|
|
|
}
|
|
|
|
|
} // end for k
|
|
|
|
|
} // end for eb
|
|
|
|
|
// fix up last record
|
|
|
|
|
p_code[-1] = orig[i];
|
|
|
|
|
|
|
|
|
|
dist_codes[DIST_LEN].code_and_extra = 0;
|
|
|
|
|
dist_codes[DIST_LEN].length = 0;
|
2016-10-03 23:50:52 +02:00
|
|
|
}
|
|
|
|
|
|
2017-03-21 01:33:25 +01:00
|
|
|
uint64_t
|
2016-10-03 23:50:52 +02:00
|
|
|
create_hufftables_icf(struct BitBuf2 *bb, struct hufftables_icf *hufftables,
|
2024-04-19 18:09:21 +02:00
|
|
|
struct isal_mod_hist *hist, uint32_t end_of_block)
|
2016-10-03 23:50:52 +02:00
|
|
|
{
|
2024-04-19 18:09:21 +02:00
|
|
|
uint32_t bl_count[MAX_DEFLATE_CODE_LEN + 1];
|
|
|
|
|
uint32_t max_ll_code, max_d_code;
|
|
|
|
|
struct heap_tree heap_space;
|
|
|
|
|
uint32_t heap_size;
|
|
|
|
|
struct rl_code cl_tokens[LIT_LEN + DIST_LEN];
|
|
|
|
|
uint32_t num_cl_tokens;
|
|
|
|
|
uint64_t cl_counts[CODE_LEN_CODES];
|
|
|
|
|
uint16_t combined_table[LIT_LEN + DIST_LEN];
|
|
|
|
|
int i;
|
|
|
|
|
uint64_t compressed_len = 0;
|
|
|
|
|
uint64_t static_compressed_len = 3; /* The static header size */
|
|
|
|
|
struct BitBuf2 bb_tmp;
|
|
|
|
|
|
|
|
|
|
struct huff_code *ll_codes = hufftables->lit_len_table;
|
|
|
|
|
struct huff_code *d_codes = hufftables->dist_table;
|
|
|
|
|
uint32_t *ll_hist = hist->ll_hist;
|
|
|
|
|
uint32_t *d_hist = hist->d_hist;
|
|
|
|
|
struct huff_code *static_ll_codes = static_hufftables.lit_len_table;
|
|
|
|
|
struct huff_code *static_d_codes = static_hufftables.dist_table;
|
|
|
|
|
|
|
|
|
|
memcpy(&bb_tmp, bb, sizeof(struct BitBuf2));
|
|
|
|
|
|
|
|
|
|
flatten_ll(hist->ll_hist);
|
|
|
|
|
|
|
|
|
|
// make sure EOB is present
|
|
|
|
|
if (ll_hist[256] == 0)
|
|
|
|
|
ll_hist[256] = 1;
|
|
|
|
|
|
|
|
|
|
heap_size = init_heap32(&heap_space, ll_hist, LIT_LEN);
|
|
|
|
|
gen_huff_code_lens(&heap_space, heap_size, bl_count, ll_codes, LIT_LEN,
|
|
|
|
|
MAX_DEFLATE_CODE_LEN);
|
|
|
|
|
max_ll_code = set_huff_codes(ll_codes, LIT_LEN, bl_count);
|
|
|
|
|
|
|
|
|
|
heap_size = init_heap32(&heap_space, d_hist, DIST_LEN);
|
|
|
|
|
gen_huff_code_lens(&heap_space, heap_size, bl_count, d_codes, DIST_LEN,
|
|
|
|
|
MAX_DEFLATE_CODE_LEN);
|
|
|
|
|
max_d_code = set_dist_huff_codes(d_codes, bl_count);
|
|
|
|
|
|
|
|
|
|
assert(max_ll_code >= 256); // must be EOB code
|
|
|
|
|
assert(max_d_code != 0);
|
|
|
|
|
|
|
|
|
|
/* Run length encode the length and distance huffman codes */
|
|
|
|
|
memset(cl_counts, 0, sizeof(cl_counts));
|
|
|
|
|
|
|
|
|
|
for (i = 0; i <= 256; i++) {
|
|
|
|
|
combined_table[i] = ll_codes[i].length;
|
|
|
|
|
compressed_len += ll_codes[i].length * ll_hist[i];
|
|
|
|
|
static_compressed_len += static_ll_codes[i].length * ll_hist[i];
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
for (; i < max_ll_code + 1; i++) {
|
|
|
|
|
combined_table[i] = ll_codes[i].length;
|
|
|
|
|
compressed_len += (ll_codes[i].length + len_code_extra_bits[i - 257]) * ll_hist[i];
|
|
|
|
|
static_compressed_len +=
|
|
|
|
|
(static_ll_codes[i].length + len_code_extra_bits[i - 257]) * ll_hist[i];
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
for (i = 0; i < max_d_code + 1; i++) {
|
|
|
|
|
combined_table[i + max_ll_code + 1] = d_codes[i].length;
|
|
|
|
|
compressed_len += (d_codes[i].length + dist_code_extra_bits[i]) * d_hist[i];
|
|
|
|
|
static_compressed_len +=
|
|
|
|
|
(static_d_codes[i].length + dist_code_extra_bits[i]) * d_hist[i];
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
if (static_compressed_len > compressed_len) {
|
|
|
|
|
num_cl_tokens = rl_encode(combined_table, max_ll_code + max_d_code + 2, cl_counts,
|
|
|
|
|
cl_tokens);
|
|
|
|
|
|
|
|
|
|
/* Create header */
|
|
|
|
|
create_header(bb, cl_tokens, num_cl_tokens, cl_counts, max_ll_code - 256,
|
|
|
|
|
max_d_code, end_of_block);
|
|
|
|
|
compressed_len += 8 * buffer_used(bb) + bb->m_bit_count;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/* Substitute in static block since it creates smaller block */
|
|
|
|
|
if (static_compressed_len <= compressed_len) {
|
|
|
|
|
memcpy(hufftables, &static_hufftables, sizeof(struct hufftables_icf));
|
|
|
|
|
memcpy(bb, &bb_tmp, sizeof(struct BitBuf2));
|
|
|
|
|
end_of_block = end_of_block ? 1 : 0;
|
|
|
|
|
write_bits(bb, 0x2 | end_of_block, 3);
|
|
|
|
|
compressed_len = static_compressed_len;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
expand_hufftables_icf(hufftables);
|
|
|
|
|
return compressed_len;
|
2016-10-03 23:50:52 +02:00
|
|
|
}
|
