В гольфе выигрывает тот, у кого меньше очков.

Применим этот принцип в Android. Мы собираемся поиграть в APK-гольф и создать приложение минимально возможного размера, которое можно установить на Android 8.0 Oreo.

Базовый уровень

Начнём с дефолтного приложения, который генерирует Android Studio. Создадим хранилище ключей, подпишем приложение и измерим размер файла в байтах командой stat -f%z $filename.

Затем установим APK на смартфон Nexus 5x под Oreo, чтобы убедиться, что всё работает.



Прекрасно. Наш APK весит примерно полтора мегабайта.

В настоящее время интерес к софтверным движкам, как из игр Quake, DOOM или Duke Nukem 3D практически нулевой. Однако, эти движки имели своё очарование и мне, например, очень нравится графика именно таких вот движков с нереалистичными текстурами на стенах. Конечно, такие текстуры можно накладывать без фильтрации и в OpenGL, получая такой же уровень графики, но всё же, написать собственный софтверный движок было весьма интересно. Движок уровня Quake я написать в своё время не смог, так как не удалось создать редактор 3D карты – я просто не представлял, как вообще рисовать в 3D карту. Да и с большой вероятность текстурирование в произвольном случае в моём исполнении (без ассемблера) было бы очень медленно. Но движок уровня DOOM мне покорился. Основу такого движка я написал в 2002 году, пользуясь книжкой Шикина и Борескова “Компьютерная графика. Полигональные модели”. На базе того движка используя графику из Doom я написал некое подобие игры под MS-DOS на Watcom C. Несколько лет назад я решил вынуть из той игры код движка и переработать его под мои текущие знания языка Си++ и представления о том, как стоило бы устроить этот движок. Ну и заодно перенести этот движок под Windows и дополнить наклонами головы, как в Blood или Duke Nukem. О том, что в результате получилось, я и написал в этой статье.

Недавняя статья на Slashdot о программировании игр на ассемблере для Атари (Donkey Kong и я) напомнила об ассемблерных приложениях, которые я писал по молодости, и о компьютерах, которые у нас тогда были.

Поначалу я набирался опыта на DEC PDP-8, но самый кайф начался, когда появилась CP/M. CP/M изначально была «операционной системой для бизнеса», но ещё это была система, которую можно было позволить себе иметь дома, — серьёзная вещь для молодого подающего надежды гика.

Многие дети российских 90-х с теплотой вспоминают часы, проведённые за приставками, — как с друзьями играли в «танчики», Батлтодс, Рокэнролл рэйсинг и кучу других игр. Уверен, что есть среди вас и такие, кто и до сих пор играет и коллекционирует классические приставки и игры для них. Что-то в них есть такое, что связывает с беззаботным детством.

Я и сам этим отчасти болею. Но когда я немного погрузился в мир ретрогейминга, оказалось, что в моем детстве было много такого, что так или иначе обошло меня стороной. Сейчас я говорю об аркадных автоматах — явлении, которое в 80-90-е было фактически двигателем прогресса. Многие знакомые нам игры сначала писались именно под аркадные автоматы, а уже потом портировались на домашние консоли в урезанном виде.

Среди интересующихся ретрогеймингом есть мнение, что играть надо на оригинальном железе, а эмуляция — это не тру. Это означает, что если вы решили вспомнить былые деньки и погонять с друзьями в «Чипа и Дэйла», то будьте добры достать себе приставку (желательно оригинальную NES или Famicom) и пару картриджей к ней. В современном мире это не проблема — можно купить всё это на интернет-аукционах. Вопрос только в том, с какой суммой вы готовы расстаться.

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

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

Выход — собрать аркадный автомат самому

Фильтр анизотропной диффузии Перона и Малика — это сглаживающий цифровые изображения фильтр, ключевая особенность которого состоит в том, что при сглаживании он сохраняет и «усиливает» границы областей на изображении.

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


Крайнее левое изображение — оригинальное, справа от оригинального — фильтрованные с различными параметрами.

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

