X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Flzms-common.c;h=95682d53a56490fd382d57b7d779b001e78782b7;hp=dc11857591dfbd19fe9dd526c428b543b884a1c1;hb=1c1c12926f4de39cb35d8d4c5a5280ab0d6ba931;hpb=027518fa61bd9232ff7fa7ecd270546d920c912f diff --git a/src/lzms-common.c b/src/lzms-common.c index dc118575..95682d53 100644 --- a/src/lzms-common.c +++ b/src/lzms-common.c @@ -6,22 +6,20 @@ */ /* - * 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 @@ -29,61 +27,88 @@ #endif #include "wimlib/endianness.h" -#include "wimlib/error.h" #include "wimlib/lzms.h" +#include "wimlib/unaligned.h" #include "wimlib/util.h" #include -/* A table that maps position slots to their base values. These are constants - * computed at runtime by lzms_compute_slot_bases(). */ -u32 lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1]; +/*************************************************************** + * Constant tables initialized by lzms_compute_slots(): * + ***************************************************************/ + +/* Table: offset slot => offset slot base value */ +u32 lzms_offset_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1]; -/* A table that maps length slots to their base values. These are constants - * computed at runtime by lzms_compute_slot_bases(). */ +/* 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]; -/* Return the slot for the specified value. */ +/* Table: length slot => number of extra length bits */ +u8 lzms_extra_length_bits[LZMS_NUM_LEN_SYMS]; + unsigned lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots) { - unsigned slot = 0; - - while (slot_base_tab[slot + 1] <= value) - slot++; - - return slot; + unsigned l = 0; + unsigned r = num_slots - 1; + for (;;) { + LZMS_ASSERT(r >= l); + unsigned slot = (l + r) / 2; + if (value >= slot_base_tab[slot]) { + if (value < slot_base_tab[slot + 1]) + return slot; + else + l = slot + 1; + } else { + r = slot - 1; + } + } } - static void lzms_decode_delta_rle_slot_bases(u32 slot_bases[], - const u8 delta_run_lens[], size_t num_run_lens) + u8 extra_bits[], + const u8 delta_run_lens[], + unsigned num_run_lens, + u32 final, + unsigned expected_num_slots) { + unsigned order = 0; u32 delta = 1; u32 base = 0; - size_t slot = 0; - for (size_t 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; - slot_bases[slot++] = base; + if (slot > 0) + extra_bits[slot - 1] = order; + slot_bases[slot] = base; + slot++; } delta <<= 1; + order++; } + LZMS_ASSERT(slot == expected_num_slots); + + slot_bases[slot] = final; + extra_bits[slot - 1] = bsr32(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_slot_bases(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, @@ -95,34 +120,30 @@ lzms_compute_slot_bases(void) 1, }; - lzms_decode_delta_rle_slot_bases(lzms_position_slot_base, - position_slot_delta_run_lens, - ARRAY_LEN(position_slot_delta_run_lens)); - - lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS] = 0x7fffffff; + /* 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); + /* Length slots */ lzms_decode_delta_rle_slot_bases(lzms_length_slot_base, + lzms_extra_length_bits, length_slot_delta_run_lens, - ARRAY_LEN(length_slot_delta_run_lens)); - - lzms_length_slot_base[LZMS_NUM_LEN_SYMS] = 0x400108ab; + ARRAY_LEN(length_slot_delta_run_lens), + 0x400108ab, + LZMS_NUM_LEN_SYMS); } -/* Initialize the global position length slot tables if not done so already. */ +/* Initialize the global offset and length slot tables if not already done. */ void -lzms_init_slot_bases(void) +lzms_init_slots(void) { - static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; - static bool already_computed = false; - - if (unlikely(!already_computed)) { - pthread_mutex_lock(&mutex); - if (!already_computed) { - lzms_compute_slot_bases(); - already_computed = true; - } - pthread_mutex_unlock(&mutex); - } + static pthread_once_t once = PTHREAD_ONCE_INIT; + + pthread_once(&once, lzms_compute_slots); } static s32 @@ -137,20 +158,20 @@ lzms_maybe_do_x86_translation(u8 data[restrict], s32 i, s32 num_op_bytes, 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 = le32_to_cpu(load_le32_unaligned(p32)); + store_le32_unaligned(cpu_to_le32(n - i), p32); } - pos = i + le16_to_cpu(*(const le16*)&data[i + num_op_bytes]); + pos = i + le16_to_cpu(load_le16_unaligned(&data[i + num_op_bytes])); } else { - pos = i + le16_to_cpu(*(const le16*)&data[i + num_op_bytes]); + pos = i + le16_to_cpu(load_le16_unaligned(&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 = le32_to_cpu(load_le32_unaligned(p32)); + store_le32_unaligned(cpu_to_le32(n + i), p32); } } @@ -164,9 +185,8 @@ lzms_maybe_do_x86_translation(u8 data[restrict], s32 i, s32 num_op_bytes, return i + 1; } -static s32 -lzms_may_x86_translate(const u8 p[restrict], - s32 *restrict max_offset_ret) +static inline s32 +lzms_may_x86_translate(const u8 p[restrict], s32 *restrict max_offset_ret) { /* Switch on first byte of the opcode, assuming it is really an x86 * instruction. */ @@ -227,40 +247,76 @@ lzms_may_x86_translate(const u8 p[restrict], * Translate relative addresses embedded in x86 instructions into absolute * addresses (@undo == %false), or undo this translation (@undo == %true). * - * @last_target_usages is a temporary array of length >= 65536. + * Absolute addresses are usually more compressible by LZ factorization. + * + * @last_target_usages must be a temporary array of length >= 65536. */ void -lzms_x86_filter(u8 data[restrict], - s32 size, - s32 last_target_usages[restrict], - bool undo) +lzms_x86_filter(u8 data[restrict], s32 size, + s32 last_target_usages[restrict], bool undo) { + /* + * Note: this filter runs unconditionally and uses a custom algorithm to + * detect data regions that probably contain x86 code. + * + * 'closest_target_usage' tracks the most recent position that has a + * good chance of being an x86 instruction. When the filter detects a + * likely x86 instruction, it updates this variable and considers the + * next 1023 bytes of data as valid for x86 translations. + * + * If part of the data does not, in fact, contain x86 machine code, then + * 'closest_target_usage' will, very likely, eventually fall more than + * 1023 bytes behind the current position. This results in x86 + * translations being disabled until the next likely x86 instruction is + * detected. + * + * Translations on relative call (e8 opcode) instructions are slightly + * more restricted. They require that the most recent likely x86 + * instruction was in the last 511 bytes, rather than the last 1023 + * bytes. + * + * To identify "likely x86 instructions", the algorithm attempts to + * track the position of the most recent potential relative-addressing + * instruction that referenced each possible memory address. If it + * finds two references to the same memory address within a 65535 byte + * window, the second reference is flagged as a likely x86 instruction. + * Since the instructions considered for translation necessarily use + * relative addressing, the algorithm does a tentative translation into + * absolute addresses. In addition, so that memory addresses can be + * looked up in an array of reasonable size (in this code, + * 'last_target_usages'), only the low-order 2 bytes of each address are + * considered significant. + */ + s32 closest_target_usage = -LZMS_X86_MAX_TRANSLATION_OFFSET - 1; for (s32 i = 0; i < 65536; i++) last_target_usages[i] = -LZMS_X86_MAX_GOOD_TARGET_OFFSET - 1; - for (s32 i = 0; i < size - 11; ) { + for (s32 i = 1; i < size - 16; ) { s32 max_trans_offset; s32 n; n = lzms_may_x86_translate(data + i, &max_trans_offset); + if (max_trans_offset) { + /* Recognized opcode. */ i = lzms_maybe_do_x86_translation(data, i, n, &closest_target_usage, last_target_usages, max_trans_offset, undo); } else { + /* Not a recognized opcode. */ i += n; } } } -static void +void lzms_init_lz_lru_queues(struct lzms_lz_lru_queues *lz) { - /* Recent offsets for LZ matches */ + /* Recent offsets for LZ matches */ for (u32 i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++) lz->recent_offsets[i] = i + 1; @@ -268,10 +324,10 @@ lzms_init_lz_lru_queues(struct lzms_lz_lru_queues *lz) 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 */ + /* Recent offsets and powers for LZ matches */ for (u32 i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++) { delta->recent_offsets[i] = i + 1; delta->recent_powers[i] = 0; @@ -286,12 +342,12 @@ lzms_init_delta_lru_queues(struct lzms_delta_lru_queues *delta) void lzms_init_lru_queues(struct lzms_lru_queues *lru) { - lzms_init_lz_lru_queues(&lru->lz); - lzms_init_delta_lru_queues(&lru->delta); + lzms_init_lz_lru_queues(&lru->lz); + lzms_init_delta_lru_queues(&lru->delta); } -static void -lzms_update_lz_lru_queues(struct lzms_lz_lru_queues *lz) +void +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--) @@ -301,7 +357,7 @@ lzms_update_lz_lru_queues(struct lzms_lz_lru_queues *lz) lz->prev_offset = lz->upcoming_offset; } -static void +void lzms_update_delta_lru_queues(struct lzms_delta_lru_queues *delta) { if (delta->prev_offset != 0) { @@ -320,6 +376,6 @@ lzms_update_delta_lru_queues(struct lzms_delta_lru_queues *delta) void lzms_update_lru_queues(struct lzms_lru_queues *lru) { - lzms_update_lz_lru_queues(&lru->lz); - lzms_update_delta_lru_queues(&lru->delta); + lzms_update_lz_lru_queue(&lru->lz); + lzms_update_delta_lru_queues(&lru->delta); }