1/*
2 * JFFS2 -- Journalling Flash File System, Version 2.
3 *
4 * Copyright (C) 2001 Red Hat, Inc.
5 *
6 * Created by Arjan van de Ven <arjanv@redhat.com>
7 *
8 * The original JFFS, from which the design for JFFS2 was derived,
9 * was designed and implemented by Axis Communications AB.
10 *
11 * The contents of this file are subject to the Red Hat eCos Public
12 * License Version 1.1 (the "Licence"); you may not use this file
13 * except in compliance with the Licence.  You may obtain a copy of
14 * the Licence at http://www.redhat.com/
15 *
16 * Software distributed under the Licence is distributed on an "AS IS"
17 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.
18 * See the Licence for the specific language governing rights and
19 * limitations under the Licence.
20 *
21 * The Original Code is JFFS2 - Journalling Flash File System, version 2
22 *
23 * Alternatively, the contents of this file may be used under the
24 * terms of the GNU General Public License version 2 (the "GPL"), in
25 * which case the provisions of the GPL are applicable instead of the
26 * above.  If you wish to allow the use of your version of this file
27 * only under the terms of the GPL and not to allow others to use your
28 * version of this file under the RHEPL, indicate your decision by
29 * deleting the provisions above and replace them with the notice and
30 * other provisions required by the GPL.  If you do not delete the
31 * provisions above, a recipient may use your version of this file
32 * under either the RHEPL or the GPL.
33 *
34 * $Id: compr_rubin.c,v 1.1.1.1 2008/10/15 03:27:07 james26_jang Exp $
35 *
36 */
37
38
39#include <linux/string.h>
40#include <linux/types.h>
41#include "compr_rubin.h"
42#include "histo_mips.h"
43
44
45
46void init_rubin(struct rubin_state *rs, int div, int *bits)
47{
48	int c;
49
50	rs->q = 0;
51	rs->p = (long) (2 * UPPER_BIT_RUBIN);
52	rs->bit_number = (long) 0;
53	rs->bit_divider = div;
54	for (c=0; c<8; c++)
55		rs->bits[c] = bits[c];
56}
57
58
59int encode(struct rubin_state *rs, long A, long B, int symbol)
60{
61
62	long i0, i1;
63	int ret;
64
65	while ((rs->q >= UPPER_BIT_RUBIN) || ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) {
66		rs->bit_number++;
67
68		ret = pushbit(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 0);
69		if (ret)
70			return ret;
71		rs->q &= LOWER_BITS_RUBIN;
72		rs->q <<= 1;
73		rs->p <<= 1;
74	}
75	i0 = A * rs->p / (A + B);
76	if (i0 <= 0) {
77		i0 = 1;
78	}
79	if (i0 >= rs->p) {
80		i0 = rs->p - 1;
81	}
82	i1 = rs->p - i0;
83
84	if (symbol == 0)
85		rs->p = i0;
86	else {
87		rs->p = i1;
88		rs->q += i0;
89	}
90	return 0;
91}
92
93
94void end_rubin(struct rubin_state *rs)
95{
96
97	int i;
98
99	for (i = 0; i < RUBIN_REG_SIZE; i++) {
100		pushbit(&rs->pp, (UPPER_BIT_RUBIN & rs->q) ? 1 : 0, 1);
101		rs->q &= LOWER_BITS_RUBIN;
102		rs->q <<= 1;
103	}
104}
105
106
107void init_decode(struct rubin_state *rs, int div, int *bits)
108{
109	init_rubin(rs, div, bits);
110
111	/* behalve lower */
112	rs->rec_q = 0;
113
114	for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE; rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp)))
115		;
116}
117
118static void __do_decode(struct rubin_state *rs, unsigned long p, unsigned long q)
119{
120	register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN;
121	unsigned long rec_q;
122	int c, bits = 0;
123
124	/*
125	 * First, work out how many bits we need from the input stream.
126	 * Note that we have already done the initial check on this
127	 * loop prior to calling this function.
128	 */
129	do {
130		bits++;
131		q &= lower_bits_rubin;
132		q <<= 1;
133		p <<= 1;
134	} while ((q >= UPPER_BIT_RUBIN) || ((p + q) <= UPPER_BIT_RUBIN));
135
136	rs->p = p;
137	rs->q = q;
138
139	rs->bit_number += bits;
140
141	/*
142	 * Now get the bits.  We really want this to be "get n bits".
143	 */
144	rec_q = rs->rec_q;
145	do {
146		c = pullbit(&rs->pp);
147		rec_q &= lower_bits_rubin;
148		rec_q <<= 1;
149		rec_q += c;
150	} while (--bits);
151	rs->rec_q = rec_q;
152}
153
154int decode(struct rubin_state *rs, long A, long B)
155{
156	unsigned long p = rs->p, q = rs->q;
157	long i0, threshold;
158	int symbol;
159
160	if (q >= UPPER_BIT_RUBIN || ((p + q) <= UPPER_BIT_RUBIN))
161		__do_decode(rs, p, q);
162
163	i0 = A * rs->p / (A + B);
164	if (i0 <= 0) {
165		i0 = 1;
166	}
167	if (i0 >= rs->p) {
168		i0 = rs->p - 1;
169	}
170
171	threshold = rs->q + i0;
172	symbol = rs->rec_q >= threshold;
173	if (rs->rec_q >= threshold) {
174		rs->q += i0;
175		i0 = rs->p - i0;
176	}
177
178	rs->p = i0;
179
180	return symbol;
181}
182
183
184
185static int out_byte(struct rubin_state *rs, unsigned char byte)
186{
187	int i, ret;
188	struct rubin_state rs_copy;
189	rs_copy = *rs;
190
191	for (i=0;i<8;i++) {
192		ret = encode(rs, rs->bit_divider-rs->bits[i],rs->bits[i],byte&1);
193		if (ret) {
194			/* Failed. Restore old state */
195			*rs = rs_copy;
196			return ret;
197		}
198		byte=byte>>1;
199	}
200	return 0;
201}
202
203static int in_byte(struct rubin_state *rs)
204{
205	int i, result = 0, bit_divider = rs->bit_divider;
206
207	for (i = 0; i < 8; i++)
208		result |= decode(rs, bit_divider - rs->bits[i], rs->bits[i]) << i;
209
210	return result;
211}
212
213
214
215int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in,
216		      unsigned char *cpage_out, __u32 *sourcelen, __u32 *dstlen)
217	{
218	int outpos = 0;
219	int pos=0;
220	struct rubin_state rs;
221
222	init_pushpull(&rs.pp, cpage_out, *dstlen * 8, 0, 32);
223
224	init_rubin(&rs, bit_divider, bits);
225
226	while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos]))
227		pos++;
228
229	end_rubin(&rs);
230
231	if (outpos > pos) {
232		/* We failed */
233		return -1;
234	}
235
236	/* Tell the caller how much we managed to compress,
237	 * and how much space it took */
238
239	outpos = (pushedbits(&rs.pp)+7)/8;
240
241	if (outpos >= pos)
242		return -1; /* We didn't actually compress */
243	*sourcelen = pos;
244	*dstlen = outpos;
245	return 0;
246}
247int dynrubin_compress(unsigned char *data_in, unsigned char *cpage_out,
248		   __u32 *sourcelen, __u32 *dstlen)
249{
250	int bits[8];
251	unsigned char histo[256];
252	int i;
253	int ret;
254	__u32 mysrclen, mydstlen;
255
256	mysrclen = *sourcelen;
257	mydstlen = *dstlen - 8;
258
259	if (*dstlen <= 12)
260		return -1;
261
262	memset(histo, 0, 256);
263	for (i=0; i<mysrclen; i++) {
264		histo[data_in[i]]++;
265	}
266	memset(bits, 0, sizeof(int)*8);
267	for (i=0; i<256; i++) {
268		if (i&128)
269			bits[7] += histo[i];
270		if (i&64)
271			bits[6] += histo[i];
272		if (i&32)
273			bits[5] += histo[i];
274		if (i&16)
275			bits[4] += histo[i];
276		if (i&8)
277			bits[3] += histo[i];
278		if (i&4)
279			bits[2] += histo[i];
280		if (i&2)
281			bits[1] += histo[i];
282		if (i&1)
283			bits[0] += histo[i];
284	}
285
286	for (i=0; i<8; i++) {
287		bits[i] = (bits[i] * 256) / mysrclen;
288		if (!bits[i]) bits[i] = 1;
289		if (bits[i] > 255) bits[i] = 255;
290		cpage_out[i] = bits[i];
291	}
292
293	ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen, &mydstlen);
294	if (ret)
295		return ret;
296
297	/* Add back the 8 bytes we took for the probabilities */
298	mydstlen += 8;
299
300	if (mysrclen <= mydstlen) {
301		/* We compressed */
302		return -1;
303	}
304
305	*sourcelen = mysrclen;
306	*dstlen = mydstlen;
307	return 0;
308}
309
310void rubin_do_decompress(int bit_divider, int *bits, unsigned char *cdata_in,
311			 unsigned char *page_out, __u32 srclen, __u32 destlen)
312{
313	int outpos = 0;
314	struct rubin_state rs;
315
316	init_pushpull(&rs.pp, cdata_in, srclen, 0, 0);
317	init_decode(&rs, bit_divider, bits);
318
319	while (outpos < destlen) {
320		page_out[outpos++] = in_byte(&rs);
321	}
322}
323
324
325void rubinmips_decompress(unsigned char *data_in, unsigned char *cpage_out,
326		   __u32 sourcelen, __u32 dstlen)
327{
328	rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);
329}
330
331void dynrubin_decompress(unsigned char *data_in, unsigned char *cpage_out,
332		   __u32 sourcelen, __u32 dstlen)
333{
334	int bits[8];
335	int c;
336
337	for (c=0; c<8; c++)
338		bits[c] = data_in[c];
339
340	rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8, dstlen);
341}
342