embox

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.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 <fs/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
	int c;
24

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
	}
32
}
33

34

35
static int encode(struct rubin_state *rs, long A, long B, int symbol) {
36

37
	long i0, i1;
38
	int ret;
39

40
	while ((rs->q >= UPPER_BIT_RUBIN) ||
41
			((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
		}
48
		rs->q &= LOWER_BITS_RUBIN;
49
		rs->q <<= 1;
50
		rs->p <<= 1;
51
	}
52
	i0 = A * rs->p / (A + B);
53
	if (i0 <= 0) {
54
		i0 = 1;
55
	}
56
	if (i0 >= rs->p) {
57
		i0 = rs->p - 1;
58
	}
59
	i1 = rs->p - i0;
60

61
	if (symbol == 0) {
62
		rs->p = i0;
63
	} else {
64
		rs->p = i1;
65
		rs->q += i0;
66
	}
67
	return 0;
68
}
69

70

71
static void end_rubin(struct rubin_state *rs) {
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
	init_rubin(rs, div, bits);
85

86
	/* behalve lower */
87
	rs->rec_q = 0;
88

89
	for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE;
90
			rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp))) {
91
		;
92
	}
93
}
94

95
static void __do_decode(struct rubin_state *rs,
96
							unsigned long p, unsigned long q) {
97
	register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN;
98
	unsigned long rec_q;
99
	int c, bits = 0;
100

101
	/*
102
	 * First, work out how many bits we need from the input stream.
103
	 * Note that we have already done the initial check on this
104
	 * loop prior to calling this function.
105
	 */
106
	do {
107
		bits++;
108
		q &= lower_bits_rubin;
109
		q <<= 1;
110
		p <<= 1;
111
	} while ((q >= UPPER_BIT_RUBIN) || ((p + q) <= UPPER_BIT_RUBIN));
112

113
	rs->p = p;
114
	rs->q = q;
115

116
	rs->bit_number += bits;
117

118
	/*
119
	 * Now get the bits.  We really want this to be "get n bits".
120
	 */
121
	rec_q = rs->rec_q;
122
	do {
123
		c = pullbit(&rs->pp);
124
		rec_q &= lower_bits_rubin;
125
		rec_q <<= 1;
126
		rec_q += c;
127
	} while (--bits);
128
	rs->rec_q = rec_q;
129
}
130

131
static int decode(struct rubin_state *rs, long A, long B) {
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

140
	i0 = A * rs->p / (A + B);
141
	if (i0 <= 0) {
142
		i0 = 1;
143
	}
144
	if (i0 >= rs->p) {
145
		i0 = rs->p - 1;
146
	}
147

148
	threshold = rs->q + i0;
149
	symbol = rs->rec_q >= threshold;
150
	if (rs->rec_q >= threshold) {
151
		rs->q += i0;
152
		i0 = rs->p - i0;
153
	}
154

155
	rs->p = i0;
156

157
	return symbol;
158
}
159

160

161

162
static int out_byte(struct rubin_state *rs, unsigned char byte) {
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
	int i, result = 0, bit_divider = rs->bit_divider;
181

182
	for (i = 0; i < 8; i++) {
183
		result |= decode(rs, bit_divider - rs->bits[i], rs->bits[i]) << i;
184
	}
185

186
	return result;
187
}
188

189

190

