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

Subversion Repositories or1k

[/] [or1k/] [trunk/] [ecos-2.0/] [packages/] [fs/] [jffs2/] [v2_0/] [src/] [compr_rubin.c] - Blame information for rev 1765

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.1.1.1 2004-02-14 13:29:19 phoenix Exp $
 *
 */
 
 
#include <linux/string.h>
#include <linux/types.h>
#include "compr_rubin.h"
#include "histo_mips.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)
{
        return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);
}
#endif
int jffs2_dynrubin_compress(unsigned char *data_in, unsigned char *cpage_out,
                   uint32_t *sourcelen, uint32_t *dstlen)
{
        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);
        }
}
 
 
void jffs2_rubinmips_decompress(unsigned char *data_in, unsigned char *cpage_out,
                   uint32_t sourcelen, uint32_t dstlen)
{
        rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);
}
 
void jffs2_dynrubin_decompress(unsigned char *data_in, unsigned char *cpage_out,
                   uint32_t sourcelen, uint32_t dstlen)
{
        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);
}

Browse

Tools

Subversion Repositories or1k

[/] [or1k/] [trunk/] [ecos-2.0/] [packages/] [fs/] [jffs2/] [v2_0/] [src/] [compr_rubin.c] - Blame information for rev 1765

Line No.	Rev	Author	Line
1	1254	phoenix	`/*`
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.1.1.1 2004-02-14 13:29:19 phoenix Exp $`
11			`*`
12			`*/`
13
14
15			`#include <linux/string.h>`
16			`#include <linux/types.h>`
17			`#include "compr_rubin.h"`
18			`#include "histo_mips.h"`
19
20
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)`
227			`{`
228			`return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);`
229			`}`
230			`#endif`
231			`int jffs2_dynrubin_compress(unsigned char data_in, unsigned char cpage_out,`
232			`uint32_t sourcelen, uint32_t dstlen)`
233			`{`
234			`int bits[8];`
235			`unsigned char histo[256];`
236			`int i;`
237			`int ret;`
238			`uint32_t mysrclen, mydstlen;`
239
240			`mysrclen = *sourcelen;`
241			`mydstlen = *dstlen - 8;`
242
243			`if (*dstlen <= 12)`
244			`return -1;`
245
246			`memset(histo, 0, 256);`
247			`for (i=0; i<mysrclen; i++) {`
248			`histo[data_in[i]]++;`
249			`}`
250			`memset(bits, 0, sizeof(int)*8);`
251			`for (i=0; i<256; i++) {`
252			`if (i&128)`
253			`bits[7] += histo[i];`
254			`if (i&64)`
255			`bits[6] += histo[i];`
256			`if (i&32)`
257			`bits[5] += histo[i];`
258			`if (i&16)`
259			`bits[4] += histo[i];`
260			`if (i&8)`
261			`bits[3] += histo[i];`
262			`if (i&4)`
263			`bits[2] += histo[i];`
264			`if (i&2)`
265			`bits[1] += histo[i];`
266			`if (i&1)`
267			`bits[0] += histo[i];`
268			`}`
269
270			`for (i=0; i<8; i++) {`
271			`bits[i] = (bits[i] * 256) / mysrclen;`
272			`if (!bits[i]) bits[i] = 1;`
273			`if (bits[i] > 255) bits[i] = 255;`
274			`cpage_out[i] = bits[i];`
275			`}`
276
277			`ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen, &mydstlen);`
278			`if (ret)`
279			`return ret;`
280
281			`/* Add back the 8 bytes we took for the probabilities */`
282			`mydstlen += 8;`
283
284			`if (mysrclen <= mydstlen) {`
285			`/* We compressed */`
286			`return -1;`
287			`}`
288
289			`*sourcelen = mysrclen;`
290			`*dstlen = mydstlen;`
291			`return 0;`
292			`}`
293
294			`static void rubin_do_decompress(int bit_divider, int bits, unsigned char cdata_in,`
295			`unsigned char *page_out, uint32_t srclen, uint32_t destlen)`
296			`{`
297			`int outpos = 0;`
298			`struct rubin_state rs;`
299
300			`init_pushpull(&rs.pp, cdata_in, srclen, 0, 0);`
301			`init_decode(&rs, bit_divider, bits);`
302
303			`while (outpos < destlen) {`
304			`page_out[outpos++] = in_byte(&rs);`
305			`}`
306			`}`
307
308
309			`void jffs2_rubinmips_decompress(unsigned char data_in, unsigned char cpage_out,`
310			`uint32_t sourcelen, uint32_t dstlen)`
311			`{`
312			`rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);`
313			`}`
314
315			`void jffs2_dynrubin_decompress(unsigned char data_in, unsigned char cpage_out,`
316			`uint32_t sourcelen, uint32_t dstlen)`
317			`{`
318			`int bits[8];`
319			`int c;`
320
321			`for (c=0; c<8; c++)`
322			`bits[c] = data_in[c];`
323
324			`rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8, dstlen);`
325			`}`