Русский
Русский
English
Статистика
Реклама

Кен томпсон

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

14.04.2021 12:16:12 | Автор: admin

Всем известна кодировка 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, работавший над системой Plane 9


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


Plane 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. Она была реализована в Plane 9 (операционная система, разработанная Bell Laboratories)
Это неправда. Я своими глазами видел, как однажды вечером в сентябре 1992 года была придумана UTF-8 на салфетке в одной закусочных Нью-Джерси.

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

В существующей реализации Unicode было много недостатков, например, чтобы понять, где именно начинается произвольный символ, надо было разобрать всю строку с самого начала, без этого нельзя было определить границы символов.
(прим. пер.)
Мы поняли, почему они хотят изменить дизайн и решили, что это хорошая возможность использовать наш опыт, чтобы разработать новый стандарт и заставить ребят из X/Open продвинуть его. Нам пришлось рассказать им об этом, и они согласились при условии, что мы быстро с этим справимся.
Потом мы пошли перекусить, и во время ужина Кен разобрался с упаковкой битов, а когда вернулись, то позвонили ребятам из X/Open и объяснили им нашу идею. Мы отправили по почте наш набросок, и они ответили, что это лучше, чем у них (но я точно помню, что они нам свой вариант не показывали), и спросили, когда мы сможем это реализовать.
Одним из вариантов разграничения символов был слэш, но это могло запутать файловую систему, она бы могла интерпретировать его как эскейп-последовательность.
(прим. пер.)
Мне кажется, что это происходило в среду вечером. Мы пообещали, что запустим систему к понедельнику, когда у них, как мне кажется, намечалось какое-то важное совещание. В тот же вечер Кен написал код кодировщика/раскодировщика, а я начал разбираться с С и с графическими библиотеками. На следующий день код был готов, и мы начали конвертировать текстовые файлы системы. К пятнице Plane 9 уже запускался и работал на так называемом UTF-8.
А в дальнейшем история была немного переписана.

Почему мы просто не воспользовались их FSS/UTF?
Насколько я помню, в том первом телефонном звонке я напел им Дезидерату своих требований для кодировки, и в FSS/UTF не было как минимум одного возможности синхронизировать поток байтов взятых из середины потока, используя для синхронизации как можно меньше символов (см выше, про определение границ символов. прим. пер).
напел им Дезидерату
Игра слов.
Имеется в виду крылатая фраза, берущая начало из альбома Леса Крейна 1971 года, чье название и заглавная композиция: Desiderata взяты из одноименной поэмы, что переводится с латыни, как: Желаемое. То есть, напел им Дезидерату следует понимать как высказал пожелания. (прим пер.)
Поскольку нигде решения не было, мы были вольны делать это как хотели.
Я думаю, что историю придумали IBM, а реализовали в Plane 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. Речь идет о том же, о чем и в предыдущем. Приношу свои извинения автору.

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

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



В связи с утверждением ISO/IEC 10646 (Unicode) в качестве международного стандарта и ожиданием широкого распространения этого Универсального Набора Кодированных символов (UCS), для операционных систем, исторически основанных на формате ASCII, необходимо разработать способы представления и обработки большого количества символов, которые можно закодировать с помощью нового стандарта. У UCS есть несколько проблем, которые нужно решить в исторически сложившихся операционных системах и среде для программирования на языке C.

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

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

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

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

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

Цель/Задача



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

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



Ниже приведены рекомендации, которые должны соблюдаться, при определении формата преобразования UCS:

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

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



Предлагаемый формат преобразования UCS кодирует значения UCS в диапазоне [0,0x7fffffff] с использованием нескольких байт на один символ и длинной 1, 2, 3, 4, 5, и 6 байт. Во всех случаях кодирования более чем одним байтом начальный байт определяет количество используемых байтов, при этом в каждом байте устанавливается старший бит. Каждый байт, который не начинается с 10XXXXXX, является началом последовательности символов UCS.

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

Bits  Hex Min Hex Max Byte Sequence in Binary1  7 00000000 0000007f 0vvvvvvv2  11 00000080 000007FF 110vvvvv 10vvvvvv3  16 00000800 0000FFFF 1110vvvv 10vvvvvv 10vvvvvv4  21 00010000 001FFFFF 11110vvv 10vvvvvv 10vvvvvv 10vvvvvv5  26 00200000 03FFFFFF 111110vv 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv6  31 04000000 7FFFFFFF 1111110v 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv10vvvvvv


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

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

