Home | History | Annotate | Download | only in src 
      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   uintptr_t tmp1 = kOneInEveryByte * (0x7F + n) - w;
     50   // Has high bit set in every w byte greater than m.
     51   uintptr_t tmp2 = w + kOneInEveryByte * (0x7F - m);
     52   return (tmp1 & tmp2 & (kOneInEveryByte * 0x80));
     53 }
     54 
     55 template <bool is_lower>
     56 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('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   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   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     while (src <= limit - sizeof(uintptr_t)) {
     79       const uintptr_t w = *reinterpret_cast<const uintptr_t*>(src);
     80       if ((w & kAsciiMask) != 0) return static_cast<int>(src - saved_src);
     81       if (AsciiRangeMask(w, lo, hi) != 0) {
     82         changed = true;
     83         break;
     84       }
     85       *reinterpret_cast<uintptr_t*>(dst) = w;
     86       src += sizeof(uintptr_t);
     87       dst += sizeof(uintptr_t);
     88     }
     89     // Process the remainder of the input performing conversion when
     90     // required one word at a time.
     91     while (src <= limit - sizeof(uintptr_t)) {
     92       const uintptr_t w = *reinterpret_cast<const uintptr_t*>(src);
     93       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       *reinterpret_cast<uintptr_t*>(dst) = w ^ (m >> 2);
     99       src += sizeof(uintptr_t);
    100       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   while (src < limit) {
    106     char c = *src;
    107     if ((c & kAsciiMask) != 0) return static_cast<int>(src - saved_src);
    108     if (lo < c && c < hi) {
    109       c ^= (1 << 5);
    110       changed = true;
    111     }
    112     *dst = c;
    113     ++src;
    114     ++dst;
    115   }
    116 
    117   DCHECK(
    118       CheckFastAsciiConvert(saved_dst, saved_src, length, changed, is_lower));
    119 
    120   *changed_out = changed;
    121   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 }  // namespace v8
    131