dc11857591dfbd19fe9dd526c428b543b884a1c1
[wimlib] / src / lzms-common.c
1 /*
2  * lzms-common.c
3  *
4  * Code shared between the compressor and decompressor for the LZMS compression
5  * format.
6  */
7
8 /*
9  * Copyright (C) 2013 Eric Biggers
10  *
11  * This file is part of wimlib, a library for working with WIM files.
12  *
13  * wimlib is free software; you can redistribute it and/or modify it under the
14  * terms of the GNU General Public License as published by the Free
15  * Software Foundation; either version 3 of the License, or (at your option)
16  * any later version.
17  *
18  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
19  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
20  * A PARTICULAR PURPOSE. See the GNU General Public License for more
21  * details.
22  *
23  * You should have received a copy of the GNU General Public License
24  * along with wimlib; if not, see http://www.gnu.org/licenses/.
25  */
26
27 #ifdef HAVE_CONFIG_H
28 #  include "config.h"
29 #endif
30
31 #include "wimlib/endianness.h"
32 #include "wimlib/error.h"
33 #include "wimlib/lzms.h"
34 #include "wimlib/util.h"
35
36 #include <pthread.h>
37
38 /* A table that maps position slots to their base values.  These are constants
39  * computed at runtime by lzms_compute_slot_bases().  */
40 u32 lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
41
42 /* A table that maps length slots to their base values.  These are constants
43  * computed at runtime by lzms_compute_slot_bases().  */
44 u32 lzms_length_slot_base[LZMS_NUM_LEN_SYMS + 1];
45
46 /* Return the slot for the specified value.  */
47 unsigned
48 lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots)
49 {
50         unsigned slot = 0;
51
52         while (slot_base_tab[slot + 1] <= value)
53                 slot++;
54
55         return slot;
56 }
57
58
59 static void
60 lzms_decode_delta_rle_slot_bases(u32 slot_bases[],
61                                  const u8 delta_run_lens[], size_t num_run_lens)
62 {
63         u32 delta = 1;
64         u32 base = 0;
65         size_t slot = 0;
66         for (size_t i = 0; i < num_run_lens; i++) {
67                 u8 run_len = delta_run_lens[i];
68                 while (run_len--) {
69                         base += delta;
70                         slot_bases[slot++] = base;
71                 }
72                 delta <<= 1;
73         }
74 }
75
76 /* Initialize the global position and length slot tables.  */
77 static void
78 lzms_compute_slot_bases(void)
79 {
80         /* If an explicit formula that maps LZMS position and length slots to
81          * slot bases exists, then it could be used here.  But until one is
82          * found, the following code fills in the slots using the observation
83          * that the increase from one slot base to the next is an increasing
84          * power of 2.  Therefore, run-length encoding of the delta of adjacent
85          * entries can be used.  */
86         static const u8 position_slot_delta_run_lens[] = {
87                 9,   0,   9,   7,   10,  15,  15,  20,
88                 20,  30,  33,  40,  42,  45,  60,  73,
89                 80,  85,  95,  105, 6,
90         };
91
92         static const u8 length_slot_delta_run_lens[] = {
93                 27,  4,   6,   4,   5,   2,   1,   1,
94                 1,   1,   1,   0,   0,   0,   0,   0,
95                 1,
96         };
97
98         lzms_decode_delta_rle_slot_bases(lzms_position_slot_base,
99                                          position_slot_delta_run_lens,
100                                          ARRAY_LEN(position_slot_delta_run_lens));
101
102         lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS] = 0x7fffffff;
103
104         lzms_decode_delta_rle_slot_bases(lzms_length_slot_base,
105                                          length_slot_delta_run_lens,
106                                          ARRAY_LEN(length_slot_delta_run_lens));
107
108         lzms_length_slot_base[LZMS_NUM_LEN_SYMS] = 0x400108ab;
109 }
110
111 /* Initialize the global position length slot tables if not done so already.  */
112 void
113 lzms_init_slot_bases(void)
114 {
115         static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
116         static bool already_computed = false;
117
118         if (unlikely(!already_computed)) {
119                 pthread_mutex_lock(&mutex);
120                 if (!already_computed) {
121                         lzms_compute_slot_bases();
122                         already_computed = true;
123                 }
124                 pthread_mutex_unlock(&mutex);
125         }
126 }
127
128 static s32
129 lzms_maybe_do_x86_translation(u8 data[restrict], s32 i, s32 num_op_bytes,
130                               s32 * restrict closest_target_usage_p,
131                               s32 last_target_usages[restrict],
132                               s32 max_trans_offset, bool undo)
133 {
134         u16 pos;
135
136         if (undo) {
137                 if (i - *closest_target_usage_p <= max_trans_offset) {
138                         LZMS_DEBUG("Undid x86 translation at position %d "
139                                    "(opcode 0x%02x)", i, data[i]);
140                         le32 *p32 = (le32*)&data[i + num_op_bytes];
141                         u32 n = le32_to_cpu(*p32);
142                         *p32 = cpu_to_le32(n - i);
143                 }
144                 pos = i + le16_to_cpu(*(const le16*)&data[i + num_op_bytes]);
145         } else {
146                 pos = i + le16_to_cpu(*(const le16*)&data[i + num_op_bytes]);
147
148                 if (i - *closest_target_usage_p <= max_trans_offset) {
149                         LZMS_DEBUG("Did x86 translation at position %d "
150                                    "(opcode 0x%02x)", i, data[i]);
151                         le32 *p32 = (le32*)&data[i + num_op_bytes];
152                         u32 n = le32_to_cpu(*p32);
153                         *p32 = cpu_to_le32(n + i);
154                 }
155         }
156
157         i += num_op_bytes + sizeof(le32) - 1;
158
159         if (i - last_target_usages[pos] <= LZMS_X86_MAX_GOOD_TARGET_OFFSET)
160                 *closest_target_usage_p = i;
161
162         last_target_usages[pos] = i;
163
164         return i + 1;
165 }
166
167 static s32
168 lzms_may_x86_translate(const u8 p[restrict],
169                        s32 *restrict max_offset_ret)
170 {
171         /* Switch on first byte of the opcode, assuming it is really an x86
172          * instruction.  */
173         *max_offset_ret = LZMS_X86_MAX_TRANSLATION_OFFSET;
174         switch (p[0]) {
175         case 0x48:
176                 if (p[1] == 0x8b) {
177                         if (p[2] == 0x5 || p[2] == 0xd) {
178                                 /* Load relative (x86_64)  */
179                                 return 3;
180                         }
181                 } else if (p[1] == 0x8d) {
182                         if ((p[2] & 0x7) == 0x5) {
183                                 /* Load effective address relative (x86_64)  */
184                                 return 3;
185                         }
186                 }
187                 break;
188
189         case 0x4c:
190                 if (p[1] == 0x8d) {
191                         if ((p[2] & 0x7) == 0x5) {
192                                 /* Load effective address relative (x86_64)  */
193                                 return 3;
194                         }
195                 }
196                 break;
197
198         case 0xe8:
199                 /* Call relative  */
200                 *max_offset_ret = LZMS_X86_MAX_TRANSLATION_OFFSET / 2;
201                 return 1;
202
203         case 0xe9:
204                 /* Jump relative  */
205                 *max_offset_ret = 0;
206                 return 5;
207
208         case 0xf0:
209                 if (p[1] == 0x83 && p[2] == 0x05) {
210                         /* Lock add relative  */
211                         return 3;
212                 }
213                 break;
214
215         case 0xff:
216                 if (p[1] == 0x15) {
217                         /* Call indirect  */
218                         return 2;
219                 }
220                 break;
221         }
222         *max_offset_ret = 0;
223         return 1;
224 }
225
226 /*
227  * Translate relative addresses embedded in x86 instructions into absolute
228  * addresses (@undo == %false), or undo this translation (@undo == %true).
229  *
230  * @last_target_usages is a temporary array of length >= 65536.
231  */
232 void
233 lzms_x86_filter(u8 data[restrict],
234                 s32 size,
235                 s32 last_target_usages[restrict],
236                 bool undo)
237 {
238         s32 closest_target_usage = -LZMS_X86_MAX_TRANSLATION_OFFSET - 1;
239
240         for (s32 i = 0; i < 65536; i++)
241                 last_target_usages[i] = -LZMS_X86_MAX_GOOD_TARGET_OFFSET - 1;
242
243         for (s32 i = 0; i < size - 11; ) {
244                 s32 max_trans_offset;
245                 s32 n;
246
247                 n = lzms_may_x86_translate(data + i, &max_trans_offset);
248                 if (max_trans_offset) {
249                         i = lzms_maybe_do_x86_translation(data, i, n,
250                                                           &closest_target_usage,
251                                                           last_target_usages,
252                                                           max_trans_offset,
253                                                           undo);
254                 } else {
255                         i += n;
256                 }
257         }
258 }
259
260 static void
261 lzms_init_lz_lru_queues(struct lzms_lz_lru_queues *lz)
262 {
263         /* Recent offsets for LZ matches  */
264         for (u32 i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++)
265                 lz->recent_offsets[i] = i + 1;
266
267         lz->prev_offset = 0;
268         lz->upcoming_offset = 0;
269 }
270
271 static void
272 lzms_init_delta_lru_queues(struct lzms_delta_lru_queues *delta)
273 {
274         /* Recent offsets and powers for LZ matches  */
275         for (u32 i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++) {
276                 delta->recent_offsets[i] = i + 1;
277                 delta->recent_powers[i] = 0;
278         }
279         delta->prev_offset = 0;
280         delta->prev_power = 0;
281         delta->upcoming_offset = 0;
282         delta->upcoming_power = 0;
283 }
284
285
286 void
287 lzms_init_lru_queues(struct lzms_lru_queues *lru)
288 {
289         lzms_init_lz_lru_queues(&lru->lz);
290         lzms_init_delta_lru_queues(&lru->delta);
291 }
292
293 static void
294 lzms_update_lz_lru_queues(struct lzms_lz_lru_queues *lz)
295 {
296         if (lz->prev_offset != 0) {
297                 for (int i = LZMS_NUM_RECENT_OFFSETS - 1; i >= 0; i--)
298                         lz->recent_offsets[i + 1] = lz->recent_offsets[i];
299                 lz->recent_offsets[0] = lz->prev_offset;
300         }
301         lz->prev_offset = lz->upcoming_offset;
302 }
303
304 static void
305 lzms_update_delta_lru_queues(struct lzms_delta_lru_queues *delta)
306 {
307         if (delta->prev_offset != 0) {
308                 for (int i = LZMS_NUM_RECENT_OFFSETS - 1; i >= 0; i--) {
309                         delta->recent_offsets[i + 1] = delta->recent_offsets[i];
310                         delta->recent_powers[i + 1] = delta->recent_powers[i];
311                 }
312                 delta->recent_offsets[0] = delta->prev_offset;
313                 delta->recent_powers[0] = delta->prev_power;
314         }
315
316         delta->prev_offset = delta->upcoming_offset;
317         delta->prev_power = delta->upcoming_power;
318 }
319
320 void
321 lzms_update_lru_queues(struct lzms_lru_queues *lru)
322 {
323         lzms_update_lz_lru_queues(&lru->lz);
324         lzms_update_delta_lru_queues(&lru->delta);
325 }