Branch data Line data Source code
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 : 0 : 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 : 0 : memset(positions,0,sizeof(positions));
41 : :
42 [ # # ][ # # ]: 0 : while (pos < (*sourcelen) && outpos <= (*dstlen)-2) {
43 : : int backpos, runlen=0;
44 : : unsigned char value;
45 : :
46 : 0 : value = data_in[pos];
47 : :
48 : 0 : cpage_out[outpos++] = data_in[pos++];
49 : :
50 : 0 : backpos = positions[value];
51 : 0 : positions[value]=pos;
52 : :
53 [ # # ][ # # ]: 0 : while ((backpos < pos) && (pos < (*sourcelen)) &&
[ # # ]
54 [ # # ]: 0 : (data_in[pos]==data_in[backpos++]) && (runlen<255)) {
55 : 0 : pos++;
56 : 0 : runlen++;
57 : : }
58 : 0 : cpage_out[outpos++] = runlen;
59 : : }
60 : :
61 [ # # ]: 0 : 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 : 0 : *sourcelen = pos;
68 : 0 : *dstlen = outpos;
69 : 0 : return 0;
70 : : }
71 : :
72 : :
73 : 0 : 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 : 0 : memset(positions,0,sizeof(positions));
82 : :
83 [ # # ]: 0 : while (outpos<destlen) {
84 : : unsigned char value;
85 : : int backoffs;
86 : : int repeat;
87 : :
88 : 0 : value = data_in[pos++];
89 : 0 : cpage_out[outpos++] = value; /* first the verbatim copied byte */
90 : 0 : repeat = data_in[pos++];
91 : 0 : backoffs = positions[value];
92 : :
93 : 0 : positions[value]=outpos;
94 [ # # ]: 0 : if (repeat) {
95 [ # # ]: 0 : if (backoffs + repeat >= outpos) {
96 [ # # ]: 0 : while(repeat) {
97 : 0 : cpage_out[outpos++] = cpage_out[backoffs++];
98 : 0 : repeat--;
99 : : }
100 : : } else {
101 : 0 : memcpy(&cpage_out[outpos],&cpage_out[backoffs],repeat);
102 : 0 : outpos+=repeat;
103 : : }
104 : : }
105 : : }
106 : 0 : 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 : 0 : int jffs2_rtime_init(void)
123 : : {
124 : 0 : return jffs2_register_compressor(&jffs2_rtime_comp);
125 : : }
126 : :
127 : 0 : void jffs2_rtime_exit(void)
128 : : {
129 : 0 : jffs2_unregister_compressor(&jffs2_rtime_comp);
130 : 0 : }
|