Как придумали кодировку UTF-8: выдержки из переписки создателей

Всем известна кодировка UTF-8, что давно доминирует в интернет пространстве, и которой пользуются много лет. Казалось бы, о ней все известно, и ничего интересного на эту тему не рассказать. Если почитать популярные ресурсы типа Википедии, то действительно там нет ничего необычного, разве что в английской версии кратко упоминается странная история о том, как ее «набросали на салфетке в закусочной». 

На самом деле изобретение этой кодировки не может быть настолько банальным хотя бы потому, что к ее созданию приложил руку Кен Томпсон — легендарная личность. Он работал вместе с Деннисом Ритчи, был одним из создателей UNIX, внес вклад в разработку C (изобрел его предшественника — B), а позднее, во время работы в Google, принял участие в создании языка Go. 

Перед вами — перевод нескольких писем, в которых разработчики вспоминают историю создания кодировки. 

Действующие лица:

ken (at) entrisphere.com — Кен Томпсон

Кен Томпсон (слева) с Деннисом Ритчи

«Rob 'Commander' Pike» — Роберт Пайк, канадский программист, работавший над UTF-8 вместе c Кеном Томпсоном

mkuhn (at) acm.org — Маркус Кун, немецкий ученый в области информатики

henry (at) spsystems.net — Генри Сперсер, автор одной из реализаций RegExp

Russ Cox <rsc@plan9.bell-labs.com> — Русс Кокс, сотрудник Bell Labs, работавший над системой Plan 9

Greger Leijonhufvud <greger@friherr.com> — Один из сотрудников X/Open

Plan 9 — Операционная система, в которой впервые была использована кодировка UTF-8 для обеспечения ее мультиязычности.

UTF-8 — Кодировка символов Юникода

Переписка 2003 года

Ниже переписка создателей кодировки, Роберта и Кена, которую Роберт Пайк начал, сетуя на то, что их вклад в создание UTF-8 незаслуженно забыли. Роберт просит одного из старых знакомых порыться в архивах почтового сервера и найти там доказательства их участия. (прим. пер.)

Subject: UTF-8 history
From: "Rob 'Commander' Pike" <r (at) google.com>
Date: Wed, 30 Apr 2003 22:32:32 -0700 (Thu 06:32 BST)
To: mkuhn (at) acm.org, henry (at) spsystems.net
Cc: ken (at) entrisphere.com

Глядя на разговоры о происхождении UTF-8, я вижу, как постоянно повторяют одну и ту же историю. 

Неправильная версия: 

1. UTF-8 разработала IBM.
2. Она была реализована в Plan 9 (операционная система, разработанная Bell Laboratories)

Это неправда. Я своими глазами видел, как однажды вечером в сентябре 1992 года была придумана UTF-8 на салфетке в одной закусочных Нью-Джерси. 

Произошло это таким образом. Мы пользовались оригинальным UTF из стандарта ISO 10646 для поддержки 16-битных символов в Plan 9, который ненавидели, и уже были готовы к выпуску Plan 9, когда однажды поздно вечером мне позвонили одни парни, кажется они были из IBM. Я припоминаю, что встречался с ними на заседании комитета X/Open в Остине. Они хотели, чтобы мы с Кеном посмотрели их проект FSS/UTF. 

В то время подавляющее большинство компьютерных программ и систем (документация, сообщения об ошибках и т.п.) было только на английском и только слева направо. Инженерам из Bell Labs показалось, что релиз Plan 9 — хороший повод для того, чтобы изменить это, поскольку проще всего вводить новшества в систему на этапе ее разработки, а не исправлять уже выпущенный продукт. Потому они стали искать специалистов, которые помогут им интернационализировать их проект.

В существующей реализации Unicode было много недостатков, например, чтобы понять, где именно начинается произвольный символ, надо было разобрать всю строку с самого начала, без этого нельзя было определить границы символов.

(прим. пер.)

