Bob Steagall presents a fast, DFA-based approach to UTF-8 conversion using SSE intrinsics and lookup tables.
CppCon.org
—
Presentation Slides, PDFs, Source Code and other presenter materials are available at: github.com/CppCon/CppCon2018
—
UTF-8 is taking on an increasingly important role in text processing. Many applications require the conversion of UTF-8 to UTF-16 or UTF-32, but typical conversion algorithms are sub-optimal. This talk will describe a fast, correct, DFA-based approach to UTF-8 conversion that requires only three simple lookup tables and a small amount of straightforward C++ code.
We'll begin with a quick review UTF-8 and its relation to UTF-16 and UTF-32, as well as the concept of code units and code points. Next, we'll look at the layout of bits within a UTF-8 byte sequence, and from that, show a simple algorithm for converting from UTF-8 to UTF-32. Along the way will be a definition of overlong and invalid byte sequences. Following that will be a discussion of how to construct a DFA to perform the same operations as the simple algorithm. We'll then look at code for the DFA traversal underlying the basic conversion algorithm, and how to gain an additional performance boost by using SSE intrinsics.
Finally, we'll compare the performance of this approach to several commonly-available implementations on Windows and Linux, and show how it's possible to do significantly faster conversions.
—
Bob Steagall, KEWB Computing
CppCon Poster Chair
I've been working in C++ since discovering the second edition of The C++ Programming Language in a college bookstore in 1992. The majority of my career has been spent in medical imaging, where I led teams building applications for functional MRI and CT-based cardiac visualization. After a brief detour through the world of DNS and analytics, I'm now working in the area of distributed stream processing. I'm a relatively new member of the C++ Standardization Committee, and launched a blog earlier this year to write about C++ and related topics. I hold BS and MS degrees in Physics, and I'm an avid cyclist when weather permits.
—
Videos Filmed & Edited by Bash Films: BashFilms.com
Work at Hudson River Trading (HRT): tinyurl.com/safxfctf
---
Videos Filmed & Edited by Bash Films: BashFilms.com
Why it's here
2 people recommend this
What people say. Recommended as a great talk on validating and converting UTF-8 using SIMD and DFA techniques.
A
u/Axman6in r/C_Programming • Recommends
On “How to get the UTF-8 Byte Width and Validate the byte sequence.”
Bob Steagall has a great talk on validating UTF-8 using SIMD, which niche change how you think about the problem: link to this video
A few years ago I implemented some low level functions in Haskell for the `text` package to count how many characters it contained, or find the byte offset of a given character index. I used some SWAR (SIMD with a register) techniques to parse the data eight bytes at a time instead of converting each character to a value representing a character. Probably the coolest trick was using masks and shifts to end up with an int64 which had the lowest bit set in each byte that was a continuation byte - 0x00010100000101. If you multiply that by the constant 0x0101010101010101, yo…
On “Seeking a C/C++ UTF-8 wrapper for Windows ANSI C Standard Library functions”
Can't remember if I saw this posted here or on one of the C++ subs but Bob Steagall's UTF-8 conversion work is easily translatable to C and supposedly it is pretty fast.
[video
https://github.com/BobSteagall/utf\_utils/tree/master
