[linux.git] / fs / jffs2 / compr_rubin.c

/*
 * JFFS2 -- Journalling Flash File System, Version 2.
 *
 * Copyright (C) 2001, 2002 Red Hat, Inc.
 *
 * Created by Arjan van de Ven <[email protected]>
 *
 * For licensing information, see the file 'LICENCE' in this directory.
 *
 * $Id: compr_rubin.c,v 1.20 2004/06/23 16:34:40 havasi Exp $
 *
 */

#include <linux/string.h>
#include <linux/types.h>
#include <linux/jffs2.h>
#include "compr_rubin.h"
#include "histo_mips.h"
#include "compr.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, void *model)
{
	return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);
}
#endif
static int jffs2_dynrubin_compress(unsigned char *data_in,
				   unsigned char *cpage_out,
				   uint32_t *sourcelen, uint32_t *dstlen,
				   void *model)
{
	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);
	}
}


static int jffs2_rubinmips_decompress(unsigned char *data_in,
				      unsigned char *cpage_out,
				      uint32_t sourcelen, uint32_t dstlen,
				      void *model)
{
	rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);
        return 0;
}

static int jffs2_dynrubin_decompress(unsigned char *data_in,
				     unsigned char *cpage_out,
				     uint32_t sourcelen, uint32_t dstlen,
				     void *model)
{
	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);
        return 0;
}

static struct jffs2_compressor jffs2_rubinmips_comp = {
    .priority = JFFS2_RUBINMIPS_PRIORITY,
    .name = "rubinmips",
    .compr = JFFS2_COMPR_DYNRUBIN,
    .compress = NULL, /*&jffs2_rubinmips_compress,*/
    .decompress = &jffs2_rubinmips_decompress,
#ifdef JFFS2_RUBINMIPS_DISABLED
    .disabled = 1,
#else
    .disabled = 0,
#endif
};

int jffs2_rubinmips_init(void)
{
    return jffs2_register_compressor(&jffs2_rubinmips_comp);
}

void jffs2_rubinmips_exit(void)
{
    jffs2_unregister_compressor(&jffs2_rubinmips_comp);
}

static struct jffs2_compressor jffs2_dynrubin_comp = {
    .priority = JFFS2_DYNRUBIN_PRIORITY,
    .name = "dynrubin",
    .compr = JFFS2_COMPR_RUBINMIPS,
    .compress = jffs2_dynrubin_compress,
    .decompress = &jffs2_dynrubin_decompress,
#ifdef JFFS2_DYNRUBIN_DISABLED
    .disabled = 1,
#else
    .disabled = 0,
#endif
};

int jffs2_dynrubin_init(void)
{
    return jffs2_register_compressor(&jffs2_dynrubin_comp);
}

void jffs2_dynrubin_exit(void)
{
    jffs2_unregister_compressor(&jffs2_dynrubin_comp);
}
Commit	Line	Data
1da177e4 LT	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 <[email protected]>
	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	*/
	13
1da177e4 LT	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"
	20
	21	static void init_rubin(struct rubin_state rs, int div, int bits)
182ec4ee	22	{
1da177e4 LT	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	static int encode(struct rubin_state *rs, long A, long B, int symbol)
	35	{
	36
	37	long i0, i1;
	38	int ret;
	39
	40	while ((rs->q >= UPPER_BIT_RUBIN) \|\| ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) {
	41	rs->bit_number++;
182ec4ee	42
1da177e4 LT	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;
	58
	59	if (symbol == 0)
	60	rs->p = i0;
	61	else {
	62	rs->p = i1;
	63	rs->q += i0;
	64	}
	65	return 0;
	66	}
	67
	68
	69	static void end_rubin(struct rubin_state *rs)
182ec4ee	70	{
1da177e4 LT	71
	72	int i;
	73
	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	}
	80
	81
	82	static void init_decode(struct rubin_state rs, int div, int bits)
	83	{
182ec4ee	84	init_rubin(rs, div, bits);
1da177e4 LT	85
	86	/* behalve lower */
	87	rs->rec_q = 0;
	88
	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	}
	92
	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;
	98
	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));
	110
	111	rs->p = p;
	112	rs->q = q;
	113
	114	rs->bit_number += bits;
	115
	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	}
	128
	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;
	134
	135	if (q >= UPPER_BIT_RUBIN \|\| ((p + q) <= UPPER_BIT_RUBIN))
	136	__do_decode(rs, p, q);
	137
	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	}
	145
	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	}
