В коде id Software порой встречаются бесподобные жемчужины. Самая знаменитая — это, конечно, 0x5f3759df, удостоившаяся даже комикса на xkcd. Здесь же речь пойдёт о заливке экрана: пиксели закрашиваются по одному в случайном порядке, без повторов. Как это сделано?

Это приблизительная расшифровка лекции о предсказании переходов (предсказании ветвлений) на localhost, новом цикле лекций, организованном RC. Выступление состоялось 22 августа 2017 года в Two Sigma Ventures.

Кто из вас использует ветвления в своём коде? Можете поднять руку, если применяете операторы if или сопоставление с образцом?

Большинство присутствующих в аудитории поднимают руки

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

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

Кейт Холман и Зак Барт — разработчики из игровой студии Zachtronics. Если вы любите запутанные технические статьи о создании игр для 25-летних компьютеров, возможно, вам понравятся наши игры-головоломки: SpaceChem, Infinifactory, TIS-100 и SHENZHEN I/O!

Приступаем

Смогут ли два программиста, привыкшие к созданию игр для современных компьютеров с гигабайтами ОЗУ и полноцветными HD-дисплеями, портировать свои игры под MS-DOS? Никто из нас не имел опыта разработки на таком старом оборудовании, но работа в искусственно ограниченных системах — основа дизайна игр Zachtronics, поэтому мы были обязаны попробовать!

Проект начался с того, что Зак создал макет SHENZHEN SOLITAIRE, мини-игры в пасьянс из нашей игры SHENZHEN I/O (также продаваемой как отдельная игра). Вот как пасьянс мог выглядеть на экране 256-цветного VGA-дисплея:



Похоже на игры, которые можно было увидеть на экранах PC начала 90-х! Теперь осталось только написать код, правда?

Пролог

