Line data    Source code

       1             : // Copyright 2016 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/string-case.h"
       6             : 
       7             : #include "src/assert-scope.h"
       8             : #include "src/base/logging.h"
       9             : #include "src/globals.h"
      10             : #include "src/utils.h"
      11             : 
      12             : namespace v8 {
      13             : namespace internal {
      14             : 
      15             : #ifdef DEBUG
      16             : bool CheckFastAsciiConvert(char* dst, const char* src, int length, bool changed,
      17             :                            bool is_to_lower) {
      18             :   bool expected_changed = false;
      19             :   for (int i = 0; i < length; i++) {
      20             :     if (dst[i] == src[i]) continue;
      21             :     expected_changed = true;
      22             :     if (is_to_lower) {
      23             :       DCHECK('A' <= src[i] && src[i] <= 'Z');
      24             :       DCHECK(dst[i] == src[i] + ('a' - 'A'));
      25             :     } else {
      26             :       DCHECK('a' <= src[i] && src[i] <= 'z');
      27             :       DCHECK(dst[i] == src[i] - ('a' - 'A'));
      28             :     }
      29             :   }
      30             :   return (expected_changed == changed);
      31             : }
      32             : #endif
      33             : 
      34             : const uintptr_t kOneInEveryByte = kUintptrAllBitsSet / 0xFF;
      35             : const uintptr_t kAsciiMask = kOneInEveryByte << 7;
      36             : 
      37             : // Given a word and two range boundaries returns a word with high bit
      38             : // set in every byte iff the corresponding input byte was strictly in
      39             : // the range (m, n). All the other bits in the result are cleared.
      40             : // This function is only useful when it can be inlined and the
      41             : // boundaries are statically known.
      42             : // Requires: all bytes in the input word and the boundaries must be
      43             : // ASCII (less than 0x7F).
      44             : static inline uintptr_t AsciiRangeMask(uintptr_t w, char m, char n) {
      45             :   // Use strict inequalities since in edge cases the function could be
      46             :   // further simplified.
      47             :   DCHECK(0 < m && m < n);
      48             :   // Has high bit set in every w byte less than n.
      49      100643 :   uintptr_t tmp1 = kOneInEveryByte * (0x7F + n) - w;
      50             :   // Has high bit set in every w byte greater than m.
      51      100643 :   uintptr_t tmp2 = w + kOneInEveryByte * (0x7F - m);
      52      100643 :   return (tmp1 & tmp2 & (kOneInEveryByte * 0x80));
      53             : }
      54             : 
      55             : template <bool is_lower>
      56        6854 : int FastAsciiConvert(char* dst, const char* src, int length,
      57             :                      bool* changed_out) {
      58             : #ifdef DEBUG
      59             :   char* saved_dst = dst;
      60             : #endif
      61             :   const char* saved_src = src;
      62             :   DisallowHeapAllocation no_gc;
      63             :   // We rely on the distance between upper and lower case letters
      64             :   // being a known power of 2.
      65             :   DCHECK_EQ('a' - 'A', 1 << 5);
      66             :   // Boundaries for the range of input characters than require conversion.
      67             :   static const char lo = is_lower ? 'A' - 1 : 'a' - 1;
      68             :   static const char hi = is_lower ? 'Z' + 1 : 'z' + 1;
      69             :   bool changed = false;
      70        6854 :   const char* const limit = src + length;
      71             : 
      72             :   // dst is newly allocated and always aligned.
      73             :   DCHECK(IsAligned(reinterpret_cast<intptr_t>(dst), sizeof(uintptr_t)));
      74             :   // Only attempt processing one word at a time if src is also aligned.
      75        6854 :   if (IsAligned(reinterpret_cast<intptr_t>(src), sizeof(uintptr_t))) {
      76             :     // Process the prefix of the input that requires no conversion one aligned
      77             :     // (machine) word at a time.
      78        8618 :     while (src <= limit - sizeof(uintptr_t)) {
      79        5313 :       const uintptr_t w = *reinterpret_cast<const uintptr_t*>(src);
      80        5313 :       if ((w & kAsciiMask) != 0) return static_cast<int>(src - saved_src);
      81        5259 :       if (AsciiRangeMask(w, lo, hi) != 0) {
      82             :         changed = true;
      83             :         break;
      84             :       }
      85        2196 :       *reinterpret_cast<uintptr_t*>(dst) = w;
      86        2196 :       src += sizeof(uintptr_t);
      87        2196 :       dst += sizeof(uintptr_t);
      88             :     }
      89             :     // Process the remainder of the input performing conversion when
      90             :     // required one word at a time.
      91      101752 :     while (src <= limit - sizeof(uintptr_t)) {
      92       95402 :       const uintptr_t w = *reinterpret_cast<const uintptr_t*>(src);
      93       95402 :       if ((w & kAsciiMask) != 0) return static_cast<int>(src - saved_src);
      94             :       uintptr_t m = AsciiRangeMask(w, lo, hi);
      95             :       // The mask has high (7th) bit set in every byte that needs
      96             :       // conversion and we know that the distance between cases is
      97             :       // 1 << 5.
      98       95384 :       *reinterpret_cast<uintptr_t*>(dst) = w ^ (m >> 2);
      99       95384 :       src += sizeof(uintptr_t);
     100       95384 :       dst += sizeof(uintptr_t);
     101             :     }
     102             :   }
     103             :   // Process the last few bytes of the input (or the whole input if
     104             :   // unaligned access is not supported).
     105      134072 :   while (src < limit) {
     106      127448 :     char c = *src;
     107      127448 :     if ((c & kAsciiMask) != 0) return static_cast<int>(src - saved_src);
     108      127290 :     if (lo < c && c < hi) {
     109       30797 :       c ^= (1 << 5);
     110             :       changed = true;
     111             :     }
     112      127290 :     *dst = c;
     113      127290 :     ++src;
     114      127290 :     ++dst;
     115             :   }
     116             : 
     117             :   DCHECK(
     118             :       CheckFastAsciiConvert(saved_dst, saved_src, length, changed, is_lower));
     119             : 
     120        6624 :   *changed_out = changed;
     121        6624 :   return length;
     122             : }
     123             : 
     124             : template int FastAsciiConvert<false>(char* dst, const char* src, int length,
     125             :                                      bool* changed_out);
     126             : template int FastAsciiConvert<true>(char* dst, const char* src, int length,
     127             :                                     bool* changed_out);
     128             : 
     129             : }  // namespace internal
     130      178779 : }  // namespace v8