Мы поняли, почему они хотят изменить дизайн и решили, что это хорошая возможность использовать наш опыт, чтобы разработать новый стандарт и заставить ребят из X/Open продвинуть его. Нам пришлось рассказать им об этом, и они согласились при условии, что мы быстро с этим справимся. 

Потом мы пошли перекусить, и во время ужина Кен разобрался с упаковкой битов, а когда вернулись, то позвонили ребятам из  X/Open и объяснили им нашу идею. Мы отправили по почте наш набросок, и они ответили, что это лучше, чем у них (но я точно помню, что они нам свой вариант не показывали), и спросили, когда мы сможем это реализовать.

Одним из вариантов разграничения символов был слэш, но это могло запутать файловую систему, она бы могла интерпретировать его как эскейп-последовательность.

(прим. пер.)

Мне кажется, что это происходило в среду вечером. Мы пообещали, что запустим систему к понедельнику, когда у них, как мне кажется, намечалось какое-то важное совещание. В тот же вечер Кен написал код кодировщика/раскодировщика, а я начал разбираться с С и с графическими библиотеками. На следующий день код был готов, и мы начали конвертировать текстовые файлы системы. К пятнице Plan 9 уже запускался и работал на так называемом UTF-8. 

А в дальнейшем история была немного переписана.

Почему мы просто не воспользовались их FSS/UTF? 

Насколько я помню, в том первом телефонном звонке я напел им Дезидерату своих требований для кодировки, и в FSS/UTF не было как минимум одного — возможности синхронизировать поток байтов взятых из середины потока, используя для синхронизации как можно меньше символов (см выше, про определение границ символов. прим. пер).

Поскольку нигде решения не было, мы были вольны делать это как хотели.
Я думаю, что «историю придумали IBM, а реализовали в Plan 9» берет свое начало в документации по RFC 2279. Мы были так счастливы, когда UTF-8 прижился, что никому не рассказали эту историю. 

Никто из нас больше не работает в Bell Labs, но я уверен, что сохранился архив электронной почты, которая может подтвердить нашу историю, и я могу попросить кого-нибудь покопаться в ней.

Итак, вся слава достается парням из X/Open и IBM за то, что они сделали это возможным и продвинули кодировку, но разработал ее Кен, и я ему помогал в этом, что бы там не говорилось в книгах по истории. 

—Роб

Date: Sat, 07 Jun 2003 18:44:05 -0700
From: "Rob `Commander' Pike" <r@google.com>
To: Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk>
cc: henry@spsystems.net, ken@entrisphere.com,
Greger Leijonhufvud <greger@friherr.com>
Subject: Re: UTF-8 history

Я попросил Расса Кокса покопаться в архивах. Прикладываю его сообщение. Я думаю, вы согласитесь, что это подтверждает историю, которую я отправил раньше. Письмо, которое мы выслали в X/Open (думаю, что Кен редактировал и рассылал этот документ) включает новый «desideratum номер 6» про обнаружение границ символов. 

Мы уже не узнаем, какое влияние оказало на нас оригинальное решение от X/Open. Они хоть и отличаются, но имеют общие характерные черты. Я не помню, чтобы подробно его рассматривал, это было слишком давно (в прошлом письме он говорит, что X/Open им свой вариант реализации не показывали. прим. пер). Но я очень хорошо помню, как Кен писал наброски на салфетке и потом жалел, что мы ее не сохранили. 

—Роб

From: Russ Cox <rsc@plan9.bell-labs.com>
To: r@google.com
Subject: utf digging
Date-Sent: Saturday, June 07, 2003 7:46 PM -0400

Файл пользователя bootes /sys/src/libc/port/rune.c был изменен пользователем division-heavy 4 сентября 1992 года. Версия, попавшая в дамп имеет время 19:51:55. На другой день в него был добавлен комментарий, но в остальном он не изменялся до 14 ноября 1996 года, когда runelen была ускорена путем явной проверки значения rune вместо использования значения, возвращаемого runetochar. Последнее изменение было 26 мая 2001 года, когда была добавлена runenlen. (Rune — структура, содержащая значение Юникод. Runelen и runetochar — функции, работающие с этим типом данных. прим.пер)

