diff options
author | wdenk <wdenk> | 2005-05-05 00:04:14 +0000 |
---|---|---|
committer | wdenk <wdenk> | 2005-05-05 00:04:14 +0000 |
commit | 07cc0999413481568b38b8d0e5f3d7514d9540b0 (patch) | |
tree | 56955f165a6a1c2647acbaaa8f5783b3b74277c9 /fs | |
parent | cf8bc5773c27adf325d7bb1a90d290b213a57417 (diff) |
Major upate of JFFS2 code; now in sync with snapshot of MTD CVS of
March 13, 2005); new configuration options CONFIG_JFFS2_LZO and
CONFIG_JFFS2_LZARI are added. Both are undefined by default.
Diffstat (limited to 'fs')
-rw-r--r-- | fs/jffs2/Makefile | 1 | ||||
-rw-r--r-- | fs/jffs2/compr_lzari.c | 262 | ||||
-rw-r--r-- | fs/jffs2/compr_lzo.c | 405 | ||||
-rw-r--r-- | fs/jffs2/jffs2_1pass.c | 18 |
4 files changed, 685 insertions, 1 deletions
diff --git a/fs/jffs2/Makefile b/fs/jffs2/Makefile index 10fbf7c2cf9..f28b17a414c 100644 --- a/fs/jffs2/Makefile +++ b/fs/jffs2/Makefile @@ -27,6 +27,7 @@ LIB = libjffs2.a AOBJS = COBJS = jffs2_1pass.o compr_rtime.o compr_rubin.o compr_zlib.o mini_inflate.o +COBJS += compr_lzo.o compr_lzari.o OBJS = $(AOBJS) $(COBJS) #CPPFLAGS += diff --git a/fs/jffs2/compr_lzari.c b/fs/jffs2/compr_lzari.c new file mode 100644 index 00000000000..a6a708bcd64 --- /dev/null +++ b/fs/jffs2/compr_lzari.c @@ -0,0 +1,262 @@ +/* + * 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_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_LZARI)) */ diff --git a/fs/jffs2/compr_lzo.c b/fs/jffs2/compr_lzo.c new file mode 100644 index 00000000000..e97c18f51e4 --- /dev/null +++ b/fs/jffs2/compr_lzo.c @@ -0,0 +1,405 @@ +/* + * 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_lzo.c,v 1.3 2004/06/23 16:34:39 havasi Exp $ + * + */ + +/* + LZO1X-1 (and -999) compression module for jffs2 + based on the original LZO sources +*/ + +/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */ + +/* + Original copyright notice follows: + + lzo1x_9x.c -- implementation of the LZO1X-999 compression algorithm + lzo_ptr.h -- low-level pointer constructs + lzo_swd.ch -- sliding window dictionary + lzoconf.h -- configuration for the LZO real-time data compression library + lzo_mchw.ch -- matching functions using a window + minilzo.c -- mini subset of the LZO real-time data compression library + config1x.h -- configuration for the LZO1X algorithm + lzo1x.h -- public interface of the LZO1X compression algorithm + + These files are part of the LZO real-time data compression library. + + Copyright (C) 1996-2002 Markus Franz Xaver Johannes Oberhumer + All Rights Reserved. + + The LZO library is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of + the License, or (at your option) any later version. + + The LZO library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with the LZO library; see the file COPYING. + If not, write to the Free Software Foundation, Inc., + 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + + Markus F.X.J. Oberhumer + <markus@oberhumer.com> +*/ + +/* + + 2004-02-16 pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu> + Initial release + -removed all 16 bit code + -all sensitive data will be on 4 byte boundary + -removed check parts for library use + -removed all but LZO1X-* compression + +*/ + + +#include <config.h> +#if ((CONFIG_COMMANDS & CFG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO)) + +#include <linux/stddef.h> +#include <jffs2/jffs2.h> +#include <jffs2/compr_rubin.h> + +/* Integral types that have *exactly* the same number of bits as a lzo_voidp */ +typedef unsigned long lzo_ptr_t; +typedef long lzo_sptr_t; + +/* data type definitions */ +#define U32 unsigned long +#define S32 signed long +#define I32 long +#define U16 unsigned short +#define S16 signed short +#define I16 short +#define U8 unsigned char +#define S8 signed char +#define I8 char + +#define M1_MAX_OFFSET 0x0400 +#define M2_MAX_OFFSET 0x0800 +#define M3_MAX_OFFSET 0x4000 +#define M4_MAX_OFFSET 0xbfff + +#define __COPY4(dst,src) * (lzo_uint32p)(dst) = * (const lzo_uint32p)(src) +#define COPY4(dst,src) __COPY4((lzo_ptr_t)(dst),(lzo_ptr_t)(src)) + +#define TEST_IP (ip < ip_end) +#define TEST_OP (op <= op_end) + +#define NEED_IP(x) \ + if ((lzo_uint)(ip_end - ip) < (lzo_uint)(x)) goto input_overrun +#define NEED_OP(x) \ + if ((lzo_uint)(op_end - op) < (lzo_uint)(x)) goto output_overrun +#define TEST_LOOKBEHIND(m_pos,out) if (m_pos < out) goto lookbehind_overrun + +typedef U32 lzo_uint32; +typedef I32 lzo_int32; +typedef U32 lzo_uint; +typedef I32 lzo_int; +typedef int lzo_bool; + +#define lzo_byte U8 +#define lzo_bytep U8 * +#define lzo_charp char * +#define lzo_voidp void * +#define lzo_shortp short * +#define lzo_ushortp unsigned short * +#define lzo_uint32p lzo_uint32 * +#define lzo_int32p lzo_int32 * +#define lzo_uintp lzo_uint * +#define lzo_intp lzo_int * +#define lzo_voidpp lzo_voidp * +#define lzo_bytepp lzo_bytep * +#define lzo_sizeof_dict_t sizeof(lzo_bytep) + +#define LZO_E_OK 0 +#define LZO_E_ERROR (-1) +#define LZO_E_OUT_OF_MEMORY (-2) /* not used right now */ +#define LZO_E_NOT_COMPRESSIBLE (-3) /* not used right now */ +#define LZO_E_INPUT_OVERRUN (-4) +#define LZO_E_OUTPUT_OVERRUN (-5) +#define LZO_E_LOOKBEHIND_OVERRUN (-6) +#define LZO_E_EOF_NOT_FOUND (-7) +#define LZO_E_INPUT_NOT_CONSUMED (-8) + +#define PTR(a) ((lzo_ptr_t) (a)) +#define PTR_LINEAR(a) PTR(a) +#define PTR_ALIGNED_4(a) ((PTR_LINEAR(a) & 3) == 0) +#define PTR_ALIGNED_8(a) ((PTR_LINEAR(a) & 7) == 0) +#define PTR_ALIGNED2_4(a,b) (((PTR_LINEAR(a) | PTR_LINEAR(b)) & 3) == 0) +#define PTR_ALIGNED2_8(a,b) (((PTR_LINEAR(a) | PTR_LINEAR(b)) & 7) == 0) +#define PTR_LT(a,b) (PTR(a) < PTR(b)) +#define PTR_GE(a,b) (PTR(a) >= PTR(b)) +#define PTR_DIFF(a,b) ((lzo_ptrdiff_t) (PTR(a) - PTR(b))) +#define pd(a,b) ((lzo_uint) ((a)-(b))) + +typedef ptrdiff_t lzo_ptrdiff_t; + +static int +lzo1x_decompress (const lzo_byte * in, lzo_uint in_len, + lzo_byte * out, lzo_uintp out_len, lzo_voidp wrkmem) +{ + register lzo_byte *op; + register const lzo_byte *ip; + register lzo_uint t; + + register const lzo_byte *m_pos; + + const lzo_byte *const ip_end = in + in_len; + lzo_byte *const op_end = out + *out_len; + + *out_len = 0; + + op = out; + ip = in; + + if (*ip > 17) + { + t = *ip++ - 17; + if (t < 4) + goto match_next; + NEED_OP (t); + NEED_IP (t + 1); + do + *op++ = *ip++; + while (--t > 0); + goto first_literal_run; + } + + while (TEST_IP && TEST_OP) + { + t = *ip++; + if (t >= 16) + goto match; + if (t == 0) + { + NEED_IP (1); + while (*ip == 0) + { + t += 255; + ip++; + NEED_IP (1); + } + t += 15 + *ip++; + } + NEED_OP (t + 3); + NEED_IP (t + 4); + if (PTR_ALIGNED2_4 (op, ip)) + { + COPY4 (op, ip); + + op += 4; + ip += 4; + if (--t > 0) + { + if (t >= 4) + { + do + { + COPY4 (op, ip); + op += 4; + ip += 4; + t -= 4; + } + while (t >= 4); + if (t > 0) + do + *op++ = *ip++; + while (--t > 0); + } + else + do + *op++ = *ip++; + while (--t > 0); + } + } + else + { + *op++ = *ip++; + *op++ = *ip++; + *op++ = *ip++; + do + *op++ = *ip++; + while (--t > 0); + } + first_literal_run: + + t = *ip++; + if (t >= 16) + goto match; + + m_pos = op - (1 + M2_MAX_OFFSET); + m_pos -= t >> 2; + m_pos -= *ip++ << 2; + TEST_LOOKBEHIND (m_pos, out); + NEED_OP (3); + *op++ = *m_pos++; + *op++ = *m_pos++; + *op++ = *m_pos; + + goto match_done; + + while (TEST_IP && TEST_OP) + { + match: + if (t >= 64) + { + m_pos = op - 1; + m_pos -= (t >> 2) & 7; + m_pos -= *ip++ << 3; + t = (t >> 5) - 1; + TEST_LOOKBEHIND (m_pos, out); + NEED_OP (t + 3 - 1); + goto copy_match; + + } + else if (t >= 32) + { + t &= 31; + if (t == 0) + { + NEED_IP (1); + while (*ip == 0) + { + t += 255; + ip++; + NEED_IP (1); + } + t += 31 + *ip++; + } + + m_pos = op - 1; + m_pos -= (ip[0] >> 2) + (ip[1] << 6); + + ip += 2; + } + else if (t >= 16) + { + m_pos = op; + m_pos -= (t & 8) << 11; + + t &= 7; + if (t == 0) + { + NEED_IP (1); + while (*ip == 0) + { + t += 255; + ip++; + NEED_IP (1); + } + t += 7 + *ip++; + } + + m_pos -= (ip[0] >> 2) + (ip[1] << 6); + + ip += 2; + if (m_pos == op) + goto eof_found; + m_pos -= 0x4000; + } + else + { + + m_pos = op - 1; + m_pos -= t >> 2; + m_pos -= *ip++ << 2; + TEST_LOOKBEHIND (m_pos, out); + NEED_OP (2); + *op++ = *m_pos++; + *op++ = *m_pos; + + goto match_done; + } + + TEST_LOOKBEHIND (m_pos, out); + NEED_OP (t + 3 - 1); + if (t >= 2 * 4 - (3 - 1) + && PTR_ALIGNED2_4 (op, m_pos)) + { + COPY4 (op, m_pos); + op += 4; + m_pos += 4; + t -= 4 - (3 - 1); + do + { + COPY4 (op, m_pos); + op += 4; + m_pos += 4; + t -= 4; + } + while (t >= 4); + if (t > 0) + do + *op++ = *m_pos++; + while (--t > 0); + } + else + + { + copy_match: + *op++ = *m_pos++; + *op++ = *m_pos++; + do + *op++ = *m_pos++; + while (--t > 0); + } + + match_done: + t = ip[-2] & 3; + + if (t == 0) + break; + + match_next: + NEED_OP (t); + NEED_IP (t + 1); + do + *op++ = *ip++; + while (--t > 0); + t = *ip++; + } + } + *out_len = op - out; + return LZO_E_EOF_NOT_FOUND; + + eof_found: + *out_len = op - out; + return (ip == ip_end ? LZO_E_OK : + (ip < + ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN)); + + input_overrun: + *out_len = op - out; + return LZO_E_INPUT_OVERRUN; + + output_overrun: + *out_len = op - out; + return LZO_E_OUTPUT_OVERRUN; + + lookbehind_overrun: + *out_len = op - out; + return LZO_E_LOOKBEHIND_OVERRUN; +} + +int lzo_decompress(unsigned char *data_in, unsigned char *cpage_out, + u32 srclen, u32 destlen) +{ + lzo_uint outlen = destlen; + return lzo1x_decompress (data_in, srclen, cpage_out, &outlen, NULL); +} + +#endif /* ((CONFIG_COMMANDS & CFG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO)) */ diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c index f3a9c53997c..a025116b7f0 100644 --- a/fs/jffs2/jffs2_1pass.c +++ b/fs/jffs2/jffs2_1pass.c @@ -274,7 +274,13 @@ static char *compr_names[] = { "RUBINMIPS", "COPY", "DYNRUBIN", - "ZLIB" + "ZLIB", +#if defined(CONFIG_JFFS2_LZO) + "LZO", +#endif +#if defined(CONFIG_JFFS2_LZARI) + "LZARI", +#endif }; /* Spinning wheel */ @@ -583,6 +589,16 @@ jffs2_1pass_read_inode(struct b_lists *pL, u32 inode, char *dest) case JFFS2_COMPR_ZLIB: ret = zlib_decompress(src, lDest, jNode->csize, jNode->dsize); break; +#if defined(CONFIG_JFFS2_LZARI) + case JFFS2_COMPR_LZARI: + ret = lzari_decompress(src, lDest, jNode->csize, jNode->dsize); + break; +#endif +#if defined(CONFIG_JFFS2_LZO) + case JFFS2_COMPR_LZO: + ret = lzo_decompress(src, lDest, jNode->csize, jNode->dsize); + break; +#endif default: /* unknown */ putLabeledWord("UNKOWN COMPRESSION METHOD = ", jNode->compr); |