linuxcompressed-devel — Linux Compressed Cache Development Mailing List

[lc-devel] [RFC] LZO de/compression support - take 6

[Nitin G. <nit...@gm...>]

Hi,

This is kernel port of LZO1X-1 compressor and LZO1X decompressor (safe
version only).

* Changes since 'take 5' (Full Changelog after this):
- Added compressor and decomrpesssor as separate and hidden config
options (default: n)
- Cleanups: removed LZO_CHECK_MPOS_NON_DET macro
- removed PTR* macros.

* Benchmarks: (system: P4 3GHz, 1G RAM)
(Using tester program from Daniel)

Following compares this kernel port ('take 6') vs original miniLZO code:

'TinyLZO' refers to this kernel port.

10000 run averages:
'Tiny LZO':
       Combined: 61.2223 usec
       Compression: 41.8412 usec
       Decompression: 19.3811 usec
'miniLZO':
       Combined: 66.0444 usec
       Compression: 46.6323 usec
       Decompression: 19.4121 usec

Result:
Overall: TinyLZO is 7.3% faster
Compressor: TinyLZO is 10.2% faster
Decompressor: TinyLZO is 0.15% faster

TODO: test 'take 6' port on archs other than x86(_32)

* Changelog vs. original LZO:
1) Used standard/kernel defined data types: (this eliminated _huge_
#ifdef chunks)
  lzo_bytep -> unsigned char *
  lzo_uint -> size_t
  lzo_xint -> size_t
  lzo_uint32p -> u32 *
  lzo_uintptr_t  -> unsigned long
2) Removed everything #ifdef'ed under COPY_DICT (this is not set for
LZO1X, so removed corres. parts).
3) Removed code #ifdef'ed for LZO1Y, LZO1Z, other variants.
4) Reformatted the code to match general kernel style.
5) The only code change: (as suggested by Andrey)
-#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

+ m_pos = op - 1 - (cpu_to_le16(*(const u16 *)ip) >> 2);

(Andrey suggested le16_to_cpu for above but I think it should be cpu_to_le16).
*** Need testing on big endian machine ***

Similarly:
-#if defined(__LITTLE_ENDIAN)
-                             m_pos -= (*(const unsigned short *)ip) >> 2;
-#else
-                             m_pos -= (ip[0] >> 2) + (ip[1] << 6);
-#endif

+ m_pos -= cpu_to_le16(*(const u16 *)ip) >> 2;

6) Get rid of LZO_CHECK_MPOS_NON_DET macro and PTR* macros.


I think it's now ready for mainline inclusion.


 include/linux/lzo1x.h        |   66 +++++++++++
 lib/Kconfig                  |    6 +
 lib/Makefile                 |    2 +
 lib/lzo1x/Makefile           |    2 +
 lib/lzo1x/lzo1x_compress.c   |  259 ++++++++++++++++++++++++++++++++++++++++++
 lib/lzo1x/lzo1x_decompress.c |  238 ++++++++++++++++++++++++++++++++++++++
 lib/lzo1x/lzo1x_int.h        |   85 ++++++++++++++
 7 files changed, 658 insertions(+), 0 deletions(-)

Signed-off-by: Nitin Gupta <nitingupta910 [at] gmail [dot] com>
---
diff --git a/include/linux/lzo1x.h b/include/linux/lzo1x.h
new file mode 100755
index 0000000..11a6f23
--- /dev/null
+++ b/include/linux/lzo1x.h
@@ -0,0 +1,66 @@
+/* lzo1x.h -- public interface of the LZO1X compression algorithm
+
+   This file is part of the LZO real-time data compression library.
+
+   Copyright (C) 1996-2005 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 modified version of lzo1x.h 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...>
+ */
+
+#ifndef __LZO1X_H
+#define __LZO1X_H
+
+/* LZO return codes */
+#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 LZO_E_NOT_YET_IMPLEMENTED	(-9)    /* [not used right now] */
+
+/* Size of temp buffer (workmem) required by lzo1x_compress */
+#define LZO1X_WORKMEM_SIZE	((size_t) (16384L * sizeof(unsigned char *)))
+
+/*
+ * This requires 'workmem' of size LZO1X_WORKMEM_SIZE
+ */
+int lzo1x_compress(const unsigned char *src, size_t src_len,
+		unsigned char *dst, size_t *dst_len,
+		void *workmem);
+
+/*
+ * This decompressor will catch all compressed data violations and
+ * return an error code in this case.
+ */
+int lzo1x_decompress(const unsigned char *src, size_t src_len,
+		unsigned char *dst, size_t *dst_len);
+#endif
diff --git a/lib/Kconfig b/lib/Kconfig
index 2e7ae6b..eb95eaa 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -64,6 +64,12 @@ config ZLIB_INFLATE
 config ZLIB_DEFLATE
 	tristate

+config LZO1X_COMPRESS
+	tristate
+
+config LZO1X_DECOMPRESS
+	tristate
+
 #
 # Generic allocator support is selected if needed
 #
diff --git a/lib/Makefile b/lib/Makefile
index c8c8e20..448ae37 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -49,6 +49,8 @@ obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
 obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
 obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/
 obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
+obj-$(CONFIG_LZO1X_COMPRESS) += lzo1x/
+obj-$(CONFIG_LZO1X_DECOMPRESS) += lzo1x/

 obj-$(CONFIG_TEXTSEARCH) += textsearch.o
 obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o
