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 
FindMatchLengthWithLimit(const uint8_t * s1,const uint8_t * s2,size_t limit)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