Hi,
This is kernel port of LZO1X de/compression algo stripped down to just ~500 LOC!
It is derived from original LZO 2.02 code found at:
http://www.oberhumer.com/opensource/lzo/download/
The code has also been reformatted to match general kernel style.
Facts for LZO (at least for original code. Should hold true for this
port also - hence the RFC!):
- The compressor can never overrun buffer.
- The "non-safe" version of decompressor can never overrun buffer if
compressed data is unmodified. I am not sure about this if compressed
data is malicious (to be confirmed from the author).
- The "safe" version can never crash (buffer overrun etc.) - confirmed
from the author.
This patch, as of yet, only gives 'non-safe' version of decompressor.
The 'safe' version will be included soon.
Since 'non-safe' version has no problems if compressed data is
unmodified, it is useful in cases we have such guarantees on
compressed data and hence don't want additional overhead of 'safe'
version. For e.g. Compressed Caching project
(http://linuxcompressed.sourceforge.net) has been using the 'non-safe'
version of LZO1X since long time without any problems w.r.t.
de/compression itself.
For now, I have tested this on x86 only.
Signed-off-by: Nitin Gupta <[email protected]>
---
diff --git a/include/linux/lzo1x.h b/include/linux/lzo1x.h
new file mode 100755
index 0000000..aae547e
--- /dev/null
+++ b/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
+ <[email protected]>
+ 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
+ <[email protected]>
+ */
+
+#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
diff --git a/lib/Kconfig b/lib/Kconfig
index 2e7ae6b..9d30b1f 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
+
#
# 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..322683e
--- /dev/null
+++ b/lib/lzo1x/Makefile
@@ -0,0 +1,2 @@
+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..02e3324
--- /dev/null
+++ b/lib/lzo1x/lzo1x_compress.c
@@ -0,0 +1,255 @@
+/* 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
+ <[email protected]>
+ 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
+ <[email protected]>
+ */
+
+#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);
+}
+
+
+/*
+ * 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 = pd(op, out);
+ return 0;
+}
+
+EXPORT_SYMBOL(lzo1x_compress);
diff --git a/lib/lzo1x/lzo1x_decompress.c b/lib/lzo1x/lzo1x_decompress.c
new file mode 100755
index 0000000..fbd4d69
--- /dev/null
+++ b/lib/lzo1x/lzo1x_decompress.c
@@ -0,0 +1,216 @@
+/* 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
+ <[email protected]>
+ 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
+ <[email protected]>
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <asm/byteorder.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;
+ 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);
diff --git a/lib/lzo1x/lzo1x_int.h b/lib/lzo1x/lzo1x_int.h
new file mode 100755
index 0000000..4dd993d
--- /dev/null
+++ b/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
+ <[email protected]>
+ 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
+ <[email protected]>
+ */
+
+#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) *(uint32_t *)(dst) = *(uint32_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 */
Good work..
On Fri, May 18, 2007 at 03:28:31PM +0530, Nitin Gupta wrote:
> Facts for LZO (at least for original code. Should hold true for this
> port also - hence the RFC!):
> - The compressor can never overrun buffer.
> - The "non-safe" version of decompressor can never overrun buffer if
> compressed data is unmodified. I am not sure about this if compressed
> data is malicious (to be confirmed from the author).
> - The "safe" version can never crash (buffer overrun etc.) - confirmed
> from the author.
What's the proof?
> +/* LZO1X_1 compression */
> +int
> +lzo1x_compress(const unsigned char *src, size_t src_len,
> + unsigned char *dst, size_t *dst_len,
> + void *workmem);
int lzo1x_compress(const unsigned char *src, size_t src_len,
unsigned char *dst, size_t *dst_len,
void *workmem);
is the preferred style.
> + 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
> + <[email protected]>
> + 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
> + <[email protected]>
> + */
> +
> +#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;
Is the register directive really useful? Or any subsequent usage of that
directive?
> + 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);
Put a space after the delimiter: DINDEX1(dindex, ip); This happens in
many places in the source, fix them all.
> + 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);
Useless brackets: (unsigned char) tt
> + }
> + do *op++ = *ii++; while (--t > 0);
memcpy(op, ii, t); ? Happens in other places as well.
> + }
> +
> + /* 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);
> +}
> +
> +
> +/*
> + * 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 = pd(op, out);
> + return 0;
> +}
> +
> +EXPORT_SYMBOL(lzo1x_compress);
> diff --git a/lib/lzo1x/lzo1x_decompress.c b/lib/lzo1x/lzo1x_decompress.c
> new file mode 100755
> index 0000000..fbd4d69
> --- /dev/null
> +++ b/lib/lzo1x/lzo1x_decompress.c
> @@ -0,0 +1,216 @@
> +/* 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
> + <[email protected]>
> + 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
> + <[email protected]>
> + */
> +
> +#include <linux/kernel.h>
> +#include <linux/module.h>
> +#include <asm/byteorder.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;
> + 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);
> diff --git a/lib/lzo1x/lzo1x_int.h b/lib/lzo1x/lzo1x_int.h
> new file mode 100755
> index 0000000..4dd993d
> --- /dev/null
> +++ b/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
> + <[email protected]>
> + 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
> + <[email protected]>
> + */
> +
> +#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) *(uint32_t *)(dst) = *(uint32_t *)(src)
Use u32.
--
Heikki Orsila Barbie's law:
[email protected] "Math is hard, let's go shopping!"
http://www.iki.fi/shd
On 5/18/07, Nitin Gupta <[email protected]> wrote:
> + Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
> + Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
[snip]
So how about making that a little less verbose. Say like:
Copyright (c) 1996-2005 Markus Franz Xaver and Johannes Oberhumer
> +#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)
Please make these static inline functions.
> +#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)))
[snip]
> +#define COPY4(dst,src) *(uint32_t *)(dst) = *(uint32_t *)(src)
Please drop these.
On 5/18/07, Pekka Enberg <[email protected]> wrote:
> So how about making that a little less verbose. Say like:
>
> Copyright (c) 1996-2005 Markus Franz Xaver and Johannes Oberhumer
Oh, the author's name really is "Markus Franz Xaver Johannes
Oberhumer." But please make the copyright statement one line.
Hi,
Thanks for review. My comments inline.
On 5/18/07, Heikki Orsila <[email protected]> wrote:
> Good work..
>
> On Fri, May 18, 2007 at 03:28:31PM +0530, Nitin Gupta wrote:
> > Facts for LZO (at least for original code. Should hold true for this
> > port also - hence the RFC!):
> > - The compressor can never overrun buffer.
> > - The "non-safe" version of decompressor can never overrun buffer if
> > compressed data is unmodified. I am not sure about this if compressed
> > data is malicious (to be confirmed from the author).
> > - The "safe" version can never crash (buffer overrun etc.) - confirmed
> > from the author.
>
> What's the proof?
I confirmned these from the author - I just ported this code. I think
he can answer you better - CC'ed him :-)
>
> > +/* LZO1X_1 compression */
> > +int
> > +lzo1x_compress(const unsigned char *src, size_t src_len,
> > + unsigned char *dst, size_t *dst_len,
> > + void *workmem);
>
> int lzo1x_compress(const unsigned char *src, size_t src_len,
> unsigned char *dst, size_t *dst_len,
> void *workmem);
>
> is the preferred style.
>
OK. Changed.
<snip>
> > + register const unsigned char *ip;
>
> Is the register directive really useful? Or any subsequent usage of that
> directive?
The author must be having some performance gain with this directive.
Though I didn't test performance changes with/without this directive.
> > + DINDEX1(dindex,ip);
>
> Put a space after the delimiter: DINDEX1(dindex, ip); This happens in
> many places in the source, fix them all.
OK.
> Useless brackets: (unsigned char) tt
>
OK.
> > + }
> > + do *op++ = *ii++; while (--t > 0);
>
> memcpy(op, ii, t); ? Happens in other places as well.
I looked more carefully into such cases. Following type of code blocks
are repeated at several places:
---
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);
}
---
Such entire blocks can be replaced by simple:
memcpy(op, ip, t + 4);
Since kernel has separate memcpy() implementation optimized for
specific archs, we shouldn't loose on perf while having simpler (and
shorter) code.
I will work on this and post again.
> > +#define COPY4(dst,src) *(uint32_t *)(dst) = *(uint32_t *)(src)
>
> Use u32.
>
What is the problem with uint32_t? Anyhow, I think COPY4 will
disappear after those memcpy changes :)
Thanks for comments. I will post revised patch soon.
Cheers,
Nitin
Hi,
On Fri, 2007-05-18 at 15:28 +0530, Nitin Gupta wrote:
> This is kernel port of LZO1X de/compression algo stripped down to just ~500 LOC!
> It is derived from original LZO 2.02 code found at:
> http://www.oberhumer.com/opensource/lzo/download/
> The code has also been reformatted to match general kernel style.
>
> Facts for LZO (at least for original code. Should hold true for this
> port also - hence the RFC!):
> - The compressor can never overrun buffer.
> - The "non-safe" version of decompressor can never overrun buffer if
> compressed data is unmodified. I am not sure about this if compressed
> data is malicious (to be confirmed from the author).
If the data is malicious, it *can* overrun the buffer.
> - The "safe" version can never crash (buffer overrun etc.) - confirmed
> from the author.
> This patch, as of yet, only gives 'non-safe' version of decompressor.
> The 'safe' version will be included soon.
How are you planning to add that back?
> Since 'non-safe' version has no problems if compressed data is
> unmodified, it is useful in cases we have such guarantees on
> compressed data and hence don't want additional overhead of 'safe'
> version. For e.g. Compressed Caching project
> (http://linuxcompressed.sourceforge.net) has been using the 'non-safe'
> version of LZO1X since long time without any problems w.r.t.
> de/compression itself.
>
> For now, I have tested this on x86 only.
The LZO author had some concerns about this code. The major issue he
highlighted was that it was 64-bit unsafe. Have you addressed that
problem? Has it been tested on 64bit?
I'm worried that in converting this code the way you have, you've
possibly introduced potential security holes. You've removed all bounds
checking and are going to have to add that back to create the "safe"
version of the decompression function. Until I mentioned it, you seemed
unaware of the potential problem and the comments above suggest you
don't understand this code as fully as I'd like with regard to
overflows.
The version I submitted has at least been subject to userspace scrutiny
over a period of time and is basically unchanged with regard to
security. It is much uglier though.
Richard
On Fri, 2007-05-18 at 16:57 +0530, Nitin Gupta wrote:
> On 5/18/07, Heikki Orsila <[email protected]> wrote:
> > Good work..
> >
> > On Fri, May 18, 2007 at 03:28:31PM +0530, Nitin Gupta wrote:
> > > Facts for LZO (at least for original code. Should hold true for this
> > > port also - hence the RFC!):
> > > - The compressor can never overrun buffer.
> > > - The "non-safe" version of decompressor can never overrun buffer if
> > > compressed data is unmodified. I am not sure about this if compressed
> > > data is malicious (to be confirmed from the author).
> > > - The "safe" version can never crash (buffer overrun etc.) - confirmed
> > > from the author.
> >
> > What's the proof?
>
> I confirmned these from the author - I just ported this code. I think
> he can answer you better - CC'ed him :-)
The thing is this is more your code now, not his and you should be able
to answer this question...
Regards,
Richard
On 138, 05 18, 2007 at 03:28:31PM +0530, Nitin Gupta wrote:
> Hi,
>
> This is kernel port of LZO1X de/compression algo stripped down to just ~500
> LOC!
> It is derived from original LZO 2.02 code found at:
> http://www.oberhumer.com/opensource/lzo/download/
> The code has also been reformatted to match general kernel style.
>
> Facts for LZO (at least for original code. Should hold true for this
> port also - hence the RFC!):
> - The compressor can never overrun buffer.
> - The "non-safe" version of decompressor can never overrun buffer if
> compressed data is unmodified. I am not sure about this if compressed
> data is malicious (to be confirmed from the author).
> - The "safe" version can never crash (buffer overrun etc.) - confirmed
> from the author.
>
> This patch, as of yet, only gives 'non-safe' version of decompressor.
> The 'safe' version will be included soon.
>
> Since 'non-safe' version has no problems if compressed data is
> unmodified, it is useful in cases we have such guarantees on
> compressed data and hence don't want additional overhead of 'safe'
> version. For e.g. Compressed Caching project
> (http://linuxcompressed.sourceforge.net) has been using the 'non-safe'
> version of LZO1X since long time without any problems w.r.t.
> de/compression itself.
>
> For now, I have tested this on x86 only.
>
> Signed-off-by: Nitin Gupta <[email protected]>
> ---
>
> diff --git a/include/linux/lzo1x.h b/include/linux/lzo1x.h
> new file mode 100755
> index 0000000..aae547e
> --- /dev/null
> +++ b/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
> + <[email protected]>
> + 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
> + <[email protected]>
> + */
> +
> +#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
> diff --git a/lib/Kconfig b/lib/Kconfig
> index 2e7ae6b..9d30b1f 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
> +
> #
> # 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..322683e
> --- /dev/null
> +++ b/lib/lzo1x/Makefile
> @@ -0,0 +1,2 @@
> +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..02e3324
> --- /dev/null
> +++ b/lib/lzo1x/lzo1x_compress.c
> @@ -0,0 +1,255 @@
> +/* 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
> + <[email protected]>
> + 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
> + <[email protected]>
> + */
> +
> +#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;
register keyword is meaningless for today's compiler.
> + 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;
Why not write this as `unsigned char *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)
> {
Empty if() body ?
> + } 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;
What's this magic number 0x4000 repeated everywhere ? M3_MAX_OFFSET perhaps ?
> + *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);
> +}
> +
> +
> +/*
> + * 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 = pd(op, out);
> + return 0;
> +}
> +
> +EXPORT_SYMBOL(lzo1x_compress);
> diff --git a/lib/lzo1x/lzo1x_decompress.c b/lib/lzo1x/lzo1x_decompress.c
> new file mode 100755
> index 0000000..fbd4d69
> --- /dev/null
> +++ b/lib/lzo1x/lzo1x_decompress.c
> @@ -0,0 +1,216 @@
> +/* 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
> + <[email protected]>
> + 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
> + <[email protected]>
> + */
> +
> +#include <linux/kernel.h>
> +#include <linux/module.h>
> +#include <asm/byteorder.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;
> + 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
IMHO you could write it this way:
m_pos = op - 1 - (le16_to_cpu(*(const u16 *)ip) >> 2);
> + 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
m_pos -= le16_to_cpu(*(const u16 *)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;
> + *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);
> diff --git a/lib/lzo1x/lzo1x_int.h b/lib/lzo1x/lzo1x_int.h
> new file mode 100755
> index 0000000..4dd993d
> --- /dev/null
> +++ b/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
> + <[email protected]>
> + 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
> + <[email protected]>
> + */
> +
> +#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) *(uint32_t *)(dst) = *(uint32_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 */
--
Andrey Panin | Linux and UNIX system administrator
[email protected] | PGP key: wwwkeys.pgp.net
On Fri, May 18, 2007 at 03:28:31PM +0530, Nitin Gupta wrote:
> +/* 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
This could stand some compression.
> + All Rights Reserved.
All rights are not reserved, otherwise it wouldn't be GPL.
--
Mathematics is the supreme nostalgia of our time.
"Nitin Gupta" <[email protected]> writes:
> Facts for LZO (at least for original code. Should hold true for this
> port also - hence the RFC!):
> - The compressor can never overrun buffer.
> - The "non-safe" version of decompressor can never overrun buffer if
> compressed data is unmodified. I am not sure about this if compressed
> data is malicious (to be confirmed from the author).
> - The "safe" version can never crash (buffer overrun etc.) - confirmed
> from the author.
I'm certainly missing something but what are the advantages of this
code (over current gzip etc.), and what will be using it?
--
Krzysztof Halasa
>I'm certainly missing something but what are the advantages of this
>code (over current gzip etc.), and what will be using it?
lzo compresses/decompresses much faster and using less cpu
this is how it compares:
bzip2: best compression, but damn slow performance
gzip: good compression with good performance
lzo: not that good compression but stunning performance
reiser4 and compressed caching is alrady using lzo compression, but they bring their own implementation - there are other projects which could make use of it - so it`s better to share the code by making it an integral part of the kernel.
roland
> Facts for LZO (at least for original code. Should hold true for this
> port also - hence the RFC!):
> - The compressor can never overrun buffer.
> - The "non-safe" version of decompressor can never overrun buffer if
> compressed data is unmodified. I am not sure about this if compressed
> data is malicious (to be confirmed from the author).
> - The "safe" version can never crash (buffer overrun etc.) - confirmed
> from the author.
I'm certainly missing something but what are the advantages of this
code (over current gzip etc.), and what will be using it?
--
Krzysztof Halasa
_______________________________________________________________
SMS schreiben mit WEB.DE FreeMail - einfach, schnell und
kostenguenstig. Jetzt gleich testen! http://f.web.de/?mc=021192
On Fri, May 18, 2007 at 11:14:57PM +0200, Krzysztof Halasa wrote:
> I'm certainly missing something but what are the advantages of this
> code (over current gzip etc.), and what will be using it?
Richard's patchset added it to the crypto library and wired it into
the JFFS2 file system. We recently started using LZO in a userland UDP
proxy to do stateless per-packet payload compression over a WAN link.
With ~1000 octet packets, our particular data stream sees 60% compression
with zlib, and 50% compression with (mini-)LZO, but LZO runs at ~5.6x
the speed of zlib. IIRC, that translates into > 700Mbps on the input
side on a 2GHZ Opteron, without any further tuning.
Once LZO is in the kernel, I'd like to see it wired into IPComp.
Unfortunately, last I checked only the "deflate" algorithm had an
assigned compression parameter index (CPI), so one will have to use a
private index until an official one is assigned.
Regards,
Bill Rugolsky
On Sat, 2007-05-19 at 14:55 -0400, Bill Rugolsky Jr. wrote:
> On Fri, May 18, 2007 at 11:14:57PM +0200, Krzysztof Halasa wrote:
> > I'm certainly missing something but what are the advantages of this
> > code (over current gzip etc.), and what will be using it?
>
> Richard's patchset added it to the crypto library and wired it into
> the JFFS2 file system.
Basically, LZO has much faster decompression speeds. For jffs2, there
was a 40% filesystem read speed improvement with LZO compared to zlib
and that resulted in a device booting 10% faster. The drawback was a
slight drop in file compression (say 5% although it varied a lot
depending on the test data). For lots of uses, that is an acceptable
compromise.
It appears resier4 is using LZO too.
> We recently started using LZO in a userland UDP
> proxy to do stateless per-packet payload compression over a WAN link.
> With ~1000 octet packets, our particular data stream sees 60% compression
> with zlib, and 50% compression with (mini-)LZO, but LZO runs at ~5.6x
> the speed of zlib. IIRC, that translates into > 700Mbps on the input
> side on a 2GHZ Opteron, without any further tuning.
Those figures sound comparable with my experiences...
Richard
Bill Rugolsky Jr. wrote:
>> I'm certainly missing something but what are the advantages of this
>> code (over current gzip etc.), and what will be using it?
>
> Richard's patchset added it to the crypto library and wired it into
> the JFFS2 file system. We recently started using LZO in a userland UDP
> proxy to do stateless per-packet payload compression over a WAN link.
> With ~1000 octet packets, our particular data stream sees 60% compression
> with zlib, and 50% compression with (mini-)LZO, but LZO runs at ~5.6x
> the speed of zlib. IIRC, that translates into > 700Mbps on the input
> side on a 2GHZ Opteron, without any further tuning.
>
> Once LZO is in the kernel, I'd like to see it wired into IPComp.
> Unfortunately, last I checked only the "deflate" algorithm had an
> assigned compression parameter index (CPI), so one will have to use a
> private index until an official one is assigned.
I also though of using LZO compression for some of the diskless nodes
which use iSCSI over 100 Mbit or slower.
Certainly, a fast de/compression algorithm in the kernel could bring
some new, innovative uses:
- there are talks about compressed filesystems (jffs2, reiser4, LogFS) -
why no one thought about a compressed tmpfs (should be way easier than a
compressed on-disk filesystem, as we don't have to care about data
recovery in event of a failure)?
- using compression for networking (like Bill mentioned)
- compressed caching
- compressed suspend-to-disk images (should suspend/restore faster this way)
--
Tomasz Chmielewski
http://wpkg.org
Hi,
On 5/18/07, Pekka Enberg <[email protected]> wrote:
> On 5/18/07, Nitin Gupta <[email protected]> wrote:
> > +#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)
>
> Please make these static inline functions.
>
What if compiler decides not to actully inline them? In that case
there will be significant perf. hit.
> > +#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)))
>
> [snip]
>
> > +#define COPY4(dst,src) *(uint32_t *)(dst) = *(uint32_t *)(src)
>
> Please drop these.
>
Done. Please see newer version posted.
Thanks for comments.
Cheers,
Nitin
Nitin Gupta wrote:
> What if compiler decides not to actully inline them? In that case
> there will be significant perf. hit.
Then you use __always_inline.
Pekka
Hi,
On 5/18/07, Andrey Panin <[email protected]> wrote:
> On 138, 05 18, 2007 at 03:28:31PM +0530, Nitin Gupta wrote:
> > + register const unsigned char *ip;
>
> register keyword is meaningless for today's compiler.
But can we assume that gcc is being used? What if we use compiler for
which it does matter (can't give example for this...)?
>
> > + 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;
>
> Why not write this as `unsigned char *op = out;` ?
>
Done.
> Empty if() body ?
No empty if() now.
> > + m_off -= 0x4000;
>
> What's this magic number 0x4000 repeated everywhere ? M3_MAX_OFFSET perhaps ?
I don't know :)
> > +#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
>
> IMHO you could write it this way:
>
> m_pos = op - 1 - (le16_to_cpu(*(const u16 *)ip) >> 2);
>
Shouldn't this be cpu_to_le16() ?
> > +#if defined(__LITTLE_ENDIAN)
> > + m_pos -= (*(const unsigned short *)ip) >> 2;
> > +#else
> > + m_pos -= (ip[0] >> 2) + (ip[1] << 6);
> > +#endif
>
> m_pos -= le16_to_cpu(*(const u16 *)ip) >> 2;
cpu_to_le16() ?
---
Can you please snip-out irrelevant code parts. It is real pain for
eyes to sneek out your comments otherwise :)
Thanks for your comments.
Cheers,
Nitin
On 5/22/07, Pekka Enberg <[email protected]> wrote:
> Nitin Gupta wrote:
> > What if compiler decides not to actully inline them? In that case
> > there will be significant perf. hit.
>
> Then you use __always_inline.
>
> Pekka
>
Ok. I will make them inline functions now.
Thanks,
Nitin
Hi,
On 5/18/07, Richard Purdie <[email protected]> wrote:
> > This patch, as of yet, only gives 'non-safe' version of decompressor.
> > The 'safe' version will be included soon.
>
> How are you planning to add that back?
>
Please see newer patch posted.
> The LZO author had some concerns about this code. The major issue he
> highlighted was that it was 64-bit unsafe. Have you addressed that
> problem?
I found certain parts which were 64-bit unsafe - corrected them. Now,
I couldn't see any more of such instances and posted as RFC :)
> Has it been tested on 64bit?
No. I am still looking for some 64-bit machine to test on (also some
Big-endian machine).
>
> I'm worried that in converting this code the way you have, you've
> possibly introduced potential security holes. You've removed all bounds
> checking and are going to have to add that back to create the "safe"
> version of the decompression function. Until I mentioned it, you seemed
> unaware of the potential problem and the comments above suggest you
> don't understand this code as fully as I'd like with regard to
> overflows.
I just did the 'logical' porting work. I don't understand the
algorithm itself since I could not find any document that describes
the same.
>
> The version I submitted has at least been subject to userspace scrutiny
> over a period of time and is basically unchanged with regard to
> security. It is much uglier though.
>
> Richard
Yes. But it will be even better if we can verify/correct this
cleaned-up version - shouldn't be that hard for just ~500 LOC :-)
Thanks for your comments.
- Nitin
Nitin Gupta wrote:
> Ok. I will make them inline functions now.
Btw, the only reason why any sane compiler would not inline
them is because it has reason to believe the end-result will
be more efficient. AFAIK you only need to use
__always_inline where it matters for correctness (like, for
example, in mm/slab.c) with GCC 4.0 and up.
On May 18 2007 15:28, Nitin Gupta wrote:
> +/* 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.
Oh holy, this is almost as bad as a 4-clause BSD-style license.
(Could the author just write "1996-2005" instead, like most
GNU tools do?)
Jan
--
On May 22 2007 14:38, Nitin Gupta wrote:
> On 5/18/07, Andrey Panin <[email protected]> wrote:
>> On 138, 05 18, 2007 at 03:28:31PM +0530, Nitin Gupta wrote:
>> > + register const unsigned char *ip;
>>
>> register keyword is meaningless for today's compiler.
>
> But can we assume that gcc is being used? What if we use compiler for
> which it does matter (can't give example for this...)?
How dumb must a compiler be? Although I cannot give an example either,
the register keyword MAY 'clog up' a register, making it harder for
cc to optimally use the whole register set. Imagine we had even less
regs than the x86(_32) already does.
Jan
--
On Tue, 2007-05-22 at 14:38 +0530, Nitin Gupta wrote:
[...]
> On 5/18/07, Andrey Panin <[email protected]> wrote:
> > On 138, 05 18, 2007 at 03:28:31PM +0530, Nitin Gupta wrote:
> > > + register const unsigned char *ip;
> >
> > register keyword is meaningless for today's compiler.
>
> But can we assume that gcc is being used? What if we use compiler for
Yes.
If another compiler wants to compile the kernel, it must have
implemented various widely used gcc extensions.
> which it does matter (can't give example for this...)?
The "register" keyword is and was always from start *at most* a hint to
the C compiler to use a register for that variable (similar to "inline"
BTW).
So every C compiler is allowed to simply ignore the "register" for any
reason - be it "not implemented" or "the compiler knows better".
Trivial reason: Think of a function with 100 register variables.
Bernd
--
Firmix Software GmbH http://www.firmix.at/
mobil: +43 664 4416156 fax: +43 1 7890849-55
Embedded Linux Development and Services
Bernd Petrovitsch wrote:
> The "register" keyword is and was always from start *at most* a hint to
> the C compiler to use a register for that variable (similar to "inline"
> BTW).
> So every C compiler is allowed to simply ignore the "register" for any
> reason - be it "not implemented" or "the compiler knows better".
> Trivial reason: Think of a function with 100 register variables.
>
The only useful semantic for "register" these days is that its illegal
to take the address of one. So it might be useful if you want to make
sure you have no aliases of a particular variable.
J