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
CheckFastAsciiConvert(char * dst,const char * src,int length,bool changed,bool is_to_lower)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).
AsciiRangeMask(uintptr_t w,char m,char n)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>
FastAsciiConvert(char * dst,const char * src,int length,bool * changed_out)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