[J-u-boot.git] / fs / jffs2 / compr_lzari.c

/*
 * JFFS2 -- Journalling Flash File System, Version 2.
 *
 * Copyright (C) 2004 Patrik Kluba,
 *                    University of Szeged, Hungary
 *
 * For licensing information, see the file 'LICENCE' in the
 * jffs2 directory.
 *
 * $Id: compr_lzari.c,v 1.3 2004/06/23 16:34:39 havasi Exp $
 *
 */

/*
   Lempel-Ziv-Arithmetic coding compression module for jffs2
   Based on the LZARI source included in LDS (lossless datacompression sources)
*/

/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */

/*
Original copyright follows:

**************************************************************
	LZARI.C -- A Data Compression Program
	(tab = 4 spaces)
**************************************************************
	4/7/1989 Haruhiko Okumura
	Use, distribute, and modify this program freely.
	Please send me your improved versions.
		PC-VAN		SCIENCE
		NIFTY-Serve	PAF01022
		CompuServe	74050,1022
**************************************************************

LZARI.C (c)1989 by Haruyasu Yoshizaki, Haruhiko Okumura, and Kenji Rikitake.
All rights reserved. Permission granted for non-commercial use.

*/

/*

	2004-02-18  pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu>
				Removed unused variables and fixed no return value

	2004-02-16  pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu>
				Initial release

*/


#include <config.h>
#if ((CONFIG_COMMANDS & CFG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO_LZARI))

#include <linux/stddef.h>
#include <jffs2/jffs2.h>


#define N			4096	/* size of ring buffer */
#define F			60	/* upper limit for match_length */
#define THRESHOLD		2	/* encode string into position and length
					   if match_length is greater than this */
#define NIL			N	/* index for root of binary search trees */

static unsigned char
		text_buf[N + F - 1];	/* ring buffer of size N,
			with extra F-1 bytes to facilitate string comparison */

/********** Arithmetic Compression **********/

/*  If you are not familiar with arithmetic compression, you should read
		I. E. Witten, R. M. Neal, and J. G. Cleary,
			Communications of the ACM, Vol. 30, pp. 520-540 (1987),
	from which much have been borrowed.  */

#define M   15

/*	Q1 (= 2 to the M) must be sufficiently large, but not so
	large as the unsigned long 4 * Q1 * (Q1 - 1) overflows.  */

#define Q1  (1UL << M)
#define Q2  (2 * Q1)
#define Q3  (3 * Q1)
#define Q4  (4 * Q1)
#define MAX_CUM (Q1 - 1)

#define N_CHAR  (256 - THRESHOLD + F)
	/* character code = 0, 1, ..., N_CHAR - 1 */

static unsigned long char_to_sym[N_CHAR], sym_to_char[N_CHAR + 1];
static unsigned long
	sym_freq[N_CHAR + 1],  /* frequency for symbols */
	sym_cum[N_CHAR + 1],   /* cumulative freq for symbols */
	position_cum[N + 1];   /* cumulative freq for positions */

static void StartModel(void)  /* Initialize model */
{
	unsigned long ch, sym, i;

	sym_cum[N_CHAR] = 0;
	for (sym = N_CHAR; sym >= 1; sym--) {
		ch = sym - 1;
		char_to_sym[ch] = sym;  sym_to_char[sym] = ch;
		sym_freq[sym] = 1;
		sym_cum[sym - 1] = sym_cum[sym] + sym_freq[sym];
	}
	sym_freq[0] = 0;  /* sentinel (!= sym_freq[1]) */
	position_cum[N] = 0;
	for (i = N; i >= 1; i--)
		position_cum[i - 1] = position_cum[i] + 10000 / (i + 200);
			/* empirical distribution function (quite tentative) */
			/* Please devise a better mechanism! */
}

static void UpdateModel(unsigned long sym)
{
	unsigned long c, ch_i, ch_sym;
	unsigned long i;
	if (sym_cum[0] >= MAX_CUM) {
		c = 0;
		for (i = N_CHAR; i > 0; i--) {
			sym_cum[i] = c;
			c += (sym_freq[i] = (sym_freq[i] + 1) >> 1);
		}
		sym_cum[0] = c;
	}
	for (i = sym; sym_freq[i] == sym_freq[i - 1]; i--) ;
	if (i < sym) {
		ch_i = sym_to_char[i];    ch_sym = sym_to_char[sym];
		sym_to_char[i] = ch_sym;  sym_to_char[sym] = ch_i;
		char_to_sym[ch_i] = sym;  char_to_sym[ch_sym] = i;
	}
	sym_freq[i]++;
	while (--i > 0) sym_cum[i]++;
	sym_cum[0]++;
}

