ia64/linux-2.6.18-xen.hg

view fs/jffs2/compr_rubin.c @ 524:7f8b544237bf

netfront: Allow netfront in domain 0.

This is useful if your physical network device is in a utility domain.

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