URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [rtos/] [ecos-3.0/] [packages/] [fs/] [jffs2/] [current/] [src/] [compr_rubin.c] - Blame information for rev 851

Go to most recent revision | Details | Compare with Previous | View Log


/*
 * JFFS2 -- Journalling Flash File System, Version 2.
 *
 * Copyright (C) 2001, 2002 Red Hat, Inc.
 *
 * Created by Arjan van de Ven <arjanv@redhat.com>
 *
 * For licensing information, see the file 'LICENCE' in this directory.
 *
 * $Id: compr_rubin.c,v 1.21 2005/05/20 15:39:54 gleixner Exp $
 *
 */
 
 
#include <linux/string.h>
#include <linux/types.h>
#include <linux/jffs2.h>
#include "compr_rubin.h"
#include "histo_mips.h"
#include "compr.h"
 
static void init_rubin(struct rubin_state *rs, int div, int *bits)
{
        int c;
 
        rs->q = 0;
        rs->p = (long) (2 * UPPER_BIT_RUBIN);
        rs->bit_number = (long) 0;
        rs->bit_divider = div;
        for (c=0; c<8; c++)
                rs->bits[c] = bits[c];
}
 
 
static int encode(struct rubin_state *rs, long A, long B, int symbol)
{
 
        long i0, i1;
        int ret;
 
        while ((rs->q >= UPPER_BIT_RUBIN) || ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) {
                rs->bit_number++;
 
                ret = pushbit(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 0);
                if (ret)
                        return ret;
                rs->q &= LOWER_BITS_RUBIN;
                rs->q <<= 1;
                rs->p <<= 1;
        }
        i0 = A * rs->p / (A + B);
        if (i0 <= 0) {
                i0 = 1;
        }
        if (i0 >= rs->p) {
                i0 = rs->p - 1;
        }
        i1 = rs->p - i0;
 
        if (symbol == 0)
                rs->p = i0;
        else {
                rs->p = i1;
                rs->q += i0;
        }
        return 0;
}
 
 
static void end_rubin(struct rubin_state *rs)
{
 
        int i;
 
        for (i = 0; i < RUBIN_REG_SIZE; i++) {
                pushbit(&rs->pp, (UPPER_BIT_RUBIN & rs->q) ? 1 : 0, 1);
                rs->q &= LOWER_BITS_RUBIN;
                rs->q <<= 1;
        }
}
 
 
static void init_decode(struct rubin_state *rs, int div, int *bits)
{
        init_rubin(rs, div, bits);
 
        /* behalve lower */
        rs->rec_q = 0;
 
        for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE; rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp)))
                ;
}
 
static void __do_decode(struct rubin_state *rs, unsigned long p, unsigned long q)
{
        register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN;
        unsigned long rec_q;
        int c, bits = 0;
 
        /*
         * First, work out how many bits we need from the input stream.
         * Note that we have already done the initial check on this
         * loop prior to calling this function.
         */
        do {
                bits++;
                q &= lower_bits_rubin;
                q <<= 1;
                p <<= 1;
        } while ((q >= UPPER_BIT_RUBIN) || ((p + q) <= UPPER_BIT_RUBIN));
 
        rs->p = p;
        rs->q = q;
 
        rs->bit_number += bits;
 
        /*
         * Now get the bits.  We really want this to be "get n bits".
         */
        rec_q = rs->rec_q;
        do {
                c = pullbit(&rs->pp);
                rec_q &= lower_bits_rubin;
                rec_q <<= 1;
                rec_q += c;
        } while (--bits);
        rs->rec_q = rec_q;
}
 
static int decode(struct rubin_state *rs, long A, long B)
{
        unsigned long p = rs->p, q = rs->q;
        long i0, threshold;
        int symbol;
 
        if (q >= UPPER_BIT_RUBIN || ((p + q) <= UPPER_BIT_RUBIN))
                __do_decode(rs, p, q);
 
        i0 = A * rs->p / (A + B);
        if (i0 <= 0) {
                i0 = 1;
        }
        if (i0 >= rs->p) {
                i0 = rs->p - 1;
        }
 
        threshold = rs->q + i0;
        symbol = rs->rec_q >= threshold;
        if (rs->rec_q >= threshold) {
                rs->q += i0;
                i0 = rs->p - i0;
        }
 
        rs->p = i0;
 
        return symbol;
}
 
 
 
static int out_byte(struct rubin_state *rs, unsigned char byte)
{
        int i, ret;
        struct rubin_state rs_copy;
        rs_copy = *rs;
 
        for (i=0;i<8;i++) {
                ret = encode(rs, rs->bit_divider-rs->bits[i],rs->bits[i],byte&1);
                if (ret) {
                        /* Failed. Restore old state */
                        *rs = rs_copy;
                        return ret;
                }
                byte=byte>>1;
        }
        return 0;
}
 
static int in_byte(struct rubin_state *rs)
{
        int i, result = 0, bit_divider = rs->bit_divider;
 
        for (i = 0; i < 8; i++)
                result |= decode(rs, bit_divider - rs->bits[i], rs->bits[i]) << i;
 
        return result;
}
 
 
 