diff --git a/lib/lzo1x/Makefile b/lib/lzo1x/Makefile
new file mode 100644
index 0000000..7b56a4d
--- /dev/null
+++ b/lib/lzo1x/Makefile
@@ -0,0 +1,2 @@
+obj-$(CONFIG_LZO1X_COMPRESS) += lzo1x_compress.o
+obj-$(CONFIG_LZO1X_DECOMPRESS) += lzo1x_decompress.o
diff --git a/lib/lzo1x/lzo1x_compress.c b/lib/lzo1x/lzo1x_compress.c
new file mode 100755
index 0000000..b525be6
--- /dev/null
+++ b/lib/lzo1x/lzo1x_compress.c
@@ -0,0 +1,259 @@
+/* lzo1x_compress.c -- LZO1X-1 compression
+
+   This file is part of the LZO real-time data compression library.
+
+   Copyright (C) 1996-2005 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 <linux/lzo1x.h>
+
+#include "lzo1x_int.h"
+
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("LZO1X Compression");
+
+/* compress a block of data. */
+static noinline 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 ((m_pos < in) || (m_off = (size_t)(ip - m_pos)) <= 0
+				 || m_off > 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 ((m_pos < in) || (m_off = (size_t)(ip - m_pos)) <= 0
+				 || m_off > 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) {
+			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 ((size_t)(ip - ii) > 0) {
+			register size_t t = (size_t)(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 = (size_t)(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 = (size_t)(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 = (size_t)(op - out);
+	return (size_t)(in_end - ii);
+}
+
+
+/*
+ * This requires buffer (workmem) of size LZO1X_WORKMEM_SIZE
+ * (exported by lzo1x.h).
+ */
+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 (!workmem)
+		return -EINVAL;
+
+	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 = (size_t)(op - out);
+	return LZO_E_OK;
+}
+
+EXPORT_SYMBOL(lzo1x_compress);
diff --git a/lib/lzo1x/lzo1x_decompress.c b/lib/lzo1x/lzo1x_decompress.c
new file mode 100755
index 0000000..75ce294
--- /dev/null
+++ b/lib/lzo1x/lzo1x_decompress.c
@@ -0,0 +1,238 @@
+/* lzo1x_decompress.c -- LZO1X decompression
+
+   This file is part of the LZO real-time data compression library.
+
+   Copyright (C) 1996-2005 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_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
+   <nit...@gm...>
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <asm/byteorder.h>
+#include <linux/lzo1x.h>
+
+#include "lzo1x_int.h"
+
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("LZO1X Decompression");
+
+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 = out;
+	register const unsigned char *ip = in, *m_pos;
+	const unsigned char * const ip_end = in + in_len;
+	unsigned char * const op_end = out + *out_len;
+	*out_len = 0;
+
+	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) {
+		t = *ip++;
+		if (t >= 16)
+			goto match;
+		/* a literal run */
+		if (t == 0) {
+			NEED_IP(1);
+			while (*ip == 0) {
+				t += 255;
+				ip++;
+				NEED_IP(1);
+			}
+			t += 15 + *ip++;
+		}
+		/* copy literals */
+		NEED_OP(t + 3);
+		NEED_IP(t + 4);
+		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;
+		TEST_LB(m_pos);
+		NEED_OP(3);
+		*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;
+				TEST_LB(m_pos);
+				NEED_OP(t + 3 - 1);
+				goto copy_match;
+			} else if (t >= 32) {	/* a M3 match */
+				t &= 31;
+				if (t == 0) {
+					NEED_IP(1);
+					while (*ip == 0) {
+						t += 255;
+						ip++;
+						NEED_IP(1);
+					}
+					t += 31 + *ip++;
+				}
+				m_pos = op - 1 - (cpu_to_le16(
+					*(const unsigned short *)ip) >> 2);
+				ip += 2;
+			} else if (t >= 16) {	/* a M4 match */
+				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 -= cpu_to_le16(
+					*(const unsigned short *)ip) >> 2;
+				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;
+				TEST_LB(m_pos);
+				NEED_OP(2);
+				*op++ = *m_pos++;
+				*op++ = *m_pos;
+				goto match_done;
+			}
+	
+			/* copy match */
+			TEST_LB(m_pos);
+			NEED_OP(t + 3 - 1);
+
+			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:
+			NEED_OP(t);
+			NEED_IP(t + 1);
+			*op++ = *ip++;
+			if (t > 1) {
+				*op++ = *ip++;
+				if (t > 2)
+					*op++ = *ip++;
+			}
+			t = *ip++;
+		} while (TEST_IP);
+	}
+
+	/* no EOF code was found */
+	*out_len = (size_t)(op - out);
+	return LZO_E_EOF_NOT_FOUND;
+
+eof_found:
+	*out_len = (size_t)(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 = (size_t)(op - out);
+	return LZO_E_INPUT_OVERRUN;
+
+output_overrun:
+	*out_len = (size_t)(op - out);
+	return LZO_E_OUTPUT_OVERRUN;
+
+lookbehind_overrun:
+	*out_len = (size_t)(op - out);
+	return LZO_E_LOOKBEHIND_OVERRUN;
+}
+
+EXPORT_SYMBOL(lzo1x_decompress);
diff --git a/lib/lzo1x/lzo1x_int.h b/lib/lzo1x/lzo1x_int.h
new file mode 100755
index 0000000..4f0fe8d
--- /dev/null
+++ b/lib/lzo1x/lzo1x_int.h
@@ -0,0 +1,85 @@
+/* lzo1x_int.h -- to be used internally by LZO de/compression algorithms
+
+   This file is part of the LZO real-time data compression library.
+
+   Copyright (C) 1996-2005 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 was derived from several header files 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...>
+ */
+
+#ifndef __LZO1X_INT_H
+#define __LZO1X_INT_H
+
+#include <linux/types.h>
+
+#define D_BITS		14
+#define D_SIZE		(1u << D_BITS)
+#define D_MASK		(D_SIZE - 1)
+#define D_HIGH		((D_MASK >> 1) + 1)
+
+#define DX2(p,s1,s2) \
+	(((((size_t)((p)[2]) << (s2)) ^ (p)[1]) << (s1)) ^ (p)[0])
+#define DX3(p,s1,s2,s3) \
+	((DX2((p) + 1, s2, s3) << (s1)) ^ (p)[0])
+#define DINDEX1(d,p) \
+	d = ((size_t)(0x21 * DX3(p, 5, 5, 6)) >> 5) & D_MASK
+#define DINDEX2(d,p) \
+	d = (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f)
+
+#define COPY4(dst,src)	*(u32 *)(dst) = *(u32 *)(src)
+
+/* LZO1X Specific constants */
+#define M1_MAX_OFFSET	0x0400
+#define M2_MAX_OFFSET	0x0800
+#define M3_MAX_OFFSET	0x4000
+#define M4_MAX_OFFSET	0xbfff
+
+#define M1_MIN_LEN	2
+#define M1_MAX_LEN	2
+#define M2_MIN_LEN	3
+#define M2_MAX_LEN	8
+#define M3_MIN_LEN	3
+#define M3_MAX_LEN	33
+#define M4_MIN_LEN	3
+#define M4_MAX_LEN	9
+
+#define M1_MARKER	0
+#define M2_MARKER	64
+#define M3_MARKER	32
+#define M4_MARKER	16
+
+/* Bounds checking */
+#define TEST_IP	(ip < ip_end)
+#define NEED_IP(x) \
+	if ((size_t)(ip_end - ip) < (size_t)(x)) goto input_overrun
+#define NEED_OP(x) \
+	if ((size_t)(op_end - op) < (size_t)(x)) goto output_overrun
+#define TEST_LB(m_pos) \
+	if (m_pos < out || m_pos >= op) goto lookbehind_overrun
+
+#endif

Re: [lc-devel] [RFC] LZO de/compression support - take 5

[Nitin G. <nit...@gm...>]

On 5/28/07, Michael-Luke Jones <ml...@ca...> wrote:
> On 28 May 2007, at 07:59, Nitin Gupta wrote:
>
> > If we get no perf. problems with this patch, then I beleive it is now
> > suitable to inclusion in mainline. Further cleanups and optimizations
> > can surely be done after that. It's still just ~500 LOC.
>
> Before LZO code is sent to Linus, its selection in Kconfig should be
> made orthogonal to the current zlib selection code.
>
> This means:
> 1) Options in lib/Kconfig hidden (selectable by drivers as required)

LZO as hidden option has no practical sense. Although LZO should be
auto-selected when some dependent project is selected (e.g. reieser4)
- there should be separate patch for this. Mixing such changes with
'core' LZO patch will just add side noise.

> 2) Decompression and Compression support separated, as read-only
> filesystems only need to build in decompression support.
>

Ok, I will do this.    I wonder if some difference in opinion in such
things can actually cause 10+ extra RFCs?

Cheers,
Nitin

[lc-devel] [RFC] LZO de/compression support - take 5

[Nitin G. <nit...@gm...>]

Hi,

This is kernel port of LZO1X-1 compressor and LZO1X decompressor (safe
version only).

--
If we get no perf. problems with this patch, then I beleive it is now
suitable to inclusion in mainline. Further cleanups and optimizations
can surely be done after that. It's still just ~500 LOC.
--

* Changes since 'take 4' (Full Changelog after this):
1) Again applied 1 cleanup (use cpu_to_le16): this was not causing slower perf.
2) Rolled back very minor cleanup: LZO_CHECK_MPOS_NON_DET macro is
back.   This is the last of cleanups that can cause different
assembler output than original. _Maybe_ this is cause for that ~9%
slowdown seen by Richard in compressor.

