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

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

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

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

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

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

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

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

Russ Cox  — Русс Кокс, сотрудник Bell Labs, работавший над системой Plan 9

Greger Leijonhufvud  — Один из сотрудников X/Open

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

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

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

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

Subject: UTF-8 history
From: "Rob 'Commander' Pike" 
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)

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

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

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

(прим. пер.)

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

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

(прим. пер.)

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

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

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

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

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

—Роб

Date: Sat, 07 Jun 2003 18:44:05 -0700
From: "Rob `Commander' Pike" 
To: Markus Kuhn 
cc: henry@spsystems.net, ken@entrisphere.com,
Greger Leijonhufvud 
Subject: Re: UTF-8 history

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

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

—Роб

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

Нашлось несколько писем из ваших ящиков, которые выдал грепинг по строке 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

Код был в какой-то степени протестирован и должен быть в довольно неплохой форме. Мы переделали код 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

Ниже приведены примеры реализаций стандартных функций 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

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

>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] != '\0';   /* return 0 for '\0', 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;
}

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, спустя почти тридцать лет, все еще актуальна и не собирается уходить на покой.

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