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 | short positions[256]; |
---|
37 | int outpos = 0; |
---|
38 | int pos=0; |
---|
39 | |
---|
40 | memset(positions,0,sizeof(positions)); |
---|
41 | |
---|
42 | while (pos < (*sourcelen) && outpos <= (*dstlen)-2) { |
---|
43 | int backpos, runlen=0; |
---|
44 | unsigned char value; |
---|
45 | |
---|
46 | value = data_in[pos]; |
---|
47 | |
---|
48 | cpage_out[outpos++] = data_in[pos++]; |
---|
49 | |
---|
50 | backpos = positions[value]; |
---|
51 | positions[value]=pos; |
---|
52 | |
---|
53 | while ((backpos < pos) && (pos < (*sourcelen)) && |
---|
54 | (data_in[pos]==data_in[backpos++]) && (runlen<255)) { |
---|
55 | pos++; |
---|
56 | runlen++; |
---|
57 | } |
---|
58 | cpage_out[outpos++] = runlen; |
---|
59 | } |
---|
60 | |
---|
61 | if (outpos >= pos) { |
---|
62 | /* We failed */ |
---|
63 | return -1; |
---|
64 | } |
---|
65 | |
---|
66 | /* Tell the caller how much we managed to compress, and how much space it took */ |
---|
67 | *sourcelen = pos; |
---|
68 | *dstlen = outpos; |
---|
69 | return 0; |
---|
70 | } |
---|
71 | |
---|
72 | |
---|
73 | static int jffs2_rtime_decompress(unsigned char *data_in, |
---|
74 | unsigned char *cpage_out, |
---|
75 | uint32_t srclen, uint32_t destlen) |
---|
76 | { |
---|
77 | short positions[256]; |
---|
78 | int outpos = 0; |
---|
79 | int pos=0; |
---|
80 | |
---|
81 | memset(positions,0,sizeof(positions)); |
---|
82 | |
---|
83 | while (outpos<destlen) { |
---|
84 | unsigned char value; |
---|
85 | int backoffs; |
---|
86 | int repeat; |
---|
87 | |
---|
88 | value = data_in[pos++]; |
---|
89 | cpage_out[outpos++] = value; /* first the verbatim copied byte */ |
---|
90 | repeat = data_in[pos++]; |
---|
91 | backoffs = positions[value]; |
---|
92 | |
---|
93 | positions[value]=outpos; |
---|
94 | if (repeat) { |
---|
95 | if (backoffs + repeat >= outpos) { |
---|
96 | while(repeat) { |
---|
97 | cpage_out[outpos++] = cpage_out[backoffs++]; |
---|
98 | repeat--; |
---|
99 | } |
---|
100 | } else { |
---|
101 | memcpy(&cpage_out[outpos],&cpage_out[backoffs],repeat); |
---|
102 | outpos+=repeat; |
---|
103 | } |
---|
104 | } |
---|
105 | } |
---|
106 | return 0; |
---|
107 | } |
---|
108 | |
---|
109 | static struct jffs2_compressor jffs2_rtime_comp = { |
---|
110 | .priority = JFFS2_RTIME_PRIORITY, |
---|
111 | .name = "rtime", |
---|
112 | .compr = JFFS2_COMPR_RTIME, |
---|
113 | .compress = &jffs2_rtime_compress, |
---|
114 | .decompress = &jffs2_rtime_decompress, |
---|
115 | #ifdef JFFS2_RTIME_DISABLED |
---|
116 | .disabled = 1, |
---|
117 | #else |
---|
118 | .disabled = 0, |
---|
119 | #endif |
---|
120 | }; |
---|
121 | |
---|
122 | int jffs2_rtime_init(void) |
---|
123 | { |
---|
124 | return jffs2_register_compressor(&jffs2_rtime_comp); |
---|
125 | } |
---|
126 | |
---|
127 | void jffs2_rtime_exit(void) |
---|
128 | { |
---|
129 | jffs2_unregister_compressor(&jffs2_rtime_comp); |
---|
130 | } |
---|