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 <brotli/types.h> 13 14 #include "../common/platform.h" 15 16 #if defined(__cplusplus) || defined(c_plusplus) 17 extern "C" { 18 #endif 19 20 /* Separate implementation for little-endian 64-bit targets, for speed. */ 21 #if defined(BROTLI_TZCNT64) && BROTLI_64_BITS && BROTLI_LITTLE_ENDIAN FindMatchLengthWithLimit(const uint8_t * s1,const uint8_t * s2,size_t limit)22static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1, 23 const uint8_t* s2, 24 size_t limit) { 25 const uint8_t *s1_orig = s1; 26 for (; limit >= 8; limit -= 8) { 27 uint64_t x = BROTLI_UNALIGNED_LOAD64LE(s2) ^ 28 BROTLI_UNALIGNED_LOAD64LE(s1); 29 s2 += 8; 30 if (x != 0) { 31 size_t matching_bits = (size_t)BROTLI_TZCNT64(x); 32 return (size_t)(s1 - s1_orig) + (matching_bits >> 3); 33 } 34 s1 += 8; 35 } 36 while (limit && *s1 == *s2) { 37 limit--; 38 ++s2; 39 ++s1; 40 } 41 return (size_t)(s1 - s1_orig); 42 } 43 #else 44 static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1, 45 const uint8_t* s2, 46 size_t limit) { 47 size_t matched = 0; 48 const uint8_t* s2_limit = s2 + limit; 49 const uint8_t* s2_ptr = s2; 50 /* Find out how long the match is. We loop over the data 32 bits at a 51 time until we find a 32-bit block that doesn't match; then we find 52 the first non-matching bit and use that to calculate the total 53 length of the match. */ 54 while (s2_ptr <= s2_limit - 4 && 55 BrotliUnalignedRead32(s2_ptr) == 56 BrotliUnalignedRead32(s1 + matched)) { 57 s2_ptr += 4; 58 matched += 4; 59 } 60 while ((s2_ptr < s2_limit) && (s1[matched] == *s2_ptr)) { 61 ++s2_ptr; 62 ++matched; 63 } 64 return matched; 65 } 66 #endif 67 68 #if defined(__cplusplus) || defined(c_plusplus) 69 } /* extern "C" */ 70 #endif 71 72 #endif /* BROTLI_ENC_FIND_MATCH_LENGTH_H_ */ 73