Skip to contentSkip to conversation

Add LZO1X compression support to the kernel

PATCH In review Richard Purdie 3 participants 5 messages Jun 6, 2007 – Jun 7, 2007 Library code

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Add LZO1X compression support to the kernel

Add LZO1X compression/decompression support to the kernel.

This has been created by taking my originally proposed patch and slowly reworking it to conform to CodingStyle whilst periodically comparing the output bytecode with the original.

The result is a version which gives the exactly same bytecode as the original code on x86_32, x86_64 and ARM (the ARM version did differ in one place but the code is functionally the same and it looks like a gcc optimisation issue).

There are some differences between this version and Nitin's. This version removes the LZO_ALIGNED_OK_4 code paths since these are not active in minilzo on any machine. Mine also only activates the unaligned access ok code paths on x86_32 and x86_64, again in common with minilzo. This was not functional in my original patch due to issues with the way the kernel defines UINT_MAX compared to userspace as detailed elsewhere.

There is some ugliness I've not removed, particularly the PTR_*() defines and the associated two if statements. I think this is the cause of the code differences I originally saw between Nitin's version and mine in the compressor so I've left these for further examination. The bytecode does change quite drastically if I attempt to simplify that code.

Also, my version probably adheres to coding style a little more closely since I moved some variable definitions around and removed a ton of pointless casts.

Nitin: Have you any objections to this version? If not, I'll finish analysing the PTR_ code changes and then hopefully we can get something into -mm...

---
 include/linux/lzo.h        |   51 ++++++++
 lib/Kconfig                |    6 
 lib/Makefile               |    2 
 lib/lzo/Makefile           |    6 
 lib/lzo/lzo1x_compress.c   |  225 ++++++++++++++++++++++++++++++++++++
 lib/lzo/lzo1x_decompress.c |  274 +++++++++++++++++++++++++++++++++++++++++++++
 lib/lzo/lzodefs.h          |   71 +++++++++++
 7 files changed, 635 insertions(+)
include/linux/lzo.h new file +51 -0
Index: linux-2.6.21/include/linux/lzo.h
===================================================================
@@ -0,0 +1,51 @@
+/*
+ * LZO Public Kernel Interface
+ * A mini subset of the LZO real-time data compression library
+ *
+ * Copyright (C) 2007 Nokia Corporation. All rights reserved.
+ *
+ * Author: Richard Purdie <[email protected]>
+ *
+ * This program 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.
+ *
+ * This program 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 this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
+ * 02110-1301 USA
+ *
+ */
+
+#define LZO1X_MEM_COMPRESS	(16384 * sizeof(unsigned char *))
+#define LZO1X_1_MEM_COMPRESS	LZO1X_MEM_COMPRESS
+
+#define lzo1x_worst_compress(x) (x + (x / 64) + 16 + 3)
+
+int lzo1x_1_compress(const unsigned char *src, size_t src_len,
+			unsigned char *dst, size_t *dst_len, void *wrkmem);
+
+/* safe decompression with overrun testing */
+int lzo1x_decompress_safe(const unsigned char *src, size_t src_len,
+			unsigned char *dst, size_t *dst_len);
+
+/*
+ * Return values (< 0 = Error)
+ */
+#define LZO_E_OK                    0
+#define LZO_E_ERROR                 (-1)
+#define LZO_E_OUT_OF_MEMORY         (-2)
+#define LZO_E_NOT_COMPRESSIBLE      (-3)
+#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)
+
+
lib/Kconfig +6 -0
Index: linux-2.6.21/lib/Kconfig
===================================================================
@@ -80,6 +80,12 @@ config ZLIB_INFLATE
 config ZLIB_DEFLATE
 	tristate
 
+config LZO_COMPRESS
+	tristate
+
+config LZO_DECOMPRESS
+	tristate
+
 #
 # Generic allocator support is selected if needed
 #