Can anyone do timing measurement in kernel space only. This will
eliminate all possible problems w.r.t usespace testing. I tried doing
the same using get_jiffies_64() across calls to compressor in the
'compress-test' module but this is giving same value when measured
just before and after calls to lzo1x_compress(). I don't know why.

If anyone can simply measure time across lzo1x_compress() and
lzo1x_decompress() calls in this compress-test module, then that will
give us proper perf. figures.

* Changelog vs. original LZO:
1) Used standard/kernel defined data types: (this eliminated _huge_
#ifdef chunks)
   lzo_bytep -> unsigned char *
   lzo_uint -> size_t
   lzo_xint -> size_t
   lzo_uint32p -> u32 *
   lzo_uintptr_t  -> unsigned long
2) Removed everything #ifdef'ed under COPY_DICT (this is not set for
LZO1X, so removed corres. parts).
3) Removed code #ifdef'ed for LZO1Y, LZO1Z, other variants.
4) Reformatted the code to match general kernel style.
5) The only code change: (as suggested by Andrey)
-#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

+ m_pos = op - 1 - (cpu_to_le16(*(const u16 *)ip) >> 2);

(Andrey suggested le16_to_cpu for above but I think it should be cpu_to_le16).
*** Need testing on big endian machine ***

Similarly:
-#if defined(__LITTLE_ENDIAN)
-                             m_pos -= (*(const unsigned short *)ip) >> 2;
-#else
-                             m_pos -= (ip[0] >> 2) + (ip[1] << 6);
-#endif

+ m_pos -= cpu_to_le16(*(const u16 *)ip) >> 2;


 include/linux/lzo1x.h        |   66 +++++++++++
 lib/Kconfig                  |    6 +
 lib/Makefile                 |    1 +
 lib/lzo1x/Makefile           |    3 +
 lib/lzo1x/lzo1x_compress.c   |  259 ++++++++++++++++++++++++++++++++++++++++++
 lib/lzo1x/lzo1x_decompress.c |  238 ++++++++++++++++++++++++++++++++++++++
 lib/lzo1x/lzo1x_int.h        |   96 ++++++++++++++++
 7 files changed, 669 insertions(+), 0 deletions(-)

Signed-off-by: Nitin Gupta <nit...@gm...>
---

 b/include/linux/lzo1x.h
new file mode 100755
index 0000000..11a6f23
--- /dev/null
+++ b/include/linux/lzo1x.h
@@ -0,0 +1,66 @@
+/* lzo1x.h -- public interface of the LZO1X compression algorithm
+
+   This file is part of the LZO real-time data compression library.
+
+   Copyright (C) 1996-2005 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 modified version of lzo1x.h 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...>
+ */
+
+#ifndef __LZO1X_H
+#define __LZO1X_H
+
+/* LZO return codes */
+#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 LZO_E_NOT_YET_IMPLEMENTED	(-9)    /* [not used right now] */
+
+/* Size of temp buffer (workmem) required by lzo1x_compress */
+#define LZO1X_WORKMEM_SIZE	((size_t) (16384L * sizeof(unsigned char *)))
+
+/*
+ * This requires 'workmem' of size LZO1X_WORKMEM_SIZE
+ */
+int lzo1x_compress(const unsigned char *src, size_t src_len,
+		unsigned char *dst, size_t *dst_len,
+		void *workmem);
+
+/*
+ * This decompressor will catch all compressed data violations and
+ * return an error code in this case.
+ */
+int lzo1x_decompress(const unsigned char *src, size_t src_len,
+		unsigned char *dst, size_t *dst_len);
+#endif
diff --git a/lib/Kconfig b/lib/Kconfig
index 2e7ae6b..257f377 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -64,6 +64,12 @@ config ZLIB_INFLATE
 config ZLIB_DEFLATE
 	tristate

+config LZO1X
+	tristate "LZO1X Compression/Decompression"
+	help
+	  Compression: LZO1X-1
+	  Decompression: LZO1X (safe)
+
 #
 # Generic allocator support is selected if needed
 #
diff --git a/lib/Makefile b/lib/Makefile
index c8c8e20..4dad99d 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -49,6 +49,7 @@ obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
 obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
 obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/
 obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
+obj-$(CONFIG_LZO1X)        += lzo1x/

 obj-$(CONFIG_TEXTSEARCH) += textsearch.o
 obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o