static int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in,
                      unsigned char *cpage_out, uint32_t *sourcelen, uint32_t *dstlen)
        {
        int outpos = 0;
        int pos=0;
        struct rubin_state rs;
 
        init_pushpull(&rs.pp, cpage_out, *dstlen * 8, 0, 32);
 
        init_rubin(&rs, bit_divider, bits);
 
        while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos]))
                pos++;
 
        end_rubin(&rs);
 
        if (outpos > pos) {
                /* We failed */
                return -1;
        }
 
        /* Tell the caller how much we managed to compress,
         * and how much space it took */
 
        outpos = (pushedbits(&rs.pp)+7)/8;
 
        if (outpos >= pos)
                return -1; /* We didn't actually compress */
        *sourcelen = pos;
        *dstlen = outpos;
        return 0;
}
#if 0
/* _compress returns the compressed size, -1 if bigger */
int jffs2_rubinmips_compress(unsigned char *data_in, unsigned char *cpage_out,
                   uint32_t *sourcelen, uint32_t *dstlen, void *model)
{
        return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);
}
#endif
static int jffs2_dynrubin_compress(unsigned char *data_in,
                                   unsigned char *cpage_out,
                                   uint32_t *sourcelen, uint32_t *dstlen,
                                   void *model)
{
        int bits[8];
        unsigned char histo[256];
        int i;
        int ret;
        uint32_t mysrclen, mydstlen;
 
        mysrclen = *sourcelen;
        mydstlen = *dstlen - 8;
 
        if (*dstlen <= 12)
                return -1;
 
        memset(histo, 0, 256);
        for (i=0; i<mysrclen; i++) {
                histo[data_in[i]]++;
        }
        memset(bits, 0, sizeof(int)*8);
        for (i=0; i<256; i++) {
                if (i&128)
                        bits[7] += histo[i];
                if (i&64)
                        bits[6] += histo[i];
                if (i&32)
                        bits[5] += histo[i];
                if (i&16)
                        bits[4] += histo[i];
                if (i&8)
                        bits[3] += histo[i];
                if (i&4)
                        bits[2] += histo[i];
                if (i&2)
                        bits[1] += histo[i];
                if (i&1)
                        bits[0] += histo[i];
        }
 
        for (i=0; i<8; i++) {
                bits[i] = (bits[i] * 256) / mysrclen;
                if (!bits[i]) bits[i] = 1;
                if (bits[i] > 255) bits[i] = 255;
                cpage_out[i] = bits[i];
        }
 
        ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen, &mydstlen);
        if (ret)
                return ret;
 
        /* Add back the 8 bytes we took for the probabilities */
        mydstlen += 8;
 
        if (mysrclen <= mydstlen) {
                /* We compressed */
                return -1;
        }
 
        *sourcelen = mysrclen;
        *dstlen = mydstlen;
        return 0;
}
 
static void rubin_do_decompress(int bit_divider, int *bits, unsigned char *cdata_in,
                         unsigned char *page_out, uint32_t srclen, uint32_t destlen)
{
        int outpos = 0;
        struct rubin_state rs;
 
        init_pushpull(&rs.pp, cdata_in, srclen, 0, 0);
        init_decode(&rs, bit_divider, bits);
 
        while (outpos < destlen) {
                page_out[outpos++] = in_byte(&rs);
        }
}
 
 
static int jffs2_rubinmips_decompress(unsigned char *data_in,
                                      unsigned char *cpage_out,
                                      uint32_t sourcelen, uint32_t dstlen,
                                      void *model)
{
        rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);
        return 0;
}
 
static int jffs2_dynrubin_decompress(unsigned char *data_in,
                                     unsigned char *cpage_out,
                                     uint32_t sourcelen, uint32_t dstlen,
                                     void *model)
{
        int bits[8];
        int c;
 
        for (c=0; c<8; c++)
                bits[c] = data_in[c];
 
        rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8, dstlen);
        return 0;
}
 
static struct jffs2_compressor jffs2_rubinmips_comp = {
    .priority = JFFS2_RUBINMIPS_PRIORITY,
    .name = "rubinmips",
    .compr = JFFS2_COMPR_DYNRUBIN,
    .compress = NULL, /*&jffs2_rubinmips_compress,*/
    .decompress = &jffs2_rubinmips_decompress,
#ifdef JFFS2_RUBINMIPS_DISABLED
    .disabled = 1,
#else
    .disabled = 0,
#endif
};
 
int jffs2_rubinmips_init(void)
{
    return jffs2_register_compressor(&jffs2_rubinmips_comp);
}
 
void jffs2_rubinmips_exit(void)
{
    jffs2_unregister_compressor(&jffs2_rubinmips_comp);
}
 
static struct jffs2_compressor jffs2_dynrubin_comp = {
    .priority = JFFS2_DYNRUBIN_PRIORITY,
    .name = "dynrubin",
    .compr = JFFS2_COMPR_RUBINMIPS,
    .compress = jffs2_dynrubin_compress,
    .decompress = &jffs2_dynrubin_decompress,
#ifdef JFFS2_DYNRUBIN_DISABLED
    .disabled = 1,
#else
    .disabled = 0,
#endif
};
 
int jffs2_dynrubin_init(void)
{
    return jffs2_register_compressor(&jffs2_dynrubin_comp);
}
 
void jffs2_dynrubin_exit(void)
{
    jffs2_unregister_compressor(&jffs2_dynrubin_comp);
}

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [rtos/] [ecos-3.0/] [packages/] [fs/] [jffs2/] [current/] [src/] [compr_rubin.c] - Blame information for rev 851

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