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

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

Infinifactory

В этой статье мы поговорим о «магической» константе 0x5f3759df, лежащей в основе элегантного алгоритмического трюка для быстрого вычисления обратного квадратного корня.

Вот полная реализация этого алгоритма:

float FastInvSqrt(float x) {
  float xhalf = 0.5f * x;
  int i = *(int*)&x;  // представим биты float в виде целого числа
  i = 0x5f3759df - (i >> 1);  // какого черта здесь происходит ?
  x = *(float*)&i;
  x = x*(1.5f-(xhalf*x*x));
  return x;
}

Этот код вычисляет некоторое (достаточно неплохое) приближение для формулы



Сегодня данная реализация уже хорошо известна, и стала она такой после появления в коде игры Quake III Arena в 2005 году. Её создание когда-то приписывали Джону Кармаку, но выяснилось, что корни уходят намного дальше – к Ardent Computer, где в середине 80-ых её написал Грег Уолш. Конкретно та версия кода, которая показана выше (с забавными комментариями), действительно из кода Quake.
В этой статье мы попробуем разобраться с данным хаком, математически вывести эту самую константу и попробовать обобщить данный метод для вычисления произвольных степеней от -1 до 1.

Да, понадобится немного математики, но школьного курса будет более, чем достаточно.

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

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

Для тестирования код нужно выделить и скопировать прямо из твита. — прим. пер.

Недавно мне попался этот твит от @FakeUnicode. Там был сниппет JavaScript, который выглядел довольно безобидно, но выводил скрытое сообщение. Мне понадобилось некоторое время, чтобы понять происходящее. Думаю, что запись шагов моего расследования может быть кому-то интересна.

Вот тот сниппет:



Что бы вы ожидали от него?

Здесь используется цикл for in, который проходит через перечислимые свойства объекта. Поскольку указано только свойство A, можно предположить, что будет показано сообщение с буквой А. Ну… я ошибался. :D

Несколько месяцев назад я получил от друга такое письмо:

---

Тема: Можешь объяснить мне эту одну строчку кода?

Текст: Считай меня тупым, но… я не понимаю её и буду благодарен, если растолкуешь подробно. Это трассировщик лучей в 128 символах. Мне кажется, он восхитительный.

<pre id=p><script>n=setInterval("for(n+=7,i=k,P='p.\\n';i-=1/k;P+=P[i%2?(i%2*j-j+n/k^j)&1:2])j=k/i;p.innerHTML=P",k=64)</script>

---

Эта строчка JavaScript отрисует анимацию, которая показана на изображении под катом. В браузере она запускается здесь. Скрипт написан автором www.p01.org, где вы можете найти эту и много других классных демок.

Однажды, посреди рабочего дня мы внезапно осознали, что мы больше не можем так жить. Душа требовала совершить что-то бессмысленное и беспощадное во имя науки. И мы решили откалибровать кофе-машину. Нормальные люди тыкают в дефолтную кнопку и пьют все, что вытечет из кофеварки. Чуть более продвинутые для этого открывают инструкцию и тщательно ей следуют. Может быть еще читают рекомендации обжарщика, если конечно это не прогорклые noname зерна, которые пару лет лежали на безымянном складе. Нас к нормальным можно отнести с большой натяжкой, поэтому мы решили идти своим путем. Короче говоря, под легкой кофеиновой интоксикацией от седьмой чашки эспрессо мы решили задействовать весь возможный арсенал лаборатории, чтобы получить эталонный напиток.

Добро пожаловать в мир безумия, ультрацентрифуг, спектрофотометрии кофе в специальных планшетах и небольшого количества python, pandas и seaborn, чтобы визуализировать все это безобразие.

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

— Что, даже на том нечитаемом эзотерическом языке, где есть всего пара команд, которые едва-едва симулируют машину Тьюринга?
— Да, этот язык называется brainfuck. Я знаю brainfuck.

