5 ms·

In practice, this sort of thing might be most likely to come up with a chars iterator. The natural iteration logic is something like: 1) If position == end, th

In practice, this sort of thing might be most likely to come up with a chars iterator. The natural iteration logic is something like: 1) If position == end, the iterator is done. 2) Otherwise, read the next byte to determine the number of bytes in the next character. 3) Read all the bytes of the next character, convert them to a regular 32-bit code point, and emit that. In the presence of invalid UTF-8, that iterator is broken. There needs to be an extra check in step 2.5: "Check that the number of bytes reported for the next character doesn't exceed the number of bytes remaining in the string." Iterating over the characters of a string is a pretty common thing to do, and that extra branch is not free.

qppo 6y ago
The check only needs to be done once, when the iterator is constructed. You can also zero pad the buffer by 3 bytes to avoid a bounds check if you really want. This seems like a premature optimization, unless you're only iterating over tiny strings.
- oconnor663 6y ago
  That's a good point. I know in the case of Rust in particular there are other invariants, like that each 32-bit code point is guaranteed to have a valid value. (The compiler knows this and may use unset bits to stash enum state or something like that.) But maybe in other languages without such strict validity guarantees, it's less of a big deal?
jart 6y ago
If the natural logic is broken then you've misunderstood the thing's nature. UTF-8 behaves more like a communications stream that was shoehorned into the purpose of character arrays. If you think about it in that way, then decoding can be done simply and elegantly: #define bsr(u) ((sizeof(int) * 8 - 1) ^ __builtin_clz(u)) #define ThomPikeByte(x) ((x) & (((1 << ThomPikeMsb(x)) - 1) | 3)) #define ThomPikeMsb(x) (((x)&0xff) < 252 ? bsr(~(x)&0xff) : 1) void ThompsonPikeDecoder(const char *s) { unsigned c, w = 0, t = 0; do { c = *s++ & 0xff; if (0200 <= c && c < 0300) { w = w << 6 | c & 077; } else { if (t) { printf("%04x\n", w); t = 0; } if (c < 0200) { printf("%04x\n", c); } else { w = ThomPikeByte(c); t = 1; } } } while (c); } That code generalizes to any 32-bit number. It's the full superset of intended behaviors including things like stream synchronization. It'll even decode numbers that were arbitrarily banned by the IETF e.g. \300\200. Most importantly, since it doesn't require a validation pass beforehand, does that mean it goes faster than the OP's code in praxis? D:
- Dylan16807 6y ago
  I strongly question "doesn't require a validation pass". 1. Your code drops naked continuation bytes entirely. 2. If a valid multibyte character is followed by extraneous continuation bytes it will not decode correctly. 3. Using the wrong number of continuation bytes is a giant mess and can give you arbitrary numbers in multiple ways. The second one especially is a behavior that's hard to defend.

qppo 6y ago

The check only needs to be done once, when the iterator is constructed. You can also zero pad the buffer by 3 bytes to avoid a bounds check if you really want. This seems like a premature optimization, unless you're only iterating over tiny strings.

oconnor663 6y ago
That's a good point. I know in the case of Rust in particular there are other invariants, like that each 32-bit code point is guaranteed to have a valid value. (The compiler knows this and may use unset bits to stash enum state or something like that.) But maybe in other languages without such strict validity guarantees, it's less of a big deal?

jart 6y ago

If the natural logic is broken then you've misunderstood the thing's nature. UTF-8 behaves more like a communications stream that was shoehorned into the purpose of character arrays. If you think about it in that way, then decoding can be done simply and elegantly: #define bsr(u) ((sizeof(int) * 8 - 1) ^ __builtin_clz(u)) #define ThomPikeByte(x) ((x) & (((1 << ThomPikeMsb(x)) - 1) | 3)) #define ThomPikeMsb(x) (((x)&0xff) < 252 ? bsr(~(x)&0xff) : 1) void ThompsonPikeDecoder(const char *s) { unsigned c, w = 0, t = 0; do { c = *s++ & 0xff; if (0200 <= c && c < 0300) { w = w << 6 | c & 077; } else { if (t) { printf("%04x\n", w); t = 0; } if (c < 0200) { printf("%04x\n", c); } else { w = ThomPikeByte(c); t = 1; } } } while (c); } That code generalizes to any 32-bit number. It's the full superset of intended behaviors including things like stream synchronization. It'll even decode numbers that were arbitrarily banned by the IETF e.g. \300\200. Most importantly, since it doesn't require a validation pass beforehand, does that mean it goes faster than the OP's code in praxis? D:

Dylan16807 6y ago
I strongly question "doesn't require a validation pass". 1. Your code drops naked continuation bytes entirely. 2. If a valid multibyte character is followed by extraneous continuation bytes it will not decode correctly. 3. Using the wrong number of continuation bytes is a giant mess and can give you arbitrary numbers in multiple ways. The second one especially is a behavior that's hard to defend.