1 // Copyright 2010 Google Inc. All Rights Reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // Function to find maximal matching prefixes of strings. 16 17 #ifndef BROTLI_ENC_FIND_MATCH_LENGTH_H_ 18 #define BROTLI_ENC_FIND_MATCH_LENGTH_H_ 19 20 #include <stdint.h> 21 22 #include "./port.h" 23 24 namespace brotli { 25 26 // Separate implementation for x86_64, for speed. 27 #if defined(__GNUC__) && defined(ARCH_K8) 28 29 static inline int FindMatchLengthWithLimit(const uint8_t* s1, 30 const uint8_t* s2, 31 size_t limit) { 32 int matched = 0; 33 size_t limit2 = (limit >> 3) + 1; // + 1 is for pre-decrement in while 34 while (PREDICT_TRUE(--limit2)) { 35 if (PREDICT_FALSE(BROTLI_UNALIGNED_LOAD64(s2) == 36 BROTLI_UNALIGNED_LOAD64(s1 + matched))) { 37 s2 += 8; 38 matched += 8; 39 } else { 40 uint64_t x = 41 BROTLI_UNALIGNED_LOAD64(s2) ^ BROTLI_UNALIGNED_LOAD64(s1 + matched); 42 int matching_bits = __builtin_ctzll(x); 43 matched += matching_bits >> 3; 44 return matched; 45 } 46 } 47 limit = (limit & 7) + 1; // + 1 is for pre-decrement in while 48 while (--limit) { 49 if (PREDICT_TRUE(s1[matched] == *s2)) { 50 ++s2; 51 ++matched; 52 } else { 53 return matched; 54 } 55 } 56 return matched; 57 } 58 #else 59 static inline int FindMatchLengthWithLimit(const uint8_t* s1, 60 const uint8_t* s2, 61 size_t limit) { 62 int matched = 0; 63 const uint8_t* s2_limit = s2 + limit; 64 const uint8_t* s2_ptr = s2; 65 // Find out how long the match is. We loop over the data 32 bits at a 66 // time until we find a 32-bit block that doesn't match; then we find 67 // the first non-matching bit and use that to calculate the total 68 // length of the match. 69 while (s2_ptr <= s2_limit - 4 && 70 BROTLI_UNALIGNED_LOAD32(s2_ptr) == 71 BROTLI_UNALIGNED_LOAD32(s1 + matched)) { 72 s2_ptr += 4; 73 matched += 4; 74 } 75 while ((s2_ptr < s2_limit) && (s1[matched] == *s2_ptr)) { 76 ++s2_ptr; 77 ++matched; 78 } 79 return matched; 80 } 81 #endif 82 83 } // namespace brotli 84 85 #endif // BROTLI_ENC_FIND_MATCH_LENGTH_H_ 86
