summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig15
-rw-r--r--lib/Kconfig.debug4
-rw-r--r--lib/Makefile6
-rw-r--r--lib/clz_ctz.c58
-rw-r--r--lib/crc-t10dif.c73
-rw-r--r--lib/decompress.c5
-rw-r--r--lib/decompress_unlz4.c187
-rw-r--r--lib/earlycpio.c2
-rw-r--r--lib/llist.c15
-rw-r--r--lib/locking-selftest.c1
-rw-r--r--lib/lz4/Makefile3
-rw-r--r--lib/lz4/lz4_compress.c443
-rw-r--r--lib/lz4/lz4_decompress.c326
-rw-r--r--lib/lz4/lz4defs.h156
-rw-r--r--lib/lz4/lz4hc_compress.c539
-rw-r--r--lib/mpi/longlong.h17
-rw-r--r--lib/percpu_counter.c2
-rw-r--r--lib/scatterlist.c133
-rw-r--r--lib/vsprintf.c124
19 files changed, 2028 insertions, 81 deletions
diff --git a/lib/Kconfig b/lib/Kconfig
index f1ed53c3aa44..71d9f81f6eed 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -66,8 +66,6 @@ config CRC16
config CRC_T10DIF
tristate "CRC calculation for the T10 Data Integrity Field"
- select CRYPTO
- select CRYPTO_CRCT10DIF
help
This option is only needed if a module that's not in the
kernel tree needs to calculate CRC checks for use with the
@@ -194,6 +192,15 @@ config LZO_COMPRESS
config LZO_DECOMPRESS
tristate
+config LZ4_COMPRESS
+ tristate
+
+config LZ4HC_COMPRESS
+ tristate
+
+config LZ4_DECOMPRESS
+ tristate
+
source "lib/xz/Kconfig"
#
@@ -218,6 +225,10 @@ config DECOMPRESS_LZO
select LZO_DECOMPRESS
tristate
+config DECOMPRESS_LZ4
+ select LZ4_DECOMPRESS
+ tristate
+
#
# Generic allocator support is selected if needed
#
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 88c8d9876702..1501aa553221 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -238,7 +238,7 @@ config DEBUG_SECTION_MISMATCH
any use of code/data previously in these sections would
most likely result in an oops.
In the code, functions and variables are annotated with
- __init, __cpuinit, etc. (see the full list in include/linux/init.h),
+ __init,, etc. (see the full list in include/linux/init.h),
which results in the code/data being placed in specific sections.
The section mismatch analysis is always performed after a full
kernel build, and enabling this option causes the following
@@ -1347,7 +1347,7 @@ config FAULT_INJECTION_STACKTRACE_FILTER
depends on FAULT_INJECTION_DEBUG_FS && STACKTRACE_SUPPORT
depends on !X86_64
select STACKTRACE
- select FRAME_POINTER if !PPC && !S390 && !MICROBLAZE && !ARM_UNWIND
+ select FRAME_POINTER if !MIPS && !PPC && !S390 && !MICROBLAZE && !ARM_UNWIND
help
Provide stacktrace filter for fault-injection capabilities
diff --git a/lib/Makefile b/lib/Makefile
index c09e38eca87a..7baccfd8a4e9 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -23,7 +23,7 @@ lib-y += kobject.o klist.o
obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
- gcd.o lcm.o list_sort.o uuid.o flex_array.o iovec.o \
+ gcd.o lcm.o list_sort.o uuid.o flex_array.o iovec.o clz_ctz.o \
bsearch.o find_last_bit.o find_next_bit.o llist.o memweight.o kfifo.o
obj-y += string_helpers.o
obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o
@@ -75,6 +75,9 @@ obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
obj-$(CONFIG_BCH) += bch.o
obj-$(CONFIG_LZO_COMPRESS) += lzo/
obj-$(CONFIG_LZO_DECOMPRESS) += lzo/
+obj-$(CONFIG_LZ4_COMPRESS) += lz4/
+obj-$(CONFIG_LZ4HC_COMPRESS) += lz4/
+obj-$(CONFIG_LZ4_DECOMPRESS) += lz4/
obj-$(CONFIG_XZ_DEC) += xz/
obj-$(CONFIG_RAID6_PQ) += raid6/
@@ -83,6 +86,7 @@ lib-$(CONFIG_DECOMPRESS_BZIP2) += decompress_bunzip2.o
lib-$(CONFIG_DECOMPRESS_LZMA) += decompress_unlzma.o
lib-$(CONFIG_DECOMPRESS_XZ) += decompress_unxz.o
lib-$(CONFIG_DECOMPRESS_LZO) += decompress_unlzo.o
+lib-$(CONFIG_DECOMPRESS_LZ4) += decompress_unlz4.o
obj-$(CONFIG_TEXTSEARCH) += textsearch.o
obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o
diff --git a/lib/clz_ctz.c b/lib/clz_ctz.c
new file mode 100644
index 000000000000..a8f8379eb49f
--- /dev/null
+++ b/lib/clz_ctz.c
@@ -0,0 +1,58 @@
+/*
+ * lib/clz_ctz.c
+ *
+ * Copyright (C) 2013 Chanho Min <chanho.min@lge.com>
+ *
+ * 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.
+ *
+ * __c[lt]z[sd]i2 can be overridden by linking arch-specific versions.
+ */
+
+#include <linux/export.h>
+#include <linux/kernel.h>
+
+int __weak __ctzsi2(int val)
+{
+ return __ffs(val);
+}
+EXPORT_SYMBOL(__ctzsi2);
+
+int __weak __clzsi2(int val)
+{
+ return 32 - fls(val);
+}
+EXPORT_SYMBOL(__clzsi2);
+
+#if BITS_PER_LONG == 32
+
+int __weak __clzdi2(long val)
+{
+ return 32 - fls((int)val);
+}
+EXPORT_SYMBOL(__clzdi2);
+
+int __weak __ctzdi2(long val)
+{
+ return __ffs((u32)val);
+}
+EXPORT_SYMBOL(__ctzdi2);
+
+#elif BITS_PER_LONG == 64
+
+int __weak __clzdi2(long val)
+{
+ return 64 - fls64((u64)val);
+}
+EXPORT_SYMBOL(__clzdi2);
+
+int __weak __ctzdi2(long val)
+{
+ return __ffs64((u64)val);
+}
+EXPORT_SYMBOL(__ctzdi2);
+
+#else
+#error BITS_PER_LONG not 32 or 64
+#endif
diff --git a/lib/crc-t10dif.c b/lib/crc-t10dif.c
index fe3428c07b47..fbbd66ed86cd 100644
--- a/lib/crc-t10dif.c
+++ b/lib/crc-t10dif.c
@@ -11,44 +11,57 @@
#include <linux/types.h>
#include <linux/module.h>
#include <linux/crc-t10dif.h>
-#include <linux/err.h>
-#include <linux/init.h>
-#include <crypto/hash.h>
-static struct crypto_shash *crct10dif_tfm;
+/* Table generated using the following polynomium:
+ * x^16 + x^15 + x^11 + x^9 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
+ * gt: 0x8bb7
+ */
+static const __u16 t10_dif_crc_table[256] = {
+ 0x0000, 0x8BB7, 0x9CD9, 0x176E, 0xB205, 0x39B2, 0x2EDC, 0xA56B,
+ 0xEFBD, 0x640A, 0x7364, 0xF8D3, 0x5DB8, 0xD60F, 0xC161, 0x4AD6,
+ 0x54CD, 0xDF7A, 0xC814, 0x43A3, 0xE6C8, 0x6D7F, 0x7A11, 0xF1A6,
+ 0xBB70, 0x30C7, 0x27A9, 0xAC1E, 0x0975, 0x82C2, 0x95AC, 0x1E1B,
+ 0xA99A, 0x222D, 0x3543, 0xBEF4, 0x1B9F, 0x9028, 0x8746, 0x0CF1,
+ 0x4627, 0xCD90, 0xDAFE, 0x5149, 0xF422, 0x7F95, 0x68FB, 0xE34C,
+ 0xFD57, 0x76E0, 0x618E, 0xEA39, 0x4F52, 0xC4E5, 0xD38B, 0x583C,
+ 0x12EA, 0x995D, 0x8E33, 0x0584, 0xA0EF, 0x2B58, 0x3C36, 0xB781,
+ 0xD883, 0x5334, 0x445A, 0xCFED, 0x6A86, 0xE131, 0xF65F, 0x7DE8,
+ 0x373E, 0xBC89, 0xABE7, 0x2050, 0x853B, 0x0E8C, 0x19E2, 0x9255,
+ 0x8C4E, 0x07F9, 0x1097, 0x9B20, 0x3E4B, 0xB5FC, 0xA292, 0x2925,
+ 0x63F3, 0xE844, 0xFF2A, 0x749D, 0xD1F6, 0x5A41, 0x4D2F, 0xC698,
+ 0x7119, 0xFAAE, 0xEDC0, 0x6677, 0xC31C, 0x48AB, 0x5FC5, 0xD472,
+ 0x9EA4, 0x1513, 0x027D, 0x89CA, 0x2CA1, 0xA716, 0xB078, 0x3BCF,
+ 0x25D4, 0xAE63, 0xB90D, 0x32BA, 0x97D1, 0x1C66, 0x0B08, 0x80BF,
+ 0xCA69, 0x41DE, 0x56B0, 0xDD07, 0x786C, 0xF3DB, 0xE4B5, 0x6F02,
+ 0x3AB1, 0xB106, 0xA668, 0x2DDF, 0x88B4, 0x0303, 0x146D, 0x9FDA,
+ 0xD50C, 0x5EBB, 0x49D5, 0xC262, 0x6709, 0xECBE, 0xFBD0, 0x7067,
+ 0x6E7C, 0xE5CB, 0xF2A5, 0x7912, 0xDC79, 0x57CE, 0x40A0, 0xCB17,
+ 0x81C1, 0x0A76, 0x1D18, 0x96AF, 0x33C4, 0xB873, 0xAF1D, 0x24AA,
+ 0x932B, 0x189C, 0x0FF2, 0x8445, 0x212E, 0xAA99, 0xBDF7, 0x3640,
+ 0x7C96, 0xF721, 0xE04F, 0x6BF8, 0xCE93, 0x4524, 0x524A, 0xD9FD,
+ 0xC7E6, 0x4C51, 0x5B3F, 0xD088, 0x75E3, 0xFE54, 0xE93A, 0x628D,
+ 0x285B, 0xA3EC, 0xB482, 0x3F35, 0x9A5E, 0x11E9, 0x0687, 0x8D30,
+ 0xE232, 0x6985, 0x7EEB, 0xF55C, 0x5037, 0xDB80, 0xCCEE, 0x4759,
+ 0x0D8F, 0x8638, 0x9156, 0x1AE1, 0xBF8A, 0x343D, 0x2353, 0xA8E4,
+ 0xB6FF, 0x3D48, 0x2A26, 0xA191, 0x04FA, 0x8F4D, 0x9823, 0x1394,
+ 0x5942, 0xD2F5, 0xC59B, 0x4E2C, 0xEB47, 0x60F0, 0x779E, 0xFC29,
+ 0x4BA8, 0xC01F, 0xD771, 0x5CC6, 0xF9AD, 0x721A, 0x6574, 0xEEC3,
+ 0xA415, 0x2FA2, 0x38CC, 0xB37B, 0x1610, 0x9DA7, 0x8AC9, 0x017E,
+ 0x1F65, 0x94D2, 0x83BC, 0x080B, 0xAD60, 0x26D7, 0x31B9, 0xBA0E,
+ 0xF0D8, 0x7B6F, 0x6C01, 0xE7B6, 0x42DD, 0xC96A, 0xDE04, 0x55B3
+};
__u16 crc_t10dif(const unsigned char *buffer, size_t len)
{
- struct {
- struct shash_desc shash;
- char ctx[2];
- } desc;
- int err;
-
- desc.shash.tfm = crct10dif_tfm;
- desc.shash.flags = 0;
- *(__u16 *)desc.ctx = 0;
+ __u16 crc = 0;
+ unsigned int i;
- err = crypto_shash_update(&desc.shash, buffer, len);
- BUG_ON(err);
+ for (i = 0 ; i < len ; i++)
+ crc = (crc << 8) ^ t10_dif_crc_table[((crc >> 8) ^ buffer[i]) & 0xff];
- return *(__u16 *)desc.ctx;
+ return crc;
}
EXPORT_SYMBOL(crc_t10dif);
-static int __init crc_t10dif_mod_init(void)
-{
- crct10dif_tfm = crypto_alloc_shash("crct10dif", 0, 0);
- return PTR_RET(crct10dif_tfm);
-}
-
-static void __exit crc_t10dif_mod_fini(void)
-{
- crypto_free_shash(crct10dif_tfm);
-}
-
-module_init(crc_t10dif_mod_init);
-module_exit(crc_t10dif_mod_fini);
-
MODULE_DESCRIPTION("T10 DIF CRC calculation");
MODULE_LICENSE("GPL");
diff --git a/lib/decompress.c b/lib/decompress.c
index f8fdedaf7b3d..4d1cd0397aab 100644
--- a/lib/decompress.c
+++ b/lib/decompress.c
@@ -11,6 +11,7 @@
#include <linux/decompress/unxz.h>
#include <linux/decompress/inflate.h>
#include <linux/decompress/unlzo.h>
+#include <linux/decompress/unlz4.h>
#include <linux/types.h>
#include <linux/string.h>
@@ -31,6 +32,9 @@
#ifndef CONFIG_DECOMPRESS_LZO
# define unlzo NULL
#endif
+#ifndef CONFIG_DECOMPRESS_LZ4
+# define unlz4 NULL
+#endif
struct compress_format {
unsigned char magic[2];
@@ -45,6 +49,7 @@ static const struct compress_format compressed_formats[] __initconst = {
{ {0x5d, 0x00}, "lzma", unlzma },
{ {0xfd, 0x37}, "xz", unxz },
{ {0x89, 0x4c}, "lzo", unlzo },
+ { {0x02, 0x21}, "lz4", unlz4 },
{ {0, 0}, NULL, NULL }
};
diff --git a/lib/decompress_unlz4.c b/lib/decompress_unlz4.c
new file mode 100644
index 000000000000..3e67cfad16ad
--- /dev/null
+++ b/lib/decompress_unlz4.c
@@ -0,0 +1,187 @@
+/*
+ * Wrapper for decompressing LZ4-compressed kernel, initramfs, and initrd
+ *
+ * Copyright (C) 2013, LG Electronics, Kyungsik Lee <kyungsik.lee@lge.com>
+ *
+ * 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.
+ */
+
+#ifdef STATIC
+#define PREBOOT
+#include "lz4/lz4_decompress.c"
+#else
+#include <linux/decompress/unlz4.h>
+#endif
+#include <linux/types.h>
+#include <linux/lz4.h>
+#include <linux/decompress/mm.h>
+#include <linux/compiler.h>
+
+#include <asm/unaligned.h>
+
+/*
+ * Note: Uncompressed chunk size is used in the compressor side
+ * (userspace side for compression).
+ * It is hardcoded because there is not proper way to extract it
+ * from the binary stream which is generated by the preliminary
+ * version of LZ4 tool so far.
+ */
+#define LZ4_DEFAULT_UNCOMPRESSED_CHUNK_SIZE (8 << 20)
+#define ARCHIVE_MAGICNUMBER 0x184C2102
+
+STATIC inline int INIT unlz4(u8 *input, int in_len,
+ int (*fill) (void *, unsigned int),
+ int (*flush) (void *, unsigned int),
+ u8 *output, int *posp,
+ void (*error) (char *x))
+{
+ int ret = -1;
+ size_t chunksize = 0;
+ size_t uncomp_chunksize = LZ4_DEFAULT_UNCOMPRESSED_CHUNK_SIZE;
+ u8 *inp;
+ u8 *inp_start;
+ u8 *outp;
+ int size = in_len;
+#ifdef PREBOOT
+ size_t out_len = get_unaligned_le32(input + in_len);
+#endif
+ size_t dest_len;
+
+
+ if (output) {
+ outp = output;
+ } else if (!flush) {
+ error("NULL output pointer and no flush function provided");
+ goto exit_0;
+ } else {
+ outp = large_malloc(uncomp_chunksize);
+ if (!outp) {
+ error("Could not allocate output buffer");
+ goto exit_0;
+ }
+ }
+
+ if (input && fill) {
+ error("Both input pointer and fill function provided,");
+ goto exit_1;
+ } else if (input) {
+ inp = input;
+ } else if (!fill) {
+ error("NULL input pointer and missing fill function");
+ goto exit_1;
+ } else {
+ inp = large_malloc(lz4_compressbound(uncomp_chunksize));
+ if (!inp) {
+ error("Could not allocate input buffer");
+ goto exit_1;
+ }
+ }
+ inp_start = inp;
+
+ if (posp)
+ *posp = 0;
+
+ if (fill)
+ fill(inp, 4);
+
+ chunksize = get_unaligned_le32(inp);
+ if (chunksize == ARCHIVE_MAGICNUMBER) {
+ inp += 4;
+ size -= 4;
+ } else {
+ error("invalid header");
+ goto exit_2;
+ }
+
+ if (posp)
+ *posp += 4;
+
+ for (;;) {
+
+ if (fill)
+ fill(inp, 4);
+
+ chunksize = get_unaligned_le32(inp);
+ if (chunksize == ARCHIVE_MAGICNUMBER) {
+ inp += 4;
+ size -= 4;
+ if (posp)
+ *posp += 4;
+ continue;
+ }
+ inp += 4;
+ size -= 4;
+
+ if (posp)
+ *posp += 4;
+
+ if (fill) {
+ if (chunksize > lz4_compressbound(uncomp_chunksize)) {
+ error("chunk length is longer than allocated");
+ goto exit_2;
+ }
+ fill(inp, chunksize);
+ }
+#ifdef PREBOOT
+ if (out_len >= uncomp_chunksize) {
+ dest_len = uncomp_chunksize;
+ out_len -= dest_len;
+ } else
+ dest_len = out_len;
+ ret = lz4_decompress(inp, &chunksize, outp, dest_len);
+#else
+ dest_len = uncomp_chunksize;
+ ret = lz4_decompress_unknownoutputsize(inp, chunksize, outp,
+ &dest_len);
+#endif
+ if (ret < 0) {
+ error("Decoding failed");
+ goto exit_2;
+ }
+
+ if (flush && flush(outp, dest_len) != dest_len)
+ goto exit_2;
+ if (output)
+ outp += dest_len;
+ if (posp)
+ *posp += chunksize;
+
+ size -= chunksize;
+
+ if (size == 0)
+ break;
+ else if (size < 0) {
+ error("data corrupted");
+ goto exit_2;
+ }
+
+ inp += chunksize;
+ if (fill)
+ inp = inp_start;
+ }
+
+ ret = 0;
+exit_2:
+ if (!input)
+ large_free(inp_start);
+exit_1:
+ if (!output)
+ large_free(outp);
+exit_0:
+ return ret;
+}
+
+#ifdef PREBOOT
+STATIC int INIT decompress(unsigned char *buf, int in_len,
+ int(*fill)(void*, unsigned int),
+ int(*flush)(void*, unsigned int),
+ unsigned char *output,
+ int *posp,
+ void(*error)(char *x)
+ )
+{
+ return unlz4(buf, in_len - 4, fill, flush, output, posp, error);
+}
+#endif
diff --git a/lib/earlycpio.c b/lib/earlycpio.c
index 8078ef49cb79..7aa7ce250c94 100644
--- a/lib/earlycpio.c
+++ b/lib/earlycpio.c
@@ -63,7 +63,7 @@ enum cpio_fields {
* the match returned an empty filename string.
*/
-struct cpio_data __cpuinit find_cpio_data(const char *path, void *data,
+struct cpio_data find_cpio_data(const char *path, void *data,
size_t len, long *offset)
{
const size_t cpio_header_len = 8*C_NFIELDS - 2;
diff --git a/lib/llist.c b/lib/llist.c
index 4a15115e90f8..4a70d120138c 100644
--- a/lib/llist.c
+++ b/lib/llist.c
@@ -39,18 +39,13 @@
bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last,
struct llist_head *head)
{
- struct llist_node *entry, *old_entry;
+ struct llist_node *first;
- entry = head->first;
- for (;;) {
- old_entry = entry;
- new_last->next = entry;
- entry = cmpxchg(&head->first, old_entry, new_first);
- if (entry == old_entry)
- break;
- }
+ do {
+ new_last->next = first = ACCESS_ONCE(head->first);
+ } while (cmpxchg(&head->first, first, new_first) != first);
- return old_entry == NULL;
+ return !first;
}
EXPORT_SYMBOL_GPL(llist_add_batch);
diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index aad024dde3c4..6dc09d8f4c24 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -12,6 +12,7 @@
*/
#include <linux/rwsem.h>
#include <linux/mutex.h>
+#include <linux/ww_mutex.h>
#include <linux/sched.h>
#include <linux/delay.h>
#include <linux/lockdep.h>
diff --git a/lib/lz4/Makefile b/lib/lz4/Makefile
new file mode 100644
index 000000000000..8085d04e9309
--- /dev/null
+++ b/lib/lz4/Makefile
@@ -0,0 +1,3 @@
+obj-$(CONFIG_LZ4_COMPRESS) += lz4_compress.o
+obj-$(CONFIG_LZ4HC_COMPRESS) += lz4hc_compress.o
+obj-$(CONFIG_LZ4_DECOMPRESS) += lz4_decompress.o
diff --git a/lib/lz4/lz4_compress.c b/lib/lz4/lz4_compress.c
new file mode 100644
index 000000000000..fd94058bd7f9
--- /dev/null
+++ b/lib/lz4/lz4_compress.c
@@ -0,0 +1,443 @@
+/*
+ * LZ4 - Fast LZ compression algorithm
+ * Copyright (C) 2011-2012, Yann Collet.
+ * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * You can contact the author at :
+ * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
+ * - LZ4 source repository : http://code.google.com/p/lz4/
+ *
+ * Changed for kernel use by:
+ * Chanho Min <chanho.min@lge.com>
+ */
+
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include <linux/lz4.h>
+#include <asm/unaligned.h>
+#include "lz4defs.h"
+
+/*
+ * LZ4_compressCtx :
+ * -----------------
+ * Compress 'isize' bytes from 'source' into an output buffer 'dest' of
+ * maximum size 'maxOutputSize'. * If it cannot achieve it, compression
+ * will stop, and result of the function will be zero.
+ * return : the number of bytes written in buffer 'dest', or 0 if the
+ * compression fails
+ */
+static inline int lz4_compressctx(void *ctx,
+ const char *source,
+ char *dest,
+ int isize,
+ int maxoutputsize)
+{
+ HTYPE *hashtable = (HTYPE *)ctx;
+ const u8 *ip = (u8 *)source;
+#if LZ4_ARCH64
+ const BYTE * const base = ip;
+#else
+ const int base = 0;
+#endif
+ const u8 *anchor = ip;
+ const u8 *const iend = ip + isize;
+ const u8 *const mflimit = iend - MFLIMIT;
+ #define MATCHLIMIT (iend - LASTLITERALS)
+
+ u8 *op = (u8 *) dest;
+ u8 *const oend = op + maxoutputsize;
+ int length;
+ const int skipstrength = SKIPSTRENGTH;
+ u32 forwardh;
+ int lastrun;
+
+ /* Init */
+ if (isize < MINLENGTH)
+ goto _last_literals;
+
+ memset((void *)hashtable, 0, LZ4_MEM_COMPRESS);
+
+ /* First Byte */
+ hashtable[LZ4_HASH_VALUE(ip)] = ip - base;
+ ip++;
+ forwardh = LZ4_HASH_VALUE(ip);
+
+ /* Main Loop */
+ for (;;) {
+ int findmatchattempts = (1U << skipstrength) + 3;
+ const u8 *forwardip = ip;
+ const u8 *ref;
+ u8 *token;
+
+ /* Find a match */
+ do {
+ u32 h = forwardh;
+ int step = findmatchattempts++ >> skipstrength;
+ ip = forwardip;
+ forwardip = ip + step;
+
+ if (unlikely(forwardip > mflimit))
+ goto _last_literals;
+
+ forwardh = LZ4_HASH_VALUE(forwardip);
+ ref = base + hashtable[h];
+ hashtable[h] = ip - base;
+ } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));
+
+ /* Catch up */
+ while ((ip > anchor) && (ref > (u8 *)source) &&
+ unlikely(ip[-1] == ref[-1])) {
+ ip--;
+ ref--;
+ }
+
+ /* Encode Literal length */
+ length = (int)(ip - anchor);
+ token = op++;
+ /* check output limit */
+ if (unlikely(op + length + (2 + 1 + LASTLITERALS) +
+ (length >> 8) > oend))
+ return 0;
+
+ if (length >= (int)RUN_MASK) {
+ int len;
+ *token = (RUN_MASK << ML_BITS);
+ len = length - RUN_MASK;
+ for (; len > 254 ; len -= 255)
+ *op++ = 255;
+ *op++ = (u8)len;
+ } else
+ *token = (length << ML_BITS);
+
+ /* Copy Literals */
+ LZ4_BLINDCOPY(anchor, op, length);
+_next_match:
+ /* Encode Offset */
+ LZ4_WRITE_LITTLEENDIAN_16(op, (u16)(ip - ref));
+
+ /* Start Counting */
+ ip += MINMATCH;
+ /* MinMatch verified */
+ ref += MINMATCH;
+ anchor = ip;
+ while (likely(ip < MATCHLIMIT - (STEPSIZE - 1))) {
+ #if LZ4_ARCH64
+ u64 diff = A64(ref) ^ A64(ip);
+ #else
+ u32 diff = A32(ref) ^ A32(ip);
+ #endif
+ if (!diff) {
+ ip += STEPSIZE;
+ ref += STEPSIZE;
+ continue;
+ }
+ ip += LZ4_NBCOMMONBYTES(diff);
+ goto _endcount;
+ }
+ #if LZ4_ARCH64
+ if ((ip < (MATCHLIMIT - 3)) && (A32(ref) == A32(ip))) {
+ ip += 4;
+ ref += 4;
+ }
+ #endif
+ if ((ip < (MATCHLIMIT - 1)) && (A16(ref) == A16(ip))) {
+ ip += 2;
+ ref += 2;
+ }
+ if ((ip < MATCHLIMIT) && (*ref == *ip))
+ ip++;
+_endcount:
+ /* Encode MatchLength */
+ length = (int)(ip - anchor);
+ /* Check output limit */
+ if (unlikely(op + (1 + LASTLITERALS) + (length >> 8) > oend))
+ return 0;
+ if (length >= (int)ML_MASK) {
+ *token += ML_MASK;
+ length -= ML_MASK;
+ for (; length > 509 ; length -= 510) {
+ *op++ = 255;
+ *op++ = 255;
+ }
+ if (length > 254) {
+ length -= 255;
+ *op++ = 255;
+ }
+ *op++ = (u8)length;
+ } else
+ *token += length;
+
+ /* Test end of chunk */
+ if (ip > mflimit) {
+ anchor = ip;
+ break;
+ }
+
+ /* Fill table */
+ hashtable[LZ4_HASH_VALUE(ip-2)] = ip - 2 - base;
+
+ /* Test next position */
+ ref = base + hashtable[LZ4_HASH_VALUE(ip)];
+ hashtable[LZ4_HASH_VALUE(ip)] = ip - base;
+ if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) {
+ token = op++;
+ *token = 0;
+ goto _next_match;
+ }
+
+ /* Prepare next loop */
+ anchor = ip++;
+ forwardh = LZ4_HASH_VALUE(ip);
+ }
+
+_last_literals:
+ /* Encode Last Literals */
+ lastrun = (int)(iend - anchor);
+ if (((char *)op - dest) + lastrun + 1
+ + ((lastrun + 255 - RUN_MASK) / 255) > (u32)maxoutputsize)
+ return 0;
+
+ if (lastrun >= (int)RUN_MASK) {
+ *op++ = (RUN_MASK << ML_BITS);
+ lastrun -= RUN_MASK;
+ for (; lastrun > 254 ; lastrun -= 255)
+ *op++ = 255;
+ *op++ = (u8)lastrun;
+ } else
+ *op++ = (lastrun << ML_BITS);
+ memcpy(op, anchor, iend - anchor);
+ op += iend - anchor;
+
+ /* End */
+ return (int)(((char *)op) - dest);
+}
+
+static inline int lz4_compress64kctx(void *ctx,
+ const char *source,
+ char *dest,
+ int isize,
+ int maxoutputsize)
+{
+ u16 *hashtable = (u16 *)ctx;
+ const u8 *ip = (u8 *) source;
+ const u8 *anchor = ip;
+ const u8 *const base = ip;
+ const u8 *const iend = ip + isize;
+ const u8 *const mflimit = iend - MFLIMIT;
+ #define MATCHLIMIT (iend - LASTLITERALS)
+
+ u8 *op = (u8 *) dest;
+ u8 *const oend = op + maxoutputsize;
+ int len, length;
+ const int skipstrength = SKIPSTRENGTH;
+ u32 forwardh;
+ int lastrun;
+
+ /* Init */
+ if (isize < MINLENGTH)
+ goto _last_literals;
+
+ memset((void *)hashtable, 0, LZ4_MEM_COMPRESS);
+
+ /* First Byte */
+ ip++;
+ forwardh = LZ4_HASH64K_VALUE(ip);
+
+ /* Main Loop */
+ for (;;) {
+ int findmatchattempts = (1U << skipstrength) + 3;
+ const u8 *forwardip = ip;
+ const u8 *ref;
+ u8 *token;
+
+ /* Find a match */
+ do {
+ u32 h = forwardh;
+ int step = findmatchattempts++ >> skipstrength;
+ ip = forwardip;
+ forwardip = ip + step;
+
+ if (forwardip > mflimit)
+ goto _last_literals;
+
+ forwardh = LZ4_HASH64K_VALUE(forwardip);
+ ref = base + hashtable[h];
+ hashtable[h] = (u16)(ip - base);
+ } while (A32(ref) != A32(ip));
+
+ /* Catch up */
+ while ((ip > anchor) && (ref > (u8 *)source)
+ && (ip[-1] == ref[-1])) {
+ ip--;
+ ref--;
+ }
+
+ /* Encode Literal length */
+ length = (int)(ip - anchor);
+ token = op++;
+ /* Check output limit */
+ if (unlikely(op + length + (2 + 1 + LASTLITERALS)
+ + (length >> 8) > oend))
+ return 0;
+ if (length >= (int)RUN_MASK) {
+ *token = (RUN_MASK << ML_BITS);
+ len = length - RUN_MASK;
+ for (; len > 254 ; len -= 255)
+ *op++ = 255;
+ *op++ = (u8)len;
+ } else
+ *token = (length << ML_BITS);
+
+ /* Copy Literals */
+ LZ4_BLINDCOPY(anchor, op, length);
+
+_next_match:
+ /* Encode Offset */
+ LZ4_WRITE_LITTLEENDIAN_16(op, (u16)(ip - ref));
+
+ /* Start Counting */
+ ip += MINMATCH;
+ /* MinMatch verified */
+ ref += MINMATCH;
+ anchor = ip;
+
+ while (ip < MATCHLIMIT - (STEPSIZE - 1)) {
+ #if LZ4_ARCH64
+ u64 diff = A64(ref) ^ A64(ip);
+ #else
+ u32 diff = A32(ref) ^ A32(ip);
+ #endif
+
+ if (!diff) {
+ ip += STEPSIZE;
+ ref += STEPSIZE;
+ continue;
+ }
+ ip += LZ4_NBCOMMONBYTES(diff);
+ goto _endcount;
+ }
+ #if LZ4_ARCH64
+ if ((ip < (MATCHLIMIT - 3)) && (A32(ref) == A32(ip))) {
+ ip += 4;
+ ref += 4;
+ }
+ #endif
+ if ((ip < (MATCHLIMIT - 1)) && (A16(ref) == A16(ip))) {
+ ip += 2;
+ ref += 2;
+ }
+ if ((ip < MATCHLIMIT) && (*ref == *ip))
+ ip++;
+_endcount:
+
+ /* Encode MatchLength */
+ len = (int)(ip - anchor);
+ /* Check output limit */
+ if (unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend))
+ return 0;
+ if (len >= (int)ML_MASK) {
+ *token += ML_MASK;
+ len -= ML_MASK;
+ for (; len > 509 ; len -= 510) {
+ *op++ = 255;
+ *op++ = 255;
+ }
+ if (len > 254) {
+ len -= 255;
+ *op++ = 255;
+ }
+ *op++ = (u8)len;
+ } else
+ *token += len;
+
+ /* Test end of chunk */
+ if (ip > mflimit) {
+ anchor = ip;
+ break;
+ }
+
+ /* Fill table */
+ hashtable[LZ4_HASH64K_VALUE(ip-2)] = (u16)(ip - 2 - base);
+
+ /* Test next position */
+ ref = base + hashtable[LZ4_HASH64K_VALUE(ip)];
+ hashtable[LZ4_HASH64K_VALUE(ip)] = (u16)(ip - base);
+ if (A32(ref) == A32(ip)) {
+ token = op++;
+ *token = 0;
+ goto _next_match;
+ }
+
+ /* Prepare next loop */
+ anchor = ip++;
+ forwardh = LZ4_HASH64K_VALUE(ip);
+ }
+
+_last_literals:
+ /* Encode Last Literals */
+ lastrun = (int)(iend - anchor);
+ if (op + lastrun + 1 + (lastrun - RUN_MASK + 255) / 255 > oend)
+ return 0;
+ if (lastrun >= (int)RUN_MASK) {
+ *op++ = (RUN_MASK << ML_BITS);
+ lastrun -= RUN_MASK;
+ for (; lastrun > 254 ; lastrun -= 255)
+ *op++ = 255;
+ *op++ = (u8)lastrun;
+ } else
+ *op++ = (lastrun << ML_BITS);
+ memcpy(op, anchor, iend - anchor);
+ op += iend - anchor;
+ /* End */
+ return (int)(((char *)op) - dest);
+}
+
+int lz4_compress(const unsigned char *src, size_t src_len,
+ unsigned char *dst, size_t *dst_len, void *wrkmem)
+{
+ int ret = -1;
+ int out_len = 0;
+
+ if (src_len < LZ4_64KLIMIT)
+ out_len = lz4_compress64kctx(wrkmem, src, dst, src_len,
+ lz4_compressbound(src_len));
+ else
+ out_len = lz4_compressctx(wrkmem, src, dst, src_len,
+ lz4_compressbound(src_len));
+
+ if (out_len < 0)
+ goto exit;
+
+ *dst_len = out_len;
+
+ return 0;
+exit:
+ return ret;
+}
+EXPORT_SYMBOL_GPL(lz4_compress);
+
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("LZ4 compressor");
diff --git a/lib/lz4/lz4_decompress.c b/lib/lz4/lz4_decompress.c
new file mode 100644
index 000000000000..d3414eae73a1
--- /dev/null
+++ b/lib/lz4/lz4_decompress.c
@@ -0,0 +1,326 @@
+/*
+ * LZ4 Decompressor for Linux kernel
+ *
+ * Copyright (C) 2013, LG Electronics, Kyungsik Lee <kyungsik.lee@lge.com>
+ *
+ * Based on LZ4 implementation by Yann Collet.
+ *
+ * LZ4 - Fast LZ compression algorithm
+ * Copyright (C) 2011-2012, Yann Collet.
+ * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * You can contact the author at :
+ * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
+ * - LZ4 source repository : http://code.google.com/p/lz4/
+ */
+
+#ifndef STATIC
+#include <linux/module.h>
+#include <linux/kernel.h>
+#endif
+#include <linux/lz4.h>
+
+#include <asm/unaligned.h>
+
+#include "lz4defs.h"
+
+static int lz4_uncompress(const char *source, char *dest, int osize)
+{
+ const BYTE *ip = (const BYTE *) source;
+ const BYTE *ref;
+ BYTE *op = (BYTE *) dest;
+ BYTE * const oend = op + osize;
+ BYTE *cpy;
+ unsigned token;
+ size_t length;
+ size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
+#if LZ4_ARCH64
+ size_t dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
+#endif
+
+ while (1) {
+
+ /* get runlength */
+ token = *ip++;
+ length = (token >> ML_BITS);
+ if (length == RUN_MASK) {
+ size_t len;
+
+ len = *ip++;
+ for (; len == 255; length += 255)
+ len = *ip++;
+ length += len;
+ }
+
+ /* copy literals */
+ cpy = op + length;
+ if (unlikely(cpy > oend - COPYLENGTH)) {
+ /*
+ * Error: not enough place for another match
+ * (min 4) + 5 literals
+ */
+ if (cpy != oend)
+ goto _output_error;
+
+ memcpy(op, ip, length);
+ ip += length;
+ break; /* EOF */
+ }
+ LZ4_WILDCOPY(ip, op, cpy);
+ ip -= (op - cpy);
+ op = cpy;
+
+ /* get offset */
+ LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
+ ip += 2;
+
+ /* Error: offset create reference outside destination buffer */
+ if (unlikely(ref < (BYTE *const) dest))
+ goto _output_error;
+
+ /* get matchlength */
+ length = token & ML_MASK;
+ if (length == ML_MASK) {
+ for (; *ip == 255; length += 255)
+ ip++;
+ length += *ip++;
+ }
+
+ /* copy repeated sequence */
+ if (unlikely((op - ref) < STEPSIZE)) {
+#if LZ4_ARCH64
+ size_t dec64 = dec64table[op - ref];
+#else
+ const int dec64 = 0;
+#endif
+ op[0] = ref[0];
+ op[1] = ref[1];
+ op[2] = ref[2];
+ op[3] = ref[3];
+ op += 4;
+ ref += 4;
+ ref -= dec32table[op-ref];
+ PUT4(ref, op);
+ op += STEPSIZE - 4;
+ ref -= dec64;
+ } else {
+ LZ4_COPYSTEP(ref, op);
+ }
+ cpy = op + length - (STEPSIZE - 4);
+ if (cpy > (oend - COPYLENGTH)) {
+
+ /* Error: request to write beyond destination buffer */
+ if (cpy > oend)
+ goto _output_error;
+ LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
+ while (op < cpy)
+ *op++ = *ref++;
+ op = cpy;
+ /*
+ * Check EOF (should never happen, since last 5 bytes
+ * are supposed to be literals)
+ */
+ if (op == oend)
+ goto _output_error;
+ continue;
+ }
+ LZ4_SECURECOPY(ref, op, cpy);
+ op = cpy; /* correction */
+ }
+ /* end of decoding */
+ return (int) (((char *)ip) - source);
+
+ /* write overflow error detected */
+_output_error:
+ return (int) (-(((char *)ip) - source));
+}
+
+static int lz4_uncompress_unknownoutputsize(const char *source, char *dest,
+ int isize, size_t maxoutputsize)
+{
+ const BYTE *ip = (const BYTE *) source;
+ const BYTE *const iend = ip + isize;
+ const BYTE *ref;
+
+
+ BYTE *op = (BYTE *) dest;
+ BYTE * const oend = op + maxoutputsize;
+ BYTE *cpy;
+
+ size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
+#if LZ4_ARCH64
+ size_t dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
+#endif
+
+ /* Main Loop */
+ while (ip < iend) {
+
+ unsigned token;
+ size_t length;
+
+ /* get runlength */
+ token = *ip++;
+ length = (token >> ML_BITS);
+ if (length == RUN_MASK) {
+ int s = 255;
+ while ((ip < iend) && (s == 255)) {
+ s = *ip++;
+ length += s;
+ }
+ }
+ /* copy literals */
+ cpy = op + length;
+ if ((cpy > oend - COPYLENGTH) ||
+ (ip + length > iend - COPYLENGTH)) {
+
+ if (cpy > oend)
+ goto _output_error;/* writes beyond buffer */
+
+ if (ip + length != iend)
+ goto _output_error;/*
+ * Error: LZ4 format requires
+ * to consume all input
+ * at this stage
+ */
+ memcpy(op, ip, length);
+ op += length;
+ break;/* Necessarily EOF, due to parsing restrictions */
+ }
+ LZ4_WILDCOPY(ip, op, cpy);
+ ip -= (op - cpy);
+ op = cpy;
+
+ /* get offset */
+ LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
+ ip += 2;
+ if (ref < (BYTE * const) dest)
+ goto _output_error;
+ /*
+ * Error : offset creates reference
+ * outside of destination buffer
+ */
+
+ /* get matchlength */
+ length = (token & ML_MASK);
+ if (length == ML_MASK) {
+ while (ip < iend) {
+ int s = *ip++;
+ length += s;
+ if (s == 255)
+ continue;
+ break;
+ }
+ }
+
+ /* copy repeated sequence */
+ if (unlikely((op - ref) < STEPSIZE)) {
+#if LZ4_ARCH64
+ size_t dec64 = dec64table[op - ref];
+#else
+ const int dec64 = 0;
+#endif
+ op[0] = ref[0];
+ op[1] = ref[1];
+ op[2] = ref[2];
+ op[3] = ref[3];
+ op += 4;
+ ref += 4;
+ ref -= dec32table[op - ref];
+ PUT4(ref, op);
+ op += STEPSIZE - 4;
+ ref -= dec64;
+ } else {
+ LZ4_COPYSTEP(ref, op);
+ }
+ cpy = op + length - (STEPSIZE-4);
+ if (cpy > oend - COPYLENGTH) {
+ if (cpy > oend)
+ goto _output_error; /* write outside of buf */
+
+ LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
+ while (op < cpy)
+ *op++ = *ref++;
+ op = cpy;
+ /*
+ * Check EOF (should never happen, since last 5 bytes
+ * are supposed to be literals)
+ */
+ if (op == oend)
+ goto _output_error;
+ continue;
+ }
+ LZ4_SECURECOPY(ref, op, cpy);
+ op = cpy; /* correction */
+ }
+ /* end of decoding */
+ return (int) (((char *) op) - dest);
+
+ /* write overflow error detected */
+_output_error:
+ return (int) (-(((char *) ip) - source));
+}
+
+int lz4_decompress(const char *src, size_t *src_len, char *dest,
+ size_t actual_dest_len)
+{
+ int ret = -1;
+ int input_len = 0;
+
+ input_len = lz4_uncompress(src, dest, actual_dest_len);
+ if (input_len < 0)
+ goto exit_0;
+ *src_len = input_len;
+
+ return 0;
+exit_0:
+ return ret;
+}
+#ifndef STATIC
+EXPORT_SYMBOL_GPL(lz4_decompress);
+#endif
+
+int lz4_decompress_unknownoutputsize(const char *src, size_t src_len,
+ char *dest, size_t *dest_len)
+{
+ int ret = -1;
+ int out_len = 0;
+
+ out_len = lz4_uncompress_unknownoutputsize(src, dest, src_len,
+ *dest_len);
+ if (out_len < 0)
+ goto exit_0;
+ *dest_len = out_len;
+
+ return 0;
+exit_0:
+ return ret;
+}
+#ifndef STATIC
+EXPORT_SYMBOL_GPL(lz4_decompress_unknownoutputsize);
+
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("LZ4 Decompressor");
+#endif
diff --git a/lib/lz4/lz4defs.h b/lib/lz4/lz4defs.h
new file mode 100644
index 000000000000..abcecdc2d0f2
--- /dev/null
+++ b/lib/lz4/lz4defs.h
@@ -0,0 +1,156 @@
+/*
+ * lz4defs.h -- architecture specific defines
+ *
+ * Copyright (C) 2013, LG Electronics, Kyungsik Lee <kyungsik.lee@lge.com>
+ *
+ * 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.
+ */
+
+/*
+ * Detects 64 bits mode
+ */
+#if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) \
+ || defined(__ppc64__) || defined(__LP64__))
+#define LZ4_ARCH64 1
+#else
+#define LZ4_ARCH64 0
+#endif
+
+/*
+ * Architecture-specific macros
+ */
+#define BYTE u8
+typedef struct _U16_S { u16 v; } U16_S;
+typedef struct _U32_S { u32 v; } U32_S;
+typedef struct _U64_S { u64 v; } U64_S;
+#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) \
+ || defined(CONFIG_ARM) && __LINUX_ARM_ARCH__ >= 6 \
+ && defined(ARM_EFFICIENT_UNALIGNED_ACCESS)
+
+#define A16(x) (((U16_S *)(x))->v)
+#define A32(x) (((U32_S *)(x))->v)
+#define A64(x) (((U64_S *)(x))->v)
+
+#define PUT4(s, d) (A32(d) = A32(s))
+#define PUT8(s, d) (A64(d) = A64(s))
+#define LZ4_WRITE_LITTLEENDIAN_16(p, v) \
+ do { \
+ A16(p) = v; \
+ p += 2; \
+ } while (0)
+#else /* CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */
+
+#define A64(x) get_unaligned((u64 *)&(((U16_S *)(x))->v))
+#define A32(x) get_unaligned((u32 *)&(((U16_S *)(x))->v))
+#define A16(x) get_unaligned((u16 *)&(((U16_S *)(x))->v))
+
+#define PUT4(s, d) \
+ put_unaligned(get_unaligned((const u32 *) s), (u32 *) d)
+#define PUT8(s, d) \
+ put_unaligned(get_unaligned((const u64 *) s), (u64 *) d)
+
+#define LZ4_WRITE_LITTLEENDIAN_16(p, v) \
+ do { \
+ put_unaligned(v, (u16 *)(p)); \
+ p += 2; \
+ } while (0)
+#endif
+
+#define COPYLENGTH 8
+#define ML_BITS 4
+#define ML_MASK ((1U << ML_BITS) - 1)
+#define RUN_BITS (8 - ML_BITS)
+#define RUN_MASK ((1U << RUN_BITS) - 1)
+#define MEMORY_USAGE 14
+#define MINMATCH 4
+#define SKIPSTRENGTH 6
+#define LASTLITERALS 5
+#define MFLIMIT (COPYLENGTH + MINMATCH)
+#define MINLENGTH (MFLIMIT + 1)
+#define MAXD_LOG 16
+#define MAXD (1 << MAXD_LOG)
+#define MAXD_MASK (u32)(MAXD - 1)
+#define MAX_DISTANCE (MAXD - 1)
+#define HASH_LOG (MAXD_LOG - 1)
+#define HASHTABLESIZE (1 << HASH_LOG)
+#define MAX_NB_ATTEMPTS 256
+#define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH)
+#define LZ4_64KLIMIT ((1<<16) + (MFLIMIT - 1))
+#define HASHLOG64K ((MEMORY_USAGE - 2) + 1)
+#define HASH64KTABLESIZE (1U << HASHLOG64K)
+#define LZ4_HASH_VALUE(p) (((A32(p)) * 2654435761U) >> \
+ ((MINMATCH * 8) - (MEMORY_USAGE-2)))
+#define LZ4_HASH64K_VALUE(p) (((A32(p)) * 2654435761U) >> \
+ ((MINMATCH * 8) - HASHLOG64K))
+#define HASH_VALUE(p) (((A32(p)) * 2654435761U) >> \
+ ((MINMATCH * 8) - HASH_LOG))
+
+#if LZ4_ARCH64/* 64-bit */
+#define STEPSIZE 8
+
+#define LZ4_COPYSTEP(s, d) \
+ do { \
+ PUT8(s, d); \
+ d += 8; \
+ s += 8; \
+ } while (0)
+
+#define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d)
+
+#define LZ4_SECURECOPY(s, d, e) \
+ do { \
+ if (d < e) { \
+ LZ4_WILDCOPY(s, d, e); \
+ } \
+ } while (0)
+#define HTYPE u32
+
+#ifdef __BIG_ENDIAN
+#define LZ4_NBCOMMONBYTES(val) (__builtin_clzll(val) >> 3)
+#else
+#define LZ4_NBCOMMONBYTES(val) (__builtin_ctzll(val) >> 3)
+#endif
+
+#else /* 32-bit */
+#define STEPSIZE 4
+
+#define LZ4_COPYSTEP(s, d) \
+ do { \
+ PUT4(s, d); \
+ d += 4; \
+ s += 4; \
+ } while (0)
+
+#define LZ4_COPYPACKET(s, d) \
+ do { \
+ LZ4_COPYSTEP(s, d); \
+ LZ4_COPYSTEP(s, d); \
+ } while (0)
+
+#define LZ4_SECURECOPY LZ4_WILDCOPY
+#define HTYPE const u8*
+
+#ifdef __BIG_ENDIAN
+#define LZ4_NBCOMMONBYTES(val) (__builtin_clz(val) >> 3)
+#else
+#define LZ4_NBCOMMONBYTES(val) (__builtin_ctz(val) >> 3)
+#endif
+
+#endif
+
+#define LZ4_READ_LITTLEENDIAN_16(d, s, p) \
+ (d = s - get_unaligned_le16(p))
+
+#define LZ4_WILDCOPY(s, d, e) \
+ do { \
+ LZ4_COPYPACKET(s, d); \
+ } while (d < e)
+
+#define LZ4_BLINDCOPY(s, d, l) \
+ do { \
+ u8 *e = (d) + l; \
+ LZ4_WILDCOPY(s, d, e); \
+ d = e; \
+ } while (0)
diff --git a/lib/lz4/lz4hc_compress.c b/lib/lz4/lz4hc_compress.c
new file mode 100644
index 000000000000..eb1a74f5e368
--- /dev/null
+++ b/lib/lz4/lz4hc_compress.c
@@ -0,0 +1,539 @@
+/*
+ * LZ4 HC - High Compression Mode of LZ4
+ * Copyright (C) 2011-2012, Yann Collet.
+ * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * You can contact the author at :
+ * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
+ * - LZ4 source repository : http://code.google.com/p/lz4/
+ *
+ * Changed for kernel use by:
+ * Chanho Min <chanho.min@lge.com>
+ */
+
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include <linux/lz4.h>
+#include <asm/unaligned.h>
+#include "lz4defs.h"
+
+struct lz4hc_data {
+ const u8 *base;
+ HTYPE hashtable[HASHTABLESIZE];
+ u16 chaintable[MAXD];
+ const u8 *nexttoupdate;
+} __attribute__((__packed__));
+
+static inline int lz4hc_init(struct lz4hc_data *hc4, const u8 *base)
+{
+ memset((void *)hc4->hashtable, 0, sizeof(hc4->hashtable));
+ memset(hc4->chaintable, 0xFF, sizeof(hc4->chaintable));
+
+#if LZ4_ARCH64
+ hc4->nexttoupdate = base + 1;
+#else
+ hc4->nexttoupdate = base;
+#endif
+ hc4->base = base;
+ return 1;
+}
+
+/* Update chains up to ip (excluded) */
+static inline void lz4hc_insert(struct lz4hc_data *hc4, const u8 *ip)
+{
+ u16 *chaintable = hc4->chaintable;
+ HTYPE *hashtable = hc4->hashtable;
+#if LZ4_ARCH64
+ const BYTE * const base = hc4->base;
+#else
+ const int base = 0;
+#endif
+
+ while (hc4->nexttoupdate < ip) {
+ const u8 *p = hc4->nexttoupdate;
+ size_t delta = p - (hashtable[HASH_VALUE(p)] + base);
+ if (delta > MAX_DISTANCE)
+ delta = MAX_DISTANCE;
+ chaintable[(size_t)(p) & MAXD_MASK] = (u16)delta;
+ hashtable[HASH_VALUE(p)] = (p) - base;
+ hc4->nexttoupdate++;
+ }
+}
+
+static inline size_t lz4hc_commonlength(const u8 *p1, const u8 *p2,
+ const u8 *const matchlimit)
+{
+ const u8 *p1t = p1;
+
+ while (p1t < matchlimit - (STEPSIZE - 1)) {
+#if LZ4_ARCH64
+ u64 diff = A64(p2) ^ A64(p1t);
+#else
+ u32 diff = A32(p2) ^ A32(p1t);
+#endif
+ if (!diff) {
+ p1t += STEPSIZE;
+ p2 += STEPSIZE;
+ continue;
+ }
+ p1t += LZ4_NBCOMMONBYTES(diff);
+ return p1t - p1;
+ }
+#if LZ4_ARCH64
+ if ((p1t < (matchlimit-3)) && (A32(p2) == A32(p1t))) {
+ p1t += 4;
+ p2 += 4;
+ }
+#endif
+
+ if ((p1t < (matchlimit - 1)) && (A16(p2) == A16(p1t))) {
+ p1t += 2;
+ p2 += 2;
+ }
+ if ((p1t < matchlimit) && (*p2 == *p1t))
+ p1t++;
+ return p1t - p1;
+}
+
+static inline int lz4hc_insertandfindbestmatch(struct lz4hc_data *hc4,
+ const u8 *ip, const u8 *const matchlimit, const u8 **matchpos)
+{
+ u16 *const chaintable = hc4->chaintable;
+ HTYPE *const hashtable = hc4->hashtable;
+ const u8 *ref;
+#if LZ4_ARCH64
+ const BYTE * const base = hc4->base;
+#else
+ const int base = 0;
+#endif
+ int nbattempts = MAX_NB_ATTEMPTS;
+ size_t repl = 0, ml = 0;
+ u16 delta;
+
+ /* HC4 match finder */
+ lz4hc_insert(hc4, ip);
+ ref = hashtable[HASH_VALUE(ip)] + base;
+
+ /* potential repetition */
+ if (ref >= ip-4) {
+ /* confirmed */
+ if (A32(ref) == A32(ip)) {
+ delta = (u16)(ip-ref);
+ repl = ml = lz4hc_commonlength(ip + MINMATCH,
+ ref + MINMATCH, matchlimit) + MINMATCH;
+ *matchpos = ref;
+ }
+ ref -= (size_t)chaintable[(size_t)(ref) & MAXD_MASK];
+ }
+
+ while ((ref >= ip - MAX_DISTANCE) && nbattempts) {
+ nbattempts--;
+ if (*(ref + ml) == *(ip + ml)) {
+ if (A32(ref) == A32(ip)) {
+ size_t mlt =
+ lz4hc_commonlength(ip + MINMATCH,
+ ref + MINMATCH, matchlimit) + MINMATCH;
+ if (mlt > ml) {
+ ml = mlt;
+ *matchpos = ref;
+ }
+ }
+ }
+ ref -= (size_t)chaintable[(size_t)(ref) & MAXD_MASK];
+ }
+
+ /* Complete table */
+ if (repl) {
+ const BYTE *ptr = ip;
+ const BYTE *end;
+ end = ip + repl - (MINMATCH-1);
+ /* Pre-Load */
+ while (ptr < end - delta) {
+ chaintable[(size_t)(ptr) & MAXD_MASK] = delta;
+ ptr++;
+ }
+ do {
+ chaintable[(size_t)(ptr) & MAXD_MASK] = delta;
+ /* Head of chain */
+ hashtable[HASH_VALUE(ptr)] = (ptr) - base;
+ ptr++;
+ } while (ptr < end);
+ hc4->nexttoupdate = end;
+ }
+
+ return (int)ml;
+}
+
+static inline int lz4hc_insertandgetwidermatch(struct lz4hc_data *hc4,
+ const u8 *ip, const u8 *startlimit, const u8 *matchlimit, int longest,
+ const u8 **matchpos, const u8 **startpos)
+{
+ u16 *const chaintable = hc4->chaintable;
+ HTYPE *const hashtable = hc4->hashtable;
+#if LZ4_ARCH64
+ const BYTE * const base = hc4->base;
+#else
+ const int base = 0;
+#endif
+ const u8 *ref;
+ int nbattempts = MAX_NB_ATTEMPTS;
+ int delta = (int)(ip - startlimit);
+
+ /* First Match */
+ lz4hc_insert(hc4, ip);
+ ref = hashtable[HASH_VALUE(ip)] + base;
+
+ while ((ref >= ip - MAX_DISTANCE) && (ref >= hc4->base)
+ && (nbattempts)) {
+ nbattempts--;
+ if (*(startlimit + longest) == *(ref - delta + longest)) {
+ if (A32(ref) == A32(ip)) {
+ const u8 *reft = ref + MINMATCH;
+ const u8 *ipt = ip + MINMATCH;
+ const u8 *startt = ip;
+
+ while (ipt < matchlimit-(STEPSIZE - 1)) {
+ #if LZ4_ARCH64
+ u64 diff = A64(reft) ^ A64(ipt);
+ #else
+ u32 diff = A32(reft) ^ A32(ipt);
+ #endif
+
+ if (!diff) {
+ ipt += STEPSIZE;
+ reft += STEPSIZE;
+ continue;
+ }
+ ipt += LZ4_NBCOMMONBYTES(diff);
+ goto _endcount;
+ }
+ #if LZ4_ARCH64
+ if ((ipt < (matchlimit - 3))
+ && (A32(reft) == A32(ipt))) {
+ ipt += 4;
+ reft += 4;
+ }
+ ipt += 2;
+ #endif
+ if ((ipt < (matchlimit - 1))
+ && (A16(reft) == A16(ipt))) {
+ reft += 2;
+ }
+ if ((ipt < matchlimit) && (*reft == *ipt))
+ ipt++;
+_endcount:
+ reft = ref;
+
+ while ((startt > startlimit)
+ && (reft > hc4->base)
+ && (startt[-1] == reft[-1])) {
+ startt--;
+ reft--;
+ }
+
+ if ((ipt - startt) > longest) {
+ longest = (int)(ipt - startt);
+ *matchpos = reft;
+ *startpos = startt;
+ }
+ }
+ }
+ ref -= (size_t)chaintable[(size_t)(ref) & MAXD_MASK];
+ }
+ return longest;
+}
+
+static inline int lz4_encodesequence(const u8 **ip, u8 **op, const u8 **anchor,
+ int ml, const u8 *ref)
+{
+ int length, len;
+ u8 *token;
+
+ /* Encode Literal length */
+ length = (int)(*ip - *anchor);
+ token = (*op)++;
+ if (length >= (int)RUN_MASK) {
+ *token = (RUN_MASK << ML_BITS);
+ len = length - RUN_MASK;
+ for (; len > 254 ; len -= 255)
+ *(*op)++ = 255;
+ *(*op)++ = (u8)len;
+ } else
+ *token = (length << ML_BITS);
+
+ /* Copy Literals */
+ LZ4_BLINDCOPY(*anchor, *op, length);
+
+ /* Encode Offset */
+ LZ4_WRITE_LITTLEENDIAN_16(*op, (u16)(*ip - ref));
+
+ /* Encode MatchLength */
+ len = (int)(ml - MINMATCH);
+ if (len >= (int)ML_MASK) {
+ *token += ML_MASK;
+ len -= ML_MASK;
+ for (; len > 509 ; len -= 510) {
+ *(*op)++ = 255;
+ *(*op)++ = 255;
+ }
+ if (len > 254) {
+ len -= 255;
+ *(*op)++ = 255;
+ }
+ *(*op)++ = (u8)len;
+ } else
+ *token += len;
+
+ /* Prepare next loop */
+ *ip += ml;
+ *anchor = *ip;
+
+ return 0;
+}
+
+static int lz4_compresshcctx(struct lz4hc_data *ctx,
+ const char *source,
+ char *dest,
+ int isize)
+{
+ const u8 *ip = (const u8 *)source;
+ const u8 *anchor = ip;
+ const u8 *const iend = ip + isize;
+ const u8 *const mflimit = iend - MFLIMIT;
+ const u8 *const matchlimit = (iend - LASTLITERALS);
+
+ u8 *op = (u8 *)dest;
+
+ int ml, ml2, ml3, ml0;
+ const u8 *ref = NULL;
+ const u8 *start2 = NULL;
+ const u8 *ref2 = NULL;
+ const u8 *start3 = NULL;
+ const u8 *ref3 = NULL;
+ const u8 *start0;
+ const u8 *ref0;
+ int lastrun;
+
+ ip++;
+
+ /* Main Loop */
+ while (ip < mflimit) {
+ ml = lz4hc_insertandfindbestmatch(ctx, ip, matchlimit, (&ref));
+ if (!ml) {
+ ip++;
+ continue;
+ }
+
+ /* saved, in case we would skip too much */
+ start0 = ip;
+ ref0 = ref;
+ ml0 = ml;
+_search2:
+ if (ip+ml < mflimit)
+ ml2 = lz4hc_insertandgetwidermatch(ctx, ip + ml - 2,
+ ip + 1, matchlimit, ml, &ref2, &start2);
+ else
+ ml2 = ml;
+ /* No better match */
+ if (ml2 == ml) {
+ lz4_encodesequence(&ip, &op, &anchor, ml, ref);
+ continue;
+ }
+
+ if (start0 < ip) {
+ /* empirical */
+ if (start2 < ip + ml0) {
+ ip = start0;
+ ref = ref0;
+ ml = ml0;
+ }
+ }
+ /*
+ * Here, start0==ip
+ * First Match too small : removed
+ */
+ if ((start2 - ip) < 3) {
+ ml = ml2;
+ ip = start2;
+ ref = ref2;
+ goto _search2;
+ }
+
+_search3:
+ /*
+ * Currently we have :
+ * ml2 > ml1, and
+ * ip1+3 <= ip2 (usually < ip1+ml1)
+ */
+ if ((start2 - ip) < OPTIMAL_ML) {
+ int correction;
+ int new_ml = ml;
+ if (new_ml > OPTIMAL_ML)
+ new_ml = OPTIMAL_ML;
+ if (ip + new_ml > start2 + ml2 - MINMATCH)
+ new_ml = (int)(start2 - ip) + ml2 - MINMATCH;
+ correction = new_ml - (int)(start2 - ip);
+ if (correction > 0) {
+ start2 += correction;
+ ref2 += correction;
+ ml2 -= correction;
+ }
+ }
+ /*
+ * Now, we have start2 = ip+new_ml,
+ * with new_ml=min(ml, OPTIMAL_ML=18)
+ */
+ if (start2 + ml2 < mflimit)
+ ml3 = lz4hc_insertandgetwidermatch(ctx,
+ start2 + ml2 - 3, start2, matchlimit,
+ ml2, &ref3, &start3);
+ else
+ ml3 = ml2;
+
+ /* No better match : 2 sequences to encode */
+ if (ml3 == ml2) {
+ /* ip & ref are known; Now for ml */
+ if (start2 < ip+ml)
+ ml = (int)(start2 - ip);
+
+ /* Now, encode 2 sequences */
+ lz4_encodesequence(&ip, &op, &anchor, ml, ref);
+ ip = start2;
+ lz4_encodesequence(&ip, &op, &anchor, ml2, ref2);
+ continue;
+ }
+
+ /* Not enough space for match 2 : remove it */
+ if (start3 < ip + ml + 3) {
+ /*
+ * can write Seq1 immediately ==> Seq2 is removed,
+ * so Seq3 becomes Seq1
+ */
+ if (start3 >= (ip + ml)) {
+ if (start2 < ip + ml) {
+ int correction =
+ (int)(ip + ml - start2);
+ start2 += correction;
+ ref2 += correction;
+ ml2 -= correction;
+ if (ml2 < MINMATCH) {
+ start2 = start3;
+ ref2 = ref3;
+ ml2 = ml3;
+ }
+ }
+
+ lz4_encodesequence(&ip, &op, &anchor, ml, ref);
+ ip = start3;
+ ref = ref3;
+ ml = ml3;
+
+ start0 = start2;
+ ref0 = ref2;
+ ml0 = ml2;
+ goto _search2;
+ }
+
+ start2 = start3;
+ ref2 = ref3;
+ ml2 = ml3;
+ goto _search3;
+ }
+
+ /*
+ * OK, now we have 3 ascending matches; let's write at least
+ * the first one ip & ref are known; Now for ml
+ */
+ if (start2 < ip + ml) {
+ if ((start2 - ip) < (int)ML_MASK) {
+ int correction;
+ if (ml > OPTIMAL_ML)
+ ml = OPTIMAL_ML;
+ if (ip + ml > start2 + ml2 - MINMATCH)
+ ml = (int)(start2 - ip) + ml2
+ - MINMATCH;
+ correction = ml - (int)(start2 - ip);
+ if (correction > 0) {
+ start2 += correction;
+ ref2 += correction;
+ ml2 -= correction;
+ }
+ } else
+ ml = (int)(start2 - ip);
+ }
+ lz4_encodesequence(&ip, &op, &anchor, ml, ref);
+
+ ip = start2;
+ ref = ref2;
+ ml = ml2;
+
+ start2 = start3;
+ ref2 = ref3;
+ ml2 = ml3;
+
+ goto _search3;
+ }
+
+ /* Encode Last Literals */
+ lastrun = (int)(iend - anchor);
+ if (lastrun >= (int)RUN_MASK) {
+ *op++ = (RUN_MASK << ML_BITS);
+ lastrun -= RUN_MASK;
+ for (; lastrun > 254 ; lastrun -= 255)
+ *op++ = 255;
+ *op++ = (u8) lastrun;
+ } else
+ *op++ = (lastrun << ML_BITS);
+ memcpy(op, anchor, iend - anchor);
+ op += iend - anchor;
+ /* End */
+ return (int) (((char *)op) - dest);
+}
+
+int lz4hc_compress(const unsigned char *src, size_t src_len,
+ unsigned char *dst, size_t *dst_len, void *wrkmem)
+{
+ int ret = -1;
+ int out_len = 0;
+
+ struct lz4hc_data *hc4 = (struct lz4hc_data *)wrkmem;
+ lz4hc_init(hc4, (const u8 *)src);
+ out_len = lz4_compresshcctx((struct lz4hc_data *)hc4, (const u8 *)src,
+ (char *)dst, (int)src_len);
+
+ if (out_len < 0)
+ goto exit;
+
+ *dst_len = out_len;
+ return 0;
+
+exit:
+ return ret;
+}
+EXPORT_SYMBOL_GPL(lz4hc_compress);
+
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("LZ4HC compressor");
diff --git a/lib/mpi/longlong.h b/lib/mpi/longlong.h
index d411355f238e..aac511417ad1 100644
--- a/lib/mpi/longlong.h
+++ b/lib/mpi/longlong.h
@@ -151,15 +151,12 @@ do { \
#endif /* __a29k__ */
#if defined(__alpha) && W_TYPE_SIZE == 64
-#define umul_ppmm(ph, pl, m0, m1) \
-do { \
- UDItype __m0 = (m0), __m1 = (m1); \
- __asm__ ("umulh %r1,%2,%0" \
- : "=r" ((UDItype) ph) \
- : "%rJ" (__m0), \
- "rI" (__m1)); \
- (pl) = __m0 * __m1; \
- } while (0)
+#define umul_ppmm(ph, pl, m0, m1) \
+do { \
+ UDItype __m0 = (m0), __m1 = (m1); \
+ (ph) = __builtin_alpha_umulh(__m0, __m1); \
+ (pl) = __m0 * __m1; \
+} while (0)
#define UMUL_TIME 46
#ifndef LONGLONG_STANDALONE
#define udiv_qrnnd(q, r, n1, n0, d) \
@@ -167,7 +164,7 @@ do { UDItype __r; \
(q) = __udiv_qrnnd(&__r, (n1), (n0), (d)); \
(r) = __r; \
} while (0)
-extern UDItype __udiv_qrnnd();
+extern UDItype __udiv_qrnnd(UDItype *, UDItype, UDItype, UDItype);
#define UDIV_TIME 220
#endif /* LONGLONG_STANDALONE */
#endif /* __alpha */
diff --git a/lib/percpu_counter.c b/lib/percpu_counter.c
index 1fc23a3277e1..93c5d5ecff4e 100644
--- a/lib/percpu_counter.c
+++ b/lib/percpu_counter.c
@@ -158,7 +158,7 @@ static void compute_batch_value(void)
percpu_counter_batch = max(32, nr*2);
}
-static int __cpuinit percpu_counter_hotcpu_callback(struct notifier_block *nb,
+static int percpu_counter_hotcpu_callback(struct notifier_block *nb,
unsigned long action, void *hcpu)
{
#ifdef CONFIG_HOTPLUG_CPU
diff --git a/lib/scatterlist.c b/lib/scatterlist.c
index a1cf8cae60e7..a685c8a79578 100644
--- a/lib/scatterlist.c
+++ b/lib/scatterlist.c
@@ -247,13 +247,15 @@ int __sg_alloc_table(struct sg_table *table, unsigned int nents,
struct scatterlist *sg, *prv;
unsigned int left;
+ memset(table, 0, sizeof(*table));
+
+ if (nents == 0)
+ return -EINVAL;
#ifndef ARCH_HAS_SG_CHAIN
if (WARN_ON_ONCE(nents > max_ents))
return -EINVAL;
#endif
- memset(table, 0, sizeof(*table));
-
left = nents;
prv = NULL;
do {
@@ -453,6 +455,65 @@ void sg_miter_start(struct sg_mapping_iter *miter, struct scatterlist *sgl,
}
EXPORT_SYMBOL(sg_miter_start);
+static bool sg_miter_get_next_page(struct sg_mapping_iter *miter)
+{
+ if (!miter->__remaining) {
+ struct scatterlist *sg;
+ unsigned long pgoffset;
+
+ if (!__sg_page_iter_next(&miter->piter))
+ return false;
+
+ sg = miter->piter.sg;
+ pgoffset = miter->piter.sg_pgoffset;
+
+ miter->__offset = pgoffset ? 0 : sg->offset;
+ miter->__remaining = sg->offset + sg->length -
+ (pgoffset << PAGE_SHIFT) - miter->__offset;
+ miter->__remaining = min_t(unsigned long, miter->__remaining,
+ PAGE_SIZE - miter->__offset);
+ }
+
+ return true;
+}
+
+/**
+ * sg_miter_skip - reposition mapping iterator
+ * @miter: sg mapping iter to be skipped
+ * @offset: number of bytes to plus the current location
+ *
+ * Description:
+ * Sets the offset of @miter to its current location plus @offset bytes.
+ * If mapping iterator @miter has been proceeded by sg_miter_next(), this
+ * stops @miter.
+ *
+ * Context:
+ * Don't care if @miter is stopped, or not proceeded yet.
+ * Otherwise, preemption disabled if the SG_MITER_ATOMIC is set.
+ *
+ * Returns:
+ * true if @miter contains the valid mapping. false if end of sg
+ * list is reached.
+ */
+static bool sg_miter_skip(struct sg_mapping_iter *miter, off_t offset)
+{
+ sg_miter_stop(miter);
+
+ while (offset) {
+ off_t consumed;
+
+ if (!sg_miter_get_next_page(miter))
+ return false;
+
+ consumed = min_t(off_t, offset, miter->__remaining);
+ miter->__offset += consumed;
+ miter->__remaining -= consumed;
+ offset -= consumed;
+ }
+
+ return true;
+}
+
/**
* sg_miter_next - proceed mapping iterator to the next mapping
* @miter: sg mapping iter to proceed
@@ -478,22 +539,9 @@ bool sg_miter_next(struct sg_mapping_iter *miter)
* Get to the next page if necessary.
* __remaining, __offset is adjusted by sg_miter_stop
*/
- if (!miter->__remaining) {
- struct scatterlist *sg;
- unsigned long pgoffset;
-
- if (!__sg_page_iter_next(&miter->piter))
- return false;
-
- sg = miter->piter.sg;
- pgoffset = miter->piter.sg_pgoffset;
+ if (!sg_miter_get_next_page(miter))
+ return false;
- miter->__offset = pgoffset ? 0 : sg->offset;
- miter->__remaining = sg->offset + sg->length -
- (pgoffset << PAGE_SHIFT) - miter->__offset;
- miter->__remaining = min_t(unsigned long, miter->__remaining,
- PAGE_SIZE - miter->__offset);
- }
miter->page = sg_page_iter_page(&miter->piter);
miter->consumed = miter->length = miter->__remaining;
@@ -552,14 +600,16 @@ EXPORT_SYMBOL(sg_miter_stop);
* @nents: Number of SG entries
* @buf: Where to copy from
* @buflen: The number of bytes to copy
- * @to_buffer: transfer direction (non zero == from an sg list to a
- * buffer, 0 == from a buffer to an sg list
+ * @skip: Number of bytes to skip before copying
+ * @to_buffer: transfer direction (true == from an sg list to a
+ * buffer, false == from a buffer to an sg list
*
* Returns the number of copied bytes.
*
**/
static size_t sg_copy_buffer(struct scatterlist *sgl, unsigned int nents,
- void *buf, size_t buflen, int to_buffer)
+ void *buf, size_t buflen, off_t skip,
+ bool to_buffer)
{
unsigned int offset = 0;
struct sg_mapping_iter miter;
@@ -573,6 +623,9 @@ static size_t sg_copy_buffer(struct scatterlist *sgl, unsigned int nents,
sg_miter_start(&miter, sgl, nents, sg_flags);
+ if (!sg_miter_skip(&miter, skip))
+ return false;
+
local_irq_save(flags);
while (sg_miter_next(&miter) && offset < buflen) {
@@ -607,7 +660,7 @@ static size_t sg_copy_buffer(struct scatterlist *sgl, unsigned int nents,
size_t sg_copy_from_buffer(struct scatterlist *sgl, unsigned int nents,
void *buf, size_t buflen)
{
- return sg_copy_buffer(sgl, nents, buf, buflen, 0);
+ return sg_copy_buffer(sgl, nents, buf, buflen, 0, false);
}
EXPORT_SYMBOL(sg_copy_from_buffer);
@@ -624,6 +677,42 @@ EXPORT_SYMBOL(sg_copy_from_buffer);
size_t sg_copy_to_buffer(struct scatterlist *sgl, unsigned int nents,
void *buf, size_t buflen)
{
- return sg_copy_buffer(sgl, nents, buf, buflen, 1);
+ return sg_copy_buffer(sgl, nents, buf, buflen, 0, true);
}
EXPORT_SYMBOL(sg_copy_to_buffer);
+
+/**
+ * sg_pcopy_from_buffer - Copy from a linear buffer to an SG list
+ * @sgl: The SG list
+ * @nents: Number of SG entries
+ * @buf: Where to copy from
+ * @skip: Number of bytes to skip before copying
+ * @buflen: The number of bytes to copy
+ *
+ * Returns the number of copied bytes.
+ *
+ **/
+size_t sg_pcopy_from_buffer(struct scatterlist *sgl, unsigned int nents,
+ void *buf, size_t buflen, off_t skip)
+{
+ return sg_copy_buffer(sgl, nents, buf, buflen, skip, false);
+}
+EXPORT_SYMBOL(sg_pcopy_from_buffer);
+
+/**
+ * sg_pcopy_to_buffer - Copy from an SG list to a linear buffer
+ * @sgl: The SG list
+ * @nents: Number of SG entries
+ * @buf: Where to copy to
+ * @skip: Number of bytes to skip before copying
+ * @buflen: The number of bytes to copy
+ *
+ * Returns the number of copied bytes.
+ *
+ **/
+size_t sg_pcopy_to_buffer(struct scatterlist *sgl, unsigned int nents,
+ void *buf, size_t buflen, off_t skip)
+{
+ return sg_copy_buffer(sgl, nents, buf, buflen, skip, true);
+}
+EXPORT_SYMBOL(sg_pcopy_to_buffer);
diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 7d8467645d2e..739a36366b79 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -923,6 +923,103 @@ char *ip4_addr_string(char *buf, char *end, const u8 *addr,
}
static noinline_for_stack
+char *ip6_addr_string_sa(char *buf, char *end, const struct sockaddr_in6 *sa,
+ struct printf_spec spec, const char *fmt)
+{
+ bool have_p = false, have_s = false, have_f = false, have_c = false;
+ char ip6_addr[sizeof("[xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:255.255.255.255]") +
+ sizeof(":12345") + sizeof("/123456789") +
+ sizeof("%1234567890")];
+ char *p = ip6_addr, *pend = ip6_addr + sizeof(ip6_addr);
+ const u8 *addr = (const u8 *) &sa->sin6_addr;
+ char fmt6[2] = { fmt[0], '6' };
+ u8 off = 0;
+
+ fmt++;
+ while (isalpha(*++fmt)) {
+ switch (*fmt) {
+ case 'p':
+ have_p = true;
+ break;
+ case 'f':
+ have_f = true;
+ break;
+ case 's':
+ have_s = true;
+ break;
+ case 'c':
+ have_c = true;
+ break;
+ }
+ }
+
+ if (have_p || have_s || have_f) {
+ *p = '[';
+ off = 1;
+ }
+
+ if (fmt6[0] == 'I' && have_c)
+ p = ip6_compressed_string(ip6_addr + off, addr);
+ else
+ p = ip6_string(ip6_addr + off, addr, fmt6);
+
+ if (have_p || have_s || have_f)
+ *p++ = ']';
+
+ if (have_p) {
+ *p++ = ':';
+ p = number(p, pend, ntohs(sa->sin6_port), spec);
+ }
+ if (have_f) {
+ *p++ = '/';
+ p = number(p, pend, ntohl(sa->sin6_flowinfo &
+ IPV6_FLOWINFO_MASK), spec);
+ }
+ if (have_s) {
+ *p++ = '%';
+ p = number(p, pend, sa->sin6_scope_id, spec);
+ }
+ *p = '\0';
+
+ return string(buf, end, ip6_addr, spec);
+}
+
+static noinline_for_stack
+char *ip4_addr_string_sa(char *buf, char *end, const struct sockaddr_in *sa,
+ struct printf_spec spec, const char *fmt)
+{
+ bool have_p = false;
+ char *p, ip4_addr[sizeof("255.255.255.255") + sizeof(":12345")];
+ char *pend = ip4_addr + sizeof(ip4_addr);
+ const u8 *addr = (const u8 *) &sa->sin_addr.s_addr;
+ char fmt4[3] = { fmt[0], '4', 0 };
+
+ fmt++;
+ while (isalpha(*++fmt)) {
+ switch (*fmt) {
+ case 'p':
+ have_p = true;
+ break;
+ case 'h':
+ case 'l':
+ case 'n':
+ case 'b':
+ fmt4[2] = *fmt;
+ break;
+ }
+ }
+
+ p = ip4_string(ip4_addr, addr, fmt4);
+ if (have_p) {
+ *p++ = ':';
+ p = number(p, pend, ntohs(sa->sin_port), spec);
+ }
+ *p = '\0';
+
+ return string(buf, end, ip4_addr, spec);
+}
+
+static noinline_for_stack
char *uuid_string(char *buf, char *end, const u8 *addr,
struct printf_spec spec, const char *fmt)
{
@@ -1007,11 +1104,17 @@ int kptr_restrict __read_mostly;
* - 'I' [46] for IPv4/IPv6 addresses printed in the usual way
* IPv4 uses dot-separated decimal without leading 0's (1.2.3.4)
* IPv6 uses colon separated network-order 16 bit hex with leading 0's
+ * [S][pfs]
+ * Generic IPv4/IPv6 address (struct sockaddr *) that falls back to
+ * [4] or [6] and is able to print port [p], flowinfo [f], scope [s]
* - 'i' [46] for 'raw' IPv4/IPv6 addresses
* IPv6 omits the colons (01020304...0f)
* IPv4 uses dot-separated decimal with leading 0's (010.123.045.006)
- * - '[Ii]4[hnbl]' IPv4 addresses in host, network, big or little endian order
- * - 'I6c' for IPv6 addresses printed as specified by
+ * [S][pfs]
+ * Generic IPv4/IPv6 address (struct sockaddr *) that falls back to
+ * [4] or [6] and is able to print port [p], flowinfo [f], scope [s]
+ * - '[Ii][4S][hnbl]' IPv4 addresses in host, network, big or little endian order
+ * - 'I[6S]c' for IPv6 addresses printed as specified by
* http://tools.ietf.org/html/rfc5952
* - 'U' For a 16 byte UUID/GUID, it prints the UUID/GUID in the form
* "xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx"
@@ -1093,6 +1196,21 @@ char *pointer(const char *fmt, char *buf, char *end, void *ptr,
return ip6_addr_string(buf, end, ptr, spec, fmt);
case '4':
return ip4_addr_string(buf, end, ptr, spec, fmt);
+ case 'S': {
+ const union {
+ struct sockaddr raw;
+ struct sockaddr_in v4;
+ struct sockaddr_in6 v6;
+ } *sa = ptr;
+
+ switch (sa->raw.sa_family) {
+ case AF_INET:
+ return ip4_addr_string_sa(buf, end, &sa->v4, spec, fmt);
+ case AF_INET6:
+ return ip6_addr_string_sa(buf, end, &sa->v6, spec, fmt);
+ default:
+ return string(buf, end, "(invalid address)", spec);
+ }}
}
break;
case 'U':
@@ -1370,6 +1488,8 @@ qualifier:
* %pI6 print an IPv6 address with colons
* %pi6 print an IPv6 address without colons
* %pI6c print an IPv6 address as specified by RFC 5952
+ * %pIS depending on sa_family of 'struct sockaddr *' print IPv4/IPv6 address
+ * %piS depending on sa_family of 'struct sockaddr *' print IPv4/IPv6 address
* %pU[bBlL] print a UUID/GUID in big or little endian using lower or upper
* case.
* %*ph[CDN] a variable-length hex string with a separator (supports up to 64
generated by cgit v1.2.3 (git 2.39.0) at 2024-11-24 09:06:24 +0300