lib/xz/xz_dec_bcj.c

   1 /*
   2  * Branch/Call/Jump (BCJ) filter decoders
   3  *
   4  * Authors: Lasse Collin <lasse.collin@tukaani.org>
   5  *          Igor Pavlov <http://7-zip.org/>
   6  *
   7  * This file has been put into the public domain.
   8  * You can do whatever you want with this file.
   9  */
  10
  11 #include "xz_private.h"
  12
  13 /*
  14  * The rest of the file is inside this ifdef. It makes things a little more
  15  * convenient when building without support for any BCJ filters.
  16  */
  17 #ifdef XZ_DEC_BCJ
  18
  19 struct xz_dec_bcj {
  20         /* Type of the BCJ filter being used */
  21         enum {
  22                 BCJ_X86 = 4,        /* x86 or x86-64 */
  23                 BCJ_POWERPC = 5,    /* Big endian only */
  24                 BCJ_IA64 = 6,       /* Big or little endian */
  25                 BCJ_ARM = 7,        /* Little endian only */
  26                 BCJ_ARMTHUMB = 8,   /* Little endian only */
  27                 BCJ_SPARC = 9       /* Big or little endian */
  28         } type;
  29
  30         /*
  31          * Return value of the next filter in the chain. We need to preserve
  32          * this information across calls, because we must not call the next
  33          * filter anymore once it has returned XZ_STREAM_END.
  34          */
  35         enum xz_ret ret;
  36
  37         /* True if we are operating in single-call mode. */
  38         bool single_call;
  39
  40         /*
  41          * Absolute position relative to the beginning of the uncompressed
  42          * data (in a single .xz Block). We care only about the lowest 32
  43          * bits so this doesn't need to be uint64_t even with big files.
  44          */
  45         uint32_t pos;
  46
  47         /* x86 filter state */
  48         uint32_t x86_prev_mask;
  49
  50         /* Temporary space to hold the variables from struct xz_buf */
  51         uint8_t *out;
  52         size_t out_pos;
  53         size_t out_size;
  54
  55         struct {
  56                 /* Amount of already filtered data in the beginning of buf */
  57                 size_t filtered;
  58
  59                 /* Total amount of data currently stored in buf  */
  60                 size_t size;
  61
  62                 /*
  63                  * Buffer to hold a mix of filtered and unfiltered data. This
  64                  * needs to be big enough to hold Alignment + 2 * Look-ahead:
  65                  *
  66                  * Type         Alignment   Look-ahead
  67                  * x86              1           4
  68                  * PowerPC          4           0
  69                  * IA-64           16           0
  70                  * ARM              4           0
  71                  * ARM-Thumb        2           2
  72                  * SPARC            4           0
  73                  */
  74                 uint8_t buf[16];
  75         } temp;
  76 };
  77
  78 #ifdef XZ_DEC_X86
  79 /*
  80  * This is used to test the most significant byte of a memory address
  81  * in an x86 instruction.
  82  */
  83 static inline int bcj_x86_test_msbyte(uint8_t b)
  84 {
  85         return b == 0x00 || b == 0xFF;
  86 }
  87
  88 static 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
 160 static 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
 181 static 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          * The local variables take a little bit stack space, but it's less
 192          * than what LZMA2 decoder takes, so it doesn't make sense to reduce
 193          * stack usage here without doing that for the LZMA2 decoder too.
 194          */
 195
 196         /* Loop counters */
 197         size_t i;
 198         size_t j;
 199
 200         /* Instruction slot (0, 1, or 2) in the 128-bit instruction word */
 201         uint32_t slot;
 202
 203         /* Bitwise offset of the instruction indicated by slot */
 204         uint32_t bit_pos;
 205
 206         /* bit_pos split into byte and bit parts */
 207         uint32_t byte_pos;
 208         uint32_t bit_res;
 209
 210         /* Address part of an instruction */
 211         uint32_t addr;
 212
 213         /* Mask used to detect which instructions to convert */
 214         uint32_t mask;
 215
 216         /* 41-bit instruction stored somewhere in the lowest 48 bits */
 217         uint64_t instr;
 218
 219         /* Instruction normalized with bit_res for easier manipulation */
 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
 265 static 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
 288 static 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
 316 static 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  * Apply the selected BCJ filter. Update *pos and s->pos to match the amount
 339  * of data that got filtered.
 340  *
 341  * NOTE: This is implemented as a switch statement to avoid using function
 342  * pointers, which could be problematic in the kernel boot code, which must
 343  * avoid pointers to static data (at least on x86).
 344  */
 345 static 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                 /* Never reached but silence compiler warnings. */
 386                 filtered = 0;
 387                 break;
 388         }
 389
 390         *pos += filtered;
 391         s->pos += filtered;
 392 }
 393
 394 /*
 395  * Flush pending filtered data from temp to the output buffer.
 396  * Move the remaining mixture of possibly filtered and unfiltered
 397  * data to the beginning of temp.
 398  */
 399 static 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  * The BCJ filter functions are primitive in sense that they process the
 414  * data in chunks of 1-16 bytes. To hide this issue, this function does
 415  * some buffering.
 416  */
 417 XZ_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          * Flush pending already filtered data to the output buffer. Return
 425          * immediatelly if we couldn't flush everything, or if the next
 426          * filter in the chain had already returned XZ_STREAM_END.
 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          * If we have more output space than what is currently pending in
 439          * temp, copy the unfiltered data from temp to the output buffer
 440          * and try to fill the output buffer by decoding more data from the
 441          * next filter in the chain. Apply the BCJ filter on the new data
 442          * in the output buffer. If everything cannot be filtered, copy it
 443          * to temp and rewind the output buffer position accordingly.
 444          */
 445         if (s->temp.size < b->out_size - b->out_pos) {
 446                 out_start = b->out_pos;
 447                 memcpy(b->out + b->out_pos, s->temp.buf, s->temp.size);
 448                 b->out_pos += s->temp.size;
 449
 450                 s->ret = xz_dec_lzma2_run(lzma2, b);
 451                 if (s->ret != XZ_STREAM_END
 452                                 && (s->ret != XZ_OK || s->single_call))
 453                         return s->ret;
 454
 455                 bcj_apply(s, b->out, &out_start, b->out_pos);
 456
 457                 /*
 458                  * As an exception, if the next filter returned XZ_STREAM_END,
 459                  * we can do that too, since the last few bytes that remain
 460                  * unfiltered are meant to remain unfiltered.
 461                  */
 462                 if (s->ret == XZ_STREAM_END)
 463                         return XZ_STREAM_END;
 464
 465                 s->temp.size = b->out_pos - out_start;
 466                 b->out_pos -= s->temp.size;
 467                 memcpy(s->temp.buf, b->out + b->out_pos, s->temp.size);
 468         }
 469
 470         /*
 471          * If we have unfiltered data in temp, try to fill by decoding more
 472          * data from the next filter. Apply the BCJ filter on temp. Then we
 473          * hopefully can fill the actual output buffer by copying filtered
 474          * data from temp. A mix of filtered and unfiltered data may be left
 475          * in temp; it will be taken care on the next call to this function.
 476          */
 477         if (s->temp.size > 0) {
 478                 /* Make b->out{,_pos,_size} temporarily point to s->temp. */
 479                 s->out = b->out;
 480                 s->out_pos = b->out_pos;
 481                 s->out_size = b->out_size;
 482                 b->out = s->temp.buf;
 483                 b->out_pos = s->temp.size;
 484                 b->out_size = sizeof(s->temp.buf);
 485
 486                 s->ret = xz_dec_lzma2_run(lzma2, b);
 487
 488                 s->temp.size = b->out_pos;
 489                 b->out = s->out;
 490                 b->out_pos = s->out_pos;
 491                 b->out_size = s->out_size;
 492
 493                 if (s->ret != XZ_OK && s->ret != XZ_STREAM_END)
 494                         return s->ret;
 495
 496                 bcj_apply(s, s->temp.buf, &s->temp.filtered, s->temp.size);
 497
 498                 /*
 499                  * If the next filter returned XZ_STREAM_END, we mark that
 500                  * everything is filtered, since the last unfiltered bytes
 501                  * of the stream are meant to be left as is.
 502                  */
 503                 if (s->ret == XZ_STREAM_END)
 504                         s->temp.filtered = s->temp.size;
 505
 506                 bcj_flush(s, b);
 507                 if (s->temp.filtered > 0)
 508                         return XZ_OK;
 509         }
 510
 511         return s->ret;
 512 }
 513
 514 XZ_EXTERN struct xz_dec_bcj *xz_dec_bcj_create(bool single_call)
 515 {
 516         struct xz_dec_bcj *s = kmalloc(sizeof(*s), GFP_KERNEL);
 517         if (s != NULL)
 518                 s->single_call = single_call;
 519
 520         return s;
 521 }
 522
 523 XZ_EXTERN enum xz_ret xz_dec_bcj_reset(struct xz_dec_bcj *s, uint8_t id)
 524 {
 525         switch (id) {
 526 #ifdef XZ_DEC_X86
 527         case BCJ_X86:
 528 #endif
 529 #ifdef XZ_DEC_POWERPC
 530         case BCJ_POWERPC:
 531 #endif
 532 #ifdef XZ_DEC_IA64
 533         case BCJ_IA64:
 534 #endif
 535 #ifdef XZ_DEC_ARM
 536         case BCJ_ARM:
 537 #endif
 538 #ifdef XZ_DEC_ARMTHUMB
 539         case BCJ_ARMTHUMB:
 540 #endif
 541 #ifdef XZ_DEC_SPARC
 542         case BCJ_SPARC:
 543 #endif
 544                 break;
 545
 546         default:
 547                 /* Unsupported Filter ID */
 548                 return XZ_OPTIONS_ERROR;
 549         }
 550
 551         s->type = id;
 552         s->ret = XZ_OK;
 553         s->pos = 0;
 554         s->x86_prev_mask = 0;
 555         s->temp.filtered = 0;
 556         s->temp.size = 0;
 557
 558         return XZ_OK;
 559 }
 560
 561 #endif