Add LZO1X algorithm to the kernel

This is a hybrid version of the patch to add the LZO1X compression
algorithm to the kernel.  Nitin and myself have merged the best parts of
the various patches to form this version which we're both happy with (and
are jointly signing off).

The performance of this version is equivalent to the original minilzo code
it was based on.  Bytecode comparisons have also been made on ARM, i386 and
x86_64 with favourable results.

There are several users of LZO lined up including jffs2, crypto and reiser4
since its much faster than zlib.

Signed-off-by: Nitin Gupta <nitingupta910@gmail.com>
Signed-off-by: Richard Purdie <rpurdie@openedhand.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

1 files changed, 254 insertions, 0 deletions

diff --git a/lib/lzo/lzo1x_decompress.c b/lib/lzo/lzo1x_decompress.c
new file mode 100644
index 00000000000..9dc7056e552
--- /dev/null
+++ b/lib/lzo/lzo1x_decompress.c
@@ -0,0 +1,254 @@
+/*
+ *  LZO1X Decompressor from MiniLZO
+ *
+ *  Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <markus@oberhumer.com>
+ *
+ *  The full LZO package can be found at:
+ *  http://www.oberhumer.com/opensource/lzo/
+ *
+ *  Changed for kernel use by:
+ *  Nitin Gupta <nitingupta910@gmail.com>
+ *  Richard Purdie <rpurdie@openedhand.com>
+ */
+
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include <linux/lzo.h>
+#include <asm/byteorder.h>
+#include <asm/unaligned.h>
+#include "lzodefs.h"
+
+#define HAVE_IP(x, ip_end, ip) ((size_t)(ip_end - ip) < (x))
+#define HAVE_OP(x, op_end, op) ((size_t)(op_end - op) < (x))
+#define HAVE_LB(m_pos, out, op) (m_pos < out || m_pos >= op)
+
+#define COPY4(dst, src)	\
+		put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst))
+
+int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
+			unsigned char *out, size_t *out_len)
+{
+	const unsigned char * const ip_end = in + in_len;
+	unsigned char * const op_end = out + *out_len;
+	const unsigned char *ip = in, *m_pos;
+	unsigned char *op = out;
+	size_t t;
+
+	*out_len = 0;
+
+	if (*ip > 17) {
+		t = *ip++ - 17;
+		if (t < 4)
+			goto match_next;
+		if (HAVE_OP(t, op_end, op))
+			goto output_overrun;
+		if (HAVE_IP(t + 1, ip_end, ip))
+			goto input_overrun;
+		do {
+			*op++ = *ip++;
+		} while (--t > 0);
+		goto first_literal_run;
+	}
+
+	while ((ip < ip_end)) {
+		t = *ip++;
+		if (t >= 16)
+			goto match;
+		if (t == 0) {
+			if (HAVE_IP(1, ip_end, ip))
+				goto input_overrun;
+			while (*ip == 0) {
+				t += 255;
+				ip++;
+				if (HAVE_IP(1, ip_end, ip))
+					goto input_overrun;
+			}
+			t += 15 + *ip++;
+		}
+		if (HAVE_OP(t + 3, op_end, op))
+			goto output_overrun;
+		if (HAVE_IP(t + 4, ip_end, ip))
+			goto input_overrun;
+
+		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;
+
+		if (HAVE_LB(m_pos, out, op))
+			goto lookbehind_overrun;
+
+		if (HAVE_OP(3, op_end, op))
+			goto output_overrun;
+		*op++ = *m_pos++;
+		*op++ = *m_pos++;
+		*op++ = *m_pos;
+
+		goto match_done;
+
+		do {
+match:
+			if (t >= 64) {
+				m_pos = op - 1;
+				m_pos -= (t >> 2) & 7;
+				m_pos -= *ip++ << 3;
+				t = (t >> 5) - 1;
+				if (HAVE_LB(m_pos, out, op))
+					goto lookbehind_overrun;
+				if (HAVE_OP(t + 3 - 1, op_end, op))
+					goto output_overrun;
+				goto copy_match;
+			} else if (t >= 32) {
+				t &= 31;
+				if (t == 0) {
+					if (HAVE_IP(1, ip_end, ip))
+						goto input_overrun;
+					while (*ip == 0) {
+						t += 255;
+						ip++;
+						if (HAVE_IP(1, ip_end, ip))
+							goto input_overrun;
+					}
+					t += 31 + *ip++;
+				}
+				m_pos = op - 1;
+				m_pos -= le16_to_cpu(get_unaligned(
+					(const unsigned short *)ip)) >> 2;
+				ip += 2;
+			} else if (t >= 16) {
+				m_pos = op;
+				m_pos -= (t & 8) << 11;
+
+				t &= 7;
+				if (t == 0) {
+					if (HAVE_IP(1, ip_end, ip))
+						goto input_overrun;
+					while (*ip == 0) {
+						t += 255;
+						ip++;
+						if (HAVE_IP(1, ip_end, ip))
+							goto input_overrun;
+					}
+					t += 7 + *ip++;
+				}
+				m_pos -= le16_to_cpu(get_unaligned(
+					(const unsigned short *)ip) >> 2);
+				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;
+
+				if (HAVE_LB(m_pos, out, op))
+					goto lookbehind_overrun;
+				if (HAVE_OP(2, op_end, op))
+					goto output_overrun;
+
+				*op++ = *m_pos++;
+				*op++ = *m_pos;
+				goto match_done;
+			}
+
+			if (HAVE_LB(m_pos, out, op))
+				goto lookbehind_overrun;
+			if (HAVE_OP(t + 3 - 1, op_end, op))
+				goto output_overrun;
+
+			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;
+match_next:
+			if (HAVE_OP(t, op_end, op))
+				goto output_overrun;
+			if (HAVE_IP(t + 1, ip_end, ip))
+				goto input_overrun;
+
+			*op++ = *ip++;
+			if (t > 1) {
+				*op++ = *ip++;
+				if (t > 2)
+					*op++ = *ip++;
+			}
+
+			t = *ip++;
+		} while (ip < ip_end);
+	}
+
+	*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;
+}
+
+EXPORT_SYMBOL_GPL(lzo1x_decompress_safe);
+
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("LZO1X Decompressor");
+