| /* Copyright 2010 Google Inc. All Rights Reserved. |
| |
| Distributed under MIT license. |
| See file LICENSE for detail or copy at https://opensource.org/licenses/MIT |
| */ |
| |
| /* Function to find maximal matching prefixes of strings. */ |
| |
| #ifndef BROTLI_ENC_FIND_MATCH_LENGTH_H_ |
| #define BROTLI_ENC_FIND_MATCH_LENGTH_H_ |
| |
| #include <brotli/types.h> |
| |
| #include "../common/platform.h" |
| |
| #if defined(__cplusplus) || defined(c_plusplus) |
| extern "C" { |
| #endif |
| |
| /* Separate implementation for little-endian 64-bit targets, for speed. */ |
| #if defined(BROTLI_TZCNT64) && BROTLI_64_BITS && BROTLI_LITTLE_ENDIAN |
| static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1, |
| const uint8_t* s2, |
| size_t limit) { |
| const uint8_t *s1_orig = s1; |
| for (; limit >= 8; limit -= 8) { |
| uint64_t x = BROTLI_UNALIGNED_LOAD64LE(s2) ^ |
| BROTLI_UNALIGNED_LOAD64LE(s1); |
| s2 += 8; |
| if (x != 0) { |
| size_t matching_bits = (size_t)BROTLI_TZCNT64(x); |
| return (size_t)(s1 - s1_orig) + (matching_bits >> 3); |
| } |
| s1 += 8; |
| } |
| while (limit && *s1 == *s2) { |
| limit--; |
| ++s2; |
| ++s1; |
| } |
| return (size_t)(s1 - s1_orig); |
| } |
| #else |
| static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1, |
| const uint8_t* s2, |
| size_t limit) { |
| size_t matched = 0; |
| const uint8_t* s2_limit = s2 + limit; |
| const uint8_t* s2_ptr = s2; |
| /* Find out how long the match is. We loop over the data 32 bits at a |
| time until we find a 32-bit block that doesn't match; then we find |
| the first non-matching bit and use that to calculate the total |
| length of the match. */ |
| while (s2_ptr <= s2_limit - 4 && |
| BrotliUnalignedRead32(s2_ptr) == |
| BrotliUnalignedRead32(s1 + matched)) { |
| s2_ptr += 4; |
| matched += 4; |
| } |
| while ((s2_ptr < s2_limit) && (s1[matched] == *s2_ptr)) { |
| ++s2_ptr; |
| ++matched; |
| } |
| return matched; |
| } |
| #endif |
| |
| #if defined(__cplusplus) || defined(c_plusplus) |
| } /* extern "C" */ |
| #endif |
| |
| #endif /* BROTLI_ENC_FIND_MATCH_LENGTH_H_ */ |