Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * JFFS2 -- Journalling Flash File System, Version 2. | |
3 | * | |
c00c310e | 4 | * Copyright © 2001-2007 Red Hat, Inc. |
6088c058 | 5 | * Copyright © 2004-2010 David Woodhouse <dwmw2@infradead.org> |
1da177e4 LT |
6 | * |
7 | * Created by Arjan van de Ven <arjanv@redhat.com> | |
8 | * | |
9 | * For licensing information, see the file 'LICENCE' in this directory. | |
10 | * | |
1da177e4 LT |
11 | * |
12 | * | |
13 | * Very simple lz77-ish encoder. | |
14 | * | |
15 | * Theory of operation: Both encoder and decoder have a list of "last | |
16 | * occurrences" for every possible source-value; after sending the | |
17 | * first source-byte, the second byte indicated the "run" length of | |
18 | * matches | |
19 | * | |
20 | * The algorithm is intended to only send "whole bytes", no bit-messing. | |
21 | * | |
22 | */ | |
23 | ||
24 | #include <linux/kernel.h> | |
25 | #include <linux/types.h> | |
26 | #include <linux/errno.h> | |
182ec4ee TG |
27 | #include <linux/string.h> |
28 | #include <linux/jffs2.h> | |
1da177e4 LT |
29 | #include "compr.h" |
30 | ||
31 | /* _compress returns the compressed size, -1 if bigger */ | |
32 | static int jffs2_rtime_compress(unsigned char *data_in, | |
33 | unsigned char *cpage_out, | |
34 | uint32_t *sourcelen, uint32_t *dstlen, | |
35 | void *model) | |
36 | { | |
37 | short positions[256]; | |
38 | int outpos = 0; | |
39 | int pos=0; | |
40 | ||
182ec4ee TG |
41 | memset(positions,0,sizeof(positions)); |
42 | ||
1da177e4 LT |
43 | while (pos < (*sourcelen) && outpos <= (*dstlen)-2) { |
44 | int backpos, runlen=0; | |
45 | unsigned char value; | |
182ec4ee | 46 | |
1da177e4 LT |
47 | value = data_in[pos]; |
48 | ||
49 | cpage_out[outpos++] = data_in[pos++]; | |
182ec4ee | 50 | |
1da177e4 LT |
51 | backpos = positions[value]; |
52 | positions[value]=pos; | |
182ec4ee | 53 | |
1da177e4 LT |
54 | while ((backpos < pos) && (pos < (*sourcelen)) && |
55 | (data_in[pos]==data_in[backpos++]) && (runlen<255)) { | |
56 | pos++; | |
57 | runlen++; | |
58 | } | |
59 | cpage_out[outpos++] = runlen; | |
60 | } | |
61 | ||
62 | if (outpos >= pos) { | |
63 | /* We failed */ | |
64 | return -1; | |
65 | } | |
182ec4ee | 66 | |
1da177e4 LT |
67 | /* Tell the caller how much we managed to compress, and how much space it took */ |
68 | *sourcelen = pos; | |
69 | *dstlen = outpos; | |
70 | return 0; | |
182ec4ee | 71 | } |
1da177e4 LT |
72 | |
73 | ||
74 | static int jffs2_rtime_decompress(unsigned char *data_in, | |
75 | unsigned char *cpage_out, | |
76 | uint32_t srclen, uint32_t destlen, | |
77 | void *model) | |
78 | { | |
79 | short positions[256]; | |
80 | int outpos = 0; | |
81 | int pos=0; | |
182ec4ee TG |
82 | |
83 | memset(positions,0,sizeof(positions)); | |
84 | ||
1da177e4 LT |
85 | while (outpos<destlen) { |
86 | unsigned char value; | |
87 | int backoffs; | |
88 | int repeat; | |
182ec4ee | 89 | |
1da177e4 LT |
90 | value = data_in[pos++]; |
91 | cpage_out[outpos++] = value; /* first the verbatim copied byte */ | |
92 | repeat = data_in[pos++]; | |
93 | backoffs = positions[value]; | |
182ec4ee | 94 | |
1da177e4 LT |
95 | positions[value]=outpos; |
96 | if (repeat) { | |
97 | if (backoffs + repeat >= outpos) { | |
98 | while(repeat) { | |
99 | cpage_out[outpos++] = cpage_out[backoffs++]; | |
100 | repeat--; | |
101 | } | |
102 | } else { | |
103 | memcpy(&cpage_out[outpos],&cpage_out[backoffs],repeat); | |
182ec4ee | 104 | outpos+=repeat; |
1da177e4 LT |
105 | } |
106 | } | |
107 | } | |
ef53cb02 | 108 | return 0; |
182ec4ee | 109 | } |
1da177e4 LT |
110 | |
111 | static struct jffs2_compressor jffs2_rtime_comp = { | |
112 | .priority = JFFS2_RTIME_PRIORITY, | |
113 | .name = "rtime", | |
114 | .compr = JFFS2_COMPR_RTIME, | |
115 | .compress = &jffs2_rtime_compress, | |
116 | .decompress = &jffs2_rtime_decompress, | |
117 | #ifdef JFFS2_RTIME_DISABLED | |
118 | .disabled = 1, | |
119 | #else | |
120 | .disabled = 0, | |
121 | #endif | |
122 | }; | |
123 | ||
124 | int jffs2_rtime_init(void) | |
125 | { | |
126 | return jffs2_register_compressor(&jffs2_rtime_comp); | |
127 | } | |
128 | ||
129 | void jffs2_rtime_exit(void) | |
130 | { | |
131 | jffs2_unregister_compressor(&jffs2_rtime_comp); | |
132 | } |