1 // Copyright 2010 Google Inc. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // Function to find maximal matching prefixes of strings.
16
17 #ifndef BROTLI_ENC_FIND_MATCH_LENGTH_H_
18 #define BROTLI_ENC_FIND_MATCH_LENGTH_H_
19
20 #include <stdint.h>
21
22 #include "./port.h"
23
24 namespace brotli {
25
26 // Separate implementation for x86_64, for speed.
27 #if defined(__GNUC__) && defined(ARCH_K8)
28
FindMatchLengthWithLimit(const uint8_t * s1,const uint8_t * s2,size_t limit)29 static inline int FindMatchLengthWithLimit(const uint8_t* s1,
30 const uint8_t* s2,
31 size_t limit) {
32 int matched = 0;
33 size_t limit2 = (limit >> 3) + 1; // + 1 is for pre-decrement in while
34 while (PREDICT_TRUE(--limit2)) {
35 if (PREDICT_FALSE(BROTLI_UNALIGNED_LOAD64(s2) ==
36 BROTLI_UNALIGNED_LOAD64(s1 + matched))) {
37 s2 += 8;
38 matched += 8;
39 } else {
40 uint64_t x =
41 BROTLI_UNALIGNED_LOAD64(s2) ^ BROTLI_UNALIGNED_LOAD64(s1 + matched);
42 int matching_bits = __builtin_ctzll(x);
43 matched += matching_bits >> 3;
44 return matched;
45 }
46 }
47 limit = (limit & 7) + 1; // + 1 is for pre-decrement in while
48 while (--limit) {
49 if (PREDICT_TRUE(s1[matched] == *s2)) {
50 ++s2;
51 ++matched;
52 } else {
53 return matched;
54 }
55 }
56 return matched;
57 }
58 #else
59 static inline int FindMatchLengthWithLimit(const uint8_t* s1,
60 const uint8_t* s2,
61 size_t limit) {
62 int matched = 0;
63 const uint8_t* s2_limit = s2 + limit;
64 const uint8_t* s2_ptr = s2;
65 // Find out how long the match is. We loop over the data 32 bits at a
66 // time until we find a 32-bit block that doesn't match; then we find
67 // the first non-matching bit and use that to calculate the total
68 // length of the match.
69 while (s2_ptr <= s2_limit - 4 &&
70 BROTLI_UNALIGNED_LOAD32(s2_ptr) ==
71 BROTLI_UNALIGNED_LOAD32(s1 + matched)) {
72 s2_ptr += 4;
73 matched += 4;
74 }
75 while ((s2_ptr < s2_limit) && (s1[matched] == *s2_ptr)) {
76 ++s2_ptr;
77 ++matched;
78 }
79 return matched;
80 }
81 #endif
82
83 } // namespace brotli
84
85 #endif // BROTLI_ENC_FIND_MATCH_LENGTH_H_
86