summaryrefslogtreecommitdiffstats
path: root/modules/brotli/enc/find_match_length.h
diff options
context:
space:
mode:
Diffstat (limited to 'modules/brotli/enc/find_match_length.h')
-rw-r--r--modules/brotli/enc/find_match_length.h80
1 files changed, 80 insertions, 0 deletions
diff --git a/modules/brotli/enc/find_match_length.h b/modules/brotli/enc/find_match_length.h
new file mode 100644
index 000000000..bc428cffd
--- /dev/null
+++ b/modules/brotli/enc/find_match_length.h
@@ -0,0 +1,80 @@
+/* Copyright 2010 Google Inc. All Rights Reserved.
+
+ Distributed under MIT license.
+ See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
+*/
+
+/* Function to find maximal matching prefixes of strings. */
+
+#ifndef BROTLI_ENC_FIND_MATCH_LENGTH_H_
+#define BROTLI_ENC_FIND_MATCH_LENGTH_H_
+
+#include "../common/platform.h"
+#include <brotli/types.h>
+
+#if defined(__cplusplus) || defined(c_plusplus)
+extern "C" {
+#endif
+
+/* Separate implementation for little-endian 64-bit targets, for speed. */
+#if defined(__GNUC__) && defined(_LP64) && defined(BROTLI_LITTLE_ENDIAN)
+
+static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1,
+ const uint8_t* s2,
+ size_t limit) {
+ size_t matched = 0;
+ size_t limit2 = (limit >> 3) + 1; /* + 1 is for pre-decrement in while */
+ while (BROTLI_PREDICT_TRUE(--limit2)) {
+ if (BROTLI_PREDICT_FALSE(BROTLI_UNALIGNED_LOAD64LE(s2) ==
+ BROTLI_UNALIGNED_LOAD64LE(s1 + matched))) {
+ s2 += 8;
+ matched += 8;
+ } else {
+ uint64_t x = BROTLI_UNALIGNED_LOAD64LE(s2) ^
+ BROTLI_UNALIGNED_LOAD64LE(s1 + matched);
+ size_t matching_bits = (size_t)__builtin_ctzll(x);
+ matched += matching_bits >> 3;
+ return matched;
+ }
+ }
+ limit = (limit & 7) + 1; /* + 1 is for pre-decrement in while */
+ while (--limit) {
+ if (BROTLI_PREDICT_TRUE(s1[matched] == *s2)) {
+ ++s2;
+ ++matched;
+ } else {
+ return matched;
+ }
+ }
+ return matched;
+}
+#else
+static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1,
+ const uint8_t* s2,
+ size_t limit) {
+ size_t matched = 0;
+ const uint8_t* s2_limit = s2 + limit;
+ const uint8_t* s2_ptr = s2;
+ /* Find out how long the match is. We loop over the data 32 bits at a
+ time until we find a 32-bit block that doesn't match; then we find
+ the first non-matching bit and use that to calculate the total
+ length of the match. */
+ while (s2_ptr <= s2_limit - 4 &&
+ BrotliUnalignedRead32(s2_ptr) ==
+ BrotliUnalignedRead32(s1 + matched)) {
+ s2_ptr += 4;
+ matched += 4;
+ }
+ while ((s2_ptr < s2_limit) && (s1[matched] == *s2_ptr)) {
+ ++s2_ptr;
+ ++matched;
+ }
+ return matched;
+}
+#endif
+
+#if defined(__cplusplus) || defined(c_plusplus)
+} /* extern "C" */
+#endif
+
+#endif /* BROTLI_ENC_FIND_MATCH_LENGTH_H_ */