15 ms·
UTF-8 – "The most elegant hack"
- purpleturtle 13y agoThis is a Computerphile video. You can find the rest here: http://www.youtube.com/user/Computerphile/videos http://www.youtube.com/user/Computerphile/videos Really fascinating interviews with luminaries.
- GyrosOfWar 13y agoBrady Haran's videos are in general very good. All of his videos are in this style, concentrated on a single topic and in general shorter than ten minutes. I especially like the SixtySymbols channel (Physics and Astronomy). He seems to have a talent for asking the right questions and/or finding the right people to answer his questions.
- omn1 13y agoThis always reminds me of the Microsoft long filename support for Windows NT. They basically use the unused bits of the old DOS 8.3 file entry (8 characters for the filename, 3 characters for the extension) to signal a long file name. Then they allocate enough space to store the file name depending on its length. The genius part is, that older systems only see the shorter filenames and keep on working. The specification of the format is at [1], although I would love to see a nice drawing of the hack. [1]: http://www.cocoadev.com/index.pl?MSDOSFileSystem http://www.cocoadev.com/index.pl?MSDOSFileSystem
- justin66 13y agoYour URL is broken but it sure sounds like you're describing the FAT32 long filename hack which appeared in Windows 95. That has nothing to do with NTFS.
- jychang 13y agoVFAT [1] existed in WinNT 3.5, which was released in 1994. [1] http://en.wikipedia.org/wiki/File_Allocation_Table#Long_file_names http://en.wikipedia.org/wiki/File_Allocation_Table#Long_file...
- elwell 13y agoDescribing a hack that uses a varying number of bytes for different characters as elegant makes me cringe. However, I have no better proposition.
- meowface 13y agoIt's about as good as you're going to get with character encoding. Unicode + UTF-8 will likely be the standard for representation and encoding for decades to come.
- kaoD 13y agoI see you love wasting resources.
- Groxx 13y agoUTF-32?
- nly 13y agoIt's not really a 'hack', but making it backward compatible with ASCII while maintaining a lot of other desirable properties is quite elegant. A lot of people complain about not being able to easily or programmatically manipulate UTF-8 strings on a character-by-character basis, like it's a typical programmers daily business to go messing with natural language, but I've never seen the great loss.
- crystaln 13y agoSeems perfectly sensible to me. Why should characters be of fixed size?
- lukasLansky 13y agoGetting i-th char in O(1) is a nice thing to have.
- mikeash 13y agoWhen is that a nice thing to have? It's almost never a useful operation to perform when working with Unicode strings.
- cma 13y agoI thought 7 bits were used in ASCII because terminals needed the 8th as a parity bit, not because machines dealt much in 7bit entities.
- cdcarter 13y agoPer the wiki page on ASCII: "The committee considered an eight-bit code, since eight bits (octets) would allow two four-bit patterns to efficiently encode two digits with binary coded decimal. However, it would require all data transmission to send eight bits when seven could suffice. The committee voted to use a seven-bit code to minimize costs associated with data transmission. Since perforated tape at the time could record eight bits in one position, it also allowed for a parity bit for error checking if desired.[17] Eight-bit machines (with octets as the native data type) that did not use parity checking typically set the eighth bit to 0.[18]"
- brazzy 13y agoNo. 5 and 6 bit codes existed. And according to Wikipedia (which cites a book "Coded Character Sets, History and Development") making ASCII an 8 bit encoding was considered (not to encode more characters, but to embed BCD data efficiently) but not done because reducing the required bandwith for all text by 12.5% represented a really significant cost reduction at that time.
- Patrick_Devine 13y agoThat is definitely true for early terminals, however the parity bit got tossed after things got less lossy. There was an 8 bit ASCII definition called "Extended ASCII" which was (is?) used for things like Curses which describes a lot of characters which have been remapped in UTF-8.
- deleted 13y ago[deleted]
- nilsbunger 13y agoOne really cool property of UTF-8 I never realized before is that a decoder can easily align to the start of a code word: every byte that has '10' in bits7,6 is not the beginning of a code. That's really useful if you want to randomly seek in a text without decoding everything in between. Between that and backwards compatibility with ASCII, I'd say it's a pretty neat hack.
- eridius 13y agoThis was actually one of the design goals of UTF-8. A decoder should be able to pick up a stream at any point and not lose a single valid codepoint.
- kazagistar 13y agoThis assumes you know the byte alignments. What if all you have is a stream of zeros and ones?
- oakwhiz 13y agoThat's the physical and link layer's fault for not possessing alignment information. You shouldn't have a bit stream, you should already have a byte stream, otherwise you are dealing with data forensics. The physical part of disks and networks usually have things like preambles, correlators, phase-locked loops, Gray codes, and self-clocking signals which can be used to deduce bit and byte boundaries, which is why in software, we almost always deal with information which we already know is correctly aligned.
- ars 13y agoThere's no way to align a bit stream containing exclusively 8 bits per byte. (Whatever code you choose for the alignment mark could also be a valid code since there are no extras.) You need to add extra bits so you can find the alignment, and once you do that you have the answer to your question.
- wgd 13y ago
- mojuba 13y agoWe should be grateful to UTF-8 for saving us from fixed multibyte Internet (so persistently pushed by MS, IBM and others), which would have made little sense in this predominantly 8-bit world. I remember someone saying at the time: the future is 16-bit modems and floppy disks anyway, so why not switch to Unicode now? Somehow that sounded absurd to me. Anyway, 20 years later, hardware is still mostly 8-bit, and basically nobody cares about Unicode apart from font designers and the Unicode Consortium. (On a side note, UTF-8 as a hack is a distant relative to Huffman encoding, itself a beautiful thing.)
- Stratoscope 13y ago"16 bits should be enough for anybody." --Anonymous The funny thing is that 16 bits wasn't enough. We thought it would be, back then. Just use 16 bits for each character and we can return to the joy and simplicity of a fixed width encoding. That didn't work out. UCS-2 was a fixed width 16-bit encoding, but it it had to be extended into the variable width UTF-16 to get more code points. You get the bloat of 16-bit data, incompatibility with ASCII, and variable width characters too. You have to go all the way to UTF-32 to get back to a fixed width encoding. So UTF-8 really was a smart move. Bite the bullet on the variable width, but make it so you can always find the beginning of the next character even if you start in the middle of one, and make it backward compatible with ASCII too. Genius. https://en.wikipedia.org/wiki/UTF-8 https://en.wikipedia.org/wiki/UTF-8 https://en.wikipedia.org/wiki/UTF-16 https://en.wikipedia.org/wiki/UTF-16 https://en.wikipedia.org/wiki/UTF-32 https://en.wikipedia.org/wiki/UTF-32
- sopooneo 13y agoPlease correct me if I'm wrong, but you don't really get fixed width in anyway do you? Because unicode itself is not fixed width. There are situations where one character on the screen is represented by two consecutive unicode code points.
- plorkyeran 13y agoOr a lot more than two, or even multiple characters for a single code point. UTF-32 appears to simplify things a lot, but in practice O(1) indexing of code points and simple iteration over code points is not actually all that useful, because code points are not characters.
- bbq 13y agoI wonder how computers would process text if societies with more complex alphabets had been at the foundation of the industry instead of English-speaking societies. What if Intel, Microsoft, IBM, and Apple were all Japanese companies and grew in a global market where English were not dominant? A big if, sure. Certainly, there must be glimpses at this in history of computing.
- stevewillows 13y agoThe video mentioned that Japan developed five different encodings that couldn't talk to each other. So in a sense, regardless of who started it, we would have ended up at something similar to UTF-8.
- contingencies 13y agoMainland China and Taiwan did something similar. I actually went to one of the newly-post-Unicode meets of Academica Sinica in Taipei where hardcore ancient Chinese academics and computational linguists were discussing unsolved conversion issues for some of those creatures.
- stevewillows 13y agoHow often does UTF-8 update to account for these issues?
- plorkyeran 13y agoUTF-8 has only been updated once (to remove 5 and 6 byte sequences, to limit it to the same range of values that UTF-16 can express). New versions of Unicode are standardized every year or two.
- contingencies 13y agoI think basically people who need to communicate beyond a certain age tend to avoid Unicode and just use images, and CJK Unicode is essentially fixed, even if still changing slowly now. More info here: http://www.unicode.org/reports/tr38/ http://www.unicode.org/reports/tr38/ My overall impression was that super ancient characters (of which there are tens of thousands more, probably with many academic arguments as to their individual distinctions or similarities) have been left out of Unicode proper and are under some documentation/standardization effort by a separate group as a 'special use region' mapping within Unicode for their own use by agreement. I can't find their site, though I could swear I had it a few years back. Initially, "Han unification" was an effort by the authors of Unicode and the Universal Character Set to map multiple character sets of the so-called CJK languages (Chinese/Japanese/Korean) into a single set of unified characters and was completed for the purposes of Unicode in 1991 (Unicode 1.0). Unfortunately, not only did they try to get modern scholars to agree on a normalized set of characters, but they also wanted them to agree of semantic equivalence (and a subset of pronunciations!)... in all cases... across all time: obviously not a good way to please hardcore academics. (It should be noted that Vietnamese also used Chinese, that in ancient history (even ~3000+ years ago) numerous non-Chinese ideographic/logographic/alphabetic scripts existed in the south-western Chinese borderland, and that in modern Chinese, certain surviving characters today seen as 'Cantonese' (from southern Chinese coast to east of Vietnam) are a surviving relic of this arguably greater and prodominantly Southern Chinese culture of ideogrammatic innovation). Some of the scripts still survive archaeologically, others survive in literary reference, and some (though primarily alphabetic, save for the Naxi Dongba script, an understanding of which is critically endangered to lost now despite government efforts at preservation) are still alive today... often with government reforms or some 19th century debris of Jesuit or other religious meddling.
- symisc_devel 13y agoNote that the UTF-8 encoding mechanism has inspired the variable length integers encoding (http://sqlite.org/src4/doc/trunk/www/varint.wiki http://sqlite.org/src4/doc/trunk/www/varint.wiki) introduced by the SQLite author (DRH) which I hope will be popular among programmers.
- nly 13y agoUnfortunately many variable length integer encodings aren't well thought out. The integer encoding used in Protocol Buffers for instance allows for multiple valid encodings of any particular integer (there's no one true canonical form)... which can make the format difficult for use with things like hashing and digital signatures
- masklinn 13y agoFWIW UTF-8 allows multiple encodings of any particular integers. Decoders should reject non-minimal encodings (they are a security risk, as it becomes possible to smuggle ASCII payload in a non-ASCII form which blindsides some security systems) but don't always do so. And of course if you don't decode UTF-8 data at any point and don't validate it either, you're still fucked.
- smagch 13y agoYou may also want to see UTF-8 Everywhere manifesto. https://news.ycombinator.com/item?id=3906253 https://news.ycombinator.com/item?id=3906253
- ppierald 13y agoUTF-8 wins for the internet because most of the payload of an HTTP request/response is 7-bit ascii characters, so it is the most efficient even in languages where UTF-16 may be more efficient because of the complexity of their character set.
- jcampbell1 13y agoAs a self-taught newbie programmer, one of my early question was, "How do letters get drawn on the screen?" My limited understanding is that it works like: bits (0's and 1's) -> encoding (e.g. UTF-8) -> glyphs (e.g. Unicode) -> Some insanely complicated black box. This black box knows how to do all sorts of things like kerning, combining cháracters, bizarre punctuation，and other magic. I understand UTF-8 and Unicode, but I have no idea how all the other magic works. Why is AV nicely kerned, and 我. nicely spaced? Apparenty this is a really hard problem because my trusty old code editor Textmate didn't get it right. Unicode to screen is a terribly hard problem.
- aaronblohowiak 13y agoindividual glyphs: http://www.smashingmagazine.com/2012/04/24/a-closer-look-at-font-rendering/ http://www.smashingmagazine.com/2012/04/24/a-closer-look-at-... kerning: http://en.wikipedia.org/wiki/Kerning#Digital_typography http://en.wikipedia.org/wiki/Kerning#Digital_typography some stuff is embedded in the font, other things the OS will do on a "best guess" basis -- which is why things look radically different between operating systems and even between different apps on the same OS if they use their own font rendering. Check out a very high-quality open source font rendering engine: https://developer.gnome.org/pango/unstable/ https://developer.gnome.org/pango/unstable/
- gonnakillme 13y agoOne way to think about text encoding is that it provides a nice way to represent indexes into a big array of glyphs: "unicode". Fonts map (some) of these indexes to graphic representations and provide "font hinting" -- clues as to how different letters should be rendered at different sizes -- and kerning information. Usually your desktop environment is the thing that handles all of this, providing widgets for other programs to combine to create GUIs. I can't find it right now, but you can probably find e.g. GNOME/GTK's implementation. (Re: Textmate: code is typically rendered in monospace font -- where every glyph has the same size -- so that it has the same alignment in every font with every renderer.)
- iv_08 13y ago
- chris_wot 13y agoI once wrote a potted history to the precursors of Unicode, starting from the telegraph codes: http://randomtechnicalstuff.blogspot.com.au/2009/05/unicode-and-oracle.html http://randomtechnicalstuff.blogspot.com.au/2009/05/unicode-...
- derleth 13y agoTom Jennings did something similar which only goes up through ASCII: http://www.wps.com/J/codes/ http://www.wps.com/J/codes/ You might also know Tom Jennings from having created Fidonet and having written the BIOS which became the basis for Phoenix Technologies BIOS. http://en.wikipedia.org/wiki/Tom_Jennings http://en.wikipedia.org/wiki/Tom_Jennings
- chris_wot 13y agoThat's awesome! Thanks for sharing this, it's really detailed. I got in a mention of the Gauss-Weber Telegraph Alphabet though :-) Everything else he's far more detailed!
- contingencies 13y agoNice article. Reading through the linked Wikipedia page[1] on ¤ (the international currency symbol), I was amazed at this part of history on symbolic innovations for great socialist profit!: In some versions of BASIC (notably in Soviet versions and ABC BASIC), the currency sign was used for string variables instead of the dollar sign. It was located on the keyboard and the character set table at the same position in many national keyboards (like Scandinavian) and eq versions of 7-bit ISO/IEC 646 ASCII, as the dollar sign is in US-ASCII. PS. This made me think of ₪, the sign for Israeli New Shekel. I wonder what percentage of currency symbols are completely symmetrical, and whether that derives from some kind of innate psychological quality that we associate with symmetry? IIRC, symmetry is oft-linked to beauty in the subconscious. (Of course, centrally issued fractional-reserve currencies nationally systematize usury, an activity universally shunned by all the world's monotheistic traditions, including Judaism: There are three Biblical passages which forbid the taking of interest in the case of "brothers," but which permit, or seemingly enjoin, it when the borrower is a Gentile [...] Lending on usury or increase is classed by Ezekiel [...] among the worst of sins. [...] abominations [...] be afraid of thy God [...] "...surely suffer death; his blood is upon him"; hence the lender on interest is compared to the shedder of blood. ... more @ http://www.jewishencyclopedia.com/articles/14615-usury http://www.jewishencyclopedia.com/articles/14615-usury) [1] https://en.wikipedia.org/wiki/%C2%A4 https://en.wikipedia.org/wiki/%C2%A4
- sytelus 13y agoI continue to be amazed by Ken Thompson's name popup in unexpected places even after all these decades. When I first learned that co-creator of Unix also invented Regular Expressions I was surprised. Then I came to know about that elegant hack of inserting malware in compiler that's practically invisible. And then Ed... Then Chess... And then UTF... And then Go... It feels like Ken Thompson is Newton of Computer Science. If you randomly open up a section of physics book 3-4 times, you are very likely to read something about Newton's contribution. Even what's more cool about him is this humble down-to-earth line from his Turing award lecture: I am a programmer. On my 1040 form, that is what I put down as my occupation. As a programmer, I write programs. It would be great to create a website that showcases all of his contributions in detail.
- LukeShu 13y agoNitpick: Thompson didn't invent regular expressions (that achievement belongs to Stephen Kleene), but he figured out how efficiently parse them with a computer, turning them from a mathematician's toy into something practical. I don't recall if Thompson is responsible for "modern" regular expression syntax--at least the `*` is borrowed from Kleene's notation. I'd look at Thompson's paper and find out, but I'm having trouble accessing my ACM subscription.
- nostrademons 13y agoThompson is at the very least responsible for the ^ and $ metacharacters.
- LukeShu 13y agoThompson's original paper used used the example espression: a(b|c)*d without any description of what it meant, so I take it that at the very least, that much was borrowed from Kleene. I am having a hard time reading it, to see if anything else was implemented, as I am unfamiliar with Algol-60 or IBM 7094 assembly. He cites Kleene's paper, saying that he assumes the reader is familiar with regular expressions; I'd look at that paper and see what Kleene described, but I can't find a copy of that. Thompson also site a paper by Brzozowski. The abstract for that paper includes: "Kleene's regular expressions, which can be used for describing sequential circuits, were defined using three operators (union, concatenation and iterate)" Which I take to mean that Kleene only came up with the syntax expressed in the example expression at the beginning.
- jacquesm 13y agoUTF-8 is a beautiful hack but the way applications handle UTF-8 text and deal with corruption ranges from excellent to horrible. I've had a text editor balk at me after an hour of work and trying to save with a 'xx character can not be encoded' and simply refusing to save without any hint as to where this character was. Playing manual divide and conquer without being able to save (just undo the changes) is pretty scary. Finally it turned out to be a quote that looked just like every other quote.
- webreac 13y agoThe UTF-8 hack is beautifull. All the problem of corruption range come from standardization commities. The only purpose of corruption range is to not admit that UCS2 and UTF16 were very bad ideas that should be killed.
- anonymouz 13y agoI wouldn't really call it a "hack", rather an instance of a standard way of producing variable length codes, namely a prefix code [1]. That it was also made to be self-synchronizing is of course neat, but again, as a hack I would rather describe some one-off thing rather than applications of well known concepts to solve a problem they were designed to solve. [1] https://en.wikipedia.org/wiki/Prefix_codes https://en.wikipedia.org/wiki/Prefix_codes
- sambeau 13y agoI once wrote a programming language that used UTF-8. I was rather proud of this hack that succinctly allowed UTF-8 variable / function names. I went searching for it and, sure enough, I still like it. BAD_UTF8 = [\xC0\xC1\xF5-\xFF]; UTF8_CB = [\x80-\xBF]; UTF8_2B = [\xC2-\xDF]; UTF8_3B = [\xE0-\xEF]; UTF82 = UTF8_2B UTF8_CB; UTF83 = UTF8_3B UTF8_CB UTF8_CB; UTF8 = UTF82 | UTF83 ; ATOM = ([_a-zA-Z]|UTF8)([_a-zA-Z0-9]|UTF8)*;
- ygra 13y agoThis looks limited to the BMP in the same way the broken utf8 charset for MySQL is. You're simply ignoring the existence of the other 16 planes. While not necessarily a problem in practice, especially with identifiers in programs, it still hints at a greater problem that you nonetheless chose to name this UTF-8 which it isn't.
- sambeau 13y agoYes, I chose to stop there for pragmatic reasons, however, the intention was always to add the other 4, 5 & 6 byte forms if/when needed. This was as much as I needed to test my wide char code (and to parse written languages e.g. Chinese). At least left like this my code would error properly if it encountered a character it didn't know.
- t_hozumi 13y agoI think that there is still a fundamental problem of string encoding. The problem is that decoders cannot know what encoding a byte stream was encoded in without additional information. Such information are often lost or omitted as you can see in web world. In such a situation, what decoders can do is just guessing. This is the reason why we still suffer Mojibake. A possible solution was to attach encoding information to a head of bytes as one or two byte. For example: UTF-8 = 0b00000001 UTF-16 = 0b00000002 Shift_JIS = 0b00000003 EUC-JP = 0b00000004 and so on. Of course this is not actual and reasonable solution because everyone must switch decoder/encoder to this protocol at once.
- userulluipeste 13y agoI never understood why there wasn't adopted a simpler solution, having bytes like: 0xxxxxxx the backward-compatible ASCII range 1xxxxxxx means this doesn't stand alone, but is followed by another one (or more) complementary byte(s). This way, the ASCII range would be defined like the "first order", and the 1xxxxxxx 0xxxxxxx would be the "2nd order" character range and so on! 1xxxxxxx 1xxxxxxx ... 0xxxxxxx as N-bytes length sequence would form the "Nth order" character range (with an extensible N, of course). This kind of encoding would have accommodated any range! If I am missing something, I'm all ears.