Все началось год назад, когда один из моих товарищей с форума T предложил переписать известную всему читерскому миру программу l2phx за авторством многоуважаемого xkor`а.
Сам l2phx (l2 packet hack, пакетник, хлапа) представляет из себя сниффер входящих и исходящих пакетов (все реализовано через LSP) клиента lineage 2 (существуют версии для других mmorpg), с возможностью отправки/подмены отдельных пакетов. Xkor постарался как следуют: реализовал методы обхода шифрации, красивый gui и тп. Но злобным админам фришек такое приложение не понравилось: оно существенно убивало их доход на старте очередных однодневок. Да-да, были времена когда любой нонейм мог зайти на любой сервер и устроить полную вакханалию этим инструментом. Тогда же и появились всяческие коммерческие защиты, которые безуспешно блокировали использование пакетника, а самые хитрые из них еще дополнительно шифровали трафик. Одна из таких защит живет на последнем издыхании и по сей день: встречайте, защита S. Сегодня защита S стоит на всех топовых серверах lineage 2. К слову, xkor предусмотрел такой исход и реализовал возможность самостоятельно написать модуль расшифровки пакетов (newxor.dll). Да только писать его было не рационально: новый сервер == новый newxor. Читерство по l2 постепенно начало умирать, ибо новички были не в состоянии отправлять пакеты методами изменения памяти клиента (HxD, cheat engine и тд).

Тогда я отнесся к этой затеи не очень серьезно: написал модуль перехвата пакетов клиент -> сервер и забросил. Почему? Потому. Но буквально 3 дня назад я решил возобновить работу над этим проектом и опубликовать данную статью. Почему? Комьюнити читеров l2 на данный момент мертво. Все баги и отмывы к ним находятся в руках 10 человек, которые общаются между собой в скайпе и на форуме T. И я тоже решил уйти. А если уходить, то лишь красиво)) Два года назад я мечтал о работающем пакетнике, а сегодня он мне не нужен.

Решение написать что-нибудь для Chaos Constructions пришло, как водится, довольно внезапно (в первую очередь потому, что до последнего момента не было очевидно, состоится он в этом году или нет). Так что, времени написать что-то большее, чем работу для конкурса Tiny intro (256 байт для любой платформы) уже не оставалось. Это же определило и выбор платформы, так как под Vectrex я уже писал пару лет назад и проще было вспомнить ассемблер 6809, чем изучать следующий.

Чем (среди прочего) мне нравится демосцена, так это тем что, приступая к работе, понятия не имеешь, что в итоге получишь. Среди нескольких идей, что именно написать, конкретно вот этой не было точно. Две были отброшены потому, что изображение на эмуляторе и реальном Vectrex'e слишком уж отличалось — после каждой сборки заливать всё это в эмулятор ПЗУ и перетыкать его в Vectrex чтобы посмотреть, что получилось — нереально.

Третью идею я было начал реализовывать, но уже в процессе увидел, что сделать такое красиво в 256 байт — слишком сложно. Но, в процессе что-то там переглючило и напомнило пружину. Вот эту идею я, в итоге, и развил:

Привет, Хабр! В своём первом посте я расскажу, как мы уже полгода как пишем неофициальный мультиплеер для NFS Most Wanted 2005 года выпуска. Сразу скажу — ссылок не будет, лишь скриншоты, дабы не сочли за банальную рекламу. Если будет интересно — спросите в комментариях. Поехали!

→ Оригинал статьи
Автор: Мартин Кръстев

Один мой друг обратил мое внимание на интересную статью на habrahabr.ru — русский перевод статьи Дэниела Лемира Быстрое удаление пробелов из строк на процессорах ARM. Эта статья заинтриговала меня по двум причинам: во-первых, кто-то на самом деле потратил время и усилия по поиску оптимального решения общей проблемы на не-x86 архитектуре (ура!), а во-вторых, результаты автор дал в конце статьи немного озадачили меня: порядка 6-ти кратное преимущество для Intel? Автор сделал однозначный вывод, что ARM-у ну очень далеко по соотношению «эффективность на такт» до «большого железа» от Интела в этой простой задаче.

Вызов принят!

(*) На самом деле, не совсем.
Наверное, многие слышали про Valgrind — отладчик, который может сказать, где в вашей нативной программе утечка памяти, где ветвление зависит от неинициализированной переменной и многое другое (а ведь кроме memcheck, у него есть и другие режимы работы). Внутри себя эта чудо-программа перемалывает нативный код в некий промежуточный байткод, инструментирует его и генерирует новый машинный код — уже с run-time проверками. Но есть проблема: Valgrind не умеет работать под Windows. Когда мне это понадобилось, поиски привели меня к аналогичной утилите под названием DrMemory, также с ней в комплекте был аналог strace. Но речь не столько о них, сколько о библиотеке динамической инструментации, на базе которой они построены, DynamoRIO. В какой-то момент я заинтересовался этой библиотекой с точки зрения написания собственной инструментации, начал искать документацию, набрёл на большое количество примеров и был поражён тем, что простенькую, но законченную инструментацию вроде подсчёта инструкций вызова можно написать буквально в 237 строк сишного кода, 32 из которых — лицензия, а 8 — описание. Нет, это, конечно не "пишем убийцу Valgrind в 30 строк кода на JavaScript", но сильно проще, чем то, что можно представить для подобной задачи.

В качестве примера давайте напишем уже четвёртую реализацию инструментации для фаззера American Fuzzy Lop, о котором недавно уже писали на Хабре.

Предположим, что я дал вам относительно длинную строку, а вы хотите удалить из неё все пробелы. В ASCII мы можем определить пробелы как знак пробела (‘ ’) и знаки окончания строки (‘\r’ и ‘\n’). Меня больше всего интересуют вопросы алгоритма и производительности, так что мы можем упростить задачу и удалить все байты со значениями меньшими либо равными 32.

В предыдущией статье, где я задавал вопрос об удалении пробелов на скорость, лучшим ответом было использование векторизации с помощью 128-битных регистров (SSE4). Оно оказалось в 5-10 раз быстрее подхода в лоб.

Очень удобно, что во всех процессорах имеются 128-битные векторные регистры, также как в процессорах x64. Неужели процессоры ARM могут работать настолько же быстро, как процессоры x64?

Инструкторы курсов «Введение в программирование» знают, что студенты находят любые причины для ошибок своих программ. Процедура сортировки отбраковала половину данных? «Это может быть вирус в Windows!» Двоичный поиск ни разу не сработал? «Компилятор Java сегодня странно себя ведёт!» Опытные программисты очень хорошо знают, что баг обычно в их собственном коде, иногда в сторонних библиотеках, очень редко в системных библиотеках, крайне редко в компиляторе и никогда — в процессоре. Я тоже так думал до недавнего времени. Пока не столкнулся с багом в процессорах Intel Skylake, когда занимался отладкой таинственных сбоев OCaml.

Первое проявление

В конце апреля 2016 года вскоре после выпуска OCaml 4.03.0 один Очень Серьёзный Индустриальный Пользователь OCaml (ОСИП) обратился ко мне в частном порядке с плохими новостями: одно из наших приложений, написанное на OCaml и скомпилированное в OCaml 4.03.0, падало случайным образом. Не при каждом запуске, но иногда вылетал segfault, в разных местах кода. Более того, сбои наблюдались только на их самых новых компьютерах, которые работали на процессорах Intel Skylake (Skylake — это кодовое название последнего на тот момент поколения процессоров Intel. Сейчас последним поколением является Kaby Lake).

За последние 25 лет мне сообщали о многих багах OCaml, но это сообщение вызывало особенное беспокойство. Почему только процессоры Skylake? В конце концов, я даже не мог воспроизвести сбои в бинарниках ОСИПа на компьютерах в моей компании Inria, потому что все они работали на более старых процессорах Intel. Почему сбои не воспроизводятся? Однопоточное приложение ОСИПа делает сетевые и дисковые операции I/O, так что его выполнение должно быть строго детерминировано, и любой баг, который вызвал segfault, должен проявлять себя при каждом запуске в том же месте кода.

Наконец-то можно запустить в моём компьютере на электромагнитных реле программу длиннее одной инструкции. Сейчас в нём есть ПЗУ на 8 команд, процессор с АЛУ и 8 восьмибитных регистров (один из которых PC).

Всего процессор поддерживает 5 групп инструкций: Арифметико-логические операции (ALU), Загрузка числа в регистр (MOVI), пересылка между регистрами (MOV), Остановка работы (HALT), Работа с памятью (LDST). Но есть нюансы…

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

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

MASM

Используется для создания драйверов под Windows.

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

Итак, в этой статье вы узнаете, как я писал кейген к ArtMoney (здесь будет описана версия 7.45.1).

Отшумели страсти после моей первой статьи на Хабре.

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

Сайт уже был один раз под подобным наплывом посетителей — когда в августе кто то опубликовал ссылку на сайт одновременно в Твиттер, ФБ и Реддит.

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

Как и ожидалось, чудо свершилось. Несмотря на то, что хостинг предельно слабенький (я его взял такой специально), несмотря на то, что сайт использует БД SQLite, которую все считают очень медленной, форум не упал. Он даже не замедлился. Все время сайт работал исправно и обслуживал всех посетителей.

Посмотрим как выглядит Хабраэффект изнутри:

Конечно, многие скажут, что это ни-ни и писать для веба нужно только на PHP, ну или на один из модерных языках Питон, Руби, Node.js и т.д.

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

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

Раньше у меня уже было веб-приложение на ассемблере — CMS для малого сайта. Только оно работает в режиме "один пишет, многие читают". При том, использует CGI интерфейс и поэтому "многие" читать одновременно тоже не получается.

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

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

Тёплый ламповый щелкающий звук тактового генератора:

Однажды мне пришлось вычислять сумму векторов целых чисел.

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

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

• её можно эффективно выполнить с помощью процессорной инструкции ADC (к сожалению, эта функция недоступна в C);
• её можно выполнить на словах любого размера (можете добавить по желанию восьмибайтные значения, только результат следует уменьшить до двух байт и добавить все биты переполнения);
• она нечувствительна к порядку следования байтов (удивительно, но это так).

Какое-то время назад я переводил рассказ Chris Salomon о его разработке игры Frogger для компьютера Vectrex. Тот рассказ, написанный им в 1998 году, является, на мой взгляд, очень интересным документом, позволяющим проникнуться как духом этой необычной платформы, так и спецификой разработки на ассемблере вообще.

Chris не забросил Vectrex и, сравнительно недавно, довёл до релиза собственный эмулятор Vectrex для Windows (лучший, на данный момент) под названием «Vide». Мне, к слову, приятно, что мои исходники Electric Force помогли ему реализовать приличную поддержку отображения векторных кривых в этом эмуляторе.

И вот, получив в руки такой мощный инструмент, Chris не смог отказать себе в удовольствии вернуться к своему старому Frogger'у, чтобы доработать и улучшить его. Об этом он рассказал в своём блоге.

Таким образом, здесь я публикую две части моего перевода — первую, об оригинальной разработке 1998 года (из файла progger.txt, бродившего вместе с исходниками игры) и вторую — о её продолжении (из блога автора).