Нашлось несколько писем из ваших ящиков, которые выдал грепинг по строке utf. 

В первом идет речь про файл utf.c, который является копией wctomb и mbtowc (функции преобразования символов. прим. пер.), что обрабатывают полную 6-байтовую кодировку UTF-8, 32-битных runes. С логикой управления потоком это выглядит довольно уродливо. Я предполагаю, что этот код появился в результате того первого письма. 

В /usr/ken/utf/xutf я нашел копию того, что, по видимому, является исходником того не самосинхронизирующегося способа кодирования.со схемой UTF-8, добавленной в конце письма (начинается со слов «Мы определяем 7 типов byte»). 

Приведенная ниже версия письма, датированная 2 сентября 23:44:10, является первой. После нескольких правок, утром 8 сентября, получилась вторая версия. Логи почтового сервера показывают, как отправляется вторая версия письма и, через некоторое время, возвращается к Кену:

helix: Sep  8 03:22:13: ken: upas/sendmail: remote inet!xopen.co.uk!xojig
>From ken Tue Sep  8 03:22:07 EDT 1992 (xojig@xopen.co.uk) 6833
helix: Sep  8 03:22:13: ken: upas/sendmail: delivered rob From ken Tue Sep 8 03:22:07 EDT 1992 6833
helix: Sep  8 03:22:16: ken: upas/sendmail: remote pyxis!andrew From ken Tue Sep  8 03:22:07 EDT 1992 (andrew) 6833
helix: Sep  8 03:22:19: ken: upas/sendmail: remote coma!dmr From ken Tue Sep  8 03:22:07 EDT 1992 (dmr) 6833
helix: Sep  8 03:25:52: ken: upas/sendmail: delivered rob From ken Tue Sep 8 03:24:58 EDT 1992 141
helix: Sep  8 03:36:13: ken: upas/sendmail: delivered ken From ken Tue Sep 8 03:36:12 EDT 1992 6833

Всего хорошего.

Файлы из почтового архива

Далее файл с перепиской из дапма почтового сервера, который Расс Кокс приаттачил к своему, в ответ на просьбу Роберта покопаться в истории. Это «первая версия». (прим пер.)

>From ken Fri Sep  4 03:37:39 EDT 1992

Вот наше предложение по модификации FSS-UTF. Речь идет о том же, о чем и в предыдущем. Приношу свои извинения автору. 

Код был в какой-то степени протестирован и должен быть в довольно неплохой форме. Мы переделали код Plan 9 для использования с этой кодировкой, собрались выпустить дистрибутив и отобрать пользователей университета для начального тестирования. 

File System Safe Universal Character Set Transformation Format (FSS-UTF)

(Далее в тексте несколько раз упоминаются «historical operating systems».  Видимо в контексте «исторически работающие с кодировкой ASCII». Я или опускал этот эпитет, или заменял его на «существующие» и т.п. прим. пер)

Самой серьезной проблемой является схема кодирования, используемая в UCS. А именно объединение стандарта UCS с существующими языками программирования, операционными системами и утилитами. Проблемы в языках программирования и операционных системах решаются в разных отраслях, тем не менее мы все еще сталкиваемся с обработкой UCS операционными системами и утилитами. 

Среди проблем, связанных с обработкой UCS в операционных системах, главной является представление данных внутри файловой системы. Основополагающей концепцией является то, что надо поддерживать существующие операционные системы, в которые были вложены инвестиции, и в тоже время пользоваться преимуществами большого количества символов, предоставляемых UCS. 

UCS дает возможность закодировать многоязычный текст с помощью одного набора символов. Но UCS и UTF не защищают нулевые байты (конец строки в некоторых языках. прим. пер.) и/или слеш в ASCII /, что делает эти кодировки несовместимыми с Unix. Следующее предложение обеспечивает формат преобразования UCS, совместимый с Unix, и, таким образом, Unix-системы могут поддерживать многоязычный текст в рамках одной кодировки.

