Skip to content

Instantly share code, notes, and snippets.

@Araq
Created July 7, 2020 07:37
Show Gist options
  • Save Araq/ea3ef89780dcbeb5730f4b058f016218 to your computer and use it in GitHub Desktop.
Save Araq/ea3ef89780dcbeb5730f4b058f016218 to your computer and use it in GitHub Desktop.
const
intrin = "<x86intrin.h>"
{.localPassC: "-msse4.2".}
type
M128i {.importc: "__m128i", header: intrin, bycopy.} = object
const
SIDD_CMP_RANGES = 0b0000_0100'i32
SIDD_NEGATIVE_POLARITY = 0b0001_0000'i32
proc mm_loadu_si128(p: pointer): M128i {.importc: "_mm_loadu_si128", header: intrin.}
proc mm_cmpestri(a: M128i; alen: int32; b: M128i; blen: int32;
options: int32): int32 {.importc: "_mm_cmpestri", header: intrin.}
template `+!`(p: pointer, s: int): pointer =
cast[pointer](cast[int](p) +% s)
proc inSseSet(c: char; ranges: string): bool =
# Since C did win nobody knows anymore how to represent set[char] properly so
# we have to do this crap for SSE4.2.
var i = 0
while i < ranges.len:
if ranges[i] <= c and c <= ranges[i+1]: return true
inc i, 2
proc scan(haystack: string; ranges: string): int =
result = 0
if haystack.len >= 16:
let ranges16 = mm_loadu_si128(unsafeAddr(ranges[0]))
var left = haystack.len # and (not 15)
var buf = cast[pointer](unsafeAddr haystack[0])
while true:
let b16 = mm_loadu_si128(buf)
let r = mm_cmpestri(ranges16, ranges.len.int32, b16, 16, SIDD_CMP_RANGES or SIDD_NEGATIVE_POLARITY)
inc result, r
if r != 16:
return result
buf = buf +! 16
dec left, 16
if left <= 0: break
else:
for i in 0 ..< haystack.len:
if not haystack[i].inSseSet(ranges):
return i
result = -1
proc scanB(haystack: string; ranges: string): int =
for i in 0 ..< haystack.len:
if not haystack[i].inSseSet(ranges):
return i
result = -1
proc sseSet(s: set[char]): string =
var last = '\0'
result = ""
for elem in s:
if result.len == 0:
result.add elem
result.add elem
elif pred(elem) == last:
result[^1] = elem # patch last interval
else:
result.add elem
result.add elem
last = elem
let identChars = sseSet({'A'..'Z', 'a'..'z', '_', '0'..'9'})
echo scan("ABCDEFGHIJKLMNOP+QRTUVWXYZ ", identChars)
echo scanB("ABCDEFGHIJKLMNOP+QRTUVWXYZ ", identChars)
echo find("ABCDEFGHIJKLMNOP+QRTUVWXYZ ", '+')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment