*/
/*
- * Copyright (C) 2013 Eric Biggers
+ * Copyright (C) 2013, 2014 Eric Biggers
*
- * This file is part of wimlib, a library for working with WIM files.
+ * This file is free software; you can redistribute it and/or modify it under
+ * the terms of the GNU Lesser General Public License as published by the Free
+ * Software Foundation; either version 3 of the License, or (at your option) any
+ * later version.
*
- * wimlib is free software; you can redistribute it and/or modify it under the
- * terms of the GNU General Public License as published by the Free
- * Software Foundation; either version 3 of the License, or (at your option)
- * any later version.
- *
- * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
- * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
- * A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * This file is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
* details.
*
- * You should have received a copy of the GNU General Public License
- * along with wimlib; if not, see http://www.gnu.org/licenses/.
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this file; if not, see http://www.gnu.org/licenses/.
*/
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif
+#include "wimlib/bitops.h"
#include "wimlib/endianness.h"
#include "wimlib/lzms.h"
+#include "wimlib/unaligned.h"
#include "wimlib/util.h"
#include <pthread.h>
* Constant tables initialized by lzms_compute_slots(): *
***************************************************************/
-/* Table: position slot => position slot base value */
-u32 lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
-
-/* Table: position slot => number of extra position bits */
-u8 lzms_extra_position_bits[LZMS_MAX_NUM_OFFSET_SYMS];
+/* Table: offset slot => offset slot base value */
+u32 lzms_offset_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
-/* Table: log2(position) => [lower bound, upper bound] on position slot */
-u16 lzms_order_to_position_slot_bounds[30][2];
+/* Table: offset slot => number of extra offset bits */
+u8 lzms_extra_offset_bits[LZMS_MAX_NUM_OFFSET_SYMS];
/* Table: length slot => length slot base value */
u32 lzms_length_slot_base[LZMS_NUM_LEN_SYMS + 1];
/* Table: length slot => number of extra length bits */
u8 lzms_extra_length_bits[LZMS_NUM_LEN_SYMS];
-/* Table: length (< LZMS_NUM_FAST_LENGTHS only) => length slot */
-u8 lzms_length_slot_fast[LZMS_NUM_FAST_LENGTHS];
-
-u32
+unsigned
lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots)
{
- u32 l = 0;
- u32 r = num_slots - 1;
+ unsigned l = 0;
+ unsigned r = num_slots - 1;
for (;;) {
LZMS_ASSERT(r >= l);
- u32 slot = (l + r) / 2;
+ unsigned slot = (l + r) / 2;
if (value >= slot_base_tab[slot]) {
if (value < slot_base_tab[slot + 1])
return slot;
lzms_decode_delta_rle_slot_bases(u32 slot_bases[],
u8 extra_bits[],
const u8 delta_run_lens[],
- u32 num_run_lens,
+ unsigned num_run_lens,
u32 final,
- u32 expected_num_slots)
+ unsigned expected_num_slots)
{
- u32 order = 0;
+ unsigned order = 0;
u32 delta = 1;
u32 base = 0;
- u32 slot = 0;
- for (u32 i = 0; i < num_run_lens; i++) {
- u8 run_len = delta_run_lens[i];
+ unsigned slot = 0;
+ for (unsigned i = 0; i < num_run_lens; i++) {
+ unsigned run_len = delta_run_lens[i];
while (run_len--) {
base += delta;
if (slot > 0)
LZMS_ASSERT(slot == expected_num_slots);
slot_bases[slot] = final;
- extra_bits[slot - 1] = bsr32(slot_bases[slot] - slot_bases[slot - 1]);
+ extra_bits[slot - 1] = fls32(slot_bases[slot] - slot_bases[slot - 1]);
}
-/* Initialize the global position and length slot tables. */
+/* Initialize the global offset and length slot tables. */
static void
lzms_compute_slots(void)
{
- /* If an explicit formula that maps LZMS position and length slots to
- * slot bases exists, then it could be used here. But until one is
- * found, the following code fills in the slots using the observation
- * that the increase from one slot base to the next is an increasing
- * power of 2. Therefore, run-length encoding of the delta of adjacent
- * entries can be used. */
- static const u8 position_slot_delta_run_lens[] = {
+ /* If an explicit formula that maps LZMS offset and length slots to slot
+ * bases exists, then it could be used here. But until one is found,
+ * the following code fills in the slots using the observation that the
+ * increase from one slot base to the next is an increasing power of 2.
+ * Therefore, run-length encoding of the delta of adjacent entries can
+ * be used. */
+ static const u8 offset_slot_delta_run_lens[] = {
9, 0, 9, 7, 10, 15, 15, 20,
20, 30, 33, 40, 42, 45, 60, 73,
80, 85, 95, 105, 6,
1,
};
- /* Position slots */
- lzms_decode_delta_rle_slot_bases(lzms_position_slot_base,
- lzms_extra_position_bits,
- position_slot_delta_run_lens,
- ARRAY_LEN(position_slot_delta_run_lens),
+ /* Offset slots */
+ lzms_decode_delta_rle_slot_bases(lzms_offset_slot_base,
+ lzms_extra_offset_bits,
+ offset_slot_delta_run_lens,
+ ARRAY_LEN(offset_slot_delta_run_lens),
0x7fffffff,
LZMS_MAX_NUM_OFFSET_SYMS);
- for (u32 order = 0; order < 30; order++) {
- lzms_order_to_position_slot_bounds[order][0] =
- lzms_get_slot(1U << order, lzms_position_slot_base,
- LZMS_MAX_NUM_OFFSET_SYMS);
- lzms_order_to_position_slot_bounds[order][1] =
- lzms_get_slot((1U << (order + 1)) - 1, lzms_position_slot_base,
- LZMS_MAX_NUM_OFFSET_SYMS);
- }
-
/* Length slots */
lzms_decode_delta_rle_slot_bases(lzms_length_slot_base,
lzms_extra_length_bits,
ARRAY_LEN(length_slot_delta_run_lens),
0x400108ab,
LZMS_NUM_LEN_SYMS);
-
- /* Create table mapping short lengths to length slots. */
- for (u32 slot = 0, i = 0; i < LZMS_NUM_FAST_LENGTHS; i++) {
- if (i >= lzms_length_slot_base[slot + 1])
- slot++;
- lzms_length_slot_fast[i] = slot;
- }
}
-/* Initialize the global position and length slot tables if not done so already.
- * */
+/* Initialize the global offset and length slot tables if not already done. */
void
lzms_init_slots(void)
{
if (i - *closest_target_usage_p <= max_trans_offset) {
LZMS_DEBUG("Undid x86 translation at position %d "
"(opcode 0x%02x)", i, data[i]);
- le32 *p32 = (le32*)&data[i + num_op_bytes];
- u32 n = le32_to_cpu(*p32);
- *p32 = cpu_to_le32(n - i);
+ void *p32 = &data[i + num_op_bytes];
+ u32 n = get_unaligned_u32_le(p32);
+ put_unaligned_u32_le(n - i, p32);
}
- pos = i + le16_to_cpu(*(const le16*)&data[i + num_op_bytes]);
+ pos = i + get_unaligned_u16_le(&data[i + num_op_bytes]);
} else {
- pos = i + le16_to_cpu(*(const le16*)&data[i + num_op_bytes]);
+ pos = i + get_unaligned_u16_le(&data[i + num_op_bytes]);
if (i - *closest_target_usage_p <= max_trans_offset) {
LZMS_DEBUG("Did x86 translation at position %d "
"(opcode 0x%02x)", i, data[i]);
- le32 *p32 = (le32*)&data[i + num_op_bytes];
- u32 n = le32_to_cpu(*p32);
- *p32 = cpu_to_le32(n + i);
+ void *p32 = &data[i + num_op_bytes];
+ u32 n = get_unaligned_u32_le(p32);
+ put_unaligned_u32_le(n + i, p32);
}
}
for (s32 i = 0; i < 65536; i++)
last_target_usages[i] = -LZMS_X86_MAX_GOOD_TARGET_OFFSET - 1;
- for (s32 i = 0; i < size - 16; ) {
+ for (s32 i = 1; i < size - 16; ) {
s32 max_trans_offset;
s32 n;
}
}
-static void
+void
lzms_init_lz_lru_queues(struct lzms_lz_lru_queues *lz)
{
/* Recent offsets for LZ matches */
lz->upcoming_offset = 0;
}
-static void
+void
lzms_init_delta_lru_queues(struct lzms_delta_lru_queues *delta)
{
/* Recent offsets and powers for LZ matches */
}
void
-lzms_update_lz_lru_queues(struct lzms_lz_lru_queues *lz)
+lzms_update_lz_lru_queue(struct lzms_lz_lru_queues *lz)
{
if (lz->prev_offset != 0) {
for (int i = LZMS_NUM_RECENT_OFFSETS - 1; i >= 0; i--)
void
lzms_update_lru_queues(struct lzms_lru_queues *lru)
{
- lzms_update_lz_lru_queues(&lru->lz);
+ lzms_update_lz_lru_queue(&lru->lz);
lzms_update_delta_lru_queues(&lru->delta);
}
git://wimlib.net / wimlib / blobdiff