static unsigned long BinarySearchSym(unsigned long x)
	/* 1      if x >= sym_cum[1],
	   N_CHAR if sym_cum[N_CHAR] > x,
	   i such that sym_cum[i - 1] > x >= sym_cum[i] otherwise */
{
	unsigned long i, j, k;

	i = 1;  j = N_CHAR;
	while (i < j) {
		k = (i + j) / 2;
		if (sym_cum[k] > x) i = k + 1;  else j = k;
	}
	return i;
}

unsigned long BinarySearchPos(unsigned long x)
	/* 0 if x >= position_cum[1],
	   N - 1 if position_cum[N] > x,
	   i such that position_cum[i] > x >= position_cum[i + 1] otherwise */
{
	unsigned long i, j, k;

	i = 1;  j = N;
	while (i < j) {
		k = (i + j) / 2;
		if (position_cum[k] > x) i = k + 1;  else j = k;
	}
	return i - 1;
}

static int Decode(unsigned char *srcbuf, unsigned char *dstbuf, unsigned long srclen,
					unsigned long dstlen)	/* Just the reverse of Encode(). */
{
	unsigned long i, r, j, k, c, range, sym;
	unsigned char *ip, *op;
	unsigned char *srcend = srcbuf + srclen;
	unsigned char *dstend = dstbuf + dstlen;
	unsigned char buffer = 0;
	unsigned char mask = 0;
	unsigned long low = 0;
	unsigned long high = Q4;
	unsigned long value = 0;

	ip = srcbuf;
	op = dstbuf;
	for (i = 0; i < M + 2; i++) {
		value *= 2;
		if ((mask >>= 1) == 0) {
			buffer = (ip >= srcend) ? 0 : *(ip++);
			mask = 128;
		}
		value += ((buffer & mask) != 0);
	}

	StartModel();
	for (i = 0; i < N - F; i++) text_buf[i] = ' ';
	r = N - F;

	while (op < dstend) {
		range = high - low;
		sym = BinarySearchSym((unsigned long)
				(((value - low + 1) * sym_cum[0] - 1) / range));
		high = low + (range * sym_cum[sym - 1]) / sym_cum[0];
		low +=       (range * sym_cum[sym    ]) / sym_cum[0];
		for ( ; ; ) {
			if (low >= Q2) {
				value -= Q2;  low -= Q2;  high -= Q2;
			} else if (low >= Q1 && high <= Q3) {
				value -= Q1;  low -= Q1;  high -= Q1;
			} else if (high > Q2) break;
			low += low;  high += high;
			value *= 2;
			if ((mask >>= 1) == 0) {
				buffer = (ip >= srcend) ? 0 : *(ip++);
				mask = 128;
			}
			value += ((buffer & mask) != 0);
		}
		c = sym_to_char[sym];
		UpdateModel(sym);
		if (c < 256) {
			if (op >= dstend) return -1;
			*(op++) = c;
			text_buf[r++] = c;
			r &= (N - 1);
		} else {
			j = c - 255 + THRESHOLD;
			range = high - low;
			i = BinarySearchPos((unsigned long)
				(((value - low + 1) * position_cum[0] - 1) / range));
			high = low + (range * position_cum[i    ]) / position_cum[0];
			low +=       (range * position_cum[i + 1]) / position_cum[0];
			for ( ; ; ) {
				if (low >= Q2) {
					value -= Q2;  low -= Q2;  high -= Q2;
				} else if (low >= Q1 && high <= Q3) {
					value -= Q1;  low -= Q1;  high -= Q1;
				} else if (high > Q2) break;
				low += low;  high += high;
				value *= 2;
				if ((mask >>= 1) == 0) {
					buffer = (ip >= srcend) ? 0 : *(ip++);
					mask = 128;
				}
				value += ((buffer & mask) != 0);
			}
			i = (r - i - 1) & (N - 1);
			for (k = 0; k < j; k++) {
				c = text_buf[(i + k) & (N - 1)];
				if (op >= dstend) return -1;
				*(op++) = c;
				text_buf[r++] = c;
				r &= (N - 1);
			}
		}
	}
	return 0;
}