typedefstruct{int  cmask;int  cval;int  shift;long lmask;long lval;} Tab;staticTab    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 */};intmbtowc(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;}intwctomb(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 ---

Скрытый текст

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



В связи с утверждением ISO/IEC 10646 (Unicode) в качестве международного стандарта и ожиданием широкого распространения этого Универсального Набора Кодированных символов (UCS), для операционных систем, исторически основанных на формате ASCII, необходимо разработать способы представления и обработки большого количества символов, которые можно закодировать с помощью нового стандарта. У UCS есть несколько проблем, которые нужно решить в исторически сложившихся операционных системах и среде для программирования на языке C.

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

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

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

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

Цель/Задача



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

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



Ниже приведены рекомендации, которые должны соблюдаться, при определении формата преобразования UCS:

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

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



Предлагаемый формат преобразования UCS кодирует значения UCS в диапазоне [0,0x7fffffff] с использованием нескольких байт на один символ и длинной 1, 2, 3, 4, 5, и 6 байт. Во всех случаях кодирования более чем одним байтом начальный байт определяет количество используемых байтов, при этом в каждом байте устанавливается старший бит. Каждый байт, который не начинается с 10XXXXXX, является началом последовательности символов UCS.

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

Bits  Hex Min Hex Max Byte Sequence in Binary1  7 00000000 0000007f 0vvvvvvv2  11 00000080 000007FF 110vvvvv 10vvvvvv3  16 00000800 0000FFFF 1110vvvv 10vvvvvv 10vvvvvv4  21 00010000 001FFFFF 11110vvv 10vvvvvv 10vvvvvv 10vvvvvv5  26 00200000 03FFFFFF 111110vv 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv6  31 04000000 7FFFFFFF 1111110v 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv10vvvvvv


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

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

typedefstruct{int  cmask;int  cval;int  shift;long lmask;long lval;} Tab;staticTab    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 */};intmbtowc(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;}intwctomb(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;}

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

T0 0xxxxxxx   7 free bitsTx 10xxxxxx   6 free bitsT1 110xxxxx   5 free bitsT2 1110xxxx   4 free bitsT3 11110xxx   3 free bitsT4 111110xx   2 free bitsT5 111111xx   2 free bits

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

>From hex Thru hex   Sequence       Bits00000000 0000007f   T0          700000080 000007FF   T1 Tx        1100000800 0000FFFF   T2 Tx Tx       1600010000 001FFFFF   T3 Tx Tx Tx     2100200000 03FFFFFF   T4 Tx Tx Tx Tx    2604000000 FFFFFFFF   T5 Tx Tx Tx Tx Tx  32

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

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

***


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

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

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

Почему работать в консоли настолько приятно? Так задумано отцами-основателями Unix

19.04.2021 12:12:03 | Автор: admin

Кен Томпсон и Деннис Ритчи

Unix. Легендарная операционная система оказала огромное влияние на разработку программного обеспечения и всю информатику в целом. Из неё выросли целые семейства Unix-подобных ОС, которыми все мы пользуемся.

Язык программирования Си, Ричард Столлман и GNU, движение Open Source, Линус Торвальдс с ядром Linux, маки, айфоны и Android. Почти всё в системном программировании 21века можно отследить до истоков до Unix.

Unix это фундаментальная база. Но что же в ней такого особенного? Есть один секрет. Точнее, два.

Философия Unix


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

Во-вторых это была правильная операционная система. Сделанная в соответствии с некими общими принципами, в соответствии с цельной философией Unix.

Брайан Керниган и Роб Пайк в книге Unix. Программное окружение формулируют основную идею этой философии:

Эффективность UNIX определяется применением особого подхода к программированию, философией использования компьютера. Для того, чтобы описать эту философию, одного предложения, конечно же, недостаточно, но вот её основная идея мощность системы в огромной степени определяется взаимодействием программ, а не их наличием.

Многие Unix-программы по отдельности выполняют довольно тривиальные задачи, но будучи объединёнными с другими, образуют полный и полезный инструментарий.

Другими словами, философия Unix это взаимодействие программ. Как говорил в своей презентации Брайан Керниган, программы Unix словно строительные блоки, которые можно комбинировать, складывая в эффективные конструкции. Выход одной программы является входом другой программы. Своеобразный конвейер (пайп).

Команды сочетаются в конвейер не только стандартными, очевидными способами. Бывают и весьма нетривиальные сочетания.

Волшебные конвейеры


Проще всего понять эту магию на конкретных примерах. пусть этот будет хит-парад авторов из репозитория по количеству коммитов, загрузка мемов с Reddit и смена обоев для рабочего стола каждый час согласно оценкам в подреддите /r/earthporn.

Список лидеров по числу коммитов


Начнём с простого примера: отобразить список авторов репозитория git, отсортированных по количеству коммитов. Если представить задачу в терминах конвейеров, то она довольно простая. Выводим логи коммитов командой git log. Опция --format=<format> позволяет указать, в каком формате отображать коммиты. В нашем случае --format='%an' выводит только имена авторов для каждого коммита.

