X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Flzx_common.c;h=fe201a42e5ab4ab67ca6f6f6367aa4cbdafb491b;hb=88afc46984c143cbf928a3186f8cc93d819e9269;hp=0993f60756d869dccad03a17ed54714f77a32056;hpb=3e8aa757aaa63297f0d54007adf46411778fb6a8;p=wimlib diff --git a/src/lzx_common.c b/src/lzx_common.c index 0993f607..fe201a42 100644 --- a/src/lzx_common.c +++ b/src/lzx_common.c @@ -3,7 +3,7 @@ */ /* - * Copyright (C) 2012, 2013, 2014, 2015 Eric Biggers + * Copyright (C) 2012-2016 Eric Biggers * * 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 @@ -25,12 +25,6 @@ #include -#include "wimlib/bitops.h" -#include "wimlib/endianness.h" -#include "wimlib/lzx_common.h" -#include "wimlib/unaligned.h" -#include "wimlib/util.h" - #ifdef __SSE2__ # include #endif @@ -39,25 +33,31 @@ # include #endif +#include "wimlib/bitops.h" +#include "wimlib/endianness.h" +#include "wimlib/lzx_common.h" +#include "wimlib/unaligned.h" +#include "wimlib/util.h" + /* Mapping: offset slot => first match offset that uses that offset slot. - */ -const u32 lzx_offset_slot_base[LZX_MAX_OFFSET_SLOTS + 1] = { - 0 , 1 , 2 , 3 , 4 , /* 0 --- 4 */ - 6 , 8 , 12 , 16 , 24 , /* 5 --- 9 */ - 32 , 48 , 64 , 96 , 128 , /* 10 --- 14 */ - 192 , 256 , 384 , 512 , 768 , /* 15 --- 19 */ - 1024 , 1536 , 2048 , 3072 , 4096 , /* 20 --- 24 */ - 6144 , 8192 , 12288 , 16384 , 24576 , /* 25 --- 29 */ - 32768 , 49152 , 65536 , 98304 , 131072 , /* 30 --- 34 */ - 196608 , 262144 , 393216 , 524288 , 655360 , /* 35 --- 39 */ - 786432 , 917504 , 1048576, 1179648, 1310720, /* 40 --- 44 */ - 1441792, 1572864, 1703936, 1835008, 1966080, /* 45 --- 49 */ - 2097152 /* extra */ + * The offset slots for repeat offsets map to "fake" offsets < 1. */ +const s32 lzx_offset_slot_base[LZX_MAX_OFFSET_SLOTS + 1] = { + -2 , -1 , 0 , 1 , 2 , /* 0 --- 4 */ + 4 , 6 , 10 , 14 , 22 , /* 5 --- 9 */ + 30 , 46 , 62 , 94 , 126 , /* 10 --- 14 */ + 190 , 254 , 382 , 510 , 766 , /* 15 --- 19 */ + 1022 , 1534 , 2046 , 3070 , 4094 , /* 20 --- 24 */ + 6142 , 8190 , 12286 , 16382 , 24574 , /* 25 --- 29 */ + 32766 , 49150 , 65534 , 98302 , 131070 , /* 30 --- 34 */ + 196606 , 262142 , 393214 , 524286 , 655358 , /* 35 --- 39 */ + 786430 , 917502 , 1048574, 1179646, 1310718, /* 40 --- 44 */ + 1441790, 1572862, 1703934, 1835006, 1966078, /* 45 --- 49 */ + 2097150 /* extra */ }; /* Mapping: offset slot => how many extra bits must be read and added to the * corresponding offset slot base to decode the match offset. */ -const u8 lzx_extra_offset_bits[LZX_MAX_OFFSET_SLOTS + 1] = { +const u8 lzx_extra_offset_bits[LZX_MAX_OFFSET_SLOTS] = { 0 , 0 , 0 , 0 , 1 , 1 , 2 , 2 , 3 , 3 , 4 , 4 , 5 , 5 , 6 , @@ -68,7 +68,6 @@ const u8 lzx_extra_offset_bits[LZX_MAX_OFFSET_SLOTS + 1] = { 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, - 17 }; /* Round the specified buffer size up to the next valid LZX window size, and @@ -77,21 +76,16 @@ const u8 lzx_extra_offset_bits[LZX_MAX_OFFSET_SLOTS + 1] = { unsigned lzx_get_window_order(size_t max_bufsize) { - unsigned order; - if (max_bufsize == 0 || max_bufsize > LZX_MAX_WINDOW_SIZE) return 0; - order = fls32(max_bufsize); - - if (((u32)1 << order) != max_bufsize) - order++; - - return max(order, LZX_MIN_WINDOW_ORDER); + return max(ilog2_ceil(max_bufsize), LZX_MIN_WINDOW_ORDER); } +/* Given a valid LZX window order, return the number of symbols that will exist + * in the main Huffman code. */ unsigned -lzx_get_num_offset_slots(unsigned window_order) +lzx_get_num_main_syms(unsigned window_order) { /* Note: one would expect that the maximum match offset would be * 'window_size - LZX_MIN_MATCH_LEN', which would occur if the first two @@ -100,16 +94,11 @@ lzx_get_num_offset_slots(unsigned window_order) * by 1. */ u32 window_size = (u32)1 << window_order; u32 max_offset = window_size - LZX_MIN_MATCH_LEN - 1; - return 1 + lzx_get_offset_slot(max_offset); -} + unsigned num_offset_slots = 30; + while (max_offset >= lzx_offset_slot_base[num_offset_slots]) + num_offset_slots++; -/* Given a valid LZX window order, return the number of symbols that will exist - * in the main Huffman code. */ -unsigned -lzx_get_num_main_syms(unsigned window_order) -{ - return LZX_NUM_CHARS + (lzx_get_num_offset_slots(window_order) * - LZX_NUM_LEN_HEADERS); + return LZX_NUM_CHARS + (num_offset_slots * LZX_NUM_LEN_HEADERS); } static void @@ -117,7 +106,7 @@ do_translate_target(void *target, s32 input_pos) { s32 abs_offset, rel_offset; - rel_offset = get_unaligned_u32_le(target); + rel_offset = get_unaligned_le32(target); if (rel_offset >= -input_pos && rel_offset < LZX_WIM_MAGIC_FILESIZE) { if (rel_offset < LZX_WIM_MAGIC_FILESIZE - input_pos) { /* "good translation" */ @@ -126,7 +115,7 @@ do_translate_target(void *target, s32 input_pos) /* "compensating translation" */ abs_offset = rel_offset - LZX_WIM_MAGIC_FILESIZE; } - put_unaligned_u32_le(abs_offset, target); + put_unaligned_le32(abs_offset, target); } } @@ -135,18 +124,18 @@ undo_translate_target(void *target, s32 input_pos) { s32 abs_offset, rel_offset; - abs_offset = get_unaligned_u32_le(target); + abs_offset = get_unaligned_le32(target); if (abs_offset >= 0) { if (abs_offset < LZX_WIM_MAGIC_FILESIZE) { /* "good translation" */ rel_offset = abs_offset - input_pos; - put_unaligned_u32_le(rel_offset, target); + put_unaligned_le32(rel_offset, target); } } else { if (abs_offset >= -input_pos) { /* "compensating translation" */ rel_offset = abs_offset + LZX_WIM_MAGIC_FILESIZE; - put_unaligned_u32_le(rel_offset, target); + put_unaligned_le32(rel_offset, target); } } } @@ -299,7 +288,7 @@ lzx_e8_filter(u8 *data, u32 size, void (*process_target)(void *, s32)) * 'valid_mask' ensures we never process an E8 byte that * was itself part of a translation target. */ while ((e8_mask &= valid_mask)) { - unsigned bit = ffs32(e8_mask); + unsigned bit = bsf32(e8_mask); (*process_target)(p + bit + 1, p + bit - data); valid_mask &= ~((u64)0x1F << bit); } @@ -326,13 +315,13 @@ lzx_e8_filter(u8 *data, u32 size, void (*process_target)(void *, s32)) } void -lzx_do_e8_preprocessing(u8 *data, u32 size) +lzx_preprocess(u8 *data, u32 size) { lzx_e8_filter(data, size, do_translate_target); } void -lzx_undo_e8_preprocessing(u8 *data, u32 size) +lzx_postprocess(u8 *data, u32 size) { lzx_e8_filter(data, size, undo_translate_target); }