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