LZX: Allow max_block_size not a power of 2
[wimlib] / include / wimlib / lzx.h
1 /*
2  * lzx.h
3  *
4  * Declarations shared between LZX compression and decompression.
5  */
6
7 #ifndef _WIMLIB_LZX_H
8 #define _WIMLIB_LZX_H
9
10 #include "wimlib/assert.h"
11 #include "wimlib/compiler.h"
12 #include "wimlib/lzx_constants.h"
13 #include "wimlib/util.h"
14 #include "wimlib/types.h"
15
16 //#define ENABLE_LZX_DEBUG
17 #ifdef ENABLE_LZX_DEBUG
18 #       define LZX_ASSERT wimlib_assert
19 #else
20 #       define LZX_ASSERT(...)
21 #endif
22
23 #define USE_LZX_EXTRA_BITS_ARRAY
24
25 #ifdef USE_LZX_EXTRA_BITS_ARRAY
26 extern const u8 lzx_extra_bits[LZX_MAX_POSITION_SLOTS];
27 #endif
28
29 /* Given the number of an LZX position slot, return the number of extra bits that
30  * are needed to encode the match offset. */
31 static inline unsigned
32 lzx_get_num_extra_bits(unsigned position_slot)
33 {
34 #ifdef USE_LZX_EXTRA_BITS_ARRAY
35         /* Use a table */
36         return lzx_extra_bits[position_slot];
37 #else
38         /* Calculate directly using a shift and subtraction. */
39         LZX_ASSERT(position_slot >= 2 && position_slot <= 37);
40         return (position_slot >> 1) - 1;
41 #endif
42 }
43
44 extern const u32 lzx_position_base[LZX_MAX_POSITION_SLOTS];
45
46 /* Returns the LZX position slot that corresponds to a given formatted offset.
47  *
48  * Logically, this returns the smallest i such that
49  * formatted_offset >= lzx_position_base[i].
50  *
51  * The actual implementation below takes advantage of the regularity of the
52  * numbers in the lzx_position_base array to calculate the slot directly from
53  * the formatted offset without actually looking at the array.
54  */
55 static inline unsigned
56 lzx_get_position_slot_raw(u32 formatted_offset)
57 {
58         if (formatted_offset >= 196608) {
59                 return (formatted_offset >> 17) + 34;
60         } else {
61                 LZX_ASSERT(2 <= formatted_offset && formatted_offset < 655360);
62                 unsigned mssb_idx = bsr32(formatted_offset);
63                 return (mssb_idx << 1) |
64                         ((formatted_offset >> (mssb_idx - 1)) & 1);
65         }
66 }
67
68 extern unsigned lzx_get_window_order(size_t max_block_size);
69
70 extern unsigned lzx_get_num_main_syms(unsigned window_order);
71
72 /* Least-recently used queue for match offsets.  */
73 struct lzx_lru_queue {
74         u32 R[LZX_NUM_RECENT_OFFSETS];
75 }
76 #ifdef __x86_64__
77 _aligned_attribute(8)  /* Improves performance of LZX compression by 1% - 2%;
78                           specifically, this speeds up
79                           lzx_choose_near_optimal_item().  */
80 #endif
81 ;
82
83 /* Initialize the LZX least-recently-used match offset queue at the beginning of
84  * a new window for either decompression or compression.  */
85 static inline void
86 lzx_lru_queue_init(struct lzx_lru_queue *queue)
87 {
88         for (unsigned i = 0; i < LZX_NUM_RECENT_OFFSETS; i++)
89                 queue->R[i] = 1;
90 }
91
92 extern void
93 lzx_do_e8_preprocessing(u8 *data, u32 size);
94
95 extern void
96 lzx_undo_e8_preprocessing(u8 *data, u32 size);
97
98 #endif /* _WIMLIB_LZX_H */