int lzari_decompress(unsigned char *data_in, unsigned char *cpage_out,
		      u32 srclen, u32 destlen)
{
    return Decode(data_in, cpage_out, srclen, destlen);
}
#endif /* ((CONFIG_COMMANDS & CFG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO_LZARI)) */
Commit	Line	Data
07cc0999 WD	1	/*
	2	* JFFS2 -- Journalling Flash File System, Version 2.
	3	*
	4	* Copyright (C) 2004 Patrik Kluba,
	5	* University of Szeged, Hungary
	6	*
	7	* For licensing information, see the file 'LICENCE' in the
	8	* jffs2 directory.
	9	*
	10	* $Id: compr_lzari.c,v 1.3 2004/06/23 16:34:39 havasi Exp $
	11	*
	12	*/
	13
	14	/*
	15	Lempel-Ziv-Arithmetic coding compression module for jffs2
	16	Based on the LZARI source included in LDS (lossless datacompression sources)
	17	*/
	18
	19	/* -- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -- */
	20
	21	/*
	22	Original copyright follows:
	23
	24	**************************************************************
	25	LZARI.C -- A Data Compression Program
	26	(tab = 4 spaces)
	27	**************************************************************
	28	4/7/1989 Haruhiko Okumura
	29	Use, distribute, and modify this program freely.
	30	Please send me your improved versions.
	31	PC-VAN SCIENCE
	32	NIFTY-Serve PAF01022
	33	CompuServe 74050,1022
	34	**************************************************************
	35
	36	LZARI.C (c)1989 by Haruyasu Yoshizaki, Haruhiko Okumura, and Kenji Rikitake.
	37	All rights reserved. Permission granted for non-commercial use.
	38
	39	*/
	40
	41	/*
	42
	43	2004-02-18 pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu>
	44	Removed unused variables and fixed no return value
	45
	46	2004-02-16 pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu>
	47	Initial release
	48
	49	*/
	50
	51
	52	#include <config.h>
