source: rtems/cpukit/libfs/src/jffs2/src/compr_rubin.c @ 6ac6a5c8

Last change on this file since 6ac6a5c8 was 6ac6a5c8, checked in by Sebastian Huber <sebastian.huber@…>, on Mar 27, 2018 at 11:01:56 AM

jffs2: Do not use command line defines

Update #3375.

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