1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
|
from rpython.rtyper.lltypesystem import lltype, rffi
from rpython.rlib import objectmodel, unroll
from rpython.rlib.rarithmetic import r_uint, intmask, LONG_BIT
from rpython.jit.backend.detect_cpu import autodetect, ProcessorAutodetectError
# accelerators for string operations using simd on regular word sizes (*not*
# SSE instructions). this style is sometimes called SWAR (SIMD Within A
# Register) or "broadword techniques"
# XXX remove wordsize and endianness restrictions properly, so far only x86-64
# is tested
USE_SIMD = False
if LONG_BIT == 64:
WORD_SIZE = 8
EVERY_BYTE_ONE = 0x0101010101010101
EVERY_BYTE_HIGHEST_BIT = 0x8080808080808080
try:
if autodetect() == "x86-64":
USE_SIMD = True
except ProcessorAutodetectError:
pass
else:
WORD_SIZE = 4
EVERY_BYTE_ONE = 0x01010101
EVERY_BYTE_HIGHEST_BIT = 0x80808080
# helpers
unrolling_wordsize = unroll.unrolling_iterable(range(WORD_SIZE))
def char_repeated_word_width(ch):
return r_uint(EVERY_BYTE_ONE) * ord(ch)
def any_char_zero(word):
return (word - r_uint(EVERY_BYTE_ONE)) & ~word & r_uint(EVERY_BYTE_HIGHEST_BIT)
def any_char_in_words_zero(*words):
return _any_char_in_any_word_zero_accum(0, *words)
def _any_char_in_any_word_zero_accum(accum, word, *words):
accum |= (word - r_uint(EVERY_BYTE_ONE)) & ~word
if not words:
return accum & r_uint(EVERY_BYTE_HIGHEST_BIT)
return _any_char_in_any_word_zero_accum(accum, *words)
def print_chars(word):
# for debugging
out = ''
for i in range(WORD_SIZE):
out += chr(word & 0xff)
word >>= 8
return out
def index_nonzero(word):
# XXX can be done very cheap in theory
assert word
for i in unrolling_wordsize:
if word & 0xff:
return i
word >>= 8
assert 0
def index_zero(word):
# XXX can be done very cheap in theory
assert any_char_zero(word)
for i in unrolling_wordsize:
if not word & 0xff:
return i
word >>= 8
assert 0 # XXX ???
def set_high_bytes_to_zero(word, keep_bytes):
mask = ((~r_uint(0)) << (8 * keep_bytes))
return word & ~mask
@objectmodel.always_inline
def position_string_ender(word):
maskquote = char_repeated_word_width('"')
maskbackslash = char_repeated_word_width('\\')
maskx20 = char_repeated_word_width(chr(0xff - 0x1f))
# x1 and x2 check for equality, if a byte is 0 the corresponding
# char is equal to " or \
x1 = maskquote ^ word
x2 = maskbackslash ^ word
# x3 checks for char < 0x20, the byte is 0 in that case
x3 = maskx20 & word
return any_char_in_words_zero(x1, x2, x3)
@objectmodel.always_inline
def find_end_of_string_simd_unaligned(ll_chars, startpos, length):
ch = ll_chars[startpos]
strhash = (ord(ch) << 7) ^ 0x345678
wordarray = rffi.cast(rffi.UNSIGNEDP, rffi.ptradd(ll_chars, startpos))
num_safe_reads = (length - startpos) // WORD_SIZE
bits = 0
for i in range(num_safe_reads):
word = wordarray[i]
cond = position_string_ender(word)
if cond:
break
bits |= word
strhash = intmask((1000003 * strhash) ^ intmask(word))
else:
# didn't find end of string yet, look at remaining chars
word = 0
shift = 0
i = startpos + num_safe_reads * WORD_SIZE
while True: # this loop should run at most WORD_SIZE times,
# if we assume that ll_chars[length] == '\x00'
ch = ll_chars[i]
if ch == '"' or ch == '\\' or ch < '\x20':
break
i += 1
bits |= ord(ch)
word |= ord(ch) << shift
shift += 8
if shift:
strhash = intmask((1000003 * strhash) ^ intmask(word))
nonascii = bool(bits & char_repeated_word_width(chr(0x80)))
return strhash, nonascii, i
# compute endposition
nonzero = index_nonzero(cond)
endposition = startpos + i * WORD_SIZE + nonzero
if nonzero:
word = set_high_bytes_to_zero(word, nonzero)
bits |= word
strhash = intmask((1000003 * strhash) ^ intmask(word))
nonascii = bool(bits & char_repeated_word_width(chr(0x80)))
return strhash, nonascii, endposition
@objectmodel.always_inline
def find_end_of_string_simd_unaligned_no_hash(ll_chars, startpos, length):
ch = ll_chars[startpos]
wordarray = rffi.cast(rffi.UNSIGNEDP, rffi.ptradd(ll_chars, startpos))
num_safe_reads = (length - startpos) // WORD_SIZE
bits = 0
for i in range(num_safe_reads):
word = wordarray[i]
cond = position_string_ender(word)
if cond:
break
bits |= word
else:
# didn't find end of string yet, look at remaining chars
i = startpos + num_safe_reads * WORD_SIZE
while True: # this loop should run at most WORD_SIZE times,
# if we assume that ll_chars[length] == '\x00'
ch = ll_chars[i]
if ch == '"' or ch == '\\' or ch < '\x20':
break
i += 1
bits |= ord(ch)
nonascii = bool(bits & char_repeated_word_width(chr(0x80)))
return nonascii, i
# compute endposition
nonzero = index_nonzero(cond)
endposition = startpos + i * WORD_SIZE + nonzero
if nonzero:
word = set_high_bytes_to_zero(word, nonzero)
bits |= word
nonascii = bool(bits & char_repeated_word_width(chr(0x80)))
return nonascii, endposition
@objectmodel.always_inline
def find_end_of_string_slow(ll_chars, i, length):
ch = ll_chars[i]
strhash = (ord(ch) << 7) ^ 0x345678
word = 0
shift = 0
bits = 0
while True:
# this loop is a fast path for strings which do not contain escape
# characters
ch = ll_chars[i]
if ch == '"' or ch == '\\' or ch < '\x20':
break
i += 1
bits |= ord(ch)
word |= ord(ch) << shift
shift += 8
if shift == WORD_SIZE * 8:
strhash = intmask((1000003 * strhash) ^ word)
shift = 0
word = 0
if shift:
strhash = intmask((1000003 * strhash) ^ word)
return strhash, bool(bits & 0x80), i
@objectmodel.always_inline
def find_end_of_string_slow_no_hash(ll_chars, i, length):
bits = 0
while True:
# this loop is a fast path for strings which do not contain escape
# characters
ch = ll_chars[i]
if ch == '"' or ch == '\\' or ch < '\x20':
break
i += 1
bits |= ord(ch)
return bool(bits & 0x80), i
if USE_SIMD:
find_end_of_string = find_end_of_string_simd_unaligned
find_end_of_string_no_hash = find_end_of_string_simd_unaligned_no_hash
else:
find_end_of_string = find_end_of_string_slow
find_end_of_string_no_hash = find_end_of_string_slow_no_hash
|