→ Часть 0
→ Часть 1, общие оптимизации

В прошлый раз мы получили ускорение в среднем в 2,5 раза без изменения подхода. В этот раз я покажу, как применять SIMD-подход и получить ускорение еще в 3,5 раза. Конечно, применение SIMD для обработки графики не является ноу-хау, можно даже сказать, что SIMD был придуман для этого. Но на практике очень мало разработчиков используют его даже в задачах обработки изображений. Например, довольно известные и распространенные библиотеки ImageMagick и LibGD написаны без использования SIMD. Отчасти так происходит потому, что SIMD-подход объективно сложнее и не кроссплатформенный, а отчасти потому, что по нему мало информации. Довольно просто найти азы, но мало детальных материалов и разбора реальных задач. От этого на Stack Overflow очень много вопросов буквально о каждой мелочи: как загрузить данные, как распаковать, запаковать. Видно, что всем приходится набивать шишки самостоятельно.

Введение

Очень часто, нам разработчикам необходимо измерить время выполнения своего (и не только своего) кода. Когда я только начал программировать, я использовал структуру DateTime для этих целей. Прошло время, и я узнал о классе Stopwatch и начал его активно использовать. Думаю аналогичная ситуация была и у вас. Не то, чтобы я раньше не задавался вопросом о том, как работает Stopwatch, просто на тот момент знаний о том, что он позволяет измерять затраченное время точнее, чем DateTime мне хватало. Пришло время разъяснить себе, а так же читателям то, как на самом деле работает класс Stopwatch, а так же выяснить его преимущества и недостатки по сравнению с использованием DateTime.

Я обожаю миниатюрные клавиатурные устройства. Эта любовь у меня еще со времен первого Psion 5MX. С тех пор была еще Nokia E90 и так далее. Увы, со временем небольших устройств с клавиатурой становится все меньше, а любить их я не перестал (может быть тоже стоит сказать, увы). Поэтому мимо GPD Win пройти я никак не мог. Выглядит он вот так.



Диагональ его экрана составляет всего 5,5", он помещается во внутреннем кармане куртки, но внутри это самый что ни на есть полноценный нетбук на Windows.

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

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

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

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

Т.е. в данном примере, если попытаться открыть любой файл относительно файла $mft, доступ ко всему тому «С» повиснет, а так как этот том является системным, подвиснет и вся система. При этом не нужно иметь каких-либо прав. Если же том был не системным, то повиснет только доступ к этому тому, но если выполнить перезагрузку, то система повиснет на ней.

Около месяца свободного времени я уделил чтению исходного кода Quake II. Это был удивительный и поучительный опыт, потому что в движок idTech3 внесено большое изменение: Quake 1, Quake World и QuakeGL объединены в одну красивую архитектуру кода. Особенно был интересен способ, которым достигли модульности, несмотря на то, что язык программирования C не обеспечивает полиморфизма.

Quake II во многих отношениях является блестящим образцом программного обеспечения, потому что это был самый популярный (по количеству лицензий) трёхмерный движок всех времён. На его основе было создано более 30 игр. Кроме того, он ознаменовал переход игровой индустрии от программной/8-битной системы цветов к аппаратной/24-битной. Этот переход произошёл примерно в 1997 году.

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

Процесс «подчистки» меня сильно увлёк: в статье теперь более 40 мегабайт видео, скриншотов и иллюстраций. Сейчас я не знаю, стоили ли мои труды того, и нужно ли публиковать в будущем необработанные заметки в ASCII, выскажите своё мнение.

[Когда график поджимает и проект уже пора выпускать, программисты могут прибегать к грязным трюкам, чтобы уже наконец выпихнуть игру за дверь. В этой статье собрано девять примеров таких «костылей» из реальной жизни.]

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

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

Иногда при анализе какой-нибудь платной программы малвари случается так, что она не хочет нормально работать, если в памяти есть отладчик или включён отладочный режим Windows.
В таких ситуациях помогает использование виртуальной машины с подключённым к ней отладчиком (например, GDB или IDA). Это если программа не пытается «сломаться» и в виртуальной машине тоже.

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

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

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

