1/* Copyright 2010 Google Inc. All Rights Reserved.
2
3   Distributed under MIT license.
4   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
5*/
6
7/* Function to find maximal matching prefixes of strings. */
8
9#ifndef BROTLI_ENC_FIND_MATCH_LENGTH_H_
10#define BROTLI_ENC_FIND_MATCH_LENGTH_H_
11
12#include "../common/platform.h"
13#include <brotli/types.h>
14
15#if defined(__cplusplus) || defined(c_plusplus)
16extern "C" {
17#endif
18
19/* Separate implementation for little-endian 64-bit targets, for speed. */
20#if defined(BROTLI_TZCNT64) && BROTLI_64_BITS && BROTLI_LITTLE_ENDIAN
21static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1,
22                                                     const uint8_t* s2,
23                                                     size_t limit) {
24  size_t matched = 0;
25  size_t limit2 = (limit >> 3) + 1;  /* + 1 is for pre-decrement in while */
26  while (BROTLI_PREDICT_TRUE(--limit2)) {
27    if (BROTLI_PREDICT_FALSE(BROTLI_UNALIGNED_LOAD64LE(s2) ==
28                      BROTLI_UNALIGNED_LOAD64LE(s1 + matched))) {
29      s2 += 8;
30      matched += 8;
31    } else {
32      uint64_t x = BROTLI_UNALIGNED_LOAD64LE(s2) ^
33          BROTLI_UNALIGNED_LOAD64LE(s1 + matched);
34      size_t matching_bits = (size_t)BROTLI_TZCNT64(x);
35      matched += matching_bits >> 3;
36      return matched;
37    }
38  }
39  limit = (limit & 7) + 1;  /* + 1 is for pre-decrement in while */
40  while (--limit) {
41    if (BROTLI_PREDICT_TRUE(s1[matched] == *s2)) {
42      ++s2;
43      ++matched;
44    } else {
45      return matched;
46    }
47  }
48  return matched;
49}
50#else
51static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1,
52                                                     const uint8_t* s2,
53                                                     size_t limit) {
54  size_t matched = 0;
55  const uint8_t* s2_limit = s2 + limit;
56  const uint8_t* s2_ptr = s2;
57  /* Find out how long the match is. We loop over the data 32 bits at a
58     time until we find a 32-bit block that doesn't match; then we find
59     the first non-matching bit and use that to calculate the total
60     length of the match. */
61  while (s2_ptr <= s2_limit - 4 &&
62         BrotliUnalignedRead32(s2_ptr) ==
63         BrotliUnalignedRead32(s1 + matched)) {
64    s2_ptr += 4;
65    matched += 4;
66  }
67  while ((s2_ptr < s2_limit) && (s1[matched] == *s2_ptr)) {
68    ++s2_ptr;
69    ++matched;
70  }
71  return matched;
72}
73#endif
74
75#if defined(__cplusplus) || defined(c_plusplus)
76}  /* extern "C" */
77#endif
78
79#endif  /* BROTLI_ENC_FIND_MATCH_LENGTH_H_ */
80