diff --git a/lib/lzo1x/Makefile b/lib/lzo1x/Makefile
new file mode 100644
index 0000000..fcd0d3e
--- /dev/null
+++ b/lib/lzo1x/Makefile
@@ -0,0 +1,3 @@
+obj-$(CONFIG_LZO1X) += lzo1x.o
+lzo1x-objs := lzo1x_compress.o lzo1x_decompress.o
+
diff --git a/lib/lzo1x/lzo1x_compress.c b/lib/lzo1x/lzo1x_compress.c
new file mode 100755
index 0000000..5b0e87f
--- /dev/null
+++ b/lib/lzo1x/lzo1x_compress.c
@@ -0,0 +1,259 @@
+/* lzo1x_compress.c -- LZO1X-1 compression
+
+   This file is part of the LZO real-time data compression library.
+
+   Copyright (C) 1996-2005 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 <linux/lzo1x.h>
+
+#include "lzo1x_int.h"
+
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("LZO1X Compression");
+
+/* compress a block of data. */
+static noinline 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) {
+			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 ((size_t)(ip - ii) > 0) {
+			register size_t t = (size_t)(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 = (size_t)(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 = (size_t)(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 = (size_t)(op - out);
+	return (size_t)(in_end - ii);
+}
+
+
+/*
+ * This requires buffer (workmem) of size LZO1X_WORKMEM_SIZE
+ * (exported by lzo1x.h).
+ */
+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 (!workmem)
+		return -EINVAL;
+
+	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 = (size_t)(op - out);
+	return LZO_E_OK;
+}
+
+EXPORT_SYMBOL(lzo1x_compress);
diff --git a/lib/lzo1x/lzo1x_decompress.c b/lib/lzo1x/lzo1x_decompress.c
new file mode 100755
index 0000000..75ce294
--- /dev/null
+++ b/lib/lzo1x/lzo1x_decompress.c
@@ -0,0 +1,238 @@
+/* lzo1x_decompress.c -- LZO1X decompression
+
+   This file is part of the LZO real-time data compression library.
+
+   Copyright (C) 1996-2005 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_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
+   <nit...@gm...>
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <asm/byteorder.h>
+#include <linux/lzo1x.h>
+
+#include "lzo1x_int.h"
+
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("LZO1X Decompression");
+
+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 = out;
+	register const unsigned char *ip = in, *m_pos;
+	const unsigned char * const ip_end = in + in_len;
+	unsigned char * const op_end = out + *out_len;
+	*out_len = 0;
+
+	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) {
+		t = *ip++;
+		if (t >= 16)
+			goto match;
+		/* a literal run */
+		if (t == 0) {
+			NEED_IP(1);
+			while (*ip == 0) {
+				t += 255;
+				ip++;
+				NEED_IP(1);
+			}
+			t += 15 + *ip++;
+		}
+		/* copy literals */
+		NEED_OP(t + 3);
+		NEED_IP(t + 4);
+		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;
+		TEST_LB(m_pos);
+		NEED_OP(3);
+		*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;
+				TEST_LB(m_pos);
+				NEED_OP(t + 3 - 1);
+				goto copy_match;
+			} else if (t >= 32) {	/* a M3 match */
+				t &= 31;
+				if (t == 0) {
+					NEED_IP(1);
+					while (*ip == 0) {
+						t += 255;
+						ip++;
+						NEED_IP(1);
+					}
+					t += 31 + *ip++;
+				}
+				m_pos = op - 1 - (cpu_to_le16(
+					*(const unsigned short *)ip) >> 2);
+				ip += 2;
+			} else if (t >= 16) {	/* a M4 match */
+				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 -= cpu_to_le16(
+					*(const unsigned short *)ip) >> 2;
+				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;
+				TEST_LB(m_pos);
+				NEED_OP(2);
+				*op++ = *m_pos++;
+				*op++ = *m_pos;
+				goto match_done;
+			}
+	
+			/* copy match */
+			TEST_LB(m_pos);
+			NEED_OP(t + 3 - 1);
+
+			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:
+			NEED_OP(t);
+			NEED_IP(t + 1);
+			*op++ = *ip++;
+			if (t > 1) {
+				*op++ = *ip++;
+				if (t > 2)
+					*op++ = *ip++;
+			}
+			t = *ip++;
+		} while (TEST_IP);
+	}
+
+	/* no EOF code was found */
+	*out_len = (size_t)(op - out);
+	return LZO_E_EOF_NOT_FOUND;
+
+eof_found:
+	*out_len = (size_t)(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 = (size_t)(op - out);
+	return LZO_E_INPUT_OVERRUN;
+
+output_overrun:
+	*out_len = (size_t)(op - out);
+	return LZO_E_OUTPUT_OVERRUN;
+
+lookbehind_overrun:
+	*out_len = (size_t)(op - out);
+	return LZO_E_LOOKBEHIND_OVERRUN;
+}
+
+EXPORT_SYMBOL(lzo1x_decompress);
diff --git a/lib/lzo1x/lzo1x_int.h b/lib/lzo1x/lzo1x_int.h
new file mode 100755
index 0000000..6c7850c
--- /dev/null
+++ b/lib/lzo1x/lzo1x_int.h
@@ -0,0 +1,96 @@
+/* lzo1x_int.h -- to be used internally by LZO de/compression algorithms
+
+   This file is part of the LZO real-time data compression library.
+
+   Copyright (C) 1996-2005 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 was derived from several header files 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...>
+ */
+
+#ifndef __LZO1X_INT_H
+#define __LZO1X_INT_H
+
+#include <linux/types.h>
+
+#define D_BITS		14
+#define D_SIZE		(1u << D_BITS)
+#define D_MASK		(D_SIZE - 1)
+#define D_HIGH		((D_MASK >> 1) + 1)
+
+#define PTR(a)		((unsigned long)(a))
+#define PTR_LT(a,b)	(PTR(a) < PTR(b))
+#define PTR_GE(a,b)	(PTR(a) >= PTR(b))
+#define PTR_DIFF(a,b)	(PTR(a) - PTR(b))
+
+#define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \
+	(m_pos = ip - (size_t)PTR_DIFF(ip, m_pos), \
+	PTR_LT(m_pos, in) || \
+	(m_off = (size_t)PTR_DIFF(ip, m_pos)) <= 0 || \
+	m_off > max_offset)
+
+#define DX2(p,s1,s2) \
+	(((((size_t)((p)[2]) << (s2)) ^ (p)[1]) << (s1)) ^ (p)[0])
+#define DX3(p,s1,s2,s3) \
+	((DX2((p) + 1, s2, s3) << (s1)) ^ (p)[0])
+#define DINDEX1(d,p) \
+	d = ((size_t)(0x21 * DX3(p, 5, 5, 6)) >> 5) & D_MASK
+#define DINDEX2(d,p) \
+	d = (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f)
+
+#define COPY4(dst,src)	*(u32 *)(dst) = *(u32 *)(src)
+
+/* LZO1X Specific constants */
+#define M1_MAX_OFFSET	0x0400
+#define M2_MAX_OFFSET	0x0800
+#define M3_MAX_OFFSET	0x4000
+#define M4_MAX_OFFSET	0xbfff
+
+#define M1_MIN_LEN	2
+#define M1_MAX_LEN	2
+#define M2_MIN_LEN	3
+#define M2_MAX_LEN	8
+#define M3_MIN_LEN	3
+#define M3_MAX_LEN	33
+#define M4_MIN_LEN	3
+#define M4_MAX_LEN	9
+
+#define M1_MARKER	0
+#define M2_MARKER	64
+#define M3_MARKER	32
+#define M4_MARKER	16
+
+/* Bounds checking */
+#define TEST_IP	(ip < ip_end)
+#define NEED_IP(x) \
+	if ((size_t)(ip_end - ip) < (size_t)(x)) goto input_overrun
+#define NEED_OP(x) \
+	if ((size_t)(op_end - op) < (size_t)(x)) goto output_overrun
+#define TEST_LB(m_pos) \
+	if (m_pos < out || m_pos >= op) goto lookbehind_overrun
+
+#endif

[lc-devel] LZO1X de/compression patch for 2.6.22-rc1

[Nitin G. <nit...@gm...>]

Patch attached. This patch contains additional formatting work to
comply with general kernel coding style.


Cheers,
Nitin

Re: [lc-devel] [RFC] LZO de/compression support in kernel [0/5]

[Nitin G. <nit...@gm...>]

>
> > * The code doesn't conform to CodingStyle as tabs aren't used for
> > indentation for a start and the brackets don't conform either.
> >

I am now done will all formatting - will post newer version (as single
patch) soon.

> > * For a better version of the include/linux/lzo1x.h header file see my
> > include/linux/lzo.h patch which includes error codes and maximum
> > compression size defines.
> >

I could not see any use for those LZO error codes (like LZO_E_OK).
Simple return value of 0 (success) and -1 (error) look fine.

> > * My patch series adds crypto layer support which might be useful for
> > testing
> >

For now, I am just looking at plain LZO algo...

> > * The patch series will need to be merged into one patch for submission
> > to mainline since its all interdependent.

Yes. I did that splitting only for easier reviewing. I will post that
as single patch soon.

> >
> > Just to confirm, this code is 100% compatible with data compressed with
> > LZO's lzo1x_compress function?
> >

Yes.

> > I suspect there is some hybrid between the two versions which would be
> > ideal! :)
> >

I don't know :-)


Cheers,
Nitin

Re: [lc-devel] [RFC] LZO de/compression support in kernel [0/5]

[Nitin G. <nit...@gm...>]

Hi,

On 5/14/07, Richard Purdie <ri...@op...> wrote:
> * The safe decompression version of the decompress function is missing.
> Ideally we should have that as I suspect most kernel use cases should be
> doing bounds checking. I did wonder if we should have bounds checking in
> the compression case too although its less significant from a security
> PoV.
>

I think the "safe" decompress version is only required when we suspect
that compressed data might be corrupted. Otherwise, if such data
corruption is not possible then this "unsafe" decompress will never
overrun output buffer -- since output buffer lenght is not used by
unsafe version but still it should never exceed buffer size beyoond
original data size.
 I think I should contact the author to make sure I am correct here...

Also "safe" decompress will obviously have perf penalties too.   But
anyhow adding option for  have safe decompress is worth it.

> * The code doesn't conform to CodingStyle as tabs aren't used for
> indentation for a start and the brackets don't conform either.
>
> * For a better version of the include/linux/lzo1x.h header file see my
> include/linux/lzo.h patch which includes error codes and maximum
> compression size defines.
>
> * My patch series adds crypto layer support which might be useful for
> testing
>
> * The patch series will need to be merged into one patch for submission
> to mainline since its all interdependent.
>
> Just to confirm, this code is 100% compatible with data compressed with
> LZO's lzo1x_compress function?
>
> I suspect there is some hybrid between the two versions which would be
> ideal! :)
>
> Cheers,
>
> Richard
>
>

