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(__GNUC__) && defined(_LP64) && defined(BROTLI_LITTLE_ENDIAN)
21
22static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1,
23 const uint8_t* s2,
24 size_t limit) {
25 size_t matched = 0;
26 size_t limit2 = (limit >> 3) + 1; /* + 1 is for pre-decrement in while */
27 while (BROTLI_PREDICT_TRUE(--limit2)) {
28 if (BROTLI_PREDICT_FALSE(BROTLI_UNALIGNED_LOAD64LE(s2) ==
29 BROTLI_UNALIGNED_LOAD64LE(s1 + matched))) {
30 s2 += 8;
31 matched += 8;
32 } else {
33 uint64_t x = BROTLI_UNALIGNED_LOAD64LE(s2) ^
34 BROTLI_UNALIGNED_LOAD64LE(s1 + matched);
35 size_t matching_bits = (size_t)__builtin_ctzll(x);
36 matched += matching_bits >> 3;
37 return matched;
38 }
39 }
40 limit = (limit & 7) + 1; /* + 1 is for pre-decrement in while */
41 while (--limit) {
42 if (BROTLI_PREDICT_TRUE(s1[matched] == *s2)) {
43 ++s2;
44 ++matched;
45 } else {
46 return matched;
47 }
48 }
49 return matched;
50}
51#else
52static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1,
53 const uint8_t* s2,
54 size_t limit) {
55 size_t matched = 0;
56 const uint8_t* s2_limit = s2 + limit;
57 const uint8_t* s2_ptr = s2;
58 /* Find out how long the match is. We loop over the data 32 bits at a
59 time until we find a 32-bit block that doesn't match; then we find
60 the first non-matching bit and use that to calculate the total
61 length of the match. */
62 while (s2_ptr <= s2_limit - 4 &&
63 BrotliUnalignedRead32(s2_ptr) ==
64 BrotliUnalignedRead32(s1 + matched)) {
65 s2_ptr += 4;
66 matched += 4;
67 }
68 while ((s2_ptr < s2_limit) && (s1[matched] == *s2_ptr)) {
69 ++s2_ptr;
70 ++matched;
71 }
72 return matched;
73}
74#endif
75
76#if defined(__cplusplus) || defined(c_plusplus)
77} /* extern "C" */
78#endif
79
80#endif /* BROTLI_ENC_FIND_MATCH_LENGTH_H_ */
81