Replace crc32 with xxhash32

On the one hand, benchmarking and profiling determined xxhash32 to be
faster than the zlib implementation of crc32, on the other hand
profiling determined that crc32 computation contributed signifficantly
to the overall runtime.

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

3 files changed, 106 insertions, 1 deletions

diff --git a/lib/sqfs/block_processor/common.c b/lib/sqfs/block_processor/common.c
index a1e8b6e..a01b5e9 100644
--- a/lib/sqfs/block_processor/common.c
+++ b/lib/sqfs/block_processor/common.c
@@ -67,7 +67,7 @@ int block_processor_do_block(sqfs_block_t *block, sqfs_compressor_t *cmp,
 		return 0;
 	}
 
-	block->checksum = crc32(0, block->data, block->size);
+	block->checksum = xxh32(block->data, block->size);
 
 	if (block->flags & (SQFS_BLK_IS_FRAGMENT | SQFS_BLK_DONT_COMPRESS))
 		return 0;
diff --git a/lib/sqfs/block_processor/internal.h b/lib/sqfs/block_processor/internal.h
index f26d58e..b7fbef0 100644
--- a/lib/sqfs/block_processor/internal.h
+++ b/lib/sqfs/block_processor/internal.h
@@ -115,4 +115,6 @@ int block_processor_do_block(sqfs_block_t *block, sqfs_compressor_t *cmp,
 SQFS_INTERNAL
 int append_to_work_queue(sqfs_block_processor_t *proc, sqfs_block_t *block);
 
+SQFS_INTERNAL sqfs_u32 xxh32(const void *input, const size_t len);
+
 #endif /* INTERNAL_H */
diff --git a/lib/sqfs/block_processor/xxhash.c b/lib/sqfs/block_processor/xxhash.c
new file mode 100644
index 0000000..8be4f9c
--- /dev/null
+++ b/lib/sqfs/block_processor/xxhash.c
@@ -0,0 +1,103 @@
+/*
+ * xxHash - Extremely Fast Hash algorithm
+ * Copyright (C) 2012-2016, Yann Collet.
+ *
+ * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *   * Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer.
+ *   * Redistributions in binary form must reproduce the above
+ *     copyright notice, this list of conditions and the following disclaimer
+ *     in the documentation and/or other materials provided with the
+ *     distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ * ----------------------------------------------------------------------------
+ * This code has been lifted from Linux (the OS kernel) and adapted for use in
+ * libsquashfs. For the original, unmodified and complete source, see below.
+ *
+ * You can contact the author at:
+ * - xxHash homepage: http://cyan4973.github.io/xxHash/
+ * - xxHash source repository: https://github.com/Cyan4973/xxHash
+ */
+#define SQFS_BUILDING_DLL
+#include "internal.h"
+
+#define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r)))
+
+static const sqfs_u32 PRIME32_1 = 2654435761U;
+static const sqfs_u32 PRIME32_2 = 2246822519U;
+static const sqfs_u32 PRIME32_3 = 3266489917U;
+static const sqfs_u32 PRIME32_4 =  668265263U;
+static const sqfs_u32 PRIME32_5 =  374761393U;
+
+static sqfs_u32 xxh32_round(sqfs_u32 seed, sqfs_u32 input)
+{
+	seed += input * PRIME32_2;
+	seed = xxh_rotl32(seed, 13);
+	seed *= PRIME32_1;
+	return seed;
+}
+
+sqfs_u32 xxh32(const void *input, const size_t len)
+{
+	const sqfs_u8 *p = (const sqfs_u8 *)input;
+	const sqfs_u8 *b_end = p + len;
+	sqfs_u32 h32;
+
+	if (len >= 16) {
+		const sqfs_u8 *const limit = b_end - 16;
+		sqfs_u32 v1 = PRIME32_1 + PRIME32_2;
+		sqfs_u32 v2 = PRIME32_2;
+		sqfs_u32 v3 = 0;
+		sqfs_u32 v4 = PRIME32_1;
+
+		do {
+			v1 = xxh32_round(v1, ((sqfs_u32 *)p)[0]);
+			v2 = xxh32_round(v2, ((sqfs_u32 *)p)[1]);
+			v3 = xxh32_round(v3, ((sqfs_u32 *)p)[2]);
+			v4 = xxh32_round(v4, ((sqfs_u32 *)p)[3]);
+			p += 16;
+		} while (p <= limit);
+
+		h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) +
+			xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18);
+	} else {
+		h32 = PRIME32_5;
+	}
+
+	h32 += (sqfs_u32)len;
+
+	while (p + 4 <= b_end) {
+		h32 += (*((sqfs_u32 *)p)) * PRIME32_3;
+		h32 = xxh_rotl32(h32, 17) * PRIME32_4;
+		p += 4;
+	}
+
+	while (p < b_end) {
+		h32 += (*p) * PRIME32_5;
+		h32 = xxh_rotl32(h32, 11) * PRIME32_1;
+		p++;
+	}
+
+	h32 ^= h32 >> 15;
+	h32 *= PRIME32_2;
+	h32 ^= h32 >> 13;
+	h32 *= PRIME32_3;
+	h32 ^= h32 >> 16;
+	return h32;
+}