1
2
3
4
5
6
7
8
9
10
11#include "xz_private.h"
12
13
14
15
16
17#ifdef XZ_DEC_BCJ
18
19struct xz_dec_bcj {
20
21 enum {
22 BCJ_X86 = 4,
23 BCJ_POWERPC = 5,
24 BCJ_IA64 = 6,
25 BCJ_ARM = 7,
26 BCJ_ARMTHUMB = 8,
27 BCJ_SPARC = 9
28 } type;
29
30
31
32
33
34
35 enum xz_ret ret;
36
37
38 bool single_call;
39
40
41
42
43
44
45 uint32_t pos;
46
47
48 uint32_t x86_prev_mask;
49
50
51 uint8_t *out;
52 size_t out_pos;
53 size_t out_size;
54
55 struct {
56
57 size_t filtered;
58
59
60 size_t size;
61
62
63
64
65
66
67
68
69
70
71
72
73
74 uint8_t buf[16];
75 } temp;
76};
77
78#ifdef XZ_DEC_X86
79
80
81
82
83static inline int bcj_x86_test_msbyte(uint8_t b)
84{
85 return b == 0x00 || b == 0xFF;
86}
87
88static size_t bcj_x86(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
89{
90 static const bool mask_to_allowed_status[8]
91 = { true, true, true, false, true, false, false, false };
92
93 static const uint8_t mask_to_bit_num[8] = { 0, 1, 2, 2, 3, 3, 3, 3 };
94
95 size_t i;
96 size_t prev_pos = (size_t)-1;
97 uint32_t prev_mask = s->x86_prev_mask;
98 uint32_t src;
99 uint32_t dest;
100 uint32_t j;
101 uint8_t b;
102
103 if (size <= 4)
104 return 0;
105
106 size -= 4;
107 for (i = 0; i < size; ++i) {
108 if ((buf[i] & 0xFE) != 0xE8)
109 continue;
110
111 prev_pos = i - prev_pos;
112 if (prev_pos > 3) {
113 prev_mask = 0;
114 } else {
115 prev_mask = (prev_mask << (prev_pos - 1)) & 7;
116 if (prev_mask != 0) {
117 b = buf[i + 4 - mask_to_bit_num[prev_mask]];
118 if (!mask_to_allowed_status[prev_mask]
119 || bcj_x86_test_msbyte(b)) {
120 prev_pos = i;
121 prev_mask = (prev_mask << 1) | 1;
122 continue;
123 }
124 }
125 }
126
127 prev_pos = i;
128
129 if (bcj_x86_test_msbyte(buf[i + 4])) {
130 src = get_unaligned_le32(buf + i + 1);
131 while (true) {
132 dest = src - (s->pos + (uint32_t)i + 5);
133 if (prev_mask == 0)
134 break;
135
136 j = mask_to_bit_num[prev_mask] * 8;
137 b = (uint8_t)(dest >> (24 - j));
138 if (!bcj_x86_test_msbyte(b))
139 break;
140
141 src = dest ^ (((uint32_t)1 << (32 - j)) - 1);
142 }
143
144 dest &= 0x01FFFFFF;
145 dest |= (uint32_t)0 - (dest & 0x01000000);
146 put_unaligned_le32(dest, buf + i + 1);
147 i += 4;
148 } else {
149 prev_mask = (prev_mask << 1) | 1;
150 }
151 }
152
153 prev_pos = i - prev_pos;
154 s->x86_prev_mask = prev_pos > 3 ? 0 : prev_mask << (prev_pos - 1);
155 return i;
156}
157#endif
158
159#ifdef XZ_DEC_POWERPC
160static size_t bcj_powerpc(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
161{
162 size_t i;
163 uint32_t instr;
164
165 for (i = 0; i + 4 <= size; i += 4) {
166 instr = get_unaligned_be32(buf + i);
167 if ((instr & 0xFC000003) == 0x48000001) {
168 instr &= 0x03FFFFFC;
169 instr -= s->pos + (uint32_t)i;
170 instr &= 0x03FFFFFC;
171 instr |= 0x48000001;
172 put_unaligned_be32(instr, buf + i);
173 }
174 }
175
176 return i;
177}
178#endif
179
180#ifdef XZ_DEC_IA64
181static size_t bcj_ia64(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
182{
183 static const uint8_t branch_table[32] = {
184 0, 0, 0, 0, 0, 0, 0, 0,
185 0, 0, 0, 0, 0, 0, 0, 0,
186 4, 4, 6, 6, 0, 0, 7, 7,
187 4, 4, 0, 0, 4, 4, 0, 0
188 };
189
190
191
192
193
194
195
196
197 size_t i;
198 size_t j;
199
200
201 uint32_t slot;
202
203
204 uint32_t bit_pos;
205
206
207 uint32_t byte_pos;
208 uint32_t bit_res;
209
210
211 uint32_t addr;
212
213
214 uint32_t mask;
215
216
217 uint64_t instr;
218
219
220 uint64_t norm;
221
222 for (i = 0; i + 16 <= size; i += 16) {
223 mask = branch_table[buf[i] & 0x1F];
224 for (slot = 0, bit_pos = 5; slot < 3; ++slot, bit_pos += 41) {
225 if (((mask >> slot) & 1) == 0)
226 continue;
227
228 byte_pos = bit_pos >> 3;
229 bit_res = bit_pos & 7;
230 instr = 0;
231 for (j = 0; j < 6; ++j)
232 instr |= (uint64_t)(buf[i + j + byte_pos])
233 << (8 * j);
234
235 norm = instr >> bit_res;
236
237 if (((norm >> 37) & 0x0F) == 0x05
238 && ((norm >> 9) & 0x07) == 0) {
239 addr = (norm >> 13) & 0x0FFFFF;
240 addr |= ((uint32_t)(norm >> 36) & 1) << 20;
241 addr <<= 4;
242 addr -= s->pos + (uint32_t)i;
243 addr >>= 4;
244
245 norm &= ~((uint64_t)0x8FFFFF << 13);
246 norm |= (uint64_t)(addr & 0x0FFFFF) << 13;
247 norm |= (uint64_t)(addr & 0x100000)
248 << (36 - 20);
249
250 instr &= (1 << bit_res) - 1;
251 instr |= norm << bit_res;
252
253 for (j = 0; j < 6; j++)
254 buf[i + j + byte_pos]
255 = (uint8_t)(instr >> (8 * j));
256 }
257 }
258 }
259
260 return i;
261}
262#endif
263
264#ifdef XZ_DEC_ARM
265static size_t bcj_arm(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
266{
267 size_t i;
268 uint32_t addr;
269
270 for (i = 0; i + 4 <= size; i += 4) {
271 if (buf[i + 3] == 0xEB) {
272 addr = (uint32_t)buf[i] | ((uint32_t)buf[i + 1] << 8)
273 | ((uint32_t)buf[i + 2] << 16);
274 addr <<= 2;
275 addr -= s->pos + (uint32_t)i + 8;
276 addr >>= 2;
277 buf[i] = (uint8_t)addr;
278 buf[i + 1] = (uint8_t)(addr >> 8);
279 buf[i + 2] = (uint8_t)(addr >> 16);
280 }
281 }
282
283 return i;
284}
285#endif
286
287#ifdef XZ_DEC_ARMTHUMB
288static size_t bcj_armthumb(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
289{
290 size_t i;
291 uint32_t addr;
292
293 for (i = 0; i + 4 <= size; i += 2) {
294 if ((buf[i + 1] & 0xF8) == 0xF0
295 && (buf[i + 3] & 0xF8) == 0xF8) {
296 addr = (((uint32_t)buf[i + 1] & 0x07) << 19)
297 | ((uint32_t)buf[i] << 11)
298 | (((uint32_t)buf[i + 3] & 0x07) << 8)
299 | (uint32_t)buf[i + 2];
300 addr <<= 1;
301 addr -= s->pos + (uint32_t)i + 4;
302 addr >>= 1;
303 buf[i + 1] = (uint8_t)(0xF0 | ((addr >> 19) & 0x07));
304 buf[i] = (uint8_t)(addr >> 11);
305 buf[i + 3] = (uint8_t)(0xF8 | ((addr >> 8) & 0x07));
306 buf[i + 2] = (uint8_t)addr;
307 i += 2;
308 }
309 }
310
311 return i;
312}
313#endif
314
315#ifdef XZ_DEC_SPARC
316static size_t bcj_sparc(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
317{
318 size_t i;
319 uint32_t instr;
320
321 for (i = 0; i + 4 <= size; i += 4) {
322 instr = get_unaligned_be32(buf + i);
323 if ((instr >> 22) == 0x100 || (instr >> 22) == 0x1FF) {
324 instr <<= 2;
325 instr -= s->pos + (uint32_t)i;
326 instr >>= 2;
327 instr = ((uint32_t)0x40000000 - (instr & 0x400000))
328 | 0x40000000 | (instr & 0x3FFFFF);
329 put_unaligned_be32(instr, buf + i);
330 }
331 }
332
333 return i;
334}
335#endif
336
337
338
339
340
341
342
343
344
345static void bcj_apply(struct xz_dec_bcj *s,
346 uint8_t *buf, size_t *pos, size_t size)
347{
348 size_t filtered;
349
350 buf += *pos;
351 size -= *pos;
352
353 switch (s->type) {
354#ifdef XZ_DEC_X86
355 case BCJ_X86:
356 filtered = bcj_x86(s, buf, size);
357 break;
358#endif
359#ifdef XZ_DEC_POWERPC
360 case BCJ_POWERPC:
361 filtered = bcj_powerpc(s, buf, size);
362 break;
363#endif
364#ifdef XZ_DEC_IA64
365 case BCJ_IA64:
366 filtered = bcj_ia64(s, buf, size);
367 break;
368#endif
369#ifdef XZ_DEC_ARM
370 case BCJ_ARM:
371 filtered = bcj_arm(s, buf, size);
372 break;
373#endif
374#ifdef XZ_DEC_ARMTHUMB
375 case BCJ_ARMTHUMB:
376 filtered = bcj_armthumb(s, buf, size);
377 break;
378#endif
379#ifdef XZ_DEC_SPARC
380 case BCJ_SPARC:
381 filtered = bcj_sparc(s, buf, size);
382 break;
383#endif
384 default:
385
386 filtered = 0;
387 break;
388 }
389
390 *pos += filtered;
391 s->pos += filtered;
392}
393
394
395
396
397
398
399static void bcj_flush(struct xz_dec_bcj *s, struct xz_buf *b)
400{
401 size_t copy_size;
402
403 copy_size = min_t(size_t, s->temp.filtered, b->out_size - b->out_pos);
404 memcpy(b->out + b->out_pos, s->temp.buf, copy_size);
405 b->out_pos += copy_size;
406
407 s->temp.filtered -= copy_size;
408 s->temp.size -= copy_size;
409 memmove(s->temp.buf, s->temp.buf + copy_size, s->temp.size);
410}
411
412
413
414
415
416
417XZ_EXTERN enum xz_ret xz_dec_bcj_run(struct xz_dec_bcj *s,
418 struct xz_dec_lzma2 *lzma2,
419 struct xz_buf *b)
420{
421 size_t out_start;
422
423
424
425
426
427
428 if (s->temp.filtered > 0) {
429 bcj_flush(s, b);
430 if (s->temp.filtered > 0)
431 return XZ_OK;
432
433 if (s->ret == XZ_STREAM_END)
434 return XZ_STREAM_END;
435 }
436
437
438
439
440
441
442
443
444
445
446
447
448
449 if (s->temp.size < b->out_size - b->out_pos || s->temp.size == 0) {
450 out_start = b->out_pos;
451 memcpy(b->out + b->out_pos, s->temp.buf, s->temp.size);
452 b->out_pos += s->temp.size;
453
454 s->ret = xz_dec_lzma2_run(lzma2, b);
455 if (s->ret != XZ_STREAM_END
456 && (s->ret != XZ_OK || s->single_call))
457 return s->ret;
458
459 bcj_apply(s, b->out, &out_start, b->out_pos);
460
461
462
463
464
465
466 if (s->ret == XZ_STREAM_END)
467 return XZ_STREAM_END;
468
469 s->temp.size = b->out_pos - out_start;
470 b->out_pos -= s->temp.size;
471 memcpy(s->temp.buf, b->out + b->out_pos, s->temp.size);
472
473
474
475
476
477
478 if (b->out_pos + s->temp.size < b->out_size)
479 return XZ_OK;
480 }
481
482
483
484
485
486
487
488
489
490 if (b->out_pos < b->out_size) {
491
492 s->out = b->out;
493 s->out_pos = b->out_pos;
494 s->out_size = b->out_size;
495 b->out = s->temp.buf;
496 b->out_pos = s->temp.size;
497 b->out_size = sizeof(s->temp.buf);
498
499 s->ret = xz_dec_lzma2_run(lzma2, b);
500
501 s->temp.size = b->out_pos;
502 b->out = s->out;
503 b->out_pos = s->out_pos;
504 b->out_size = s->out_size;
505
506 if (s->ret != XZ_OK && s->ret != XZ_STREAM_END)
507 return s->ret;
508
509 bcj_apply(s, s->temp.buf, &s->temp.filtered, s->temp.size);
510
511
512
513
514
515
516 if (s->ret == XZ_STREAM_END)
517 s->temp.filtered = s->temp.size;
518
519 bcj_flush(s, b);
520 if (s->temp.filtered > 0)
521 return XZ_OK;
522 }
523
524 return s->ret;
525}
526
527XZ_EXTERN struct xz_dec_bcj *xz_dec_bcj_create(bool single_call)
528{
529 struct xz_dec_bcj *s = kmalloc(sizeof(*s), GFP_KERNEL);
530 if (s != NULL)
531 s->single_call = single_call;
532
533 return s;
534}
535
536XZ_EXTERN enum xz_ret xz_dec_bcj_reset(struct xz_dec_bcj *s, uint8_t id)
537{
538 switch (id) {
539#ifdef XZ_DEC_X86
540 case BCJ_X86:
541#endif
542#ifdef XZ_DEC_POWERPC
543 case BCJ_POWERPC:
544#endif
545#ifdef XZ_DEC_IA64
546 case BCJ_IA64:
547#endif
548#ifdef XZ_DEC_ARM
549 case BCJ_ARM:
550#endif
551#ifdef XZ_DEC_ARMTHUMB
552 case BCJ_ARMTHUMB:
553#endif
554#ifdef XZ_DEC_SPARC
555 case BCJ_SPARC:
556#endif
557 break;
558
559 default:
560
561 return XZ_OPTIONS_ERROR;
562 }
563
564 s->type = id;
565 s->ret = XZ_OK;
566 s->pos = 0;
567 s->x86_prev_mask = 0;
568 s->temp.filtered = 0;
569 s->temp.size = 0;
570
571 return XZ_OK;
572}
573
574#endif
575