Valid UTF-8

UTF-8 stores each character of a text as 1 to 4 bytes. Write valid_utf8(data) that takes a list of byte values (whole numbers from 0 to 255) and returns True if the whole list is valid UTF-8, and False otherwise.

In the bit patterns below, x marks a bit that carries part of the character's number (its code point). Every byte after the first one of a character must be a continuation byte of the form 10xxxxxx.

• 1 byte: 0xxxxxxx, for code points 0 to 0x7F;
• 2 bytes: 110xxxxx and 1 continuation byte, for code points 0x80 to 0x7FF;
• 3 bytes: 1110xxxx and 2 continuation bytes, for code points 0x800 to 0xFFFF, except 0xD800 to 0xDFFF;
• 4 bytes: 11110xxx and 3 continuation bytes, for code points 0x10000 to 0x10FFFF.

The code point is made by joining the x bits of all the character's bytes, first byte first. The data is valid when it splits completely into characters like these, each with a code point in the range allowed for its length. So the data is not valid if:

• a character starts with a continuation byte, or with a byte of the form 11111xxx;
• a character is cut short: one of its continuation bytes is missing, or the data ends in the middle of it;
• a code point is below the range for its length (it was written with more bytes than it needs, like code point 65 written with two bytes), lies between 0xD800 and 0xDFFF, or is above 0x10FFFF.

Examples

valid_utf8([72, 105])            # returns True
valid_utf8([226, 130, 172])      # returns True
valid_utf8([226, 130])           # returns False
valid_utf8([193, 129])           # returns False

The first list is the text Hi. The second is the euro sign: 11100010 10000010 10101100 joins to code point 0x20AC. The third is the same character cut short. The last one has the right shape, but its code point is 65 (the letter A), which must be written with one byte.

Constraints

• 0 <= len(data) <= 300,000
• 0 <= data[i] <= 255