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