More lz_hash_chains, lz_binary_trees performance improvements

[wimlib] / include / wimlib / lz_extend.h

diff --git a/include/wimlib/lz_extend.h b/include/wimlib/lz_extend.h
new file mode 100644 (file)
index 0000000..7d7ed8b
--- /dev/null
+++ b/include/wimlib/lz_extend.h
@@ -0,0 +1,74 @@
+/*
+ * lz_extend.h
+ *
+ * Fast match extension for Lempel-Ziv matchfinding.
+ *
+ * The author dedicates this file to the public domain.
+ * You can do whatever you want with this file.
+ */
+
+#ifndef _WIMLIB_LZ_EXTEND_H
+#define _WIMLIB_LZ_EXTEND_H
+
+#include "wimlib/types.h"
+
+#if (defined(__x86_64__) || defined(__i386__)) && defined(__GNUC__)
+#  define HAVE_FAST_LZ_EXTEND 1
+#else
+#  define HAVE_FAST_LZ_EXTEND 0
+#endif
+
+/* Return the number of bytes at @matchptr that match the bytes at @strptr, up
+ * to a maximum of @max_len.  Initially, @start_len bytes are matched.  */
+static inline u32
+lz_extend(const u8 * const strptr, const u8 * const matchptr,
+         const u32 start_len, const u32 max_len)
+{
+       u32 len = start_len;
+
+#if HAVE_FAST_LZ_EXTEND
+
+       while (len + sizeof(unsigned long) <= max_len) {
+               unsigned long x;
+
+               x = *(const unsigned long *)&matchptr[len] ^
+                   *(const unsigned long *)&strptr[len];
+               if (x != 0)
+                       return len + (__builtin_ctzl(x) >> 3);
+               len += sizeof(unsigned long);
+       }
+
+       if (sizeof(unsigned int) < sizeof(unsigned long) &&
+           len + sizeof(unsigned int) <= max_len)
+       {
+               unsigned int x;
+
+               x = *(const unsigned int *)&matchptr[len] ^
+                   *(const unsigned int *)&strptr[len];
+               if (x != 0)
+                       return len + (__builtin_ctz(x) >> 3);
+               len += sizeof(unsigned int);
+       }
+
+       if (sizeof(unsigned int) == 4) {
+               if (len < max_len && matchptr[len] == strptr[len]) {
+                       len++;
+                       if (len < max_len && matchptr[len] == strptr[len]) {
+                               len++;
+                               if (len < max_len && matchptr[len] == strptr[len]) {
+                                       len++;
+                               }
+                       }
+               }
+               return len;
+       }
+
+#endif /* HAVE_FAST_LZ_EXTEND */
+
+       while (len < max_len && matchptr[len] == strptr[len])
+               len++;
+
+       return len;
+}
+
+#endif /* _WIMLIB_LZ_EXTEND_H */