191
static int rubin_do_compress(int bit_divider, int *bits,
192
		unsigned char *data_in,unsigned char *cpage_out,
193
				uint32_t *sourcelen, uint32_t *dstlen) {
194
	int outpos = 0;
195
	int pos=0;
196
	struct rubin_state rs;
197

198
	init_pushpull(&rs.pp, (char *) 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

206
	end_rubin(&rs);
207

208
	if (outpos > pos) {
209
		/* We failed */
210
		return -1;
211
	}
212

213
	/* Tell the caller how much we managed to compress,
214
	 * and how much space it took */
215

216
	outpos = (pushedbits(&rs.pp)+7)/8;
217

218
	if (outpos >= pos) {
219
		return -1; /* We didn't actually compress */
220
	}
221
	*sourcelen = pos;
222
	*dstlen = outpos;
223
	return 0;
224
}
225

226
static int jffs2_dynrubin_compress(unsigned char *data_in,
227
				   unsigned char *cpage_out,
228
				   uint32_t *sourcelen, uint32_t *dstlen,
229
				   void *model) {
230
	int bits[8];
231
	unsigned char histo[256];
232
	int i;
233
	int ret;
234
	uint32_t mysrclen, mydstlen;
235

236
	mysrclen = *sourcelen;
237
	mydstlen = *dstlen - 8;
238

239
	if (*dstlen <= 12) {
240
		return -1;
241
	}
242

243
	memset(histo, 0, 256);
244
	for (i=0; i<mysrclen; i++) {
245
		histo[data_in[i]]++;
246
	}
247
	memset(bits, 0, sizeof(int)*8);
248
	for (i=0; i<256; i++) {
249
		if (i&128) {
250
			bits[7] += histo[i];
251
		}
252
		if (i&64) {
253
			bits[6] += histo[i];
254
		}
255
		if (i&32) {
256
			bits[5] += histo[i];
257
		}
258
		if (i&16) {
259
			bits[4] += histo[i];
260
		}
261
		if (i&8) {
262
			bits[3] += histo[i];
263
		}
264
		if (i&4) {
265
			bits[2] += histo[i];
266
		}
267
		if (i&2) {
268
			bits[1] += histo[i];
269
		}
270
		if (i&1) {
271
			bits[0] += histo[i];
272
		}
273
	}
274

275
	for (i=0; i<8; i++) {
276
		bits[i] = (bits[i] * 256) / mysrclen;
277
		if (!bits[i]) {
278
			bits[i] = 1;
279
		}
280
		if (bits[i] > 255) {
281
			bits[i] = 255;
282
		}
283
		cpage_out[i] = bits[i];
284
	}
285

286
	ret = rubin_do_compress(256, bits,
287
			data_in, cpage_out+8, &mysrclen, &mydstlen);
288
	if (ret) {
289
		return ret;
290
	}
291

292
	/* Add back the 8 bytes we took for the probabilities */
293
	mydstlen += 8;
294

295
	if (mysrclen <= mydstlen) {
296
		/* We compressed */
297
		return -1;
298
	}
299

300
	*sourcelen = mysrclen;
301
	*dstlen = mydstlen;
302
	return 0;
303
}
304

305
static void rubin_do_decompress(int bit_divider, int *bits,
306
		unsigned char *cdata_in, unsigned char *page_out,
307
						uint32_t srclen, uint32_t destlen) {
308
	int outpos = 0;
309
	struct rubin_state rs;
310

311
	init_pushpull(&rs.pp, (char *) cdata_in, srclen, 0, 0);
312
	init_decode(&rs, bit_divider, bits);
313

314
	while (outpos < destlen) {
315
		page_out[outpos++] = in_byte(&rs);
316
	}
317
}
318

319

320
static int jffs2_rubinmips_decompress(unsigned char *data_in,
321
				      unsigned char *cpage_out,
322
				      uint32_t sourcelen, uint32_t dstlen,
323
				      void *model) {
324
	rubin_do_decompress(BIT_DIVIDER_MIPS,
325
			bits_mips, data_in, cpage_out, sourcelen, dstlen);
326
    return 0;
327
}
328

329
static int jffs2_dynrubin_decompress(unsigned char *data_in,
330
				     unsigned char *cpage_out,
331
				     uint32_t sourcelen, uint32_t dstlen,
332
				     void *model) {
333
	int bits[8];
334
	int c;
335

336
	for (c=0; c<8; c++) {
337
		bits[c] = data_in[c];
338
	}
339

340
	rubin_do_decompress(256, bits,
341
			data_in+8, cpage_out, sourcelen-8, dstlen);
342
        return 0;
343
}
344

345
static struct jffs2_compressor jffs2_rubinmips_comp = {
346
    .priority = JFFS2_RUBINMIPS_PRIORITY,
347
    .name = "rubinmips",
348
    .compr = JFFS2_COMPR_DYNRUBIN,
349
    .compress = NULL, /*&jffs2_rubinmips_compress,*/
350
    .decompress = &jffs2_rubinmips_decompress,
351
#ifdef JFFS2_RUBINMIPS_DISABLED
352
    .disabled = 1,
353
#else
354
    .disabled = 0,
355
#endif
356
};
357

358
int jffs2_rubinmips_init(void) {
359
    return jffs2_register_compressor(&jffs2_rubinmips_comp);
360
}
361

362
void jffs2_rubinmips_exit(void) {
363
    jffs2_unregister_compressor(&jffs2_rubinmips_comp);
364
}
365

366
static struct jffs2_compressor jffs2_dynrubin_comp = {
367
    .priority = JFFS2_DYNRUBIN_PRIORITY,
368
    .name = "dynrubin",
369
    .compr = JFFS2_COMPR_RUBINMIPS,
370
    .compress = jffs2_dynrubin_compress,
371
    .decompress = &jffs2_dynrubin_decompress,
372
#ifdef JFFS2_DYNRUBIN_DISABLED
373
    .disabled = 1,
374
#else
375
    .disabled = 0,
376
#endif
377
};
378

379
int jffs2_dynrubin_init(void) {
380
    return jffs2_register_compressor(&jffs2_dynrubin_comp);
381
}
382

383
void jffs2_dynrubin_exit(void) {
384
    jffs2_unregister_compressor(&jffs2_dynrubin_comp);
385
}
386