Home About Articles Posts zoomlogo's site

The UTF-8 encoding.

UTF-8 is the most widely used encoding in the world. I spent the last year only working with C and assumed ASCII for whatever strings I needed to process. I didn't bother learning UTF-8, until recently.

Some history about UTF-8.

As the "legend" goes, UTF-8 was formulated on a placemat by Ken Thompson while at dinner with Rob Pike. They soon utilized this everywhere in their latest research project, Plan 9 from Bell Labs. Plan 9 didn't stick with the world, but we got stuck with UTF-8 at least (and some other ideas from Plan 9).

One of the biggest strengths of UTF-8 is that it is backwards compatible with ASCII. Any ASCII document predating UTF-8 is automatically UTF-8 compatible. The other neat thing about UTF-8 is how the format itself is structured.

Unicode code points.

Let me first tell you about the Unicode standard. UTF stands for Unicode Transformation Format. The Unicode standard is maintained by the Unicode Consortium which aims to standardize how different glyphs from different languages around the world can be represented as a stream of bytes.

For this, each glyph/character is assigned a unique number in this standard called its code point. The code point is represented as a hexadecimal number of 4 to 6 hexadecimal digits preceded by a U+. For example, the letter A is represented by the code point U+0041 and the emoji ✅ by U+2705.

The UTF-8 standard then tells us how to convert these code points into byte streams.

The basics of UTF-8.

The UTF-8 encoding is a variable length encoding. This means that a valid character can consist of a single byte, or two bytes, or three or (the maximum) four bytes. The neat thing about the encoding is that given any byte at any offset from a UTF-8 text stream, we can determine if that byte is a:

  1. Start byte, which starts the sequence to denote a code point. The start bytes also contain the information of how many continuation bytes follow them.
  2. Continuation byte, which follow the start byte.

Let us look into each case.

1 byte.

Code points in the range U+0000 to U+007F are all represented as a single UTF-8 byte. We can write a code point as a binary number in that range generically as 0xxxxxxx (skipping the first two zeros).

And that 0xxxxxxx, is the byte sequence in UTF-8. The characters in the range U+0000 to U+007F are precisely the same as that of ASCII. And now because their byte representations match, UTF-8 is backwards compatible.

2 bytes.

Code points in the range U+0080 to U+07FF are represented using two bytes. Again writing a code point as a binary number in that range, we get 0xxxyyyyzzzz (skipping the first zero). You can see that in this range, the payload is exactly 11 bits, which is split like:

0xxxyyyyzzzz yyyy 0xxx zzzz 110xxxyy 10yyzzzz

As you can see, the start byte 110xxxyy starts with two ones, exactly the number of bytes required to represent the entire character. Then the continuation byte 10yyzzzz always starts with 10. The rest of the bits in both bytes are just filled with the bits from the code point.

3 bytes.

Code points in the range U+0800 to U+FFFF are represented using three bytes. In binary, wwwwxxxxyyyyzzzz. Here, the payload is 16 bits, which is split into groups of .

wwwwxxxxyyyyzzzz xxxx wwww yyyy zzzz 1110wwww 10xxxxyy 10yyzzzz

4 bytes.

Code points in the range U+010000 to U+10FFFF are represented using 4 bytes. In binary, we have our payload as 21 bits: 000uvvvvwwwwxxxxyyyyzzzz. This is split into groups of .

000uvvvvwwwwxxxxyyyyzzzz wwww vvvv 000u xxxx yyyy zzzz 11110uvv 10vvwwww 10xxxxyy 10yyzzzz

Writing a code point to UTF-8 converter in C.

Before we continue with this section, please note that not every byte sequence is valid UTF-8. With that out of the way, the simplest program we can write now is to convert a code point to a UTF-8 character.

This is actually very, very easy, just some conditionals and bitwise operations:

/* assuming buf is big enough */
int
utf8_bytes(unsigned int c, unsigned char *buf)
{
        if (c < 0x80) {
                buf[0] = c;
                return 1;
        }
        if (c < 0x800) {
                buf[0] = (unsigned char) (0xC0 + ((c >> 6) & 0x1F));
                buf[1] = (unsigned char) (0x80 + (c & 0x3F));
                return 2;
        }
        if (c < 0x010000) {
                buf[0] = (unsigned char) (0xE0 + ((c >> 12) & 0xF));
                buf[1] = (unsigned char) (0x80 + ((c >> 6) & 0x3F));
                buf[2] = (unsigned char) (0x80 + (c & 0x3F));
                return 3;
        }
        if (c < 0x110000) {
                buf[0] = (unsigned char) (0xF0 + ((c >> 18) & 0x7));
                buf[1] = (unsigned char) (0x80 + ((c >> 12) & 0x3F));
                buf[2] = (unsigned char) (0x80 + ((c >> 6) & 0x3F));
                buf[3] = (unsigned char) (0x80 + (c & 0x3F));
                return 4;
        }
        return -1;
}

Paradigm shift.

I was looking at the example fractals.k program (found here at the online interpreter for ngn/k) and it has a code point to UTF-8 converter written in ngn/k (which also works in the fork growler/k):