Re: [lc-devel] [RFC] LZO de/compression support in kernel [0/5] -- correct [2/5]

[Nitin G. <nit...@gm...>]

Oops! this is patch [2/5]

On 5/14/07, Nitin Gupta <nit...@gm...> wrote:
> This adds LZO1X as config option in kernel and does Makefile changes
> to add it as additional target.
>
> Signed-off-by: Nitin Gupta <nit...@gm...>
...
<snip>

[lc-devel] [RFC] LZO de/compression support in kernel [5/5]

[Nitin G. <nit...@gm...>]

This is LZO decompression code.

Signed-off-by: Nitin Gupta <nit...@gm...>

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
+   <ma...@ob...>
+   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
+   <nit...@gm...>
+ */
+
+#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);

[lc-devel] [RFC] LZO de/compression support in kernel [4/5]

[Nitin G. <nit...@gm...>]

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);

[lc-devel] [RFC] LZO de/compression support in kernel [3/5]

[Nitin G. <nit...@gm...>]

This contains stuff used internally by LZO code. This is not intended
to be used directly by other modules.

Signed-off-by: Nitin Gupta <nit...@gm...>


Index: linux-cc/lib/lzo1x/lzo1x_int.h
===================================================================
--- /dev/null
+++ linux-cc/lib/lzo1x/lzo1x_int.h
@@ -0,0 +1,105 @@
+/* lzo1x_int.h -- to be used internally by LZO de/compression algorithms
+
+   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 was derived from several header files 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...>
+ */
+
+#ifndef __LZO1X_INT_H
+#define __LZO1X_INT_H
+
+#include <linux/types.h>
+
+#define D_SIZE		(1u << D_BITS)
+#define D_MASK		(D_SIZE - 1)
+#define D_HIGH		((D_MASK >> 1) + 1)
+
+#define DX2(p,s1,s2) \
+	(((((size_t)((p)[2]) << (s2)) ^ (p)[1]) << (s1)) ^ (p)[0])
+#define DX3(p,s1,s2,s3) ((DX2((p)+1,s2,s3) << (s1)) ^ (p)[0])
+#define DMUL(a,b)	((size_t) ((a) * (b)))
+#define DMS(v,s)	((size_t) (((v) & (D_MASK >> (s))) << (s)))
+#define DM(v)		DMS(v,0)
+
+#define D_BITS		14
+#define DINDEX1(d,p)	d = DM(DMUL(0x21,DX3(p,5,5,6)) >> 5)
+#define DINDEX2(d,p)	d = (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f)
+#define DENTRY(p,in)	(p)
+
+#define PTR(a)		((unsigned long) (a))
+#define PTR_LT(a,b)	(PTR(a) < PTR(b))
+#define PTR_GE(a,b)	(PTR(a) >= PTR(b))
+#define PTR_DIFF(a,b)	(PTR(a) - PTR(b))
+#define pd(a,b)		((size_t) ((a)-(b)))
+
+#define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \
+	( m_pos = ip - (size_t) PTR_DIFF(ip,m_pos), \
+	PTR_LT(m_pos,in) || \
+	(m_off = (size_t) PTR_DIFF(ip,m_pos)) <= 0 || \
+	m_off > max_offset )
+
+#define COPY4(dst,src)	*(size_t *)(dst) = *(size_t *)(src)
+
+
+/* LZO1X Specific constants */
+
+#define M1_MAX_OFFSET	0x0400
+#define M2_MAX_OFFSET	0x0800
+#define M3_MAX_OFFSET	0x4000
+#define M4_MAX_OFFSET	0xbfff
+
+#define MX_MAX_OFFSET	(M1_MAX_OFFSET + M2_MAX_OFFSET)
+
+#define M1_MIN_LEN	2
+#define M1_MAX_LEN	2
+#define M2_MIN_LEN	3
+#define M2_MAX_LEN	8
+#define M3_MIN_LEN	3
+#define M3_MAX_LEN	33
+#define M4_MIN_LEN	3
+#define M4_MAX_LEN	9
+
+#define M1_MARKER	0
+#define M2_MARKER	64
+#define M3_MARKER	32
+#define M4_MARKER	16
+
+#define MIN_LOOKAHEAD	(M2_MAX_LEN + 1)
+
+#endif /* already included */

Re: [lc-devel] [RFC] LZO de/compression support in kernel [0/5]

[Nitin G. <nit...@gm...>]

This adds LZO1X as config option in kernel and does Makefile changes
to add it as additional target.

Signed-off-by: Nitin Gupta <nit...@gm...>

Index: linux-cc/lib/Kconfig
===================================================================
--- linux-cc.orig/lib/Kconfig
+++ linux-cc/lib/Kconfig
@@ -64,6 +64,9 @@ config ZLIB_INFLATE
 config ZLIB_DEFLATE
 	tristate

+config LZO1X
+        tristate "LZO1X Compression/Decompression"
+
 #
 # Generic allocator support is selected if needed
 #
Index: linux-cc/lib/Makefile
===================================================================
--- linux-cc.orig/lib/Makefile
+++ linux-cc/lib/Makefile
@@ -49,6 +49,7 @@ obj-$(CONFIG_GENERIC_ALLOCATOR) += genal
 obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
 obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/
 obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
+obj-$(CONFIG_LZO1X) += lzo1x/

 obj-$(CONFIG_TEXTSEARCH) += textsearch.o
 obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o
Index: linux-cc/lib/lzo1x/Makefile
===================================================================
--- /dev/null
+++ linux-cc/lib/lzo1x/Makefile
@@ -0,0 +1,2 @@
+obj-$(CONFIG_LZO1X) += lzo1x.o
+lzo1x-objs := lzo1x_compress.o lzo1x_decompress.o

[lc-devel] [RFC] LZO de/compression support in kernel [1/5]

[Nitin G. <nit...@gm...>]

This is the public interface for LZO de/compression.


Index: linux-cc/include/linux/lzo1x.h
===================================================================
--- /dev/null
+++ linux-cc/include/linux/lzo1x.h
@@ -0,0 +1,61 @@
+/* lzo1x.h -- public interface of the LZO1X compression algorithm
+
+   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 modified version of lzo1x.h 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...>
+ */
+
+#ifndef __LZO1X_H
+#define __LZO1X_H
+
+/* Size of temp buffer (workmem) required by lzo1x_compress */
+#define LZO1X_WORKMEM_SIZE	((size_t) (16384L * sizeof(unsigned char *)))
+
+/* LZO1X_1 compression */
+int
+lzo1x_compress(const unsigned char *src, size_t src_len,
+		unsigned char *dst, size_t *dst_len,
+		void *workmem);
+
+/* LZO1X_1 decompression */
+int
+lzo1x_decompress(const unsigned char *src, size_t src_len,
+		unsigned char *dst, size_t *dst_len);
+
+#endif

[lc-devel] [RFC] LZO de/compression support in kernel [0/5]

[Nitin G. <nit...@gm...>]

Hi,

This is kernel port of LZO1X-1 compression algo stripped down to just
~500 lines!
The original code is from:
http://www.oberhumer.com/opensource/lzo/download/lzo-2.02.tar.gz

This is the same flavour of LZO that we are currently using in
compressed caching.

