3 ms·
There is validating and "validating", what is this code doing? For example, valid utf-8 must always use the shortest possible sequence or it's invalid. Valid
by nabla9 9y ago
There is validating and "validating", what is this code doing?
For example, valid utf-8 must always use the shortest possible sequence or it's invalid. Validator must check against decoding invalid sequences.
example of invalid sequence:
0xF0 0x80 0x80 0x8A
- jwilk 9y agoThe test suite includes these as "bad" sequences: * \xc0\x9f (overlong U+001F) * \xed\xa0\x81 (surrogate)
- SloopJon 9y agoI was too lazy to look up what these sequences represented, but I did a quick test with the Euro symbol example from Wikipedia, and it did indeed reject the overlong sequence: #include <stdbool.h> #include <string.h> #include <stdio.h> #include "simdutf8check.h" int main(int argc, char *argv[]) { const char euro[] = "\xe2\x82\xac"; const char eurolong[] = "\xf0\x82\x82\xac"; bool valid = validate_utf8_fast(euro, sizeof euro); printf("validate_utf8_fast(euro): %d\n", valid); valid = validate_utf8_fast(eurolong, sizeof eurolong); printf("validate_utf8_fast(eurolong): %d\n", valid); return 0; }
- Someone 9y ago”For example, valid utf-8 must always use the shortest possible sequence or it's invalid.” nabla9 likely knows this, but for those wondering: utf8 can’t contain overlong encodings (https://en.m.wikipedia.org/wiki/UTF-8#Overlong_encodings https://en.m.wikipedia.org/wiki/UTF-8#Overlong_encodings), but need not use precomposed characters (https://en.m.wikipedia.org/wiki/Precomposed_character https://en.m.wikipedia.org/wiki/Precomposed_character) whenever possible (another way in which a shorter sequence is possible)
- rspeer 9y agoThis is built on UTF-8 described as a state machine. The state machine already rejects overlong sequences. There is no sense of "validator" in which an expression that accepts overlong sequences could be called a UTF-8 validator.
- kwillets 9y agoThere are actually a few different parts to the code, and they work somewhat independently. The first is to classify each byte by type, using the highest 4-5 bits. The types are: ASCII continuation initial byte of: 2 3 4-byte sequence Given these types, the multibyte sequences are checked for proper lengths, ie each length indicator has to be followed by that exact number of continuation bytes until the next non-continuation. We do this by putting the following byte count where each initial is found, zeroing the rest, and carrying counts right with shift-and-subtract, saturated to 0. This just creates a descending sequence after each initial, eg 4 -> 3,2,1, which should reach zero right at the next initial or "first" byte (ascii or multi). The vector of nonzero following bytes xored with the vector of first bytes should then be all 1's, ie there should be no gaps or overlaps. The next task is to check for overlongs. These are just bitfields in the first or second bytes which should be nonzero, and they can be checked at least two ways. One is masking and checking for any nonzero bits, based on a lookup table of masks. Another is comparison, based on the idea that any 1 bits in the bitfield of interest will make the byte larger than all 0's (the higher-order bits are fixed). Both of these methods assign checks on a per-length basis, using a lookup table from the highest 4 bits. Longer sequences also check the second byte in similar fashion. In the end we basically have bitmaps of each type, and we check that they don't intersect and that their union covers the range. The code is a bit complicated by carrying over the previous range so that sequences that span registers will still get checked.