2 * lzx-common.c - Common data for LZX compression and decompression.
6 * Copyright (C) 2012, 2013 Eric Biggers
8 * This file is part of wimlib, a library for working with WIM files.
10 * wimlib is free software; you can redistribute it and/or modify it under the
11 * terms of the GNU General Public License as published by the Free
12 * Software Foundation; either version 3 of the License, or (at your option)
15 * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
16 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
17 * A PARTICULAR PURPOSE. See the GNU General Public License for more
20 * You should have received a copy of the GNU General Public License
21 * along with wimlib; if not, see http://www.gnu.org/licenses/.
28 #include "wimlib/lzx.h"
29 #include "wimlib/util.h"
31 /* LZX uses what it calls 'position slots' to represent match offsets.
32 * What this means is that a small 'position slot' number and a small
33 * offset from that slot are encoded instead of one large offset for
35 * - lzx_position_base is an index to the position slot bases
36 * - lzx_extra_bits states how many bits of offset-from-base data is needed.
39 const u32 lzx_position_base[LZX_MAX_POSITION_SLOTS] = {
40 0 , 1 , 2 , 3 , 4 , /* 0 --- 4 */
41 6 , 8 , 12 , 16 , 24 , /* 5 --- 9 */
42 32 , 48 , 64 , 96 , 128 , /* 10 --- 14 */
43 192 , 256 , 384 , 512 , 768 , /* 15 --- 19 */
44 1024 , 1536 , 2048 , 3072 , 4096 , /* 20 --- 24 */
45 6144 , 8192 , 12288 , 16384 , 24576 , /* 25 --- 29 */
46 32768 , 49152 , 65536 , 98304 , 131072 , /* 30 --- 34 */
47 196608 , 262144 , 393216 , 524288 , 655360 , /* 35 --- 39 */
48 786432 , 917504 , 1048576, 1179648, 1310720, /* 40 --- 44 */
49 1441792, 1572864, 1703936, 1835008, 1966080, /* 45 --- 49 */
53 #ifdef USE_LZX_EXTRA_BITS_ARRAY
54 const u8 lzx_extra_bits[LZX_MAX_POSITION_SLOTS] = {
69 /* LZX window size must be a power of 2 between 2^15 and 2^21, inclusively. */
71 lzx_window_size_valid(size_t window_size)
73 if (window_size == 0 || (u32)window_size != window_size)
75 u32 order = bsr32(window_size);
76 if (window_size != 1U << order)
78 return (order >= LZX_MIN_WINDOW_ORDER && order <= LZX_MAX_WINDOW_ORDER);
81 /* Given a valid LZX window size, return the number of symbols that will exist
82 * in the main Huffman code. */
84 lzx_get_num_main_syms(u32 window_size)
86 /* NOTE: the calculation *should* be as follows:
88 * u32 max_offset = window_size - LZX_MIN_MATCH_LEN;
89 * u32 max_formatted_offset = max_offset + LZX_OFFSET_OFFSET;
90 * u32 num_position_slots = 1 + lzx_get_position_slot_raw(max_formatted_offset);
92 * However since LZX_MIN_MATCH_LEN == LZX_OFFSET_OFFSET, we would get
93 * max_formatted_offset == window_size, which would bump the number of
94 * position slots up by 1 since every valid LZX window size is equal to
95 * a position base value. The format doesn't do this, and instead
96 * disallows matches with minimum length and maximum offset. This sets
97 * max_formatted_offset = window_size - 1, so instead we must calculate:
99 * num_position_slots = 1 + lzx_get_position_slot_raw(window_size - 1);
101 * ... which is the same as
103 * num_position_slots = lzx_get_position_slot_raw(window_size);
105 * ... since every valid window size is equal to a position base value.
107 unsigned num_position_slots = lzx_get_position_slot_raw(window_size);
109 /* Now calculate the number of main symbols as LZX_NUM_CHARS literal
110 * symbols, plus 8 symbols per position slot (since there are 8 possible
111 * length headers, and we need all (position slot, length header)
113 return LZX_NUM_CHARS + (num_position_slots << 3);