Данная кодировка формата преобразования предназначена для кодирования файлов, как промежуточный шаг к полной поддержке UCS. Однако, поскольку почти все реализации Unis сталкиваются с одинаковыми проблемами поддержки UCS, это предложение предназначено для обеспечения общей совместимости кодировки на данном этапе.

Цель/Задача

Критерии для формата преобразования

1. Совместимость с существующими файловыми системами.
   Запрещено использовать нулевой байт и символ слэша как часть имени файла. 
2. Совместимость с существующими программами.
   В существующей модели многобайтовой обработки не должны использоваться коды ASCII. В формате преобразования представления символа UCS, которого нет в наборе символов ASCII, не должны использоваться коды ASCII.
3. Простота конвертации из UCS и обратно.
4. Первый байт содержит указание на длину многобайтовой последовательности.
5. Формат преобразования не должен быть затратным, в смысле количества байт, используемых для кодирования.
6. Должна быть возможность легко определять начало символа, находясь в любом месте байтового потока (строки. прим.пер.).

Предписания FSS-UTF

Простой способ запомнить формат: количество старших единиц в первом байте означает количество байт в многобайтовом символе.

Bits    Hex Min  Hex Max  Byte Sequence in Binary
1    7  00000000 0000007f 0vvvvvvv
2   11  00000080 000007FF 110vvvvv 10vvvvvv
3   16  00000800 0000FFFF 1110vvvv 10vvvvvv 10vvvvvv
4   21  00010000 001FFFFF 11110vvv 10vvvvvv 10vvvvvv 10vvvvvv
5   26  00200000 03FFFFFF 111110vv 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv
6   31  04000000 7FFFFFFF 1111110v 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv

Значение символа UCD в многобайтовой кодировке — это конкатенация v-битов. Если возможно несколько способов кодирования, например UCS 0, то допустимым считается самый короткий.

Ниже приведены примеры реализаций стандартных функций C wcstombs() и mbstowcs(), которые демонстрируют алгоритмы конвертирования из UCS в формат преобразования и конвертирования из формата преобразования в UCS. Примеры реализаций включают проверку ошибок, некоторые из которых могут быть не нужны для согласования:

typedef

struct
{
    int   cmask;
    int   cval;
    int   shift;
    long  lmask;
    long  lval;
} Tab;

static
Tab       tab[] =
{
    0x80, 0x00,  0*6,   0x7F,         0,            /* 1 byte sequence */
    0xE0, 0xC0,  1*6,   0x7FF,        0x80,         /* 2 byte sequence */
    0xF0, 0xE0,  2*6,   0xFFFF,              0x800,        /* 3 byte sequence */
    0xF8, 0xF0,  3*6,   0x1FFFFF,     0x10000,      /* 4 byte sequence */
    0xFC, 0xF8,  4*6,   0x3FFFFFF,    0x200000,     /* 5 byte sequence */
    0xFE, 0xFC,  5*6,   0x7FFFFFFF,   0x4000000,    /* 6 byte sequence */
    0,                                              /* end of table */
};

int
mbtowc(wchar_t *p, char *s, size_t n)
{
    long l;
    int c0, c, nc;
    Tab *t;

    if(s == 0)
        return 0;

    nc = 0;
    if(n <= nc)
        return -1;
    c0 = *s & 0xff;
    l = c0;
    for(t=tab; t->cmask; t++) {
        nc++;
        if((c0 & t->cmask) == t->cval) {
            l &= t->lmask;
            if(l < t->lval)
                return -1;
            *p = l;
            return nc;
        }
        if(n <= nc)
            return -1;
        s++;
        c = (*s ^ 0x80) & 0xFF;
        if(c & 0xC0)
            return -1;
        l = (l<<6) | c;
    }
    return -1;
}

