GNU Linux-libre 4.9.308-gnu1
[releases.git] / fs / jffs2 / compr_rubin.c
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 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
14
15 #include <linux/string.h>
16 #include <linux/types.h>
17 #include <linux/jffs2.h>
18 #include <linux/errno.h>
19 #include "compr.h"
20
21
22 #define RUBIN_REG_SIZE   16
23 #define UPPER_BIT_RUBIN    (((long) 1)<<(RUBIN_REG_SIZE-1))
24 #define LOWER_BITS_RUBIN   ((((long) 1)<<(RUBIN_REG_SIZE-1))-1)
25
26
27 #define BIT_DIVIDER_MIPS 1043
28 static int bits_mips[8] = { 277, 249, 290, 267, 229, 341, 212, 241};
29
30 struct pushpull {
31         unsigned char *buf;
32         unsigned int buflen;
33         unsigned int ofs;
34         unsigned int reserve;
35 };
36
37 struct rubin_state {
38         unsigned long p;
39         unsigned long q;
40         unsigned long rec_q;
41         long bit_number;
42         struct pushpull pp;
43         int bit_divider;
44         int bits[8];
45 };
46
47 static inline void init_pushpull(struct pushpull *pp, char *buf,
48                                  unsigned buflen, unsigned ofs,
49                                  unsigned reserve)
50 {
51         pp->buf = buf;
52         pp->buflen = buflen;
53         pp->ofs = ofs;
54         pp->reserve = reserve;
55 }
56
57 static inline int pushbit(struct pushpull *pp, int bit, int use_reserved)
58 {
59         if (pp->ofs >= pp->buflen - (use_reserved?0:pp->reserve))
60                 return -ENOSPC;
61
62         if (bit)
63                 pp->buf[pp->ofs >> 3] |= (1<<(7-(pp->ofs & 7)));
64         else
65                 pp->buf[pp->ofs >> 3] &= ~(1<<(7-(pp->ofs & 7)));
66
67         pp->ofs++;
68
69         return 0;
70 }
71
72 static inline int pushedbits(struct pushpull *pp)
73 {
74         return pp->ofs;
75 }
76
77 static inline int pullbit(struct pushpull *pp)
78 {
79         int bit;
80
81         bit = (pp->buf[pp->ofs >> 3] >> (7-(pp->ofs & 7))) & 1;
82
83         pp->ofs++;
84         return bit;
85 }
86
87
88 static void init_rubin(struct rubin_state *rs, int div, int *bits)
89 {
90         int c;
91
92         rs->q = 0;
93         rs->p = (long) (2 * UPPER_BIT_RUBIN);
94         rs->bit_number = (long) 0;
95         rs->bit_divider = div;
96
97         for (c=0; c<8; c++)
98                 rs->bits[c] = bits[c];
99 }
100
101
102 static int encode(struct rubin_state *rs, long A, long B, int symbol)
103 {
104
105         long i0, i1;
106         int ret;
107
108         while ((rs->q >= UPPER_BIT_RUBIN) ||
109                ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) {
110                 rs->bit_number++;
111
112                 ret = pushbit(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 0);
113                 if (ret)
114                         return ret;
115                 rs->q &= LOWER_BITS_RUBIN;
116                 rs->q <<= 1;
117                 rs->p <<= 1;
118         }
119         i0 = A * rs->p / (A + B);
120         if (i0 <= 0)
121                 i0 = 1;
122
123         if (i0 >= rs->p)
124                 i0 = rs->p - 1;
125
126         i1 = rs->p - i0;
127
128         if (symbol == 0)
129                 rs->p = i0;
130         else {
131                 rs->p = i1;
132                 rs->q += i0;
133         }
134         return 0;
135 }
136
137
138 static void end_rubin(struct rubin_state *rs)
139 {
140
141         int i;
142
143         for (i = 0; i < RUBIN_REG_SIZE; i++) {
144                 pushbit(&rs->pp, (UPPER_BIT_RUBIN & rs->q) ? 1 : 0, 1);
145                 rs->q &= LOWER_BITS_RUBIN;
146                 rs->q <<= 1;
147         }
148 }
149
150
151 static void init_decode(struct rubin_state *rs, int div, int *bits)
152 {
153         init_rubin(rs, div, bits);
154
155         /* behalve lower */
156         rs->rec_q = 0;
157
158         for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE;
159              rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp)))
160                 ;
161 }
162
163 static void __do_decode(struct rubin_state *rs, unsigned long p,
164                         unsigned long q)
165 {
166         register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN;
167         unsigned long rec_q;
168         int c, bits = 0;
169
170         /*
171          * First, work out how many bits we need from the input stream.
172          * Note that we have already done the initial check on this
173          * loop prior to calling this function.
174          */
175         do {
176                 bits++;
177                 q &= lower_bits_rubin;
178                 q <<= 1;
179                 p <<= 1;
180         } while ((q >= UPPER_BIT_RUBIN) || ((p + q) <= UPPER_BIT_RUBIN));
181
182         rs->p = p;
183         rs->q = q;
184
185         rs->bit_number += bits;
186
187         /*
188          * Now get the bits.  We really want this to be "get n bits".
189          */
190         rec_q = rs->rec_q;
191         do {
192                 c = pullbit(&rs->pp);
193                 rec_q &= lower_bits_rubin;
194                 rec_q <<= 1;
195                 rec_q += c;
196         } while (--bits);
197         rs->rec_q = rec_q;
198 }
199
200 static int decode(struct rubin_state *rs, long A, long B)
201 {
202         unsigned long p = rs->p, q = rs->q;
203         long i0, threshold;
204         int symbol;
205
206         if (q >= UPPER_BIT_RUBIN || ((p + q) <= UPPER_BIT_RUBIN))
207                 __do_decode(rs, p, q);
208
209         i0 = A * rs->p / (A + B);
210         if (i0 <= 0)
211                 i0 = 1;
212
213         if (i0 >= rs->p)
214                 i0 = rs->p - 1;
215
216         threshold = rs->q + i0;
217         symbol = rs->rec_q >= threshold;
218         if (rs->rec_q >= threshold) {
219                 rs->q += i0;
220                 i0 = rs->p - i0;
221         }
222
223         rs->p = i0;
224
225         return symbol;
226 }
227
228
229
230 static int out_byte(struct rubin_state *rs, unsigned char byte)
231 {
232         int i, ret;
233         struct rubin_state rs_copy;
234         rs_copy = *rs;
235
236         for (i=0; i<8; i++) {
237                 ret = encode(rs, rs->bit_divider-rs->bits[i],
238                              rs->bits[i], byte & 1);
239                 if (ret) {
240                         /* Failed. Restore old state */
241                         *rs = rs_copy;
242                         return ret;
243                 }
244                 byte >>= 1 ;
245         }
246         return 0;
247 }
248
249 static int in_byte(struct rubin_state *rs)
250 {
251         int i, result = 0, bit_divider = rs->bit_divider;
252
253         for (i = 0; i < 8; i++)
254                 result |= decode(rs, bit_divider - rs->bits[i],
255                                  rs->bits[i]) << i;
256
257         return result;
258 }
259
260
261
262 static int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in,
263                              unsigned char *cpage_out, uint32_t *sourcelen,
264                              uint32_t *dstlen)
265         {
266         int outpos = 0;
267         int pos=0;
268         struct rubin_state rs;
269
270         init_pushpull(&rs.pp, cpage_out, *dstlen * 8, 0, 32);
271
272         init_rubin(&rs, bit_divider, bits);
273
274         while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos]))
275                 pos++;
276
277         end_rubin(&rs);
278
279         if (outpos > pos) {
280                 /* We failed */
281                 return -1;
282         }
283
284         /* Tell the caller how much we managed to compress,
285          * and how much space it took */
286
287         outpos = (pushedbits(&rs.pp)+7)/8;
288
289         if (outpos >= pos)
290                 return -1; /* We didn't actually compress */
291         *sourcelen = pos;
292         *dstlen = outpos;
293         return 0;
294 }
295 #if 0
296 /* _compress returns the compressed size, -1 if bigger */
297 int jffs2_rubinmips_compress(unsigned char *data_in, unsigned char *cpage_out,
298                    uint32_t *sourcelen, uint32_t *dstlen)
299 {
300         return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in,
301                                  cpage_out, sourcelen, dstlen);
302 }
303 #endif
304 static int jffs2_dynrubin_compress(unsigned char *data_in,
305                                    unsigned char *cpage_out,
306                                    uint32_t *sourcelen, uint32_t *dstlen)
307 {
308         int bits[8];
309         unsigned char histo[256];
310         int i;
311         int ret;
312         uint32_t mysrclen, mydstlen;
313
314         mysrclen = *sourcelen;
315         mydstlen = *dstlen - 8;
316
317         if (*dstlen <= 12)
318                 return -1;
319
320         memset(histo, 0, 256);
321         for (i=0; i<mysrclen; i++)
322                 histo[data_in[i]]++;
323         memset(bits, 0, sizeof(int)*8);
324         for (i=0; i<256; i++) {
325                 if (i&128)
326                         bits[7] += histo[i];
327                 if (i&64)
328                         bits[6] += histo[i];
329                 if (i&32)
330                         bits[5] += histo[i];
331                 if (i&16)
332                         bits[4] += histo[i];
333                 if (i&8)
334                         bits[3] += histo[i];
335                 if (i&4)
336                         bits[2] += histo[i];
337                 if (i&2)
338                         bits[1] += histo[i];
339                 if (i&1)
340                         bits[0] += histo[i];
341         }
342
343         for (i=0; i<8; i++) {
344                 bits[i] = (bits[i] * 256) / mysrclen;
345                 if (!bits[i]) bits[i] = 1;
346                 if (bits[i] > 255) bits[i] = 255;
347                 cpage_out[i] = bits[i];
348         }
349
350         ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen,
351                                 &mydstlen);
352         if (ret)
353                 return ret;
354
355         /* Add back the 8 bytes we took for the probabilities */
356         mydstlen += 8;
357
358         if (mysrclen <= mydstlen) {
359                 /* We compressed */
360                 return -1;
361         }
362
363         *sourcelen = mysrclen;
364         *dstlen = mydstlen;
365         return 0;
366 }
367
368 static void rubin_do_decompress(int bit_divider, int *bits,
369                                 unsigned char *cdata_in, 
370                                 unsigned char *page_out, uint32_t srclen,
371                                 uint32_t destlen)
372 {
373         int outpos = 0;
374         struct rubin_state rs;
375
376         init_pushpull(&rs.pp, cdata_in, srclen, 0, 0);
377         init_decode(&rs, bit_divider, bits);
378
379         while (outpos < destlen)
380                 page_out[outpos++] = in_byte(&rs);
381 }
382
383
384 static int jffs2_rubinmips_decompress(unsigned char *data_in,
385                                       unsigned char *cpage_out,
386                                       uint32_t sourcelen, uint32_t dstlen)
387 {
388         rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in,
389                             cpage_out, sourcelen, dstlen);
390         return 0;
391 }
392
393 static int jffs2_dynrubin_decompress(unsigned char *data_in,
394                                      unsigned char *cpage_out,
395                                      uint32_t sourcelen, uint32_t dstlen)
396 {
397         int bits[8];
398         int c;
399
400         for (c=0; c<8; c++)
401                 bits[c] = data_in[c];
402
403         rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8,
404                             dstlen);
405         return 0;
406 }
407
408 static struct jffs2_compressor jffs2_rubinmips_comp = {
409         .priority = JFFS2_RUBINMIPS_PRIORITY,
410         .name = "rubinmips",
411         .compr = JFFS2_COMPR_DYNRUBIN,
412         .compress = NULL, /*&jffs2_rubinmips_compress,*/
413         .decompress = &jffs2_rubinmips_decompress,
414 #ifdef JFFS2_RUBINMIPS_DISABLED
415         .disabled = 1,
416 #else
417         .disabled = 0,
418 #endif
419 };
420
421 int jffs2_rubinmips_init(void)
422 {
423         return jffs2_register_compressor(&jffs2_rubinmips_comp);
424 }
425
426 void jffs2_rubinmips_exit(void)
427 {
428         jffs2_unregister_compressor(&jffs2_rubinmips_comp);
429 }
430
431 static struct jffs2_compressor jffs2_dynrubin_comp = {
432         .priority = JFFS2_DYNRUBIN_PRIORITY,
433         .name = "dynrubin",
434         .compr = JFFS2_COMPR_RUBINMIPS,
435         .compress = jffs2_dynrubin_compress,
436         .decompress = &jffs2_dynrubin_decompress,
437 #ifdef JFFS2_DYNRUBIN_DISABLED
438         .disabled = 1,
439 #else
440         .disabled = 0,
441 #endif
442 };
443
444 int jffs2_dynrubin_init(void)
445 {
446         return jffs2_register_compressor(&jffs2_dynrubin_comp);
447 }
448
449 void jffs2_dynrubin_exit(void)
450 {
451         jffs2_unregister_compressor(&jffs2_dynrubin_comp);
452 }