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) |
16 | extern "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 | |
22 | static 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 |
52 | static 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 | |