9
\$\begingroup\$

UTF-8 is a relatively simple way to encode Unicode codepoints in a variable-width format such that it doesn't easily confuse code that isn't Unicode aware.

UTF-8 overview

  • Bytes in the range of 1-0x7F, inclusive, are normally valid
  • Bytes with the bit pattern 10XX XXXX are considered continuation bytes, with the six least significant bits being used to encode part of a codepoint. These must not appear unless they are expected by a preceding byte.
  • Bytes with the pattern 110X XXXX expect one continuation byte afterward
  • Bytes with the pattern 1110 XXXX expect two continuation bytes afterward
  • Bytes with the pattern 1111 0XXX expect three continuation bytes afterward
  • All other bytes are invalid and should not appear anywhere in a UTF-8 stream. 5, 6, and 7 byte clusters are possible in theory, but will not be allowed for the purposes of this challenge.

Overlong encodings

UTF-8 also requires that a codepoint should be represented with the minimum number of bytes. Any byte sequence that could be represented with fewer bytes is not valid. Modified UTF-8 adds one exception to this for null characters (U+0000), which should be represented as C0 80 (hex representation)), and instead disallows null bytes to appear anywhere in the stream. (This makes it compatible with null-terminated strings)

Challenge

You are to make a program that, when given a string of bytes, will determine if that string represents valid Modified UTF-8 and will return a truthy value if valid and a falsy value otherwise. Note that you must check for overlong encodings and null bytes (since this is Modified UTF-8). You do not need to decode the UTF-8 values.

Examples

41 42 43  ==> yes (all bytes are in the 0-0x7F range)
00 01 02  ==> no (there is a null byte in the stream)
80 7F 41  ==> no (there is a continuation byte without a starter byte)
D9 84 10  ==> yes (the correct number of continuation bytes follow a starter byte)
F0 81 82 41  ==> no (there are not enough continuation bytes after F0)
EF 8A A7 91  ==> no (too many continuation bytes)
E1 E1 01  ==> no (starter byte where a continuation byte is expected)
E0 80 87  ==> no (overlong encoding)
41 C0 80  ==> yes (null byte encoded with the only legal overlong encoding)
F8 42 43  ==> no (invalid byte 'F8')

Rules

  • Standard rules and loopholes apply
  • Input and output can be in any convenient format as long as all values in the unsigned byte range (0-255) can be read in.
    • You may need to use an array or file rather than a null-terminated string. You need to be able to read null bytes.
  • Shortest code wins!
  • Note that using builtins to decode the UTF-8 is not guaranteed to conform to the requirements given here. You may need to work around it and create special cases.

EDIT: added bonus for not using builtins that decode UTF-8

EDIT2: removed bonus since only the Rust answer qualified and it's awkward to define.

\$\endgroup\$
  • \$\begingroup\$ I've been waiting for this one. \$\endgroup\$ – Adám Jan 16 at 21:22
  • \$\begingroup\$ You may want to add a test case with an invalid byte in the range 0xF8-0xFF. \$\endgroup\$ – Arnauld Jan 16 at 21:26
  • 2
    \$\begingroup\$ It seems that surrogates (0xD800 - 0xDFFF) and codepoints beyond 0x10FFFF are allowed, contrary to the "modern" UTF-8 spec. I think this should be clarified, ideally with additional test cases. \$\endgroup\$ – nwellnhof Jan 17 at 8:55
  • \$\begingroup\$ more examples would be helpful \$\endgroup\$ – don bright Jan 22 at 20:31
  • \$\begingroup\$ "Bytes in the range of 0-0x7F, inclusive, are normally valid " is that supposed to be 1 to 0x7f? \$\endgroup\$ – don bright Jan 22 at 20:46
2
\$\begingroup\$

Elixir, 69 bytes

import String
&valid? replace replace(&1,<<0>>,"\xFF"),"\xC0\x80","0"

Try it online!

Makes use of built-in string validation function. Takes input as Elixir binary.

\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Unicode), 41 39 bytesSBCS

Anonymous tacit prefix function. Takes a Unicode string as argument where the characters' code points represent the input bytes.

{0::0⋄×⌊/'UTF-8'⎕UCS⍣2⎕UCS⍵}'À\x80'⎕R⎕A

Try it online!

'À\x80'⎕R⎕AReplace C0 80s with the uppercase Alphabet