$ git log --format='%an'AliceBobDeniseDeniseCandiceDeniseAliceAliceAlice

Теперь утилита sort сортирует их по алфавиту.

$ git log --format='%an' | sortAliceAliceAliceAliceBobCandiceDeniseDeniseDenise

Далее используем uniq.

$ git log --format='%an' | sort | uniq -c    4 Alice    1 Bob    1 Candice    3 Denise

Согласно man-странице uniq, она учитывает только соседние совпадающие строки. Вот почему нужно было сначала отсортировать список. Флаг -c выводит перед каждой строкой количество вхождений.

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

$ git log --format='%an' | sort | uniq -c | sort -nr    4 Alice    3 Denise    1 Candice    1 Bob

Флаг -r указывает на обратный порядок сортировки. Вот и всё. Теперь у нас есть список авторов, отсортированных по количеству коммитов.

Просмотр мемов из /r/memes и установка обоев из /r/earthporn


Вы знали, что можно добавить .json к любому URL на Reddit, чтобы получить выдачу в формате JSON вместо обычного HTML? Это открывает целый мир возможностей! Например, просмотр мемов прямо из командной строки (ну, не совсем, потому что фактическое изображение будет отображаться в графической программе). Мы можем просто запросить файл напрямую через curl или wget: https://reddit.com/r/memes.json.

$ wget -O - -q 'https://reddit.com/r/memes.json''{"kind": "Listing", "data": {"modhash": "xyloiccqgm649f320569f4efb427cdcbd89e68aeceeda8fe1a", "dist": 27, "children":[{"kind": "t3", "data": {"approved_at_utc": null, "subreddit": "memes","selftext": "More info available at....'......

Wget принимает опцию -O с указанием файла для записи. Большинство программ, которые принимают такую опцию, также допускают значение -, что означает стандартный вывод stdout (или ввод, в зависимости от контекста). Опция -q просто означает работу в тихом режиме, не отображая информацию типа статуса скачивания. Теперь у нас есть большая структура JSON. Чтобы проанализировать и осмысленно использовать эти данные в командной строке, можно взять утилиту jq, аналог sed/awk для JSON. У неё простой интуитивно понятный язык.

Ответ JSON выглядит примерно так:

{    "kind": "Listing",    "data": {        "modhash": "awe40m26lde06517c260e2071117e208f8c9b5b29e1da12bf7",        "dist": 27,        "children": [],        "after": "t3_gi892x",        "before": null    }}

Итак, здесь у нас тип Listing и массив children. Каждый элемент этого массива отдельный пост.

Вот как выглядит один из элементов массива:

{    "kind": "t3",    "data": {        "subreddit": "memes",        "selftext": "",        "created": 1589309289,        "author_fullname": "t2_4amm4a5w",        "gilded": 0,        "title": "Its hard to argue with his assessment",        "subreddit_name_prefixed": "r/memes",        "downs": 0,        "hide_score": false,        "name": "t3_gi8wkj",        "quarantine": false,        "permalink": "/r/memes/comments/gi8wkj/its_hard_to_argue_with_his_assessment/",        "url": "https://i.redd.it/6vi05eobdby41.jpg",        "upvote_ratio": 0.93,        "subreddit_type": "public",        "ups": 11367,        "total_awards_received": 0,        "score": 11367,        "author_premium": false,        "thumbnail": "https://b.thumbs.redditmedia.com/QZt8_SBJDdKLVnXK8P4Wr_02ALEhGoGFEeNhpsyIfvw.jpg",        "gildings": {},        "post_hint": "image",        ".................."        "много строк скипнуто"        ".................."    }}

Здесь много интересных атрибутов, в том числе URL картинки с мемом.

Мы можем легко получить список всех URL со всех постов:

$ wget -O - -q reddit.com/r/memes.json | jq '.data.children[] |.data.url'"https://www.reddit.com/r/memes/comments/g9w9bv/join_the_unofficial_redditmc_minecraft_server_at/""https://www.reddit.com/r/memes/comments/ggsomm/10_million_subscriber_event/""https://i.imgur.com/KpwIuSO.png""https://i.redd.it/ey1f7ksrtay41.jpg""https://i.redd.it/is3cckgbeby41.png""https://i.redd.it/4pfwbtqsaby41.jpg"......

Игнорируйте первые две ссылки, это в основном закреплённые посты от модераторов.

Утилита jq считывает данные из стандартного входа и получает JSON, который мы видели ранее. Затем указан массив постов .data.children. Синтаксис .data.children[] | .data.url означает: пройти по каждому элементу массива и вывести поле url, которое находится в поле data каждого элемента.

