Merge tag 'lzo-update-signature-20130226' of git://github.com/markus-oberhumer/linux

Pull LZO compression update from Markus Oberhumer:
 "Summary:
  ========

  Update the Linux kernel LZO compression and decompression code to the
  current upstream version which features significant performance
  improvements on modern machines.

  Some *synthetic* benchmarks:
  ============================

    x86_64 (Sandy Bridge), gcc-4.6 -O3, Silesia test corpus, 256 kB block-size:

                     compression speed   decompression speed

    LZO-2005    :         150 MB/sec          468 MB/sec
    LZO-2012    :         434 MB/sec         1210 MB/sec

    i386 (Sandy Bridge), gcc-4.6 -O3, Silesia test corpus, 256 kB block-size:

                     compression speed   decompression speed

    LZO-2005    :         143 MB/sec          409 MB/sec
    LZO-2012    :         372 MB/sec         1121 MB/sec

    armv7 (Cortex-A9), Linaro gcc-4.6 -O3, Silesia test corpus, 256 kB block-size:

                     compression speed   decompression speed

    LZO-2005    :          27 MB/sec           84 MB/sec
    LZO-2012    :          44 MB/sec          117 MB/sec
  **LZO-2013-UA :          47 MB/sec          167 MB/sec

  Legend:

    LZO-2005    : LZO version in current 3.8 kernel (which is based on
                     the LZO 2.02 release from 2005)
    LZO-2012    : updated LZO version available in linux-next
  **LZO-2013-UA : updated LZO version available in linux-next plus experimental
                     ARM Unaligned Access patch. This needs approval
                     from some ARM maintainer ist NOT YET INCLUDED."

Andrew Morton <akpm@linux-foundation.org> acks it and says:
 "There's a new LZ4 on the block which is even faster than the sped-up
  LZO, but various filesystems and things use LZO"

* tag 'lzo-update-signature-20130226' of git://github.com/markus-oberhumer/linux:
  crypto: testmgr - update LZO compression test vectors
  lib/lzo: Update LZO compression to current upstream version
  lib/lzo: Rename lzo1x_decompress.c to lzo1x_decompress_safe.c

6 files changed, 460 insertions, 409 deletions

diff --git a/lib/decompress_unlzo.c b/lib/decompress_unlzo.c
index 4531294fa62f..960183d4258f 100644
--- a/lib/decompress_unlzo.c
+++ b/lib/decompress_unlzo.c
@@ -31,7 +31,7 @@
  */
 
 #ifdef STATIC
-#include "lzo/lzo1x_decompress.c"
+#include "lzo/lzo1x_decompress_safe.c"
 #else
 #include <linux/decompress/unlzo.h>
 #endif
diff --git a/lib/lzo/Makefile b/lib/lzo/Makefile
index e764116ea12d..f0f7d7ca2b83 100644
--- a/lib/lzo/Makefile
+++ b/lib/lzo/Makefile
@@ -1,5 +1,5 @@
 lzo_compress-objs := lzo1x_compress.o
-lzo_decompress-objs := lzo1x_decompress.o
+lzo_decompress-objs := lzo1x_decompress_safe.o
 
 obj-$(CONFIG_LZO_COMPRESS) += lzo_compress.o
 obj-$(CONFIG_LZO_DECOMPRESS) += lzo_decompress.o
diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
index a6040990a62e..236eb21167b5 100644
--- a/lib/lzo/lzo1x_compress.c
+++ b/lib/lzo/lzo1x_compress.c
@@ -1,194 +1,243 @@
 /*
- *  LZO1X Compressor from MiniLZO
+ *  LZO1X Compressor from LZO
  *
- *  Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <markus@oberhumer.com>
+ *  Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com>
  *
  *  The full LZO package can be found at:
  *  http://www.oberhumer.com/opensource/lzo/
  *
- *  Changed for kernel use by:
+ *  Changed for Linux kernel use by:
  *  Nitin Gupta <nitingupta910@gmail.com>
  *  Richard Purdie <rpurdie@openedhand.com>
  */
 
 #include <linux/module.h>
 #include <linux/kernel.h>
