Merge branch 'gfar' of master.kernel.org:/pub/scm/linux/kernel/git/galak/powerpc...
[linux-2.6] / fs / jffs2 / compr_rtime.c
1 /*
2  * JFFS2 -- Journalling Flash File System, Version 2.
3  *
4  * Copyright (C) 2001-2003 Red Hat, Inc.
5  *
6  * Created by Arjan van de Ven <arjanv@redhat.com>
7  *
8  * For licensing information, see the file 'LICENCE' in this directory.
9  *
10  * $Id: compr_rtime.c,v 1.14 2004/06/23 16:34:40 havasi Exp $
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                                 void *model)
36 {
37         short positions[256];
38         int outpos = 0;
39         int pos=0;
40
41         memset(positions,0,sizeof(positions));
42
43         while (pos < (*sourcelen) && outpos <= (*dstlen)-2) {
44                 int backpos, runlen=0;
45                 unsigned char value;
46
47                 value = data_in[pos];
48
49                 cpage_out[outpos++] = data_in[pos++];
50
51                 backpos = positions[value];
52                 positions[value]=pos;
53
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         }
66
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;
71 }
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;
82
83         memset(positions,0,sizeof(positions));
84
85         while (outpos<destlen) {
86                 unsigned char value;
87                 int backoffs;
88                 int repeat;
89
90                 value = data_in[pos++];
91                 cpage_out[outpos++] = value; /* first the verbatim copied byte */
92                 repeat = data_in[pos++];
93                 backoffs = positions[value];
94
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);
104                                 outpos+=repeat;
105                         }
106                 }
107         }
108         return 0;
109 }
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 }