[lc-devel] [RFC] LZO de/compression support in kernel [4/5]
Status: Beta
Brought to you by:
nitin_sf
Menu
▾
▴
[lc-devel] [RFC] LZO de/compression support in kernel [4/5]
|
From: Nitin G. <nit...@gm...> - 2007-05-14 12:57:53
|
This is the LZO1X-1 compression code. Signed-off-by: Nitin Gupta <nit...@gm...> Index: linux-cc/lib/lzo1x/lzo1x_compress.c =================================================================== --- /dev/null +++ linux-cc/lib/lzo1x/lzo1x_compress.c @@ -0,0 +1,284 @@ +/* lzo1x_compress.c -- LZO1X-1 compression + + This file is part of the LZO real-time data compression library. + + Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 1996 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, + version 2, as published by the Free Software Foundation. + + 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., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + + Markus F.X.J. Oberhumer + <ma...@ob...> + http://www.oberhumer.com/opensource/lzo/ + + + This file is derived from lzo1x_1.c and lzo1x_c.ch found in original + LZO 2.02 code. Some additional changes have also been made to make + it work in kernel space. + + Nitin Gupta + <nit...@gm...> + */ + +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/compiler.h> + +#include "lzo1x_int.h" + +MODULE_LICENSE("GPL"); +MODULE_DESCRIPTION("LZO1X Compression"); + +/*********************************************************************** +// compress a block of data. +************************************************************************/ + +static unsigned int +lzo1x_compress_worker(const unsigned char *in, size_t in_len, + unsigned char *out, size_t *out_len, + void *workmem) +{ + register const unsigned char *ip; + unsigned char *op; + const unsigned char * const in_end = in + in_len; + const unsigned char * const ip_end = in + in_len - M2_MAX_LEN - 5; + const unsigned char *ii; + const unsigned char ** const dict = (const unsigned char **)workmem; + + op = out; + ip = in; + ii = ip; + + ip += 4; + for (;;) + { + register const unsigned char *m_pos; + size_t m_off; + size_t m_len; + size_t dindex; + + DINDEX1(dindex,ip); + m_pos = dict[dindex]; + if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET)) + goto literal; + if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3]) + goto try_match; + DINDEX2(dindex,ip); + + m_pos = dict[dindex]; + if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET)) + goto literal; + if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3]) + goto try_match; + goto literal; + + +try_match: + if (*(const unsigned short *)m_pos != *(const unsigned short *)ip) + { + } + else + { + if (likely(m_pos[2] == ip[2])) + goto match; + } + + /* a literal */ +literal: + dict[dindex] = ip; + ++ip; + if (unlikely(ip >= ip_end)) + break; + continue; + + + /* a match */ +match: + dict[dindex] = ip; + /* store current literal run */ + if (pd(ip,ii) > 0) + { + register size_t t = pd(ip,ii); + + if (t <= 3) + { + op[-2] |= (unsigned char)(t); + } + else if (t <= 18) + *op++ = (unsigned char)(t - 3); + else + { + register size_t tt = t - 18; + + *op++ = 0; + while (tt > 255) + { + tt -= 255; + *op++ = 0; + } + *op++ = (unsigned char)(tt); + } + do *op++ = *ii++; while (--t > 0); + } + + /* code the match */ + ip += 3; + if (m_pos[3] != *ip++ || m_pos[4] != *ip++ || m_pos[5] != *ip++ || + m_pos[6] != *ip++ || m_pos[7] != *ip++ || m_pos[8] != *ip++ + ) + { + --ip; + m_len = pd(ip, ii); + + if (m_off <= M2_MAX_OFFSET) + { + m_off -= 1; + *op++ = (unsigned char)(((m_len - 1) << 5) | ((m_off & 7) << 2)); + *op++ = (unsigned char)(m_off >> 3); + } + else if (m_off <= M3_MAX_OFFSET) + { + m_off -= 1; + *op++ = (unsigned char)(M3_MARKER | (m_len - 2)); + goto m3_m4_offset; + } + else + { + m_off -= 0x4000; + *op++ = (unsigned char)(M4_MARKER | + ((m_off & 0x4000) >> 11) | (m_len - 2)); + goto m3_m4_offset; + } + } + else + { + { + const unsigned char *end = in_end; + const unsigned char *m = m_pos + M2_MAX_LEN + 1; + while (ip < end && *m == *ip) + m++, ip++; + m_len = pd(ip, ii); + } + + if (m_off <= M3_MAX_OFFSET) + { + m_off -= 1; + if (m_len <= 33) + *op++ = (unsigned char)(M3_MARKER | (m_len - 2)); + else + { + m_len -= 33; + *op++ = M3_MARKER | 0; + goto m3_m4_len; + } + } + else + { + m_off -= 0x4000; + if (m_len <= M4_MAX_LEN) + *op++ = (unsigned char)(M4_MARKER | + ((m_off & 0x4000) >> 11) | (m_len - 2)); + else + { + m_len -= M4_MAX_LEN; + *op++ = (unsigned char)(M4_MARKER | ((m_off & 0x4000) >> 11)); +m3_m4_len: + while (m_len > 255) + { + m_len -= 255; + *op++ = 0; + } + *op++ = (unsigned char)(m_len); + } + } + +m3_m4_offset: + *op++ = (unsigned char)((m_off & 63) << 2); + *op++ = (unsigned char)(m_off >> 6); + } + + ii = ip; + if (unlikely(ip >= ip_end)) + break; + } + + *out_len = pd(op, out); + return pd(in_end,ii); +} + + +/*********************************************************************** +// public entry point +************************************************************************/ + +int +lzo1x_compress(const unsigned char *in, size_t in_len, + unsigned char *out, size_t *out_len, + void *workmem) +{ + unsigned char *op = out; + size_t t; + + if (unlikely(in_len <= M2_MAX_LEN + 5)) + t = in_len; + else + { + t = lzo1x_compress_worker(in,in_len,op,out_len,workmem); + op += *out_len; + } + + if (t > 0) + { + const unsigned char *ii = in + in_len - t; + + if (op == out && t <= 238) + *op++ = (unsigned char)(17 + t); + else if (t <= 3) + op[-2] |= (unsigned char)(t); + else if (t <= 18) + *op++ = (unsigned char)(t - 3); + else + { + size_t tt = t - 18; + + *op++ = 0; + while (tt > 255) + { + tt -= 255; + *op++ = 0; + } + *op++ = (unsigned char)(tt); + } + do *op++ = *ii++; while (--t > 0); + } + + *op++ = M4_MARKER | 1; + *op++ = 0; + *op++ = 0; + + *out_len = pd(op, out); + return 0; +} + +EXPORT_SYMBOL(lzo1x_compress); |
