target/linux/generic-2.6/patches-2.6.30/052-pcomp_lzma_support.patch

   1 --- /dev/null
   2 +++ b/crypto/unlzma.c
   3 @@ -0,0 +1,710 @@
   4 +/*
   5 + * LZMA uncompresion module for pcomp
   6 + * Copyright (C) 2009  Felix Fietkau <nbd@openwrt.org>
   7 + *
   8 + * Based on:
   9 + *  Initial Linux kernel adaptation
  10 + *  Copyright (C) 2006  Alain < alain@knaff.lu >
  11 + *
  12 + *  Based on small lzma deflate implementation/Small range coder
  13 + *  implementation for lzma.
  14 + *  Copyright (C) 2006  Aurelien Jacobs < aurel@gnuage.org >
  15 + *
  16 + *  Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)
  17 + *  Copyright (C) 1999-2005  Igor Pavlov
  18 + *
  19 + * This program is free software; you can redistribute it and/or modify it
  20 + * under the terms of the GNU General Public License version 2 as published
  21 + * by the Free Software Foundation.
  22 + *
  23 + * FIXME: the current implementation assumes that the caller will
  24 + * not free any output buffers until the whole decompression has been
  25 + * completed. This is necessary, because LZMA looks back at old output
  26 + * instead of doing a separate dictionary allocation, which saves RAM.
  27 + */
  28 +
  29 +#include <linux/init.h>
  30 +#include <linux/module.h>
  31 +#include <linux/vmalloc.h>
  32 +#include <linux/interrupt.h>
  33 +#include <linux/mm.h>
  34 +#include <linux/net.h>
  35 +#include <linux/slab.h>
  36 +#include <linux/kthread.h>
  37 +
  38 +#include <crypto/internal/compress.h>
  39 +#include "unlzma.h"
  40 +
  41 +static int instance = 0;
  42 +
  43 +struct unlzma_buffer {
  44 +       struct unlzma_buffer *last;
  45 +       int offset;
  46 +       int size;
  47 +       u8 *ptr;
  48 +};
  49 +
  50 +struct unlzma_ctx {
  51 +       struct task_struct *thread;
  52 +       wait_queue_head_t next_req;
  53 +       struct mutex mutex;
  54 +       bool active;
  55 +       bool cancel;
  56 +
  57 +       const u8 *next_in;
  58 +       int avail_in;
  59 +
  60 +       u8 *next_out;
  61 +       int avail_out;
  62 +
  63 +       /* reader state */
  64 +       u32 code;
  65 +       u32 range;
  66 +       u32 bound;
  67 +
  68 +       /* writer state */
  69 +       u8 previous_byte;
  70 +       ssize_t pos;
  71 +       struct unlzma_buffer *head;
  72 +
  73 +       /* cstate */
  74 +       int state;
  75 +       u32 rep0, rep1, rep2, rep3;
  76 +
  77 +       u32 dict_size;
  78 +
  79 +       void *workspace;
  80 +       int workspace_size;
  81 +};
  82 +
  83 +static inline bool
  84 +unlzma_should_stop(struct unlzma_ctx *ctx)
  85 +{
  86 +       return unlikely(kthread_should_stop() || ctx->cancel);
  87 +}
  88 +
  89 +static void
  90 +unlzma_request_buffer(struct unlzma_ctx *ctx, int *avail)
  91 +{
  92 +       mutex_unlock(&ctx->mutex);
  93 +       wait_event(ctx->next_req, unlzma_should_stop(ctx) || (*avail > 0));
  94 +       mutex_lock(&ctx->mutex);
  95 +}
  96 +
  97 +static u8
  98 +rc_read(struct unlzma_ctx *ctx)
  99 +{
 100 +       if (unlikely(ctx->avail_in <= 0))
 101 +               unlzma_request_buffer(ctx, &ctx->avail_in);
 102 +
 103 +       if (unlzma_should_stop(ctx))
 104 +               return 0;
 105 +
 106 +       ctx->avail_in--;
 107 +       return *(ctx->next_in++);
 108 +}
 109 +
 110 +
 111 +static inline void
 112 +rc_get_code(struct unlzma_ctx *ctx)
 113 +{
 114 +       ctx->code = (ctx->code << 8) | rc_read(ctx);
 115 +}
 116 +
 117 +static void
 118 +rc_normalize(struct unlzma_ctx *ctx)
 119 +{
 120 +       if (ctx->range < (1 << RC_TOP_BITS)) {
 121 +               ctx->range <<= 8;
 122 +               rc_get_code(ctx);
 123 +       }
 124 +}
 125 +
 126 +static int
 127 +rc_is_bit_0(struct unlzma_ctx *ctx, u16 *p)
 128 +{
 129 +       rc_normalize(ctx);
 130 +       ctx->bound = *p * (ctx->range >> RC_MODEL_TOTAL_BITS);
 131 +       return ctx->code < ctx->bound;
 132 +}
 133 +
 134 +static void
 135 +rc_update_bit_0(struct unlzma_ctx *ctx, u16 *p)
 136 +{
 137 +       ctx->range = ctx->bound;
 138 +       *p += ((1 << RC_MODEL_TOTAL_BITS) - *p) >> RC_MOVE_BITS;
 139 +}
 140 +
 141 +static void
 142 +rc_update_bit_1(struct unlzma_ctx *ctx, u16 *p)
 143 +{
 144 +       ctx->range -= ctx->bound;
 145 +       ctx->code -= ctx->bound;
 146 +       *p -= *p >> RC_MOVE_BITS;
 147 +}
 148 +
 149 +static bool
 150 +rc_get_bit(struct unlzma_ctx *ctx, u16 *p, int *symbol)
 151 +{
 152 +       if (rc_is_bit_0(ctx, p)) {
 153 +               rc_update_bit_0(ctx, p);
 154 +               *symbol *= 2;
 155 +               return 0;
 156 +       } else {
 157 +               rc_update_bit_1(ctx, p);
 158 +               *symbol = *symbol * 2 + 1;
 159 +               return 1;
 160 +       }
 161 +}
 162 +
 163 +static int
 164 +rc_direct_bit(struct unlzma_ctx *ctx)
 165 +{
 166 +       rc_normalize(ctx);
 167 +       ctx->range >>= 1;
 168 +       if (ctx->code >= ctx->range) {
 169 +               ctx->code -= ctx->range;
 170 +               return 1;
 171 +       }
 172 +       return 0;
 173 +}
 174 +
 175 +static void
 176 +rc_bit_tree_decode(struct unlzma_ctx *ctx, u16 *p, int num_levels, int *symbol)
 177 +{
 178 +       int i = num_levels;
 179 +
 180 +       *symbol = 1;
 181 +       while (i--)
 182 +               rc_get_bit(ctx, p + *symbol, symbol);
 183 +       *symbol -= 1 << num_levels;
 184 +}
 185 +
 186 +static u8
 187 +peek_old_byte(struct unlzma_ctx *ctx, u32 offs)
 188 +{
 189 +       struct unlzma_buffer *bh = ctx->head;
 190 +       u32 pos;
 191 +
 192 +       pos = ctx->pos - offs;
 193 +       if (pos >= ctx->dict_size) {
 194 +               pos = (~pos % ctx->dict_size);
 195 +       }
 196 +
 197 +       while (bh->offset > pos) {
 198 +               bh = bh->last;
 199 +               if (!bh)
 200 +                       return 0;
 201 +       }
 202 +
 203 +       pos -= bh->offset;
 204 +       if (pos > bh->size)
 205 +               return 0;
 206 +
 207 +       return bh->ptr[pos];
 208 +}
 209 +
 210 +static void
 211 +get_buffer(struct unlzma_ctx *ctx)
 212 +{
 213 +       struct unlzma_buffer *bh;
 214 +
 215 +       bh = kzalloc(sizeof(struct unlzma_buffer), GFP_KERNEL);
 216 +       bh->ptr = ctx->next_out;
 217 +       bh->offset = ctx->pos;
 218 +       bh->last = ctx->head;
 219 +       bh->size = ctx->avail_out;
 220 +       ctx->head = bh;
 221 +}
 222 +
 223 +static void
 224 +write_byte(struct unlzma_ctx *ctx, u8 byte)
 225 +{
 226 +       if (unlikely(ctx->avail_out <= 0)) {
 227 +               unlzma_request_buffer(ctx, &ctx->avail_out);
 228 +               get_buffer(ctx);
 229 +       }
 230 +
 231 +       if (!ctx->avail_out)
 232 +               return;
 233 +
 234 +       ctx->previous_byte = byte;
 235 +       *(ctx->next_out++) = byte;
 236 +       ctx->avail_out--;
 237 +       ctx->pos++;
 238 +}
 239 +
 240 +
 241 +static inline void
 242 +copy_byte(struct unlzma_ctx *ctx, u32 offs)
 243 +{
 244 +       write_byte(ctx, peek_old_byte(ctx, offs));
 245 +}
 246 +
 247 +static void
 248 +copy_bytes(struct unlzma_ctx *ctx, u32 rep0, int len)
 249 +{
 250 +       do {
 251 +               copy_byte(ctx, rep0);
 252 +               len--;
 253 +               if (unlzma_should_stop(ctx))
 254 +                       break;
 255 +       } while (len != 0);
 256 +}
 257 +
 258 +static void
 259 +process_bit0(struct unlzma_ctx *ctx, u16 *p, int pos_state, u16 *prob,
 260 +             int lc, u32 literal_pos_mask)
 261 +{
 262 +       int mi = 1;
 263 +       rc_update_bit_0(ctx, prob);
 264 +       prob = (p + LZMA_LITERAL +
 265 +               (LZMA_LIT_SIZE
 266 +                * (((ctx->pos & literal_pos_mask) << lc)
 267 +                   + (ctx->previous_byte >> (8 - lc))))
 268 +               );
 269 +
 270 +       if (ctx->state >= LZMA_NUM_LIT_STATES) {
 271 +               int match_byte = peek_old_byte(ctx, ctx->rep0);
 272 +               do {
 273 +                       u16 bit;
 274 +                       u16 *prob_lit;
 275 +
 276 +                       match_byte <<= 1;
 277 +                       bit = match_byte & 0x100;
 278 +                       prob_lit = prob + 0x100 + bit + mi;
 279 +                       if (rc_get_bit(ctx, prob_lit, &mi) != !!bit)
 280 +                               break;
 281 +               } while (mi < 0x100);
 282 +       }
 283 +       while (mi < 0x100) {
 284 +               u16 *prob_lit = prob + mi;
 285 +               rc_get_bit(ctx, prob_lit, &mi);
 286 +       }
 287 +       write_byte(ctx, mi);
 288 +       if (ctx->state < 4)
 289 +               ctx->state = 0;
 290 +       else if (ctx->state < 10)
 291 +               ctx->state -= 3;
 292 +       else
 293 +               ctx->state -= 6;
 294 +}
 295 +
 296 +static void
 297 +process_bit1(struct unlzma_ctx *ctx, u16 *p, int pos_state, u16 *prob)
 298 +{
 299 +       int offset;
 300 +       u16 *prob_len;
 301 +       int num_bits;
 302 +       int len;
 303 +
 304 +       rc_update_bit_1(ctx, prob);
 305 +       prob = p + LZMA_IS_REP + ctx->state;
 306 +       if (rc_is_bit_0(ctx, prob)) {
 307 +               rc_update_bit_0(ctx, prob);
 308 +               ctx->rep3 = ctx->rep2;
 309 +               ctx->rep2 = ctx->rep1;
 310 +               ctx->rep1 = ctx->rep0;
 311 +               ctx->state = ctx->state < LZMA_NUM_LIT_STATES ? 0 : 3;
 312 +               prob = p + LZMA_LEN_CODER;
 313 +       } else {
 314 +               rc_update_bit_1(ctx, prob);
 315 +               prob = p + LZMA_IS_REP_G0 + ctx->state;
 316 +               if (rc_is_bit_0(ctx, prob)) {
 317 +                       rc_update_bit_0(ctx, prob);
 318 +                       prob = (p + LZMA_IS_REP_0_LONG
 319 +                               + (ctx->state <<
 320 +                                  LZMA_NUM_POS_BITS_MAX) +
 321 +                               pos_state);
 322 +                       if (rc_is_bit_0(ctx, prob)) {
 323 +                               rc_update_bit_0(ctx, prob);
 324 +
 325 +                               ctx->state = ctx->state < LZMA_NUM_LIT_STATES ?
 326 +                                       9 : 11;
 327 +                               copy_byte(ctx, ctx->rep0);
 328 +                               return;
 329 +                       } else {
 330 +                               rc_update_bit_1(ctx, prob);
 331 +                       }
 332 +               } else {
 333 +                       u32 distance;
 334 +
 335 +                       rc_update_bit_1(ctx, prob);
 336 +                       prob = p + LZMA_IS_REP_G1 + ctx->state;
 337 +                       if (rc_is_bit_0(ctx, prob)) {
 338 +                               rc_update_bit_0(ctx, prob);
 339 +                               distance = ctx->rep1;
 340 +                       } else {
 341 +                               rc_update_bit_1(ctx, prob);
 342 +                               prob = p + LZMA_IS_REP_G2 + ctx->state;
 343 +                               if (rc_is_bit_0(ctx, prob)) {
 344 +                                       rc_update_bit_0(ctx, prob);
 345 +                                       distance = ctx->rep2;
 346 +                               } else {
 347 +                                       rc_update_bit_1(ctx, prob);
 348 +                                       distance = ctx->rep3;
 349 +                                       ctx->rep3 = ctx->rep2;
 350 +                               }
 351 +                               ctx->rep2 = ctx->rep1;
 352 +                       }
 353 +                       ctx->rep1 = ctx->rep0;
 354 +                       ctx->rep0 = distance;
 355 +               }
 356 +               ctx->state = ctx->state < LZMA_NUM_LIT_STATES ? 8 : 11;
 357 +               prob = p + LZMA_REP_LEN_CODER;
 358 +       }
 359 +
 360 +       prob_len = prob + LZMA_LEN_CHOICE;
 361 +       if (rc_is_bit_0(ctx, prob_len)) {
 362 +               rc_update_bit_0(ctx, prob_len);
 363 +               prob_len = (prob + LZMA_LEN_LOW
 364 +                           + (pos_state <<
 365 +                              LZMA_LEN_NUM_LOW_BITS));
 366 +               offset = 0;
 367 +               num_bits = LZMA_LEN_NUM_LOW_BITS;
 368 +       } else {
 369 +               rc_update_bit_1(ctx, prob_len);
 370 +               prob_len = prob + LZMA_LEN_CHOICE_2;
 371 +               if (rc_is_bit_0(ctx, prob_len)) {
 372 +                       rc_update_bit_0(ctx, prob_len);
 373 +                       prob_len = (prob + LZMA_LEN_MID
 374 +                                   + (pos_state <<
 375 +                                      LZMA_LEN_NUM_MID_BITS));
 376 +                       offset = 1 << LZMA_LEN_NUM_LOW_BITS;
 377 +                       num_bits = LZMA_LEN_NUM_MID_BITS;
 378 +               } else {
 379 +                       rc_update_bit_1(ctx, prob_len);
 380 +                       prob_len = prob + LZMA_LEN_HIGH;
 381 +                       offset = ((1 << LZMA_LEN_NUM_LOW_BITS)
 382 +                                 + (1 << LZMA_LEN_NUM_MID_BITS));
 383 +                       num_bits = LZMA_LEN_NUM_HIGH_BITS;
 384 +               }
 385 +       }
 386 +
 387 +       rc_bit_tree_decode(ctx, prob_len, num_bits, &len);
 388 +       len += offset;
 389 +
 390 +       if (ctx->state < 4) {
 391 +               int pos_slot;
 392 +
 393 +               ctx->state += LZMA_NUM_LIT_STATES;
 394 +               prob =
 395 +                       p + LZMA_POS_SLOT +
 396 +                       ((len <
 397 +                         LZMA_NUM_LEN_TO_POS_STATES ? len :
 398 +                         LZMA_NUM_LEN_TO_POS_STATES - 1)
 399 +                        << LZMA_NUM_POS_SLOT_BITS);
 400 +               rc_bit_tree_decode(ctx, prob,
 401 +                                  LZMA_NUM_POS_SLOT_BITS,
 402 +                                  &pos_slot);
 403 +               if (pos_slot >= LZMA_START_POS_MODEL_INDEX) {
 404 +                       int i, mi;
 405 +                       num_bits = (pos_slot >> 1) - 1;
 406 +                       ctx->rep0 = 2 | (pos_slot & 1);
 407 +                       if (pos_slot < LZMA_END_POS_MODEL_INDEX) {
 408 +                               ctx->rep0 <<= num_bits;
 409 +                               prob = p + LZMA_SPEC_POS +
 410 +                                       ctx->rep0 - pos_slot - 1;
 411 +                       } else {
 412 +                               num_bits -= LZMA_NUM_ALIGN_BITS;
 413 +                               while (num_bits--)
 414 +                                       ctx->rep0 = (ctx->rep0 << 1) |
 415 +                                               rc_direct_bit(ctx);
 416 +                               prob = p + LZMA_ALIGN;
 417 +                               ctx->rep0 <<= LZMA_NUM_ALIGN_BITS;
 418 +                               num_bits = LZMA_NUM_ALIGN_BITS;
 419 +                       }
 420 +                       i = 1;
 421 +                       mi = 1;
 422 +                       while (num_bits--) {
 423 +                               if (rc_get_bit(ctx, prob + mi, &mi))
 424 +                                       ctx->rep0 |= i;
 425 +                               i <<= 1;
 426 +                       }
 427 +               } else
 428 +                       ctx->rep0 = pos_slot;
 429 +               if (++(ctx->rep0) == 0)
 430 +                       return;
 431 +       }
 432 +
 433 +       len += LZMA_MATCH_MIN_LEN;
 434 +
 435 +       copy_bytes(ctx, ctx->rep0, len);
 436 +}
 437 +
 438 +
 439 +static int
 440 +do_unlzma(struct unlzma_ctx *ctx)
 441 +{
 442 +       u8 hdr_buf[sizeof(struct lzma_header)];
 443 +       struct lzma_header *header = (struct lzma_header *)hdr_buf;
 444 +       u32 pos_state_mask;
 445 +       u32 literal_pos_mask;
 446 +       int lc, pb, lp;
 447 +       int num_probs;
 448 +       int i, mi;
 449 +       u16 *p;
 450 +
 451 +       for (i = 0; i < sizeof(struct lzma_header); i++) {
 452 +               hdr_buf[i] = rc_read(ctx);
 453 +       }
 454 +
 455 +       ctx->pos = 0;
 456 +       get_buffer(ctx);
 457 +       ctx->active = true;
 458 +       ctx->state = 0;
 459 +       ctx->rep0 = ctx->rep1 = ctx->rep2 = ctx->rep3 = 1;
 460 +
 461 +       ctx->previous_byte = 0;
 462 +       ctx->code = 0;
 463 +       ctx->range = 0xFFFFFFFF;
 464 +
 465 +       ctx->dict_size = le32_to_cpu(header->dict_size);
 466 +
 467 +       if (header->pos >= (9 * 5 * 5))
 468 +               return -1;
 469 +
 470 +       mi = 0;
 471 +       lc = header->pos;
 472 +       while (lc >= 9) {
 473 +               mi++;
 474 +               lc -= 9;
 475 +       }
 476 +       pb = 0;
 477 +       lp = mi;
 478 +       while (lp >= 5) {
 479 +               pb++;
 480 +               lp -= 5;
 481 +       }
 482 +       pos_state_mask = (1 << pb) - 1;
 483 +       literal_pos_mask = (1 << lp) - 1;
 484 +
 485 +       if (ctx->dict_size == 0)
 486 +               ctx->dict_size = 1;
 487 +
 488 +       num_probs = LZMA_BASE_SIZE + (LZMA_LIT_SIZE << (lc + lp));
 489 +       if (ctx->workspace_size < num_probs * sizeof(*p)) {
 490 +               if (ctx->workspace)
 491 +                       vfree(ctx->workspace);
 492 +               ctx->workspace = vmalloc(num_probs * sizeof(*p));
 493 +       }
 494 +       p = (u16 *) ctx->workspace;
 495 +       if (!p)
 496 +               return -1;
 497 +
 498 +       num_probs = LZMA_LITERAL + (LZMA_LIT_SIZE << (lc + lp));
 499 +       for (i = 0; i < num_probs; i++)
 500 +               p[i] = (1 << RC_MODEL_TOTAL_BITS) >> 1;
 501 +
 502 +       for (i = 0; i < 5; i++)
 503 +               rc_get_code(ctx);
 504 +
 505 +       while (1) {
 506 +               int pos_state = ctx->pos & pos_state_mask;
 507 +               u16 *prob = p + LZMA_IS_MATCH +
 508 +                       (ctx->state << LZMA_NUM_POS_BITS_MAX) + pos_state;
 509 +               if (rc_is_bit_0(ctx, prob))
 510 +                       process_bit0(ctx, p, pos_state, prob,
 511 +                                    lc, literal_pos_mask);
 512 +               else {
 513 +                       process_bit1(ctx, p, pos_state, prob);
 514 +                       if (ctx->rep0 == 0)
 515 +                               break;
 516 +               }
 517 +               if (unlzma_should_stop(ctx))
 518 +                       break;
 519 +       }
 520 +
 521 +       return ctx->pos;
 522 +}
 523 +
 524 +
 525 +static void
 526 +unlzma_reset_buf(struct unlzma_ctx *ctx)
 527 +{
 528 +       ctx->avail_in = 0;
 529 +       ctx->next_in = NULL;
 530 +       ctx->avail_out = 0;
 531 +       ctx->next_out = NULL;
 532 +}
 533 +
 534 +static int
 535 +unlzma_thread(void *data)
 536 +{
 537 +       struct unlzma_ctx *ctx = data;
 538 +
 539 +       mutex_lock(&ctx->mutex);
 540 +       do {
 541 +               if (do_unlzma(ctx) < 0)
 542 +                       ctx->pos = 0;
 543 +               unlzma_reset_buf(ctx);
 544 +               ctx->cancel = false;
 545 +               ctx->active = false;
 546 +               while (ctx->head) {
 547 +                       struct unlzma_buffer *bh = ctx->head;
 548 +                       ctx->head = bh->last;
 549 +                       kfree(bh);
 550 +               }
 551 +       } while (!kthread_should_stop());
 552 +       mutex_unlock(&ctx->mutex);
 553 +       return 0;
 554 +}
 555 +
 556 +
 557 +static int
 558 +unlzma_init(struct crypto_tfm *tfm)
 559 +{
 560 +       return 0;
 561 +}
 562 +
 563 +static void
 564 +unlzma_cancel(struct unlzma_ctx *ctx)
 565 +{
 566 +       unlzma_reset_buf(ctx);
 567 +
 568 +       if (!ctx->active)
 569 +               return;
 570 +
 571 +       ctx->cancel = true;
 572 +       do {
 573 +               mutex_unlock(&ctx->mutex);
 574 +               wake_up(&ctx->next_req);
 575 +               schedule();
 576 +               mutex_lock(&ctx->mutex);
 577 +       } while (ctx->cancel);
 578 +}
 579 +
 580 +
 581 +static void
 582 +unlzma_exit(struct crypto_tfm *tfm)
 583 +{
 584 +       struct unlzma_ctx *ctx = crypto_tfm_ctx(tfm);
 585 +
 586 +       if (ctx->thread) {
 587 +               unlzma_cancel(ctx);
 588 +               kthread_stop(ctx->thread);
 589 +               ctx->thread = NULL;
 590 +       }
 591 +}
 592 +
 593 +static int
 594 +unlzma_decompress_setup(struct crypto_pcomp *tfm, void *p, unsigned int len)
 595 +{
 596 +       struct unlzma_ctx *ctx = crypto_tfm_ctx(crypto_pcomp_tfm(tfm));
 597 +       int ret = 0;
 598 +
 599 +       if (ctx->thread)
 600 +               return 0;
 601 +
 602 +       mutex_init(&ctx->mutex);
 603 +       init_waitqueue_head(&ctx->next_req);
 604 +       ctx->thread = kthread_run(unlzma_thread, ctx, "unlzma/%d", instance++);
 605 +       if (IS_ERR(ctx->thread)) {
 606 +               ret = PTR_ERR(ctx->thread);
 607 +               ctx->thread = NULL;
 608 +       }
 609 +
 610 +       return ret;
 611 +}
 612 +
 613 +static int
 614 +unlzma_decompress_init(struct crypto_pcomp *tfm)
 615 +{
 616 +       struct unlzma_ctx *ctx = crypto_tfm_ctx(crypto_pcomp_tfm(tfm));
 617 +
 618 +       ctx->pos = 0;
 619 +       return 0;
 620 +}
 621 +
 622 +static void
 623 +unlzma_wait_complete(struct unlzma_ctx *ctx, bool finish)
 624 +{
 625 +       do {
 626 +               mutex_unlock(&ctx->mutex);
 627 +               wake_up(&ctx->next_req);
 628 +               schedule();
 629 +               mutex_lock(&ctx->mutex);
 630 +       } while (ctx->active && (ctx->avail_in > 0) && (ctx->avail_out > 0));
 631 +}
 632 +
 633 +static int
 634 +unlzma_decompress_update(struct crypto_pcomp *tfm, struct comp_request *req)
 635 +{
 636 +       struct unlzma_ctx *ctx = crypto_tfm_ctx(crypto_pcomp_tfm(tfm));
 637 +       size_t pos = 0;
 638 +
 639 +       mutex_lock(&ctx->mutex);
 640 +       if (!ctx->active && !req->avail_in)
 641 +               goto out;
 642 +
 643 +       pos = ctx->pos;
 644 +       ctx->next_in = req->next_in;
 645 +       ctx->avail_in = req->avail_in;
 646 +       ctx->next_out = req->next_out;
 647 +       ctx->avail_out = req->avail_out;
 648 +
 649 +       unlzma_wait_complete(ctx, false);
 650 +
 651 +       req->next_in = ctx->next_in;
 652 +       req->avail_in = ctx->avail_in;
 653 +       req->next_out = ctx->next_out;
 654 +       req->avail_out = ctx->avail_out;
 655 +       pos = ctx->pos - pos;
 656 +
 657 +out:
 658 +       mutex_unlock(&ctx->mutex);
 659 +       return pos;
 660 +}
 661 +
 662 +static int
 663 +unlzma_decompress_final(struct crypto_pcomp *tfm, struct comp_request *req)
 664 +{
 665 +       struct unlzma_ctx *ctx = crypto_tfm_ctx(crypto_pcomp_tfm(tfm));
 666 +       int ret = 0;
 667 +
 668 +       /* cancel pending operation */
 669 +       mutex_lock(&ctx->mutex);
 670 +       if (ctx->active) {
 671 +               // ret = -EINVAL;
 672 +               unlzma_cancel(ctx);
 673 +       }
 674 +       ctx->pos = 0;
 675 +       mutex_unlock(&ctx->mutex);
 676 +       return ret;
 677 +}
 678 +
 679 +
 680 +static struct pcomp_alg unlzma_alg = {
 681 +       .decompress_setup       = unlzma_decompress_setup,
 682 +       .decompress_init        = unlzma_decompress_init,
 683 +       .decompress_update      = unlzma_decompress_update,
 684 +       .decompress_final       = unlzma_decompress_final,
 685 +
 686 +       .base                   = {
 687 +               .cra_name       = "lzma",
 688 +               .cra_flags      = CRYPTO_ALG_TYPE_PCOMPRESS,
 689 +               .cra_ctxsize    = sizeof(struct unlzma_ctx),
 690 +               .cra_module     = THIS_MODULE,
 691 +               .cra_init       = unlzma_init,
 692 +               .cra_exit       = unlzma_exit,
 693 +       }
 694 +};
 695 +
 696 +static int __init
 697 +unlzma_mod_init(void)
 698 +{
 699 +       return crypto_register_pcomp(&unlzma_alg);
 700 +}
 701 +
 702 +static void __exit
 703 +unlzma_mod_exit(void)
 704 +{
 705 +       crypto_unregister_pcomp(&unlzma_alg);
 706 +}
 707 +
 708 +module_init(unlzma_mod_init);
 709 +module_exit(unlzma_mod_exit);
 710 +
 711 +MODULE_LICENSE("GPL");
 712 +MODULE_DESCRIPTION("LZMA Decompression Algorithm");
 713 +MODULE_AUTHOR("Felix Fietkau <nbd@openwrt.org>");
 714 --- a/crypto/Kconfig
 715 +++ b/crypto/Kconfig
 716 @@ -758,6 +758,12 @@ config CRYPTO_ZLIB
 717         help
 718           This is the zlib algorithm.
 719
 720 +config CRYPTO_UNLZMA
 721 +       tristate "LZMA decompression"
 722 +       select CRYPTO_PCOMP
 723 +       help
 724 +         This is the lzma decompression module.
 725 +
 726  config CRYPTO_LZO
 727         tristate "LZO compression algorithm"
 728         select CRYPTO_ALGAPI
 729 --- a/crypto/Makefile
 730 +++ b/crypto/Makefile
 731 @@ -75,6 +75,7 @@ obj-$(CONFIG_CRYPTO_SEED) += seed.o
 732  obj-$(CONFIG_CRYPTO_SALSA20) += salsa20_generic.o
 733  obj-$(CONFIG_CRYPTO_DEFLATE) += deflate.o
 734  obj-$(CONFIG_CRYPTO_ZLIB) += zlib.o
 735 +obj-$(CONFIG_CRYPTO_UNLZMA) += unlzma.o
 736  obj-$(CONFIG_CRYPTO_MICHAEL_MIC) += michael_mic.o
 737  obj-$(CONFIG_CRYPTO_CRC32C) += crc32c.o
 738  obj-$(CONFIG_CRYPTO_AUTHENC) += authenc.o
 739 --- /dev/null
 740 +++ b/crypto/unlzma.h
 741 @@ -0,0 +1,80 @@
 742 +/* LZMA uncompresion module for pcomp
 743 + * Copyright (C) 2009  Felix Fietkau <nbd@openwrt.org>
 744 + *
 745 + * Based on:
 746 + *  Initial Linux kernel adaptation
 747 + *  Copyright (C) 2006  Alain < alain@knaff.lu >
 748 + *
 749 + *  Based on small lzma deflate implementation/Small range coder
 750 + *  implementation for lzma.
 751 + *  Copyright (C) 2006  Aurelien Jacobs < aurel@gnuage.org >
 752 + *
 753 + *  Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)
 754 + *  Copyright (C) 1999-2005  Igor Pavlov
 755 + *
 756 + * This program is free software; you can redistribute it and/or modify it
 757 + * under the terms of the GNU General Public License version 2 as published
 758 + * by the Free Software Foundation.
 759 + */
 760 +#ifndef __UNLZMA_H
 761 +#define __UNLZMA_H
 762 +
 763 +struct lzma_header {
 764 +       __u8 pos;
 765 +       __le32 dict_size;
 766 +} __attribute__ ((packed)) ;
 767 +
 768 +
 769 +#define RC_TOP_BITS 24
 770 +#define RC_MOVE_BITS 5
 771 +#define RC_MODEL_TOTAL_BITS 11
 772 +
 773 +#define LZMA_BASE_SIZE 1846
 774 +#define LZMA_LIT_SIZE 768
 775 +
 776 +#define LZMA_NUM_POS_BITS_MAX 4
 777 +
 778 +#define LZMA_LEN_NUM_LOW_BITS 3
 779 +#define LZMA_LEN_NUM_MID_BITS 3
 780 +#define LZMA_LEN_NUM_HIGH_BITS 8
 781 +
 782 +#define LZMA_LEN_CHOICE 0
 783 +#define LZMA_LEN_CHOICE_2 (LZMA_LEN_CHOICE + 1)
 784 +#define LZMA_LEN_LOW (LZMA_LEN_CHOICE_2 + 1)
 785 +#define LZMA_LEN_MID (LZMA_LEN_LOW \
 786 +                     + (1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_LOW_BITS)))
 787 +#define LZMA_LEN_HIGH (LZMA_LEN_MID \
 788 +                      +(1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_MID_BITS)))
 789 +#define LZMA_NUM_LEN_PROBS (LZMA_LEN_HIGH + (1 << LZMA_LEN_NUM_HIGH_BITS))
 790 +
 791 +#define LZMA_NUM_STATES 12
 792 +#define LZMA_NUM_LIT_STATES 7
 793 +
 794 +#define LZMA_START_POS_MODEL_INDEX 4
 795 +#define LZMA_END_POS_MODEL_INDEX 14
 796 +#define LZMA_NUM_FULL_DISTANCES (1 << (LZMA_END_POS_MODEL_INDEX >> 1))
 797 +
 798 +#define LZMA_NUM_POS_SLOT_BITS 6
 799 +#define LZMA_NUM_LEN_TO_POS_STATES 4
 800 +
 801 +#define LZMA_NUM_ALIGN_BITS 4
 802 +
 803 +#define LZMA_MATCH_MIN_LEN 2
 804 +
 805 +#define LZMA_IS_MATCH 0
 806 +#define LZMA_IS_REP (LZMA_IS_MATCH + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX))
 807 +#define LZMA_IS_REP_G0 (LZMA_IS_REP + LZMA_NUM_STATES)
 808 +#define LZMA_IS_REP_G1 (LZMA_IS_REP_G0 + LZMA_NUM_STATES)
 809 +#define LZMA_IS_REP_G2 (LZMA_IS_REP_G1 + LZMA_NUM_STATES)
 810 +#define LZMA_IS_REP_0_LONG (LZMA_IS_REP_G2 + LZMA_NUM_STATES)
 811 +#define LZMA_POS_SLOT (LZMA_IS_REP_0_LONG \
 812 +                      + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX))
 813 +#define LZMA_SPEC_POS (LZMA_POS_SLOT \
 814 +                      +(LZMA_NUM_LEN_TO_POS_STATES << LZMA_NUM_POS_SLOT_BITS))
 815 +#define LZMA_ALIGN (LZMA_SPEC_POS \
 816 +                   + LZMA_NUM_FULL_DISTANCES - LZMA_END_POS_MODEL_INDEX)
 817 +#define LZMA_LEN_CODER (LZMA_ALIGN + (1 << LZMA_NUM_ALIGN_BITS))
 818 +#define LZMA_REP_LEN_CODER (LZMA_LEN_CODER + LZMA_NUM_LEN_PROBS)
 819 +#define LZMA_LITERAL (LZMA_REP_LEN_CODER + LZMA_NUM_LEN_PROBS)
 820 +
 821 +#endif