152
153	rs->p = i0;
154
155	return symbol;
156	}
157
158
159
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;
165
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	}
177
178	static int in_byte(struct rubin_state *rs)
179	{
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	return result;
186	}
187
188
189
182ec4ee	190	static int rubin_do_compress(int bit_divider, int bits, unsigned char data_in,
1da177e4 LT	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;
	196
	197	init_pushpull(&rs.pp, cpage_out, dstlen 8, 0, 32);
	198
	199	init_rubin(&rs, bit_divider, bits);
182ec4ee	200
1da177e4 LT	201	while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos]))
1da177e4 LT	202	pos++;
182ec4ee	203
1da177e4 LT	204	end_rubin(&rs);
	205
	206	if (outpos > pos) {
	207	/* We failed */
	208	return -1;
	209	}
182ec4ee TG	210
182ec4ee TG	211	/* Tell the caller how much we managed to compress,
1da177e4	212	* and how much space it took */
182ec4ee	213
1da177e4	214	outpos = (pushedbits(&rs.pp)+7)/8;
182ec4ee	215
1da177e4 LT	216	if (outpos >= pos)
	217	return -1; /* We didn't actually compress */
	218	*sourcelen = pos;
	219	*dstlen = outpos;
	220	return 0;
182ec4ee	221	}
1da177e4 LT	222	#if 0
1da177e4 LT	223	/* _compress returns the compressed size, -1 if bigger */
182ec4ee	224	int jffs2_rubinmips_compress(unsigned char data_in, unsigned char cpage_out,
1da177e4 LT	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
75c96f85 AB	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)
1da177e4 LT	234	{
	235	int bits[8];
	236	unsigned char histo[256];
	237	int i;
	238	int ret;
	239	uint32_t mysrclen, mydstlen;
	240
	241	mysrclen = *sourcelen;
	242	mydstlen = *dstlen - 8;
	243
	244	if (*dstlen <= 12)
	245	return -1;
	246
	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	}
	270
	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	}
	277
	278	ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen, &mydstlen);
182ec4ee	279	if (ret)
1da177e4 LT	280	return ret;
	281
	282	/* Add back the 8 bytes we took for the probabilities */
	283	mydstlen += 8;
	284
	285	if (mysrclen <= mydstlen) {
	286	/* We compressed */
	287	return -1;
	288	}
	289
	290	*sourcelen = mysrclen;
	291	*dstlen = mydstlen;
	292	return 0;
	293	}
	294
182ec4ee	295	static void rubin_do_decompress(int bit_divider, int bits, unsigned char cdata_in,
1da177e4 LT	296	unsigned char *page_out, uint32_t srclen, uint32_t destlen)
	297	{
	298	int outpos = 0;
	299	struct rubin_state rs;
182ec4ee	300
1da177e4 LT	301	init_pushpull(&rs.pp, cdata_in, srclen, 0, 0);
1da177e4 LT	302	init_decode(&rs, bit_divider, bits);
182ec4ee	303
1da177e4 LT	304	while (outpos < destlen) {
	305	page_out[outpos++] = in_byte(&rs);
	306	}
182ec4ee	307	}
1da177e4 LT	308
1da177e4 LT	309
75c96f85 AB	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)
1da177e4 LT	314	{
	315	rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);
	316	return 0;
	317	}
	318
75c96f85 AB	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)
1da177e4 LT	323	{
	324	int bits[8];
	325	int c;
	326
	327	for (c=0; c<8; c++)
	328	bits[c] = data_in[c];
	329
	330	rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8, dstlen);
	331	return 0;
	332	}
	333
	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	};
	346
	347	int jffs2_rubinmips_init(void)
	348	{
	349	return jffs2_register_compressor(&jffs2_rubinmips_comp);
	350	}
	351
	352	void jffs2_rubinmips_exit(void)
	353	{
	354	jffs2_unregister_compressor(&jffs2_rubinmips_comp);
	355	}
	356
	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	};
	369
	370	int jffs2_dynrubin_init(void)
	371	{
	372	return jffs2_register_compressor(&jffs2_dynrubin_comp);
	373	}
	374
	375	void jffs2_dynrubin_exit(void)
	376	{
	377	jffs2_unregister_compressor(&jffs2_dynrubin_comp);
	378	}