2  * JFFS2 -- Journalling Flash File System, Version 2.
4  * Copyright © 2001-2007 Red Hat, Inc.
5  * Copyright © 2004-2010 David Woodhouse <dwmw2@infradead.org>
23 #define UPPER_BIT_RUBIN    (((long) 1)<<(RUBIN_REG_SIZE-1))
24 #define LOWER_BITS_RUBIN   ((((long) 1)<<(RUBIN_REG_SIZE-1))-1)
51 	pp->buf = buf;  in init_pushpull()
52 	pp->buflen = buflen;  in init_pushpull()
53 	pp->ofs = ofs;  in init_pushpull()
54 	pp->reserve = reserve;  in init_pushpull()
59 	if (pp->ofs >= pp->buflen - (use_reserved?0:pp->reserve))  in pushbit()
60 		return -ENOSPC;  in pushbit()
63 		pp->buf[pp->ofs >> 3] |= (1<<(7-(pp->ofs & 7)));  in pushbit()
65 		pp->buf[pp->ofs >> 3] &= ~(1<<(7-(pp->ofs & 7)));  in pushbit()
67 	pp->ofs++;  in pushbit()
74 	return pp->ofs;  in pushedbits()
81 	bit = (pp->buf[pp->ofs >> 3] >> (7-(pp->ofs & 7))) & 1;  in pullbit()
83 	pp->ofs++;  in pullbit()
88 static void init_rubin(struct rubin_state *rs, int div, int *bits)  in init_rubin()  argument
92 	rs->q = 0;  in init_rubin()
93 	rs->p = (long) (2 * UPPER_BIT_RUBIN);  in init_rubin()
94 	rs->bit_number = (long) 0;  in init_rubin()
95 	rs->bit_divider = div;  in init_rubin()
98 		rs->bits[c] = bits[c];  in init_rubin()
102 static int encode(struct rubin_state *rs, long A, long B, int symbol)  in encode()  argument
108 	while ((rs->q >= UPPER_BIT_RUBIN) ||  in encode()
109 	       ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) {  in encode()
110 		rs->bit_number++;  in encode()
112 		ret = pushbit(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 0);  in encode()
115 		rs->q &= LOWER_BITS_RUBIN;  in encode()
116 		rs->q <<= 1;  in encode()
117 		rs->p <<= 1;  in encode()
119 	i0 = A * rs->p / (A + B);  in encode()
123 	if (i0 >= rs->p)  in encode()
124 		i0 = rs->p - 1;  in encode()
126 	i1 = rs->p - i0;  in encode()
129 		rs->p = i0;  in encode()
131 		rs->p = i1;  in encode()
132 		rs->q += i0;  in encode()
138 static void end_rubin(struct rubin_state *rs)  in end_rubin()  argument
144 		pushbit(&rs->pp, (UPPER_BIT_RUBIN & rs->q) ? 1 : 0, 1);  in end_rubin()
145 		rs->q &= LOWER_BITS_RUBIN;  in end_rubin()
146 		rs->q <<= 1;  in end_rubin()
151 static void init_decode(struct rubin_state *rs, int div, int *bits)  in init_decode()  argument
153 	init_rubin(rs, div, bits);  in init_decode()
156 	rs->rec_q = 0;  in init_decode()
158 	for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE;  in init_decode()
159 	     rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp)))  in init_decode()
163 static void __do_decode(struct rubin_state *rs, unsigned long p,  in __do_decode()  argument
182 	rs->p = p;  in __do_decode()
183 	rs->q = q;  in __do_decode()
185 	rs->bit_number += bits;  in __do_decode()
190 	rec_q = rs->rec_q;  in __do_decode()
192 		c = pullbit(&rs->pp);  in __do_decode()
196 	} while (--bits);  in __do_decode()
197 	rs->rec_q = rec_q;  in __do_decode()
200 static int decode(struct rubin_state *rs, long A, long B)  in decode()  argument
202 	unsigned long p = rs->p, q = rs->q;  in decode()
207 		__do_decode(rs, p, q);  in decode()
209 	i0 = A * rs->p / (A + B);  in decode()
213 	if (i0 >= rs->p)  in decode()
214 		i0 = rs->p - 1;  in decode()
216 	threshold = rs->q + i0;  in decode()
217 	symbol = rs->rec_q >= threshold;  in decode()
218 	if (rs->rec_q >= threshold) {  in decode()
219 		rs->q += i0;  in decode()
220 		i0 = rs->p - i0;  in decode()
223 	rs->p = i0;  in decode()
230 static int out_byte(struct rubin_state *rs, unsigned char byte)  in out_byte()  argument
234 	rs_copy = *rs;  in out_byte()
237 		ret = encode(rs, rs->bit_divider-rs->bits[i],  in out_byte()
238 			     rs->bits[i], byte & 1);  in out_byte()
241 			*rs = rs_copy;  in out_byte()
249 static int in_byte(struct rubin_state *rs)  in in_byte()  argument
251 	int i, result = 0, bit_divider = rs->bit_divider;  in in_byte()
254 		result |= decode(rs, bit_divider - rs->bits[i],  in in_byte()
255 				 rs->bits[i]) << i;  in in_byte()
268 	struct rubin_state rs;  in rubin_do_compress()  local
270 	init_pushpull(&rs.pp, cpage_out, *dstlen * 8, 0, 32);  in rubin_do_compress()
272 	init_rubin(&rs, bit_divider, bits);  in rubin_do_compress()
274 	while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos]))  in rubin_do_compress()
277 	end_rubin(&rs);  in rubin_do_compress()
281 		return -1;  in rubin_do_compress()
287 	outpos = (pushedbits(&rs.pp)+7)/8;  in rubin_do_compress()
290 		return -1; /* We didn't actually compress */  in rubin_do_compress()
296 /* _compress returns the compressed size, -1 if bigger */
315 	mydstlen = *dstlen - 8;  in jffs2_dynrubin_compress()
318 		return -1;  in jffs2_dynrubin_compress()
360 		return -1;  in jffs2_dynrubin_compress()
374 	struct rubin_state rs;  in rubin_do_decompress()  local
376 	init_pushpull(&rs.pp, cdata_in, srclen, 0, 0);  in rubin_do_decompress()
377 	init_decode(&rs, bit_divider, bits);  in rubin_do_decompress()
380 		page_out[outpos++] = in_byte(&rs);  in rubin_do_decompress()
403 	rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8,  in jffs2_dynrubin_decompress()