BaseTools/Source/C/BrotliCompress/enc/find_match_length.h

   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/types.h"
  13 #include "./port.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(__GNUC__) && defined(_LP64) && defined(IS_LITTLE_ENDIAN)
  21
  22 static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1,
  23                                                      const uint8_t* s2,
  24                                                      size_t limit) {
  25   size_t matched = 0;
  26   size_t limit2 = (limit >> 3) + 1;  /* + 1 is for pre-decrement in while */
  27   while (PREDICT_TRUE(--limit2)) {
  28     if (PREDICT_FALSE(BROTLI_UNALIGNED_LOAD64(s2) ==
  29                       BROTLI_UNALIGNED_LOAD64(s1 + matched))) {
  30       s2 += 8;
  31       matched += 8;
  32     } else {
  33       uint64_t x =
  34           BROTLI_UNALIGNED_LOAD64(s2) ^ BROTLI_UNALIGNED_LOAD64(s1 + matched);
  35       size_t matching_bits = (size_t)__builtin_ctzll(x);
  36       matched += matching_bits >> 3;
  37       return matched;
  38     }
  39   }
  40   limit = (limit & 7) + 1;  /* + 1 is for pre-decrement in while */
  41   while (--limit) {
  42     if (PREDICT_TRUE(s1[matched] == *s2)) {
  43       ++s2;
  44       ++matched;
  45     } else {
  46       return matched;
  47     }
  48   }
  49   return matched;
  50 }
  51 #else
  52 static BROTLI_INLINE size_t FindMatchLengthWithLimit(const uint8_t* s1,
  53                                                      const uint8_t* s2,
  54                                                      size_t limit) {
  55   size_t matched = 0;
  56   const uint8_t* s2_limit = s2 + limit;
  57   const uint8_t* s2_ptr = s2;
  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. */
  62   while (s2_ptr <= s2_limit - 4 &&
  63          BROTLI_UNALIGNED_LOAD32(s2_ptr) ==
  64          BROTLI_UNALIGNED_LOAD32(s1 + matched)) {
  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
  76 #if defined(__cplusplus) || defined(c_plusplus)
  77 }  /* extern "C" */
  78 #endif
  79
  80 #endif  /* BROTLI_ENC_FIND_MATCH_LENGTH_H_ */