2 * Cryptoapi LZF compression module.
4 * Copyright (c) 2004-2005 Nigel Cunningham <nigel@suspend2.net>
6 * based on the deflate.c file:
8 * Copyright (c) 2003 James Morris <jmorris@intercode.com.au>
10 * and upon the LZF compression module donated to the Suspend2 project with
11 * the following copyright:
13 * This program is free software; you can redistribute it and/or modify it
14 * under the terms of the GNU General Public License as published by the Free
15 * Software Foundation; either version 2 of the License, or (at your option)
17 * Copyright (c) 2000-2003 Marc Alexander Lehmann <pcg@goof.com>
19 * Redistribution and use in source and binary forms, with or without modifica-
20 * tion, are permitted provided that the following conditions are met:
22 * 1. Redistributions of source code must retain the above copyright notice,
23 * this list of conditions and the following disclaimer.
25 * 2. Redistributions in binary form must reproduce the above copyright
26 * notice, this list of conditions and the following disclaimer in the
27 * documentation and/or other materials provided with the distribution.
29 * 3. The name of the author may not be used to endorse or promote products
30 * derived from this software without specific prior written permission.
32 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
33 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MER-
34 * CHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
35 * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE-
36 * CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
37 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
38 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
39 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH-
40 * ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
41 * OF THE POSSIBILITY OF SUCH DAMAGE.
43 * Alternatively, the contents of this file may be used under the terms of
44 * the GNU General Public License version 2 (the "GPL"), in which case the
45 * provisions of the GPL are applicable instead of the above. If you wish to
46 * allow the use of your version of this file only under the terms of the
47 * GPL and not to allow others to use your version of this file under the
48 * BSD license, indicate your decision by deleting the provisions above and
49 * replace them with the notice and other provisions required by the GPL. If
50 * you do not delete the provisions above, a recipient may use your version
51 * of this file under either the BSD or the GPL.
54 #include <linux/kernel.h>
55 #include <linux/module.h>
56 #include <linux/init.h>
57 #include <linux/module.h>
58 #include <linux/crypto.h>
59 #include <linux/err.h>
60 #include <linux/vmalloc.h>
61 #include <asm/string.h>
69 * size of hashtable is (1 << hlog) * sizeof (char *)
70 * decompression is independent of the hash table size
71 * the difference between 15 and 14 is very small
72 * for small blocks (and 14 is also faster).
73 * For a low-memory configuration, use hlog == 13;
74 * For best compression, use 15 or 16.
76 static const int hlog
= 14;
79 * don't play with this unless you benchmark!
80 * decompression is not dependent on the hash function
81 * the hashing function might seem strange, just believe me
84 static inline u16
first(const u8
*p
)
86 return ((p
[0]) << 8) + p
[1];
89 static inline u16
next(u8 v
, const u8
*p
)
91 return ((v
) << 8) + p
[2];
94 static inline u32
idx(unsigned int h
)
96 return (((h
^ (h
<< 5)) >> (3*8 - hlog
)) + h
*3) & ((1 << hlog
) - 1);
100 * IDX works because it is very similar to a multiplicative hash, e.g.
101 * (h * 57321 >> (3*8 - hlog))
102 * the next one is also quite good, albeit slow ;)
103 * (int)(cos(h & 0xffffff) * 1e6)
106 static const int max_lit
= (1 << 5);
107 static const int max_off
= (1 << 13);
108 static const int max_ref
= ((1 << 8) + (1 << 3));
113 * 000LLLLL <L+1> ; literal
114 * LLLOOOOO oooooooo ; backref L
115 * 111OOOOO LLLLLLLL oooooooo ; backref L+7
119 static void lzf_compress_exit(struct crypto_tfm
*tfm
)
121 struct lzf_ctx
*ctx
= crypto_tfm_ctx(tfm
);
130 static int lzf_compress_init(struct crypto_tfm
*tfm
)
132 struct lzf_ctx
*ctx
= crypto_tfm_ctx(tfm
);
134 /* Get LZF ready to go */
135 ctx
->hbuf
= vmalloc_32((1 << hlog
) * sizeof(char *));
139 printk(KERN_WARNING
"Failed to allocate %ld bytes for lzf workspace\n",
140 (long) ((1 << hlog
) * sizeof(char *)));
144 static int lzf_compress(struct crypto_tfm
*tfm
, const u8
*in_data
,
145 unsigned int in_len
, u8
*out_data
, unsigned int *out_len
)
147 struct lzf_ctx
*ctx
= crypto_tfm_ctx(tfm
);
148 const u8
**htab
= ctx
->hbuf
;
150 const u8
*ip
= in_data
;
152 const u8
*in_end
= ip
+ in_len
;
153 u8
*out_end
= op
+ *out_len
- 3;
156 unsigned int hval
= first(ip
);
160 memset(htab
, 0, sizeof(htab
));
163 if (ip
< in_end
- 2) {
164 hval
= next(hval
, ip
);
165 hslot
= htab
+ idx(hval
);
169 if ((off
= ip
- ref
- 1) < max_off
170 && ip
+ 4 < in_end
&& ref
> in_data
171 && *(u16
*) ref
== *(u16
*) ip
&& ref
[2] == ip
[2]
173 /* match found at *ref++ */
174 unsigned int len
= 2;
175 unsigned int maxlen
= in_end
- ip
- len
;
176 maxlen
= maxlen
> max_ref
? max_ref
: maxlen
;
180 while (len
< maxlen
&& ref
[len
] == ip
[len
]);
182 if (op
+ lit
+ 1 + 3 >= out_end
) {
183 *out_len
= PAGE_SIZE
;
199 *op
++ = (off
>> 8) + (len
<< 5);
201 *op
++ = (off
>> 8) + (7 << 5);
209 hval
= next(hval
, ip
);
210 htab
[idx(hval
)] = ip
;
214 } else if (ip
== in_end
)
217 /* one more literal byte we must copy */
221 if (lit
== max_lit
) {
222 if (op
+ 1 + max_lit
>= out_end
) {
223 *out_len
= PAGE_SIZE
;
228 memcpy(op
, ip
- max_lit
, max_lit
);
235 if (op
+ lit
+ 1 >= out_end
) {
236 *out_len
= PAGE_SIZE
;
247 *out_len
= op
- out_data
;
251 static int lzf_decompress(struct crypto_tfm
*tfm
, const u8
*src
,
252 unsigned int slen
, u8
*dst
, unsigned int *dlen
)
256 u8
const *const in_end
= ip
+ slen
;
257 u8
*const out_end
= op
+ *dlen
;
261 unsigned int ctrl
= *ip
++;
263 if (ctrl
< (1 << 5)) { /* literal run */
266 if (op
+ ctrl
> out_end
)
268 memcpy(op
, ip
, ctrl
);
271 } else { /* back reference */
273 unsigned int len
= ctrl
>> 5;
275 u8
*ref
= op
- ((ctrl
& 0x1f) << 8) - 1;
283 if (op
+ len
> out_end
|| ref
< (u8
*) dst
)
291 while (op
< out_end
&& ip
< in_end
);
293 *dlen
= op
- (u8
*) dst
;
297 static struct crypto_alg alg
= {
299 .cra_flags
= CRYPTO_ALG_TYPE_COMPRESS
,
301 .cra_module
= THIS_MODULE
,
302 .cra_list
= LIST_HEAD_INIT(alg
.cra_list
),
303 .cra_init
= lzf_compress_init
,
304 .cra_exit
= lzf_compress_exit
,
305 .cra_u
= { .compress
= {
306 .coa_compress
= lzf_compress
,
307 .coa_decompress
= lzf_decompress
} }
310 static int __init
init(void)
312 return crypto_register_alg(&alg
);
315 static void __exit
fini(void)
317 crypto_unregister_alg(&alg
);
323 MODULE_LICENSE("GPL");
324 MODULE_DESCRIPTION("LZF Compression Algorithm");
325 MODULE_AUTHOR("Marc Alexander Lehmann & Nigel Cunningham");