Таким образом, мы получаем список URL всех топовых мемов в подреддите /r/memes на данный момент. Если хотите посмотреть лучшие посты недели, нужно писать https://reddit.com/r/memes/top.json?t=week. Топ всех времён: t=all, за год: t=year и так далее.

Как только у нас есть список всех URL, можно просто передать его в xargs. Это действительно полезная утилита для построения командных строк из стандартного ввода. Из описания:

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

Пустые строки игнорируются.

То есть такая команда:

$ echo "https://i.redd.it/4pfwbtqsaby41.jpg" | xargs wget -O meme.jpg -q

будет равнозначна этой:

$ wget -O meme.jpg -q "https://i.redd.it/4pfwbtqsaby41.jpg"

Теперь можно просто передать список URL'ов в просмотрщик изображений feh или eog, который принимает URL в качестве допустимого аргумента.

$ wget -O - -q reddit.com/r/memes.json | jq '.data.children[] |.data.url' | xargs feh

И у нас запускается feh с мемами, которые можно листать клавишами со стрелками, словно это картинки на локальном диске.



Или можно загрузить все изображения с помощью wget, заменив feh на wget в строке выше.

А возможности безграничны. Ещё один вариант использования картинок с Reddit через JSON установка топовой картинки подреддита /r/earthporn в качестве обоев рабочего стола:

$ wget -O - -q reddit.com/r/earthporn.json | jq '.data.children[] |.data.url' | head -1 | xargs feh --bg-fill

Если хотите, можно настроить cron-задание, которое выполняется каждый час.


Лес в Нидерландах [20001333]


Гренландия [40323024]

Конечно, вместо /r/earthporn можно брать картинки из других подреддитов.

Вот в чём мощь конвейеров Unix. Одна-единственная строка делает всё: скачивает файл JSON, разбирает его, находит нужные данные, потом скачивает картинку по URL и устанавливает её в качестве обоев.

Это всего несколько случайных примеров. В реальности можно очень многое сделать однострочной командой в консоли, построив конвейер из простых утилит.

Работа, которая доставляет удовольствие


Особая философия Unix настолько глубока и фундаментальна, что породила целые классы Unix-подобных систем, к числу которых относятся BSD, macOS и Linux. Все они построены на этой философии. А побочный эффект работы в такой системе чувство правильности и цельности. Что так всё и должно работать: из кирпичиков, маленьких строительных блоков, которые сцепливаются в конвейеры любой сложности. Это же гениально.

Интересные факты об отцах-основателях


Может, через много лет Томпсона и Ритчи канонизируют, причислив к лику отцов-основателей разумного компьютерного мира. А сейчас цифровые археологи продолжают откапывать всё новые факты из истории Unix.

Например, в 2014 году исследователь Лея Нойкирхер нашла в дампах исходного дерева BSD 3 файл /etc/passwd с паролями всех ветеранов, таких как Деннис Ричи, Кен Томпсон, Брайан В. Керниган, Стив Борн и Билл Джой.

Для хэшей использовался алгоритм crypt(3) с максимальной длиной пароля 8 символов. Лея взломала их стандартными брутерами john и hashcat. Большинство паролей были очень слабыми. Только пароль Кена Томпсона не поддавался взлому. Даже полный перебор всех строчных букв и цифр (несколько дней) не дал результата. Неужели он использовал специальные символы? Лишь в 2017 году Найджел Уильямс в списке рассылки The Unix Heritage Society раскрыл эту тайну. Пароль со всеми возможными символами оказался q2-q4!: это первый ход пешкой на две клетки в описательной нотации и начало многих типичных дебютов, что очень хорошо вписывается в бэкграунд Кена Томпсона по компьютерным шахматам. Брутфорс на видеокарте AMD Radeon Vega64 занял более четырёх дней.

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


Десктоп Брайана Кернигана (октябрь 2015)

Деннис Ритчи (19412011) в 2002 году использовал необычную установку: его домашний клиент на NT4 подключён по ISDN к удалённому серверу Plan9 в центральном офисе Bell Labs.



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

Дальше у нас Брам Моленар, автор многофункционального текстового редактора Vim:


Десктоп Брама Моленара (сентябрь 2002)


Десктоп Брама Моленара (ноябрь 2015)

Джордан Хаббард, один из сооснователей проекта FreeBSD:


Десктоп Джордана Хаббарда (ноябрь 2015)

P. S. К сожалению, Линус Торвальдс не смог сделать скриншот из своей консоли в текстовом режиме.

Будем надеяться, новое поколение современных разработчиков не забудет, что мы стоим на плечах гигантов.



На правах рекламы


Устанавливайте любые операционные системы на наших VDS с мгновенной активацией. Сервер готов к работе через минуту после оплаты!

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru