Помните ли вы игрушки из своего детства?

Пожалуй, одну точно помнят многие. Восьмибитную игровую приставку, пиратский клон Nintendo Entertainment System (NES), которая продавалась в России под брендом Dendy. О-о-о, сколько времени было проведено за теми незабываемыми играми!

Как работало то, что приносило нам столько радости в детстве? Как создавались игры для NES, каковы были ограничения платформы по ресурсам? Программисты, увлекающиеся ретро-платформами, пытаются разобраться в этом.

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

К счастью, сегодня появилось больше информации о внутренностях NES и играх для нее. Например, вот хорошая иллюстрированная книга (все еще незаконченная), которая раскрывает особенности архитектуры приставки и показывает, как создавать для нее простые игры на языке ассемблера.

#literature

Помните, у нас тут был опрос, насколько далеко, на ваш взгляд, следует заходить в поддержке legacy?

Вот, откуда он вырос.

При недавнем осмотре кода ядра возник на первый взгляд несерьёзный вопрос: стоит ли проверять наличие инструкции cpuid прежде, чем начинать ею пользоваться?

С одной стороны, она присутствует в наборе инструкций, начиная с процессора Intel386, который вышел в 1985 году. И нам пока что не известен ни один случай, когда cpuid не была бы поддержана на процессоре архитектуры x86. Но ключевое слово здесь — «пока», потому что с другой стороны Intel Software Developers Manual в описании cpuid первым делом описывает способ проверки наличия данной инструкции. Сама проверка довольно простая — нужно проверить, что мы можем записать флаг ID в регистре xFLAGS.

И описание там неспроста...👇

Intel SDM описывает именно архитектуру x86, реализуемую Intel. То есть там описаны концептуальные вещи, свод правил, как должен работать ЦПУ. Если, допустим, по документации должно быть одно поведение, а на самом деле силикон ведет себя иначе — то это ситуация описывается в errata, а не исправляется мануал.

Из мануала следует тот факт, что архитектурно никто не обещает поддержку этой инструкции ни в одном из продуктов Intel на x86. Условный новый Intel Quark может кидать исключение #UD (undefined opcode) при попытке исполнения cpuid, что недопустимо, например, в том же загрузчике.

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

А теперь скажите еще раз: насколько, на ваш взгляд, далеко следует заходить в поддержке legacy? 😆

Наткнулись на познавательную статью 2002 года, оценивающую актуальность security evaluation, который учинили в 1974-ом году над ОС Multics.

Вкратце, старые операционки были более секурны даже без модных харденингов. А все из-за более строгих security default-ов и стека, растущего в правильном направлении (а значит, гудбай переполнение буфера на стеке и прощай ROP).

Сам отчет значительно длиннее его пост-анализа, но интересен с точки зрения формата и процедуры security evaluation тех лет.

Помните, когда последний раз сталкивались с текстом в неверной кодировке? Вероятно, это было достаточно давно — сегодня балом правит Unicode, а большинство операционных систем и приложений понимают кодировку UTF-8.

Но так было не всегда: компьютеры изначально были заточены исключительно на английский язык и использовали стандартную кодировку ASCII (American Standard Code for Information Interchange). Если вы хотели использовать какой-либо национальный алфавит, приходилось прибегать к альтернативным кодовым страницам.

Таких 8-битовых кодовых страниц разработали великое множество, в том числе и для кириллических языков.

Для русского языка в мире Unix наиболее распространенной кодировкой была KOI8-R. Аббревиатура KOI означает буквально "Код Обмена Информацией".

Программисты знали, что работа с текстами в этой кодировке была не слишком удобной: кириллические буквы в ней были расположены не по алфавиту, что сильно отличало кодировку от других. Это приводило к необходимости использовать таблицы поиска кодов символов и другие ухищрения.

Просто сравните.

В популярной одно время кодовой странице Windows-1251 коды кириллических строчных букв начинались с 0xE0 и далее располагались по алфавиту: 0xE0 соответствовал 'а', 0xE1 - 'б' и так далее.

В KOI8-R строчные кириллические буквы начинались с 'ю' под кодом 0xC0 и далее шли коды букв 'а', 'б', 'ц', 'д', 'е', 'ф' и других... Зачем такие сложности?

