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