Introduce ilog2_ceil()

[wimlib] / src / lzx_common.c

diff --git a/src/lzx_common.c b/src/lzx_common.c
index 0993f60756d869dccad03a17ed54714f77a32056..7925f1f197b6803ce31bca7fed7564302f6220e1 100644 (file)
--- 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 <string.h>
 
-#include "wimlib/bitops.h"
-#include "wimlib/endianness.h"
-#include "wimlib/lzx_common.h"
-#include "wimlib/unaligned.h"
-#include "wimlib/util.h"
-
 #ifdef __SSE2__
 #  include <emmintrin.h>
 #endif
@@ -39,6 +33,12 @@
 #  include <immintrin.h>
 #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] = {
@@ -57,7 +57,7 @@ const u32 lzx_offset_slot_base[LZX_MAX_OFFSET_SLOTS + 1] = {
 
 /* 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
@@ -99,17 +93,13 @@ lzx_get_num_offset_slots(unsigned window_order)
         * disallows this case.  This reduces the number of needed offset slots
         * 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);
-}
+       u32 max_adjusted_offset = (window_size - LZX_MIN_MATCH_LEN - 1) +
+                                 LZX_OFFSET_ADJUSTMENT;
+       unsigned num_offset_slots = 30;
+       while (max_adjusted_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 +107,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 +116,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 +125,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);
                }
        }
 }
@@ -326,13 +316,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);
 }