Пытливые читатели уже заметили, что последовательность букв в KOI8-R похожа по звучанию на последовательность букв в английском алфавите: a, b, c, d, e, f... И это не случайность.

Коды прописных латинских букв отличались от соответствующих им кодов строчных кириллических лишь на один бит: 0xC1 — 'а' (кириллическая), 0x41 — 'A' (латинская). В битовом представлении это 11000001 и 01000001.

Чем хороша эта особенность кодирования? На системах, которые умели работать только с семибитовыми кодировками, старший бит кода символа отбрасывался, поэтому русский текст в большинстве кодировок не мог быть отображен. Но выручала особенность кодирования кириллицы в KOI8-R: текст на таких системах отображался в фонетической транскрипции, только регистр букв инвертировался. "Привет, мир!" превращалось в "pRIVET, MIR!"

Кстати, особенности отображения текстов KOI8-R при просмотре в режиме других популярных кодовых страниц очень узнаваемы. А впечатлительные люди даже находят в этом мусоре из псевдографики тайный смысл!

#retro

Анатолий Шалыто — доктор технических наук, профессор ИТМО. Несмотря на возраст (родился в 1948 году), он ведет активную академическую жизнь. Во многом это объясняется его способностью к самомотивации.

Шалыто регулярно пишет короткие заметки, сподвигающие на большие свершения. Их он собирает в книгу «Заметки о мотивации». В ней уже 1111 страниц — хватит надолго.

#literature

Этот известный комикс XKCD повествует о методе генерации паролей, который называется pass phrases.

Pass phrase — это достаточно длинное бессмысленное предложение, состоящее из нескольких случайно подобранных слов. Теоретически, такие предложения ничуть не хуже коротких паролей, использующих разные регистры букв и спецсимволы.

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

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

Как вы думаете, достаточно ли безопасны pass phrases?

Пользуетесь ли вы менеджером паролей или помните пароли наизусть?

Пишите ответы в комментариях.

Вам тоже часто кажется, что для большинства задач можно найти не только сложное высокооптимизированное решение, но и более простое, которое дает довольно хороший результат?

Доминик Саблевски (Dominic Szablewski), например, придумал формат сжатия изображений без потерь, который в большинстве случаев показывает степень сжатия, сравнимую с PNG. Формат называется QOI («Quite OK Image Format» — «Вполне приемлемый формат изображения»).

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

Автор провел серию измерений на множестве различных изображений. Скорость декомпрессии может быть в 4 раза выше. Эти результаты впечатляют!

Исходный код проекта доступен на GitHub.

Кстати, он же создал шутер в стиле Quake для браузеров весом 13 килобайт всего за месяц. Чтобы поиграть, нужно перейти по ссылке.

#digest

Как решать сложные задачи?

Санджой Махаджан (Sanjoy Mahajan), автор книги The Art of Insight in Science and Engineering, предлагает традиционные инструменты, которые ученые и инженеры применяют для борьбы со сложностью. Среди них: «Разделяй и властвуй», абстракция, использование симметрии и подобия, анализ размерностей, базовые случаи, приблизительная оценка и т.п.

Подходы объединены в систему. Чтобы победить сложность, ей можно попытаться управлять или уменьшить ее, теряя часть информации о задаче.

И вдогонку — ещё одна книга Санджоя Махаджана, Street-Fighting Mathematics, про методы приблизительных вычислений. Это немного другой, расширенный взгляд на ряд подходов из предыдущей книги.

#literature

О «назальных демонах» и стандартах языка С

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

Но если сверить это со статистикой?

В стандарте ANSI C существует такое понятие как undefined behavior — термин, который дает компилятору некоторую свободу поведения (или кодогенерации) в определенных ситуациях. Это породило шутки о назальных демонах — «When the compiler encounters [a given undefined construct] it is legal for it to make demons fly out of your nose».

Иногда неопределенное поведение обусловлено желанием дать свободу оптимизации (например, переполнение знакового числа — это то самое undefined behavior, ведь может быть разное представление знака). Иногда неопределенное поведение описывают ситуацию глубокого заблуждения программиста (не стреляйте себе в ногу, переопределяя setjmp). 👇

