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