[linux-mm-cc] [RFC] LZO de/compression support in kernel [5/5]
Nitin Gupta
nitingupta910 at gmail.com
Mon May 14 08:59:03 EDT 2007
This is LZO decompression code.
Signed-off-by: Nitin Gupta <nitingupta910 at gmail.com>
Index: linux-cc/lib/lzo1x/lzo1x_decompress.c
===================================================================
--- /dev/null
+++ linux-cc/lib/lzo1x/lzo1x_decompress.c
@@ -0,0 +1,226 @@
+/* lzo1x_decompress.c -- LZO1X decompression
+
+ 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_d1.c and lzo1x_d.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 <asm/byteorder.h>
+
+#include "lzo1x_int.h"
+
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("LZO1X Decompression");
+
+/***********************************************************************
+// decompress a block of data.
+************************************************************************/
+
+int
+lzo1x_decompress(const unsigned char *in, size_t in_len,
+ unsigned char *out, size_t *out_len)
+{
+ register size_t t;
+ register unsigned char *op;
+ register const unsigned char *ip, *m_pos;
+ const unsigned char * const ip_end = in + in_len;
+
+ *out_len = 0;
+
+ op = out;
+ ip = in;
+
+ if (*ip > 17)
+ {
+ t = *ip++ - 17;
+ if (t < 4)
+ goto match_next;
+ do *op++ = *ip++; while (--t > 0);
+ goto first_literal_run;
+ }
+
+ while (1)
+ {
+ t = *ip++;
+ if (t >= 16)
+ goto match;
+ /* a literal run */
+ if (t == 0)
+ {
+ while (*ip == 0)
+ {
+ t += 255;
+ ip++;
+ }
+ t += 15 + *ip++;
+ }
+ /* copy literals */
+ 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);
+ }
+
+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;
+ *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos;
+ goto match_done;
+
+
+ /* handle matches */
+ do {
+match:
+ if (t >= 64) /* a M2 match */
+ {
+ m_pos = op - 1;
+ m_pos -= (t >> 2) & 7;
+ m_pos -= *ip++ << 3;
+ t = (t >> 5) - 1;
+ goto copy_match;
+ }
+ else if (t >= 32) /* a M3 match */
+ {
+ t &= 31;
+ if (t == 0)
+ {
+ while (*ip == 0)
+ {
+ t += 255;
+ ip++;
+ }
+ t += 31 + *ip++;
+ }
+#if defined(__LITTLE_ENDIAN)
+ m_pos = op - 1;
+ m_pos -= (*(const unsigned short *)ip) >> 2;
+#else
+ m_pos = op - 1;
+ m_pos -= (ip[0] >> 2) + (ip[1] << 6);
+#endif
+ ip += 2;
+ }
+ else if (t >= 16) /* a M4 match */
+ {
+ m_pos = op;
+ m_pos -= (t & 8) << 11;
+ t &= 7;
+ if (t == 0)
+ {
+ while (*ip == 0)
+ {
+ t += 255;
+ ip++;
+ }
+ t += 7 + *ip++;
+ }
+#if defined(__LITTLE_ENDIAN)
+ m_pos -= (*(const unsigned short *)ip) >> 2;
+#else
+ m_pos -= (ip[0] >> 2) + (ip[1] << 6);
+#endif
+ ip += 2;
+ if (m_pos == op)
+ goto eof_found;
+ m_pos -= 0x4000;
+ }
+ else /* a M1 match */
+ {
+ m_pos = op - 1;
+ m_pos -= t >> 2;
+ m_pos -= *ip++ << 2;
+ *op++ = *m_pos++; *op++ = *m_pos;
+ goto match_done;
+ }
+
+ /* copy match */
+ if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4)
+ {
+ 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;
+
+ /* copy literals */
+match_next:
+ *op++ = *ip++;
+ if (t > 1) { *op++ = *ip++; if (t > 2) { *op++ = *ip++; } }
+ t = *ip++;
+ } while (1);
+ }
+
+eof_found:
+ *out_len = pd(op, out);
+ return (ip == ip_end ? 0 : -1);
+}
+
+EXPORT_SYMBOL(lzo1x_decompress);
More information about the linux-mm-cc
mailing list