int
wctomb(char *s, wchar_t wc)
{
    long l;
    int c, nc;
    Tab *t;

    if(s == 0)
        return 0;

    l = wc;
    nc = 0;
    for(t=tab; t->cmask; t++) {
        nc++;
        if(l <= t->lmask) {
            c = t->shift;
            *s = t->cval | (l>>c);
            while(c > 0) {
                c -= 6;
                s++;
                *s = 0x80 | ((l>>c) & 0x3F);
            }
            return nc;
        }
    }
    return -1;
}

>From ken Tue Sep  8 03:24:58 EDT 1992

Я послал его по почте, но письмо ушло в черную дыру, потому я не получил свою копию. Наверное, это интернет-адрес был в коме.

Вторая версия письма, с правками

Далее прикладывается копия письма, которая выше описывается как: «После нескольких правок, утром 8 сентября, получилась вторая версия». Повторяющаяся часть скрыта под спойлером. (прим.пер.)

>From ken Tue Sep  8 03:42:43 EDT 1992

Наконец-то я получил свою копию.

--- /usr/ken/utf/xutf from dump of Sep 2 1992 ---

Bits    Hex Min  Hex Max  Byte Sequence in Binary
1    7  00000000 0000007f 0vvvvvvv
2   11  00000080 000007FF 110vvvvv 10vvvvvv
3   16  00000800 0000FFFF 1110vvvv 10vvvvvv 10vvvvvv
4   21  00010000 001FFFFF 11110vvv 10vvvvvv 10vvvvvv 10vvvvvv
5   26  00200000 03FFFFFF 111110vv 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv
6   31  04000000 7FFFFFFF 1111110v 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv

typedef

struct
{
    int   cmask;
    int   cval;
    int   shift;
    long  lmask;
    long  lval;
} Tab;

static
Tab       tab[] =
{
    0x80, 0x00,  0*6,   0x7F,         0,            /* 1 byte sequence */
    0xE0, 0xC0,  1*6,   0x7FF,        0x80,         /* 2 byte sequence */
    0xF0, 0xE0,  2*6,   0xFFFF,              0x800,        /* 3 byte sequence */
    0xF8, 0xF0,  3*6,   0x1FFFFF,     0x10000,      /* 4 byte sequence */
    0xFC, 0xF8,  4*6,   0x3FFFFFF,    0x200000,     /* 5 byte sequence */
    0xFE, 0xFC,  5*6,   0x7FFFFFFF,   0x4000000,    /* 6 byte sequence */
    0,                                              /* end of table */
};

int
mbtowc(wchar_t *p, char *s, size_t n)
{
    long l;
    int c0, c, nc;
    Tab *t;

    if(s == 0)
        return 0;

    nc = 0;
    if(n <= nc)
        return -1;
    c0 = *s & 0xff;
    l = c0;
    for(t=tab; t->cmask; t++) {
        nc++;
        if((c0 & t->cmask) == t->cval) {
            l &= t->lmask;
            if(l < t->lval)
                return -1;
            *p = l;
            return nc;
        }
        if(n <= nc)
            return -1;
        s++;
        c = (*s ^ 0x80) & 0xFF;
        if(c & 0xC0)
            return -1;
        l = (l<<6) | c;
    }
    return -1;
}

int
wctomb(char *s, wchar_t wc)
{
    long l;
    int c, nc;
    Tab *t;

    if(s == 0)
        return 0;

    l = wc;
    nc = 0;
    for(t=tab; t->cmask; t++) {
        nc++;
        if(l <= t->lmask) {
            c = t->shift;
            *s = t->cval | (l>>c);
            while(c > 0) {
                c -= 6;
                s++;
                *s = 0x80 | ((l>>c) & 0x3F);
            }
            return nc;
        }
    }
    return -1;
}