И вот, ANSI C говорит о 96 причинах undefined behavior.
Стандарт ISO/IEC 9899:1999 (C99) говорит уже о 191 пунктах UB.
ISO/IEC 9899:2011 (C11) — о 203 (вот они во всей красе).
А стандарт С17 — и того более!

Если смотреть просто на KPI, то представляешь заголовки в духе желтой прессы о падении качества в новых стандартах. Ведь UB — один из источников уязвимостей...

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

А что вы думаете на эту тему?

#digest

Минутка пятничного настроения

Александр Золотов (Night Radio) выпустил свою музыкальную композицию в виде простой программы на Cи с единственной зависимостью от libSDL2. Все синтезаторы и звуковые эффекты реализованы непосредственно в программе.

Александр известен, в частности, своим модульным синтезатором SunVox и другими хорошими программами, ориентированными на сочинение музыки и компьютерную графику.

#digest

Сравнение latency различных операций в компьютерных системах

В System Design Primer попалась замечательная табличка со сравнением разного рода задержек в компьютерных системах. Например, там приводятся: время доступа к данным в L1 кеше, время обращения к ОЗУ, время чтения 4 килобайт с SSD, и так далее.

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

Low-tech Password Managers

Совсем недавно мы писали про pass phrases и способы запоминания паролей. Упоминали и менеджеры паролей, как наиболее безопасный способ хранения по-настоящему стойких к перебору паролей, но сложных для запоминания.

Теперь хотелось бы обратиться к факту бытия: кто-то просто записывает пароли на бумагу.

Плохо ли это, записывать пароли? Удивительно, но на этот счет есть разные мнения.

👉 Подробнее..

4 хорошие бесплатные книги про алгоритмы и структуры данных

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

Каждая из книг приводит примеры кода на своем языке — выбирайте стек по вкусу!

👉 Подробнее..

#literature

Пятничная минутка погружения в детство

Обнаружили новый шедевр от Morphcat Games — игру Böbl для ретро-платформы NES

Видео с игровым процессом доступно на Youtube https://www.youtube.com/watch?v=Uor-iTY-FqQ

Кстати, о самой NES мы ностальгировали совсем недавно в этом посте.

#fun

Симметричная криптография и цифровая подпись

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

Но существуют ли механизмы цифровой подписи, построенные вокруг симметричной криптографии?

👉 Разберемся подробнее

#digest

Занятный факт о режиме probe — он «читерит»

Probe mode используется для отладки CPU Intel через JTAG. В этом режиме конвейер останавливается, и появляется возможность обозревать его полное состояние, в зависимости от уровня доступа. Грубо говоря, когда CPU полностью разлочен, в т.н. уровне «red», мы можем обозревать вообще все — знать бы только JTAG IR DR сдвиги.

Есть еще уровень «orange» для OEM, когда Intel Top Secret информация недоступна для интроспекции, но частично открыты фабрики интерконнекта, которые могут помочь интеграции IP блоков. И есть дефолтный «green», когда мы с вами, например, можем посмотреть архитектурный стейт CPU — все, что описано в Intel SDM. Это, например, удобно, если вы отлаживаете прошивки с reset вектора.

Но вот в чем подвох — JTAG очень «железный». Это значит, что манипуляции IP блоками происходят на уровне сигналов. Стало быть, если мы хотим «прошагнуть» одну макроинструкцию, мы на самом деле не можем это сделать, потому что внутри ядра целый огромный конвейер, о котором мы ничего не знаем и не должны знать. То есть JTAG может крутить самые мелкие «крутилки» в конвейере, и исполнить макроинструкцию для него — слишком сложно.

И тут врывается probe mode! Грубо говоря, при помощи него можно «попросить» конвейер полностью прокрутить одну макроинструкцию и обновить архитектурное состояние. Причем прокрутка эта происходит в «идеальных» условиях, без сторонних эффектов, которые привносили бы соседи по конвейеру. Поэтому отладка через JTAG получается не совсем «железной», а только частично, когда дело доходит до разделения микро- и макро- архитектуры. Но и волки цели, и овцы сыты.

#digest