kc3-lang/brotli/enc/find_match_length.h

• Show log

  Commit

• Hash : e643328a
  Author :
  Date : 2015-02-25T10:24:13
  

  Speed up FindMatchLength for non-x86 64-bit targets.
  
  This CL enables 64-bit optimization for non-x86 target.
  

Download

• enc/find_match_length.h

• // Copyright 2010 Google Inc. All Rights Reserved.
  //
  // Licensed under the Apache License, Version 2.0 (the "License");
  // you may not use this file except in compliance with the License.
  // You may obtain a copy of the License at
  //
  // http://www.apache.org/licenses/LICENSE-2.0
  //
  // Unless required by applicable law or agreed to in writing, software
  // distributed under the License is distributed on an "AS IS" BASIS,
  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  // See the License for the specific language governing permissions and
  // limitations under the License.
  //
  // Function to find maximal matching prefixes of strings.
  
  #ifndef BROTLI_ENC_FIND_MATCH_LENGTH_H_
  #define BROTLI_ENC_FIND_MATCH_LENGTH_H_
  
  #include <stdint.h>
  
  #include <stddef.h>
  
  #include "./port.h"
  
  namespace brotli {
  
  // Separate implementation for little-endian 64-bit targets, for speed.
  #if defined(__GNUC__) && defined(_LP64) && defined(IS_LITTLE_ENDIAN)
  
  static inline int FindMatchLengthWithLimit(const uint8_t* s1,
                                             const uint8_t* s2,
                                             size_t limit) {
    int matched = 0;
    size_t limit2 = (limit >> 3) + 1;  // + 1 is for pre-decrement in while
    while (PREDICT_TRUE(--limit2)) {
      if (PREDICT_FALSE(BROTLI_UNALIGNED_LOAD64(s2) ==
                        BROTLI_UNALIGNED_LOAD64(s1 + matched))) {
        s2 += 8;
        matched += 8;
      } else {
        uint64_t x =
            BROTLI_UNALIGNED_LOAD64(s2) ^ BROTLI_UNALIGNED_LOAD64(s1 + matched);
        int matching_bits =  __builtin_ctzll(x);
        matched += matching_bits >> 3;
        return matched;
      }
    }
    limit = (limit & 7) + 1;  // + 1 is for pre-decrement in while
    while (--limit) {
      if (PREDICT_TRUE(s1[matched] == *s2)) {
        ++s2;
        ++matched;
      } else {
        return matched;
      }
    }
    return matched;
  }
  #else
  static inline int FindMatchLengthWithLimit(const uint8_t* s1,
                                             const uint8_t* s2,
                                             size_t limit) {
    int matched = 0;
    const uint8_t* s2_limit = s2 + limit;
    const uint8_t* s2_ptr = s2;
    // Find out how long the match is. We loop over the data 32 bits at a
    // time until we find a 32-bit block that doesn't match; then we find
    // the first non-matching bit and use that to calculate the total
    // length of the match.
    while (s2_ptr <= s2_limit - 4 &&
           BROTLI_UNALIGNED_LOAD32(s2_ptr) ==
           BROTLI_UNALIGNED_LOAD32(s1 + matched)) {
      s2_ptr += 4;
      matched += 4;
    }
    while ((s2_ptr < s2_limit) && (s1[matched] == *s2_ptr)) {
      ++s2_ptr;
      ++matched;
    }
    return matched;
  }
  #endif
  
  }  // namespace brotli
  
  #endif  // BROTLI_ENC_FIND_MATCH_LENGTH_H_
  

Download