[linux-mm-cc] [RFC] LZO de/compression support in kernel [4/5]
Nitin Gupta
nitingupta910 at gmail.com
Mon May 14 08:57:52 EDT 2007
This is the LZO1X-1 compression code.
Signed-off-by: Nitin Gupta <nitingupta910 at gmail.com>
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
+ <markus at oberhumer.com>
+ 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
+ <nitingupta910 at gmail.com>
+ */
+
+#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);
More information about the linux-mm-cc
mailing list