-#include <linux/lzo.h>
 #include <asm/unaligned.h>
+#include <linux/lzo.h>
 #include "lzodefs.h"
 
 static noinline size_t
-_lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
-                unsigned char *out, size_t *out_len, void *wrkmem)
+lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
+                    unsigned char *out, size_t *out_len,
+                    size_t ti, void *wrkmem)
 {
+        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 ** const dict = wrkmem;
-        const unsigned char *ip = in, *ii = ip;
-        const unsigned char *end, *m, *m_pos;
-        size_t m_off, m_len, dindex;
-        unsigned char *op = out;
+        const unsigned char * const ip_end = in + in_len - 20;
+        const unsigned char *ii;
+        lzo_dict_t * const dict = (lzo_dict_t *) wrkmem;
 
-        ip += 4;
+        op = out;
+        ip = in;
+        ii = ip;
+        ip += ti < 4 ? 4 - ti : 0;
 
         for (;;) {
-                dindex = ((size_t)(0x21 * DX3(ip, 5, 5, 6)) >> 5) & D_MASK;
-                m_pos = dict[dindex];
-
-                if (m_pos < in)
-                        goto literal;
-
-                if (ip == m_pos || ((size_t)(ip - m_pos) > M4_MAX_OFFSET))
-                        goto literal;
-
-                m_off = ip - m_pos;
-                if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
-                        goto try_match;
-
-                dindex = (dindex & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f);
-                m_pos = dict[dindex];
-
-                if (m_pos < in)
-                        goto literal;
-
-                if (ip == m_pos || ((size_t)(ip - m_pos) > M4_MAX_OFFSET))
-                        goto literal;
-
-                m_off = ip - m_pos;
-                if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
-                        goto try_match;
-
-                goto literal;
-
-try_match:
-                if (get_unaligned((const unsigned short *)m_pos)
-                                == get_unaligned((const unsigned short *)ip)) {
-                        if (likely(m_pos[2] == ip[2]))
-                                        goto match;
-                }
-
+                const unsigned char *m_pos;
+                size_t t, m_len, m_off;
+                u32 dv;
 literal:
-                dict[dindex] = ip;
-                ++ip;
+                ip += 1 + ((ip - ii) >> 5);
+next:
                 if (unlikely(ip >= ip_end))
                         break;
-                continue;
-
-match:
-                dict[dindex] = ip;
-                if (ip != ii) {
-                        size_t t = ip - ii;
+                dv = get_unaligned_le32(ip);
+                t = ((dv * 0x1824429d) >> (32 - D_BITS)) & D_MASK;
+                m_pos = in + dict[t];
+                dict[t] = (lzo_dict_t) (ip - in);
+                if (unlikely(dv != get_unaligned_le32(m_pos)))
+                        goto literal;
 
+                ii -= ti;
+                ti = 0;
+                t = ip - ii;
+                if (t != 0) {
                         if (t <= 3) {
                                 op[-2] |= t;
-                        } else if (t <= 18) {
+                                COPY4(op, ii);
+                                op += t;
+                        } else if (t <= 16) {
                                 *op++ = (t - 3);
+                                COPY8(op, ii);
+                                COPY8(op + 8, ii + 8);
+                                op += t;
                         } else {
-                                size_t tt = t - 18;
-
-                                *op++ = 0;
-                                while (tt > 255) {
-                                        tt -= 255;
+                                if (t <= 18) {
+                                        *op++ = (t - 3);
+                                } else {
+                                        size_t tt = t - 18;
                                         *op++ = 0;
+                                        while (unlikely(tt > 255)) {
+                                                tt -= 255;
+                                                *op++ = 0;
+                                        }
+                                        *op++ = tt;
                                 }
-                                *op++ = tt;
+                                do {
+                                        COPY8(op, ii);
+                                        COPY8(op + 8, ii + 8);
+                                        op += 16;
+                                        ii += 16;
+                                        t -= 16;