diff options
Diffstat (limited to 'lib')
72 files changed, 1511 insertions, 789 deletions
diff --git a/lib/Kconfig b/lib/Kconfig index 028aba9e72a..4a8aba2e5cc 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -29,6 +29,10 @@ config GENERIC_IOMAP bool select GENERIC_PCI_IOMAP +config GENERIC_IO + boolean + default n + config CRC_CCITT tristate "CRC-CCITT functions" help @@ -61,14 +65,71 @@ config CRC_ITU_T functions require M here. config CRC32 - tristate "CRC32 functions" + tristate "CRC32/CRC32c functions" default y select BITREVERSE help This option is provided for the case where no in-kernel-tree - modules require CRC32 functions, but a module built outside the - kernel tree does. Such modules that use library CRC32 functions - require M here. + modules require CRC32/CRC32c functions, but a module built outside + the kernel tree does. Such modules that use library CRC32/CRC32c + functions require M here. + +config CRC32_SELFTEST + bool "CRC32 perform self test on init" + default n + depends on CRC32 + help + This option enables the CRC32 library functions to perform a + self test on initialization. The self test computes crc32_le + and crc32_be over byte strings with random alignment and length + and computes the total elapsed time and number of bytes processed. + +choice + prompt "CRC32 implementation" + depends on CRC32 + default CRC32_SLICEBY8 + help + This option allows a kernel builder to override the default choice + of CRC32 algorithm. Choose the default ("slice by 8") unless you + know that you need one of the others. + +config CRC32_SLICEBY8 + bool "Slice by 8 bytes" + help + Calculate checksum 8 bytes at a time with a clever slicing algorithm. + This is the fastest algorithm, but comes with a 8KiB lookup table. + Most modern processors have enough cache to hold this table without + thrashing the cache. + + This is the default implementation choice. Choose this one unless + you have a good reason not to. + +config CRC32_SLICEBY4 + bool "Slice by 4 bytes" + help + Calculate checksum 4 bytes at a time with a clever slicing algorithm. + This is a bit slower than slice by 8, but has a smaller 4KiB lookup + table. + + Only choose this option if you know what you are doing. + +config CRC32_SARWATE + bool "Sarwate's Algorithm (one byte at a time)" + help + Calculate checksum a byte at a time using Sarwate's algorithm. This + is not particularly fast, but has a small 256 byte lookup table. + + Only choose this option if you know what you are doing. + +config CRC32_BIT + bool "Classic Algorithm (one bit at a time)" + help + Calculate checksum one bit at a time. This is VERY slow, but has + no lookup table. This is provided as a debugging option. + + Only choose this option if you are debugging crc32. + +endchoice config CRC7 tristate "CRC7 functions" @@ -224,6 +285,7 @@ config BTREE config HAS_IOMEM boolean depends on !NO_IOMEM + select GENERIC_IO default y config HAS_IOPORT diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index f32a41f2a82..6777153f18f 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -184,7 +184,7 @@ config LOCKUP_DETECTOR config HARDLOCKUP_DETECTOR def_bool LOCKUP_DETECTOR && PERF_EVENTS && HAVE_PERF_EVENTS_NMI && \ - !ARCH_HAS_NMI_WATCHDOG + !HAVE_NMI_WATCHDOG config BOOTPARAM_HARDLOCKUP_PANIC bool "Panic (Reboot) On Hard Lockups" @@ -1142,14 +1142,6 @@ config LATENCYTOP Enable this option if you want to use the LatencyTOP tool to find out which userspace is blocking on what kernel operations. -config SYSCTL_SYSCALL_CHECK - bool "Sysctl checks" - depends on SYSCTL - ---help--- - sys_sysctl uses binary paths that have been found challenging - to properly maintain and use. This enables checks that help - you to keep things correct. - source mm/Kconfig.debug source kernel/trace/Kconfig diff --git a/lib/argv_split.c b/lib/argv_split.c index 4b1b083f219..1e9a6cbc368 100644 --- a/lib/argv_split.c +++ b/lib/argv_split.c @@ -6,7 +6,7 @@ #include <linux/ctype.h> #include <linux/string.h> #include <linux/slab.h> -#include <linux/module.h> +#include <linux/export.h> static const char *skip_arg(const char *cp) { diff --git a/lib/atomic64.c b/lib/atomic64.c index 3975470caf4..978537809d8 100644 --- a/lib/atomic64.c +++ b/lib/atomic64.c @@ -13,7 +13,7 @@ #include <linux/cache.h> #include <linux/spinlock.h> #include <linux/init.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/atomic.h> /* diff --git a/lib/atomic64_test.c b/lib/atomic64_test.c index 0c33cde2a1e..cb99b91c3a1 100644 --- a/lib/atomic64_test.c +++ b/lib/atomic64_test.c @@ -9,6 +9,7 @@ * (at your option) any later version. */ #include <linux/init.h> +#include <linux/bug.h> #include <linux/kernel.h> #include <linux/atomic.h> diff --git a/lib/average.c b/lib/average.c index 5576c284149..99a67e662b3 100644 --- a/lib/average.c +++ b/lib/average.c @@ -5,8 +5,9 @@ * Version 2. See the file COPYING for more details. */ -#include <linux/module.h> +#include <linux/export.h> #include <linux/average.h> +#include <linux/kernel.h> #include <linux/bug.h> #include <linux/log2.h> diff --git a/lib/bcd.c b/lib/bcd.c index d74257fd0fe..55efaf74234 100644 --- a/lib/bcd.c +++ b/lib/bcd.c @@ -1,5 +1,5 @@ #include <linux/bcd.h> -#include <linux/module.h> +#include <linux/export.h> unsigned bcd2bin(unsigned char val) { diff --git a/lib/bitmap.c b/lib/bitmap.c index 0d4a127dd9b..b5a8b6ad245 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -5,11 +5,13 @@ * This source code is licensed under the GNU General Public License, * Version 2. See the file COPYING for more details. */ -#include <linux/module.h> +#include <linux/export.h> +#include <linux/thread_info.h> #include <linux/ctype.h> #include <linux/errno.h> #include <linux/bitmap.h> #include <linux/bitops.h> +#include <linux/bug.h> #include <asm/uaccess.h> /* diff --git a/lib/bsearch.c b/lib/bsearch.c index 5b54758e2af..e33c179089d 100644 --- a/lib/bsearch.c +++ b/lib/bsearch.c @@ -9,7 +9,7 @@ * published by the Free Software Foundation; version 2. */ -#include <linux/module.h> +#include <linux/export.h> #include <linux/bsearch.h> /* diff --git a/lib/check_signature.c b/lib/check_signature.c index fd6af199247..6b49797980c 100644 --- a/lib/check_signature.c +++ b/lib/check_signature.c @@ -1,5 +1,5 @@ #include <linux/io.h> -#include <linux/module.h> +#include <linux/export.h> /** * check_signature - find BIOS signatures diff --git a/lib/checksum.c b/lib/checksum.c index 8df2f91e6d9..12dceb27ff2 100644 --- a/lib/checksum.c +++ b/lib/checksum.c @@ -32,7 +32,7 @@ /* Revised by Kenneth Albanowski for m68knommu. Basic problem: unaligned access kills, so most of the assembly has to go. */ -#include <linux/module.h> +#include <linux/export.h> #include <net/checksum.h> #include <asm/byteorder.h> diff --git a/lib/cmdline.c b/lib/cmdline.c index f5f3ad8b62f..eb6791188cf 100644 --- a/lib/cmdline.c +++ b/lib/cmdline.c @@ -12,7 +12,7 @@ * */ -#include <linux/module.h> +#include <linux/export.h> #include <linux/kernel.h> #include <linux/string.h> diff --git a/lib/cpu_rmap.c b/lib/cpu_rmap.c index 987acfafeb8..145dec5267c 100644 --- a/lib/cpu_rmap.c +++ b/lib/cpu_rmap.c @@ -11,7 +11,7 @@ #ifdef CONFIG_GENERIC_HARDIRQS #include <linux/interrupt.h> #endif -#include <linux/module.h> +#include <linux/export.h> /* * These functions maintain a mapping from CPUs to some ordered set of diff --git a/lib/cpumask.c b/lib/cpumask.c index af3e5817de9..402a54ac35c 100644 --- a/lib/cpumask.c +++ b/lib/cpumask.c @@ -2,7 +2,7 @@ #include <linux/kernel.h> #include <linux/bitops.h> #include <linux/cpumask.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/bootmem.h> int __first_cpu(const cpumask_t *srcp) @@ -26,18 +26,6 @@ int __next_cpu_nr(int n, const cpumask_t *srcp) EXPORT_SYMBOL(__next_cpu_nr); #endif -int __any_online_cpu(const cpumask_t *mask) -{ - int cpu; - - for_each_cpu(cpu, mask) { - if (cpu_online(cpu)) - break; - } - return cpu; -} -EXPORT_SYMBOL(__any_online_cpu); - /** * cpumask_next_and - get the next cpu in *src1p & *src2p * @n: the cpu prior to the place to search (ie. return will be > @n) diff --git a/lib/crc32.c b/lib/crc32.c index 4b35d2b4437..b0d278fb1d9 100644 --- a/lib/crc32.c +++ b/lib/crc32.c @@ -1,4 +1,8 @@ /* + * Aug 8, 2011 Bob Pearson with help from Joakim Tjernlund and George Spelvin + * cleaned up code to current version of sparse and added the slicing-by-8 + * algorithm to the closely similar existing slicing-by-4 algorithm. + * * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com> * Nicer crc32 functions/docs submitted by linux@horizon.com. Thanks! * Code was from the public domain, copyright abandoned. Code was @@ -20,52 +24,58 @@ * Version 2. See the file COPYING for more details. */ +/* see: Documentation/crc32.txt for a description of algorithms */ + #include <linux/crc32.h> -#include <linux/kernel.h> #include <linux/module.h> -#include <linux/compiler.h> #include <linux/types.h> -#include <linux/init.h> -#include <linux/atomic.h> #include "crc32defs.h" -#if CRC_LE_BITS == 8 -# define tole(x) __constant_cpu_to_le32(x) + +#if CRC_LE_BITS > 8 +# define tole(x) ((__force u32) __constant_cpu_to_le32(x)) #else # define tole(x) (x) #endif -#if CRC_BE_BITS == 8 -# define tobe(x) __constant_cpu_to_be32(x) +#if CRC_BE_BITS > 8 +# define tobe(x) ((__force u32) __constant_cpu_to_be32(x)) #else # define tobe(x) (x) #endif + #include "crc32table.h" MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>"); -MODULE_DESCRIPTION("Ethernet CRC32 calculations"); +MODULE_DESCRIPTION("Various CRC32 calculations"); MODULE_LICENSE("GPL"); -#if CRC_LE_BITS == 8 || CRC_BE_BITS == 8 +#if CRC_LE_BITS > 8 || CRC_BE_BITS > 8 +/* implements slicing-by-4 or slicing-by-8 algorithm */ static inline u32 crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) { # ifdef __LITTLE_ENDIAN # define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8) -# define DO_CRC4 crc = t3[(crc) & 255] ^ \ - t2[(crc >> 8) & 255] ^ \ - t1[(crc >> 16) & 255] ^ \ - t0[(crc >> 24) & 255] +# define DO_CRC4 (t3[(q) & 255] ^ t2[(q >> 8) & 255] ^ \ + t1[(q >> 16) & 255] ^ t0[(q >> 24) & 255]) +# define DO_CRC8 (t7[(q) & 255] ^ t6[(q >> 8) & 255] ^ \ + t5[(q >> 16) & 255] ^ t4[(q >> 24) & 255]) # else # define DO_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8) -# define DO_CRC4 crc = t0[(crc) & 255] ^ \ - t1[(crc >> 8) & 255] ^ \ - t2[(crc >> 16) & 255] ^ \ - t3[(crc >> 24) & 255] +# define DO_CRC4 (t0[(q) & 255] ^ t1[(q >> 8) & 255] ^ \ + t2[(q >> 16) & 255] ^ t3[(q >> 24) & 255]) +# define DO_CRC8 (t4[(q) & 255] ^ t5[(q >> 8) & 255] ^ \ + t6[(q >> 16) & 255] ^ t7[(q >> 24) & 255]) # endif const u32 *b; size_t rem_len; +# ifdef CONFIG_X86 + size_t i; +# endif const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3]; + const u32 *t4 = tab[4], *t5 = tab[5], *t6 = tab[6], *t7 = tab[7]; + u32 q; /* Align it */ if (unlikely((long)buf & 3 && len)) { @@ -73,27 +83,51 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) DO_CRC(*buf++); } while ((--len) && ((long)buf)&3); } + +# if CRC_LE_BITS == 32 rem_len = len & 3; - /* load data 32 bits wide, xor data 32 bits wide. */ len = len >> 2; +# else + rem_len = len & 7; + len = len >> 3; +# endif + b = (const u32 *)buf; +# ifdef CONFIG_X86 + --b; + for (i = 0; i < len; i++) { +# else for (--b; len; --len) { - crc ^= *++b; /* use pre increment for speed */ - DO_CRC4; +# endif + q = crc ^ *++b; /* use pre increment for speed */ +# if CRC_LE_BITS == 32 + crc = DO_CRC4; +# else + crc = DO_CRC8; + q = *++b; + crc ^= DO_CRC4; +# endif } len = rem_len; /* And the last few bytes */ if (len) { u8 *p = (u8 *)(b + 1) - 1; +# ifdef CONFIG_X86 + for (i = 0; i < len; i++) + DO_CRC(*++p); /* use pre increment for speed */ +# else do { DO_CRC(*++p); /* use pre increment for speed */ } while (--len); +# endif } return crc; #undef DO_CRC #undef DO_CRC4 +#undef DO_CRC8 } #endif + /** * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for @@ -101,53 +135,66 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) * @p: pointer to buffer over which CRC is run * @len: length of buffer @p */ -u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len); - -#if CRC_LE_BITS == 1 -/* - * In fact, the table-based code will work in this case, but it can be - * simplified by inlining the table in ?: form. - */ - -u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) +static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p, + size_t len, const u32 (*tab)[256], + u32 polynomial) { +#if CRC_LE_BITS == 1 int i; while (len--) { crc ^= *p++; for (i = 0; i < 8; i++) - crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0); + crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0); + } +# elif CRC_LE_BITS == 2 + while (len--) { + crc ^= *p++; + crc = (crc >> 2) ^ tab[0][crc & 3]; + crc = (crc >> 2) ^ tab[0][crc & 3]; + crc = (crc >> 2) ^ tab[0][crc & 3]; + crc = (crc >> 2) ^ tab[0][crc & 3]; } - return crc; -} -#else /* Table-based approach */ - -u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) -{ -# if CRC_LE_BITS == 8 - const u32 (*tab)[] = crc32table_le; - - crc = __cpu_to_le32(crc); - crc = crc32_body(crc, p, len, tab); - return __le32_to_cpu(crc); # elif CRC_LE_BITS == 4 while (len--) { crc ^= *p++; - crc = (crc >> 4) ^ crc32table_le[crc & 15]; - crc = (crc >> 4) ^ crc32table_le[crc & 15]; + crc = (crc >> 4) ^ tab[0][crc & 15]; + crc = (crc >> 4) ^ tab[0][crc & 15]; } - return crc; -# elif CRC_LE_BITS == 2 +# elif CRC_LE_BITS == 8 + /* aka Sarwate algorithm */ while (len--) { crc ^= *p++; - crc = (crc >> 2) ^ crc32table_le[crc & 3]; - crc = (crc >> 2) ^ crc32table_le[crc & 3]; - crc = (crc >> 2) ^ crc32table_le[crc & 3]; - crc = (crc >> 2) ^ crc32table_le[crc & 3]; + crc = (crc >> 8) ^ tab[0][crc & 255]; } +# else + crc = (__force u32) __cpu_to_le32(crc); + crc = crc32_body(crc, p, len, tab); + crc = __le32_to_cpu((__force __le32)crc); +#endif return crc; -# endif +} + +#if CRC_LE_BITS == 1 +u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_le_generic(crc, p, len, NULL, CRCPOLY_LE); +} +u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_le_generic(crc, p, len, NULL, CRC32C_POLY_LE); +} +#else +u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_le_generic(crc, p, len, crc32table_le, CRCPOLY_LE); +} +u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_le_generic(crc, p, len, crc32ctable_le, CRC32C_POLY_LE); } #endif +EXPORT_SYMBOL(crc32_le); +EXPORT_SYMBOL(__crc32c_le); /** * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32 @@ -156,317 +203,913 @@ u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) * @p: pointer to buffer over which CRC is run * @len: length of buffer @p */ -u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len); - -#if CRC_BE_BITS == 1 -/* - * In fact, the table-based code will work in this case, but it can be - * simplified by inlining the table in ?: form. - */ - -u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) +static inline u32 __pure crc32_be_generic(u32 crc, unsigned char const *p, + size_t len, const u32 (*tab)[256], + u32 polynomial) { +#if CRC_BE_BITS == 1 int i; while (len--) { crc ^= *p++ << 24; for (i = 0; i < 8; i++) crc = - (crc << 1) ^ ((crc & 0x80000000) ? CRCPOLY_BE : + (crc << 1) ^ ((crc & 0x80000000) ? polynomial : 0); } - return crc; -} - -#else /* Table-based approach */ -u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) -{ -# if CRC_BE_BITS == 8 - const u32 (*tab)[] = crc32table_be; - - crc = __cpu_to_be32(crc); - crc = crc32_body(crc, p, len, tab); - return __be32_to_cpu(crc); +# elif CRC_BE_BITS == 2 + while (len--) { + crc ^= *p++ << 24; + crc = (crc << 2) ^ tab[0][crc >> 30]; + crc = (crc << 2) ^ tab[0][crc >> 30]; + crc = (crc << 2) ^ tab[0][crc >> 30]; + crc = (crc << 2) ^ tab[0][crc >> 30]; + } # elif CRC_BE_BITS == 4 while (len--) { crc ^= *p++ << 24; - crc = (crc << 4) ^ crc32table_be[crc >> 28]; - crc = (crc << 4) ^ crc32table_be[crc >> 28]; + crc = (crc << 4) ^ tab[0][crc >> 28]; + crc = (crc << 4) ^ tab[0][crc >> 28]; } - return crc; -# elif CRC_BE_BITS == 2 +# elif CRC_BE_BITS == 8 while (len--) { crc ^= *p++ << 24; - crc = (crc << 2) ^ crc32table_be[crc >> 30]; - crc = (crc << 2) ^ crc32table_be[crc >> 30]; - crc = (crc << 2) ^ crc32table_be[crc >> 30]; - crc = (crc << 2) ^ crc32table_be[crc >> 30]; + crc = (crc << 8) ^ tab[0][crc >> 24]; } - return crc; +# else + crc = (__force u32) __cpu_to_be32(crc); + crc = crc32_body(crc, p, len, tab); + crc = __be32_to_cpu((__force __be32)crc); # endif + return crc; } -#endif -EXPORT_SYMBOL(crc32_le); +#if CRC_LE_BITS == 1 +u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_be_generic(crc, p, len, NULL, CRCPOLY_BE); +} +#else +u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_be_generic(crc, p, len, crc32table_be, CRCPOLY_BE); +} +#endif EXPORT_SYMBOL(crc32_be); -/* - * A brief CRC tutorial. - * - * A CRC is a long-division remainder. You add the CRC to the message, - * and the whole thing (message+CRC) is a multiple of the given - * CRC polynomial. To check the CRC, you can either check that the - * CRC matches the recomputed value, *or* you can check that the - * remainder computed on the message+CRC is 0. This latter approach - * is used by a lot of hardware implementations, and is why so many - * protocols put the end-of-frame flag after the CRC. - * - * It's actually the same long division you learned in school, except that - * - We're working in binary, so the digits are only 0 and 1, and - * - When dividing polynomials, there are no carries. Rather than add and - * subtract, we just xor. Thus, we tend to get a bit sloppy about - * the difference between adding and subtracting. - * - * A 32-bit CRC polynomial is actually 33 bits long. But since it's - * 33 bits long, bit 32 is always going to be set, so usually the CRC - * is written in hex with the most significant bit omitted. (If you're - * familiar with the IEEE 754 floating-point format, it's the same idea.) - * - * Note that a CRC is computed over a string of *bits*, so you have - * to decide on the endianness of the bits within each byte. To get - * the best error-detecting properties, this should correspond to the - * order they're actually sent. For example, standard RS-232 serial is - * little-endian; the most significant bit (sometimes used for parity) - * is sent last. And when appending a CRC word to a message, you should - * do it in the right order, matching the endianness. - * - * Just like with ordinary division, the remainder is always smaller than - * the divisor (the CRC polynomial) you're dividing by. Each step of the - * division, you take one more digit (bit) of the dividend and append it - * to the current remainder. Then you figure out the appropriate multiple - * of the divisor to subtract to being the remainder back into range. - * In binary, it's easy - it has to be either 0 or 1, and to make the - * XOR cancel, it's just a copy of bit 32 of the remainder. - * - * When computing a CRC, we don't care about the quotient, so we can - * throw the quotient bit away, but subtract the appropriate multiple of - * the polynomial from the remainder and we're back to where we started, - * ready to process the next bit. - * - * A big-endian CRC written this way would be coded like: - * for (i = 0; i < input_bits; i++) { - * multiple = remainder & 0x80000000 ? CRCPOLY : 0; - * remainder = (remainder << 1 | next_input_bit()) ^ multiple; - * } - * Notice how, to get at bit 32 of the shifted remainder, we look - * at bit 31 of the remainder *before* shifting it. - * - * But also notice how the next_input_bit() bits we're shifting into - * the remainder don't actually affect any decision-making until - * 32 bits later. Thus, the first 32 cycles of this are pretty boring. - * Also, to add the CRC to a message, we need a 32-bit-long hole for it at - * the end, so we have to add 32 extra cycles shifting in zeros at the - * end of every message, - * - * So the standard trick is to rearrage merging in the next_input_bit() - * until the moment it's needed. Then the first 32 cycles can be precomputed, - * and merging in the final 32 zero bits to make room for the CRC can be - * skipped entirely. - * This changes the code to: - * for (i = 0; i < input_bits; i++) { - * remainder ^= next_input_bit() << 31; - * multiple = (remainder & 0x80000000) ? CRCPOLY : 0; - * remainder = (remainder << 1) ^ multiple; - * } - * With this optimization, the little-endian code is simpler: - * for (i = 0; i < input_bits; i++) { - * remainder ^= next_input_bit(); - * multiple = (remainder & 1) ? CRCPOLY : 0; - * remainder = (remainder >> 1) ^ multiple; - * } - * - * Note that the other details of endianness have been hidden in CRCPOLY - * (which must be bit-reversed) and next_input_bit(). - * - * However, as long as next_input_bit is returning the bits in a sensible - * order, we can actually do the merging 8 or more bits at a time rather - * than one bit at a time: - * for (i = 0; i < input_bytes; i++) { - * remainder ^= next_input_byte() << 24; - * for (j = 0; j < 8; j++) { - * multiple = (remainder & 0x80000000) ? CRCPOLY : 0; - * remainder = (remainder << 1) ^ multiple; - * } - * } - * Or in little-endian: - * for (i = 0; i < input_bytes; i++) { - * remainder ^= next_input_byte(); - * for (j = 0; j < 8; j++) { - * multiple = (remainder & 1) ? CRCPOLY : 0; - * remainder = (remainder << 1) ^ multiple; - * } - * } - * If the input is a multiple of 32 bits, you can even XOR in a 32-bit - * word at a time and increase the inner loop count to 32. - * - * You can also mix and match the two loop styles, for example doing the - * bulk of a message byte-at-a-time and adding bit-at-a-time processing - * for any fractional bytes at the end. - * - * The only remaining optimization is to the byte-at-a-time table method. - * Here, rather than just shifting one bit of the remainder to decide - * in the correct multiple to subtract, we can shift a byte at a time. - * This produces a 40-bit (rather than a 33-bit) intermediate remainder, - * but again the multiple of the polynomial to subtract depends only on - * the high bits, the high 8 bits in this case. - * - * The multiple we need in that case is the low 32 bits of a 40-bit - * value whose high 8 bits are given, and which is a multiple of the - * generator polynomial. This is simply the CRC-32 of the given - * one-byte message. - * - * Two more details: normally, appending zero bits to a message which - * is already a multiple of a polynomial produces a larger multiple of that - * polynomial. To enable a CRC to detect this condition, it's common to - * invert the CRC before appending it. This makes the remainder of the - * message+crc come out not as zero, but some fixed non-zero value. - * - * The same problem applies to zero bits prepended to the message, and - * a similar solution is used. Instead of starting with a remainder of - * 0, an initial remainder of all ones is used. As long as you start - * the same way on decoding, it doesn't make a difference. - */ - -#ifdef UNITTEST +#ifdef CONFIG_CRC32_SELFTEST -#include <stdlib.h> -#include <stdio.h> +/* 4096 random bytes */ +static u8 __attribute__((__aligned__(8))) test_buf[] = +{ + 0x5b, 0x85, 0x21, 0xcb, 0x09, 0x68, 0x7d, 0x30, + 0xc7, 0x69, 0xd7, 0x30, 0x92, 0xde, 0x59, 0xe4, + 0xc9, 0x6e, 0x8b, 0xdb, 0x98, 0x6b, 0xaa, 0x60, + 0xa8, 0xb5, 0xbc, 0x6c, 0xa9, 0xb1, 0x5b, 0x2c, + 0xea, 0xb4, 0x92, 0x6a, 0x3f, 0x79, 0x91, 0xe4, + 0xe9, 0x70, 0x51, 0x8c, 0x7f, 0x95, 0x6f, 0x1a, + 0x56, 0xa1, 0x5c, 0x27, 0x03, 0x67, 0x9f, 0x3a, + 0xe2, 0x31, 0x11, 0x29, 0x6b, 0x98, 0xfc, 0xc4, + 0x53, 0x24, 0xc5, 0x8b, 0xce, 0x47, 0xb2, 0xb9, + 0x32, 0xcb, 0xc1, 0xd0, 0x03, 0x57, 0x4e, 0xd4, + 0xe9, 0x3c, 0xa1, 0x63, 0xcf, 0x12, 0x0e, 0xca, + 0xe1, 0x13, 0xd1, 0x93, 0xa6, 0x88, 0x5c, 0x61, + 0x5b, 0xbb, 0xf0, 0x19, 0x46, 0xb4, 0xcf, 0x9e, + 0xb6, 0x6b, 0x4c, 0x3a, 0xcf, 0x60, 0xf9, 0x7a, + 0x8d, 0x07, 0x63, 0xdb, 0x40, 0xe9, 0x0b, 0x6f, + 0xad, 0x97, 0xf1, 0xed, 0xd0, 0x1e, 0x26, 0xfd, + 0xbf, 0xb7, 0xc8, 0x04, 0x94, 0xf8, 0x8b, 0x8c, + 0xf1, 0xab, 0x7a, 0xd4, 0xdd, 0xf3, 0xe8, 0x88, + 0xc3, 0xed, 0x17, 0x8a, 0x9b, 0x40, 0x0d, 0x53, + 0x62, 0x12, 0x03, 0x5f, 0x1b, 0x35, 0x32, 0x1f, + 0xb4, 0x7b, 0x93, 0x78, 0x0d, 0xdb, 0xce, 0xa4, + 0xc0, 0x47, 0xd5, 0xbf, 0x68, 0xe8, 0x5d, 0x74, + 0x8f, 0x8e, 0x75, 0x1c, 0xb2, 0x4f, 0x9a, 0x60, + 0xd1, 0xbe, 0x10, 0xf4, 0x5c, 0xa1, 0x53, 0x09, + 0xa5, 0xe0, 0x09, 0x54, 0x85, 0x5c, 0xdc, 0x07, + 0xe7, 0x21, 0x69, 0x7b, 0x8a, 0xfd, 0x90, 0xf1, + 0x22, 0xd0, 0xb4, 0x36, 0x28, 0xe6, 0xb8, 0x0f, + 0x39, 0xde, 0xc8, 0xf3, 0x86, 0x60, 0x34, 0xd2, + 0x5e, 0xdf, 0xfd, 0xcf, 0x0f, 0xa9, 0x65, 0xf0, + 0xd5, 0x4d, 0x96, 0x40, 0xe3, 0xdf, 0x3f, 0x95, + 0x5a, 0x39, 0x19, 0x93, 0xf4, 0x75, 0xce, 0x22, + 0x00, 0x1c, 0x93, 0xe2, 0x03, 0x66, 0xf4, 0x93, + 0x73, 0x86, 0x81, 0x8e, 0x29, 0x44, 0x48, 0x86, + 0x61, 0x7c, 0x48, 0xa3, 0x43, 0xd2, 0x9c, 0x8d, + 0xd4, 0x95, 0xdd, 0xe1, 0x22, 0x89, 0x3a, 0x40, + 0x4c, 0x1b, 0x8a, 0x04, 0xa8, 0x09, 0x69, 0x8b, + 0xea, 0xc6, 0x55, 0x8e, 0x57, 0xe6, 0x64, 0x35, + 0xf0, 0xc7, 0x16, 0x9f, 0x5d, 0x5e, 0x86, 0x40, + 0x46, 0xbb, 0xe5, 0x45, 0x88, 0xfe, 0xc9, 0x63, + 0x15, 0xfb, 0xf5, 0xbd, 0x71, 0x61, 0xeb, 0x7b, + 0x78, 0x70, 0x07, 0x31, 0x03, 0x9f, 0xb2, 0xc8, + 0xa7, 0xab, 0x47, 0xfd, 0xdf, 0xa0, 0x78, 0x72, + 0xa4, 0x2a, 0xe4, 0xb6, 0xba, 0xc0, 0x1e, 0x86, + 0x71, 0xe6, 0x3d, 0x18, 0x37, 0x70, 0xe6, 0xff, + 0xe0, 0xbc, 0x0b, 0x22, 0xa0, 0x1f, 0xd3, 0xed, + 0xa2, 0x55, 0x39, 0xab, 0xa8, 0x13, 0x73, 0x7c, + 0x3f, 0xb2, 0xd6, 0x19, 0xac, 0xff, 0x99, 0xed, + 0xe8, 0xe6, 0xa6, 0x22, 0xe3, 0x9c, 0xf1, 0x30, + 0xdc, 0x01, 0x0a, 0x56, 0xfa, 0xe4, 0xc9, 0x99, + 0xdd, 0xa8, 0xd8, 0xda, 0x35, 0x51, 0x73, 0xb4, + 0x40, 0x86, 0x85, 0xdb, 0x5c, 0xd5, 0x85, 0x80, + 0x14, 0x9c, 0xfd, 0x98, 0xa9, 0x82, 0xc5, 0x37, + 0xff, 0x32, 0x5d, 0xd0, 0x0b, 0xfa, 0xdc, 0x04, + 0x5e, 0x09, 0xd2, 0xca, 0x17, 0x4b, 0x1a, 0x8e, + 0x15, 0xe1, 0xcc, 0x4e, 0x52, 0x88, 0x35, 0xbd, + 0x48, 0xfe, 0x15, 0xa0, 0x91, 0xfd, 0x7e, 0x6c, + 0x0e, 0x5d, 0x79, 0x1b, 0x81, 0x79, 0xd2, 0x09, + 0x34, 0x70, 0x3d, 0x81, 0xec, 0xf6, 0x24, 0xbb, + 0xfb, 0xf1, 0x7b, 0xdf, 0x54, 0xea, 0x80, 0x9b, + 0xc7, 0x99, 0x9e, 0xbd, 0x16, 0x78, 0x12, 0x53, + 0x5e, 0x01, 0xa7, 0x4e, 0xbd, 0x67, 0xe1, 0x9b, + 0x4c, 0x0e, 0x61, 0x45, 0x97, 0xd2, 0xf0, 0x0f, + 0xfe, 0x15, 0x08, 0xb7, 0x11, 0x4c, 0xe7, 0xff, + 0x81, 0x53, 0xff, 0x91, 0x25, 0x38, 0x7e, 0x40, + 0x94, 0xe5, 0xe0, 0xad, 0xe6, 0xd9, 0x79, 0xb6, + 0x92, 0xc9, 0xfc, 0xde, 0xc3, 0x1a, 0x23, 0xbb, + 0xdd, 0xc8, 0x51, 0x0c, 0x3a, 0x72, 0xfa, 0x73, + 0x6f, 0xb7, 0xee, 0x61, 0x39, 0x03, 0x01, 0x3f, + 0x7f, 0x94, 0x2e, 0x2e, 0xba, 0x3a, 0xbb, 0xb4, + 0xfa, 0x6a, 0x17, 0xfe, 0xea, 0xef, 0x5e, 0x66, + 0x97, 0x3f, 0x32, 0x3d, 0xd7, 0x3e, 0xb1, 0xf1, + 0x6c, 0x14, 0x4c, 0xfd, 0x37, 0xd3, 0x38, 0x80, + 0xfb, 0xde, 0xa6, 0x24, 0x1e, 0xc8, 0xca, 0x7f, + 0x3a, 0x93, 0xd8, 0x8b, 0x18, 0x13, 0xb2, 0xe5, + 0xe4, 0x93, 0x05, 0x53, 0x4f, 0x84, 0x66, 0xa7, + 0x58, 0x5c, 0x7b, 0x86, 0x52, 0x6d, 0x0d, 0xce, + 0xa4, 0x30, 0x7d, 0xb6, 0x18, 0x9f, 0xeb, 0xff, + 0x22, 0xbb, 0x72, 0x29, 0xb9, 0x44, 0x0b, 0x48, + 0x1e, 0x84, 0x71, 0x81, 0xe3, 0x6d, 0x73, 0x26, + 0x92, 0xb4, 0x4d, 0x2a, 0x29, 0xb8, 0x1f, 0x72, + 0xed, 0xd0, 0xe1, 0x64, 0x77, 0xea, 0x8e, 0x88, + 0x0f, 0xef, 0x3f, 0xb1, 0x3b, 0xad, 0xf9, 0xc9, + 0x8b, 0xd0, 0xac, 0xc6, 0xcc, 0xa9, 0x40, 0xcc, + 0x76, 0xf6, 0x3b, 0x53, 0xb5, 0x88, 0xcb, 0xc8, + 0x37, 0xf1, 0xa2, 0xba, 0x23, 0x15, 0x99, 0x09, + 0xcc, 0xe7, 0x7a, 0x3b, 0x37, 0xf7, 0x58, 0xc8, + 0x46, 0x8c, 0x2b, 0x2f, 0x4e, 0x0e, 0xa6, 0x5c, + 0xea, 0x85, 0x55, 0xba, 0x02, 0x0e, 0x0e, 0x48, + 0xbc, 0xe1, 0xb1, 0x01, 0x35, 0x79, 0x13, 0x3d, + 0x1b, 0xc0, 0x53, 0x68, 0x11, 0xe7, 0x95, 0x0f, + 0x9d, 0x3f, 0x4c, 0x47, 0x7b, 0x4d, 0x1c, 0xae, + 0x50, 0x9b, 0xcb, 0xdd, 0x05, 0x8d, 0x9a, 0x97, + 0xfd, 0x8c, 0xef, 0x0c, 0x1d, 0x67, 0x73, 0xa8, + 0x28, 0x36, 0xd5, 0xb6, 0x92, 0x33, 0x40, 0x75, + 0x0b, 0x51, 0xc3, 0x64, 0xba, 0x1d, 0xc2, 0xcc, + 0xee, 0x7d, 0x54, 0x0f, 0x27, 0x69, 0xa7, 0x27, + 0x63, 0x30, 0x29, 0xd9, 0xc8, 0x84, 0xd8, 0xdf, + 0x9f, 0x68, 0x8d, 0x04, 0xca, 0xa6, 0xc5, 0xc7, + 0x7a, 0x5c, 0xc8, 0xd1, 0xcb, 0x4a, 0xec, 0xd0, + 0xd8, 0x20, 0x69, 0xc5, 0x17, 0xcd, 0x78, 0xc8, + 0x75, 0x23, 0x30, 0x69, 0xc9, 0xd4, 0xea, 0x5c, + 0x4f, 0x6b, 0x86, 0x3f, 0x8b, 0xfe, 0xee, 0x44, + 0xc9, 0x7c, 0xb7, 0xdd, 0x3e, 0xe5, 0xec, 0x54, + 0x03, 0x3e, 0xaa, 0x82, 0xc6, 0xdf, 0xb2, 0x38, + 0x0e, 0x5d, 0xb3, 0x88, 0xd9, 0xd3, 0x69, 0x5f, + 0x8f, 0x70, 0x8a, 0x7e, 0x11, 0xd9, 0x1e, 0x7b, + 0x38, 0xf1, 0x42, 0x1a, 0xc0, 0x35, 0xf5, 0xc7, + 0x36, 0x85, 0xf5, 0xf7, 0xb8, 0x7e, 0xc7, 0xef, + 0x18, 0xf1, 0x63, 0xd6, 0x7a, 0xc6, 0xc9, 0x0e, + 0x4d, 0x69, 0x4f, 0x84, 0xef, 0x26, 0x41, 0x0c, + 0xec, 0xc7, 0xe0, 0x7e, 0x3c, 0x67, 0x01, 0x4c, + 0x62, 0x1a, 0x20, 0x6f, 0xee, 0x47, 0x4d, 0xc0, + 0x99, 0x13, 0x8d, 0x91, 0x4a, 0x26, 0xd4, 0x37, + 0x28, 0x90, 0x58, 0x75, 0x66, 0x2b, 0x0a, 0xdf, + 0xda, 0xee, 0x92, 0x25, 0x90, 0x62, 0x39, 0x9e, + 0x44, 0x98, 0xad, 0xc1, 0x88, 0xed, 0xe4, 0xb4, + 0xaf, 0xf5, 0x8c, 0x9b, 0x48, 0x4d, 0x56, 0x60, + 0x97, 0x0f, 0x61, 0x59, 0x9e, 0xa6, 0x27, 0xfe, + 0xc1, 0x91, 0x15, 0x38, 0xb8, 0x0f, 0xae, 0x61, + 0x7d, 0x26, 0x13, 0x5a, 0x73, 0xff, 0x1c, 0xa3, + 0x61, 0x04, 0x58, 0x48, 0x55, 0x44, 0x11, 0xfe, + 0x15, 0xca, 0xc3, 0xbd, 0xca, 0xc5, 0xb4, 0x40, + 0x5d, 0x1b, 0x7f, 0x39, 0xb5, 0x9c, 0x35, 0xec, + 0x61, 0x15, 0x32, 0x32, 0xb8, 0x4e, 0x40, 0x9f, + 0x17, 0x1f, 0x0a, 0x4d, 0xa9, 0x91, 0xef, 0xb7, + 0xb0, 0xeb, 0xc2, 0x83, 0x9a, 0x6c, 0xd2, 0x79, + 0x43, 0x78, 0x5e, 0x2f, 0xe5, 0xdd, 0x1a, 0x3c, + 0x45, 0xab, 0x29, 0x40, 0x3a, 0x37, 0x5b, 0x6f, + 0xd7, 0xfc, 0x48, 0x64, 0x3c, 0x49, 0xfb, 0x21, + 0xbe, 0xc3, 0xff, 0x07, 0xfb, 0x17, 0xe9, 0xc9, + 0x0c, 0x4c, 0x5c, 0x15, 0x9e, 0x8e, 0x22, 0x30, + 0x0a, 0xde, 0x48, 0x7f, 0xdb, 0x0d, 0xd1, 0x2b, + 0x87, 0x38, 0x9e, 0xcc, 0x5a, 0x01, 0x16, 0xee, + 0x75, 0x49, 0x0d, 0x30, 0x01, 0x34, 0x6a, 0xb6, + 0x9a, 0x5a, 0x2a, 0xec, 0xbb, 0x48, 0xac, 0xd3, + 0x77, 0x83, 0xd8, 0x08, 0x86, 0x4f, 0x48, 0x09, + 0x29, 0x41, 0x79, 0xa1, 0x03, 0x12, 0xc4, 0xcd, + 0x90, 0x55, 0x47, 0x66, 0x74, 0x9a, 0xcc, 0x4f, + 0x35, 0x8c, 0xd6, 0x98, 0xef, 0xeb, 0x45, 0xb9, + 0x9a, 0x26, 0x2f, 0x39, 0xa5, 0x70, 0x6d, 0xfc, + 0xb4, 0x51, 0xee, 0xf4, 0x9c, 0xe7, 0x38, 0x59, + 0xad, 0xf4, 0xbc, 0x46, 0xff, 0x46, 0x8e, 0x60, + 0x9c, 0xa3, 0x60, 0x1d, 0xf8, 0x26, 0x72, 0xf5, + 0x72, 0x9d, 0x68, 0x80, 0x04, 0xf6, 0x0b, 0xa1, + 0x0a, 0xd5, 0xa7, 0x82, 0x3a, 0x3e, 0x47, 0xa8, + 0x5a, 0xde, 0x59, 0x4f, 0x7b, 0x07, 0xb3, 0xe9, + 0x24, 0x19, 0x3d, 0x34, 0x05, 0xec, 0xf1, 0xab, + 0x6e, 0x64, 0x8f, 0xd3, 0xe6, 0x41, 0x86, 0x80, + 0x70, 0xe3, 0x8d, 0x60, 0x9c, 0x34, 0x25, 0x01, + 0x07, 0x4d, 0x19, 0x41, 0x4e, 0x3d, 0x5c, 0x7e, + 0xa8, 0xf5, 0xcc, 0xd5, 0x7b, 0xe2, 0x7d, 0x3d, + 0x49, 0x86, 0x7d, 0x07, 0xb7, 0x10, 0xe3, 0x35, + 0xb8, 0x84, 0x6d, 0x76, 0xab, 0x17, 0xc6, 0x38, + 0xb4, 0xd3, 0x28, 0x57, 0xad, 0xd3, 0x88, 0x5a, + 0xda, 0xea, 0xc8, 0x94, 0xcc, 0x37, 0x19, 0xac, + 0x9c, 0x9f, 0x4b, 0x00, 0x15, 0xc0, 0xc8, 0xca, + 0x1f, 0x15, 0xaa, 0xe0, 0xdb, 0xf9, 0x2f, 0x57, + 0x1b, 0x24, 0xc7, 0x6f, 0x76, 0x29, 0xfb, 0xed, + 0x25, 0x0d, 0xc0, 0xfe, 0xbd, 0x5a, 0xbf, 0x20, + 0x08, 0x51, 0x05, 0xec, 0x71, 0xa3, 0xbf, 0xef, + 0x5e, 0x99, 0x75, 0xdb, 0x3c, 0x5f, 0x9a, 0x8c, + 0xbb, 0x19, 0x5c, 0x0e, 0x93, 0x19, 0xf8, 0x6a, + 0xbc, 0xf2, 0x12, 0x54, 0x2f, 0xcb, 0x28, 0x64, + 0x88, 0xb3, 0x92, 0x0d, 0x96, 0xd1, 0xa6, 0xe4, + 0x1f, 0xf1, 0x4d, 0xa4, 0xab, 0x1c, 0xee, 0x54, + 0xf2, 0xad, 0x29, 0x6d, 0x32, 0x37, 0xb2, 0x16, + 0x77, 0x5c, 0xdc, 0x2e, 0x54, 0xec, 0x75, 0x26, + 0xc6, 0x36, 0xd9, 0x17, 0x2c, 0xf1, 0x7a, 0xdc, + 0x4b, 0xf1, 0xe2, 0xd9, 0x95, 0xba, 0xac, 0x87, + 0xc1, 0xf3, 0x8e, 0x58, 0x08, 0xd8, 0x87, 0x60, + 0xc9, 0xee, 0x6a, 0xde, 0xa4, 0xd2, 0xfc, 0x0d, + 0xe5, 0x36, 0xc4, 0x5c, 0x52, 0xb3, 0x07, 0x54, + 0x65, 0x24, 0xc1, 0xb1, 0xd1, 0xb1, 0x53, 0x13, + 0x31, 0x79, 0x7f, 0x05, 0x76, 0xeb, 0x37, 0x59, + 0x15, 0x2b, 0xd1, 0x3f, 0xac, 0x08, 0x97, 0xeb, + 0x91, 0x98, 0xdf, 0x6c, 0x09, 0x0d, 0x04, 0x9f, + 0xdc, 0x3b, 0x0e, 0x60, 0x68, 0x47, 0x23, 0x15, + 0x16, 0xc6, 0x0b, 0x35, 0xf8, 0x77, 0xa2, 0x78, + 0x50, 0xd4, 0x64, 0x22, 0x33, 0xff, 0xfb, 0x93, + 0x71, 0x46, 0x50, 0x39, 0x1b, 0x9c, 0xea, 0x4e, + 0x8d, 0x0c, 0x37, 0xe5, 0x5c, 0x51, 0x3a, 0x31, + 0xb2, 0x85, 0x84, 0x3f, 0x41, 0xee, 0xa2, 0xc1, + 0xc6, 0x13, 0x3b, 0x54, 0x28, 0xd2, 0x18, 0x37, + 0xcc, 0x46, 0x9f, 0x6a, 0x91, 0x3d, 0x5a, 0x15, + 0x3c, 0x89, 0xa3, 0x61, 0x06, 0x7d, 0x2e, 0x78, + 0xbe, 0x7d, 0x40, 0xba, 0x2f, 0x95, 0xb1, 0x2f, + 0x87, 0x3b, 0x8a, 0xbe, 0x6a, 0xf4, 0xc2, 0x31, + 0x74, 0xee, 0x91, 0xe0, 0x23, 0xaa, 0x5d, 0x7f, + 0xdd, 0xf0, 0x44, 0x8c, 0x0b, 0x59, 0x2b, 0xfc, + 0x48, 0x3a, 0xdf, 0x07, 0x05, 0x38, 0x6c, 0xc9, + 0xeb, 0x18, 0x24, 0x68, 0x8d, 0x58, 0x98, 0xd3, + 0x31, 0xa3, 0xe4, 0x70, 0x59, 0xb1, 0x21, 0xbe, + 0x7e, 0x65, 0x7d, 0xb8, 0x04, 0xab, 0xf6, 0xe4, + 0xd7, 0xda, 0xec, 0x09, 0x8f, 0xda, 0x6d, 0x24, + 0x07, 0xcc, 0x29, 0x17, 0x05, 0x78, 0x1a, 0xc1, + 0xb1, 0xce, 0xfc, 0xaa, 0x2d, 0xe7, 0xcc, 0x85, + 0x84, 0x84, 0x03, 0x2a, 0x0c, 0x3f, 0xa9, 0xf8, + 0xfd, 0x84, 0x53, 0x59, 0x5c, 0xf0, 0xd4, 0x09, + 0xf0, 0xd2, 0x6c, 0x32, 0x03, 0xb0, 0xa0, 0x8c, + 0x52, 0xeb, 0x23, 0x91, 0x88, 0x43, 0x13, 0x46, + 0xf6, 0x1e, 0xb4, 0x1b, 0xf5, 0x8e, 0x3a, 0xb5, + 0x3d, 0x00, 0xf6, 0xe5, 0x08, 0x3d, 0x5f, 0x39, + 0xd3, 0x21, 0x69, 0xbc, 0x03, 0x22, 0x3a, 0xd2, + 0x5c, 0x84, 0xf8, 0x15, 0xc4, 0x80, 0x0b, 0xbc, + 0x29, 0x3c, 0xf3, 0x95, 0x98, 0xcd, 0x8f, 0x35, + 0xbc, 0xa5, 0x3e, 0xfc, 0xd4, 0x13, 0x9e, 0xde, + 0x4f, 0xce, 0x71, 0x9d, 0x09, 0xad, 0xf2, 0x80, + 0x6b, 0x65, 0x7f, 0x03, 0x00, 0x14, 0x7c, 0x15, + 0x85, 0x40, 0x6d, 0x70, 0xea, 0xdc, 0xb3, 0x63, + 0x35, 0x4f, 0x4d, 0xe0, 0xd9, 0xd5, 0x3c, 0x58, + 0x56, 0x23, 0x80, 0xe2, 0x36, 0xdd, 0x75, 0x1d, + 0x94, 0x11, 0x41, 0x8e, 0xe0, 0x81, 0x8e, 0xcf, + 0xe0, 0xe5, 0xf6, 0xde, 0xd1, 0xe7, 0x04, 0x12, + 0x79, 0x92, 0x2b, 0x71, 0x2a, 0x79, 0x8b, 0x7c, + 0x44, 0x79, 0x16, 0x30, 0x4e, 0xf4, 0xf6, 0x9b, + 0xb7, 0x40, 0xa3, 0x5a, 0xa7, 0x69, 0x3e, 0xc1, + 0x3a, 0x04, 0xd0, 0x88, 0xa0, 0x3b, 0xdd, 0xc6, + 0x9e, 0x7e, 0x1e, 0x1e, 0x8f, 0x44, 0xf7, 0x73, + 0x67, 0x1e, 0x1a, 0x78, 0xfa, 0x62, 0xf4, 0xa9, + 0xa8, 0xc6, 0x5b, 0xb8, 0xfa, 0x06, 0x7d, 0x5e, + 0x38, 0x1c, 0x9a, 0x39, 0xe9, 0x39, 0x98, 0x22, + 0x0b, 0xa7, 0xac, 0x0b, 0xf3, 0xbc, 0xf1, 0xeb, + 0x8c, 0x81, 0xe3, 0x48, 0x8a, 0xed, 0x42, 0xc2, + 0x38, 0xcf, 0x3e, 0xda, 0xd2, 0x89, 0x8d, 0x9c, + 0x53, 0xb5, 0x2f, 0x41, 0x01, 0x26, 0x84, 0x9c, + 0xa3, 0x56, 0xf6, 0x49, 0xc7, 0xd4, 0x9f, 0x93, + 0x1b, 0x96, 0x49, 0x5e, 0xad, 0xb3, 0x84, 0x1f, + 0x3c, 0xa4, 0xe0, 0x9b, 0xd1, 0x90, 0xbc, 0x38, + 0x6c, 0xdd, 0x95, 0x4d, 0x9d, 0xb1, 0x71, 0x57, + 0x2d, 0x34, 0xe8, 0xb8, 0x42, 0xc7, 0x99, 0x03, + 0xc7, 0x07, 0x30, 0x65, 0x91, 0x55, 0xd5, 0x90, + 0x70, 0x97, 0x37, 0x68, 0xd4, 0x11, 0xf9, 0xe8, + 0xce, 0xec, 0xdc, 0x34, 0xd5, 0xd3, 0xb7, 0xc4, + 0xb8, 0x97, 0x05, 0x92, 0xad, 0xf8, 0xe2, 0x36, + 0x64, 0x41, 0xc9, 0xc5, 0x41, 0x77, 0x52, 0xd7, + 0x2c, 0xa5, 0x24, 0x2f, 0xd9, 0x34, 0x0b, 0x47, + 0x35, 0xa7, 0x28, 0x8b, 0xc5, 0xcd, 0xe9, 0x46, + 0xac, 0x39, 0x94, 0x3c, 0x10, 0xc6, 0x29, 0x73, + 0x0e, 0x0e, 0x5d, 0xe0, 0x71, 0x03, 0x8a, 0x72, + 0x0e, 0x26, 0xb0, 0x7d, 0x84, 0xed, 0x95, 0x23, + 0x49, 0x5a, 0x45, 0x83, 0x45, 0x60, 0x11, 0x4a, + 0x46, 0x31, 0xd4, 0xd8, 0x16, 0x54, 0x98, 0x58, + 0xed, 0x6d, 0xcc, 0x5d, 0xd6, 0x50, 0x61, 0x9f, + 0x9d, 0xc5, 0x3e, 0x9d, 0x32, 0x47, 0xde, 0x96, + 0xe1, 0x5d, 0xd8, 0xf8, 0xb4, 0x69, 0x6f, 0xb9, + 0x15, 0x90, 0x57, 0x7a, 0xf6, 0xad, 0xb0, 0x5b, + 0xf5, 0xa6, 0x36, 0x94, 0xfd, 0x84, 0xce, 0x1c, + 0x0f, 0x4b, 0xd0, 0xc2, 0x5b, 0x6b, 0x56, 0xef, + 0x73, 0x93, 0x0b, 0xc3, 0xee, 0xd9, 0xcf, 0xd3, + 0xa4, 0x22, 0x58, 0xcd, 0x50, 0x6e, 0x65, 0xf4, + 0xe9, 0xb7, 0x71, 0xaf, 0x4b, 0xb3, 0xb6, 0x2f, + 0x0f, 0x0e, 0x3b, 0xc9, 0x85, 0x14, 0xf5, 0x17, + 0xe8, 0x7a, 0x3a, 0xbf, 0x5f, 0x5e, 0xf8, 0x18, + 0x48, 0xa6, 0x72, 0xab, 0x06, 0x95, 0xe9, 0xc8, + 0xa7, 0xf4, 0x32, 0x44, 0x04, 0x0c, 0x84, 0x98, + 0x73, 0xe3, 0x89, 0x8d, 0x5f, 0x7e, 0x4a, 0x42, + 0x8f, 0xc5, 0x28, 0xb1, 0x82, 0xef, 0x1c, 0x97, + 0x31, 0x3b, 0x4d, 0xe0, 0x0e, 0x10, 0x10, 0x97, + 0x93, 0x49, 0x78, 0x2f, 0x0d, 0x86, 0x8b, 0xa1, + 0x53, 0xa9, 0x81, 0x20, 0x79, 0xe7, 0x07, 0x77, + 0xb6, 0xac, 0x5e, 0xd2, 0x05, 0xcd, 0xe9, 0xdb, + 0x8a, 0x94, 0x82, 0x8a, 0x23, 0xb9, 0x3d, 0x1c, + 0xa9, 0x7d, 0x72, 0x4a, 0xed, 0x33, 0xa3, 0xdb, + 0x21, 0xa7, 0x86, 0x33, 0x45, 0xa5, 0xaa, 0x56, + 0x45, 0xb5, 0x83, 0x29, 0x40, 0x47, 0x79, 0x04, + 0x6e, 0xb9, 0x95, 0xd0, 0x81, 0x77, 0x2d, 0x48, + 0x1e, 0xfe, 0xc3, 0xc2, 0x1e, 0xe5, 0xf2, 0xbe, + 0xfd, 0x3b, 0x94, 0x9f, 0xc4, 0xc4, 0x26, 0x9d, + 0xe4, 0x66, 0x1e, 0x19, 0xee, 0x6c, 0x79, 0x97, + 0x11, 0x31, 0x4b, 0x0d, 0x01, 0xcb, 0xde, 0xa8, + 0xf6, 0x6d, 0x7c, 0x39, 0x46, 0x4e, 0x7e, 0x3f, + 0x94, 0x17, 0xdf, 0xa1, 0x7d, 0xd9, 0x1c, 0x8e, + 0xbc, 0x7d, 0x33, 0x7d, 0xe3, 0x12, 0x40, 0xca, + 0xab, 0x37, 0x11, 0x46, 0xd4, 0xae, 0xef, 0x44, + 0xa2, 0xb3, 0x6a, 0x66, 0x0e, 0x0c, 0x90, 0x7f, + 0xdf, 0x5c, 0x66, 0x5f, 0xf2, 0x94, 0x9f, 0xa6, + 0x73, 0x4f, 0xeb, 0x0d, 0xad, 0xbf, 0xc0, 0x63, + 0x5c, 0xdc, 0x46, 0x51, 0xe8, 0x8e, 0x90, 0x19, + 0xa8, 0xa4, 0x3c, 0x91, 0x79, 0xfa, 0x7e, 0x58, + 0x85, 0x13, 0x55, 0xc5, 0x19, 0x82, 0x37, 0x1b, + 0x0a, 0x02, 0x1f, 0x99, 0x6b, 0x18, 0xf1, 0x28, + 0x08, 0xa2, 0x73, 0xb8, 0x0f, 0x2e, 0xcd, 0xbf, + 0xf3, 0x86, 0x7f, 0xea, 0xef, 0xd0, 0xbb, 0xa6, + 0x21, 0xdf, 0x49, 0x73, 0x51, 0xcc, 0x36, 0xd3, + 0x3e, 0xa0, 0xf8, 0x44, 0xdf, 0xd3, 0xa6, 0xbe, + 0x8a, 0xd4, 0x57, 0xdd, 0x72, 0x94, 0x61, 0x0f, + 0x82, 0xd1, 0x07, 0xb8, 0x7c, 0x18, 0x83, 0xdf, + 0x3a, 0xe5, 0x50, 0x6a, 0x82, 0x20, 0xac, 0xa9, + 0xa8, 0xff, 0xd9, 0xf3, 0x77, 0x33, 0x5a, 0x9e, + 0x7f, 0x6d, 0xfe, 0x5d, 0x33, 0x41, 0x42, 0xe7, + 0x6c, 0x19, 0xe0, 0x44, 0x8a, 0x15, 0xf6, 0x70, + 0x98, 0xb7, 0x68, 0x4d, 0xfa, 0x97, 0x39, 0xb0, + 0x8e, 0xe8, 0x84, 0x8b, 0x75, 0x30, 0xb7, 0x7d, + 0x92, 0x69, 0x20, 0x9c, 0x81, 0xfb, 0x4b, 0xf4, + 0x01, 0x50, 0xeb, 0xce, 0x0c, 0x1c, 0x6c, 0xb5, + 0x4a, 0xd7, 0x27, 0x0c, 0xce, 0xbb, 0xe5, 0x85, + 0xf0, 0xb6, 0xee, 0xd5, 0x70, 0xdd, 0x3b, 0xfc, + 0xd4, 0x99, 0xf1, 0x33, 0xdd, 0x8b, 0xc4, 0x2f, + 0xae, 0xab, 0x74, 0x96, 0x32, 0xc7, 0x4c, 0x56, + 0x3c, 0x89, 0x0f, 0x96, 0x0b, 0x42, 0xc0, 0xcb, + 0xee, 0x0f, 0x0b, 0x8c, 0xfb, 0x7e, 0x47, 0x7b, + 0x64, 0x48, 0xfd, 0xb2, 0x00, 0x80, 0x89, 0xa5, + 0x13, 0x55, 0x62, 0xfc, 0x8f, 0xe2, 0x42, 0x03, + 0xb7, 0x4e, 0x2a, 0x79, 0xb4, 0x82, 0xea, 0x23, + 0x49, 0xda, 0xaf, 0x52, 0x63, 0x1e, 0x60, 0x03, + 0x89, 0x06, 0x44, 0x46, 0x08, 0xc3, 0xc4, 0x87, + 0x70, 0x2e, 0xda, 0x94, 0xad, 0x6b, 0xe0, 0xe4, + 0xd1, 0x8a, 0x06, 0xc2, 0xa8, 0xc0, 0xa7, 0x43, + 0x3c, 0x47, 0x52, 0x0e, 0xc3, 0x77, 0x81, 0x11, + 0x67, 0x0e, 0xa0, 0x70, 0x04, 0x47, 0x29, 0x40, + 0x86, 0x0d, 0x34, 0x56, 0xa7, 0xc9, 0x35, 0x59, + 0x68, 0xdc, 0x93, 0x81, 0x70, 0xee, 0x86, 0xd9, + 0x80, 0x06, 0x40, 0x4f, 0x1a, 0x0d, 0x40, 0x30, + 0x0b, 0xcb, 0x96, 0x47, 0xc1, 0xb7, 0x52, 0xfd, + 0x56, 0xe0, 0x72, 0x4b, 0xfb, 0xbd, 0x92, 0x45, + 0x61, 0x71, 0xc2, 0x33, 0x11, 0xbf, 0x52, 0x83, + 0x79, 0x26, 0xe0, 0x49, 0x6b, 0xb7, 0x05, 0x8b, + 0xe8, 0x0e, 0x87, 0x31, 0xd7, 0x9d, 0x8a, 0xf5, + 0xc0, 0x5f, 0x2e, 0x58, 0x4a, 0xdb, 0x11, 0xb3, + 0x6c, 0x30, 0x2a, 0x46, 0x19, 0xe3, 0x27, 0x84, + 0x1f, 0x63, 0x6e, 0xf6, 0x57, 0xc7, 0xc9, 0xd8, + 0x5e, 0xba, 0xb3, 0x87, 0xd5, 0x83, 0x26, 0x34, + 0x21, 0x9e, 0x65, 0xde, 0x42, 0xd3, 0xbe, 0x7b, + 0xbc, 0x91, 0x71, 0x44, 0x4d, 0x99, 0x3b, 0x31, + 0xe5, 0x3f, 0x11, 0x4e, 0x7f, 0x13, 0x51, 0x3b, + 0xae, 0x79, 0xc9, 0xd3, 0x81, 0x8e, 0x25, 0x40, + 0x10, 0xfc, 0x07, 0x1e, 0xf9, 0x7b, 0x9a, 0x4b, + 0x6c, 0xe3, 0xb3, 0xad, 0x1a, 0x0a, 0xdd, 0x9e, + 0x59, 0x0c, 0xa2, 0xcd, 0xae, 0x48, 0x4a, 0x38, + 0x5b, 0x47, 0x41, 0x94, 0x65, 0x6b, 0xbb, 0xeb, + 0x5b, 0xe3, 0xaf, 0x07, 0x5b, 0xd4, 0x4a, 0xa2, + 0xc9, 0x5d, 0x2f, 0x64, 0x03, 0xd7, 0x3a, 0x2c, + 0x6e, 0xce, 0x76, 0x95, 0xb4, 0xb3, 0xc0, 0xf1, + 0xe2, 0x45, 0x73, 0x7a, 0x5c, 0xab, 0xc1, 0xfc, + 0x02, 0x8d, 0x81, 0x29, 0xb3, 0xac, 0x07, 0xec, + 0x40, 0x7d, 0x45, 0xd9, 0x7a, 0x59, 0xee, 0x34, + 0xf0, 0xe9, 0xd5, 0x7b, 0x96, 0xb1, 0x3d, 0x95, + 0xcc, 0x86, 0xb5, 0xb6, 0x04, 0x2d, 0xb5, 0x92, + 0x7e, 0x76, 0xf4, 0x06, 0xa9, 0xa3, 0x12, 0x0f, + 0xb1, 0xaf, 0x26, 0xba, 0x7c, 0xfc, 0x7e, 0x1c, + 0xbc, 0x2c, 0x49, 0x97, 0x53, 0x60, 0x13, 0x0b, + 0xa6, 0x61, 0x83, 0x89, 0x42, 0xd4, 0x17, 0x0c, + 0x6c, 0x26, 0x52, 0xc3, 0xb3, 0xd4, 0x67, 0xf5, + 0xe3, 0x04, 0xb7, 0xf4, 0xcb, 0x80, 0xb8, 0xcb, + 0x77, 0x56, 0x3e, 0xaa, 0x57, 0x54, 0xee, 0xb4, + 0x2c, 0x67, 0xcf, 0xf2, 0xdc, 0xbe, 0x55, 0xf9, + 0x43, 0x1f, 0x6e, 0x22, 0x97, 0x67, 0x7f, 0xc4, + 0xef, 0xb1, 0x26, 0x31, 0x1e, 0x27, 0xdf, 0x41, + 0x80, 0x47, 0x6c, 0xe2, 0xfa, 0xa9, 0x8c, 0x2a, + 0xf6, 0xf2, 0xab, 0xf0, 0x15, 0xda, 0x6c, 0xc8, + 0xfe, 0xb5, 0x23, 0xde, 0xa9, 0x05, 0x3f, 0x06, + 0x54, 0x4c, 0xcd, 0xe1, 0xab, 0xfc, 0x0e, 0x62, + 0x33, 0x31, 0x73, 0x2c, 0x76, 0xcb, 0xb4, 0x47, + 0x1e, 0x20, 0xad, 0xd8, 0xf2, 0x31, 0xdd, 0xc4, + 0x8b, 0x0c, 0x77, 0xbe, 0xe1, 0x8b, 0x26, 0x00, + 0x02, 0x58, 0xd6, 0x8d, 0xef, 0xad, 0x74, 0x67, + 0xab, 0x3f, 0xef, 0xcb, 0x6f, 0xb0, 0xcc, 0x81, + 0x44, 0x4c, 0xaf, 0xe9, 0x49, 0x4f, 0xdb, 0xa0, + 0x25, 0xa4, 0xf0, 0x89, 0xf1, 0xbe, 0xd8, 0x10, + 0xff, 0xb1, 0x3b, 0x4b, 0xfa, 0x98, 0xf5, 0x79, + 0x6d, 0x1e, 0x69, 0x4d, 0x57, 0xb1, 0xc8, 0x19, + 0x1b, 0xbd, 0x1e, 0x8c, 0x84, 0xb7, 0x7b, 0xe8, + 0xd2, 0x2d, 0x09, 0x41, 0x41, 0x37, 0x3d, 0xb1, + 0x6f, 0x26, 0x5d, 0x71, 0x16, 0x3d, 0xb7, 0x83, + 0x27, 0x2c, 0xa7, 0xb6, 0x50, 0xbd, 0x91, 0x86, + 0xab, 0x24, 0xa1, 0x38, 0xfd, 0xea, 0x71, 0x55, + 0x7e, 0x9a, 0x07, 0x77, 0x4b, 0xfa, 0x61, 0x66, + 0x20, 0x1e, 0x28, 0x95, 0x18, 0x1b, 0xa4, 0xa0, + 0xfd, 0xc0, 0x89, 0x72, 0x43, 0xd9, 0x3b, 0x49, + 0x5a, 0x3f, 0x9d, 0xbf, 0xdb, 0xb4, 0x46, 0xea, + 0x42, 0x01, 0x77, 0x23, 0x68, 0x95, 0xb6, 0x24, + 0xb3, 0xa8, 0x6c, 0x28, 0x3b, 0x11, 0x40, 0x7e, + 0x18, 0x65, 0x6d, 0xd8, 0x24, 0x42, 0x7d, 0x88, + 0xc0, 0x52, 0xd9, 0x05, 0xe4, 0x95, 0x90, 0x87, + 0x8c, 0xf4, 0xd0, 0x6b, 0xb9, 0x83, 0x99, 0x34, + 0x6d, 0xfe, 0x54, 0x40, 0x94, 0x52, 0x21, 0x4f, + 0x14, 0x25, 0xc5, 0xd6, 0x5e, 0x95, 0xdc, 0x0a, + 0x2b, 0x89, 0x20, 0x11, 0x84, 0x48, 0xd6, 0x3a, + 0xcd, 0x5c, 0x24, 0xad, 0x62, 0xe3, 0xb1, 0x93, + 0x25, 0x8d, 0xcd, 0x7e, 0xfc, 0x27, 0xa3, 0x37, + 0xfd, 0x84, 0xfc, 0x1b, 0xb2, 0xf1, 0x27, 0x38, + 0x5a, 0xb7, 0xfc, 0xf2, 0xfa, 0x95, 0x66, 0xd4, + 0xfb, 0xba, 0xa7, 0xd7, 0xa3, 0x72, 0x69, 0x48, + 0x48, 0x8c, 0xeb, 0x28, 0x89, 0xfe, 0x33, 0x65, + 0x5a, 0x36, 0x01, 0x7e, 0x06, 0x79, 0x0a, 0x09, + 0x3b, 0x74, 0x11, 0x9a, 0x6e, 0xbf, 0xd4, 0x9e, + 0x58, 0x90, 0x49, 0x4f, 0x4d, 0x08, 0xd4, 0xe5, + 0x4a, 0x09, 0x21, 0xef, 0x8b, 0xb8, 0x74, 0x3b, + 0x91, 0xdd, 0x36, 0x85, 0x60, 0x2d, 0xfa, 0xd4, + 0x45, 0x7b, 0x45, 0x53, 0xf5, 0x47, 0x87, 0x7e, + 0xa6, 0x37, 0xc8, 0x78, 0x7a, 0x68, 0x9d, 0x8d, + 0x65, 0x2c, 0x0e, 0x91, 0x5c, 0xa2, 0x60, 0xf0, + 0x8e, 0x3f, 0xe9, 0x1a, 0xcd, 0xaa, 0xe7, 0xd5, + 0x77, 0x18, 0xaf, 0xc9, 0xbc, 0x18, 0xea, 0x48, + 0x1b, 0xfb, 0x22, 0x48, 0x70, 0x16, 0x29, 0x9e, + 0x5b, 0xc1, 0x2c, 0x66, 0x23, 0xbc, 0xf0, 0x1f, + 0xef, 0xaf, 0xe4, 0xd6, 0x04, 0x19, 0x82, 0x7a, + 0x0b, 0xba, 0x4b, 0x46, 0xb1, 0x6a, 0x85, 0x5d, + 0xb4, 0x73, 0xd6, 0x21, 0xa1, 0x71, 0x60, 0x14, + 0xee, 0x0a, 0x77, 0xc4, 0x66, 0x2e, 0xf9, 0x69, + 0x30, 0xaf, 0x41, 0x0b, 0xc8, 0x83, 0x3c, 0x53, + 0x99, 0x19, 0x27, 0x46, 0xf7, 0x41, 0x6e, 0x56, + 0xdc, 0x94, 0x28, 0x67, 0x4e, 0xb7, 0x25, 0x48, + 0x8a, 0xc2, 0xe0, 0x60, 0x96, 0xcc, 0x18, 0xf4, + 0x84, 0xdd, 0xa7, 0x5e, 0x3e, 0x05, 0x0b, 0x26, + 0x26, 0xb2, 0x5c, 0x1f, 0x57, 0x1a, 0x04, 0x7e, + 0x6a, 0xe3, 0x2f, 0xb4, 0x35, 0xb6, 0x38, 0x40, + 0x40, 0xcd, 0x6f, 0x87, 0x2e, 0xef, 0xa3, 0xd7, + 0xa9, 0xc2, 0xe8, 0x0d, 0x27, 0xdf, 0x44, 0x62, + 0x99, 0xa0, 0xfc, 0xcf, 0x81, 0x78, 0xcb, 0xfe, + 0xe5, 0xa0, 0x03, 0x4e, 0x6c, 0xd7, 0xf4, 0xaf, + 0x7a, 0xbb, 0x61, 0x82, 0xfe, 0x71, 0x89, 0xb2, + 0x22, 0x7c, 0x8e, 0x83, 0x04, 0xce, 0xf6, 0x5d, + 0x84, 0x8f, 0x95, 0x6a, 0x7f, 0xad, 0xfd, 0x32, + 0x9c, 0x5e, 0xe4, 0x9c, 0x89, 0x60, 0x54, 0xaa, + 0x96, 0x72, 0xd2, 0xd7, 0x36, 0x85, 0xa9, 0x45, + 0xd2, 0x2a, 0xa1, 0x81, 0x49, 0x6f, 0x7e, 0x04, + 0xfa, 0xe2, 0xfe, 0x90, 0x26, 0x77, 0x5a, 0x33, + 0xb8, 0x04, 0x9a, 0x7a, 0xe6, 0x4c, 0x4f, 0xad, + 0x72, 0x96, 0x08, 0x28, 0x58, 0x13, 0xf8, 0xc4, + 0x1c, 0xf0, 0xc3, 0x45, 0x95, 0x49, 0x20, 0x8c, + 0x9f, 0x39, 0x70, 0xe1, 0x77, 0xfe, 0xd5, 0x4b, + 0xaf, 0x86, 0xda, 0xef, 0x22, 0x06, 0x83, 0x36, + 0x29, 0x12, 0x11, 0x40, 0xbc, 0x3b, 0x86, 0xaa, + 0xaa, 0x65, 0x60, 0xc3, 0x80, 0xca, 0xed, 0xa9, + 0xf3, 0xb0, 0x79, 0x96, 0xa2, 0x55, 0x27, 0x28, + 0x55, 0x73, 0x26, 0xa5, 0x50, 0xea, 0x92, 0x4b, + 0x3c, 0x5c, 0x82, 0x33, 0xf0, 0x01, 0x3f, 0x03, + 0xc1, 0x08, 0x05, 0xbf, 0x98, 0xf4, 0x9b, 0x6d, + 0xa5, 0xa8, 0xb4, 0x82, 0x0c, 0x06, 0xfa, 0xff, + 0x2d, 0x08, 0xf3, 0x05, 0x4f, 0x57, 0x2a, 0x39, + 0xd4, 0x83, 0x0d, 0x75, 0x51, 0xd8, 0x5b, 0x1b, + 0xd3, 0x51, 0x5a, 0x32, 0x2a, 0x9b, 0x32, 0xb2, + 0xf2, 0xa4, 0x96, 0x12, 0xf2, 0xae, 0x40, 0x34, + 0x67, 0xa8, 0xf5, 0x44, 0xd5, 0x35, 0x53, 0xfe, + 0xa3, 0x60, 0x96, 0x63, 0x0f, 0x1f, 0x6e, 0xb0, + 0x5a, 0x42, 0xa6, 0xfc, 0x51, 0x0b, 0x60, 0x27, + 0xbc, 0x06, 0x71, 0xed, 0x65, 0x5b, 0x23, 0x86, + 0x4a, 0x07, 0x3b, 0x22, 0x07, 0x46, 0xe6, 0x90, + 0x3e, 0xf3, 0x25, 0x50, 0x1b, 0x4c, 0x7f, 0x03, + 0x08, 0xa8, 0x36, 0x6b, 0x87, 0xe5, 0xe3, 0xdb, + 0x9a, 0x38, 0x83, 0xff, 0x9f, 0x1a, 0x9f, 0x57, + 0xa4, 0x2a, 0xf6, 0x37, 0xbc, 0x1a, 0xff, 0xc9, + 0x1e, 0x35, 0x0c, 0xc3, 0x7c, 0xa3, 0xb2, 0xe5, + 0xd2, 0xc6, 0xb4, 0x57, 0x47, 0xe4, 0x32, 0x16, + 0x6d, 0xa9, 0xae, 0x64, 0xe6, 0x2d, 0x8d, 0xc5, + 0x8d, 0x50, 0x8e, 0xe8, 0x1a, 0x22, 0x34, 0x2a, + 0xd9, 0xeb, 0x51, 0x90, 0x4a, 0xb1, 0x41, 0x7d, + 0x64, 0xf9, 0xb9, 0x0d, 0xf6, 0x23, 0x33, 0xb0, + 0x33, 0xf4, 0xf7, 0x3f, 0x27, 0x84, 0xc6, 0x0f, + 0x54, 0xa5, 0xc0, 0x2e, 0xec, 0x0b, 0x3a, 0x48, + 0x6e, 0x80, 0x35, 0x81, 0x43, 0x9b, 0x90, 0xb1, + 0xd0, 0x2b, 0xea, 0x21, 0xdc, 0xda, 0x5b, 0x09, + 0xf4, 0xcc, 0x10, 0xb4, 0xc7, 0xfe, 0x79, 0x51, + 0xc3, 0xc5, 0xac, 0x88, 0x74, 0x84, 0x0b, 0x4b, + 0xca, 0x79, 0x16, 0x29, 0xfb, 0x69, 0x54, 0xdf, + 0x41, 0x7e, 0xe9, 0xc7, 0x8e, 0xea, 0xa5, 0xfe, + 0xfc, 0x76, 0x0e, 0x90, 0xc4, 0x92, 0x38, 0xad, + 0x7b, 0x48, 0xe6, 0x6e, 0xf7, 0x21, 0xfd, 0x4e, + 0x93, 0x0a, 0x7b, 0x41, 0x83, 0x68, 0xfb, 0x57, + 0x51, 0x76, 0x34, 0xa9, 0x6c, 0x00, 0xaa, 0x4f, + 0x66, 0x65, 0x98, 0x4a, 0x4f, 0xa3, 0xa0, 0xef, + 0x69, 0x3f, 0xe3, 0x1c, 0x92, 0x8c, 0xfd, 0xd8, + 0xe8, 0xde, 0x7c, 0x7f, 0x3e, 0x84, 0x8e, 0x69, + 0x3c, 0xf1, 0xf2, 0x05, 0x46, 0xdc, 0x2f, 0x9d, + 0x5e, 0x6e, 0x4c, 0xfb, 0xb5, 0x99, 0x2a, 0x59, + 0x63, 0xc1, 0x34, 0xbc, 0x57, 0xc0, 0x0d, 0xb9, + 0x61, 0x25, 0xf3, 0x33, 0x23, 0x51, 0xb6, 0x0d, + 0x07, 0xa6, 0xab, 0x94, 0x4a, 0xb7, 0x2a, 0xea, + 0xee, 0xac, 0xa3, 0xc3, 0x04, 0x8b, 0x0e, 0x56, + 0xfe, 0x44, 0xa7, 0x39, 0xe2, 0xed, 0xed, 0xb4, + 0x22, 0x2b, 0xac, 0x12, 0x32, 0x28, 0x91, 0xd8, + 0xa5, 0xab, 0xff, 0x5f, 0xe0, 0x4b, 0xda, 0x78, + 0x17, 0xda, 0xf1, 0x01, 0x5b, 0xcd, 0xe2, 0x5f, + 0x50, 0x45, 0x73, 0x2b, 0xe4, 0x76, 0x77, 0xf4, + 0x64, 0x1d, 0x43, 0xfb, 0x84, 0x7a, 0xea, 0x91, + 0xae, 0xf9, 0x9e, 0xb7, 0xb4, 0xb0, 0x91, 0x5f, + 0x16, 0x35, 0x9a, 0x11, 0xb8, 0xc7, 0xc1, 0x8c, + 0xc6, 0x10, 0x8d, 0x2f, 0x63, 0x4a, 0xa7, 0x57, + 0x3a, 0x51, 0xd6, 0x32, 0x2d, 0x64, 0x72, 0xd4, + 0x66, 0xdc, 0x10, 0xa6, 0x67, 0xd6, 0x04, 0x23, + 0x9d, 0x0a, 0x11, 0x77, 0xdd, 0x37, 0x94, 0x17, + 0x3c, 0xbf, 0x8b, 0x65, 0xb0, 0x2e, 0x5e, 0x66, + 0x47, 0x64, 0xac, 0xdd, 0xf0, 0x84, 0xfd, 0x39, + 0xfa, 0x15, 0x5d, 0xef, 0xae, 0xca, 0xc1, 0x36, + 0xa7, 0x5c, 0xbf, 0xc7, 0x08, 0xc2, 0x66, 0x00, + 0x74, 0x74, 0x4e, 0x27, 0x3f, 0x55, 0x8a, 0xb7, + 0x38, 0x66, 0x83, 0x6d, 0xcf, 0x99, 0x9e, 0x60, + 0x8f, 0xdd, 0x2e, 0x62, 0x22, 0x0e, 0xef, 0x0c, + 0x98, 0xa7, 0x85, 0x74, 0x3b, 0x9d, 0xec, 0x9e, + 0xa9, 0x19, 0x72, 0xa5, 0x7f, 0x2c, 0x39, 0xb7, + 0x7d, 0xb7, 0xf1, 0x12, 0x65, 0x27, 0x4b, 0x5a, + 0xde, 0x17, 0xfe, 0xad, 0x44, 0xf3, 0x20, 0x4d, + 0xfd, 0xe4, 0x1f, 0xb5, 0x81, 0xb0, 0x36, 0x37, + 0x08, 0x6f, 0xc3, 0x0c, 0xe9, 0x85, 0x98, 0x82, + 0xa9, 0x62, 0x0c, 0xc4, 0x97, 0xc0, 0x50, 0xc8, + 0xa7, 0x3c, 0x50, 0x9f, 0x43, 0xb9, 0xcd, 0x5e, + 0x4d, 0xfa, 0x1c, 0x4b, 0x0b, 0xa9, 0x98, 0x85, + 0x38, 0x92, 0xac, 0x8d, 0xe4, 0xad, 0x9b, 0x98, + 0xab, 0xd9, 0x38, 0xac, 0x62, 0x52, 0xa3, 0x22, + 0x63, 0x0f, 0xbf, 0x95, 0x48, 0xdf, 0x69, 0xe7, + 0x8b, 0x33, 0xd5, 0xb2, 0xbd, 0x05, 0x49, 0x49, + 0x9d, 0x57, 0x73, 0x19, 0x33, 0xae, 0xfa, 0x33, + 0xf1, 0x19, 0xa8, 0x80, 0xce, 0x04, 0x9f, 0xbc, + 0x1d, 0x65, 0x82, 0x1b, 0xe5, 0x3a, 0x51, 0xc8, + 0x1c, 0x21, 0xe3, 0x5d, 0xf3, 0x7d, 0x9b, 0x2f, + 0x2c, 0x1d, 0x4a, 0x7f, 0x9b, 0x68, 0x35, 0xa3, + 0xb2, 0x50, 0xf7, 0x62, 0x79, 0xcd, 0xf4, 0x98, + 0x4f, 0xe5, 0x63, 0x7c, 0x3e, 0x45, 0x31, 0x8c, + 0x16, 0xa0, 0x12, 0xc8, 0x58, 0xce, 0x39, 0xa6, + 0xbc, 0x54, 0xdb, 0xc5, 0xe0, 0xd5, 0xba, 0xbc, + 0xb9, 0x04, 0xf4, 0x8d, 0xe8, 0x2f, 0x15, 0x9d, +}; -#if 0 /*Not used at present */ -static void -buf_dump(char const *prefix, unsigned char const *buf, size_t len) +/* 100 test cases */ +static struct crc_test { + u32 crc; /* random starting crc */ + u32 start; /* random 6 bit offset in buf */ + u32 length; /* random 11 bit length of test */ + u32 crc_le; /* expected crc32_le result */ + u32 crc_be; /* expected crc32_be result */ + u32 crc32c_le; /* expected crc32c_le result */ +} test[] = { - fputs(prefix, stdout); - while (len--) - printf(" %02x", *buf++); - putchar('\n'); + {0x674bf11d, 0x00000038, 0x00000542, 0x0af6d466, 0xd8b6e4c1, + 0xf6e93d6c}, + {0x35c672c6, 0x0000003a, 0x000001aa, 0xc6d3dfba, 0x28aaf3ad, + 0x0fe92aca}, + {0x496da28e, 0x00000039, 0x000005af, 0xd933660f, 0x5d57e81f, + 0x52e1ebb8}, + {0x09a9b90e, 0x00000027, 0x000001f8, 0xb45fe007, 0xf45fca9a, + 0x0798af9a}, + {0xdc97e5a9, 0x00000025, 0x000003b6, 0xf81a3562, 0xe0126ba2, + 0x18eb3152}, + {0x47c58900, 0x0000000a, 0x000000b9, 0x8e58eccf, 0xf3afc793, + 0xd00d08c7}, + {0x292561e8, 0x0000000c, 0x00000403, 0xa2ba8aaf, 0x0b797aed, + 0x8ba966bc}, + {0x415037f6, 0x00000003, 0x00000676, 0xa17d52e8, 0x7f0fdf35, + 0x11d694a2}, + {0x3466e707, 0x00000026, 0x00000042, 0x258319be, 0x75c484a2, + 0x6ab3208d}, + {0xafd1281b, 0x00000023, 0x000002ee, 0x4428eaf8, 0x06c7ad10, + 0xba4603c5}, + {0xd3857b18, 0x00000028, 0x000004a2, 0x5c430821, 0xb062b7cb, + 0xe6071c6f}, + {0x1d825a8f, 0x0000002b, 0x0000050b, 0xd2c45f0c, 0xd68634e0, + 0x179ec30a}, + {0x5033e3bc, 0x0000000b, 0x00000078, 0xa3ea4113, 0xac6d31fb, + 0x0903beb8}, + {0x94f1fb5e, 0x0000000f, 0x000003a2, 0xfbfc50b1, 0x3cfe50ed, + 0x6a7cb4fa}, + {0xc9a0fe14, 0x00000009, 0x00000473, 0x5fb61894, 0x87070591, + 0xdb535801}, + {0x88a034b1, 0x0000001c, 0x000005ad, 0xc1b16053, 0x46f95c67, + 0x92bed597}, + {0xf0f72239, 0x00000020, 0x0000026d, 0xa6fa58f3, 0xf8c2c1dd, + 0x192a3f1b}, + {0xcc20a5e3, 0x0000003b, 0x0000067a, 0x7740185a, 0x308b979a, + 0xccbaec1a}, + {0xce589c95, 0x0000002b, 0x00000641, 0xd055e987, 0x40aae25b, + 0x7eabae4d}, + {0x78edc885, 0x00000035, 0x000005be, 0xa39cb14b, 0x035b0d1f, + 0x28c72982}, + {0x9d40a377, 0x0000003b, 0x00000038, 0x1f47ccd2, 0x197fbc9d, + 0xc3cd4d18}, + {0x703d0e01, 0x0000003c, 0x000006f1, 0x88735e7c, 0xfed57c5a, + 0xbca8f0e7}, + {0x776bf505, 0x0000000f, 0x000005b2, 0x5cc4fc01, 0xf32efb97, + 0x713f60b3}, + {0x4a3e7854, 0x00000027, 0x000004b8, 0x8d923c82, 0x0cbfb4a2, + 0xebd08fd5}, + {0x209172dd, 0x0000003b, 0x00000356, 0xb89e9c2b, 0xd7868138, + 0x64406c59}, + {0x3ba4cc5b, 0x0000002f, 0x00000203, 0xe51601a9, 0x5b2a1032, + 0x7421890e}, + {0xfc62f297, 0x00000000, 0x00000079, 0x71a8e1a2, 0x5d88685f, + 0xe9347603}, + {0x64280b8b, 0x00000016, 0x000007ab, 0x0fa7a30c, 0xda3a455f, + 0x1bef9060}, + {0x97dd724b, 0x00000033, 0x000007ad, 0x5788b2f4, 0xd7326d32, + 0x34720072}, + {0x61394b52, 0x00000035, 0x00000571, 0xc66525f1, 0xcabe7fef, + 0x48310f59}, + {0x29b4faff, 0x00000024, 0x0000006e, 0xca13751e, 0x993648e0, + 0x783a4213}, + {0x29bfb1dc, 0x0000000b, 0x00000244, 0x436c43f7, 0x429f7a59, + 0x9e8efd41}, + {0x86ae934b, 0x00000035, 0x00000104, 0x0760ec93, 0x9cf7d0f4, + 0xfc3d34a5}, + {0xc4c1024e, 0x0000002e, 0x000006b1, 0x6516a3ec, 0x19321f9c, + 0x17a52ae2}, + {0x3287a80a, 0x00000026, 0x00000496, 0x0b257eb1, 0x754ebd51, + 0x886d935a}, + {0xa4db423e, 0x00000023, 0x0000045d, 0x9b3a66dc, 0x873e9f11, + 0xeaaeaeb2}, + {0x7a1078df, 0x00000015, 0x0000014a, 0x8c2484c5, 0x6a628659, + 0x8e900a4b}, + {0x6048bd5b, 0x00000006, 0x0000006a, 0x897e3559, 0xac9961af, + 0xd74662b1}, + {0xd8f9ea20, 0x0000003d, 0x00000277, 0x60eb905b, 0xed2aaf99, + 0xd26752ba}, + {0xea5ec3b4, 0x0000002a, 0x000004fe, 0x869965dc, 0x6c1f833b, + 0x8b1fcd62}, + {0x2dfb005d, 0x00000016, 0x00000345, 0x6a3b117e, 0xf05e8521, + 0xf54342fe}, + {0x5a214ade, 0x00000020, 0x000005b6, 0x467f70be, 0xcb22ccd3, + 0x5b95b988}, + {0xf0ab9cca, 0x00000032, 0x00000515, 0xed223df3, 0x7f3ef01d, + 0x2e1176be}, + {0x91b444f9, 0x0000002e, 0x000007f8, 0x84e9a983, 0x5676756f, + 0x66120546}, + {0x1b5d2ddb, 0x0000002e, 0x0000012c, 0xba638c4c, 0x3f42047b, + 0xf256a5cc}, + {0xd824d1bb, 0x0000003a, 0x000007b5, 0x6288653b, 0x3a3ebea0, + 0x4af1dd69}, + {0x0470180c, 0x00000034, 0x000001f0, 0x9d5b80d6, 0x3de08195, + 0x56f0a04a}, + {0xffaa3a3f, 0x00000036, 0x00000299, 0xf3a82ab8, 0x53e0c13d, + 0x74f6b6b2}, + {0x6406cfeb, 0x00000023, 0x00000600, 0xa920b8e8, 0xe4e2acf4, + 0x085951fd}, + {0xb24aaa38, 0x0000003e, 0x000004a1, 0x657cc328, 0x5077b2c3, + 0xc65387eb}, + {0x58b2ab7c, 0x00000039, 0x000002b4, 0x3a17ee7e, 0x9dcb3643, + 0x1ca9257b}, + {0x3db85970, 0x00000006, 0x000002b6, 0x95268b59, 0xb9812c10, + 0xfd196d76}, + {0x857830c5, 0x00000003, 0x00000590, 0x4ef439d5, 0xf042161d, + 0x5ef88339}, + {0xe1fcd978, 0x0000003e, 0x000007d8, 0xae8d8699, 0xce0a1ef5, + 0x2c3714d9}, + {0xb982a768, 0x00000016, 0x000006e0, 0x62fad3df, 0x5f8a067b, + 0x58576548}, + {0x1d581ce8, 0x0000001e, 0x0000058b, 0xf0f5da53, 0x26e39eee, + 0xfd7c57de}, + {0x2456719b, 0x00000025, 0x00000503, 0x4296ac64, 0xd50e4c14, + 0xd5fedd59}, + {0xfae6d8f2, 0x00000000, 0x0000055d, 0x057fdf2e, 0x2a31391a, + 0x1cc3b17b}, + {0xcba828e3, 0x00000039, 0x000002ce, 0xe3f22351, 0x8f00877b, + 0x270eed73}, + {0x13d25952, 0x0000000a, 0x0000072d, 0x76d4b4cc, 0x5eb67ec3, + 0x91ecbb11}, + {0x0342be3f, 0x00000015, 0x00000599, 0xec75d9f1, 0x9d4d2826, + 0x05ed8d0c}, + {0xeaa344e0, 0x00000014, 0x000004d8, 0x72a4c981, 0x2064ea06, + 0x0b09ad5b}, + {0xbbb52021, 0x0000003b, 0x00000272, 0x04af99fc, 0xaf042d35, + 0xf8d511fb}, + {0xb66384dc, 0x0000001d, 0x000007fc, 0xd7629116, 0x782bd801, + 0x5ad832cc}, + {0x616c01b6, 0x00000022, 0x000002c8, 0x5b1dab30, 0x783ce7d2, + 0x1214d196}, + {0xce2bdaad, 0x00000016, 0x0000062a, 0x932535c8, 0x3f02926d, + 0x5747218a}, + {0x00fe84d7, 0x00000005, 0x00000205, 0x850e50aa, 0x753d649c, + 0xde8f14de}, + {0xbebdcb4c, 0x00000006, 0x0000055d, 0xbeaa37a2, 0x2d8c9eba, + 0x3563b7b9}, + {0xd8b1a02a, 0x00000010, 0x00000387, 0x5017d2fc, 0x503541a5, + 0x071475d0}, + {0x3b96cad2, 0x00000036, 0x00000347, 0x1d2372ae, 0x926cd90b, + 0x54c79d60}, + {0xc94c1ed7, 0x00000005, 0x0000038b, 0x9e9fdb22, 0x144a9178, + 0x4c53eee6}, + {0x1aad454e, 0x00000025, 0x000002b2, 0xc3f6315c, 0x5c7a35b3, + 0x10137a3c}, + {0xa4fec9a6, 0x00000000, 0x000006d6, 0x90be5080, 0xa4107605, + 0xaa9d6c73}, + {0x1bbe71e2, 0x0000001f, 0x000002fd, 0x4e504c3b, 0x284ccaf1, + 0xb63d23e7}, + {0x4201c7e4, 0x00000002, 0x000002b7, 0x7822e3f9, 0x0cc912a9, + 0x7f53e9cf}, + {0x23fddc96, 0x00000003, 0x00000627, 0x8a385125, 0x07767e78, + 0x13c1cd83}, + {0xd82ba25c, 0x00000016, 0x0000063e, 0x98e4148a, 0x283330c9, + 0x49ff5867}, + {0x786f2032, 0x0000002d, 0x0000060f, 0xf201600a, 0xf561bfcd, + 0x8467f211}, + {0xfebe4e1f, 0x0000002a, 0x000004f2, 0x95e51961, 0xfd80dcab, + 0x3f9683b2}, + {0x1a6e0a39, 0x00000008, 0x00000672, 0x8af6c2a5, 0x78dd84cb, + 0x76a3f874}, + {0x56000ab8, 0x0000000e, 0x000000e5, 0x36bacb8f, 0x22ee1f77, + 0x863b702f}, + {0x4717fe0c, 0x00000000, 0x000006ec, 0x8439f342, 0x5c8e03da, + 0xdc6c58ff}, + {0xd5d5d68e, 0x0000003c, 0x000003a3, 0x46fff083, 0x177d1b39, + 0x0622cc95}, + {0xc25dd6c6, 0x00000024, 0x000006c0, 0x5ceb8eb4, 0x892b0d16, + 0xe85605cd}, + {0xe9b11300, 0x00000023, 0x00000683, 0x07a5d59a, 0x6c6a3208, + 0x31da5f06}, + {0x95cd285e, 0x00000001, 0x00000047, 0x7b3a4368, 0x0202c07e, + 0xa1f2e784}, + {0xd9245a25, 0x0000001e, 0x000003a6, 0xd33c1841, 0x1936c0d5, + 0xb07cc616}, + {0x103279db, 0x00000006, 0x0000039b, 0xca09b8a0, 0x77d62892, + 0xbf943b6c}, + {0x1cba3172, 0x00000027, 0x000001c8, 0xcb377194, 0xebe682db, + 0x2c01af1c}, + {0x8f613739, 0x0000000c, 0x000001df, 0xb4b0bc87, 0x7710bd43, + 0x0fe5f56d}, + {0x1c6aa90d, 0x0000001b, 0x0000053c, 0x70559245, 0xda7894ac, + 0xf8943b2d}, + {0xaabe5b93, 0x0000003d, 0x00000715, 0xcdbf42fa, 0x0c3b99e7, + 0xe4d89272}, + {0xf15dd038, 0x00000006, 0x000006db, 0x6e104aea, 0x8d5967f2, + 0x7c2f6bbb}, + {0x584dd49c, 0x00000020, 0x000007bc, 0x36b6cfd6, 0xad4e23b2, + 0xabbf388b}, + {0x5d8c9506, 0x00000020, 0x00000470, 0x4c62378e, 0x31d92640, + 0x1dca1f4e}, + {0xb80d17b0, 0x00000032, 0x00000346, 0x22a5bb88, 0x9a7ec89f, + 0x5c170e23}, + {0xdaf0592e, 0x00000023, 0x000007b0, 0x3cab3f99, 0x9b1fdd99, + 0xc0e9d672}, + {0x4793cc85, 0x0000000d, 0x00000706, 0xe82e04f6, 0xed3db6b7, + 0xc18bdc86}, + {0x82ebf64e, 0x00000009, 0x000007c3, 0x69d590a9, 0x9efa8499, + 0xa874fcdd}, + {0xb18a0319, 0x00000026, 0x000007db, 0x1cf98dcc, 0x8fa9ad6a, + 0x9dc0bb48}, +}; -} -#endif +#include <linux/time.h> -static void bytereverse(unsigned char *buf, size_t len) +static int __init crc32c_test(void) { - while (len--) { - unsigned char x = bitrev8(*buf); - *buf++ = x; + int i; + int errors = 0; + int bytes = 0; + struct timespec start, stop; + u64 nsec; + unsigned long flags; + + /* keep static to prevent cache warming code from + * getting eliminated by the compiler */ + static u32 crc; + + /* pre-warm the cache */ + for (i = 0; i < 100; i++) { + bytes += 2*test[i].length; + + crc ^= __crc32c_le(test[i].crc, test_buf + + test[i].start, test[i].length); } -} -static void random_garbage(unsigned char *buf, size_t len) -{ - while (len--) - *buf++ = (unsigned char) random(); -} + /* reduce OS noise */ + local_irq_save(flags); + local_irq_disable(); -#if 0 /* Not used at present */ -static void store_le(u32 x, unsigned char *buf) -{ - buf[0] = (unsigned char) x; - buf[1] = (unsigned char) (x >> 8); - buf[2] = (unsigned char) (x >> 16); - buf[3] = (unsigned char) (x >> 24); -} -#endif + getnstimeofday(&start); + for (i = 0; i < 100; i++) { + if (test[i].crc32c_le != __crc32c_le(test[i].crc, test_buf + + test[i].start, test[i].length)) + errors++; + } + getnstimeofday(&stop); -static void store_be(u32 x, unsigned char *buf) -{ - buf[0] = (unsigned char) (x >> 24); - buf[1] = (unsigned char) (x >> 16); - buf[2] = (unsigned char) (x >> 8); - buf[3] = (unsigned char) x; + local_irq_restore(flags); + local_irq_enable(); + + nsec = stop.tv_nsec - start.tv_nsec + + 1000000000 * (stop.tv_sec - start.tv_sec); + + pr_info("crc32c: CRC_LE_BITS = %d\n", CRC_LE_BITS); + + if (errors) + pr_warn("crc32c: %d self tests failed\n", errors); + else { + pr_info("crc32c: self tests passed, processed %d bytes in %lld nsec\n", + bytes, nsec); + } + + return 0; } -/* - * This checks that CRC(buf + CRC(buf)) = 0, and that - * CRC commutes with bit-reversal. This has the side effect - * of bytewise bit-reversing the input buffer, and returns - * the CRC of the reversed buffer. - */ -static u32 test_step(u32 init, unsigned char *buf, size_t len) +static int __init crc32_test(void) { - u32 crc1, crc2; - size_t i; + int i; + int errors = 0; + int bytes = 0; + struct timespec start, stop; + u64 nsec; + unsigned long flags; + + /* keep static to prevent cache warming code from + * getting eliminated by the compiler */ + static u32 crc; + + /* pre-warm the cache */ + for (i = 0; i < 100; i++) { + bytes += 2*test[i].length; - crc1 = crc32_be(init, buf, len); - store_be(crc1, buf + len); - crc2 = crc32_be(init, buf, len + 4); - if (crc2) - printf("\nCRC cancellation fail: 0x%08x should be 0\n", - crc2); - - for (i = 0; i <= len + 4; i++) { - crc2 = crc32_be(init, buf, i); - crc2 = crc32_be(crc2, buf + i, len + 4 - i); - if (crc2) - printf("\nCRC split fail: 0x%08x\n", crc2); + crc ^= crc32_le(test[i].crc, test_buf + + test[i].start, test[i].length); + + crc ^= crc32_be(test[i].crc, test_buf + + test[i].start, test[i].length); } - /* Now swap it around for the other test */ - - bytereverse(buf, len + 4); - init = bitrev32(init); - crc2 = bitrev32(crc1); - if (crc1 != bitrev32(crc2)) - printf("\nBit reversal fail: 0x%08x -> 0x%08x -> 0x%08x\n", - crc1, crc2, bitrev32(crc2)); - crc1 = crc32_le(init, buf, len); - if (crc1 != crc2) - printf("\nCRC endianness fail: 0x%08x != 0x%08x\n", crc1, - crc2); - crc2 = crc32_le(init, buf, len + 4); - if (crc2) - printf("\nCRC cancellation fail: 0x%08x should be 0\n", - crc2); - - for (i = 0; i <= len + 4; i++) { - crc2 = crc32_le(init, buf, i); - crc2 = crc32_le(crc2, buf + i, len + 4 - i); - if (crc2) - printf("\nCRC split fail: 0x%08x\n", crc2); + /* reduce OS noise */ + local_irq_save(flags); + local_irq_disable(); + + getnstimeofday(&start); + for (i = 0; i < 100; i++) { + if (test[i].crc_le != crc32_le(test[i].crc, test_buf + + test[i].start, test[i].length)) + errors++; + + if (test[i].crc_be != crc32_be(test[i].crc, test_buf + + test[i].start, test[i].length)) + errors++; } + getnstimeofday(&stop); - return crc1; -} + local_irq_restore(flags); + local_irq_enable(); -#define SIZE 64 -#define INIT1 0 -#define INIT2 0 + nsec = stop.tv_nsec - start.tv_nsec + + 1000000000 * (stop.tv_sec - start.tv_sec); -int main(void) -{ - unsigned char buf1[SIZE + 4]; - unsigned char buf2[SIZE + 4]; - unsigned char buf3[SIZE + 4]; - int i, j; - u32 crc1, crc2, crc3; - - for (i = 0; i <= SIZE; i++) { - printf("\rTesting length %d...", i); - fflush(stdout); - random_garbage(buf1, i); - random_garbage(buf2, i); - for (j = 0; j < i; j++) - buf3[j] = buf1[j] ^ buf2[j]; - - crc1 = test_step(INIT1, buf1, i); - crc2 = test_step(INIT2, buf2, i); - /* Now check that CRC(buf1 ^ buf2) = CRC(buf1) ^ CRC(buf2) */ - crc3 = test_step(INIT1 ^ INIT2, buf3, i); - if (crc3 != (crc1 ^ crc2)) - printf("CRC XOR fail: 0x%08x != 0x%08x ^ 0x%08x\n", - crc3, crc1, crc2); + pr_info("crc32: CRC_LE_BITS = %d, CRC_BE BITS = %d\n", + CRC_LE_BITS, CRC_BE_BITS); + + if (errors) + pr_warn("crc32: %d self tests failed\n", errors); + else { + pr_info("crc32: self tests passed, processed %d bytes in %lld nsec\n", + bytes, nsec); } - printf("\nAll test complete. No failures expected.\n"); + return 0; } -#endif /* UNITTEST */ +static int __init crc32test_init(void) +{ + crc32_test(); + crc32c_test(); + return 0; +} + +static void __exit crc32_exit(void) +{ +} + +module_init(crc32test_init); +module_exit(crc32_exit); +#endif /* CONFIG_CRC32_SELFTEST */ diff --git a/lib/crc32defs.h b/lib/crc32defs.h index 9b6773d7374..64cba2c3c70 100644 --- a/lib/crc32defs.h +++ b/lib/crc32defs.h @@ -6,27 +6,67 @@ #define CRCPOLY_LE 0xedb88320 #define CRCPOLY_BE 0x04c11db7 -/* How many bits at a time to use. Requires a table of 4<<CRC_xx_BITS bytes. */ -/* For less performance-sensitive, use 4 */ -#ifndef CRC_LE_BITS +/* + * This is the CRC32c polynomial, as outlined by Castagnoli. + * x^32+x^28+x^27+x^26+x^25+x^23+x^22+x^20+x^19+x^18+x^14+x^13+x^11+x^10+x^9+ + * x^8+x^6+x^0 + */ +#define CRC32C_POLY_LE 0x82F63B78 + +/* Try to choose an implementation variant via Kconfig */ +#ifdef CONFIG_CRC32_SLICEBY8 +# define CRC_LE_BITS 64 +# define CRC_BE_BITS 64 +#endif +#ifdef CONFIG_CRC32_SLICEBY4 +# define CRC_LE_BITS 32 +# define CRC_BE_BITS 32 +#endif +#ifdef CONFIG_CRC32_SARWATE # define CRC_LE_BITS 8 +# define CRC_BE_BITS 8 +#endif +#ifdef CONFIG_CRC32_BIT +# define CRC_LE_BITS 1 +# define CRC_BE_BITS 1 +#endif + +/* + * How many bits at a time to use. Valid values are 1, 2, 4, 8, 32 and 64. + * For less performance-sensitive, use 4 or 8 to save table size. + * For larger systems choose same as CPU architecture as default. + * This works well on X86_64, SPARC64 systems. This may require some + * elaboration after experiments with other architectures. + */ +#ifndef CRC_LE_BITS +# ifdef CONFIG_64BIT +# define CRC_LE_BITS 64 +# else +# define CRC_LE_BITS 32 +# endif #endif #ifndef CRC_BE_BITS -# define CRC_BE_BITS 8 +# ifdef CONFIG_64BIT +# define CRC_BE_BITS 64 +# else +# define CRC_BE_BITS 32 +# endif #endif /* * Little-endian CRC computation. Used with serial bit streams sent * lsbit-first. Be sure to use cpu_to_le32() to append the computed CRC. */ -#if CRC_LE_BITS > 8 || CRC_LE_BITS < 1 || CRC_LE_BITS & CRC_LE_BITS-1 -# error CRC_LE_BITS must be a power of 2 between 1 and 8 +#if CRC_LE_BITS > 64 || CRC_LE_BITS < 1 || CRC_LE_BITS == 16 || \ + CRC_LE_BITS & CRC_LE_BITS-1 +# error "CRC_LE_BITS must be one of {1, 2, 4, 8, 32, 64}" #endif /* * Big-endian CRC computation. Used with serial bit streams sent * msbit-first. Be sure to use cpu_to_be32() to append the computed CRC. */ -#if CRC_BE_BITS > 8 || CRC_BE_BITS < 1 || CRC_BE_BITS & CRC_BE_BITS-1 -# error CRC_BE_BITS must be a power of 2 between 1 and 8 +#if CRC_BE_BITS > 64 || CRC_BE_BITS < 1 || CRC_BE_BITS == 16 || \ + CRC_BE_BITS & CRC_BE_BITS-1 +# error "CRC_BE_BITS must be one of {1, 2, 4, 8, 32, 64}" #endif diff --git a/lib/ctype.c b/lib/ctype.c index 26baa620e95..c646df91a2f 100644 --- a/lib/ctype.c +++ b/lib/ctype.c @@ -5,7 +5,8 @@ */ #include <linux/ctype.h> -#include <linux/module.h> +#include <linux/compiler.h> +#include <linux/export.h> const unsigned char _ctype[] = { _C,_C,_C,_C,_C,_C,_C,_C, /* 0-7 */ diff --git a/lib/debug_locks.c b/lib/debug_locks.c index b1c17730767..f2fa60c5934 100644 --- a/lib/debug_locks.c +++ b/lib/debug_locks.c @@ -10,7 +10,7 @@ */ #include <linux/rwsem.h> #include <linux/mutex.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/spinlock.h> #include <linux/debug_locks.h> diff --git a/lib/dec_and_lock.c b/lib/dec_and_lock.c index b5257725daa..e26278576b3 100644 --- a/lib/dec_and_lock.c +++ b/lib/dec_and_lock.c @@ -1,4 +1,4 @@ -#include <linux/module.h> +#include <linux/export.h> #include <linux/spinlock.h> #include <linux/atomic.h> diff --git a/lib/devres.c b/lib/devres.c index 9676617b448..80b9c76d436 100644 --- a/lib/devres.c +++ b/lib/devres.c @@ -1,7 +1,7 @@ #include <linux/pci.h> #include <linux/io.h> #include <linux/gfp.h> -#include <linux/module.h> +#include <linux/export.h> void devm_ioremap_release(struct device *dev, void *res) { diff --git a/lib/div64.c b/lib/div64.c index 5b491919177..3ea24907d52 100644 --- a/lib/div64.c +++ b/lib/div64.c @@ -16,7 +16,8 @@ * assembly versions such as arch/ppc/lib/div64.S and arch/sh/lib/div64.S. */ -#include <linux/module.h> +#include <linux/export.h> +#include <linux/kernel.h> #include <linux/math64.h> /* Not needed on 64bit architectures */ diff --git a/lib/dump_stack.c b/lib/dump_stack.c index 53bff4c8452..42f4f55c945 100644 --- a/lib/dump_stack.c +++ b/lib/dump_stack.c @@ -4,7 +4,7 @@ */ #include <linux/kernel.h> -#include <linux/module.h> +#include <linux/export.h> void dump_stack(void) { diff --git a/lib/fault-inject.c b/lib/fault-inject.c index b4801f51b60..6805453c18e 100644 --- a/lib/fault-inject.c +++ b/lib/fault-inject.c @@ -5,7 +5,7 @@ #include <linux/stat.h> #include <linux/types.h> #include <linux/fs.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/interrupt.h> #include <linux/stacktrace.h> #include <linux/fault-inject.h> diff --git a/lib/find_last_bit.c b/lib/find_last_bit.c index d903959ad69..91ca09fbf6f 100644 --- a/lib/find_last_bit.c +++ b/lib/find_last_bit.c @@ -11,7 +11,7 @@ */ #include <linux/bitops.h> -#include <linux/module.h> +#include <linux/export.h> #include <asm/types.h> #include <asm/byteorder.h> diff --git a/lib/find_next_bit.c b/lib/find_next_bit.c index 4bd75a73ba0..0cbfc0b4398 100644 --- a/lib/find_next_bit.c +++ b/lib/find_next_bit.c @@ -10,7 +10,7 @@ */ #include <linux/bitops.h> -#include <linux/module.h> +#include <linux/export.h> #include <asm/types.h> #include <asm/byteorder.h> diff --git a/lib/flex_array.c b/lib/flex_array.c index 9b8b89458c4..6948a6692fc 100644 --- a/lib/flex_array.c +++ b/lib/flex_array.c @@ -23,7 +23,7 @@ #include <linux/flex_array.h> #include <linux/slab.h> #include <linux/stddef.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/reciprocal_div.h> struct flex_array_part { diff --git a/lib/gcd.c b/lib/gcd.c index f879033d982..cce4f3cd14b 100644 --- a/lib/gcd.c +++ b/lib/gcd.c @@ -1,6 +1,6 @@ #include <linux/kernel.h> #include <linux/gcd.h> -#include <linux/module.h> +#include <linux/export.h> /* Greatest common divisor */ unsigned long gcd(unsigned long a, unsigned long b) diff --git a/lib/gen_crc32table.c b/lib/gen_crc32table.c index 85d0e412a04..8f8d5439e2d 100644 --- a/lib/gen_crc32table.c +++ b/lib/gen_crc32table.c @@ -1,14 +1,29 @@ #include <stdio.h> +#include "../include/generated/autoconf.h" #include "crc32defs.h" #include <inttypes.h> #define ENTRIES_PER_LINE 4 -#define LE_TABLE_SIZE (1 << CRC_LE_BITS) -#define BE_TABLE_SIZE (1 << CRC_BE_BITS) +#if CRC_LE_BITS > 8 +# define LE_TABLE_ROWS (CRC_LE_BITS/8) +# define LE_TABLE_SIZE 256 +#else +# define LE_TABLE_ROWS 1 +# define LE_TABLE_SIZE (1 << CRC_LE_BITS) +#endif -static uint32_t crc32table_le[4][LE_TABLE_SIZE]; -static uint32_t crc32table_be[4][BE_TABLE_SIZE]; +#if CRC_BE_BITS > 8 +# define BE_TABLE_ROWS (CRC_BE_BITS/8) +# define BE_TABLE_SIZE 256 +#else +# define BE_TABLE_ROWS 1 +# define BE_TABLE_SIZE (1 << CRC_BE_BITS) +#endif + +static uint32_t crc32table_le[LE_TABLE_ROWS][256]; +static uint32_t crc32table_be[BE_TABLE_ROWS][256]; +static uint32_t crc32ctable_le[LE_TABLE_ROWS][256]; /** * crc32init_le() - allocate and initialize LE table data @@ -17,27 +32,38 @@ static uint32_t crc32table_be[4][BE_TABLE_SIZE]; * fact that crctable[i^j] = crctable[i] ^ crctable[j]. * */ -static void crc32init_le(void) +static void crc32init_le_generic(const uint32_t polynomial, + uint32_t (*tab)[256]) { unsigned i, j; uint32_t crc = 1; - crc32table_le[0][0] = 0; + tab[0][0] = 0; - for (i = 1 << (CRC_LE_BITS - 1); i; i >>= 1) { - crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0); + for (i = LE_TABLE_SIZE >> 1; i; i >>= 1) { + crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0); for (j = 0; j < LE_TABLE_SIZE; j += 2 * i) - crc32table_le[0][i + j] = crc ^ crc32table_le[0][j]; + tab[0][i + j] = crc ^ tab[0][j]; } for (i = 0; i < LE_TABLE_SIZE; i++) { - crc = crc32table_le[0][i]; - for (j = 1; j < 4; j++) { - crc = crc32table_le[0][crc & 0xff] ^ (crc >> 8); - crc32table_le[j][i] = crc; + crc = tab[0][i]; + for (j = 1; j < LE_TABLE_ROWS; j++) { + crc = tab[0][crc & 0xff] ^ (crc >> 8); + tab[j][i] = crc; } } } +static void crc32init_le(void) +{ + crc32init_le_generic(CRCPOLY_LE, crc32table_le); +} + +static void crc32cinit_le(void) +{ + crc32init_le_generic(CRC32C_POLY_LE, crc32ctable_le); +} + /** * crc32init_be() - allocate and initialize BE table data */ @@ -55,18 +81,18 @@ static void crc32init_be(void) } for (i = 0; i < BE_TABLE_SIZE; i++) { crc = crc32table_be[0][i]; - for (j = 1; j < 4; j++) { + for (j = 1; j < BE_TABLE_ROWS; j++) { crc = crc32table_be[0][(crc >> 24) & 0xff] ^ (crc << 8); crc32table_be[j][i] = crc; } } } -static void output_table(uint32_t table[4][256], int len, char *trans) +static void output_table(uint32_t (*table)[256], int rows, int len, char *trans) { int i, j; - for (j = 0 ; j < 4; j++) { + for (j = 0 ; j < rows; j++) { printf("{"); for (i = 0; i < len - 1; i++) { if (i % ENTRIES_PER_LINE == 0) @@ -83,15 +109,30 @@ int main(int argc, char** argv) if (CRC_LE_BITS > 1) { crc32init_le(); - printf("static const u32 crc32table_le[4][256] = {"); - output_table(crc32table_le, LE_TABLE_SIZE, "tole"); + printf("static const u32 __cacheline_aligned " + "crc32table_le[%d][%d] = {", + LE_TABLE_ROWS, LE_TABLE_SIZE); + output_table(crc32table_le, LE_TABLE_ROWS, + LE_TABLE_SIZE, "tole"); printf("};\n"); } if (CRC_BE_BITS > 1) { crc32init_be(); - printf("static const u32 crc32table_be[4][256] = {"); - output_table(crc32table_be, BE_TABLE_SIZE, "tobe"); + printf("static const u32 __cacheline_aligned " + "crc32table_be[%d][%d] = {", + BE_TABLE_ROWS, BE_TABLE_SIZE); + output_table(crc32table_be, LE_TABLE_ROWS, + BE_TABLE_SIZE, "tobe"); + printf("};\n"); + } + if (CRC_LE_BITS > 1) { + crc32cinit_le(); + printf("static const u32 __cacheline_aligned " + "crc32ctable_le[%d][%d] = {", + LE_TABLE_ROWS, LE_TABLE_SIZE); + output_table(crc32ctable_le, LE_TABLE_ROWS, + LE_TABLE_SIZE, "tole"); printf("};\n"); } diff --git a/lib/genalloc.c b/lib/genalloc.c index f352cc42f4f..6bc04aab6ec 100644 --- a/lib/genalloc.c +++ b/lib/genalloc.c @@ -29,7 +29,7 @@ */ #include <linux/slab.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/bitmap.h> #include <linux/rculist.h> #include <linux/interrupt.h> diff --git a/lib/halfmd4.c b/lib/halfmd4.c index e11db26f8ae..66d0ee8b777 100644 --- a/lib/halfmd4.c +++ b/lib/halfmd4.c @@ -1,5 +1,5 @@ #include <linux/kernel.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/cryptohash.h> /* F, G and H are basic MD4 functions: selection, majority, parity */ diff --git a/lib/hexdump.c b/lib/hexdump.c index 51d5ae21024..6540d657dca 100644 --- a/lib/hexdump.c +++ b/lib/hexdump.c @@ -10,7 +10,7 @@ #include <linux/types.h> #include <linux/ctype.h> #include <linux/kernel.h> -#include <linux/module.h> +#include <linux/export.h> const char hex_asc[] = "0123456789abcdef"; EXPORT_SYMBOL(hex_asc); diff --git a/lib/hweight.c b/lib/hweight.c index 3c79d50814c..b7d81ba143d 100644 --- a/lib/hweight.c +++ b/lib/hweight.c @@ -1,4 +1,4 @@ -#include <linux/module.h> +#include <linux/export.h> #include <linux/bitops.h> #include <asm/types.h> diff --git a/lib/idr.c b/lib/idr.c index 12499ba7967..4046e29c0a9 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -29,7 +29,7 @@ #ifndef TEST // to test in user space... #include <linux/slab.h> #include <linux/init.h> -#include <linux/module.h> +#include <linux/export.h> #endif #include <linux/err.h> #include <linux/string.h> diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c index fd355a99327..fc2eeb7cb2e 100644 --- a/lib/int_sqrt.c +++ b/lib/int_sqrt.c @@ -1,6 +1,6 @@ #include <linux/kernel.h> -#include <linux/module.h> +#include <linux/export.h> /** * int_sqrt - rough approximation to sqrt diff --git a/lib/iomap.c b/lib/iomap.c index ada922a808e..2c08f36862e 100644 --- a/lib/iomap.c +++ b/lib/iomap.c @@ -6,7 +6,7 @@ #include <linux/pci.h> #include <linux/io.h> -#include <linux/module.h> +#include <linux/export.h> /* * Read/write from/to an (offsettable) iomem cookie. It might be a PIO diff --git a/lib/iomap_copy.c b/lib/iomap_copy.c index 864fc5ea398..4527e751b5e 100644 --- a/lib/iomap_copy.c +++ b/lib/iomap_copy.c @@ -15,7 +15,7 @@ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. */ -#include <linux/module.h> +#include <linux/export.h> #include <linux/io.h> /** diff --git a/lib/iommu-helper.c b/lib/iommu-helper.c index da053313ee5..c27e269210c 100644 --- a/lib/iommu-helper.c +++ b/lib/iommu-helper.c @@ -2,8 +2,9 @@ * IOMMU helper functions for the free area management */ -#include <linux/module.h> +#include <linux/export.h> #include <linux/bitmap.h> +#include <linux/bug.h> int iommu_is_span_boundary(unsigned int index, unsigned int nr, unsigned long shift, diff --git a/lib/ioremap.c b/lib/ioremap.c index da4e2ad74b6..0c9216c4876 100644 --- a/lib/ioremap.c +++ b/lib/ioremap.c @@ -9,7 +9,7 @@ #include <linux/mm.h> #include <linux/sched.h> #include <linux/io.h> -#include <linux/module.h> +#include <linux/export.h> #include <asm/cacheflush.h> #include <asm/pgtable.h> diff --git a/lib/irq_regs.c b/lib/irq_regs.c index 753880a5440..9c0a1d70fbe 100644 --- a/lib/irq_regs.c +++ b/lib/irq_regs.c @@ -8,7 +8,8 @@ * as published by the Free Software Foundation; either version * 2 of the License, or (at your option) any later version. */ -#include <linux/module.h> +#include <linux/export.h> +#include <linux/percpu.h> #include <asm/irq_regs.h> #ifndef ARCH_HAS_OWN_IRQ_REGS diff --git a/lib/kasprintf.c b/lib/kasprintf.c index 9c4233b2378..ae0de80c1c8 100644 --- a/lib/kasprintf.c +++ b/lib/kasprintf.c @@ -5,7 +5,7 @@ */ #include <stdarg.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/slab.h> #include <linux/types.h> #include <linux/string.h> diff --git a/lib/klist.c b/lib/klist.c index 573d6068a42..0874e41609a 100644 --- a/lib/klist.c +++ b/lib/klist.c @@ -35,7 +35,7 @@ */ #include <linux/klist.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/sched.h> /* diff --git a/lib/kobject.c b/lib/kobject.c index c33d7a18d63..21dee7c19af 100644 --- a/lib/kobject.c +++ b/lib/kobject.c @@ -14,7 +14,7 @@ #include <linux/kobject.h> #include <linux/string.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/stat.h> #include <linux/slab.h> diff --git a/lib/kobject_uevent.c b/lib/kobject_uevent.c index 75cbdb52bf5..1a91efa6d12 100644 --- a/lib/kobject_uevent.c +++ b/lib/kobject_uevent.c @@ -17,7 +17,8 @@ #include <linux/spinlock.h> #include <linux/string.h> #include <linux/kobject.h> -#include <linux/module.h> +#include <linux/export.h> +#include <linux/kmod.h> #include <linux/slab.h> #include <linux/user_namespace.h> #include <linux/socket.h> diff --git a/lib/kstrtox.c b/lib/kstrtox.c index b1dd3e7d88c..c3615eab0cc 100644 --- a/lib/kstrtox.c +++ b/lib/kstrtox.c @@ -15,7 +15,7 @@ #include <linux/errno.h> #include <linux/kernel.h> #include <linux/math64.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/types.h> #include <asm/uaccess.h> #include "kstrtox.h" diff --git a/lib/lcm.c b/lib/lcm.c index 10b5cfcacf6..b9c8de461e9 100644 --- a/lib/lcm.c +++ b/lib/lcm.c @@ -1,6 +1,6 @@ #include <linux/kernel.h> #include <linux/gcd.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/lcm.h> /* Lowest common multiple */ diff --git a/lib/list_debug.c b/lib/list_debug.c index b8029a5583f..982b850d4e7 100644 --- a/lib/list_debug.c +++ b/lib/list_debug.c @@ -6,8 +6,10 @@ * DEBUG_LIST. */ -#include <linux/module.h> +#include <linux/export.h> #include <linux/list.h> +#include <linux/bug.h> +#include <linux/kernel.h> /* * Insert a new entry between two known consecutive entries. diff --git a/lib/llist.c b/lib/llist.c index 700cff77a38..4a15115e90f 100644 --- a/lib/llist.c +++ b/lib/llist.c @@ -23,11 +23,10 @@ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #include <linux/kernel.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/interrupt.h> #include <linux/llist.h> -#include <asm/system.h> /** * llist_add_batch - add several linked entries in batch diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c index 507a22fab73..7aae0f2a5e0 100644 --- a/lib/locking-selftest.c +++ b/lib/locking-selftest.c @@ -14,7 +14,6 @@ #include <linux/mutex.h> #include <linux/sched.h> #include <linux/delay.h> -#include <linux/module.h> #include <linux/lockdep.h> #include <linux/spinlock.h> #include <linux/kallsyms.h> diff --git a/lib/md5.c b/lib/md5.c index c777180e1f2..958a3c15923 100644 --- a/lib/md5.c +++ b/lib/md5.c @@ -1,5 +1,5 @@ #include <linux/kernel.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/cryptohash.h> #define F1(x, y, z) (z ^ (x & (y ^ z))) diff --git a/lib/nlattr.c b/lib/nlattr.c index a8408b6cacd..4226dfeb517 100644 --- a/lib/nlattr.c +++ b/lib/nlattr.c @@ -5,7 +5,7 @@ * Alexey Kuznetsov <kuznet@ms2.inr.ac.ru> */ -#include <linux/module.h> +#include <linux/export.h> #include <linux/kernel.h> #include <linux/errno.h> #include <linux/jiffies.h> diff --git a/lib/parser.c b/lib/parser.c index dcbaaef6cf1..c4341008483 100644 --- a/lib/parser.c +++ b/lib/parser.c @@ -6,7 +6,8 @@ */ #include <linux/ctype.h> -#include <linux/module.h> +#include <linux/types.h> +#include <linux/export.h> #include <linux/parser.h> #include <linux/slab.h> #include <linux/string.h> diff --git a/lib/plist.c b/lib/plist.c index a0a4da489c2..6ab0e521c48 100644 --- a/lib/plist.c +++ b/lib/plist.c @@ -23,6 +23,7 @@ * information. */ +#include <linux/bug.h> #include <linux/plist.h> #include <linux/spinlock.h> diff --git a/lib/prio_tree.c b/lib/prio_tree.c index ccfd850b0de..8d443af03b4 100644 --- a/lib/prio_tree.c +++ b/lib/prio_tree.c @@ -85,6 +85,17 @@ static inline unsigned long prio_tree_maxindex(unsigned int bits) return index_bits_to_maxindex[bits - 1]; } +static void prio_set_parent(struct prio_tree_node *parent, + struct prio_tree_node *child, bool left) +{ + if (left) + parent->left = child; + else + parent->right = child; + + child->parent = parent; +} + /* * Extend a priority search tree so that it can store a node with heap_index * max_heap_index. In the worst case, this algorithm takes O((log n)^2). @@ -94,45 +105,32 @@ static inline unsigned long prio_tree_maxindex(unsigned int bits) static struct prio_tree_node *prio_tree_expand(struct prio_tree_root *root, struct prio_tree_node *node, unsigned long max_heap_index) { - struct prio_tree_node *first = NULL, *prev, *last = NULL; + struct prio_tree_node *prev; if (max_heap_index > prio_tree_maxindex(root->index_bits)) root->index_bits++; + prev = node; + INIT_PRIO_TREE_NODE(node); + while (max_heap_index > prio_tree_maxindex(root->index_bits)) { + struct prio_tree_node *tmp = root->prio_tree_node; + root->index_bits++; if (prio_tree_empty(root)) continue; - if (first == NULL) { - first = root->prio_tree_node; - prio_tree_remove(root, root->prio_tree_node); - INIT_PRIO_TREE_NODE(first); - last = first; - } else { - prev = last; - last = root->prio_tree_node; - prio_tree_remove(root, root->prio_tree_node); - INIT_PRIO_TREE_NODE(last); - prev->left = last; - last->parent = prev; - } - } - - INIT_PRIO_TREE_NODE(node); - - if (first) { - node->left = first; - first->parent = node; - } else - last = node; + prio_tree_remove(root, root->prio_tree_node); + INIT_PRIO_TREE_NODE(tmp); - if (!prio_tree_empty(root)) { - last->left = root->prio_tree_node; - last->left->parent = last; + prio_set_parent(prev, tmp, true); + prev = tmp; } + if (!prio_tree_empty(root)) + prio_set_parent(prev, root->prio_tree_node, true); + root->prio_tree_node = node; return node; } @@ -151,25 +149,15 @@ struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root, * We can reduce root->index_bits here. However, it is complex * and does not help much to improve performance (IMO). */ - node->parent = node; root->prio_tree_node = node; - } else { - node->parent = old->parent; - if (old->parent->left == old) - old->parent->left = node; - else - old->parent->right = node; - } + } else + prio_set_parent(old->parent, node, old->parent->left == old); - if (!prio_tree_left_empty(old)) { - node->left = old->left; - old->left->parent = node; - } + if (!prio_tree_left_empty(old)) + prio_set_parent(node, old->left, true); - if (!prio_tree_right_empty(old)) { - node->right = old->right; - old->right->parent = node; - } + if (!prio_tree_right_empty(old)) + prio_set_parent(node, old->right, false); return old; } @@ -229,16 +217,14 @@ struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root, if (index & mask) { if (prio_tree_right_empty(cur)) { INIT_PRIO_TREE_NODE(node); - cur->right = node; - node->parent = cur; + prio_set_parent(cur, node, false); return res; } else cur = cur->right; } else { if (prio_tree_left_empty(cur)) { INIT_PRIO_TREE_NODE(node); - cur->left = node; - node->parent = cur; + prio_set_parent(cur, node, true); return res; } else cur = cur->left; @@ -305,6 +291,40 @@ void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node) cur = prio_tree_replace(root, cur->parent, cur); } +static void iter_walk_down(struct prio_tree_iter *iter) +{ + iter->mask >>= 1; + if (iter->mask) { + if (iter->size_level) + iter->size_level++; + return; + } + + if (iter->size_level) { + BUG_ON(!prio_tree_left_empty(iter->cur)); + BUG_ON(!prio_tree_right_empty(iter->cur)); + iter->size_level++; + iter->mask = ULONG_MAX; + } else { + iter->size_level = 1; + iter->mask = 1UL << (BITS_PER_LONG - 1); + } +} + +static void iter_walk_up(struct prio_tree_iter *iter) +{ + if (iter->mask == ULONG_MAX) + iter->mask = 1UL; + else if (iter->size_level == 1) + iter->mask = 1UL; + else + iter->mask <<= 1; + if (iter->size_level) + iter->size_level--; + if (!iter->size_level && (iter->value & iter->mask)) + iter->value ^= iter->mask; +} + /* * Following functions help to enumerate all prio_tree_nodes in the tree that * overlap with the input interval X [radix_index, heap_index]. The enumeration @@ -323,21 +343,7 @@ static struct prio_tree_node *prio_tree_left(struct prio_tree_iter *iter, if (iter->r_index <= *h_index) { iter->cur = iter->cur->left; - iter->mask >>= 1; - if (iter->mask) { - if (iter->size_level) - iter->size_level++; - } else { - if (iter->size_level) { - BUG_ON(!prio_tree_left_empty(iter->cur)); - BUG_ON(!prio_tree_right_empty(iter->cur)); - iter->size_level++; - iter->mask = ULONG_MAX; - } else { - iter->size_level = 1; - iter->mask = 1UL << (BITS_PER_LONG - 1); - } - } + iter_walk_down(iter); return iter->cur; } @@ -364,22 +370,7 @@ static struct prio_tree_node *prio_tree_right(struct prio_tree_iter *iter, if (iter->r_index <= *h_index) { iter->cur = iter->cur->right; - iter->mask >>= 1; - iter->value = value; - if (iter->mask) { - if (iter->size_level) - iter->size_level++; - } else { - if (iter->size_level) { - BUG_ON(!prio_tree_left_empty(iter->cur)); - BUG_ON(!prio_tree_right_empty(iter->cur)); - iter->size_level++; - iter->mask = ULONG_MAX; - } else { - iter->size_level = 1; - iter->mask = 1UL << (BITS_PER_LONG - 1); - } - } + iter_walk_down(iter); return iter->cur; } @@ -389,16 +380,7 @@ static struct prio_tree_node *prio_tree_right(struct prio_tree_iter *iter, static struct prio_tree_node *prio_tree_parent(struct prio_tree_iter *iter) { iter->cur = iter->cur->parent; - if (iter->mask == ULONG_MAX) - iter->mask = 1UL; - else if (iter->size_level == 1) - iter->mask = 1UL; - else - iter->mask <<= 1; - if (iter->size_level) - iter->size_level--; - if (!iter->size_level && (iter->value & iter->mask)) - iter->value ^= iter->mask; + iter_walk_up(iter); return iter->cur; } diff --git a/lib/radix-tree.c b/lib/radix-tree.c index dc63d081839..86516f5588e 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -3,6 +3,7 @@ * Portions Copyright (C) 2001 Christoph Hellwig * Copyright (C) 2005 SGI, Christoph Lameter * Copyright (C) 2006 Nick Piggin + * Copyright (C) 2012 Konstantin Khlebnikov * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as @@ -22,7 +23,7 @@ #include <linux/errno.h> #include <linux/init.h> #include <linux/kernel.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/radix-tree.h> #include <linux/percpu.h> #include <linux/slab.h> @@ -146,6 +147,43 @@ static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag) } return 0; } + +/** + * radix_tree_find_next_bit - find the next set bit in a memory region + * + * @addr: The address to base the search on + * @size: The bitmap size in bits + * @offset: The bitnumber to start searching at + * + * Unrollable variant of find_next_bit() for constant size arrays. + * Tail bits starting from size to roundup(size, BITS_PER_LONG) must be zero. + * Returns next bit offset, or size if nothing found. + */ +static __always_inline unsigned long +radix_tree_find_next_bit(const unsigned long *addr, + unsigned long size, unsigned long offset) +{ + if (!__builtin_constant_p(size)) + return find_next_bit(addr, size, offset); + + if (offset < size) { + unsigned long tmp; + + addr += offset / BITS_PER_LONG; + tmp = *addr >> (offset % BITS_PER_LONG); + if (tmp) + return __ffs(tmp) + offset; + offset = (offset + BITS_PER_LONG) & ~(BITS_PER_LONG - 1); + while (offset < size) { + tmp = *++addr; + if (tmp) + return __ffs(tmp) + offset; + offset += BITS_PER_LONG; + } + } + return size; +} + /* * This assumes that the caller has performed appropriate preallocation, and * that the caller has pinned this thread of control to the current CPU. @@ -613,6 +651,119 @@ int radix_tree_tag_get(struct radix_tree_root *root, EXPORT_SYMBOL(radix_tree_tag_get); /** + * radix_tree_next_chunk - find next chunk of slots for iteration + * + * @root: radix tree root + * @iter: iterator state + * @flags: RADIX_TREE_ITER_* flags and tag index + * Returns: pointer to chunk first slot, or NULL if iteration is over + */ +void **radix_tree_next_chunk(struct radix_tree_root *root, + struct radix_tree_iter *iter, unsigned flags) +{ + unsigned shift, tag = flags & RADIX_TREE_ITER_TAG_MASK; + struct radix_tree_node *rnode, *node; + unsigned long index, offset; + + if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag)) + return NULL; + + /* + * Catch next_index overflow after ~0UL. iter->index never overflows + * during iterating; it can be zero only at the beginning. + * And we cannot overflow iter->next_index in a single step, + * because RADIX_TREE_MAP_SHIFT < BITS_PER_LONG. + */ + index = iter->next_index; + if (!index && iter->index) + return NULL; + + rnode = rcu_dereference_raw(root->rnode); + if (radix_tree_is_indirect_ptr(rnode)) { + rnode = indirect_to_ptr(rnode); + } else if (rnode && !index) { + /* Single-slot tree */ + iter->index = 0; + iter->next_index = 1; + iter->tags = 1; + return (void **)&root->rnode; + } else + return NULL; + +restart: + shift = (rnode->height - 1) * RADIX_TREE_MAP_SHIFT; + offset = index >> shift; + + /* Index outside of the tree */ + if (offset >= RADIX_TREE_MAP_SIZE) + return NULL; + + node = rnode; + while (1) { + if ((flags & RADIX_TREE_ITER_TAGGED) ? + !test_bit(offset, node->tags[tag]) : + !node->slots[offset]) { + /* Hole detected */ + if (flags & RADIX_TREE_ITER_CONTIG) + return NULL; + + if (flags & RADIX_TREE_ITER_TAGGED) + offset = radix_tree_find_next_bit( + node->tags[tag], + RADIX_TREE_MAP_SIZE, + offset + 1); + else + while (++offset < RADIX_TREE_MAP_SIZE) { + if (node->slots[offset]) + break; + } + index &= ~((RADIX_TREE_MAP_SIZE << shift) - 1); + index += offset << shift; + /* Overflow after ~0UL */ + if (!index) + return NULL; + if (offset == RADIX_TREE_MAP_SIZE) + goto restart; + } + + /* This is leaf-node */ + if (!shift) + break; + + node = rcu_dereference_raw(node->slots[offset]); + if (node == NULL) + goto restart; + shift -= RADIX_TREE_MAP_SHIFT; + offset = (index >> shift) & RADIX_TREE_MAP_MASK; + } + + /* Update the iterator state */ + iter->index = index; + iter->next_index = (index | RADIX_TREE_MAP_MASK) + 1; + + /* Construct iter->tags bit-mask from node->tags[tag] array */ + if (flags & RADIX_TREE_ITER_TAGGED) { + unsigned tag_long, tag_bit; + + tag_long = offset / BITS_PER_LONG; + tag_bit = offset % BITS_PER_LONG; + iter->tags = node->tags[tag][tag_long] >> tag_bit; + /* This never happens if RADIX_TREE_TAG_LONGS == 1 */ + if (tag_long < RADIX_TREE_TAG_LONGS - 1) { + /* Pick tags from next element */ + if (tag_bit) + iter->tags |= node->tags[tag][tag_long + 1] << + (BITS_PER_LONG - tag_bit); + /* Clip chunk size, here only BITS_PER_LONG tags */ + iter->next_index = index + BITS_PER_LONG; + } + } + + return node->slots + offset; +} +EXPORT_SYMBOL(radix_tree_next_chunk); + +/** * radix_tree_range_tag_if_tagged - for each item in given range set given * tag if item has another tag set * @root: radix tree root @@ -817,57 +968,6 @@ unsigned long radix_tree_prev_hole(struct radix_tree_root *root, } EXPORT_SYMBOL(radix_tree_prev_hole); -static unsigned int -__lookup(struct radix_tree_node *slot, void ***results, unsigned long *indices, - unsigned long index, unsigned int max_items, unsigned long *next_index) -{ - unsigned int nr_found = 0; - unsigned int shift, height; - unsigned long i; - - height = slot->height; - if (height == 0) - goto out; - shift = (height-1) * RADIX_TREE_MAP_SHIFT; - - for ( ; height > 1; height--) { - i = (index >> shift) & RADIX_TREE_MAP_MASK; - for (;;) { - if (slot->slots[i] != NULL) - break; - index &= ~((1UL << shift) - 1); - index += 1UL << shift; - if (index == 0) - goto out; /* 32-bit wraparound */ - i++; - if (i == RADIX_TREE_MAP_SIZE) - goto out; - } - - shift -= RADIX_TREE_MAP_SHIFT; - slot = rcu_dereference_raw(slot->slots[i]); - if (slot == NULL) - goto out; - } - - /* Bottom level: grab some items */ - for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) { - if (slot->slots[i]) { - results[nr_found] = &(slot->slots[i]); - if (indices) - indices[nr_found] = index; - if (++nr_found == max_items) { - index++; - goto out; - } - } - index++; - } -out: - *next_index = index; - return nr_found; -} - /** * radix_tree_gang_lookup - perform multiple lookup on a radix tree * @root: radix tree root @@ -891,48 +991,19 @@ unsigned int radix_tree_gang_lookup(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items) { - unsigned long max_index; - struct radix_tree_node *node; - unsigned long cur_index = first_index; - unsigned int ret; + struct radix_tree_iter iter; + void **slot; + unsigned int ret = 0; - node = rcu_dereference_raw(root->rnode); - if (!node) + if (unlikely(!max_items)) return 0; - if (!radix_tree_is_indirect_ptr(node)) { - if (first_index > 0) - return 0; - results[0] = node; - return 1; - } - node = indirect_to_ptr(node); - - max_index = radix_tree_maxindex(node->height); - - ret = 0; - while (ret < max_items) { - unsigned int nr_found, slots_found, i; - unsigned long next_index; /* Index of next search */ - - if (cur_index > max_index) - break; - slots_found = __lookup(node, (void ***)results + ret, NULL, - cur_index, max_items - ret, &next_index); - nr_found = 0; - for (i = 0; i < slots_found; i++) { - struct radix_tree_node *slot; - slot = *(((void ***)results)[ret + i]); - if (!slot) - continue; - results[ret + nr_found] = - indirect_to_ptr(rcu_dereference_raw(slot)); - nr_found++; - } - ret += nr_found; - if (next_index == 0) + radix_tree_for_each_slot(slot, root, &iter, first_index) { + results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot)); + if (!results[ret]) + continue; + if (++ret == max_items) break; - cur_index = next_index; } return ret; @@ -962,112 +1033,25 @@ radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results, unsigned long *indices, unsigned long first_index, unsigned int max_items) { - unsigned long max_index; - struct radix_tree_node *node; - unsigned long cur_index = first_index; - unsigned int ret; + struct radix_tree_iter iter; + void **slot; + unsigned int ret = 0; - node = rcu_dereference_raw(root->rnode); - if (!node) + if (unlikely(!max_items)) return 0; - if (!radix_tree_is_indirect_ptr(node)) { - if (first_index > 0) - return 0; - results[0] = (void **)&root->rnode; + radix_tree_for_each_slot(slot, root, &iter, first_index) { + results[ret] = slot; if (indices) - indices[0] = 0; - return 1; - } - node = indirect_to_ptr(node); - - max_index = radix_tree_maxindex(node->height); - - ret = 0; - while (ret < max_items) { - unsigned int slots_found; - unsigned long next_index; /* Index of next search */ - - if (cur_index > max_index) + indices[ret] = iter.index; + if (++ret == max_items) break; - slots_found = __lookup(node, results + ret, - indices ? indices + ret : NULL, - cur_index, max_items - ret, &next_index); - ret += slots_found; - if (next_index == 0) - break; - cur_index = next_index; } return ret; } EXPORT_SYMBOL(radix_tree_gang_lookup_slot); -/* - * FIXME: the two tag_get()s here should use find_next_bit() instead of - * open-coding the search. - */ -static unsigned int -__lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index, - unsigned int max_items, unsigned long *next_index, unsigned int tag) -{ - unsigned int nr_found = 0; - unsigned int shift, height; - - height = slot->height; - if (height == 0) - goto out; - shift = (height-1) * RADIX_TREE_MAP_SHIFT; - - while (height > 0) { - unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ; - - for (;;) { - if (tag_get(slot, tag, i)) - break; - index &= ~((1UL << shift) - 1); - index += 1UL << shift; - if (index == 0) - goto out; /* 32-bit wraparound */ - i++; - if (i == RADIX_TREE_MAP_SIZE) - goto out; - } - height--; - if (height == 0) { /* Bottom level: grab some items */ - unsigned long j = index & RADIX_TREE_MAP_MASK; - - for ( ; j < RADIX_TREE_MAP_SIZE; j++) { - index++; - if (!tag_get(slot, tag, j)) - continue; - /* - * Even though the tag was found set, we need to - * recheck that we have a non-NULL node, because - * if this lookup is lockless, it may have been - * subsequently deleted. - * - * Similar care must be taken in any place that - * lookup ->slots[x] without a lock (ie. can't - * rely on its value remaining the same). - */ - if (slot->slots[j]) { - results[nr_found++] = &(slot->slots[j]); - if (nr_found == max_items) - goto out; - } - } - } - shift -= RADIX_TREE_MAP_SHIFT; - slot = rcu_dereference_raw(slot->slots[i]); - if (slot == NULL) - break; - } -out: - *next_index = index; - return nr_found; -} - /** * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree * based on a tag @@ -1086,52 +1070,19 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items, unsigned int tag) { - struct radix_tree_node *node; - unsigned long max_index; - unsigned long cur_index = first_index; - unsigned int ret; - - /* check the root's tag bit */ - if (!root_tag_get(root, tag)) - return 0; + struct radix_tree_iter iter; + void **slot; + unsigned int ret = 0; - node = rcu_dereference_raw(root->rnode); - if (!node) + if (unlikely(!max_items)) return 0; - if (!radix_tree_is_indirect_ptr(node)) { - if (first_index > 0) - return 0; - results[0] = node; - return 1; - } - node = indirect_to_ptr(node); - - max_index = radix_tree_maxindex(node->height); - - ret = 0; - while (ret < max_items) { - unsigned int nr_found, slots_found, i; - unsigned long next_index; /* Index of next search */ - - if (cur_index > max_index) - break; - slots_found = __lookup_tag(node, (void ***)results + ret, - cur_index, max_items - ret, &next_index, tag); - nr_found = 0; - for (i = 0; i < slots_found; i++) { - struct radix_tree_node *slot; - slot = *(((void ***)results)[ret + i]); - if (!slot) - continue; - results[ret + nr_found] = - indirect_to_ptr(rcu_dereference_raw(slot)); - nr_found++; - } - ret += nr_found; - if (next_index == 0) + radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { + results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot)); + if (!results[ret]) + continue; + if (++ret == max_items) break; - cur_index = next_index; } return ret; @@ -1156,42 +1107,17 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results, unsigned long first_index, unsigned int max_items, unsigned int tag) { - struct radix_tree_node *node; - unsigned long max_index; - unsigned long cur_index = first_index; - unsigned int ret; + struct radix_tree_iter iter; + void **slot; + unsigned int ret = 0; - /* check the root's tag bit */ - if (!root_tag_get(root, tag)) - return 0; - - node = rcu_dereference_raw(root->rnode); - if (!node) + if (unlikely(!max_items)) return 0; - if (!radix_tree_is_indirect_ptr(node)) { - if (first_index > 0) - return 0; - results[0] = (void **)&root->rnode; - return 1; - } - node = indirect_to_ptr(node); - - max_index = radix_tree_maxindex(node->height); - - ret = 0; - while (ret < max_items) { - unsigned int slots_found; - unsigned long next_index; /* Index of next search */ - - if (cur_index > max_index) - break; - slots_found = __lookup_tag(node, results + ret, - cur_index, max_items - ret, &next_index, tag); - ret += slots_found; - if (next_index == 0) + radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { + results[ret] = slot; + if (++ret == max_items) break; - cur_index = next_index; } return ret; diff --git a/lib/raid6/altivec.uc b/lib/raid6/altivec.uc index 2654d5c854b..b71012b756f 100644 --- a/lib/raid6/altivec.uc +++ b/lib/raid6/altivec.uc @@ -28,8 +28,8 @@ #include <altivec.h> #ifdef __KERNEL__ -# include <asm/system.h> # include <asm/cputable.h> +# include <asm/switch_to.h> #endif /* diff --git a/lib/random32.c b/lib/random32.c index fc3545a3277..938bde5876a 100644 --- a/lib/random32.c +++ b/lib/random32.c @@ -35,7 +35,7 @@ #include <linux/types.h> #include <linux/percpu.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/jiffies.h> #include <linux/random.h> diff --git a/lib/ratelimit.c b/lib/ratelimit.c index c96d500577d..40e03ea2a96 100644 --- a/lib/ratelimit.c +++ b/lib/ratelimit.c @@ -11,7 +11,7 @@ #include <linux/ratelimit.h> #include <linux/jiffies.h> -#include <linux/module.h> +#include <linux/export.h> /* * __ratelimit - rate limiting diff --git a/lib/rational.c b/lib/rational.c index 3ed247b8066..d326da3976f 100644 --- a/lib/rational.c +++ b/lib/rational.c @@ -7,7 +7,8 @@ */ #include <linux/rational.h> -#include <linux/module.h> +#include <linux/compiler.h> +#include <linux/export.h> /* * calculate best rational approximation for a given fraction diff --git a/lib/rbtree.c b/lib/rbtree.c index a16be19a130..d4175565dc2 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -21,7 +21,7 @@ */ #include <linux/rbtree.h> -#include <linux/module.h> +#include <linux/export.h> static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) { diff --git a/lib/rwsem-spinlock.c b/lib/rwsem-spinlock.c index f2393c21fe8..7e0d6a58fc8 100644 --- a/lib/rwsem-spinlock.c +++ b/lib/rwsem-spinlock.c @@ -7,7 +7,7 @@ */ #include <linux/rwsem.h> #include <linux/sched.h> -#include <linux/module.h> +#include <linux/export.h> struct rwsem_waiter { struct list_head list; diff --git a/lib/rwsem.c b/lib/rwsem.c index 410aa1189b1..8337e1b9bb8 100644 --- a/lib/rwsem.c +++ b/lib/rwsem.c @@ -6,7 +6,7 @@ #include <linux/rwsem.h> #include <linux/sched.h> #include <linux/init.h> -#include <linux/module.h> +#include <linux/export.h> /* * Initialize an rwsem: diff --git a/lib/scatterlist.c b/lib/scatterlist.c index 33b2cbb9738..6096e89bee5 100644 --- a/lib/scatterlist.c +++ b/lib/scatterlist.c @@ -6,7 +6,7 @@ * This source code is licensed under the GNU General Public License, * Version 2. See the file COPYING for more details. */ -#include <linux/module.h> +#include <linux/export.h> #include <linux/slab.h> #include <linux/scatterlist.h> #include <linux/highmem.h> diff --git a/lib/sha1.c b/lib/sha1.c index 1de509a159c..1df191e04a2 100644 --- a/lib/sha1.c +++ b/lib/sha1.c @@ -6,7 +6,7 @@ */ #include <linux/kernel.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/bitops.h> #include <linux/cryptohash.h> #include <asm/unaligned.h> diff --git a/lib/smp_processor_id.c b/lib/smp_processor_id.c index 503f087382a..4c0d0e51d49 100644 --- a/lib/smp_processor_id.c +++ b/lib/smp_processor_id.c @@ -3,7 +3,7 @@ * * DEBUG_PREEMPT variant of smp_processor_id(). */ -#include <linux/module.h> +#include <linux/export.h> #include <linux/kallsyms.h> #include <linux/sched.h> diff --git a/lib/spinlock_debug.c b/lib/spinlock_debug.c index 5f3eacdd617..525d160d44f 100644 --- a/lib/spinlock_debug.c +++ b/lib/spinlock_debug.c @@ -11,7 +11,7 @@ #include <linux/interrupt.h> #include <linux/debug_locks.h> #include <linux/delay.h> -#include <linux/module.h> +#include <linux/export.h> void __raw_spin_lock_init(raw_spinlock_t *lock, const char *name, struct lock_class_key *key) diff --git a/lib/string.c b/lib/string.c index dc4a86341f9..e5878de4f10 100644 --- a/lib/string.c +++ b/lib/string.c @@ -22,7 +22,10 @@ #include <linux/types.h> #include <linux/string.h> #include <linux/ctype.h> -#include <linux/module.h> +#include <linux/kernel.h> +#include <linux/export.h> +#include <linux/bug.h> +#include <linux/errno.h> #ifndef __HAVE_ARCH_STRNICMP /** @@ -785,12 +788,24 @@ void *memchr_inv(const void *start, int c, size_t bytes) if (bytes <= 16) return check_bytes8(start, value, bytes); - value64 = value | value << 8 | value << 16 | value << 24; - value64 = (value64 & 0xffffffff) | value64 << 32; - prefix = 8 - ((unsigned long)start) % 8; + value64 = value; +#if defined(ARCH_HAS_FAST_MULTIPLIER) && BITS_PER_LONG == 64 + value64 *= 0x0101010101010101; +#elif defined(ARCH_HAS_FAST_MULTIPLIER) + value64 *= 0x01010101; + value64 |= value64 << 32; +#else + value64 |= value64 << 8; + value64 |= value64 << 16; + value64 |= value64 << 32; +#endif + prefix = (unsigned long)start % 8; if (prefix) { - u8 *r = check_bytes8(start, value, prefix); + u8 *r; + + prefix = 8 - prefix; + r = check_bytes8(start, value, prefix); if (r) return r; start += prefix; diff --git a/lib/string_helpers.c b/lib/string_helpers.c index ab431d4cc97..dd4ece37269 100644 --- a/lib/string_helpers.c +++ b/lib/string_helpers.c @@ -5,7 +5,7 @@ */ #include <linux/kernel.h> #include <linux/math64.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/string_helpers.h> /** diff --git a/lib/swiotlb.c b/lib/swiotlb.c index d0f6315f4a2..414f46ed1dc 100644 --- a/lib/swiotlb.c +++ b/lib/swiotlb.c @@ -20,7 +20,7 @@ #include <linux/cache.h> #include <linux/dma-mapping.h> #include <linux/mm.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/spinlock.h> #include <linux/string.h> #include <linux/swiotlb.h> diff --git a/lib/syscall.c b/lib/syscall.c index a4f7067f72f..58710eefeac 100644 --- a/lib/syscall.c +++ b/lib/syscall.c @@ -1,6 +1,6 @@ #include <linux/ptrace.h> #include <linux/sched.h> -#include <linux/module.h> +#include <linux/export.h> #include <asm/syscall.h> static int collect_syscall(struct task_struct *target, long *callno, diff --git a/lib/timerqueue.c b/lib/timerqueue.c index 191176a43e9..a382e4a3260 100644 --- a/lib/timerqueue.c +++ b/lib/timerqueue.c @@ -22,9 +22,10 @@ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ +#include <linux/bug.h> #include <linux/timerqueue.h> #include <linux/rbtree.h> -#include <linux/module.h> +#include <linux/export.h> /** * timerqueue_add - Adds timer to timerqueue. diff --git a/lib/uuid.c b/lib/uuid.c index 8fadd7cef46..52a6fe6387d 100644 --- a/lib/uuid.c +++ b/lib/uuid.c @@ -19,7 +19,7 @@ */ #include <linux/kernel.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/uuid.h> #include <linux/random.h> diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 38e612e66da..abbabec9720 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -17,7 +17,7 @@ */ #include <stdarg.h> -#include <linux/module.h> +#include <linux/module.h> /* for KSYM_SYMBOL_LEN */ #include <linux/types.h> #include <linux/string.h> #include <linux/ctype.h> @@ -212,6 +212,26 @@ char *put_dec(char *buf, unsigned long long num) } } +/* + * Convert passed number to decimal string. + * Returns the length of string. On buffer overflow, returns 0. + * + * If speed is not important, use snprintf(). It's easy to read the code. + */ +int num_to_str(char *buf, int size, unsigned long long num) +{ + char tmp[21]; /* Enough for 2^64 in decimal */ + int idx, len; + + len = put_dec(tmp, num) - tmp; + + if (len > size) + return 0; + for (idx = 0; idx < len; ++idx) + buf[idx] = tmp[len - idx - 1]; + return len; +} + #define ZEROPAD 1 /* pad with zero */ #define SIGN 2 /* unsigned/signed long */ #define PLUS 4 /* show plus */ |