lib/Makefile +2 -0
Index: linux-2.6.21/lib/Makefile
===================================================================
@@ -51,6 +51,8 @@ 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_LZO_COMPRESS) += lzo/
+obj-$(CONFIG_LZO_DECOMPRESS) += lzo/
 
 obj-$(CONFIG_TEXTSEARCH) += textsearch.o
 obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o
lib/lzo/Makefile new file +6 -0
Index: linux-2.6.21/lib/lzo/Makefile
===================================================================
@@ -0,0 +1,6 @@
+lzo_compress-objs := lzo1x_compress.o
+lzo_decompress-objs := lzo1x_decompress.o
+
+obj-$(CONFIG_LZO_COMPRESS) += lzo_compress.o
+obj-$(CONFIG_LZO_DECOMPRESS) += lzo_decompress.o
+
lib/lzo/lzodefs.h new file +71 -0

71 lines not on this page · raw message

lib/lzo/lzo1x_compress.c new file +225 -0

225 lines not on this page · raw message

lib/lzo/lzo1x_decompress.c new file +274 -0

274 lines not on this page · raw message

#1 lore raw

On 6/6/07, Richard Purdie <[email protected]> wrote:
<snip>

Quoted 5 lines

Nitin: Have you any objections to this version? If not, I'll finish analysing the PTR_ code changes and then hopefully we can get something into -mm...

Your code now looks nice and clean. But I don't know what you want. I already spent lot of time on version 7 I posted and contains all those corrections which were suggested for my earlier version. I cannot ask you to look into possible problems (if any) in my code now since you are not interested in that anyway. So, please continue this duplication.

Thanks,
Nitin

#2 lore raw
Quoted 6 lines · Nitin Gupta

Your code now looks nice and clean. But I don't know what you want. I already spent lot of time on version 7 I posted and contains all those corrections which were suggested for my earlier version. I cannot ask you to look into possible problems (if any) in my code now since you are not interested in that anyway. So, please continue this duplication.

What I (and others) repeatedly asked for was an explanation of why there were the differences between the bytecode from your version and the bytecode from mine. This was never explained by you and I was left to do this myself. Sadly, doing so meant some duplication.

Anyhow, I think I can now explain the differences. Now we have two versions, its a question of how to proceed. Basically one needs to be merged into the other. I will try and compare the two patches and see what differences we have.

Regards,

Richard

#3 lore raw
Quoted 8 lines · Richard Purdie
Quoted 6 lines · Nitin Gupta

Your code now looks nice and clean. But I don't know what you want. I already spent lot of time on version 7 I posted and contains all those corrections which were suggested for my earlier version. I cannot ask you to look into possible problems (if any) in my code now since you are not interested in that anyway. So, please continue this duplication.

Quoted 5 lines

What I (and others) repeatedly asked for was an explanation of why there were the differences between the bytecode from your version and the bytecode from mine. This was never explained by you and I was left to do this myself. Sadly, doing so meant some duplication.

I don't know the reason for bytecode difference. I focused on making sure that the C code is functionally identical to original code. I never did a bytecode diff.

Quoted 4 lines

Anyhow, I think I can now explain the differences. Now we have two versions, its a question of how to proceed. Basically one needs to be merged into the other. I will try and compare the two patches and see what differences we have.

Sounds good.

Regards,
Nitin

#4 lore raw
In reply to Richard Purdie

lib/lzo/lzodefs.h line 71

Quoted 6 lines · Richard Purdie
lib/lzo/lzodefs.h new file +6 -0
+/* Which machines to allow unaligned accesses on */
+#if defined(CONFIG_X86_32) || defined(CONFIG_X86_64)
+#define LZO_UNALIGNED_OK_2
+#define LZO_UNALIGNED_OK_4
+#endif
+

This is silly, just use get/put_unaligned(). This same issue was pointed out in Nitin's patch and already corrected there, perhaps it would be more constructive to work on getting cleanups from both implementations integrated in to something mergeable rather than trying to see who can get in to -mm first.