И это был не трюк — мы проверили. Я называл известный мне язык программирования, он тратил пару минут в Интернете на то, чтобы освежить свои знания по нему — и был способен писать на этом языке работающие алгоритмы. Я никак не мог понять этого. Ему, как и мне, было тогда около 18 лет — как он мог в этом возрасте знать все эти языки?


Интерпретатор brainfuck, написанный на brainfuck

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

Сегодня я советую своим студентам «постараться изучить все языки программирования». Подумайте сами — ведь эта идея лучше, чем все вот эти «В этом году я выучу Go! Ой, нет, теперь говорят что в моде Rust — выучу лучше Rust! Или Swift ...». Просто выучите все — не ошибётесь. А эта статья, возможно, вам в этом немного поможет.

Только что я столкнулся с еще одним проявлением синдрома самозванца: «Я правда разработчик — или просто хорошо гуглю?»

Далее следовал ответ, в котором я, однако, не увидел главного — поэтому ответить придется мне: слишком уж многие боятся без каких-либо оснований.

Переведено в Alconost

Если информацию легко найти, это не делает человека глупым

Частенько мне доводится слышать одну историю — полагаю, подлинность ее сомнительна, но, как бы там ни было, суть такова. Когда у Эйнштейна попросили номер телефона, он полез его искать и сказал: «Зачем запоминать то, что можно найти менее чем за две минуты?»

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


Дальше много картинок и gif-анимация. Но прежде, чем переходить под кат, посмотрите на картинку выше и скажите, что на ней нарисовано?

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

Отключив сборщик мусора Python (GC), который освобождает память, отслеживая и удаляя неиспользуемые данные, Instagram стал работать на 10% быстрее. Да-да, вы не ослышались! Отключив сборщик мусора, можно сократить объем потребляемой памяти и повысить эффективность работы кэша процессора. Хотите узнать, почему так происходит? Тогда пристегните ремни!

Вот интересная демонстрация возможностей afl; меня реально удивило, что она работает!

$ mkdir in_dir
$ echo 'hello' >in_dir/hello
$ ./afl-fuzz -i in_dir -o out_dir ./jpeg-9a/djpeg

В сущности, я создал текстовый файл только со словом "hello" и попросил фаззер выдавать поток в программу, которая ожидает на входе изображение JPEG (djpeg это простая утилита, которая идёт вместе с распространённой графической библиотекой IJG jpeg; libjpeg-turbo тоже должна подойти). Конечно, мои входные данные не похожи на валидное изображение, так что утилита быстро отвергает их:

$ ./djpeg '../out_dir/queue/id:000000,orig:hello'
Not a JPEG file: starts with 0x68 0x65

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

Жилой массив людей. Нет, серьёзно.

Холивары между ценителями Си и приверженцами его ублюдка сына в лице C++ начались ещё до моего рождения и прекратятся разве что после смерти обоих этих языков и меня заодно.

Адепты великого творения Кернигана-Ритчи до последней секунды рабочего дня готовы доказывать приспешникам Страуструпа аксиомы про вечность Си и его невероятную гибкость.
Те в ответ по-свойски советуют им лучше порадоваться рабочему дню, ведь он вот-вот окажется последним – двадцать первому веку кроссплатформенный ассемблер не нужен.
Распаляясь, сторонники Си приводят миллионы давно прошедших через голову навылет тезисов "почему Си лучше C++", при этом каждый раз подчёркивая, что второй все достоинства первого растерял ещё будучи в отцовской утробе, попутно утратив лик человеческий.
Обвиняемая сторона в обиде не остаётся и...

а хотя постойте, о чём это я.

Я люблю Си, уважаю C++ и не переношу холивары (честно). При этом я осознаю, что в Си действительно не хватает многого, и яркий тому пример – отсутствие удобной работы с данными. В C++ эту проблему во многом решает STL и свойства самого языка. На мой студенческий взгляд, здесь особо отличается всем знакомый std::vector. Если стало интересно, как я реализовал его аналог средствами C89 – прошу под кат.