{} apply the following anonymous function, where the argument is :

0:: if any error happens:

  0 return zero

 try:

  ⎕UCS⍵ convert the string to code points

  'UTF-8'⎕UCS⍣2 interpret as UTF-8 bytes and convert resulting text back to bytes

  ⌊/ lowest byte (zero if a null byte is present, positive if not, "infinity" if empty string)

  × sign (zero if null byte is present, one if not)

\$\endgroup\$
  • \$\begingroup\$ Wouldn't this return truthy for D9 C0 80 84 C0 80 10? \$\endgroup\$ – Neil Jan 17 at 0:46
  • \$\begingroup\$ @Neil It does indeed. Is that wrong because removing C0 80 makes unrelated bytes be adjacent in a way that's valid, though they are invalid when separate? Edit: Updated to fix that at no byte cost. \$\endgroup\$ – Adám Jan 17 at 1:12
  • \$\begingroup\$ some of the characters are coming up on my screen as just rectangles or boxes, is that normal? im in firefox on linux. APL is a very interesting language. \$\endgroup\$ – don bright Jan 22 at 21:40
  • \$\begingroup\$ @donbright In my experience, APL characters always render correctly, even if sometimes less than beautifully, so those boxes are probably just Quads of which there should be four in the main code. It should render like this. And yes, APL is amazing, and lot's of fun. You can easily and quickly learn it too — just come on over in the APL Orchard. \$\endgroup\$ – Adám Jan 22 at 22:18
  • \$\begingroup\$ yes they are quads. thanks. \$\endgroup\$ – don bright Jan 22 at 22:19
1
\$\begingroup\$

Python 2, 104 102 bytes

''.join(chr(int(c,16))for c in input().replace('00','-').replace('C0 80','0').split()).decode('utf-8')

Try it online!

Outputs via exit code

\$\endgroup\$
0
\$\begingroup\$

Rust - 191 bytes 313 bytes

Per comment below original did not work properly. New and improved version. No libraries are used, because The Mighty Rust Has No Need For You And Your Libraries. This code uses pattern matching with a state machine. By shamelessly ripping off the UTF8 spec, after finding it via reference and discussion by Jon Skeet, we can copy the spec almost character for character into a rust Match pattern match block. At the end, we add in Beefster's special Mutf8 requirement for C0 80 to be considered valid. Ungolfed:

/* http://www.unicode.org/versions/corrigendum1.html
 Code Points        1st Byte    2nd Byte    3rd Byte    4th Byte
U+0000..U+007F      00..7F           
U+0080..U+07FF      C2..DF      80..BF           
U+0800..U+0FFF      E0          A0..BF      80..BF       
U+1000..U+FFFF      E1..EF      80..BF      80..BF       
U+10000..U+3FFFF    F0          90..BF      80..BF      80..BF
U+40000..U+FFFFF    F1..F3      80..BF      80..BF      80..BF
U+100000..U+10FFFF  F4          80..8F      80..BF      80..BF
*/

let m=|v:&Vec<u8>|v.iter().fold(0, |s, b| match (s, b) {
        (0, 0x01..=0x7F) => 0,
        (0, 0xc2..=0xdf) => 1,
        (0, 0xe0) => 2,
        (0, 0xe1..=0xef) => 4,
        (0, 0xf0) => 5,
        (0, 0xf1..=0xf3) => 6,
        (0, 0xf4) => 7,
        (1, 0x80..=0xbf) => 0,
        (2, 0xa0..=0xbf) => 1,
        (4, 0x80..=0xbf) => 1,
        (5, 0x90..=0xbf) => 4,
        (6, 0x80..=0xbf) => 4,
        (7, 0x80..=0x8f) => 4,
        (0, 0xc0) => 8, // beefster mutf8 null
        (8, 0x80) => 0, // beefster mutf8 null
        _ => -1,
    })==0;

try it on the rust playground

\$\endgroup\$
  • \$\begingroup\$ Props for doing it manually, but I think your overlong check is incorrect. \$\endgroup\$ – Beefster Jan 23 at 17:51
  • \$\begingroup\$ Your challenge, dear sir, provokes me to imitation, and I conclude this letter by challenging you, in my turn, to fix upon a man who will expose your question more bluntly (bit.ly/2T8tXhO) \$\endgroup\$ – don bright Jan 24 at 1:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.