I have a need to encode/decode hex characters without using the standard library's built-in utilities (for performance - I'm working on the level of a single, known-to-be-ASCII character as a UInt8
, rather than a full-blown UTF8 String
). The generally-accepted fastest way to do this is using a lookup table, like this:
/// Returns the ASCII value corresponding to the low nibble of `number`, encoded as hex.
func ascii_getHexDigit(_ number: UInt8) -> UInt8 {
let table: StaticString = "0123456789ABCDEF"
return table.withUTF8Buffer { table in
table[Int(number & 0x0F)]
}
}
/// Returns the numerical value of a hex digit, or 99 if the character is not a hex digit.
func ascii_parseHexDigit(ascii: UInt8) -> UInt8 {
let (index, underflow) = ascii.subtractingReportingOverflow(0x30)
guard underflow == false else { return 99 }
let table = [
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, // numbers 0-9
99, 99, 99, 99, 99, 99, 99, // 7 invalid chars from ':' to '@'
10, 11, 12, 13, 14, 15, // uppercase A-F
99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, // 20 invalid chars G-Z
99, 99, 99, 99, 99, 99, // 6 invalid chars from '[' to '`'
10, 11, 12, 13, 14, 15, // lowercase a-f
99 as UInt8 // for type inference
]
guard index < table.count else { return 99 }
return table[Int(index)]
}
I really need to micro-optimise this code as part of a parser I'm building. For the StaticString
case, this looks good. The produced assembly is basically optimal:
output.ascii_getHexDigit(Swift.UInt8) -> Swift.UInt8:
push rbp
mov rbp, rsp
and edi, 15
lea rax, [rip + .L__unnamed_1]
mov al, byte ptr [rdi + rax]
pop rbp
ret
However, for the second case (a let
array of bytes), the result isn't so amazing. There are 4 runtime calls, including retain/release:
output.ascii_parseHexDigit(ascii: Swift.UInt8) -> Swift.UInt8:
push rbp
mov rbp, rsp
push r15
push r14
push rbx
push rax
mov ebx, edi
mov r15b, 99
sub bl, 48
jb .LBB2_4
lea rdi, [rip + (demangling cache variable for type metadata for Swift._ContiguousArrayStorage<Swift.UInt8>)]
call __swift_instantiateConcreteTypeFromMangledName
lea rsi, [rip + (outlined variable #0 of output.ascii_parseHexDigit(ascii: Swift.UInt8) -> Swift.UInt8)+8]
mov rdi, rax
call swift_initStaticObject@PLT
mov r14, rax
mov rdi, rax
call swift_retain@PLT
mov r15b, 99
cmp bl, 55
ja .LBB2_3
movzx eax, bl
mov r15b, byte ptr [r14 + rax + 32]
.LBB2_3:
mov rdi, r14
call swift_release@PLT
.LBB2_4:
mov eax, r15d
add rsp, 8
pop rbx
pop r14
pop r15
pop rbp
ret
I've tried rewriting this as a tuple, but that also isn't amazing. It avoids the runtime calls, which is nice, but since tuples don't have subscript operations, I need to use pointers and offsets to access the elements. Unfortunately, this means copying the tuple to a temporary inside the function (see Godbolt link).
Does anybody know the optimal way to create a numerical lookup table in Swift? What I'd like is something that results in essentially the same assembly as the StaticString
example. I could encode the table as a String, but that just seems kind of ridiculous.