412babe3	53	#if ((CONFIG_COMMANDS & CFG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO_LZARI))
07cc0999 WD	54
	55	#include <linux/stddef.h>
	56	#include <jffs2/jffs2.h>
	57
	58
	59	#define N 4096 /* size of ring buffer */
	60	#define F 60 /* upper limit for match_length */
	61	#define THRESHOLD 2 /* encode string into position and length
	62	if match_length is greater than this */
	63	#define NIL N /* index for root of binary search trees */
	64
	65	static unsigned char
	66	text_buf[N + F - 1]; /* ring buffer of size N,
	67	with extra F-1 bytes to facilitate string comparison */
	68
	69	/******** Arithmetic Compression ********/
	70
	71	/* If you are not familiar with arithmetic compression, you should read
	72	I. E. Witten, R. M. Neal, and J. G. Cleary,
	73	Communications of the ACM, Vol. 30, pp. 520-540 (1987),
	74	from which much have been borrowed. */
	75
	76	#define M 15
	77
	78	/* Q1 (= 2 to the M) must be sufficiently large, but not so
	79	large as the unsigned long 4 * Q1 * (Q1 - 1) overflows. */
	80
	81	#define Q1 (1UL << M)
	82	#define Q2 (2 * Q1)
	83	#define Q3 (3 * Q1)
	84	#define Q4 (4 * Q1)
	85	#define MAX_CUM (Q1 - 1)
	86
	87	#define N_CHAR (256 - THRESHOLD + F)
	88	/* character code = 0, 1, ..., N_CHAR - 1 */
	89
	90	static unsigned long char_to_sym[N_CHAR], sym_to_char[N_CHAR + 1];
	91	static unsigned long
	92	sym_freq[N_CHAR + 1], /* frequency for symbols */
	93	sym_cum[N_CHAR + 1], /* cumulative freq for symbols */
	94	position_cum[N + 1]; /* cumulative freq for positions */
	95
	96	static void StartModel(void) /* Initialize model */
	97	{
	98	unsigned long ch, sym, i;
	99
	100	sym_cum[N_CHAR] = 0;
	101	for (sym = N_CHAR; sym >= 1; sym--) {
	102	ch = sym - 1;
	103	char_to_sym[ch] = sym; sym_to_char[sym] = ch;
	104	sym_freq[sym] = 1;
	105	sym_cum[sym - 1] = sym_cum[sym] + sym_freq[sym];
	106	}
	107	sym_freq[0] = 0; /* sentinel (!= sym_freq[1]) */
	108	position_cum[N] = 0;
	109	for (i = N; i >= 1; i--)
	110	position_cum[i - 1] = position_cum[i] + 10000 / (i + 200);
	111	/* empirical distribution function (quite tentative) */
	112	/* Please devise a better mechanism! */
	113	}
	114
	115	static void UpdateModel(unsigned long sym)
	116	{
	117	unsigned long c, ch_i, ch_sym;
118	unsigned long i;
119	if (sym_cum[0] >= MAX_CUM) {
120	c = 0;
121	for (i = N_CHAR; i > 0; i--) {
122	sym_cum[i] = c;
123	c += (sym_freq[i] = (sym_freq[i] + 1) >> 1);
124	}
125	sym_cum[0] = c;
126	}
127	for (i = sym; sym_freq[i] == sym_freq[i - 1]; i--) ;
128	if (i < sym) {
129	ch_i = sym_to_char[i]; ch_sym = sym_to_char[sym];
130	sym_to_char[i] = ch_sym; sym_to_char[sym] = ch_i;
131	char_to_sym[ch_i] = sym; char_to_sym[ch_sym] = i;
132	}
133	sym_freq[i]++;
134	while (--i > 0) sym_cum[i]++;
135	sym_cum[0]++;
136	}
137
138	static unsigned long BinarySearchSym(unsigned long x)
139	/* 1 if x >= sym_cum[1],
140	N_CHAR if sym_cum[N_CHAR] > x,
141	i such that sym_cum[i - 1] > x >= sym_cum[i] otherwise */
142	{
143	unsigned long i, j, k;
144
145	i = 1; j = N_CHAR;
146	while (i < j) {
147	k = (i + j) / 2;
148	if (sym_cum[k] > x) i = k + 1; else j = k;
149	}
150	return i;
151	}
152
153	unsigned long BinarySearchPos(unsigned long x)
154	/* 0 if x >= position_cum[1],
155	N - 1 if position_cum[N] > x,
156	i such that position_cum[i] > x >= position_cum[i + 1] otherwise */
157	{
158	unsigned long i, j, k;
159
160	i = 1; j = N;
161	while (i < j) {
162	k = (i + j) / 2;
163	if (position_cum[k] > x) i = k + 1; else j = k;
164	}
165	return i - 1;
166	}
167
168	static int Decode(unsigned char srcbuf, unsigned char dstbuf, unsigned long srclen,
169	unsigned long dstlen) /* Just the reverse of Encode(). */
170	{
171	unsigned long i, r, j, k, c, range, sym;
172	unsigned char ip, op;
173	unsigned char *srcend = srcbuf + srclen;
174	unsigned char *dstend = dstbuf + dstlen;
175	unsigned char buffer = 0;
176	unsigned char mask = 0;
177	unsigned long low = 0;
178	unsigned long high = Q4;
179	unsigned long value = 0;
180
181	ip = srcbuf;
182	op = dstbuf;
183	for (i = 0; i < M + 2; i++) {
184	value *= 2;
185	if ((mask >>= 1) == 0) {
186	buffer = (ip >= srcend) ? 0 : *(ip++);
187	mask = 128;
188	}
189	value += ((buffer & mask) != 0);
190	}
191
192	StartModel();
193	for (i = 0; i < N - F; i++) text_buf[i] = ' ';
194	r = N - F;
195
196	while (op < dstend) {
197	range = high - low;
198	sym = BinarySearchSym((unsigned long)
199	(((value - low + 1) * sym_cum[0] - 1) / range));
200	high = low + (range * sym_cum[sym - 1]) / sym_cum[0];
201	low += (range * sym_cum[sym ]) / sym_cum[0];
202	for ( ; ; ) {
203	if (low >= Q2) {
204	value -= Q2; low -= Q2; high -= Q2;
205	} else if (low >= Q1 && high <= Q3) {
206	value -= Q1; low -= Q1; high -= Q1;
207	} else if (high > Q2) break;
208	low += low; high += high;
209	value *= 2;
210	if ((mask >>= 1) == 0) {
211	buffer = (ip >= srcend) ? 0 : *(ip++);
212	mask = 128;
213	}
214	value += ((buffer & mask) != 0);
215	}
216	c = sym_to_char[sym];
217	UpdateModel(sym);
218	if (c < 256) {
219	if (op >= dstend) return -1;
220	*(op++) = c;
221	text_buf[r++] = c;
222	r &= (N - 1);
223	} else {
224	j = c - 255 + THRESHOLD;
225	range = high - low;
226	i = BinarySearchPos((unsigned long)
227	(((value - low + 1) * position_cum[0] - 1) / range));
228	high = low + (range * position_cum[i ]) / position_cum[0];
229	low += (range * position_cum[i + 1]) / position_cum[0];
230	for ( ; ; ) {
231	if (low >= Q2) {
232	value -= Q2; low -= Q2; high -= Q2;
233	} else if (low >= Q1 && high <= Q3) {
234	value -= Q1; low -= Q1; high -= Q1;
235	} else if (high > Q2) break;
236	low += low; high += high;
237	value *= 2;
238	if ((mask >>= 1) == 0) {
239	buffer = (ip >= srcend) ? 0 : *(ip++);
240	mask = 128;
241	}
242	value += ((buffer & mask) != 0);
243	}
244	i = (r - i - 1) & (N - 1);
245	for (k = 0; k < j; k++) {
246	c = text_buf[(i + k) & (N - 1)];
247	if (op >= dstend) return -1;
248	*(op++) = c;
249	text_buf[r++] = c;
250	r &= (N - 1);
251	}
252	}
253	}
254	return 0;
255	}
256
257	int lzari_decompress(unsigned char data_in, unsigned char cpage_out,
258	u32 srclen, u32 destlen)
259	{
260	return Decode(data_in, cpage_out, srclen, destlen);
261	}
412babe3	262	#endif /* ((CONFIG_COMMANDS & CFG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO_LZARI)) */