5 ms·
If I'm not wrong, UTF-8 continuation bytes always start with binary 10, where ASCII always starts with 0 and multi-byte starts start with either 11 (2 bytes), 1
by Felk 9y ago
If I'm not wrong, UTF-8 continuation bytes always start with binary 10, where ASCII always starts with 0 and multi-byte starts start with either 11 (2 bytes), 111 (3 bytes) or 1111 (4 bytes)
- paulddraper 9y agoCorrect. This is what makes UTF-8 is "self-correcting", in that you can always find which code unit you are at for a code point.
- Manishearth 9y agoThat doesn't solve the problem of searching for multibyte character AB and finding multibyte character CB instead :) Or, searching for multibyte character ABB (like U+A041 YI SYLLABLE PA) and finding the first "B" instead of the second "B". Sadly there's no memchr for consecutive sequences of characters. memchr2/memchr3 let you search for multiple needles in the haystack, not a bigger needle.
- comex 9y agoThere’s memmem...
- burntsushi 9y agomemmem is substring search. You could use it for char search, but does memmem know about UTF-8? If, say, memmem uses memchr internally in a skip loop and it happens to look at the first byte in the UTF-8 encoded codepoint, then it is going to perform a lot worse in most cases involving the search of text that is in a language other than English (because it will wind up searching for a very common byte). Or maybe memmem does something else clever for shorter needles. Dunno. Best to benchmark it. But it's not an obvious win a priori.
- Manishearth 9y agoI do want to see if a 2/3/4-byte memchr can be written that uses the same bitmasking as regular memchr but extended to more bits (perhaps via SIMD). That would be pretty neat.
- burntsushi 9y agoYeah that's what I was thinking memmem might do. But yeah, I bet you that Hyperscan has a vectorized algorithm for this somewhere. It is just a matter of finding it.
- deleted 9y ago[deleted]
- comex 9y agoYeah, I suspect it wouldn't actually be a win, though of course it will depend on the implementation. Just pointing out that "there's no memchr for consecutive sequence of characters" isn't exactly true.
- Manishearth 9y agoI mean, you can count a simple string search loop as "memchr for consecutive sequences" as well, what I meant was a technique that uses the same bitmasking trick as memchr, applied to multiple bytes (perhaps via SIMD). It's doable.