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