Hi all,
This patchset replaces the current crc32c software implementation, which uses a
slow per-byte lookup table algorithm, with a faster implementation that uses an
adaptation of the slice-by-8 algorithm that Bob Pearson has been pushing for
crc32.
The motivation for this patchset is that I am working on adding full metadata
checksumming to ext4[1]. As far as performance impact of adding checksumming
goes, I see nearly no change with a standard mail server ffsb simulation. On a
test that involves only file creation and deletion and extent tree writes, I
see a drop of about 50 pcercent with the current kernel crc32c implementation;
this improves to a drop of about 20 percent with the enclosed crc32c code.
When metadata is usually a small fraction of total IO, this new implementation
doesn't help much because metadata is usually a small fraction of total IO.
However, when we are doing IO that is almost all metadata (such as rm -rf'ing a
tree), then this patch speeds up the operation substantially.
Please have a look at the patches, and please feel free to suggest any changes.
I will be at LPC next week if anyone wishes to discuss, debate, or protest.
Incidentally, given that iscsi, sctp, and btrfs also use crc32c, this patchset
should improve their speed as well. I have not yet quantified that, however.
--D
[1] https://ext4.wiki.kernel.org/index.php/Ext4_Metadata_Checksums
Provide a big-endian version of crc32c for modules that want it.
Signed-off-by: Darrick J. Wong <[email protected]>
---
include/linux/crc32c.h | 5 +++--
lib/libcrc32c.c | 43 ++++++++++++++++++++++++++++++++++---------
2 files changed, 37 insertions(+), 11 deletions(-)
diff --git a/include/linux/crc32c.h b/include/linux/crc32c.h
index bd8b44d..33320e1 100644
--- a/include/linux/crc32c.h
+++ b/include/linux/crc32c.h
@@ -3,9 +3,10 @@
#include <linux/types.h>
-extern u32 crc32c(u32 crc, const void *address, unsigned int length);
+extern u32 crc32c_le(u32 crc, const void *address, unsigned int length);
+extern u32 crc32c_be(u32 crc, const void *address, unsigned int length);
/* This macro exists for backwards-compatibility. */
-#define crc32c_le crc32c
+#define crc32c crc32c_le
#endif /* _LINUX_CRC32C_H */
diff --git a/lib/libcrc32c.c b/lib/libcrc32c.c
index 244f548..e421ff5 100644
--- a/lib/libcrc32c.c
+++ b/lib/libcrc32c.c
@@ -37,17 +37,17 @@
#include <linux/kernel.h>
#include <linux/module.h>
-static struct crypto_shash *tfm;
+static struct crypto_shash *tfm_le, *tfm_be;
-u32 crc32c(u32 crc, const void *address, unsigned int length)
+u32 crc32c_le(u32 crc, const void *address, unsigned int length)
{
struct {
struct shash_desc shash;
- char ctx[crypto_shash_descsize(tfm)];
+ char ctx[crypto_shash_descsize(tfm_le)];
} desc;
int err;
- desc.shash.tfm = tfm;
+ desc.shash.tfm = tfm_le;
desc.shash.flags = 0;
*(u32 *)desc.ctx = crc;
@@ -56,21 +56,46 @@ u32 crc32c(u32 crc, const void *address, unsigned int length)
return *(u32 *)desc.ctx;
}
+EXPORT_SYMBOL(crc32c_le);
-EXPORT_SYMBOL(crc32c);
+u32 crc32c_be(u32 crc, const void *address, unsigned int length)
+{
+ struct {
+ struct shash_desc shash;
+ char ctx[crypto_shash_descsize(tfm_be)];
+ } desc;
+ int err;
+
+ desc.shash.tfm = tfm_be;
+ desc.shash.flags = 0;
+ *(u32 *)desc.ctx = crc;
+
+ err = crypto_shash_update(&desc.shash, address, length);
+ BUG_ON(err);
+
+ return *(u32 *)desc.ctx;
+}
+EXPORT_SYMBOL(crc32c_be);
static int __init libcrc32c_mod_init(void)
{
- tfm = crypto_alloc_shash("crc32c", 0, 0);
- if (IS_ERR(tfm))
- return PTR_ERR(tfm);
+ tfm_le = crypto_alloc_shash("crc32c", 0, 0);
+ if (IS_ERR(tfm_le))
+ return PTR_ERR(tfm_le);
+
+ tfm_be = crypto_alloc_shash("crc32c-be", 0, 0);
+ if (IS_ERR(tfm_be)) {
+ crypto_free_shash(tfm_le);
+ return PTR_ERR(tfm_be);
+ }
return 0;
}
static void __exit libcrc32c_mod_fini(void)
{
- crypto_free_shash(tfm);
+ crypto_free_shash(tfm_be);
+ crypto_free_shash(tfm_le);
}
module_init(libcrc32c_mod_init);
The existing CRC32c implementation uses Sarwate's algorithm to calculate the
code one byte at a time. Using slicing-by-8, we can process buffers 8 bytes at
a time, for a substantial increase in performance.
Signed-off-by: Darrick J. Wong <[email protected]>
---
crypto/Makefile | 11 +
crypto/crc32c.c | 635 ++++++++++++++++++++++++++++++++++++++++++--------
crypto/crc32c_defs.h | 34 +++
3 files changed, 576 insertions(+), 104 deletions(-)
create mode 100644 crypto/crc32c_defs.h
diff --git a/crypto/Makefile b/crypto/Makefile
index ce5a813..00811ef 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -94,3 +94,14 @@ obj-$(CONFIG_CRYPTO_USER_API_SKCIPHER) += algif_skcipher.o
#
obj-$(CONFIG_XOR_BLOCKS) += xor.o
obj-$(CONFIG_ASYNC_CORE) += async_tx/
+
+hostprogs-y := gen_crc32ctable
+clean-files := crc32ctable.h
+
+$(obj)/crc32c.o: $(obj)/crc32c_table.h
+
+quiet_cmd_crc32c = GEN $@
+ cmd_crc32c = $< > $@
+
+$(obj)/crc32c_table.h: $(obj)/gen_crc32ctable
+ $(call cmd,crc32c)
diff --git a/crypto/crc32c.c b/crypto/crc32c.c
index 3f9ad28..d18f6a1 100644
--- a/crypto/crc32c.c
+++ b/crypto/crc32c.c
@@ -33,6 +33,35 @@
* Software Foundation; either version 2 of the License, or (at your option)
* any later version.
*
+ * The current crc32c implementation is adapted from Bob Pearson's slice-by-8
+ * crc32 kernel patch from mid-2011.
+ *
+ * August 26, 2011 Darrick J. Wong <djwong at us.ibm.com>
+ * Reuse Bob Pearson's slice-by-8 implementation for e2fsprogs.
+ *
+ * July 20, 2011 Bob Pearson <rpearson at systemfabricworks.com>
+ * added slice by 8 algorithm to the existing conventional and
+ * slice by 4 algorithms.
+ *
+ * Oct 15, 2000 Matt Domsch <[email protected]>
+ * Nicer crc32 functions/docs submitted by [email protected]. Thanks!
+ * Code was from the public domain, copyright abandoned. Code was
+ * subsequently included in the kernel, thus was re-licensed under the
+ * GNU GPL v2.
+ *
+ * Oct 12, 2000 Matt Domsch <[email protected]>
+ * Same crc32 function was used in 5 other places in the kernel.
+ * I made one version, and deleted the others.
+ * There are various incantations of crc32(). Some use a seed of 0 or ~0.
+ * Some xor at the end with ~0. The generic crc32() function takes
+ * seed as an argument, and doesn't xor at the end. Then individual
+ * users can do whatever they need.
+ * drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0.
+ * fs/jffs2 uses seed 0, doesn't xor with ~0.
+ * fs/partitions/efi.c uses seed ~0, xor's with ~0.
+ *
+ * This source code is licensed under the GNU General Public License,
+ * Version 2. See the file COPYING for more details.
*/
#include <crypto/internal/hash.h>
@@ -40,6 +69,7 @@
#include <linux/module.h>
#include <linux/string.h>
#include <linux/kernel.h>
+#include "crc32c_defs.h"
#define CHKSUM_BLOCK_SIZE 1
#define CHKSUM_DIGEST_SIZE 4
@@ -52,92 +82,398 @@ struct chksum_desc_ctx {
u32 crc;
};
-/*
- * This is the CRC-32C table
- * Generated with:
- * width = 32 bits
- * poly = 0x1EDC6F41
- * reflect input bytes = true
- * reflect output bytes = true
- */
+#if CRC_LE_BITS > 8
+# define tole(x) (__force u32) __constant_cpu_to_le32(x)
+#else
+# define tole(x) (x)
+#endif
-static const u32 crc32c_table[256] = {
- 0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L,
- 0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL,
- 0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL,
- 0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L,
- 0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL,
- 0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L,
- 0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L,
- 0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL,
- 0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL,
- 0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L,
- 0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L,
- 0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL,
- 0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L,
- 0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL,
- 0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL,
- 0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L,
- 0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L,
- 0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L,
- 0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L,
- 0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L,
- 0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L,
- 0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L,
- 0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L,
- 0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L,
- 0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L,
- 0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L,
- 0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L,
- 0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L,
- 0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L,
- 0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L,
- 0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L,
- 0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L,
- 0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL,
- 0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L,
- 0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L,
- 0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL,
- 0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L,
- 0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL,
- 0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL,
- 0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L,
- 0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L,
- 0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL,
- 0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL,
- 0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L,
- 0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL,
- 0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L,
- 0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L,
- 0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL,
- 0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L,
- 0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL,
- 0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL,
- 0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L,
- 0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL,
- 0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L,
- 0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L,
- 0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL,
- 0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL,
- 0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L,
- 0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L,
- 0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL,
- 0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L,
- 0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL,
- 0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL,
- 0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L
-};
+#if CRC_BE_BITS > 8
+# define tobe(x) (__force u32) __constant_cpu_to_be32(x)
+#else
+# define tobe(x) (x)
+#endif
-/*
- * Steps through buffer one byte at at time, calculates reflected
- * crc using table.
- */
+#include "crc32c_table.h"
+
+#if CRC_LE_BITS == 32
+/* slice by 4 algorithm */
+static u32 crc32c_le_body(u32 crc, u8 const *buf, size_t len)
+{
+ const u8 *p8;
+ const u32 *p32;
+ size_t init_bytes;
+ size_t words;
+ size_t end_bytes;
+ size_t i;
+ u32 q;
+ u8 i0, i1, i2, i3;
+
+ crc = (__force u32) __cpu_to_le32(crc);
+
+ /* unroll loop into 'init_bytes' odd bytes followed by
+ * 'words' aligned 4 byte words followed by
+ * 'end_bytes' odd bytes at the end */
+ p8 = buf;
+ p32 = (u32 *)PTR_ALIGN(p8, 4);
+ init_bytes = min((uintptr_t)p32 - (uintptr_t)p8, len);
+ words = (len - init_bytes) >> 2;
+ end_bytes = (len - init_bytes) & 3;
+
+ for (i = 0; i < init_bytes; i++) {
+#ifdef __LITTLE_ENDIAN
+ i0 = *p8++ ^ crc;
+ crc = t0_le[i0] ^ (crc >> 8);
+#else
+ i0 = *p8++ ^ (crc >> 24);
+ crc = t0_le[i0] ^ (crc << 8);
+#endif
+ }
+
+ /* using pre-increment below slightly faster */
+ p32--;
-static u32 crc32c(u32 crc, const u8 *data, unsigned int length)
+ for (i = 0; i < words; i++) {
+#ifdef __LITTLE_ENDIAN
+ q = *++p32 ^ crc;
+ i3 = q;
+ i2 = q >> 8;
+ i1 = q >> 16;
+ i0 = q >> 24;
+ crc = t3_le[i3] ^ t2_le[i2] ^ t1_le[i1] ^ t0_le[i0];
+#else
+ q = *++p32 ^ crc;
+ i3 = q >> 24;
+ i2 = q >> 16;
+ i1 = q >> 8;
+ i0 = q;
+ crc = t3_le[i3] ^ t2_le[i2] ^ t1_le[i1] ^ t0_le[i0];
+#endif
+ }
+
+ p8 = (u8 *)(++p32);
+
+ for (i = 0; i < end_bytes; i++) {
+#ifdef __LITTLE_ENDIAN
+ i0 = *p8++ ^ crc;
+ crc = t0_le[i0] ^ (crc >> 8);
+#else
+ i0 = *p8++ ^ (crc >> 24);
+ crc = t0_le[i0] ^ (crc << 8);
+#endif
+ }
+
+ return __le32_to_cpu((__force __le32)crc);
+}
+#endif
+
+#if CRC_BE_BITS == 32
+static u32 crc32c_be_body(u32 crc, u8 const *buf, size_t len)
{
- while (length--)
- crc = crc32c_table[(crc ^ *data++) & 0xFFL] ^ (crc >> 8);
+ const u8 *p8;
+ const u32 *p32;
+ size_t init_bytes;
+ size_t words;
+ size_t end_bytes;
+ size_t i;
+ u32 q;
+ u8 i0, i1, i2, i3;
+
+ crc = (__force u32) __cpu_to_be32(crc);
+
+ p8 = buf;
+ p32 = (u32 *)PTR_ALIGN(p8, 4);
+ init_bytes = min((uintptr_t)p32 - (uintptr_t)p8, len);
+ words = (len - init_bytes) >> 2;
+ end_bytes = (len - init_bytes) & 3;
+
+ for (i = 0; i < init_bytes; i++) {
+#ifdef __LITTLE_ENDIAN
+ i0 = *p8++ ^ crc;
+ crc = t0_be[i0] ^ (crc >> 8);
+#else
+ i0 = *p8++ ^ (crc >> 24);
+ crc = t0_be[i0] ^ (crc << 8);
+#endif
+ }
+
+ p32--;
+
+ for (i = 0; i < words; i++) {
+#ifdef __LITTLE_ENDIAN
+ q = *++p32 ^ crc;
+ i3 = q;
+ i2 = q >> 8;
+ i1 = q >> 16;
+ i0 = q >> 24;
+ crc = t3_be[i3] ^ t2_be[i2] ^ t1_be[i1] ^ t0_be[i0];
+#else
+ q = *++p32 ^ crc;
+ i3 = q >> 24;
+ i2 = q >> 16;
+ i1 = q >> 8;
+ i0 = q;
+ crc = t3_be[i3] ^ t2_be[i2] ^ t1_be[i1] ^ t0_be[i0];
+#endif
+ }
+
+ p8 = (u8 *)(++p32);
+
+ for (i = 0; i < end_bytes; i++) {
+#ifdef __LITTLE_ENDIAN
+ i0 = *p8++ ^ crc;
+ crc = t0_be[i0] ^ (crc >> 8);
+#else
+ i0 = *p8++ ^ (crc >> 24);
+ crc = t0_be[i0] ^ (crc << 8);
+#endif
+ }
+
+ return __be32_to_cpu((__force __be32)crc);
+}
+#endif
+
+#if CRC_LE_BITS == 64
+/* slice by 8 algorithm */
+static u32 crc32c_le_body(u32 crc, u8 const *buf, size_t len)
+{
+ const u8 *p8;
+ const u32 *p32;
+ size_t init_bytes;
+ size_t words;
+ size_t end_bytes;
+ size_t i;
+ u32 q;
+ u8 i0, i1, i2, i3;
+
+ crc = (__force u32) __cpu_to_le32(crc);
+
+ p8 = buf;
+ p32 = (u32 *)PTR_ALIGN(p8, 8);
+ init_bytes = min((uintptr_t)p32 - (uintptr_t)p8, len);
+ words = (len - init_bytes) >> 3;
+ end_bytes = (len - init_bytes) & 7;
+
+ for (i = 0; i < init_bytes; i++) {
+#ifdef __LITTLE_ENDIAN
+ i0 = *p8++ ^ crc;
+ crc = t0_le[i0] ^ (crc >> 8);
+#else
+ i0 = *p8++ ^ (crc >> 24);
+ crc = t0_le[i0] ^ (crc << 8);
+#endif
+ }
+
+ p32--;
+
+ for (i = 0; i < words; i++) {
+#ifdef __LITTLE_ENDIAN
+ q = *++p32 ^ crc;
+ i3 = q;
+ i2 = q >> 8;
+ i1 = q >> 16;
+ i0 = q >> 24;
+ crc = t7_le[i3] ^ t6_le[i2] ^ t5_le[i1] ^ t4_le[i0];
+
+ q = *++p32;
+ i3 = q;
+ i2 = q >> 8;
+ i1 = q >> 16;
+ i0 = q >> 24;
+ crc ^= t3_le[i3] ^ t2_le[i2] ^ t1_le[i1] ^ t0_le[i0];
+#else
+ q = *++p32 ^ crc;
+ i3 = q >> 24;
+ i2 = q >> 16;
+ i1 = q >> 8;
+ i0 = q;
+ crc = t7_le[i3] ^ t6_le[i2] ^ t5_le[i1] ^ t4_le[i0];
+
+ q = *++p32;
+ i3 = q >> 24;
+ i2 = q >> 16;
+ i1 = q >> 8;
+ i0 = q;
+ crc ^= t3_le[i3] ^ t2_le[i2] ^ t1_le[i1] ^ t0_le[i0];
+#endif
+ }
+
+ p8 = (u8 *)(++p32);
+
+ for (i = 0; i < end_bytes; i++) {
+#ifdef __LITTLE_ENDIAN
+ i0 = *p8++ ^ crc;
+ crc = t0_le[i0] ^ (crc >> 8);
+#else
+ i0 = *p8++ ^ (crc >> 24);
+ crc = t0_le[i0] ^ (crc << 8);
+#endif
+ }
+
+ return __le32_to_cpu(crc);
+}
+#endif
+
+#if CRC_BE_BITS == 64
+static u32 crc32c_be_body(u32 crc, u8 const *buf, size_t len)
+{
+ const u8 *p8;
+ const u32 *p32;
+ size_t init_bytes;
+ size_t words;
+ size_t end_bytes;
+ size_t i;
+ u32 q;
+ u8 i0, i1, i2, i3;
+
+ crc = (__force u32) __cpu_to_be32(crc);
+
+ p8 = buf;
+ p32 = (u32 *)PTR_ALIGN(p8, 8);
+ init_bytes = min((uintptr_t)p32 - (uintptr_t)p8, len);
+ words = (len - init_bytes) >> 3;
+ end_bytes = (len - init_bytes) & 7;
+
+ for (i = 0; i < init_bytes; i++) {
+#ifdef __LITTLE_ENDIAN
+ i0 = *p8++ ^ crc;
+ crc = t0_be[i0] ^ (crc >> 8);
+#else
+ i0 = *p8++ ^ (crc >> 24);
+ crc = t0_be[i0] ^ (crc << 8);
+#endif
+ }
+
+ p32--;
+
+ for (i = 0; i < words; i++) {
+#ifdef __LITTLE_ENDIAN
+ q = *++p32 ^ crc;
+ i3 = q;
+ i2 = q >> 8;
+ i1 = q >> 16;
+ i0 = q >> 24;
+ crc = t7_be[i3] ^ t6_be[i2] ^ t5_be[i1] ^ t4_be[i0];
+
+ q = *++p32;
+ i3 = q;
+ i2 = q >> 8;
+ i1 = q >> 16;
+ i0 = q >> 24;
+ crc ^= t3_be[i3] ^ t2_be[i2] ^ t1_be[i1] ^ t0_be[i0];
+#else
+ q = *++p32 ^ crc;
+ i3 = q >> 24;
+ i2 = q >> 16;
+ i1 = q >> 8;
+ i0 = q;
+ crc = t7_be[i3] ^ t6_be[i2] ^ t5_be[i1] ^ t4_be[i0];
+
+ q = *++p32;
+ i3 = q >> 24;
+ i2 = q >> 16;
+ i1 = q >> 8;
+ i0 = q;
+ crc ^= t3_be[i3] ^ t2_be[i2] ^ t1_be[i1] ^ t0_be[i0];
+#endif
+ }
+
+ p8 = (u8 *)(++p32);
+
+ for (i = 0; i < end_bytes; i++) {
+#ifdef __LITTLE_ENDIAN
+ i0 = *p8++ ^ crc;
+ crc = t0_be[i0] ^ (crc >> 8);
+#else
+ i0 = *p8++ ^ (crc >> 24);
+ crc = t0_be[i0] ^ (crc << 8);
+#endif
+ }
+
+ return __be32_to_cpu(crc);
+}
+#endif
+
+/**
+ * crc32c_le() - Calculate bitwise little-endian CRC32c.
+ * @crc: seed value for computation. ~0 for ext4, sometimes 0 for
+ * other uses, or the previous crc32c value if computing incrementally.
+ * @p: pointer to buffer over which CRC is run
+ * @len: length of buffer @p
+ */
+static u32 crc32c_le(u32 crc, unsigned char const *p, size_t len)
+{
+#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);
+ }
+# elif CRC_LE_BITS == 2
+ while (len--) {
+ crc ^= *p++;
+ crc = (crc >> 2) ^ t0_le[crc & 0x03];
+ crc = (crc >> 2) ^ t0_le[crc & 0x03];
+ crc = (crc >> 2) ^ t0_le[crc & 0x03];
+ crc = (crc >> 2) ^ t0_le[crc & 0x03];
+ }
+# elif CRC_LE_BITS == 4
+ while (len--) {
+ crc ^= *p++;
+ crc = (crc >> 4) ^ t0_le[crc & 0x0f];
+ crc = (crc >> 4) ^ t0_le[crc & 0x0f];
+ }
+# elif CRC_LE_BITS == 8
+ while (len--) {
+ crc ^= *p++;
+ crc = (crc >> 8) ^ t0_le[crc & 0xff];
+ }
+# else
+ crc = crc32c_le_body(crc, p, len);
+# endif
+ return crc;
+}
+/**
+ * crc32c_be() - Calculate bitwise big-endian CRC32c.
+ * @crc: seed value for computation. ~0 for ext4, sometimes 0 for
+ * other uses, or the previous crc32c value if computing incrementally.
+ * @p: pointer to buffer over which CRC is run
+ * @len: length of buffer @p
+ */
+static u32 crc32c_be(u32 crc, unsigned char const *p, size_t len)
+{
+#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 : 0);
+ }
+# elif CRC_BE_BITS == 2
+ while (len--) {
+ crc ^= *p++ << 24;
+ crc = (crc << 2) ^ t0_be[crc >> 30];
+ crc = (crc << 2) ^ t0_be[crc >> 30];
+ crc = (crc << 2) ^ t0_be[crc >> 30];
+ crc = (crc << 2) ^ t0_be[crc >> 30];
+ }
+# elif CRC_BE_BITS == 4
+ while (len--) {
+ crc ^= *p++ << 24;
+ crc = (crc << 4) ^ t0_be[crc >> 28];
+ crc = (crc << 4) ^ t0_be[crc >> 28];
+ }
+# elif CRC_BE_BITS == 8
+ while (len--) {
+ crc ^= *p++ << 24;
+ crc = (crc << 8) ^ t0_be[crc >> 24];
+ }
+# else
+ crc = crc32c_be_body(crc, p, len);
+# endif
return crc;
}
@@ -146,7 +482,7 @@ static u32 crc32c(u32 crc, const u8 *data, unsigned int length)
* crc using table.
*/
-static int chksum_init(struct shash_desc *desc)
+static int crc32c_init(struct shash_desc *desc)
{
struct chksum_ctx *mctx = crypto_shash_ctx(desc->tfm);
struct chksum_desc_ctx *ctx = shash_desc_ctx(desc);
@@ -156,12 +492,21 @@ static int chksum_init(struct shash_desc *desc)
return 0;
}
+static int crc32c_cra_init(struct crypto_tfm *tfm)
+{
+ struct chksum_ctx *mctx = crypto_tfm_ctx(tfm);
+
+ mctx->key = ~0;
+ return 0;
+}
+
+/* Little Endian version of algorithm */
/*
* Setting the seed allows arbitrary accumulators and flexible XOR policy
* If your algorithm starts with ~0, then XOR with ~0 before you set
* the seed.
*/
-static int chksum_setkey(struct crypto_shash *tfm, const u8 *key,
+static int crc32c_le_setkey(struct crypto_shash *tfm, const u8 *key,
unsigned int keylen)
{
struct chksum_ctx *mctx = crypto_shash_ctx(tfm);
@@ -174,16 +519,16 @@ static int chksum_setkey(struct crypto_shash *tfm, const u8 *key,
return 0;
}
-static int chksum_update(struct shash_desc *desc, const u8 *data,
+static int crc32c_le_update(struct shash_desc *desc, const u8 *data,
unsigned int length)
{
struct chksum_desc_ctx *ctx = shash_desc_ctx(desc);
- ctx->crc = crc32c(ctx->crc, data, length);
+ ctx->crc = crc32c_le(ctx->crc, data, length);
return 0;
}
-static int chksum_final(struct shash_desc *desc, u8 *out)
+static int crc32c_le_final(struct shash_desc *desc, u8 *out)
{
struct chksum_desc_ctx *ctx = shash_desc_ctx(desc);
@@ -191,44 +536,96 @@ static int chksum_final(struct shash_desc *desc, u8 *out)
return 0;
}
-static int __chksum_finup(u32 *crcp, const u8 *data, unsigned int len, u8 *out)
+static int __crc32c_le_finup(u32 *crcp, const u8 *data, unsigned int len,
+ u8 *out)
{
- *(__le32 *)out = ~cpu_to_le32(crc32c(*crcp, data, len));
+ *(__le32 *)out = ~cpu_to_le32(crc32c_le(*crcp, data, len));
return 0;
}
-static int chksum_finup(struct shash_desc *desc, const u8 *data,
+static int crc32c_le_finup(struct shash_desc *desc, const u8 *data,
unsigned int len, u8 *out)
{
struct chksum_desc_ctx *ctx = shash_desc_ctx(desc);
- return __chksum_finup(&ctx->crc, data, len, out);
+ return __crc32c_le_finup(&ctx->crc, data, len, out);
}
-static int chksum_digest(struct shash_desc *desc, const u8 *data,
+static int crc32c_le_digest(struct shash_desc *desc, const u8 *data,
unsigned int length, u8 *out)
{
struct chksum_ctx *mctx = crypto_shash_ctx(desc->tfm);
- return __chksum_finup(&mctx->key, data, length, out);
+ return __crc32c_le_finup(&mctx->key, data, length, out);
}
-static int crc32c_cra_init(struct crypto_tfm *tfm)
+/* Big Endian version of algorithm */
+/*
+ * Setting the seed allows arbitrary accumulators and flexible XOR policy
+ * If your algorithm starts with ~0, then XOR with ~0 before you set
+ * the seed.
+ */
+static int crc32c_be_setkey(struct crypto_shash *tfm, const u8 *key,
+ unsigned int keylen)
{
- struct chksum_ctx *mctx = crypto_tfm_ctx(tfm);
+ struct chksum_ctx *mctx = crypto_shash_ctx(tfm);
- mctx->key = ~0;
+ if (keylen != sizeof(mctx->key)) {
+ crypto_shash_set_flags(tfm, CRYPTO_TFM_RES_BAD_KEY_LEN);
+ return -EINVAL;
+ }
+ mctx->key = be32_to_cpu(*(__be32 *)key);
return 0;
}
-static struct shash_alg alg = {
+static int crc32c_be_update(struct shash_desc *desc, const u8 *data,
+ unsigned int length)
+{
+ struct chksum_desc_ctx *ctx = shash_desc_ctx(desc);
+
+ ctx->crc = crc32c_be(ctx->crc, data, length);
+ return 0;
+}
+
+static int crc32c_be_final(struct shash_desc *desc, u8 *out)
+{
+ struct chksum_desc_ctx *ctx = shash_desc_ctx(desc);
+
+ *(__be32 *)out = ~cpu_to_be32p(&ctx->crc);
+ return 0;
+}
+
+static int __crc32c_be_finup(u32 *crcp, const u8 *data, unsigned int len,
+ u8 *out)
+{
+ *(__be32 *)out = ~cpu_to_be32(crc32c_be(*crcp, data, len));
+ return 0;
+}
+
+static int crc32c_be_finup(struct shash_desc *desc, const u8 *data,
+ unsigned int len, u8 *out)
+{
+ struct chksum_desc_ctx *ctx = shash_desc_ctx(desc);
+
+ return __crc32c_be_finup(&ctx->crc, data, len, out);
+}
+
+static int crc32c_be_digest(struct shash_desc *desc, const u8 *data,
+ unsigned int length, u8 *out)
+{
+ struct chksum_ctx *mctx = crypto_shash_ctx(desc->tfm);
+
+ return __crc32c_be_finup(&mctx->key, data, length, out);
+}
+
+static struct shash_alg alg_le = {
.digestsize = CHKSUM_DIGEST_SIZE,
- .setkey = chksum_setkey,
- .init = chksum_init,
- .update = chksum_update,
- .final = chksum_final,
- .finup = chksum_finup,
- .digest = chksum_digest,
+ .setkey = crc32c_le_setkey,
+ .init = crc32c_init,
+ .update = crc32c_le_update,
+ .final = crc32c_le_final,
+ .finup = crc32c_le_finup,
+ .digest = crc32c_le_digest,
.descsize = sizeof(struct chksum_desc_ctx),
.base = {
.cra_name = "crc32c",
@@ -242,14 +639,44 @@ static struct shash_alg alg = {
}
};
+static struct shash_alg alg_be = {
+ .digestsize = CHKSUM_DIGEST_SIZE,
+ .setkey = crc32c_be_setkey,
+ .init = crc32c_init,
+ .update = crc32c_be_update,
+ .final = crc32c_be_final,
+ .finup = crc32c_be_finup,
+ .digest = crc32c_be_digest,
+ .descsize = sizeof(struct chksum_desc_ctx),
+ .base = {
+ .cra_name = "crc32c-be",
+ .cra_driver_name = "crc32c-generic",
+ .cra_priority = 100,
+ .cra_blocksize = CHKSUM_BLOCK_SIZE,
+ .cra_alignmask = 3,
+ .cra_ctxsize = sizeof(struct chksum_ctx),
+ .cra_module = THIS_MODULE,
+ .cra_init = crc32c_cra_init,
+ }
+};
+
static int __init crc32c_mod_init(void)
{
- return crypto_register_shash(&alg);
+ int ret;
+
+ ret = crypto_register_shash(&alg_le);
+ if (ret)
+ return ret;
+ ret = crypto_register_shash(&alg_be);
+ if (ret)
+ crypto_unregister_shash(&alg_le);
+ return ret;
}
static void __exit crc32c_mod_fini(void)
{
- crypto_unregister_shash(&alg);
+ crypto_unregister_shash(&alg_be);
+ crypto_unregister_shash(&alg_le);
}
module_init(crc32c_mod_init);
diff --git a/crypto/crc32c_defs.h b/crypto/crc32c_defs.h
new file mode 100644
index 0000000..977df8f
--- /dev/null
+++ b/crypto/crc32c_defs.h
@@ -0,0 +1,34 @@
+/*
+ * 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 CRCPOLY_LE 0x82F63B78
+#define CRCPOLY_BE 0x1EDC6F41
+
+/* How many bits at a time to use. Valid values are 1, 2, 4, 8, 32 and 64. */
+/* For less performance-sensitive, use 4 */
+#ifndef CRC_LE_BITS
+# define CRC_LE_BITS 64
+#endif
+#ifndef CRC_BE_BITS
+# define CRC_BE_BITS 64
+#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 > 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 > 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
This is a loadable module that will self-test the CRC32c code.
Signed-off-by: Darrick J. Wong <[email protected]>
---
lib/Kconfig | 7 +
lib/Makefile | 1
lib/libcrc32c_test.c | 694 ++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 702 insertions(+), 0 deletions(-)
create mode 100644 lib/libcrc32c_test.c
diff --git a/lib/Kconfig b/lib/Kconfig
index 6c695ff..2bfdde8 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -79,6 +79,13 @@ config LIBCRC32C
require M here. See Castagnoli93.
Module will be libcrc32c.
+config LIBCRC32C_SELFTEST
+ tristate "CRC32c Self-Test"
+ depends on CRYPTO_CRC32C
+ help
+ This is a testing module that ensure that a crc32c implementation
+ is working correctly.
+
config CRC8
tristate "CRC8 function"
help
diff --git a/lib/Makefile b/lib/Makefile
index 3f5bc6d..79ca5ed 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -61,6 +61,7 @@ obj-$(CONFIG_CRC_ITU_T) += crc-itu-t.o
obj-$(CONFIG_CRC32) += crc32.o
obj-$(CONFIG_CRC7) += crc7.o
obj-$(CONFIG_LIBCRC32C) += libcrc32c.o
+obj-$(CONFIG_LIBCRC32C_SELFTEST) += libcrc32c_test.o
obj-$(CONFIG_CRC8) += crc8.o
obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
diff --git a/lib/libcrc32c_test.c b/lib/libcrc32c_test.c
new file mode 100644
index 0000000..8b5c75f
--- /dev/null
+++ b/lib/libcrc32c_test.c
@@ -0,0 +1,694 @@
+/*
+ * libcrc32c_test.c: Test buffer and checksums for crc32c.
+ */
+#include <linux/module.h>
+#include <linux/crc32c.h>
+
+static u8 test_buf[] = {
+ 0xd9, 0xd7, 0x6a, 0x13, 0x3a, 0xb1, 0x05, 0x48,
+ 0xda, 0xad, 0x14, 0xbd, 0x03, 0x3a, 0x58, 0x5e,
+ 0x6e, 0xd1, 0x56, 0xc9, 0x2e, 0xc4, 0xcb, 0x6b,
+ 0xe8, 0x77, 0x52, 0x37, 0x4e, 0x0f, 0x55, 0xd2,
+ 0x12, 0x65, 0x90, 0xc2, 0x41, 0x49, 0x81, 0x01,
+ 0xf5, 0x01, 0xeb, 0x2d, 0x78, 0x74, 0x23, 0x5d,
+ 0x84, 0x5c, 0x81, 0x92, 0x21, 0xe9, 0x8d, 0x1d,
+ 0x89, 0xf2, 0x4a, 0xac, 0xdd, 0xf9, 0xaf, 0xee,
+ 0x44, 0xe7, 0x6e, 0xed, 0xfb, 0xd8, 0x89, 0x0e,
+ 0x96, 0x62, 0xcd, 0xa4, 0x4b, 0xa9, 0xe5, 0x45,
+ 0xb1, 0x29, 0x9b, 0x0f, 0xfc, 0xbd, 0x83, 0xab,
+ 0xa8, 0x54, 0x96, 0x44, 0x2c, 0x7f, 0xbb, 0xe7,
+ 0x52, 0x29, 0x08, 0xee, 0x14, 0xc5, 0xc2, 0xec,
+ 0x5a, 0xeb, 0x40, 0x40, 0xea, 0xd1, 0x3d, 0x15,
+ 0x73, 0xaa, 0x8c, 0x73, 0xfc, 0xf2, 0x2b, 0x49,
+ 0x0b, 0x13, 0x96, 0xd9, 0x8e, 0x4b, 0xbc, 0xe0,
+ 0xf4, 0xd2, 0xe0, 0x2e, 0x7a, 0xf0, 0x5d, 0x1f,
+ 0xd2, 0x92, 0x97, 0xe0, 0xaa, 0x59, 0xab, 0xc9,
+ 0x5c, 0xa6, 0x51, 0x1a, 0xe3, 0xd6, 0x06, 0xb9,
+ 0xae, 0xb8, 0x76, 0x36, 0x79, 0x37, 0x52, 0xf6,
+ 0x34, 0xaf, 0x27, 0x19, 0xe1, 0xc0, 0x2b, 0xdd,
+ 0x01, 0x15, 0xcd, 0xce, 0x44, 0xf6, 0x4c, 0x18,
+ 0x92, 0x69, 0xbe, 0x8a, 0x76, 0x23, 0x52, 0x13,
+ 0x3f, 0xf9, 0xe0, 0xf5, 0x06, 0x28, 0x7c, 0xc7,
+ 0xf3, 0x42, 0x0f, 0xdd, 0x40, 0x33, 0xf7, 0x99,
+ 0xe2, 0xad, 0x26, 0xd9, 0x53, 0x10, 0x72, 0x0c,
+ 0x4e, 0x43, 0x4c, 0x61, 0xfe, 0xd9, 0xc1, 0x16,
+ 0xa1, 0x93, 0xca, 0x3c, 0x75, 0x7f, 0x07, 0x7a,
+ 0x65, 0xb3, 0x53, 0x2a, 0x52, 0x00, 0xa0, 0x62,
+ 0xe0, 0xa3, 0x1f, 0xad, 0xd7, 0xbb, 0xc0, 0x83,
+ 0x5d, 0x54, 0x87, 0x5f, 0xc8, 0x2f, 0xc8, 0xbf,
+ 0x69, 0x04, 0x91, 0xc8, 0xa6, 0x1d, 0x4d, 0x46,
+ 0x91, 0xfc, 0x26, 0xf4, 0x16, 0xd1, 0xa4, 0xbf,
+ 0x5c, 0xa2, 0x6c, 0xdd, 0xb4, 0x40, 0xf2, 0x2e,
+ 0xa2, 0xad, 0xf7, 0xf4, 0xa5, 0x8a, 0x3e, 0x23,
+ 0x64, 0x08, 0xc8, 0xa1, 0xa0, 0xf0, 0x5d, 0x70,
+ 0xd2, 0x77, 0xfd, 0xc8, 0x50, 0x83, 0x0f, 0xd6,
+ 0x2b, 0xe4, 0x1f, 0x52, 0x34, 0x33, 0x68, 0xfd,
+ 0x92, 0xbe, 0x9f, 0x97, 0x6b, 0x8d, 0x81, 0x91,
+ 0x0f, 0xef, 0x65, 0xc8, 0x0d, 0x15, 0x01, 0x77,
+ 0x58, 0xb2, 0xf4, 0x1b, 0x06, 0x7e, 0xf5, 0xca,
+ 0x15, 0x2e, 0x38, 0xd8, 0x81, 0x1c, 0x1c, 0xa0,
+ 0xb6, 0x13, 0x6a, 0x2b, 0x71, 0x34, 0x52, 0xd7,
+ 0x1d, 0xbd, 0x37, 0x59, 0xbc, 0x86, 0x25, 0x2b,
+ 0xa8, 0x93, 0xce, 0x1a, 0x03, 0x16, 0xfe, 0x01,
+ 0x57, 0x99, 0x24, 0x25, 0x2c, 0xb3, 0xab, 0x1e,
+ 0x2d, 0x65, 0x20, 0x89, 0x17, 0x02, 0x0e, 0x0a,
+ 0xf5, 0x1e, 0xc7, 0xff, 0x1f, 0x61, 0xa9, 0x54,
+ 0x18, 0xd4, 0xba, 0x50, 0x57, 0x02, 0xa1, 0xab,
+ 0x22, 0x2e, 0x07, 0xea, 0xa9, 0xa3, 0x83, 0x4f,
+ 0x27, 0xf5, 0xc5, 0xee, 0x3c, 0x3b, 0x10, 0xad,
+ 0x32, 0x2b, 0x1c, 0x03, 0xcb, 0xaf, 0x98, 0x83,
+ 0x54, 0xc3, 0x68, 0x63, 0xd4, 0xe0, 0x0e, 0x3c,
+ 0x1a, 0x4e, 0xc0, 0x81, 0xd0, 0xe8, 0x6a, 0x62,
+ 0x6b, 0x3e, 0x6f, 0xc4, 0xc6, 0x33, 0x4e, 0x26,
+ 0x21, 0xf5, 0x04, 0xdf, 0xfa, 0xce, 0x45, 0xaf,
+ 0xdc, 0x5e, 0x1b, 0xad, 0x93, 0xca, 0xf5, 0xcf,
+ 0xd7, 0xee, 0x0c, 0x5c, 0x5e, 0xb4, 0xf0, 0x92,
+ 0xd2, 0xf2, 0xf0, 0xa9, 0x1e, 0xab, 0x80, 0x68,
+ 0x46, 0xef, 0xcc, 0x26, 0x0c, 0x5c, 0xdd, 0x4e,
+ 0x83, 0xb8, 0xb9, 0x53, 0x6e, 0xf8, 0x93, 0x38,
+ 0x67, 0xa4, 0x41, 0x87, 0x72, 0xe7, 0x7e, 0x86,
+ 0xc9, 0x49, 0x00, 0x33, 0xb1, 0x38, 0x6c, 0x71,
+ 0xd7, 0x1d, 0x8e, 0x61, 0x01, 0xb6, 0x57, 0xa9,
+ 0xf1, 0xac, 0x15, 0xc2, 0x83, 0x77, 0xca, 0x64,
+ 0xca, 0x7b, 0x6c, 0xa1, 0x10, 0x1b, 0x13, 0xd0,
+ 0xd3, 0x9e, 0x9e, 0x10, 0x70, 0xc8, 0x1a, 0xbb,
+ 0x3f, 0x19, 0x86, 0xab, 0x01, 0x0e, 0xea, 0x34,
+ 0x22, 0xea, 0xe2, 0x15, 0xb7, 0xed, 0x21, 0x21,
+ 0x75, 0xa5, 0xe7, 0x08, 0xa1, 0x38, 0xe0, 0x91,
+ 0x05, 0x60, 0xea, 0xa7, 0x50, 0x27, 0x18, 0x07,
+ 0x9d, 0xe0, 0x18, 0x2b, 0xd4, 0x07, 0x59, 0x00,
+ 0xe6, 0x45, 0x18, 0x2a, 0x30, 0x6e, 0xf3, 0xb4,
+ 0xd0, 0xef, 0xa6, 0x5b, 0x71, 0xa2, 0x5a, 0x3b,
+ 0x89, 0x4c, 0xaf, 0x3f, 0xcb, 0x9f, 0x03, 0xfb,
+ 0x43, 0x7c, 0x6b, 0xd3, 0x6a, 0xea, 0xce, 0x4a,
+ 0x5f, 0x64, 0xb5, 0x62, 0xda, 0x5d, 0x27, 0xb7,
+ 0xb8, 0x11, 0xca, 0x33, 0x30, 0xec, 0x70, 0xf0,
+ 0x1b, 0x03, 0x50, 0xff, 0x5e, 0xa6, 0x08, 0xde,
+ 0x37, 0x70, 0xc0, 0x81, 0x55, 0x60, 0x17, 0xa1,
+ 0x85, 0xae, 0x26, 0x44, 0xe4, 0x67, 0x3c, 0x91,
+ 0xfd, 0xc4, 0x3d, 0x97, 0x72, 0x23, 0xf3, 0x3c,
+ 0x8f, 0xe0, 0xe2, 0xf2, 0x09, 0x96, 0x10, 0x67,
+ 0xb5, 0xfe, 0xff, 0x3d, 0x4a, 0xc8, 0x62, 0x11,
+ 0xa5, 0x98, 0xc1, 0x2d, 0x40, 0x82, 0x88, 0x8b,
+ 0xe5, 0xb0, 0x75, 0xbf, 0x2f, 0xa8, 0x6a, 0x55,
+ 0x49, 0x2e, 0x9c, 0x29, 0xd2, 0x7c, 0xbf, 0xf3,
+ 0xaa, 0x3a, 0x16, 0x4a, 0xa4, 0x15, 0xf3, 0x48,
+ 0xde, 0x38, 0x13, 0x44, 0x26, 0x02, 0xe6, 0xe9,
+ 0xa8, 0x24, 0x89, 0xb5, 0x43, 0x95, 0xe4, 0x4c,
+ 0xc3, 0xa0, 0xdf, 0xcc, 0x42, 0xf8, 0x8d, 0xb0,
+ 0x3b, 0xea, 0x10, 0xb7, 0xe1, 0x40, 0x54, 0xb9,
+ 0xa3, 0x2d, 0xfb, 0xb4, 0x91, 0xc0, 0x3e, 0x94,
+ 0xf1, 0xa1, 0x3c, 0xbe, 0xef, 0xb8, 0x70, 0x55,
+ 0x0a, 0x26, 0x93, 0xbf, 0xe6, 0x21, 0x92, 0x32,
+ 0x3c, 0x39, 0x27, 0x6a, 0x23, 0x48, 0x02, 0x35,
+ 0x3c, 0xd4, 0xcc, 0x04, 0xc0, 0x4e, 0xa7, 0x02,
+ 0x63, 0x37, 0xc2, 0xb8, 0x56, 0x1d, 0x57, 0x57,
+ 0x42, 0x04, 0x8d, 0xee, 0xcf, 0x8b, 0xc9, 0xc3,
+ 0xba, 0x3b, 0x15, 0xd7, 0xaf, 0xbf, 0x9e, 0xcd,
+ 0x44, 0xcf, 0xf0, 0x00, 0xb7, 0x3a, 0xfc, 0xa8,
+ 0x12, 0xab, 0x3a, 0x62, 0x01, 0x21, 0x46, 0xe9,
+ 0x1e, 0x48, 0x37, 0xfc, 0x13, 0x4d, 0xf6, 0x2a,
+ 0x72, 0x40, 0x75, 0x38, 0x71, 0xf2, 0x17, 0x20,
+ 0x2c, 0xdd, 0xc0, 0x49, 0xbc, 0x63, 0x33, 0xea,
+ 0x06, 0x75, 0x41, 0xe7, 0x5c, 0x1f, 0xfb, 0xf9,
+ 0x68, 0x83, 0xc2, 0x5a, 0x4a, 0x1e, 0x61, 0x08,
+ 0x57, 0xf3, 0x00, 0xba, 0x77, 0x92, 0x63, 0xa5,
+ 0xb7, 0xfe, 0x97, 0x22, 0xda, 0x5e, 0xd3, 0xaf,
+ 0xbc, 0x89, 0x0d, 0x4c, 0x37, 0xa9, 0x27, 0x4a,
+ 0x7f, 0xdb, 0x81, 0x39, 0x11, 0x86, 0x12, 0xf9,
+ 0x10, 0x50, 0xe4, 0xdb, 0x72, 0xf9, 0xae, 0x10,
+ 0x7c, 0xed, 0x50, 0x5c, 0x61, 0xeb, 0x42, 0x1e,
+ 0xa4, 0xf4, 0xf0, 0xfa, 0x45, 0x4d, 0x95, 0x2b,
+ 0xd4, 0x67, 0x4a, 0xe3, 0x8a, 0x15, 0x55, 0x92,
+ 0x77, 0x64, 0x8c, 0x51, 0x38, 0xf9, 0x26, 0x3e,
+ 0x68, 0xe2, 0xac, 0xbb, 0x64, 0x77, 0xe2, 0x82,
+ 0xa4, 0x42, 0x41, 0x38, 0xa0, 0xf0, 0xc9, 0xd8,
+ 0x6c, 0xe0, 0xef, 0x4c, 0xda, 0xb4, 0x92, 0xef,
+ 0x1b, 0xe3, 0x9b, 0xc1, 0x44, 0x3c, 0xb9, 0xb7,
+ 0x39, 0xac, 0x5c, 0x32, 0x39, 0xb4, 0x21, 0x85,
+ 0x93, 0xbc, 0xf2, 0x51, 0x43, 0xb7, 0xae, 0x1e,
+ 0x61, 0x9c, 0x38, 0x9c, 0xaa, 0xff, 0xde, 0xfc,
+ 0xbf, 0x85, 0xef, 0x17, 0x34, 0x36, 0x71, 0x5f,
+ 0x04, 0x16, 0xa6, 0x9e, 0xfd, 0x3a, 0x03, 0xd8,
+ 0xbf, 0x71, 0x70, 0x20, 0x8f, 0x7c, 0xfb, 0xff,
+ 0x61, 0xe0, 0xe2, 0x60, 0xa7, 0xb1, 0xc0, 0xe0,
+ 0xd9, 0x3f, 0xdc, 0x8d, 0x4a, 0xa4, 0x52, 0x61,
+ 0xaf, 0x9d, 0xdf, 0x8a, 0x0d, 0x41, 0xc0, 0x25,
+ 0x68, 0x12, 0x7b, 0xd5, 0xc7, 0xdb, 0x68, 0x70,
+ 0x2d, 0x7d, 0x95, 0x12, 0x03, 0x23, 0x0c, 0xe8,
+ 0x14, 0x41, 0x11, 0x28, 0xec, 0x9d, 0xd3, 0x28,
+ 0x77, 0x7a, 0x3c, 0x93, 0x8e, 0x5c, 0x7e, 0xb3,
+ 0x42, 0x9a, 0x18, 0x25, 0x93, 0xc8, 0xea, 0x43,
+ 0x1b, 0xbe, 0xd5, 0x27, 0xf1, 0xd4, 0xe0, 0x1e,
+ 0xce, 0xc7, 0xc7, 0x2c, 0x25, 0x35, 0x58, 0xb8,
+ 0x6c, 0xf3, 0xa2, 0xad, 0xe7, 0x58, 0x49, 0x47,
+ 0xf7, 0xca, 0xde, 0x8b, 0x81, 0xb7, 0x75, 0xf4,
+ 0x95, 0xa7, 0x5c, 0xc3, 0x2c, 0x0e, 0x1c, 0x52,
+ 0x9a, 0xc3, 0x2a, 0x00, 0x21, 0xa7, 0x51, 0x6b,
+ 0xf0, 0x05, 0x87, 0x8c, 0x42, 0x1b, 0xc3, 0x2e,
+ 0xa3, 0x76, 0x22, 0xd5, 0x7f, 0x56, 0x10, 0xef,
+ 0x98, 0x85, 0x65, 0x86, 0x71, 0x87, 0xd2, 0x8c,
+ 0xc0, 0x47, 0x20, 0xe8, 0xb5, 0x1c, 0xe3, 0xdd,
+ 0x3c, 0x5c, 0x03, 0xbb, 0x0e, 0x97, 0x3b, 0xe1,
+ 0x56, 0x9a, 0xd5, 0x0a, 0x63, 0xd5, 0x33, 0xaf,
+ 0x36, 0xca, 0xcf, 0x8f, 0x00, 0x28, 0xa3, 0x45,
+ 0xb8, 0xcd, 0xde, 0x73, 0xd4, 0xfa, 0x2d, 0x6f,
+ 0xdb, 0x93, 0xaa, 0xdd, 0x7f, 0xd2, 0x22, 0x9c,
+ 0x96, 0x48, 0x1e, 0xa8, 0x63, 0xbe, 0xbc, 0x0d,
+ 0x14, 0x3c, 0x2e, 0x11, 0x1f, 0xd2, 0xf4, 0x57,
+ 0xb3, 0x47, 0xf8, 0xa6, 0x1b, 0xc3, 0xa7, 0x95,
+ 0x2d, 0xd4, 0xca, 0xb8, 0x0d, 0xfb, 0x06, 0x85,
+ 0xda, 0x63, 0xf0, 0x3e, 0x9d, 0x5e, 0xee, 0xce,
+ 0xed, 0x74, 0x1d, 0x2c, 0x97, 0x3f, 0x71, 0x95,
+ 0x12, 0x03, 0xc5, 0x92, 0x46, 0x84, 0x1b, 0x07,
+ 0xe6, 0xb4, 0x1d, 0x3a, 0xf1, 0x89, 0x90, 0x50,
+ 0x10, 0x29, 0x34, 0xc0, 0x90, 0xbe, 0x4a, 0xa9,
+ 0x0d, 0xb0, 0x7b, 0xfb, 0x35, 0xee, 0x4e, 0x34,
+ 0xec, 0x5a, 0x58, 0xbc, 0xb8, 0xda, 0x38, 0x88,
+ 0x8c, 0x74, 0x1e, 0xc9, 0xab, 0x78, 0x2e, 0x2a,
+ 0x17, 0x8a, 0x43, 0x3d, 0xa1, 0x2a, 0x41, 0xb5,
+ 0xd6, 0xe8, 0x5b, 0xc5, 0x4a, 0x1c, 0x3c, 0x9f,
+ 0x8d, 0x3a, 0x69, 0x88, 0xf8, 0x80, 0xd2, 0x11,
+ 0xfc, 0x7e, 0x80, 0x8e, 0x7f, 0x85, 0x64, 0x9c,
+ 0x46, 0x58, 0xc8, 0x48, 0x98, 0x4b, 0xf5, 0x73,
+ 0x3f, 0x49, 0xce, 0x53, 0x2c, 0xd5, 0xfc, 0x33,
+ 0xf1, 0x6f, 0xd8, 0xe9, 0x2e, 0x70, 0x2e, 0xdc,
+ 0xe5, 0x43, 0x80, 0x38, 0xf2, 0x87, 0xed, 0x85,
+ 0xe4, 0x3e, 0x45, 0x14, 0x20, 0xcf, 0xa0, 0x61,
+ 0x4f, 0xe8, 0xd7, 0x5b, 0xb3, 0x0d, 0x0e, 0x4e,
+ 0x4d, 0xce, 0xbe, 0xba, 0xaa, 0x90, 0x09, 0xcb,
+ 0x4b, 0x5d, 0x08, 0xff, 0x52, 0xd5, 0x23, 0xbc,
+ 0xad, 0x8d, 0xd3, 0x06, 0x4a, 0xa0, 0x51, 0x56,
+ 0xa7, 0xd8, 0x33, 0xab, 0xbc, 0xd0, 0xdf, 0x92,
+ 0x87, 0x20, 0x2d, 0x7b, 0x5e, 0xfa, 0x30, 0xa7,
+ 0x06, 0x06, 0xe5, 0x4f, 0x2c, 0xb5, 0x61, 0xd7,
+ 0x54, 0xd3, 0xdf, 0xd0, 0x0a, 0xb0, 0x06, 0xce,
+ 0xf6, 0x86, 0xb7, 0x8e, 0xaa, 0x7b, 0x78, 0xd5,
+ 0xb9, 0xeb, 0x07, 0xac, 0x5f, 0xc5, 0xd2, 0x8c,
+ 0x40, 0xe0, 0x7f, 0x98, 0xd4, 0xe5, 0x4b, 0xca,
+ 0xfb, 0x47, 0xef, 0xef, 0xb9, 0x4d, 0x6d, 0x8f,
+ 0x82, 0x68, 0x74, 0x84, 0xe0, 0x0a, 0x93, 0x0f,
+ 0xb2, 0x01, 0xa9, 0x9f, 0x68, 0x6a, 0xe8, 0xf7,
+ 0xfb, 0x0b, 0xde, 0x17, 0xe0, 0x30, 0x38, 0x51,
+ 0xbc, 0x07, 0xb8, 0x2c, 0x91, 0x0f, 0xc1, 0x0e,
+ 0xa6, 0xf9, 0xf0, 0xd5, 0x48, 0x76, 0x8a, 0xde,
+ 0x74, 0xe3, 0x30, 0x65, 0x56, 0xb3, 0x5c, 0xe2,
+ 0x89, 0x8d, 0xda, 0x80, 0xad, 0x0f, 0x22, 0xfb,
+ 0x24, 0x1d, 0x16, 0xdd, 0x34, 0x4b, 0x90, 0x58,
+ 0x4e, 0x0c, 0x13, 0x28, 0xcf, 0x1d, 0xa4, 0xaa,
+ 0xb7, 0xf3, 0xb1, 0x66, 0xad, 0x3b, 0xcf, 0x79,
+ 0x12, 0x04, 0xd7, 0x79, 0xd9, 0x5f, 0xdf, 0x89,
+ 0xb2, 0x5b, 0xa7, 0x9a, 0x26, 0x1e, 0x67, 0x46,
+ 0x7c, 0x66, 0x95, 0x67, 0xe6, 0x45, 0x8b, 0x1f,
+ 0x65, 0x79, 0x9f, 0x6d, 0x11, 0x81, 0x17, 0x0d,
+ 0x11, 0xb0, 0x5c, 0xb4, 0xc7, 0x27, 0x87, 0xab,
+ 0x5d, 0x0a, 0x18, 0xae, 0x4e, 0x06, 0xa3, 0x3d,
+ 0xc7, 0xb0, 0x22, 0xba, 0x03, 0xa4, 0x0f, 0xe5,
+ 0x1c, 0x72, 0x2a, 0x04, 0xce, 0x83, 0xe9, 0xf3,
+ 0xd7, 0xc9, 0x67, 0x6c, 0x1e, 0x6b, 0x3c, 0x9b,
+ 0x0b, 0x5e, 0x6a, 0xa6, 0x79, 0x0a, 0xf1, 0xbe,
+ 0xd7, 0xb4, 0x6f, 0x45, 0x1e, 0xfb, 0x78, 0x97,
+ 0xaf, 0x34, 0x76, 0x95, 0x52, 0xf7, 0x3d, 0x5d,
+ 0x07, 0x28, 0x57, 0x9c, 0x4a, 0x0f, 0xcf, 0x0b,
+ 0x1b, 0xc4, 0xc2, 0x72, 0xd7, 0x72, 0x38, 0x9b,
+ 0xea, 0xeb, 0xee, 0xae, 0x34, 0xc8, 0x01, 0xd7,
+ 0xa5, 0xe3, 0xce, 0x41, 0xad, 0x02, 0x60, 0x23,
+ 0x18, 0x36, 0xba, 0x17, 0xfa, 0xcf, 0xe4, 0xda,
+ 0xdc, 0xfc, 0x82, 0xdc, 0x7c, 0x11, 0xf4, 0xb8,
+ 0x52, 0x5d, 0xf7, 0x2f, 0xc8, 0xfe, 0x4a, 0xe6,
+ 0xb9, 0xaf, 0x4b, 0x17, 0x18, 0x91, 0xc2, 0xfe,
+ 0xd7, 0x3a, 0x77, 0x0c, 0xa0, 0x43, 0x9c, 0x6f,
+ 0x13, 0x06, 0xbe, 0x6e, 0xe0, 0x1a, 0x3c, 0xf3,
+ 0xf5, 0xcc, 0x78, 0xfb, 0x5d, 0xd5, 0xda, 0xb7,
+ 0x58, 0xea, 0x86, 0x42, 0x6b, 0x32, 0xff, 0xb2,
+ 0xe2, 0xee, 0x03, 0x1f, 0xf4, 0xef, 0xdb, 0x53,
+ 0x79, 0xd5, 0x4e, 0xaf, 0x60, 0x8e, 0x02, 0xc2,
+ 0xcc, 0x39, 0x97, 0x7b, 0xfd, 0xa1, 0xf8, 0x7a,
+ 0x26, 0xe8, 0x55, 0xd6, 0xa4, 0x8b, 0xa0, 0x1b,
+ 0x2d, 0x63, 0xaa, 0x73, 0x71, 0x6e, 0xbf, 0x8b,
+ 0x3b, 0xe3, 0x1b, 0x0d, 0xbb, 0x2e, 0x44, 0x09,
+ 0x64, 0xac, 0xc7, 0x9e, 0xb5, 0xc6, 0x77, 0xb0,
+ 0x79, 0xb3, 0xaa, 0xfc, 0x67, 0x57, 0x9a, 0x50,
+ 0x81, 0x37, 0x14, 0x7c, 0xd7, 0xa0, 0xd4, 0x6a,
+ 0x79, 0x84, 0x51, 0x0e, 0x95, 0x0a, 0x30, 0xa3,
+ 0x60, 0x55, 0x48, 0x05, 0x16, 0xae, 0x43, 0x90,
+ 0xdc, 0x8e, 0x09, 0xbe, 0x79, 0xf6, 0x90, 0x74,
+ 0xf8, 0x20, 0x96, 0x4d, 0xa7, 0xf5, 0x1a, 0x2b,
+ 0xc7, 0x15, 0x9d, 0x18, 0xf7, 0x94, 0x87, 0xf7,
+ 0xf4, 0xfb, 0x0d, 0x61, 0xb6, 0xd7, 0xbe, 0x10,
+ 0x8e, 0x47, 0x3c, 0x10, 0x44, 0x90, 0x52, 0x21,
+ 0x83, 0xc0, 0xf5, 0x99, 0xaa, 0xbc, 0xf6, 0x55,
+ 0xae, 0xf5, 0xb2, 0xa4, 0xcd, 0x4d, 0xb9, 0x38,
+ 0x6c, 0xbc, 0x80, 0xc3, 0xad, 0xf4, 0x46, 0x31,
+ 0x01, 0x58, 0x2d, 0x88, 0x57, 0xc3, 0x23, 0xd1,
+ 0x64, 0xc9, 0xa3, 0x21, 0x6b, 0x8b, 0x8a, 0x23,
+ 0x2c, 0x4f, 0xa9, 0xcd, 0x67, 0xfa, 0x77, 0xad,
+ 0xa3, 0x16, 0xa2, 0xe5, 0x19, 0x14, 0x70, 0x41,
+ 0x5b, 0xda, 0x14, 0xde, 0xe3, 0xe5, 0xc1, 0x15,
+ 0xb4, 0x77, 0xa4, 0x9b, 0xb8, 0xb1, 0x28, 0x51,
+ 0x30, 0xb4, 0xf1, 0xf3, 0xf8, 0x6d, 0xd0, 0xc3,
+ 0x8c, 0x4c, 0x76, 0xb0, 0x9a, 0xdf, 0xc8, 0xbe,
+ 0xf8, 0x4a, 0x61, 0x6e, 0x3e, 0xd6, 0x3c, 0xe8,
+ 0xde, 0x56, 0xa0, 0x9c, 0x25, 0xbe, 0xce, 0x93,
+ 0x1f, 0x88, 0xfb, 0x9a, 0x1a, 0xe2, 0xff, 0x88,
+ 0xad, 0x10, 0xcb, 0x6c, 0xd6, 0xe7, 0x39, 0x0b,
+ 0xe5, 0x1a, 0x06, 0x05, 0x64, 0x5b, 0x0a, 0xdf,
+ 0x22, 0x58, 0xd7, 0xfb, 0x88, 0x12, 0xdd, 0xb7,
+ 0x52, 0x3a, 0xc9, 0xbf, 0x49, 0xdf, 0x8c, 0x87,
+ 0x9f, 0x84, 0xb5, 0x0a, 0xf6, 0x00, 0x52, 0xae,
+ 0x67, 0x12, 0x1a, 0x8c, 0x71, 0x15, 0xf5, 0xa1,
+ 0x13, 0x39, 0xf0, 0x91, 0x7e, 0x88, 0x7c, 0xb3,
+ 0x95, 0x50, 0x02, 0xa6, 0x63, 0xb5, 0x64, 0xfb,
+ 0x90, 0x87, 0x61, 0xe2, 0x27, 0xaf, 0x11, 0x0c,
+ 0x73, 0x83, 0xef, 0xa9, 0x28, 0xfe, 0xc8, 0x85,
+ 0x1a, 0x3a, 0xde, 0xf2, 0xe5, 0x25, 0x64, 0x6d,
+ 0xaa, 0x41, 0x4c, 0x80, 0x2e, 0x84, 0xff, 0xc1,
+ 0xc0, 0x54, 0x0c, 0x29, 0x1b, 0xa3, 0x07, 0x7c,
+ 0x33, 0x4c, 0x10, 0xf6, 0x6f, 0x79, 0xdf, 0xd3,
+ 0xf0, 0x24, 0x57, 0xf1, 0x60, 0xe1, 0xf0, 0xbd,
+ 0xc4, 0x1f, 0xf4, 0x67, 0xd2, 0xd3, 0xcc, 0x6a,
+ 0x07, 0x72, 0x44, 0x16, 0x85, 0x46, 0xd0, 0x73,
+ 0x87, 0xa9, 0xc7, 0x2f, 0xd1, 0xf5, 0xec, 0xe3,
+ 0x28, 0xa3, 0x93, 0x4f, 0xd7, 0x76, 0xc1, 0x3c,
+ 0x0d, 0x13, 0x33, 0xcf, 0x5b, 0xbd, 0x6a, 0x52,
+ 0x4e, 0xee, 0xc8, 0x5e, 0xa1, 0x58, 0x4a, 0x08,
+ 0x81, 0xd9, 0x23, 0xcc, 0xfb, 0x1c, 0xb2, 0xd8,
+ 0xa3, 0xe4, 0x53, 0xfe, 0xf4, 0x4b, 0x48, 0xc1,
+ 0x20, 0xa4, 0x97, 0xf8, 0x38, 0xa3, 0x69, 0xc1,
+ 0x11, 0xf0, 0xa1, 0x3b, 0xa9, 0x9a, 0x12, 0x61,
+ 0xe8, 0x8d, 0x99, 0x44, 0x3f, 0x94, 0x72, 0x82,
+ 0x19, 0x96, 0x62, 0xb0, 0xa6, 0x64, 0x05, 0x19,
+ 0x8f, 0xd6, 0x5d, 0x05, 0xbf, 0x79, 0x9e, 0x9d,
+ 0xe4, 0x93, 0x4c, 0xad, 0x61, 0x8c, 0x18, 0xda,
+ 0xb6, 0x2e, 0xb3, 0xca, 0x14, 0x4d, 0x53, 0xa4,
+ 0x97, 0x27, 0x10, 0x56, 0xa2, 0x67, 0x5a, 0x5a,
+ 0x5e, 0x13, 0xc0, 0xdb, 0xa7, 0x9f, 0x45, 0x5b,
+ 0xeb, 0x1a, 0x14, 0x0c, 0x8c, 0x38, 0x5e, 0x77,
+ 0x9a, 0xec, 0x75, 0x68, 0x93, 0x65, 0x02, 0x9c,
+ 0xfb, 0x62, 0x60, 0x49, 0xdd, 0xb2, 0x2a, 0x67,
+ 0x86, 0xe3, 0x8a, 0x7d, 0x8c, 0x46, 0x78, 0x81,
+ 0x60, 0x69, 0xf2, 0x3f, 0x74, 0x11, 0x35, 0xff,
+ 0x77, 0xa3, 0x66, 0x20, 0xfc, 0x98, 0x4a, 0x35,
+ 0x7a, 0x52, 0xe4, 0x90, 0x13, 0x80, 0xb9, 0xa6,
+ 0x73, 0x7a, 0x7d, 0x66, 0x6e, 0x6b, 0xb6, 0x43,
+ 0x10, 0xd5, 0x91, 0x2b, 0x66, 0xdd, 0x89, 0x87,
+ 0xe3, 0x8c, 0x58, 0x53, 0x2f, 0x40, 0x74, 0x45,
+ 0x1b, 0x77, 0x7a, 0xa4, 0x44, 0x19, 0x78, 0xba,
+ 0x87, 0x10, 0x41, 0x31, 0x32, 0x5f, 0x87, 0x68,
+ 0xde, 0x43, 0x4a, 0xef, 0x33, 0xb3, 0x11, 0x83,
+ 0xa9, 0xc2, 0x6f, 0x8d, 0x34, 0xe2, 0x95, 0x84,
+ 0x3a, 0x4f, 0x6f, 0x8c, 0x31, 0x1d, 0xb6, 0xf5,
+ 0x95, 0x0d, 0x01, 0x11, 0x20, 0xdf, 0x72, 0xf3,
+ 0x3f, 0x9a, 0x33, 0xaa, 0xb1, 0x06, 0x6a, 0x63,
+ 0x47, 0x91, 0x01, 0xdf, 0xb3, 0x54, 0x36, 0xfd,
+ 0x06, 0x2d, 0xb8, 0x08, 0xe3, 0xd3, 0x65, 0xac,
+ 0x66, 0x03, 0xee, 0xa4, 0x63, 0xbd, 0xd4, 0xce,
+ 0xbd, 0x79, 0xa7, 0x48, 0x38, 0xc5, 0x7d, 0xb5,
+ 0x71, 0x9a, 0x3c, 0x11, 0x7c, 0x6c, 0xe2, 0x54,
+ 0x02, 0x5d, 0x42, 0xab, 0x25, 0x93, 0x66, 0x01,
+ 0x37, 0x78, 0x35, 0x4a, 0x8c, 0x19, 0x4d, 0x00,
+ 0x75, 0x4f, 0xcc, 0xc0, 0x26, 0x82, 0xc1, 0x35,
+ 0x8c, 0xc7, 0xc2, 0x59, 0x01, 0x3e, 0x98, 0x22,
+ 0x88, 0x9c, 0x90, 0x75, 0x05, 0x33, 0x07, 0xb9,
+ 0x39, 0x81, 0x38, 0x58, 0x10, 0x29, 0xcf, 0xc8,
+ 0x98, 0xb2, 0x03, 0xd7, 0x5b, 0xb3, 0x18, 0xba,
+ 0x34, 0x0c, 0x9f, 0xab, 0xd7, 0xed, 0x29, 0x82,
+ 0x41, 0xe0, 0x20, 0x97, 0x57, 0x92, 0xb2, 0xb8,
+ 0x10, 0x2d, 0x0b, 0xa2, 0xc5, 0x8f, 0x90, 0x6f,
+ 0xed, 0x12, 0x56, 0x25, 0xbe, 0xfd, 0x75, 0xf7,
+ 0xb6, 0xf8, 0x40, 0x67, 0x39, 0x11, 0xfa, 0x15,
+ 0xae, 0x6a, 0x54, 0x5f, 0x32, 0x2b, 0xf8, 0x48,
+ 0x55, 0xbe, 0x86, 0x2f, 0x69, 0x48, 0x5b, 0x5d,
+ 0x4d, 0xb7, 0x35, 0xaa, 0xb6, 0x91, 0x88, 0x19,
+ 0x96, 0x1c, 0x68, 0xf6, 0x85, 0x9e, 0xb3, 0xb2,
+ 0xa3, 0x32, 0xd4, 0x52, 0x70, 0xb7, 0x62, 0xe3,
+ 0x14, 0xb6, 0x78, 0x5f, 0x1b, 0x1d, 0x04, 0x9c,
+ 0x26, 0x0c, 0x33, 0x94, 0xb1, 0x97, 0x08, 0xdb,
+ 0x0b, 0x39, 0x29, 0xd4, 0xbc, 0x6d, 0xdf, 0x02,
+ 0xc6, 0x99, 0xab, 0x99, 0x32, 0xe5, 0xce, 0x51,
+ 0x4f, 0xae, 0xb8, 0x8b, 0xe0, 0xaf, 0x07, 0xc4,
+ 0xf9, 0x41, 0x7c, 0x59, 0xa0, 0xac, 0x74, 0x4d,
+ 0x7e, 0x43, 0x77, 0x9c, 0x06, 0x49, 0x79, 0x8a,
+ 0x14, 0x73, 0x93, 0xa8, 0x5b, 0x1b, 0x34, 0x29,
+ 0x78, 0x04, 0x2f, 0xd7, 0x1f, 0x13, 0x90, 0xe0,
+ 0xdd, 0x3b, 0x42, 0x6b, 0x79, 0x6e, 0x52, 0xc7,
+ 0x0f, 0x38, 0xda, 0x01, 0x2c, 0x8d, 0xe6, 0x94,
+ 0x5d, 0x59, 0x27, 0x1d, 0x10, 0x4e, 0x11, 0x36,
+ 0xfb, 0x53, 0x16, 0x05, 0x25, 0xf2, 0x64, 0xd8,
+ 0xf9, 0xcd, 0x5c, 0xfe, 0xb4, 0x18, 0x44, 0x80,
+ 0x10, 0xbc, 0x3d, 0xf3, 0x1d, 0x5a, 0xf0, 0xc1,
+ 0xc3, 0x55, 0xff, 0x41, 0x3e, 0xe3, 0xef, 0x44,
+ 0xb2, 0xc0, 0x01, 0x18, 0xa2, 0x49, 0x88, 0x78,
+ 0x0d, 0x4c, 0xc8, 0x73, 0xcf, 0x30, 0x85, 0x3a,
+ 0x88, 0x90, 0x01, 0xcf, 0x69, 0x53, 0xa3, 0x18,
+ 0x3f, 0xd6, 0xe7, 0x94, 0x14, 0xa7, 0xae, 0xcd,
+ 0x6f, 0x11, 0x72, 0xfe, 0x2b, 0xb0, 0x81, 0x53,
+ 0xea, 0x67, 0xd6, 0xe4, 0xca, 0x42, 0xa0, 0xf9,
+ 0xb1, 0xd4, 0xb5, 0x3b, 0xc9, 0xf0, 0x36, 0xc1,
+ 0x1c, 0xf4, 0xb1, 0xf6, 0x84, 0xd0, 0x86, 0x6c,
+ 0x76, 0x9a, 0x03, 0xc2, 0xb6, 0x2e, 0x9a, 0x46,
+ 0xf5, 0x5f, 0x2c, 0x38, 0xac, 0xad, 0x6f, 0x2e,
+ 0x7a, 0x18, 0x2d, 0x22, 0x95, 0x5e, 0x5e, 0xc9,
+ 0x7a, 0x0a, 0x56, 0xe1, 0xc7, 0x15, 0xfd, 0xbf,
+ 0xff, 0xf7, 0x7e, 0x85, 0x20, 0xa9, 0x8a, 0x9c,
+ 0xa9, 0x7d, 0xe8, 0xed, 0xfc, 0x7f, 0xbb, 0xf0,
+ 0x05, 0x3f, 0xce, 0x4f, 0x4c, 0xee, 0xa4, 0xa0,
+ 0xcc, 0x9c, 0x62, 0x1e, 0xd6, 0xd0, 0x30, 0x37,
+ 0xb8, 0x98, 0x56, 0x1d, 0xaa, 0xd6, 0x5e, 0x73,
+ 0x12, 0xe4, 0x88, 0x82, 0x48, 0x64, 0x06, 0xd7,
+ 0x2a, 0x31, 0x50, 0x7b, 0x10, 0x17, 0xb8, 0x4c,
+ 0x5a, 0x8d, 0xf1, 0xfc, 0xf1, 0x33, 0x3b, 0x98,
+ 0x42, 0x18, 0x5b, 0x35, 0x78, 0xca, 0x8e, 0x41,
+ 0x52, 0xae, 0x6d, 0xe1, 0xa2, 0x9d, 0x5b, 0xbd,
+ 0xf3, 0x5f, 0x49, 0xc1, 0x27, 0x06, 0xc1, 0xaf,
+ 0xc0, 0xa3, 0x9d, 0xf3, 0x1c, 0x8e, 0x90, 0x8a,
+ 0xb0, 0x69, 0xb0, 0xc5, 0x11, 0x0c, 0x91, 0x14,
+ 0x1f, 0x5e, 0x10, 0xe1, 0x1d, 0x14, 0x30, 0x54,
+ 0x1e, 0x17, 0x3d, 0x31, 0x7b, 0xbf, 0x2f, 0x9d,
+ 0x6d, 0x63, 0x32, 0xf0, 0x9d, 0x9f, 0x95, 0x3d,
+ 0x0b, 0xd2, 0x4d, 0x10, 0xe2, 0x3f, 0x67, 0x69,
+ 0x43, 0x9a, 0x4a, 0x2c, 0x54, 0x71, 0xa8, 0xa0,
+ 0x9e, 0x9f, 0x10, 0xaf, 0x1b, 0xce, 0x99, 0xe3,
+ 0x25, 0x32, 0x10, 0x54, 0x80, 0xfe, 0xda, 0x57,
+ 0xd0, 0xb2, 0x92, 0x7f, 0xbb, 0x5f, 0xe7, 0x4d,
+ 0x1b, 0x3d, 0x46, 0x4d, 0xe4, 0x4c, 0xd6, 0xaf,
+ 0x1a, 0x32, 0x12, 0x40, 0xb8, 0x84, 0x8e, 0xe4,
+ 0x80, 0xce, 0x7e, 0xc1, 0x13, 0x8b, 0xb0, 0xb7,
+ 0x6f, 0x24, 0xba, 0x85, 0x50, 0x83, 0xc3, 0xcf,
+ 0x19, 0xb3, 0xf0, 0xc7, 0xee, 0x68, 0xbe, 0x9e,
+ 0x6d, 0xb9, 0xfb, 0xd5, 0x29, 0xce, 0x82, 0xcd,
+ 0x69, 0x16, 0x68, 0x6b, 0x6a, 0xf4, 0x02, 0x32,
+ 0xce, 0x60, 0x37, 0x0c, 0xb9, 0x38, 0x92, 0x9c,
+ 0x42, 0xa9, 0x0b, 0x53, 0x96, 0xfe, 0x39, 0xc1,
+ 0x24, 0x65, 0x9b, 0xcd, 0xe7, 0x8d, 0x36, 0x07,
+ 0x9f, 0x1d, 0x35, 0x8e, 0xdc, 0x4c, 0xb5, 0x68,
+ 0xc5, 0xfd, 0x44, 0x19, 0xf2, 0x6c, 0x59, 0x1c,
+ 0xb1, 0x0b, 0x35, 0x48, 0x86, 0x1a, 0x05, 0x22,
+ 0x03, 0x0c, 0x0c, 0xa2, 0x92, 0x90, 0x35, 0xfb,
+ 0x37, 0x94, 0xc7, 0x15, 0x84, 0xae, 0xe8, 0x05,
+ 0xa0, 0xf7, 0x30, 0x11, 0x5c, 0xe4, 0x5d, 0x3e,
+ 0x12, 0x54, 0x80, 0x54, 0x6b, 0x09, 0x8c, 0xce,
+ 0x80, 0x5e, 0xa7, 0xc8, 0x6a, 0x0c, 0x56, 0xe1,
+ 0x18, 0x7d, 0xc9, 0x39, 0xc1, 0xef, 0xe3, 0x25,
+ 0xa0, 0x8b, 0x2f, 0x60, 0x3a, 0x43, 0x39, 0xa6,
+ 0x28, 0x28, 0x7b, 0x4c, 0x77, 0xd4, 0x49, 0x61,
+ 0x46, 0xe9, 0x1b, 0x45, 0xd6, 0xb1, 0x56, 0xe1,
+ 0x7d, 0x34, 0xcd, 0x06, 0xb6, 0x67, 0x8d, 0x7d,
+ 0x7a, 0xe2, 0xbe, 0x68, 0x35, 0xa6, 0x78, 0xe5,
+ 0x47, 0x48, 0xb7, 0xc7, 0xde, 0xcd, 0xc9, 0x05,
+ 0xb4, 0xe7, 0x50, 0x48, 0xe1, 0x4b, 0xfe, 0x76,
+ 0x77, 0xc6, 0xf7, 0x5f, 0xcb, 0xc2, 0xa8, 0xd7,
+ 0xd6, 0x8a, 0xe5, 0x49, 0xd9, 0xca, 0x45, 0xf4,
+ 0xda, 0xcd, 0x33, 0xd1, 0x59, 0x2d, 0x9e, 0xc1,
+ 0x5c, 0xe6, 0x01, 0x18, 0xb8, 0xf0, 0x5e, 0xb1,
+ 0x69, 0x95, 0x2f, 0x02, 0x2a, 0xe7, 0x4a, 0xd7,
+ 0xd1, 0xc3, 0xd5, 0x6f, 0x15, 0xc8, 0xdc, 0x29,
+ 0xde, 0xb9, 0x3f, 0x8b, 0xa6, 0xbc, 0xdd, 0x25,
+ 0x84, 0x35, 0x3c, 0x90, 0x2d, 0xc2, 0x1e, 0x98,
+ 0x8a, 0x50, 0x09, 0x77, 0x42, 0xe9, 0x35, 0x8a,
+ 0x7c, 0x97, 0xbf, 0xe8, 0xbf, 0x56, 0xd0, 0x8b,
+ 0x65, 0xd3, 0xaf, 0x1e, 0x05, 0x94, 0xfa, 0xac,
+ 0xa8, 0x2b, 0x28, 0xcb, 0x37, 0x3e, 0xe8, 0xbb,
+ 0x66, 0x3a, 0xed, 0xb2, 0x48, 0x10, 0x0f, 0x3a,
+ 0x5a, 0xc5, 0xdb, 0x26, 0x0e, 0xaa, 0x5e, 0x69,
+ 0x15, 0xd6, 0x81, 0xae, 0xbd, 0xe6, 0x03, 0xf1,
+ 0xf6, 0x37, 0xc8, 0xde, 0x70, 0x1f, 0x64, 0xb9,
+ 0x5e, 0xbf, 0x2e, 0x4f, 0xb1, 0xea, 0xa0, 0x17,
+ 0xe6, 0x7c, 0xf9, 0x2f, 0x1e, 0xd8, 0x58, 0xde,
+ 0xa7, 0xf0, 0x46, 0x52, 0x95, 0xdf, 0xa4, 0x96,
+ 0xd0, 0xc4, 0x97, 0x2b, 0x95, 0xcd, 0x5e, 0x40,
+ 0x23, 0x5c, 0x10, 0xee, 0xba, 0x72, 0x9b, 0xcf,
+ 0x0b, 0xe8, 0x18, 0x3a, 0x70, 0xd2, 0x5e, 0x07,
+ 0x68, 0x93, 0xef, 0x4a, 0x5b, 0x8d, 0x72, 0x41,
+ 0x4e, 0xea, 0x33, 0x6a, 0x0a, 0x5e, 0xfb, 0x02,
+ 0x3f, 0xd4, 0xed, 0x5b, 0xe0, 0x42, 0x84, 0xd4,
+ 0xaa, 0x85, 0xdc, 0x5b, 0x67, 0xee, 0x71, 0x67,
+ 0xba, 0x8e, 0xd2, 0xbe, 0x61, 0xdf, 0x5a, 0x26,
+ 0xb9, 0xf0, 0x77, 0x81, 0x53, 0x24, 0x16, 0xcb,
+ 0x8c, 0xb8, 0x06, 0x6e, 0x68, 0xda, 0xc8, 0x2d,
+ 0x17, 0x54, 0xdb, 0x46, 0xcb, 0xfd, 0x1f, 0x3d,
+ 0x94, 0x81, 0x09, 0x4b, 0xfa, 0xb1, 0x46, 0xd9,
+ 0x11, 0xa3, 0xb7, 0x31, 0x9c, 0xd2, 0x38, 0xd6,
+ 0xba, 0x3d, 0xa3, 0x74, 0xd8, 0xf1, 0x24, 0xe8,
+ 0x9c, 0xcb, 0x1d, 0xf9, 0x4a, 0xf7, 0xc8, 0x4b,
+ 0xfe, 0x97, 0x7c, 0xa1, 0x02, 0xeb, 0x40, 0xc3,
+ 0x89, 0x71, 0x01, 0xcd, 0x33, 0x2a, 0xc2, 0x82,
+ 0xce, 0x62, 0x8d, 0x53, 0x7c, 0xdf, 0xce, 0xd7,
+ 0xf5, 0xa8, 0x4f, 0xf2, 0xf2, 0x2e, 0xc1, 0xeb,
+ 0x97, 0x99, 0x37, 0x3c, 0x53, 0xa6, 0xb4, 0x46,
+ 0x05, 0x64, 0x92, 0x87, 0x08, 0x3c, 0x23, 0x4b,
+ 0x9d, 0x67, 0x18, 0xf9, 0xe2, 0x0b, 0x1c, 0x39,
+ 0xd3, 0x87, 0x70, 0xc0, 0xb9, 0x1e, 0x52, 0x0a,
+ 0x0f, 0x48, 0xe2, 0xe7, 0x51, 0x72, 0x94, 0xf7,
+ 0xa3, 0xdc, 0xe5, 0x66, 0x33, 0x39, 0x54, 0x06,
+ 0x55, 0x93, 0x30, 0xf9, 0x5e, 0x76, 0x8f, 0xe0,
+ 0x59, 0x4d, 0x0d, 0xa7, 0xf5, 0xbe, 0xdb, 0x20,
+ 0xad, 0x0d, 0x76, 0x88, 0x5f, 0x9c, 0x7c, 0x75,
+ 0x2f, 0x2a, 0x0b, 0x79, 0x6e, 0xd3, 0xe2, 0x66,
+ 0xf5, 0x4a, 0x2d, 0x87, 0x87, 0x49, 0x84, 0x17,
+ 0xa2, 0x62, 0x4c, 0xbb, 0xe4, 0x6e, 0x98, 0x10,
+ 0xc9, 0xfb, 0x8a, 0x04, 0x68, 0x8d, 0x22, 0x66,
+ 0xad, 0xea, 0x2a, 0xc9, 0x97, 0x2d, 0x3c, 0xbc,
+ 0xd0, 0x77, 0x5f, 0xe6, 0xb8, 0x7f, 0xe6, 0xf6,
+ 0x39, 0xbf, 0x56, 0x0e, 0x26, 0x6d, 0xc5, 0x3e,
+ 0x53, 0x19, 0xd6, 0xb4, 0x57, 0x36, 0xa3, 0xc6,
+ 0xd3, 0x3d, 0x66, 0x79, 0x30, 0x5c, 0x14, 0x0c,
+ 0x0f, 0x3e, 0x96, 0xae, 0x90, 0x97, 0xab, 0x0d,
+ 0x9f, 0xc3, 0xe7, 0x66, 0x3e, 0xe0, 0x31, 0x43,
+ 0x4b, 0x01, 0xb3, 0x0e, 0x9e, 0x8c, 0x82, 0x4a,
+ 0x8c, 0xc7, 0x79, 0x85, 0xdf, 0x75, 0x0d, 0xb4,
+ 0x2b, 0x03, 0x14, 0xef, 0x72, 0x58, 0xfd, 0x64,
+ 0xc8, 0xe3, 0x0d, 0x9a, 0x14, 0x6f, 0x76, 0xf9,
+ 0x46, 0xd1, 0xd2, 0x81, 0xb3, 0x16, 0x6e, 0xc7,
+ 0x76, 0x82, 0xce, 0xf4, 0xee, 0x33, 0x00, 0xe6,
+ 0x77, 0xc4, 0xad, 0x4f, 0x06, 0xa7, 0x48, 0x80,
+ 0x9e, 0x21, 0x66, 0xca, 0x75, 0x69, 0x57, 0xcb,
+ 0xf0, 0x67, 0x6a, 0xaa, 0x8f, 0x88, 0x14, 0xbd,
+ 0x65, 0x62, 0xe2, 0xad, 0xcc, 0x22, 0x88, 0x7b,
+ 0x94, 0xbd, 0x0e, 0xcd, 0xb6, 0x69, 0xa2, 0xcb,
+ 0x7d, 0x57, 0x5c, 0xb4, 0x92, 0x80, 0x13, 0x99,
+ 0x84, 0xf3, 0x79, 0x0a, 0x2d, 0x70, 0xa4, 0xe0,
+ 0xde, 0xc6, 0x32, 0xb0, 0x8a, 0x62, 0xb5, 0xcf,
+ 0xfa, 0x5e, 0x5a, 0x92, 0x32, 0x7d, 0x34, 0x07,
+ 0xb5, 0x52, 0x3a, 0xb5, 0x7d, 0x0f, 0xa1, 0xba,
+ 0x56, 0xd0, 0x07, 0x76, 0x11, 0xf2, 0xc3, 0x33,
+ 0x9d, 0xbd, 0x12, 0x35, 0x5e, 0xf7, 0x05, 0x88,
+ 0x76, 0x94, 0xa6, 0xbf, 0xed, 0xb8, 0xa4, 0xa2,
+ 0x0c, 0xbe, 0x0f, 0x6a, 0xaf, 0xf3, 0x1b, 0x33,
+ 0x4a, 0xb7, 0x68, 0x3f, 0xbe, 0x95, 0x13, 0x97,
+ 0x0f, 0x15, 0x17, 0x1b, 0x23, 0xaa, 0x08, 0x78,
+ 0xa6, 0x5b, 0x08, 0xa2, 0x9d, 0x03, 0xa8, 0xa7,
+ 0x39, 0xdc, 0xbc, 0x9a, 0x85, 0xf5, 0xe5, 0x55,
+ 0x59, 0x3c, 0xef, 0xf9, 0x3f, 0x22, 0x8e, 0xf8,
+ 0xd8, 0x3e, 0x02, 0x0b, 0xd8, 0x78, 0x4b, 0x15,
+ 0x7f, 0xaa, 0x2c, 0xff, 0xbe, 0x77, 0x33, 0xc7,
+ 0x6a, 0x12, 0xaa, 0xa4, 0xbe, 0xc0, 0x3b, 0xcb,
+ 0x13, 0x9d, 0x9c, 0x5a, 0x9f, 0x8a, 0x57, 0x36,
+ 0x4f, 0x02, 0x5a, 0xf8, 0x1d, 0x97, 0x77, 0x43,
+ 0xc8, 0xa5, 0xb7, 0x9b, 0x10, 0x98, 0xfd, 0x58,
+ 0xbf, 0x42, 0xf6, 0xbf, 0xff, 0x6c, 0x40, 0x18,
+ 0x18, 0xdf, 0xac, 0x57, 0x71, 0xea, 0xcc, 0x8e,
+ 0xfd, 0xfe, 0x10, 0xfb, 0xb9, 0xfe, 0xbc, 0x9a,
+ 0x9c, 0x27, 0xe4, 0x10, 0x15, 0x94, 0x41, 0xa1,
+ 0xcc, 0xf6, 0x25, 0x49, 0x4f, 0x96, 0xc1, 0x8c,
+ 0x9e, 0x3e, 0x18, 0x29, 0x49, 0x92, 0xe7, 0xfe,
+ 0x22, 0xff, 0xed, 0x02, 0x16, 0x90, 0xef, 0xac,
+ 0xec, 0x95, 0x1d, 0x5b, 0x94, 0x9c, 0xf6, 0x7c,
+ 0x1b, 0x5a, 0x9d, 0xb0, 0x9b, 0x05, 0x36, 0xbf,
+ 0xef, 0xec, 0x63, 0x35, 0x40, 0x24, 0x45, 0x40,
+ 0x30, 0x1a, 0x9b, 0x90, 0xc3, 0xc2, 0xf7, 0x37,
+ 0xfb, 0x08, 0x8e, 0x48, 0x19, 0x48, 0xed, 0xa8,
+ 0xa8, 0x04, 0x6f, 0xd0, 0x33, 0xe9, 0xb8, 0x8d,
+ 0xe7, 0x1e, 0x5c, 0x47, 0x74, 0xc0, 0x66, 0x30,
+ 0x4e, 0xa7, 0x86, 0x73, 0xf1, 0xe5, 0x78, 0xa6,
+ 0xe0, 0xc1, 0xda, 0x13, 0x72, 0x07, 0x85, 0x34,
+ 0x63, 0x95, 0x49, 0x30, 0x4b, 0x9d, 0x03, 0xf1,
+ 0x7a, 0x6b, 0x91, 0xa2, 0x85, 0x41, 0xf9, 0x4a,
+ 0xd6, 0xff, 0xff, 0x86, 0xf7, 0xf0, 0xce, 0xb9,
+ 0x07, 0xf1, 0x88, 0x04, 0x33, 0xaa, 0xeb, 0x54,
+ 0xb2, 0x1c, 0x8e, 0x2e, 0x7b, 0x04, 0xa8, 0xcc,
+ 0x2c, 0x7a, 0xb3, 0xad, 0x1a, 0x89, 0x38, 0x89,
+ 0xd7, 0x11, 0x3a, 0x8c, 0xcf, 0xe3, 0xc5, 0xba,
+ 0xb0, 0xcc, 0xc4, 0xe3, 0x33, 0xf3, 0x18, 0xba,
+ 0xec, 0x56, 0xd9, 0x1c, 0x40, 0x70, 0x0d, 0x4e,
+ 0x97, 0x01, 0x23, 0xf3, 0x5a, 0xdc, 0xbf, 0x68,
+ 0x93, 0xc2, 0x1d, 0x8a, 0x96, 0xb7, 0xac, 0x18,
+ 0x6f, 0xf7, 0x84, 0x71, 0x0d, 0x3d, 0xf8, 0xba,
+ 0xdf, 0xb6, 0x89, 0x1d, 0x78, 0x19, 0xf2, 0x59,
+ 0xe9, 0x15, 0x55, 0x29, 0x73, 0x50, 0x59, 0x14,
+ 0x02, 0x21, 0x16, 0x8f, 0x0f, 0xdf, 0xa5, 0xf0,
+};
+
+static struct crc_test {
+ u32 crc; /* random starting crc */
+ u32 start; /* random offset in buf */
+ u32 length; /* random length of test */
+ u32 crc_le; /* expected crc32_le result */
+ u32 crc_be; /* expected crc32_be result */
+} test[] = {
+ {0xffffffff, 0x00000000, 0x00001000, 0x13934bef, 0x14f3b75f},
+ {0xfe7328ea, 0x00000763, 0x00000717, 0xed2c0d70, 0x57531214},
+ {0x4c40684e, 0x00000721, 0x0000011e, 0xd7f46ccc, 0xedf12ec3},
+ {0x6b487f90, 0x00000264, 0x000007bc, 0x759e9939, 0x9af8e387},
+ {0x9f5810db, 0x00000afa, 0x00000255, 0x2685197f, 0x716de6ed},
+ {0xb15c4755, 0x00000d5b, 0x000002a4, 0xd8fadcb5, 0xfc34ae3f},
+ {0x06518253, 0x00000ffb, 0x00000004, 0xabee2433, 0xfa30ac9e},
+ {0xd9e71c55, 0x00000a2a, 0x00000259, 0x96682af2, 0xe5907ea3},
+ {0x0c1ae843, 0x00000ce4, 0x0000031b, 0x7b637c43, 0xe7f71b04},
+ {0xec3cd517, 0x000002ff, 0x00000566, 0x5d719a77, 0xed16e045},
+ {0x77828e95, 0x0000067f, 0x0000038f, 0x43ee5b6c, 0x35999927},
+ {0xec87b4e3, 0x00000d1c, 0x000002e3, 0x2ddd2eee, 0x9452d3f8},
+ {0x412158bb, 0x00000eee, 0x00000111, 0x67b38ba2, 0x177976d0},
+ {0x2e52de3e, 0x00000c4a, 0x000003b5, 0xbcc5d61d, 0xf60fee71},
+ {0x6ddaae8b, 0x00000d99, 0x00000266, 0x8b535544, 0x1dab8596},
+ {0x049b6cb1, 0x000009c5, 0x000000b0, 0xfc22cabc, 0x47ebc954},
+ {0x77d4b954, 0x0000028a, 0x000007fa, 0x71d00923, 0x905585ef},
+ {0x5e192355, 0x00000ac1, 0x000001fa, 0xb966b81a, 0x33c12903},
+ {0x7d80b71d, 0x00000213, 0x000001e0, 0x2bba371a, 0x5f4bd8d9},
+ {0x01f6f1e4, 0x000001d6, 0x00000395, 0xb7e8a647, 0x2a7943a1},
+ {0x1dfabb13, 0x00000e14, 0x000001eb, 0x53917fba, 0x8dee1e5d},
+ {0xb00a4449, 0x00000bf6, 0x00000409, 0xedecb577, 0x628e087d},
+ {0x7ecd3981, 0x0000083f, 0x0000016b, 0xefef62b9, 0xda4f94e6},
+ {0xf8f330d2, 0x000004be, 0x00000757, 0x9357c9f3, 0x8e2d5c2f},
+ {0x03c38af2, 0x00000d23, 0x000002dc, 0x360fa8c0, 0x6294c0d6},
+ {0x687bb79b, 0x00000f3d, 0x000000c2, 0x448d3be2, 0x08f48f3a},
+ {0x6710f550, 0x000009e9, 0x00000603, 0xdbfd1998, 0xc950ac29},
+ {0x873171d1, 0x00000787, 0x000004d5, 0xab7f1b62, 0xe66896ab},
+ {0x373b1314, 0x00000f0f, 0x000000f0, 0x184098ab, 0x4038e674},
+ {0x90fad9cd, 0x00000ead, 0x00000152, 0x23ce52ff, 0x9eff3974},
+ {0x19676fe7, 0x0000007d, 0x0000070d, 0xf8a76f1e, 0xfbc5c8a9},
+ {0x89facd45, 0x000005f3, 0x00000473, 0x4331a006, 0xb8f0f0cc},
+ {0x6f173747, 0x00000fc3, 0x0000003c, 0xb012f08e, 0x5126e378},
+ {0x4b44a106, 0x0000075a, 0x0000008b, 0xf6f7ac38, 0xf9b1781b},
+ {0xb620ad06, 0x00000774, 0x0000017e, 0xd34558e6, 0xb175edd3},
+ {0x976f21e9, 0x000008d7, 0x0000034a, 0xe533aa3a, 0x1e4367b9},
+ {0x687628c0, 0x000006c5, 0x0000061b, 0x3a840b15, 0xfb5989a0},
+ {0xe24ac108, 0x00000cd0, 0x0000032f, 0x51010ae8, 0xcdd8f182},
+ {0x361c44a3, 0x00000304, 0x00000719, 0xfd7bd481, 0x12de540f},
+ {0xd93ff95e, 0x00000db7, 0x0000008e, 0xcfbbc304, 0x42eecd5a},
+ {0xed752d12, 0x00000883, 0x00000091, 0x65a6c868, 0x9ebfa578},
+ {0xb4ff4b54, 0x000003d3, 0x000001c1, 0xf82597e7, 0xa8ad2b19},
+ {0x111b520f, 0x00000708, 0x000000eb, 0xc3e109f3, 0x323ace17},
+ {0x62c806f2, 0x00000ba3, 0x0000045c, 0x874d3a72, 0xaf1a1360},
+ {0x40d97470, 0x000005e1, 0x0000058d, 0x87a9684f, 0x524244a8},
+ {0x4312179c, 0x00000056, 0x0000070e, 0x809a00f5, 0xf9e940b0},
+ {0x13d5f84c, 0x00000a2d, 0x00000104, 0xf3d27578, 0x5d33341c},
+ {0x1f302cb2, 0x00000151, 0x00000014, 0x1e162693, 0x53c3cfc3},
+ {0xe491db24, 0x00000600, 0x000006f6, 0x7ff09615, 0xa300ecf7},
+ {0xf9a98069, 0x000002ba, 0x000002ad, 0x01af7387, 0x31c0911e},
+ {0xe9c477ad, 0x0000015f, 0x00000778, 0x6facf9a0, 0x1993b688},
+ {0x353f32b2, 0x0000087c, 0x00000783, 0x6cc964ea, 0x418db561},
+ {0x78e1b24f, 0x00000650, 0x000006a8, 0xb3bb7c27, 0xf2aad006},
+ {0x61aa400e, 0x00000049, 0x00000254, 0xb8cd1681, 0x79150b15},
+ {0xb84b10b0, 0x00000f73, 0x0000008c, 0x406a6450, 0x0c705222},
+ {0x9fa99c9c, 0x00000a7c, 0x000004d7, 0xfb3d21b4, 0xe4e789df},
+ {0x3fc9ebe3, 0x00000cd9, 0x000000d6, 0x43803f9c, 0x5a152be5},
+ {0x529879cd, 0x000002f2, 0x00000595, 0x78b4c6a6, 0xf7236ec4},
+ {0x3a933019, 0x00000516, 0x00000266, 0xdcb45436, 0x2c7935f5},
+ {0x887b4977, 0x00000227, 0x0000038d, 0xc5f7c3d9, 0x0d6d7df6},
+ {0x770745de, 0x000008c6, 0x00000739, 0xf69145e8, 0x47d5efc9},
+ {0x28be3b47, 0x00000c46, 0x0000032b, 0x764c028f, 0x1eb70d64},
+ {0x5013a050, 0x00000cf6, 0x00000309, 0xea8fe164, 0x186affa4},
+ {0x2ec4c9ba, 0x000006e8, 0x0000078d, 0xa35557a9, 0xb41f49ec},
+ {0xa9f950c9, 0x00000d33, 0x000002cc, 0x41ea8618, 0xab8dfae3},
+ {0x5b520229, 0x000007b2, 0x00000484, 0x44569f1f, 0x607a8052},
+ {0xd8dcbbfc, 0x0000002f, 0x0000048c, 0xdb88ab8b, 0xf1c411f1},
+ {0x25529792, 0x00000d1d, 0x000002e2, 0x20cda404, 0x32683a2d},
+ {0x9f3f6d71, 0x00000238, 0x0000079a, 0x0720443e, 0x4b8ba2ff},
+ {0x64121215, 0x000007ff, 0x0000038f, 0x6aacff2c, 0x3b84233b},
+ {0xfb6cdde0, 0x00000ef8, 0x00000107, 0xbd43a0f1, 0x926624d0},
+ {0x221c9d6f, 0x000007b6, 0x0000014f, 0xb67f834b, 0x2bdedda4},
+ {0x030e1de4, 0x00000836, 0x000004b4, 0x0d67d26a, 0x75a73b73},
+ {0xb56fa6cf, 0x00000c07, 0x000003f8, 0x60601ac1, 0x10a43f35},
+ {0xb55c89f5, 0x0000098e, 0x000001d4, 0x2400efbe, 0x006e28eb},
+ {0x5e90b6d5, 0x0000070b, 0x000003ea, 0x3bb5d6ea, 0xb175fa6b},
+ {0x2a7045ae, 0x00000961, 0x00000633, 0xfca89e4b, 0x962cd6d2},
+ {0x8b374ea9, 0x000006ba, 0x00000780, 0xbce036ed, 0x4dc8279b},
+ {0x8bd90bc9, 0x00000562, 0x00000369, 0xcb26a24b, 0x50dee743},
+ {0x5b1b1762, 0x000000fd, 0x0000051a, 0x33cdda07, 0xee75ff7b},
+ {0xa4153555, 0x0000058f, 0x000005c7, 0xbe50eeca, 0xe73fffcc},
+ {0x0be1f931, 0x00000651, 0x00000672, 0x95a25753, 0x4ad6270f},
+ {0xb7e78618, 0x00000a7f, 0x000002bb, 0xe06bcc1c, 0x1a35ee59},
+ {0x4a9bc41b, 0x00000e51, 0x000001ae, 0x709e8d2c, 0x75080ca8},
+ {0xfc359d13, 0x00000440, 0x000002f8, 0x0a58451f, 0x6fa3cfbf},
+ {0x5aa48619, 0x000006d1, 0x00000284, 0x928ead83, 0xbd600efc},
+ {0xa609afa8, 0x0000053e, 0x00000272, 0xb048c141, 0x184f80bb},
+ {0x3f108afb, 0x00000949, 0x00000150, 0x9a6bb5bc, 0x0ea02be1},
+ {0x79bec2d3, 0x000008ed, 0x00000712, 0x32692d57, 0x2eb13289},
+ {0x9429e067, 0x00000bc3, 0x0000043c, 0x5295ceff, 0x8a9014a7},
+ {0xae58b96a, 0x0000082d, 0x000007d2, 0xc2a681ba, 0x6af94089},
+ {0x95df24be, 0x00000985, 0x000004c1, 0x3a287765, 0x379fcb42},
+ {0x5e94976f, 0x00000596, 0x000004ed, 0xff00c489, 0x991fc1f5},
+ {0xf5e5f1de, 0x00000d31, 0x000002ce, 0x35f28e91, 0x543def1a},
+ {0xa2c219cf, 0x00000a3c, 0x00000374, 0x707d21eb, 0xa6d28bc1},
+ {0xf21b6ceb, 0x00000919, 0x00000135, 0x0847fb8b, 0x224468c2},
+ {0xaa988728, 0x00000787, 0x00000771, 0x885aeaa4, 0x814db00b},
+ {0xaa5dfaac, 0x000003e5, 0x0000051b, 0x52c48ab7, 0x725bef8a},
+ {0x0a053968, 0x00000d2a, 0x000002d5, 0x7a90256d, 0xc53b9402},
+ {0x1421dc20, 0x00000eef, 0x00000110, 0x97d6da24, 0x10846935},
+ {0xb47c2166, 0x00000a6a, 0x00000209, 0xcfd6cc52, 0x46e2797e},
+ {0x77dd1955, 0x000000de, 0x00000266, 0xba74bcaa, 0x4fa3fe9c},
+ {0x68a03cc2, 0x0000082f, 0x000007b0, 0x752bd5d8, 0x4f760c63},
+ {0x0226b0a3, 0x00000a5f, 0x000005a0, 0x82de4970, 0x8ee1310e},
+ {0x637bf3b1, 0x00000d93, 0x0000026c, 0x5c7115cb, 0x9f6a0ced},
+ {0x3b120edf, 0x00000c13, 0x000003ec, 0x80d7d20f, 0x241657d5},
+ {0xe2456780, 0x000002eb, 0x00000641, 0xc0a5d289, 0x74df96b4},
+ {0x9b2e7125, 0x00000c0c, 0x000003f3, 0xcc15f57e, 0x03e290bf},
+ {0x153033ef, 0x00000787, 0x000006b6, 0x3cde443b, 0x7bf1d121},
+ {0x18458b3f, 0x0000066c, 0x00000561, 0x9a2bd8c6, 0x9d564bef},
+ {0x4ff9d4b9, 0x00000c8f, 0x0000033a, 0xd0ee6d6d, 0xee00aa0b},
+ {0xdf84b5d9, 0x00000802, 0x0000029a, 0xdab0d74a, 0xd0cb63dc},
+ {0x81ee15df, 0x000003ce, 0x00000725, 0x9942e2de, 0xe48fb26b},
+ {0x5c768e04, 0x00000afd, 0x00000160, 0x36110831, 0x8dc74483},
+ {0xe5e18094, 0x00000b4b, 0x000000a0, 0xffa3e4a7, 0xc0145e1b},
+ {0xed7263b6, 0x00000d0d, 0x000002f2, 0xb0006a35, 0x5468ae3a},
+ {0x5bfde7d7, 0x000006fb, 0x00000554, 0xa4193b76, 0xb73d34b2},
+ {0x67f4a743, 0x00000b85, 0x0000047a, 0xf05c8d8f, 0x4f843e49},
+ {0xf13bdf22, 0x00000ff7, 0x00000008, 0x816351eb, 0x41f537f6},
+ {0x08ecc608, 0x00000d5d, 0x00000098, 0x90492772, 0xf5172204},
+ {0x296f52ba, 0x000004f9, 0x00000788, 0x5e5a4896, 0xe01d5b46},
+ {0xbe4624c2, 0x00000427, 0x000004ef, 0xcd267b94, 0x7b9069f4},
+ {0x906f7c7c, 0x00000a05, 0x0000003f, 0x03fcfc33, 0x7b6ff563},
+ {0x8f7b323e, 0x00000458, 0x000004c7, 0xcd4969c8, 0xd4c22ada},
+ {0x88d6593d, 0x00000597, 0x000005b5, 0xf199cd3b, 0x5c3e8ca2},
+ {0x978a7768, 0x00000268, 0x000001d3, 0xb28c95bd, 0x49a2cc67},
+ {0x857a621e, 0x000007a7, 0x000003a8, 0xf4bf84ab, 0xde26f369},
+ {0xb0e121ef, 0x000005be, 0x00000644, 0x28747c14, 0x61d4dc6b},
+ {0, 0, 0, 0, 0},
+};
+
+static int test_crc32c(void)
+{
+ struct crc_test *t = test;
+ int failures = 0;
+
+ while (t->length) {
+ u32 be, le;
+ le = crc32c_le(t->crc, test_buf + t->start, t->length);
+ be = crc32c_be(t->crc, test_buf + t->start, t->length);
+ if (le != t->crc_le) {
+ printk(KERN_INFO "crc32c test %d LE fails, %x != %x\n",
+ (t - test), le, t->crc_le);
+ failures++;
+ }
+ if (be != t->crc_be) {
+ printk(KERN_INFO "crc32c test %d BE fails, %x != %x\n",
+ (t - test), be, t->crc_be);
+ failures++;
+ }
+ t++;
+ }
+
+ return failures;
+}
+
+static int __init libcrc32c_test_mod_init(void)
+{
+ return test_crc32c() ? -EIO : -EAGAIN;
+}
+
+module_init(libcrc32c_test_mod_init);
+
+MODULE_AUTHOR("Darrick J. Wong <[email protected]>");
+MODULE_DESCRIPTION("CRC32c (Castagnoli) self-test");
+MODULE_LICENSE("GPL");
Could you elaborate a little on this?
> -----Original Message-----
> From: Herbert Xu [mailto:[email protected]]
> Sent: Wednesday, August 31, 2011 8:08 PM
> To: Darrick J. Wong
> Cc: Andreas Dilger; Theodore Tso; David Miller; Bob Pearson; linux-kernel;
> Mingming Cao; linux-crypto; linux-fsdevel; [email protected]
> Subject: Re: [PATCH 3/3] crc32c: Implement a self-test for CRC32c
>
> On Wed, Aug 31, 2011 at 05:33:36PM -0700, Darrick J. Wong wrote:
> > This is a loadable module that will self-test the CRC32c code.
> >
> > Signed-off-by: Darrick J. Wong <[email protected]>
>
> Please use the existing crypto testing framework.
>
> Thanks,
> --
> Email: Herbert Xu <[email protected]>
> Home Page: http://gondor.apana.org.au/~herbert/
> PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Bob Pearson <[email protected]> wrote:
> Could you elaborate a little on this?
Sure, we already have a self-test infrastructure under crypto
in testmgr.*. It even includes test vectors for crc32c.
Cheers,
--
Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
On Wed, Aug 31, 2011 at 05:33:36PM -0700, Darrick J. Wong wrote:
> This is a loadable module that will self-test the CRC32c code.
>
> Signed-off-by: Darrick J. Wong <[email protected]>
Please use the existing crypto testing framework.
Thanks,
--
Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Hi Darrick,
The same code in crc32.c was helpful to measure performance and help code tuning as well as indicate correctness. Otherwise the code in crypto may be enough to test all the corner cases. If this survives the review I wonder if there is a way to combine crc32 and crc32c together somehow. I like yours because you can load/unload and not need the memory permanently.
Bob
On Thu, Sep 01, 2011 at 12:40:08AM -0500, Bob Pearson wrote:
> Hi Darrick,
>
> The same code in crc32.c was helpful to measure performance and help code tuning as well as indicate correctness. Otherwise the code in crypto may be enough to test all the corner cases. If this survives the review I wonder if there is a way to combine crc32 and crc32c together somehow. I like yours because you can load/unload and not need the memory permanently.
You can unload the crypto testmgr module too.
Cheers,
--
Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
On Thu, Sep 01, 2011 at 12:40:08AM -0500, Bob Pearson wrote:
> Hi Darrick,
>
> The same code in crc32.c was helpful to measure performance and help code
> tuning as well as indicate correctness. Otherwise the code in crypto may be
> enough to test all the corner cases. If this survives the review I wonder if
> there is a way to combine crc32 and crc32c together somehow. I like yours
> because you can load/unload and not need the memory permanently.
I suspect it would be pretty easy to adapt the Makefile to generate the
relevant .c and .h files; in particular it could be useful to use the crypto
framework for crc32 on the off chance anyone wants to provide hwaccel for that
too.
That said, merging libcrc32c-test vectors with the existing one (sorry, I
didn't realize that existed) shouldn't be too difficult.
--D
On Thu, Sep 01, 2011 at 03:18:54PM -0700, Darrick J. Wong wrote:
> I suspect it would be pretty easy to adapt the Makefile to generate the
> relevant .c and .h files; in particular it could be useful to use the crypto
> framework for crc32 on the off chance anyone wants to provide hwaccel for that
> too.
crc32 or crc32c? Note that there already is a hardware optimized crc32c
for recent Intel CPUs in arch/x86/crypto/crc32c-intel.c.
On Thu, Sep 01, 2011 at 06:24:22PM -0400, Christoph Hellwig wrote:
> On Thu, Sep 01, 2011 at 03:18:54PM -0700, Darrick J. Wong wrote:
> > I suspect it would be pretty easy to adapt the Makefile to generate the
> > relevant .c and .h files; in particular it could be useful to use the crypto
> > framework for crc32 on the off chance anyone wants to provide hwaccel for that
> > too.
>
> crc32 or crc32c? Note that there already is a hardware optimized crc32c
> for recent Intel CPUs in arch/x86/crypto/crc32c-intel.c.
crc32, since it currently doesn't use the crypto api at all, and Bob was
interested in implementing slice-by-8 for it. Though I suppose so long as
there aren't any reasons to override the sw crc32 implementation we could just
fall back to Bob's earlier patch to implement slice-by-8 for crc32?
<shrug> I don't mind implementing faster crc32/crc32c.
(As far as crc32c goes, my motivation is to make sw crc32c faster for the cases
where you don't have Intel hw.)
--D