Before posting this to LKML, it would be great we replace existing LZO
code in ccaching patche with this version. If it can take torture of
ccaching then it's good enough for mainline w.r.t stability. Please
also look into coding style if it's acceptable for mainline - I did
not consider much about the diffability with original LZO code as I
just wanted a clean looking code :-)

I have created a simple kernel module to test this LZO port. I will
refine that a bit and post on
http://linux-mm.org/CompressedCaching/Code soon.

Any comments/reviews are welcome :)

(patches are against 2.6.22-rc1)

Cheers,
Nitin

Re: [lc-devel] Compressed TMPFS

[Nitin G. <nit...@gm...>]

Hi,

On 4/28/07, Jun OKAJIMA <ok...@di...> wrote:
>
> 1. Can I understand the project as a linux version of "RAM Doubler" ?
>    ( RAM Doubler is an interesting util for Macintosh in old days. )
>    "Compressed Cache" compresses main memory. Not only cache, but whole mem. Right?
>

"Compressed Cache" compresses parts of memory which would otherwise be
swapped or put back on disks when you are running low on memory. So,
it does not compress _whole_ memory but only certain amount
(configurable) of such relatively unused memory (essentially reducing
costly disk I/O).

> 2. What I need is, so called "compressed tmpfs", in other words,
>    I need a DBLSPACE of MSDOS for RAM disk.
>    This project can work for my purpose?
>

If I understand, you require in-memory filesystem that compressed
_all_ its contents. This is not what ccaching does.

> 3. Do you have any figure which shows performance improvement of compressing?
>    As you must know, there seems to be a trade-off about CPU usage and memory
>    efficiency. Compressed Cache really improves the performance? If so,
>    how much in what case?
>

No performance figures yet. Still I am working on stabilizing it!
An important feature of automatic ccache resizing based on workload is
still missing. So, any performance figures will be highly tied to kind
of benchmark load you use.


Cheers,
Nitin

[lc-devel] Compressed TMPFS

[Jun O. <ok...@di...>]

Hello hackers.

If I am asking a foolish question, forgive me because I
know little about the project.

1. Can I understand the project as a linux version of "RAM Doubler" ?
   ( RAM Doubler is an interesting util for Macintosh in old days. )
   "Compressed Cache" compresses main memory. Not only cache, but whole mem. Right?

2. What I need is, so called "compressed tmpfs", in other words,
   I need a DBLSPACE of MSDOS for RAM disk.
   This project can work for my purpose?

3. Do you have any figure which shows performance improvement of compressing?
   As you must know, there seems to be a trade-off about CPU usage and memory
   efficiency. Compressed Cache really improves the performance? If so,
   how much in what case?

        TIA,
                  --- Okajima, Jun. Tokyo, Japan.

 

[lc-devel] Announce: Compressed Cache for 2.6.21

[Nitin G. <nit...@gm...>]

Hi All,

---
Project Home: http://linuxcompressed.sourceforge.net
---

Compressed Cache patch for Linux 2.6.21 is released!

As usual, it contains various bug fixes and cleanups (see Changelog).
No new features are added! Stability First - Right? :-)

Following this release, we will be following Project Roadmap posted
at: http://linuxcompressed.sourceforge.net/todo/index.html

There are also plans to start Roadmap Wiki soon!

* Testing Notes (tested on 32-bit x86 only):
- Config:
  Mem = 128M
  max_fs_backed_cc_size = 2560 (10M)
  max_anon_cc_size = 1280 (5M)

(see http://linuxcompressed.sourceforge.net/help/index.html for
description of above params).

- Tests:
  Started Firefox (4 instances), konqueror (3), fillmem test (128M).
No Crashes - system remained responsive.

* Changelog: ccache for 2.6.18 vs 2.6.21

- Some changes due to new RCU locking used for page/swap cache.
- Bug fix: Bug caused NULL pointer errors in some conditions.
- Bug fix: Bug caused /proc/ccache_stats to report incorrect figures.
- Minor cleanups.


Please mail me/mailing list any bugs/issues you find.


PS: Git repository is now seriously outdated! Due to some
proxy/firewall/blah reasons, I am not able to access it. So, released
patches contain the Latest-and-Greatest(tm) stuff :-)


Cheers,
Nitin

Re: [lc-devel] linuxcompressed-devel Digest, Vol 7, Issue 3

[Allan B. <all...@gm...>]

Hi ace,

Please, use this format to report bug:
http://www.kernel.org/pub/linux/docs/lkml/reporting-bugs.html
It will go to help us.

Tks,

-- Allan

On 1/12/07, lin...@li... <
lin...@li...> wrote:
>
> Send linuxcompressed-devel mailing list submissions to
>         lin...@li...
>
> To subscribe or unsubscribe via the World Wide Web, visit
>         https://lists.sourceforge.net/lists/listinfo/linuxcompressed-devel
> or, via email, send a message with subject or body 'help' to
>         lin...@li...
>
> You can reach the person managing the list at
>         lin...@li...
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of linuxcompressed-devel digest..."
>
>
> Today's Topics:
>
>    1. Re: Update Compressed cache alpha-007 to kernel 2.6.19.1 (ace)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Fri, 12 Jan 2007 16:38:37 +0100
> From: ace <ace...@at...>
> Subject: Re: [lc-devel] Update Compressed cache alpha-007 to kernel
>         2.6.19.1
> To: Linux Compressed Cache Development List
>         <lin...@li...>
> Message-ID: <45A...@at...>
> Content-Type: text/plain; charset=ISO-8859-1
>
> Allan Bezerra wrote:
> > Hi all!
> >
> > For those who may be interested, I update compressed cache patch to
> > kernel 2.6.19.1 <http://2.6.19.1>
> Great, this is something usable:)
>
> > I tested this patch on 32-bit system Only with 10M for
> > page-cache and 5M for swap-cache (RAM: 128M).
> Unfortunatelly, it didn't work for me. It compiled and booted fine. But
> when I tried to just copy the kernel tree (~300MB), various kernel
> threads crashed with BUGs (like kswapd0) and such things. Sometimes it
> looked like there is no problem, just that the console was flooded with
> messages from ccache (cc_writepage), but without any error indication,
> just that the machine almost hanged (it was alive but no new processes
> could run). I tried various sizes for ccache (from 200MB to 10MB as
> adviced above), I have 320MB RAM. I can provide the crash dump, stack
> trace, offending functions, if you anybody is interested and I write
> them down on paper.
>
> What do I do wrong? Can ccache be sensitive to various kernel tweaking
> options, e.g. preemption, irqstacks, debugging? May it conflict with the
> suspend2 patch (www.suspend2.net, but I don't think that patch does
> anything while the system is running). I'll try more and let you know.
> Thanks,
>
> Peter
>
>
>
>
> ------------------------------
>
> -------------------------------------------------------------------------
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to share
> your
> opinions on IT & business topics through brief surveys - and earn cash
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
>
> ------------------------------
>
> _______________________________________________
> linuxcompressed-devel mailing list
> lin...@li...
> https://lists.sourceforge.net/lists/listinfo/linuxcompressed-devel
>
>
> End of linuxcompressed-devel Digest, Vol 7, Issue 3
> ***************************************************
>

Re: [lc-devel] Update Compressed cache alpha-007 to kernel 2.6.19.1

[ace <ace...@at...>]

Allan Bezerra wrote:
> Hi all!
> 
> For those who may be interested, I update compressed cache patch to
> kernel 2.6.19.1 <http://2.6.19.1>
Great, this is something usable:)