int mbtowc(wchar_t *p, const char *s, size_t n)
{
       unsigned char *uc;      /* so that all bytes are nonnegative */

       if ((uc = (unsigned char *)s) == 0)
           return 0;               /* no shift states */
       if (n == 0)
           return -1;
       if ((*p = uc[0]) < 0x80)
           return uc[0] != '';   /* return 0 for '', else 1 */
       if (uc[0] < 0xc0)
       {
           if (n < 2)
               return -1;
           if (uc[1] < 0x80)
               goto bad;
           *p &= 0x3f;
           *p <<= 7;
           *p |= uc[1] & 0x7f;
           *p += OFF1;
           return 2;
       }
       if (uc[0] < 0xe0)
       {
           if (n < 3)
               return -1;
           if (uc[1] < 0x80 || uc[2] < 0x80)
               goto bad;
           *p &= 0x1f;
           *p <<= 14;
           *p |= (uc[1] & 0x7f) << 7;
           *p |= uc[2] & 0x7f;
           *p += OFF2;
           return 3;
       }
       if (uc[0] < 0xf0)
       {
           if (n < 4)
               return -1;
           if (uc[1] < 0x80 || uc[2] < 0x80 || uc[3] < 0x80)
               goto bad;
           *p &= 0x0f;
           *p <<= 21;
           *p |= (uc[1] & 0x7f) << 14;
           *p |= (uc[2] & 0x7f) << 7;
           *p |= uc[3] & 0x7f;
           *p += OFF3;
           return 4;
       }
       if (uc[0] < 0xf8)
       {
           if (n < 5)
               return -1;
           if (uc[1] < 0x80 || uc[2] < 0x80 || uc[3] < 0x80 || uc[4] < 0x80)
               goto bad;
           *p &= 0x07;
           *p <<= 28;
           *p |= (uc[1] & 0x7f) << 21;
           *p |= (uc[2] & 0x7f) << 14;
           *p |= (uc[3] & 0x7f) << 7;
           *p |= uc[4] & 0x7f;
           if (((*p += OFF4) & ~(wchar_t)0x7fffffff) == 0)
               return 5;
       }
bad:;
       errno = EILSEQ;
       return -1;
}

Мы определяем 7 байтовых типов:

T0 0xxxxxxx      7 free bits
Tx 10xxxxxx      6 free bits
T1 110xxxxx      5 free bits
T2 1110xxxx      4 free bits
T3 11110xxx      3 free bits
T4 111110xx      2 free bits
T5 111111xx      2 free bits

Кодирование выглядит следующим образом:

>From hex Thru hex      Sequence             Bits
00000000  0000007f      T0                   7
00000080  000007FF      T1 Tx                11
00000800  0000FFFF      T2 Tx Tx             16
00010000  001FFFFF      T3 Tx Tx Tx          21
00200000  03FFFFFF      T4 Tx Tx Tx Tx       26
04000000  FFFFFFFF      T5 Tx Tx Tx Tx Tx    32

Некоторые примечания:

1. Двумя байтами можно закодировать 2^11 степени символов, но использоваться будут только 2^11—2^7. Коды в диапазоне 0-7F будут считаться недопустимыми.  Я думаю, что это лучше, чем добавление кучи «магических» констант без реальной пользы. Это замечание применимо ко всем более длинным последовательностям.
2. Последовательности из 4, 5 и 6 байт существуют только по политическим причинам. Я бы предпочел их удалить.
3. 6-байтовая последовательность охватывает 32 бита, предложение FSS-UTF охватывает только 31.
4. Все последовательности синхронизируются по любому байту, не являющемуся Tx.

***

Эта короткая переписка расставила все по своим местам. Хоть и не сохранилась та «легендарная салфетка», но выдержек из архива почтового сервера хватило, чтобы сообщество признало их заслуги. В Википедию добавили имена Кена и Роберта и забавный факт про салфетку в закусочной, а в сети эта история гуляет и обсуждается «как есть», в виде простого текста, содержащего несколько писем и часть дампа из почтового сервера. 

Давно забыта операционная система Plan 9, никто не помнит для чего ее писали и почему она «номер девять», а UTF-8, спустя почти тридцать лет, все еще актуальна и не собирается уходить на покой.

Казалось бы, это всего лишь кодировка, но даже такая простая история может оказаться занимательной, если немного в нее углубиться. На заре развития технологий нельзя было предугадать, что выстрелит и войдет в историю, а что забудется.

Источник архивов

Автор: ruvds

Источник