Eugene Klyuchnikov | 771eb10 | 2015-11-27 11:27:11 +0100 | [diff] [blame] | 1 | /* Copyright 2010 Google Inc. All Rights Reserved. |
| 2 | |
Eugene Klyuchnikov | 24ffa78 | 2015-12-11 11:11:51 +0100 | [diff] [blame] | 3 | Distributed under MIT license. |
Eugene Klyuchnikov | 771eb10 | 2015-11-27 11:27:11 +0100 | [diff] [blame] | 4 | See file LICENSE for detail or copy at https://opensource.org/licenses/MIT |
| 5 | */ |
| 6 | |
Eugene Kliuchnikov | 352b0b2 | 2016-06-03 11:19:23 +0200 | [diff] [blame] | 7 | /* Function to find maximal matching prefixes of strings. */ |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 8 | |
| 9 | #ifndef BROTLI_ENC_FIND_MATCH_LENGTH_H_ |
| 10 | #define BROTLI_ENC_FIND_MATCH_LENGTH_H_ |
| 11 | |
Eugene Kliuchnikov | da254cf | 2017-12-12 14:33:12 +0100 | [diff] [blame] | 12 | #include "../common/platform.h" |
Eugene Kliuchnikov | 8148001 | 2016-08-23 14:40:33 +0200 | [diff] [blame] | 13 | #include <brotli/types.h> |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 14 | |
Eugene Kliuchnikov | b972c67 | 2016-06-13 11:01:04 +0200 | [diff] [blame] | 15 | #if defined(__cplusplus) || defined(c_plusplus) |
| 16 | extern "C" { |
| 17 | #endif |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 18 | |
Eugene Kliuchnikov | 352b0b2 | 2016-06-03 11:19:23 +0200 | [diff] [blame] | 19 | /* Separate implementation for little-endian 64-bit targets, for speed. */ |
Eugene Kliuchnikov | d63e8f7 | 2017-08-04 10:02:56 +0200 | [diff] [blame] | 20 | #if defined(__GNUC__) && defined(_LP64) && defined(BROTLI_LITTLE_ENDIAN) |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 21 | |
Eugene Kliuchnikov | b972c67 | 2016-06-13 11:01:04 +0200 | [diff] [blame] | 22 | static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1, |
| 23 | const uint8_t* s2, |
| 24 | size_t limit) { |
Zoltan Szabadka | 8844b7f | 2016-01-07 16:27:49 +0100 | [diff] [blame] | 25 | size_t matched = 0; |
Eugene Kliuchnikov | 352b0b2 | 2016-06-03 11:19:23 +0200 | [diff] [blame] | 26 | size_t limit2 = (limit >> 3) + 1; /* + 1 is for pre-decrement in while */ |
Eugene Kliuchnikov | 69982c2 | 2016-10-18 16:45:32 +0200 | [diff] [blame] | 27 | while (BROTLI_PREDICT_TRUE(--limit2)) { |
Eugene Kliuchnikov | d63e8f7 | 2017-08-04 10:02:56 +0200 | [diff] [blame] | 28 | if (BROTLI_PREDICT_FALSE(BROTLI_UNALIGNED_LOAD64LE(s2) == |
| 29 | BROTLI_UNALIGNED_LOAD64LE(s1 + matched))) { |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 30 | s2 += 8; |
| 31 | matched += 8; |
| 32 | } else { |
Eugene Kliuchnikov | d63e8f7 | 2017-08-04 10:02:56 +0200 | [diff] [blame] | 33 | uint64_t x = BROTLI_UNALIGNED_LOAD64LE(s2) ^ |
| 34 | BROTLI_UNALIGNED_LOAD64LE(s1 + matched); |
Eugene Kliuchnikov | b972c67 | 2016-06-13 11:01:04 +0200 | [diff] [blame] | 35 | size_t matching_bits = (size_t)__builtin_ctzll(x); |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 36 | matched += matching_bits >> 3; |
| 37 | return matched; |
| 38 | } |
| 39 | } |
Eugene Kliuchnikov | 352b0b2 | 2016-06-03 11:19:23 +0200 | [diff] [blame] | 40 | limit = (limit & 7) + 1; /* + 1 is for pre-decrement in while */ |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 41 | while (--limit) { |
Eugene Kliuchnikov | 69982c2 | 2016-10-18 16:45:32 +0200 | [diff] [blame] | 42 | if (BROTLI_PREDICT_TRUE(s1[matched] == *s2)) { |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 43 | ++s2; |
| 44 | ++matched; |
| 45 | } else { |
| 46 | return matched; |
| 47 | } |
| 48 | } |
| 49 | return matched; |
| 50 | } |
| 51 | #else |
Eugene Kliuchnikov | b972c67 | 2016-06-13 11:01:04 +0200 | [diff] [blame] | 52 | static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1, |
| 53 | const uint8_t* s2, |
| 54 | size_t limit) { |
Zoltan Szabadka | 8844b7f | 2016-01-07 16:27:49 +0100 | [diff] [blame] | 55 | size_t matched = 0; |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 56 | const uint8_t* s2_limit = s2 + limit; |
| 57 | const uint8_t* s2_ptr = s2; |
Eugene Kliuchnikov | 352b0b2 | 2016-06-03 11:19:23 +0200 | [diff] [blame] | 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. */ |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 62 | while (s2_ptr <= s2_limit - 4 && |
Eugene Kliuchnikov | da254cf | 2017-12-12 14:33:12 +0100 | [diff] [blame] | 63 | BrotliUnalignedRead32(s2_ptr) == |
| 64 | BrotliUnalignedRead32(s1 + matched)) { |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 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 | |
Eugene Kliuchnikov | b972c67 | 2016-06-13 11:01:04 +0200 | [diff] [blame] | 76 | #if defined(__cplusplus) || defined(c_plusplus) |
| 77 | } /* extern "C" */ |
| 78 | #endif |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 79 | |
Eugene Kliuchnikov | 352b0b2 | 2016-06-03 11:19:23 +0200 | [diff] [blame] | 80 | #endif /* BROTLI_ENC_FIND_MATCH_LENGTH_H_ */ |