> I tested this patch on 32-bit system Only with 10M for
> page-cache and 5M for swap-cache (RAM: 128M).
Unfortunatelly, it didn't work for me. It compiled and booted fine. But
when I tried to just copy the kernel tree (~300MB), various kernel
threads crashed with BUGs (like kswapd0) and such things. Sometimes it
looked like there is no problem, just that the console was flooded with
messages from ccache (cc_writepage), but without any error indication,
just that the machine almost hanged (it was alive but no new processes
could run). I tried various sizes for ccache (from 200MB to 10MB as
adviced above), I have 320MB RAM. I can provide the crash dump, stack
trace, offending functions, if you anybody is interested and I write
them down on paper.

What do I do wrong? Can ccache be sensitive to various kernel tweaking
options, e.g. preemption, irqstacks, debugging? May it conflict with the
suspend2 patch (www.suspend2.net, but I don't think that patch does
anything while the system is running). I'll try more and let you know.
Thanks,

Peter

Re: [lc-devel] Update Compressed cache alpha-007 to kernel 2.6.19.1

[Nitin G. <nit...@gm...>]

Hi Allan,

On 1/8/07, Allan Bezerra <all...@gm...> wrote:

> I tested this patch on 32-bit system Only with 10M for
> page-cache and 5M for swap-cache (RAM: 128M).
>

Did you also get time to do any performance benchmarks?

> [Patch download]:
> http://www.indt.org/allan/patch-ccache-alpha-007-2.6.19.1.tar.bz2
>

I could not look at the code but if you can split this big patch into
logical pieces (de/compression algos, ccache structure handling etc.)
then there will be better chances to get a review.

> * Changelog: ccache-alpha-007 (applies to 2.6.19.1)
>

Did you forget this? :)


Cheers,
Nitin

[lc-devel] Update Compressed cache alpha-007 to kernel 2.6.19.1

[Allan B. <all...@gm...>]

Hi all!

For those who may be interested, I update compressed cache patch to kernel
2.6.19.1

I tested this patch on 32-bit system Only with 10M for
page-cache and 5M for swap-cache (RAM: 128M).

[Patch download]:
http://www.indt.org/allan/patch-ccache-alpha-007-2.6.19.1.tar.bz2

* Changelog: ccache-alpha-007 (applies to 2.6.19.1)

Cheers,

 -- Allan Bezerra

Re: [lc-devel] Update Compressed cache alpha-007 to kernel 2.6.19

[ace <ace...@at...>]

>> could you make a patch against a stable kernel (e.g. 2.6.19 final),
>> because that is what we use. Thanks
>>
> 
> CCaching patch posted by Allan is for 2.6.19 [I'm not sure which -rc]
> (though I could not test this patch!)
> 
> Cheers,
> Nitin
Thanks, but that version can't be for 2.6.19 final release, because it
didn't exist at that time. Now that it is finally released, dould
somebody please update ccache for the final 2.6.19 kernel, so that I can
try it out? Thanks.


Peter

Re: [lc-devel] Update Compressed cache alpha-007 to kernel 2.6.19

[Nitin G. <nit...@gm...>]

On 11/14/06, Allan Bezerra <all...@gm...> wrote:
>
> Now, I'm looking for suggestions made by Peterz
> http://mailman.laptop.org/pipermail/linux-mm-cc/2006-September/000066.html
> I intend to send a patch soon.
>

Awesome!

> Gupta, my olpc board is working now! :) I will start to make the tests on
> board this week.
>

Awesome! :)


Just one thing -- I think using git rather than following -rc releases
can be better. This can save you lot of time trying to figure out
changes between -rc's.

Cheers,
Nitin


