News for hackers. Stuff that matters.
Re:Database character sets and collations explained – why ut... by Dylan16807 on Thursday January 06, 2022 @04:37AM (#29821350)
To give a slightly more complete answer as to why, utf-8 was designed to be both backwards compatible with ASCII and self-synchronizing.

So you can't use half the values of a byte when encoding code points outside of ASCII, and the remaining 128 values need to be split between starting bytes and continuation bytes. At best you're going to fit about 6 bits into each byte, and unicode spans the equivalent of just over 20 bits, so you need 4 bytes max.

utf-8 opts to keep encoding very simple, and in 2-4 bytes it can store 11, 16, and 21 bits respectively.

If you discarded ASCII compatibility, you could create a 1-3 byte self-synchronizing unicode encoding. But at that point maybe you should be compressing your text instead.

Or you could weaken the compatibility and create "utf-1 but better" to fit into 3 bytes.

Re:Database character sets and collations explained – why ut... by chrismorgan on Thursday January 06, 2022 @06:12AM (#29822142)
> Actually it does seem feasible to make an encoding that's backwards compatible with all printable ASCII characters, and uses 3 bytes for all other code points.

Sorry, you can’t squeeze Unicode in that way, even unsynchronised: you fall just over 2½ bits short. No, reserving the 95 printable ASCII characters scuttles your hopes, meaning you get less than 1½ bits of that byte to use for the rest of Unicode, when you needed a touch over 4 bits.

To represent all the rest: Unicode scalar values minus printable ASCII is U+0000–U+10FFFF minus U+D800–U+DFFF minus U+0020–U+007E: 1,111,969 possibilities, log₂(1111969) ≈ 20.085 bits of entropy. (Removing the 2048 surrogates and 95 printable ASCII characters barely made a dent, under 0.003 bits, but I had to remove it for informational correctness.)

95 printable ASCII characters, log₂(95) ≈ 6.57 bits. Subtract that reservation from the three bytes available and you’ve got about 17.43 bits left for the rest of Unicode, but you needed over 20.

[Edit: I observe you’ve removed what I was quoting before I posted my comment. Still fun mathematics.]

> If you discarded ASCII compatibility, you could create a 1-3 byte self-synchronizing unicode encoding.

Not quite. If you discarded ASCII compatibility, then you’d have almost four bits to spare, which is enough for a self-synchronising fixed-width 3-byte encoding (reserving the first bit of each byte to signal if it’s a start byte) or for an unsynchronised variable-width encoding of some kind; but to make it even 2-or-3 or 1-or-3 (rather than 1–3) bytes wide variable-width, you’d need four bits (3 + log₂ 2) for self-synchronisation, and you’re about 0.085 bits short. (1–3 bytes variable-width would require 3 + log₂ 3 ≈ 4.58 bits.)

—⁂—

I just got nerd-sniped, didn’t I?

Re:Database character sets and collations explained – why ut... by Dylan16807 on Thursday January 06, 2022 @11:06PM (#29834695)
> Sorry, you can’t squeeze Unicode in that way, even unsynchronised: you fall just over 2½ bits short. No, reserving the 95 printable ASCII characters scuttles your hopes, meaning you get less than 1½ bits of that byte to use for the rest of Unicode, when you needed a touch over 4 bits.

So it depends on exactly what we mean by compatible, and that's why I removed it.

But in particular, the encoding I had in mind when I wrote that was one that allows most ASCII characters as the middle byte of a triplet. That way whether you truncate from beginning or end you'll never have a rogue byte successfully decode.

So something like: Lead bytes from C0-FF, middle bytes from 00-BF, final bytes from 00-1F or 7F-BF.

If you also exclude null, tab, newline, and line feed, that gives you 64 x 188 x 93, which is just enough for every code point.

But arguably that's not compatible enough because you couldn't search for single ASCII characters with a dumb byte-wise algorithm.

> Not quite. If you discarded ASCII compatibility, then you’d have almost four bits to spare, which is enough for a self-synchronising fixed-width 3-byte encoding (reserving the first bit of each byte to signal if it’s a start byte) or for an unsynchronised variable-width encoding of some kind; but to make it even 2-or-3 or 1-or-3 (rather than 1–3) bytes wide variable-width, you’d need four bits (3 + log₂ 2) for self-synchronisation, and you’re about 0.085 bits short. (1–3 bytes variable-width would require 3 + log₂ 3 ≈ 4.58 bits.)

I don't know where you got that equation but it's not the right one for the situation.

Here's a really simple encoding just to disprove it: Leading bytes encode the plane (17 options) plus two more bits into decimal values 0 through 67. Continuation bytes encode 7 bits into decimal values 128 through 255. 17 planes + 2 bits + 7 bits + 7 bits, perfect fit. The remaining values, 68-127, can be used for single byte (and two byte) encodings.

But also the definition I was using for self-synchronizing doesn't seem to match the one on wikipedia. My intent was a code where you can guarantee sync after a specific small number of bytes (unlike UTF-1). In particular, if you let standalone bytes and continuation bytes overlap each other, you can still guarantee sync within 3 bytes. This gives you lots of space to play with, and you could make a very useful encoding. You could have >150 single byte codepoints and thousands of double byte codepoints and fit everything else into three bytes.

Re:Database character sets and collations explained – why ut... by chrismorgan on Friday January 07, 2022 @01:37AM (#29835794)
My (3 + log₂ 2) came from reckoning that you needed one whole bit as a signal in each byte (3), and that the byte-width thing (log₂ 2) was extra to that. As you correctly point out, this was incorrect: the first byte doesn’t need one full bit of entropy to signal that it’s the first byte.
Re:Database character sets and collations explained – why ut... by kingcharles on Thursday January 06, 2022 @01:18PM (#29827475)
I had to Google ⁂ as I've never seen that character before. Fascinating! It makes a nice Christmas snowflake stand-in.

I wonder what HN's rules are with sanitizing Unicode, as they won't allow emojis?

Re:Database character sets and collations explained – why ut... by chrismorgan on Thursday January 06, 2022 @08:32PM (#29833510)
I use “—⁂—” as my horizontal rule in plain text, via my Compose key (Compose+h+r).

HN removes things that are officially marked as emoji, normalises whitespace to space (which annoys me because I sometimes want to type things like narrow no-break space in equations which it makes wider and loses the no-breakyness of), and that’s all I’ve noticed. Control characters probably get some treatment or other too.

Re:Database character sets and collations explained – why ut... by erik_seaberg on Thursday January 06, 2022 @06:47AM (#29822416)
If 21 bits seems like an odd place to stop, it’s because the Unicode consortium said they wouldn’t allocate any codepoints beyond U+10FFFF (the end of plane 16), because that’s as far as UTF-16 could go using a four-byte surrogate pair (10+10 bits, offset by U+10000).
Re:Database character sets and collations explained – why ut... by Dylan16807 on Thursday January 06, 2022 @11:25PM (#29834822)
Not that UTF-8 really stops at 21. As originally formulated it has 5 and 6 byte encodings for 26 and 31 bits, but an entire unsigned int of code points was later decided to be unnecessary, and those encodings were marked as invalid.
Re:Database character sets and collations explained – why ut... by Dylan16807 on Saturday January 08, 2022 @03:01AM (#29849668)
* Positive signed int, not unsigned, oops.