UTF-8 bit by bit (2001) | Hacker News Reader

UTF-8 bit by bit (2001)

wiki.tcl-lang.org

76 pointsnetworked19 comments

Here's a potentially random question: Is UTF-8 essentially a fancy way of representing arbitrary precision BigInts where the character-to-integer mapping is specified by Unicode, and which coincides with ASCII encodings on a certain range of numbers?

UTF-8 is not arbitrary precision. There is a artificial limit at 2^20. And Unicode does not map theses to characters. Unicode maps these to so called "code points". These "code points" then are mapped to charaters ("glypheme clusters" in unicode speak) in a very complicated way. A sequence of code points can be different kinds of normal forms, for example.

> UTF-8 is not arbitrary precision. There is a artificial limit at 2^20.

Since that limit is artificial it can safely be ignored. UTF-8 was designed as a 32b encoding. I don't think it is arbitrary-precision either though, since it was also designed to be self-synchronising.

> glypheme

Grapheme. A grapheme is more or less a user-perceived character, a "grapheme cluster" is a group (cluster) of codepoints roughly corresponding to a grapheme.

> A sequence of code points can be different kinds of normal forms, for example.

That has limited relevance, since not all clusters exist in precomposed forms they have to be handled regardless of normalisation, there's just some redundancies.

UTF-8 is a "fancy" way of representing 32 bit integers in a self-synchronising byte format.

I can see an extension to 7 bytes (by making the leading byte 11111110 which I think would still be unambiguous) going up to 37 bits, but at 8 bytes you'd start getting collisions in the byte patterns and would lose the self-synchronising properties.

You could in theory extend the pattern up to 42 bits:

    0xxxxxxx
    110xxxxx 10xxxxxx
    1110xxxx 10xxxxxx 10xxxxxx
    11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
    111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
    1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
    11111110 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
    11111111 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx

True, not sure why I figured FF was not an acceptable LBP.

Possibly because I assumed you'd need a special continuation byte and all of them would be unavailable, but the existing continuation bytes work fine so that's just not correct. FF could even lead to special patterns of continuation bytes allowing for smuggling more data in there I guess.

> 32 bit integers

The original UTF-8 was at most 31 bits long (one bit in the leading byte, 6*5 = 30 bits in six subsequent bytes).

> you'd start getting collisions in the byte patterns and would lose the self-synchronising properties

I'm not sure why. The main requirement for self-synchronization in this case is that the leading byte doesn't appear anywhere else, which would be the case for the leading byte FF. It would require substantial modifications to go beyond 7 bytes (say, it would have alternative means to denote the length of following data bytes) but it is surely possible.

There is a proposal for infinitely long UTF-8 extensions: http://ucsx.org/%E2%88%9E8

It only goes to 31 bits, otherwise you are correct.

Although the term "character" is ambiguous so Unicode use more specific terms. An encoded integer represent a "code point" which usually corresponds to a character, but in some cases characters are represented by multiple code points. For example "â" might be represented by the code point for "^" following the code point for "a". This in turn opens a whole can of worms since the same character can be represented as code points in multiple ways.

The encoding scheme goes to 31 bits, but UTF-8 nowadays goes to ≈20 bits. https://en.wikipedia.org/wiki/UTF-8#Invalid_code_points:

“Since RFC 3629 (November 2003), the high and low surrogate halves used by UTF-16 (U+D800 through U+DFFF) and code points not encodable by UTF-16 (those after U+10FFFF) are not legal Unicode values, and their UTF-8 encoding must be treated as an invalid byte sequence.”

Minor quibble, UTF-8 is used to represent Unicode code points, not integers. People like to map the bit patterns to integers in various bases for stuff like ordering but it is inherently a different sort of thing.

This leaves a question: what of 0xFF? It can't be a "trailer", and has no trailing zero required of a "locomotive". No worries, it's simply forbidden.

If you are processing UTF-8 and can't handle "forbidden" (for example you are in a language with no exception handling, or this is code which has a must-never-fail constraint) you should treat whatever forbidden sequence you've encountered as U+FFFD ("Replacement Character") and continue. The replacement character is commonly visually represented as a black diamond with a white question mark inside it, so humans will recognise that this means something went wrong, while a machine can't confuse U+FFFD with any letter, digit, white space, or other commonly used element it may be treating specially so this prevents many potential attacks on a parser.

The article is unfortunate because it's actually handling a common non-UTF-8 encoding in which U+0000 is encoded differently so as to keep C-style null-terminated string semantics while allowing the NUL character. You should probably avoid the necessity for such semantics.

This special encoding of the null character is Modified UTF-8 and is used by various Java and JVM APIs and in Java class files.

https://en.wikipedia.org/wiki/UTF-8#Modified_UTF-8

The bytes FF FE or FE FF in the beginning of file are often used to indicate whole file is UTF-16 with "byte order mark", not UTF-8. I don't know of any other practical use, it's best to treat it as invalid.

I found this analogy of trains and railcars good but I'm lost on this bit

(110)00000 (10)000000 => C0 80

EDIT: OK I asssume he's referring to C and octal here and not a hexadecimal and decimal numbers?

Binary 11000000 10000000 = hexadecimal C0 80.

Thank you, got it now!

I think he might have been clearer if he'd said

"To represent a NUL byte without any physical NUL bytes, we don't discard the indicators and instead treat it like a character above ASCII, which must be a minimum two bytes long 11000000 10000000 => hexadecimal C0 80."

One small fun fact: utf8 uses big-endian.

Reply on news.ycombinator.com