1 | /* |
2 | * JFFS2 -- Journalling Flash File System, Version 2. |
3 | * |
4 | * Copyright © 2001-2007 Red Hat, Inc. |
5 | * Copyright © 2004-2010 David Woodhouse <dwmw2@infradead.org> |
6 | * |
7 | * Created by Arjan van de Ven <arjanv@redhat.com> |
8 | * |
9 | * For licensing information, see the file 'LICENCE' in this directory. |
10 | * |
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> |
27 | #include <linux/string.h> |
28 | #include <linux/jffs2.h> |
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 | { |
36 | unsigned short positions[256]; |
37 | int outpos = 0; |
38 | int pos=0; |
39 | |
40 | if (*dstlen <= 3) |
41 | return -1; |
42 | |
43 | memset(positions,0,sizeof(positions)); |
44 | |
45 | while (pos < (*sourcelen) && outpos <= (*dstlen)-2) { |
46 | int backpos, runlen=0; |
47 | unsigned char value; |
48 | |
49 | value = data_in[pos]; |
50 | |
51 | cpage_out[outpos++] = data_in[pos++]; |
52 | |
53 | backpos = positions[value]; |
54 | positions[value]=pos; |
55 | |
56 | while ((backpos < pos) && (pos < (*sourcelen)) && |
57 | (data_in[pos]==data_in[backpos++]) && (runlen<255)) { |
58 | pos++; |
59 | runlen++; |
60 | } |
61 | cpage_out[outpos++] = runlen; |
62 | } |
63 | |
64 | if (outpos >= pos) { |
65 | /* We failed */ |
66 | return -1; |
67 | } |
68 | |
69 | /* Tell the caller how much we managed to compress, and how much space it took */ |
70 | *sourcelen = pos; |
71 | *dstlen = outpos; |
72 | return 0; |
73 | } |
74 | |
75 | |
76 | static int jffs2_rtime_decompress(unsigned char *data_in, |
77 | unsigned char *cpage_out, |
78 | uint32_t srclen, uint32_t destlen) |
79 | { |
80 | unsigned short positions[256]; |
81 | int outpos = 0; |
82 | int pos=0; |
83 | |
84 | memset(positions,0,sizeof(positions)); |
85 | |
86 | while (outpos<destlen) { |
87 | unsigned char value; |
88 | int backoffs; |
89 | int repeat; |
90 | |
91 | value = data_in[pos++]; |
92 | cpage_out[outpos++] = value; /* first the verbatim copied byte */ |
93 | repeat = data_in[pos++]; |
94 | backoffs = positions[value]; |
95 | |
96 | positions[value]=outpos; |
97 | if (repeat) { |
98 | if (backoffs + repeat >= outpos) { |
99 | while(repeat) { |
100 | cpage_out[outpos++] = cpage_out[backoffs++]; |
101 | repeat--; |
102 | } |
103 | } else { |
104 | memcpy(&cpage_out[outpos],&cpage_out[backoffs],repeat); |
105 | outpos+=repeat; |
106 | } |
107 | } |
108 | } |
109 | return 0; |
110 | } |
111 | |
112 | static struct jffs2_compressor jffs2_rtime_comp = { |
113 | .priority = JFFS2_RTIME_PRIORITY, |
114 | .name = "rtime" , |
115 | .compr = JFFS2_COMPR_RTIME, |
116 | .compress = &jffs2_rtime_compress, |
117 | .decompress = &jffs2_rtime_decompress, |
118 | #ifdef JFFS2_RTIME_DISABLED |
119 | .disabled = 1, |
120 | #else |
121 | .disabled = 0, |
122 | #endif |
123 | }; |
124 | |
125 | int jffs2_rtime_init(void) |
126 | { |
127 | return jffs2_register_compressor(comp: &jffs2_rtime_comp); |
128 | } |
129 | |
130 | void jffs2_rtime_exit(void) |
131 | { |
132 | jffs2_unregister_compressor(comp: &jffs2_rtime_comp); |
133 | } |
134 | |