Just code IT

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

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

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

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

#literature

Low-tech Password Managers

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

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

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

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

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

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

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

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

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

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

#digest

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

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

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

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

#digest

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

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

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

В стандарте 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). 👇

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

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

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

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

#literature

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

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

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

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

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

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

#digest

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

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

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

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

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

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

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

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

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

#literature

Помните, когда последний раз сталкивались с текстом в неверной кодировке? Вероятно, это было достаточно давно — сегодня балом правит 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#literature

Just code IT pinned «Пока спросим, а чуть позже поясним 🙂 Насколько далеко, на ваш взгляд, следует заходить в поддержке legacy?»

Мало кто, когда речь заходит о литературе про разработку компиляторов, вспоминает книгу «Compiler Design in C» Аллена Голуба (Allen Holub). А зря. У нее практический уклон и выбор языка программирования.

Здорово, что автор, рассказывая о подходах к лексическому и синтаксическому анализу, показывает как можно реализовать на C генераторы таких анализаторов. Да, в книге есть реализация аналога YACC с полным объяснением внутренностей.

Интересен и выбор языка, который генерирует компилятор в качестве выхлопа. Хотя лучше обойтись без спойлеров!

#literature

Хороший пример проектной документации, неожиданно переросшей во что-то большее — сайт проекта Qibec.

Qibec — это процессор, собранный из отдельных транзисторов. Он устроен очень просто и может выполнять всего одну инструкцию. Такие процессоры называют OISC (One Instruction Set Computer) или URISC (Ultimate Reduced Instruction Set Computer). Несмотря на простоту, Qibec может выполнять произвольные программы.

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

На сайте описаны все аспекты работы Qibec, выложены файлы прошивки, схемы и утилиты для отладки и программирования.

Посмотрите, как здорово выглядит Qibec в действии!