u8:{`c$(0x00c0e0f0[c],c#128)+(0,64+&c:1+128 2048 65536'x)\x}

That is the entire function which we wrote in C just now! How does it work?

Brief introduction to k.

k is actually a series of programming languages made by Arthur Whitney, which were inspired by APL. Each revision of k is incompatible with the previous revision. The version I'm using is ngn/k, which is a free open source k6 implementation. A list of implementations of various versions can be found here.

Like APL (and J), k is classified as an array language. This means arrays are first-class citizens. Operations fundamentally work on arrays. An example is:

4 3 2 1+1 2 3 4

Here, 4 3 2 1 is an array and 1 2 3 4 is another array. Adding them together using + does not concatenate these arrays like they might do when using Python lists, but instead each element is added to its corresponding element in the other array. Hence the new array actually is:

5 5 5 5

This is called vectorization.

k actually has a different array model compared to APL. APL treats arrays as true tensors. There is a concept of rank, and many operations work on a certain rank. Rank based operations allows us to perform operations on specific subarrays of a certain rank.

In k's model, arrays actually behave like nested lists found in say, Python. There isn't a concept of rank, but rather how nested the lists are (i.e., depth).

k, like APL is evaluated RTL. This means an expression like:

3*4+1

evaluates to 15, not 13. Also, the same symbol can perform different operations, depending on how many arguments are supplied to it.

=5

Generates a identity matrix, and:

5=5

checks for equality.

Decoding the snippet.

Let us look at how this snippet actually works.

u8:{`c$(0x00c0e0f0[c],c#128)+(0,64+&c:1+128 2048 65536'x)\x}

The {} encloses a function, which accepts a single argument x. The : assigns the function to a variable called u8. Following the RTL evaluation order, the first thing that happens is:

(0,64+&c:1+128 2048 65536'x)\x

The expression inside the parenthesis is evaluated first:

0,64+&c:1+128 2048 65536'x

Already we see our first few primitives in action. The ' primitive, when supplied with an array on the left and a value on the right performs a binary search. Some examples:

 1 10 100'0
-1
 1 10 100'5
0
 1 10 100'10
1
 1 10 100'50
1
 1 10 100'500
2

Look at the exact numbers in the left hand side of ' in the u8 function:

128 2048 65536

Does that look familiar? Convert them to hexadecimal numbers, you get 0x80 0x800 0x010000, which is exactly the bounds we checked for in the C code above! Since a zero based index is returned from this binary search, we add 1 to it and store the result in the variable c. Note that the binary search returns -1 when x < 128.

c:1+128 2048 65536'x

This is exactly the number of continuation bytes we need to represent the code point x! Next:

&c

Returns a vector of c zeros. We add 64 (64+) to each element in that array, giving us an array of c elements, each element being 64. We prepend a 0 to that array (0,).

Let us take an example, let us say our code point is U+2705, in decimal this would be 9989. Let us see the result for each step.

 x:9989                /assign x 9989
 :r:128 2048 65536'x   /binary search  (r is a temporary variable)
1
 :c:1+r                /add one and assign to c
2
 :r:&c                 /array of c zeros
0 0
 :r:64+r               /add 64 to each
64 64
 :r:0,r                /prepend a zero
0 64 64

Now we have this array 0 64 64 on the left of the operator \ and x on the right of that operator. In k6, x\y performs base decomposition. For our case: 0 64 64\x peels off two 6 bit chunks in the last position and leaves the remainder in the first position. For our example:

 x:9989
 0 64 64\x
2 28 5
 /in general
 2\5           /convert to base 2
1 0 1
 0 60 60\2300  /convert 2300 seconds to hours, minutes, seconds
0 38 20

The 6 bit chunks are exactly the amount of bits that can be placed in a continuation byte. All we need to do now is to set the correct bits for the continuation bytes and the start byte. This is handled by the following code:

`c$(0x00c0e0f0[c],c#128)+r

Let us see step by step what happens, for our example:

 x:9989
 c:2
 r:2 28 5       /our converted chunk
 c#128          /array of `c' elements, each being 128
128 128
 0x00c0e0f0[c]  /index into the start byte code using `c'
                /bytes are indexed like so:
                / 0x00c0e0f0[0]
                /0x00
                / 0x00c0e0f0[1]
                /0xc0
                / 0x00c0e0f0[2]
                /0xe0
                / 0x00c0e0f0[3]
                /0xf0
0xe0
 :m:0x00c0e0f0[c],c#128   /create the mask for the start byte and the
                          /continuation byte bits
(0xe0
 128
 128)
 `c$m+r         /add the bits to `OR' them and convert to
                /a character.  conversion is done using `c$
0xe29c85
 `0:0xe29c85    /print to stdout
✅

Now we have achieved the same thing that the C function did. But, here is the power of k, I can pass u8 a vector of code points instead of a single code point by just performing a map:

 u8:{`c$(0x00c0e0f0[c],c#128)+(0,64+&c:1+128 2048 65536'x)\x}
 u8'1022 1044 1088
("Ͼ"
 "Д"
 "р")

Contrasting with C.

In C, we wrote a few if statements to determine the length of the byte sequence. Then we had to use some bitshifts and some bitwise operators to mask the bits correctly.

In k, we went a different route. We first performed a search (which replaces the if statements) to an index. Then we did some simple operations to transform the data and decode it using \ and finally apply the headers using addition.

Understanding and trying to use an array language changes how you look at data processing. It forces you to separate the data and the structure. I wanted to introduce k here because I thought that snippet was particularly genius and clearly shows how k differs from C.