[Прим. пер.: в оригинале статьи есть интерактивные демо, которые я продублировал с помощью видео. Для большей наглядности рекомендую изучить примеры в оригинале.]

В играх жанра Tower Defense (TD) множество врагов стремится добраться в одну точку. Во многих играх TD существует заранее заданный путь или несколько путей. В некоторых, в том числе в классической Desktop Tower Defense можно размещать башни в произвольных местах, и они становятся препятствиями, влияющими на пути врагов. Запустите демо и нажимайте на карту, чтобы возводить или убирать стены:

Изменение размера изображения с учётом содержимого (Content Aware Image Resize), жидкое растяжение (liquid resizing), ретаргетинг (retargeting) или вырезание шва (seam carving) относятся к методу изменения размера изображения, где можно вставлять или удалять швы, или наименее важные пути, для уменьшения или наращивания изображения. Об этой идее я узнал из ролика на YouTube, от Shai Avidan и Ariel Shamir.

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

Для подопытной картинки, я поискал по запросу¹ "sample image", и нашел её²:

Хочу рассказать сообществу о проведённом мной эксперименте.

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

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

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

Или ещё замечательный пример — Kerbal Space Program. Там физика уже является непосредственым источником геймплея.

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

Я давно мечтал сделать именно такой, до предела физически реалистичный римейк Scorched Earth. Но все мои эксперименты с моделированием физических систем упирались в неумолимо медленные процессоры. Тысяча-две частиц были пределом для real-time симуляции.

Но недавнее моё «открытие» изменило ситуацию.

Здравствуйте, меня зовут Саша, я написал самый быстрый ресайз изображений для современных х86 процессоров. Я так утверждаю, поскольку все остальные библиотеки, которые я сумел найти и протестировать, оказались медленнее. Я занялся этой задачей, когда работал над оптимизацией ресайза картинок на лету в Uploadcare. Мы решили открыть код и в результате появился проект Pillow-SIMD. Любой желающий с легкостью может использовать его в приложении на языке Python.

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

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

Отдавать реализацию на аутсорс слишком дорого и не гарантирует наилучшего решения. Отдать на откуп фрилансеру — дешевле, но и решение скорее всего будет таким же дешевым и основанным на существующих библиотеках, типа OpenCV. Но если бы задача решалась так просто, то конкуренты уже давно бы этим воспользовались и сделали достойный продукт, но его на рынке нет. В общем, присущие нам перфекционизм, амбициозность и желание быть лучшими, не позволяют нам выводить на рынок продукт «как у всех», нам нужно лучше, быстрее, сильнее. Приняли решение самостоятельно разобраться в вопросе, выработать решение, написать подробное техническое задание и уже отдать на реализацию фрилансеру. Была надежда, что существуют готовые решения, которых просто не заметили конкуренты. Но изучив вопрос (а вместе с ним и алгоритмы ORB, BRIEF, FAST, SIFT, SURF, BRISK, A-KAZE, Viola-Jones и еще несколько) стало понятно, что у всех этих алгоритмов есть свои недостатки. Хотя для решения нашей задачи некоторые из вышеперечисленных алгоритмов и подходили, но как то неожиданно захотелось уникальности и простоты решения. И вот выношу на суд сообщества, алгоритм собственного сочинения.

Любителей покритиковать (конструктивно) прошу под кат.

Ломать не строить. Иногда ломать — дело не менее сложное и благородное, чем строить.

В январе «Лаборатория Касперского» открывает свой сезон зимних айтишных видов спорта и запускает конкурс CrackMe. Скачайте три файла и разреверсите их, чтобы вычислить ключ, который генерируется в зависимости от введенного адреса email. Полученный ключ необходимо зарегистрировать на сайте.



Задания пронумерованы в порядке повышения сложности, поэтому советуем решать их в той же очередности.