Троичные вычисления

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

• Считаем до трёх: раз
• Считаем до трёх: два (память)
• Считаем до трёх: три (счётчики)
• Считаем до трёх: четыре (однотритный вычислитель и система команд трёхтритного)

Я выбрал сбалансированную троичную систему, в которой один трит может представлять одно из трёх значений -1, 0 или 1. Весьма подробно о ней можно почитать тут.

На любые вопросы из разряда «зачем?!» я отвечаю заранее: «Because I can».

Когда я читал книгу «Паттерны разработки игр», написанную замечательным человеком по имени Bob Nystrom (я не пишу его имя по-русски, поскольку не имею ни малейшего понятия, как это произносится), в одной из глав мне на глаза попалась небольшая ода языку Smalltalk как праотцу всех современных объектно-ориентированных языков, намного опередившему своё время. Поскольку я по жизни испытываю необоримую приязнь ко всяким винтажным языкам, естественно, я полез про него гуглить. И разумеется, вместо того, чтобы вынести из этого опыта что-то полезное, я научился плохому.

Настоящие программисты — это облака, big data, high load… А у нас — практически DIY. 2 установки — уже тиражирование, 100 штук — производство… Но зато атомные ледоколы, маневровые локомотивы, трактора, шлюзы, мосты, опускающиеся вниз от лишнего асфальта, беспилотники размером в дом, 50 человек персонала на цех длиной больше двух километров… и надежность, надежность, надежность… И пяток гендиректоров в костюмах прямо на поле при демонстрации системы на тракторе…


Обычное окончание отладки — убираем антенны с путеправильной машины

Итак… пришла просьба от коллег — написать ТКП (технико-коммерческое предложение) на хитрый GPS-трекер. И комментарии, что большие и настоящие делать отказались.

"Возможно, самая красивая система счисления — это сбалансированная троичная" — Дональд Е. Кнут, Искусство программирования, Издание 2.

Многие знают, что компьютеры хранят данные и работают с ними с помощью двоичной системы счисления. Одно из главных объяснений этому можно найти в схеме современных компьютеров, которые состоят из миллиардов простых и массово производимых транзисторов и конденсаторов, которые могут вместе представлять два состояния: высокое напряжение (1) и низкое напряжение (0).

Такая конструкция сегодня настолько распространена, что трудно себе представить, как компьютеры могут работать иначе. Но, в Советской России 50-х годов они работали иначе. Если вы вдруг не слышали про такое, загуглите "Сетунь" — сбалансированный трехкомпонентный компьютер, разработанный в 1958 году небольшой группой во главе с Брусенцовым, в МГУ.

Перед тем, как говорить о Брусенцове и Сетуни, давайте я немного объясню вам троичную сбалансированную систему счисления.

Сбалансированная троичность

Тернарная или троичная — это система счисления, в которой есть три вероятных значения: 0, 1 и 2. В её сбалансированной версии существуют три вероятности -1, 0 и +1, часто упрощённые до -, 0 и + соответственно.

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

Несколько лет назад Фабрис Беллар написал jslinux — эмулятор ПК, написанный на JavaScript. После этого был ещё как минимум Virtual x86. Но все они, насколько мне известно, являлись интерпретаторами, в то время как написанный значительно раньше тем же Фабрисом Белларом Qemu, да и, наверное, любой уважающий себя современный эмулятор, использует JIT-компиляцию гостевого кода в код хостовой системы. Мне показалось, что самое время реализовать обратную задачу по отношению к той, которую решают браузеры: JIT-компиляцию машинного кода в JavaScript, для чего логичнее всего виделось портировать Qemu. Казалось бы, почему именно Qemu, есть же более простые и user-friendly эмуляторы — тот же VirtualBox, например — поставил и работает. Но у Qemu есть несколько интересных особенностей

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

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

И вот, после двух лет неспешного ковыряния в свободное время исходников Qemu появился работающий прототип, в котором уже можно запустить, например, Kolibri OS.