projects / mirror_edk2.git / blame
| Commit | Line | Data |
|---|---|---|
| 11b7501a SB |
1 | /* Copyright 2010 Google Inc. All Rights Reserved.\r |
| 2 | \r | |
| 3 | Distributed under MIT license.\r | |
| 4 | See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r | |
| 5 | */\r | |
| 6 | \r | |
| 7 | /* Function to find maximal matching prefixes of strings. */\r | |
| 8 | \r | |
| 9 | #ifndef BROTLI_ENC_FIND_MATCH_LENGTH_H_\r | |
| 10 | #define BROTLI_ENC_FIND_MATCH_LENGTH_H_\r | |
| 11 | \r | |
| 12 | #include "../common/types.h"\r | |
| 13 | #include "./port.h"\r | |
| 14 | \r | |
| 15 | #if defined(__cplusplus) || defined(c_plusplus)\r | |
| 16 | extern "C" {\r | |
| 17 | #endif\r | |
| 18 | \r | |
| 19 | /* Separate implementation for little-endian 64-bit targets, for speed. */\r | |
| 20 | #if defined(__GNUC__) && defined(_LP64) && defined(IS_LITTLE_ENDIAN)\r | |
| 21 | \r | |
| 22 | static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1,\r | |
| 23 | const uint8_t* s2,\r | |
| 24 | size_t limit) {\r | |
| 25 | size_t matched = 0;\r | |
| 26 | size_t limit2 = (limit >> 3) + 1; /* + 1 is for pre-decrement in while */\r | |
| 27 | while (PREDICT_TRUE(--limit2)) {\r | |
| 28 | if (PREDICT_FALSE(BROTLI_UNALIGNED_LOAD64(s2) ==\r | |
| 29 | BROTLI_UNALIGNED_LOAD64(s1 + matched))) {\r | |
| 30 | s2 += 8;\r | |
| 31 | matched += 8;\r | |
| 32 | } else {\r | |
| 33 | uint64_t x =\r | |
| 34 | BROTLI_UNALIGNED_LOAD64(s2) ^ BROTLI_UNALIGNED_LOAD64(s1 + matched);\r | |
| 35 | size_t matching_bits = (size_t)__builtin_ctzll(x);\r | |
| 36 | matched += matching_bits >> 3;\r | |
| 37 | return matched;\r | |
| 38 | }\r | |
| 39 | }\r | |
| 40 | limit = (limit & 7) + 1; /* + 1 is for pre-decrement in while */\r | |
| 41 | while (--limit) {\r | |
| 42 | if (PREDICT_TRUE(s1[matched] == *s2)) {\r | |
| 43 | ++s2;\r | |
| 44 | ++matched;\r | |
| 45 | } else {\r | |
| 46 | return matched;\r | |
| 47 | }\r | |
| 48 | }\r | |
| 49 | return matched;\r | |
| 50 | }\r | |
| 51 | #else\r | |
| 52 | static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1,\r | |
| 53 | const uint8_t* s2,\r | |
| 54 | size_t limit) {\r | |
| 55 | size_t matched = 0;\r | |
| 56 | const uint8_t* s2_limit = s2 + limit;\r | |
| 57 | const uint8_t* s2_ptr = s2;\r | |
| 58 | /* Find out how long the match is. We loop over the data 32 bits at a\r | |
| 59 | time until we find a 32-bit block that doesn't match; then we find\r | |
| 60 | the first non-matching bit and use that to calculate the total\r | |
| 61 | length of the match. */\r | |
| 62 | while (s2_ptr <= s2_limit - 4 &&\r | |
| 63 | BROTLI_UNALIGNED_LOAD32(s2_ptr) ==\r | |
| 64 | BROTLI_UNALIGNED_LOAD32(s1 + matched)) {\r | |
| 65 | s2_ptr += 4;\r | |
| 66 | matched += 4;\r | |
| 67 | }\r | |
| 68 | while ((s2_ptr < s2_limit) && (s1[matched] == *s2_ptr)) {\r | |
| 69 | ++s2_ptr;\r | |
| 70 | ++matched;\r | |
| 71 | }\r | |
| 72 | return matched;\r | |
| 73 | }\r | |
| 74 | #endif\r | |
| 75 | \r | |
| 76 | #if defined(__cplusplus) || defined(c_plusplus)\r | |
| 77 | } /* extern "C" */\r | |
| 78 | #endif\r | |
| 79 | \r | |
| 80 | #endif /* BROTLI_ENC_FIND_MATCH_LENGTH_H_ */\r |