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_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 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