> Br,
>
> -- Allan Bezerra
>
>  On 11/13/06,
> lin...@li... <
> lin...@li...> wrote:
> > Send linuxcompressed-devel mailing list submissions to
> >         lin...@li...
> >
> > To subscribe or unsubscribe via the World Wide Web, visit
> >
> https://lists.sourceforge.net/lists/listinfo/linuxcompressed-devel
> > or, via email, send a message with subject or body 'help' to
> >
> lin...@li...
> >
> > You can reach the person managing the list at
> >         lin...@li...
> >
> > When replying, please edit your Subject line so it is more specific
> > than "Re: Contents of linuxcompressed-devel digest..."
> >
> >
> > Today's Topics:
> >
> >    1. Re: Update Compressed cache alpha-007 to kernel 2.6.19
> >       (Nitin Gupta)
> >
> >
> >
> ----------------------------------------------------------------------
> >
> > Message: 1
> > Date: Mon, 13 Nov 2006 10:32:27 +0530
> > From: "Nitin Gupta" <nit...@gm... >
> > Subject: Re: [lc-devel] Update Compressed cache alpha-007 to kernel
> >         2.6.19
> > To: "Linux Compressed Cache Development List"
> >         < lin...@li...>
> > Message-ID:
> >
> <f68...@ma...
> >
> > Content-Type: text/plain; charset=ISO-8859-1; format=flowed
> >
> >
> > On 11/11/06, ace <ace...@at...> wrote:
> >
> > Hi,
> >
> > > Hi guys.
> > >
> > > What is the current status of compressed cache? I always see the 'alpha'
> > >   naming, is there anything considered moderately stable that we could
> > > test? Something with no known dataloss problems:) Something we could try
> > > on serious systems for several minutes to see what it does. If yes,
> >
> > I never experienced any data corruption kind of problems while testing
> > it but still before you come to kill me consider not to try this on
> > 'production' machine :)
> >
> > > could you make a patch against a stable kernel (e.g. 2.6.19 final),
> > > because that is what we use. Thanks
> > >
> >
> > CCaching patch posted by Allan is for 2.6.19 [I'm not sure which -rc]
> > (though I could not test this patch!)
> >
> > Cheers,
> > Nitin
> >
> >
> >
> > > Peter
> > >
> > > Allan Bezerra wrote:
> > > > ------------
> > > > Project: Compressed Caching for Linux
> > > > Project Home: http://linuxcompressed.sourceforge.net
> > > > < http://linuxcompressed.sourceforge.net>
> > > > Git (web):
> http://dev.laptop.org/git.do?p=projects/linux-mm-cc
> > > > Git (git): git://dev.laptop.org/projects/linux-mm-cc
> > > > ------------
> > > >
> > > > Hi Nitin and all!
> > > >
> > > > For those who may be interested, I update compressed cache patch to
> > > > kernel 2.6.19.
> > > > This patch has no significantly changes.
> > > >
> > > > * Changelog: ccache-alpha-007 (applies to 2.6.19)
> > > >
> > > > Cheers,
> > > >
> > > > -- Allan Bezerra
> > > >
> > > >
> > > >
> ------------------------------------------------------------------------
> > > >
> > >
> > >
> > >
> > >
> -------------------------------------------------------------------------
> > > Using Tomcat but need to do more? Need to support web services,
> security?
> > > Get stuff done quickly with pre-integrated technology to make your job
> easier
> > > Download IBM WebSphere Application Server v.1.0.1 based on Apache
> Geronimo
> > >
> http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
> > > _______________________________________________
> > > linuxcompressed-devel mailing list
> > > lin...@li...
> > >
> https://lists.sourceforge.net/lists/listinfo/linuxcompressed-devel
> > >
> >
> >
> >
> > ------------------------------
> >
> >
> -------------------------------------------------------------------------
> > Using Tomcat but need to do more? Need to support web services, security?
> > Get stuff done quickly with pre-integrated technology to make your job
> easier
> > Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
> >
> http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
> >
> > ------------------------------
> >
> > _______________________________________________
> > linuxcompressed-devel mailing list
> > lin...@li...
> >
> https://lists.sourceforge.net/lists/listinfo/linuxcompressed-devel
> >
> >
> > End of linuxcompressed-devel Digest, Vol 5, Issue 5
> > ***************************************************
> >
>
>

Re: [lc-devel] Update Compressed cache alpha-007 to kernel 2.6.19

[Allan B. <all...@gm...>]

> CCaching patch posted by Allan is for 2.6.19 [I'm not sure which -rc]
(though I could not test this patch!)
I update compressed cache patch to kernel 2.6.19-rc1.

Now, I'm looking for suggestions made by Peterz
http://mailman.laptop.org/pipermail/linux-mm-cc/2006-September/000066.html
I intend to send a patch soon.

Gupta, my olpc board is working now! :) I will start to make the tests on
board this week.

Br,

-- Allan Bezerra

On 11/13/06, lin...@li...
<lin...@li...>
wrote:
>
> Send linuxcompressed-devel mailing list submissions to
>         lin...@li...
>
> To subscribe or unsubscribe via the World Wide Web, visit
>         https://lists.sourceforge.net/lists/listinfo/linuxcompressed-devel
> or, via email, send a message with subject or body 'help' to
>         lin...@li...
>
> You can reach the person managing the list at
>         lin...@li...
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of linuxcompressed-devel digest..."
>
>
> Today's Topics:
>
>    1. Re: Update Compressed cache alpha-007 to kernel 2.6.19
>       (Nitin Gupta)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Mon, 13 Nov 2006 10:32:27 +0530
> From: "Nitin Gupta" <nit...@gm...>
> Subject: Re: [lc-devel] Update Compressed cache alpha-007 to kernel
>         2.6.19
> To: "Linux Compressed Cache Development List"
>         <lin...@li...>
> Message-ID:
>         <f68...@ma...>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
> On 11/11/06, ace <ace...@at...> wrote:
>
> Hi,
>
> > Hi guys.
> >
> > What is the current status of compressed cache? I always see the 'alpha'
> >   naming, is there anything considered moderately stable that we could
> > test? Something with no known dataloss problems:) Something we could try
> > on serious systems for several minutes to see what it does. If yes,
>
> I never experienced any data corruption kind of problems while testing
> it but still before you come to kill me consider not to try this on
> 'production' machine :)
>
> > could you make a patch against a stable kernel (e.g. 2.6.19 final),
> > because that is what we use. Thanks
> >
>
> CCaching patch posted by Allan is for 2.6.19 [I'm not sure which -rc]
> (though I could not test this patch!)
>
> Cheers,
> Nitin
>
>
>
> > Peter
> >
> > Allan Bezerra wrote:
> > > ------------
> > > Project: Compressed Caching for Linux
> > > Project Home: http://linuxcompressed.sourceforge.net
> > > < http://linuxcompressed.sourceforge.net>
> > > Git (web): http://dev.laptop.org/git.do?p=projects/linux-mm-cc
> > > Git (git): git://dev.laptop.org/projects/linux-mm-cc
> > > ------------
> > >
> > > Hi Nitin and all!
> > >
> > > For those who may be interested, I update compressed cache patch to
> > > kernel 2.6.19.
> > > This patch has no significantly changes.
> > >
> > > * Changelog: ccache-alpha-007 (applies to 2.6.19)
> > >
> > > Cheers,
> > >
> > > -- Allan Bezerra
> > >
> > >
> > >
> ------------------------------------------------------------------------
> > >
> >
> >
> >
> >
> -------------------------------------------------------------------------
> > Using Tomcat but need to do more? Need to support web services,
> security?
> > Get stuff done quickly with pre-integrated technology to make your job
> easier
> > Download IBM WebSphere Application Server v.1.0.1 based on Apache
> Geronimo
> > http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
>
> > _______________________________________________
> > linuxcompressed-devel mailing list
> > lin...@li...
> > https://lists.sourceforge.net/lists/listinfo/linuxcompressed-devel
> >
>
>
>
> ------------------------------
>
> -------------------------------------------------------------------------
> Using Tomcat but need to do more? Need to support web services, security?
> Get stuff done quickly with pre-integrated technology to make your job
> easier
> Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
>
> http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
>
> ------------------------------
>
> _______________________________________________
> linuxcompressed-devel mailing list
> lin...@li...
> https://lists.sourceforge.net/lists/listinfo/linuxcompressed-devel
>
>
> End of linuxcompressed-devel Digest, Vol 5, Issue 5
> ***************************************************
>

Re: [lc-devel] Update Compressed cache alpha-007 to kernel 2.6.19

[Nitin G. <nit...@gm...>]

On 11/11/06, ace <ace...@at...> wrote:

Hi,

> Hi guys.
>
> What is the current status of compressed cache? I always see the 'alpha'
>   naming, is there anything considered moderately stable that we could
> test? Something with no known dataloss problems:) Something we could try
> on serious systems for several minutes to see what it does. If yes,

I never experienced any data corruption kind of problems while testing
it but still before you come to kill me consider not to try this on
'production' machine :)

> could you make a patch against a stable kernel (e.g. 2.6.19 final),
> because that is what we use. Thanks
>

CCaching patch posted by Allan is for 2.6.19 [I'm not sure which -rc]
(though I could not test this patch!)

Cheers,
Nitin



> Peter
>
> Allan Bezerra wrote:
> > ------------
> > Project: Compressed Caching for Linux
> > Project Home: http://linuxcompressed.sourceforge.net
> > <http://linuxcompressed.sourceforge.net>
> > Git (web): http://dev.laptop.org/git.do?p=projects/linux-mm-cc
> > Git (git): git://dev.laptop.org/projects/linux-mm-cc
> > ------------
> >
> > Hi Nitin and all!
> >
> > For those who may be interested, I update compressed cache patch to
> > kernel 2.6.19.
> > This patch has no significantly changes.
> >
> > * Changelog: ccache-alpha-007 (applies to 2.6.19)
> >
> > Cheers,
> >
> > -- Allan Bezerra
> >
> >
> > ------------------------------------------------------------------------
> >
>
>
>
> -------------------------------------------------------------------------
> Using Tomcat but need to do more? Need to support web services, security?
> Get stuff done quickly with pre-integrated technology to make your job easier
> Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
> http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
> _______________________________________________
> linuxcompressed-devel mailing list
> lin...@li...
> https://lists.sourceforge.net/lists/listinfo/linuxcompressed-devel
>

Re: [lc-devel] Update Compressed cache alpha-007 to kernel 2.6.19

[ace <ace...@at...>]

Hi guys.

What is the current status of compressed cache? I always see the 'alpha'
  naming, is there anything considered moderately stable that we could
test? Something with no known dataloss problems:) Something we could try
on serious systems for several minutes to see what it does. If yes,
could you make a patch against a stable kernel (e.g. 2.6.19 final),
because that is what we use. Thanks

Peter

Allan Bezerra wrote:
> ------------
> Project: Compressed Caching for Linux
> Project Home: http://linuxcompressed.sourceforge.net
> <http://linuxcompressed.sourceforge.net>
> Git (web): http://dev.laptop.org/git.do?p=projects/linux-mm-cc
> Git (git): git://dev.laptop.org/projects/linux-mm-cc
> ------------
> 
> Hi Nitin and all!
> 
> For those who may be interested, I update compressed cache patch to
> kernel 2.6.19.
> This patch has no significantly changes.
> 
> * Changelog: ccache-alpha-007 (applies to 2.6.19)
> 
> Cheers,
> 
> -- Allan Bezerra
> 
> 
> ------------------------------------------------------------------------
>