Мир изменился. Я чувствую это в воде, чувствую это в земле, ощущаю в воздухе.
«Властелин колец», Джон Рональд Руэл Толкин
Alexey Dokuchaev
@danfe
Оператор ЭВМ
Возвращаем к жизни калькулятор HP Prime G2
10 min
Tutorial
Калькулятор с восстановленной прошивкой.
В предыдущих сериях:
- Установка Linux на калькулятор. Часть I
- Установка Linux на калькулятор. Часть II
- Запускаем DOOM на калькуляторе HP Prime G2
Если вы читали серию моих опытов с калькулятором, то вероятнее всего, помните, что в попытке сделать бекап оригинальной прошивки, я её окончательно и бесповоротно стёр. Далее, после всех моих экспериментов, калькулятор был сложен в коробочку, и в ней даже пережил переезд, но с тех пор не покидал её. Поскольку линукс ещё требовалось допиливать до рабочего состояния, а энтузиазм уже совершенно закончился. Да и не очень понятно, какое практическое применение калькулятора с линукс, разве что девчонкам показывать, что там работает doom. В целом, весь проект был для того, чтобы освежить в памяти сборку и установку линукс на подобные устройства, дабы мозги не ржавели.
В результате, когда в очередной раз наткнулся в шкафу на лоток с этим барахлом, принял волевое решение вернуть его к жизни, в качестве калькулятора, каким он и был в девичестве.
Как обычно, путь был тернист, даже был сформирован мердж реквест автору перепрошивки линукса, но обо всём по порядку.
Реставрация ноутбука Commodore 286LT
4 min
Мы в Software & Computer Museum любим старые компьютеры. И особенно нам нравится, когда они работают. Сегодня хочу поделиться историей, как мы реставрировали ноутбук Commodore 286LT. У него было довольно много проблем и я расскажу о решении каждой из них.
Волновой метод построения цветовой гаммы
8 min
Sandbox
Привет, Хабр!
В колористике существует несколько методов построения цветовой гаммы (цветовой палитры), основанных на расположении цветов друг относительно друга в цветовом круге и, как правило, имеющих одинаковую яркость. Гармоничность восприятия которых не обоснована в достаточной степени с физической точки зрения.
В теории музыки есть понятие консонирующих интервалов. Консонансами называют интервалы, звучащие более мягко и гармонично. Есть три группы консонансов: весьма совершенные (чистый унисон, октава), совершенные (чистая квинта, чистая кварта) и несовершенные (большая терция, малая терция, секста). Также есть понятие консонирующего аккорда — мажорное или минорное трезвучие, состоящее исключительно из консонирующих интервалов.
Ускоряем неускоряемое или знакомимся с SIMD
9 min
Есть класс задач, которые нельзя ускорить за счёт оптимизации алгоритмов, а ускорить надо. В этой практически тупиковой ситуации к нам на помощь приходят разработчики процессоров, которые сделали команды, позволяющие выполнять операции на большим количеством данных за одну операцию. В случае x86 процессоров это инструкции сделанные в расширениях MMX, SSE, SSE2, SSE3, SSE4, SSE4.1, SSE4.2, AVX, AVX2, AVX512.
В качестве «подопытного кролика» я взял следующую задачу:
В таком виде бенчмарк показывает следующие результаты:
Под катом я покажу как его ускорить в 5+ раз.
В качестве «подопытного кролика» я взял следующую задачу:
Есть неупорядоченный массив arr с числами типа uint16_t. Необходимо найти количество вхождений числа v в массив arr.Классическое решение, работающее за линейное время выглядит так:
int64_t cnt = 0;
for (int i = 0; i < ARR_SIZE; ++i)
if (arr[i] == v)
++cnt;
В таком виде бенчмарк показывает следующие результаты:
------------------------------------------------------------
Benchmark Time CPU Iterations
------------------------------------------------------------
BM_Count 2084 ns 2084 ns 333079
Под катом я покажу как его ускорить в 5+ раз.
Реверс-инжиниринг рендеринга «Ведьмака 3»
27 min
Translation
Недавно я начал разбираться с рендерингом «Ведьмака 3». В этой игре есть потрясающие приёмы рендеринга. Кроме того, она великолепна с точки зрения сюжета/музыки/геймплея.
В этой статье я расскажу о решениях, использованных для рендеринга The Witcher 3. Она не будет такой всеобъемлющей, как анализ графики GTA V Адриана Корреже, по крайней мере, пока.
Мы начнём с реверс-инжиниринга тональной коррекции.
В этой статье я расскажу о решениях, использованных для рендеринга The Witcher 3. Она не будет такой всеобъемлющей, как анализ графики GTA V Адриана Корреже, по крайней мере, пока.
Мы начнём с реверс-инжиниринга тональной коррекции.
Мастер-класс «Почему Стив Джобс любил шрифты» (Алексей Каптерев)
19 min
Tutorial
Привет, Хабр! Давно у нас в блоге не было расшифровок мастер-классов. Исправляемся. В этом посте вас ждет грандиозное путешествие в мир шрифтов от древнейших времен до наших дней. Если вы хотите понять, каким образом шрифты влияют на наши эмоции и наконец научиться отличать гуманистический гротеск от ленточной антиквы — добро пожаловать под кат. И да, там очень много картинок. Передаем слово автору.
Шутка, написанная гарнитурой Times, на 10 % смешнее той, что написана гарнитурой Arial. Почему? Чёрт знает. Лучшее объяснение, которое я видел: юмор ассоциируется с агрессией, с остротой, с остроумием — а Times выглядит более острым, чем Arial.
Ещё один любопытный эксперимент, в котором участвовало 45 тыс. человек. Заходишь на сайт, тебе показывают статью Дэвида Дойча, британского физика. В статье автор пишет, что сегодня очень трудно внезапно умереть. Например, от инфекционного заболевания или в уличной драке. Лет сто назад это случалось намного чаще. Главный вывод статьи — сейчас мир безопасен как никогда. В среднем, конечно, ведь где-то постоянно идут локальные военные конфликты.
Стоимость операций в тактах ЦП
17 min
Translation
Всем доброго! Вот мы и добрались до тематики С++ на наших курсах и по нашей старой доброй традиции делимся тем, что мы нашли достаточно интересным при подготовке программы и то, что будем затрагивать во время обучения.
Инфографика:
Когда нам нужно оптимизировать код, мы должны отпрофилировать его и упростить. Однако, иногда имеет смысл просто узнать приблизительную стоимость некоторых популярных операций, чтобы не делать с самого начала неэффективных вещей (и, надеюсь, не профилировать программу позже).
Инфографика:
Когда нам нужно оптимизировать код, мы должны отпрофилировать его и упростить. Однако, иногда имеет смысл просто узнать приблизительную стоимость некоторых популярных операций, чтобы не делать с самого начала неэффективных вещей (и, надеюсь, не профилировать программу позже).
Реверс-инжиниринг игры Lost Vikings
31 min
Translation
После интересной обратной разработки игрового движка Comprehend (см. Recomprehend) я подбирал новый проект для реверс-инжиниринга игры под DOS. За долгие годы разные люди реверсировали множество старых популярных игр и опубликовали для них спецификации и инструменты. Например, на сайте shikadi.net есть куча информации об играх, в которые я играл в детстве.
Я обнаружил, что для реверс-инжиниринга игры The Lost Vikings компании Blizzard (тогда она называлась Silicon and Synapse), похоже, не предпринималось никаких серьёзных попыток. Игра была выпущена в 1993 году, на закате эры DOS, и очень нравилась мне в юности. The Lost Vikings — это головоломка-платформер, в которой игрок управляет тремя викингами, каждый из которых имеет собственные умения. Викингам нужно объединить свои силы для решения загадок и прохождения уровней с различной тематикой: космический корабль, доисторический мир, Древний Египет. На изображении ниже показан первый уровень игры (источник: Strategy Wiki):
Казалось, что эту игру разобрать будет довольно просто. Уровни основаны на тайловых картах и содержат простые загадки: кнопки, включающие и отключающие объекты, передвижные ящики и поднимающий предметы кран. И на самом деле, бóльшая часть проекта по обратной разработке была достаточно прямолинейной. У игры есть один пакетный файл данных, содержащий сжатые блоки файлов. Блоки кодируют различные ресурсы игры, такие как спрайты, карты, звуки и т.д. Я написал несколько утилит, которые можно использовать для просмотра ресурсов игры: The Lost Vikings Tools.
Я обнаружил, что для реверс-инжиниринга игры The Lost Vikings компании Blizzard (тогда она называлась Silicon and Synapse), похоже, не предпринималось никаких серьёзных попыток. Игра была выпущена в 1993 году, на закате эры DOS, и очень нравилась мне в юности. The Lost Vikings — это головоломка-платформер, в которой игрок управляет тремя викингами, каждый из которых имеет собственные умения. Викингам нужно объединить свои силы для решения загадок и прохождения уровней с различной тематикой: космический корабль, доисторический мир, Древний Египет. На изображении ниже показан первый уровень игры (источник: Strategy Wiki):
Казалось, что эту игру разобрать будет довольно просто. Уровни основаны на тайловых картах и содержат простые загадки: кнопки, включающие и отключающие объекты, передвижные ящики и поднимающий предметы кран. И на самом деле, бóльшая часть проекта по обратной разработке была достаточно прямолинейной. У игры есть один пакетный файл данных, содержащий сжатые блоки файлов. Блоки кодируют различные ресурсы игры, такие как спрайты, карты, звуки и т.д. Я написал несколько утилит, которые можно использовать для просмотра ресурсов игры: The Lost Vikings Tools.
Задача с погрешностью и переполнением
3 min
Хочу с вами поделиться небольшой алгоритмической задачей, которую мне не так давно подкинули коллеги по цеху. Как мне кажется, решение получилось довольно элегантное.
Суть задачи заключалась в следующем. Есть некое устройство (микроконтроллер), которое умеет обращаться только с 32-битными целыми значениями и не умеет работать с плавающей запятой.
На таком аппарате есть таймер, который в секунду генерирует 32768 тиков. Необходимо написать функцию, переводящую тики в миллисекунды без потери точности (желательно с округлением).
Суть задачи заключалась в следующем. Есть некое устройство (микроконтроллер), которое умеет обращаться только с 32-битными целыми значениями и не умеет работать с плавающей запятой.
На таком аппарате есть таймер, который в секунду генерирует 32768 тиков. Необходимо написать функцию, переводящую тики в миллисекунды без потери точности (желательно с округлением).
Правда о PCM компании Numonyx: революция, которой не случилось
3 min
Анекдот вместо предисловия:
— Вы слышали, Иванов выиграл в лотерею «Волгу».
— Вообще-то не Иванов, а Рабинович, не «Волгу», а сто рублей, не в лотерею, а в преферанс, и не выиграл, а проиграл.
На днях на Хабре появилась ссылка на сногсшибательную новость: в технологии производства памяти произошла революция, и скоро у нас будет единая память супер-пупер память на основе халькогенидных материалов, использующая фазовые переходы, вызванные нагревом при пропускании через ячейку электрического тока. Работает быстро как DRAM, да еще и энергонезависимая, как Flash.
К сожалению, практически все, написанное в статье — неправильно…
Чтобы у хабрасообщества не создалось неправильного представления о том, что происходит в мире памяти, хотелось бы рассказать правдивую историю PCM.
На вполне резонный вопрос с галерки: «А ты собсно кто такой, чтобы нам твою якобы правду слушать?» могу ответить, что я работаю отделе разработки компании-производителя памяти (в том числе и PCM) и по долгу службы «держу руку на пульсе».
— Вы слышали, Иванов выиграл в лотерею «Волгу».
— Вообще-то не Иванов, а Рабинович, не «Волгу», а сто рублей, не в лотерею, а в преферанс, и не выиграл, а проиграл.
На днях на Хабре появилась ссылка на сногсшибательную новость: в технологии производства памяти произошла революция, и скоро у нас будет единая память супер-пупер память на основе халькогенидных материалов, использующая фазовые переходы, вызванные нагревом при пропускании через ячейку электрического тока. Работает быстро как DRAM, да еще и энергонезависимая, как Flash.
К сожалению, практически все, написанное в статье — неправильно…
Чтобы у хабрасообщества не создалось неправильного представления о том, что происходит в мире памяти, хотелось бы рассказать правдивую историю PCM.
На вполне резонный вопрос с галерки: «А ты собсно кто такой, чтобы нам твою якобы правду слушать?» могу ответить, что я работаю отделе разработки компании-производителя памяти (в том числе и PCM) и по долгу службы «держу руку на пульсе».
Типографская раскладка в линуксе
2 min
xkeyboard-config с версии 1.5 содержит дополнительный уровень с полезными юникодными символами, который можно прилепить к любой раскладке. Собственно, я поучаствовал в процессе его добавления туда. Этот набор символов был написан несколько лет назад под впечатлением от раскладки Ильи Бирмана, потом постоянно переделывался и стабилизировался.
Автоматическая оптимизация алгоритмов с помощью быстрого возведения матриц в степень
20 min
Пусть мы хотим вычислить десятимиллионное число Фибоначчи программой на Python. Функция, использующая тривиальный алгоритм, на моём компьютере будет производить вычисления более 25 минут. Но если применить к функции специальный оптимизирующий декоратор, функция вычислит ответ всего за 18 секунд (в 85 раз быстрее):
Дело в том, что перед выполнением программы интерпретатор Python компилирует все её части в специальный байт-код. Используя метод, описанный хабрапользователем SkidanovAlex, данный декоратор анализирует получившийся байт-код функции и пытается оптимизировать применяющийся там алгоритм. Далее вы увидите, что эта оптимизация может ускорять программу не в определённое количество раз, а асимптотически. Так, чем больше будет количество итераций в цикле, тем в большее количество раз ускорится оптимизированная функция по сравнению с исходной.
Эта статья расскажет о том, в каких случаях и каким образом декоратору удаётся делать подобные оптимизации. Также вы сможете сами скачать и протестировать библиотеку cpmoptimize, содержащую данный декоратор.
Дело в том, что перед выполнением программы интерпретатор Python компилирует все её части в специальный байт-код. Используя метод, описанный хабрапользователем SkidanovAlex, данный декоратор анализирует получившийся байт-код функции и пытается оптимизировать применяющийся там алгоритм. Далее вы увидите, что эта оптимизация может ускорять программу не в определённое количество раз, а асимптотически. Так, чем больше будет количество итераций в цикле, тем в большее количество раз ускорится оптимизированная функция по сравнению с исходной.
Эта статья расскажет о том, в каких случаях и каким образом декоратору удаётся делать подобные оптимизации. Также вы сможете сами скачать и протестировать библиотеку cpmoptimize, содержащую данный декоратор.
Секреты тернарного оператора
4 min
Каждый уважающий себя программист С\С++ знает что такое тернарный оператор и большинство использовало его хотя бы раз в своих программах. Но знаете ли вы все секреты тернарного оператора? Какие потенциальные опасности сопряжены с его использованием и какие, казалось бы не связанные с его прямым предназначением, возможности в нем таятся? Эта статья дает вам возможность проверить свои знания и, возможно, узнать что-то новое.
Android компонент с нуля
7 min
Tutorial
Sandbox
Всем привет! Создание собственных компонентов интерфейса часто является необходимостью чтобы выделиться из общей массы похожих программ. В этой статье как раз рассматривается создание простого, нестандартного компонента на примере кнопки-таймера.
Кроссворд из регулярных выражений
1 min
Кроссворд, подсказки в котором — регулярные выражения.
Оригинал в PDF.
Автор — не я! Это часть MIT Mistery Hunt 2013.
Оригинал в PDF.
Автор — не я! Это часть MIT Mistery Hunt 2013.
Теория относительности в картинках
6 min
Tutorial
В своей статье я хотел бы рассказать о теории относительности. Эта теория не требуется в представлении. С самого своего создания она была окутана ореолом тайны, поскольку полностью подрывает наши привычные представления о пространстве и времени. Все мы в школе учили формулы теории относительности, но мало кто действительно понимал их. И это не удивительно, ведь человеку, чтобы по-настоящему понять какую-то теорию во всей её красоте, полноте и непротиворечивости, не достаточно знать формулы. Нужно иметь какой-то визуальный ориентир, нужна динамика, чтобы было что-то, что можно повертеть в руках. Я решил восполнить этот пробел и написал небольшую программку, в которой можно «повертеть в руках» пространство-время. Мы, как настоящие исследователи, с помощью небольших экспериментов попытаемся выяснить основные свойства этой загадочной материи.
Под катом много картинок (и ни одной формулы).
Под катом много картинок (и ни одной формулы).
Используем быстрое возведение матриц в степень для написания очень быстрого интерпретатора простого языка программирования
6 min
Sandbox
Недавно на хабре появилась неплохая статья про вычисление N-ного числа фибоначи за O(log N) арифметических операций. Разумный вопрос, всплывший в комментариях, был: «зачем это может пригодиться на практике». Само по себе вычисление N-ого числа фибоначи может и не очень интересно, однако подход с матрицами, использованный в статье, на практике может применяться для гораздо более широкого круга задач.
В ходе этой статьи мы разберем как написать интерпретатор, который может выполнять простые операции (присвоение, сложение, вычитание и урезанное умножение) над ограниченным количеством переменных с вложенными циклами с произвольным количеством итераций за доли секунды (конечно, если промежуточные значения при вычислениях будут оставаться в разумных пределах). Например, вот такой код, поданный на вход интерпретатору:
Незамедлительно выведет a = 1000000000000000000000000000, b = 500000000000000000000000000500000000000000000000000000, несмотря на то, что если бы программа выполнялась наивно, интерпретатору необходимо было бы выполнить октиллион операций.
В ходе этой статьи мы разберем как написать интерпретатор, который может выполнять простые операции (присвоение, сложение, вычитание и урезанное умножение) над ограниченным количеством переменных с вложенными циклами с произвольным количеством итераций за доли секунды (конечно, если промежуточные значения при вычислениях будут оставаться в разумных пределах). Например, вот такой код, поданный на вход интерпретатору:
loop 1000000000
loop 1000000000
loop 1000000000
a += 1
b += a
end
end
end
end
Незамедлительно выведет a = 1000000000000000000000000000, b = 500000000000000000000000000500000000000000000000000000, несмотря на то, что если бы программа выполнялась наивно, интерпретатору необходимо было бы выполнить октиллион операций.
Ломаем BIOS: включение поддержки виртуализации VT-x на нетбуке Acer Aspire One
7 min
В данной статье мы расскажем вам пошагово о том, как допилить напильником свой нетбук или ноутбук, в котором по какому-то недоразумению выключен и залочен в таком состоянии бит 2 в MSR 0x3A — попросту говоря, у вас есть в процессоре поддержка виртуализации, но она заблокирована биосом.
ПРЕДУПРЕЖДЕНИЕ: всё, описанное в этой статье, рассчитано на то, что вы знаете, что делаете. Всё на свой страх и риск! Если не уверены — не пытайтесь повторить это дома.
Проблема, которую мы будем решать, для конечного пользователя компьютера выглядит так: При использовании гипервизора второго типа (например, VirtualBox)
Вот такое сообщение вы можете видеть при попытке запуска виртуалки с числом процессоров, большим чем 1:
Аналогичное сообщение об ошибке вы также получаете, если собираетесь запускать 64-битную виртуальную машину (например, Debian amd64) с 32-разнядной хост ОС, например WinXP.
На этот вопрос можно ответить, проверив некоторые биты в некоторых словах состояния процессора. Самый простой способ убедиться, что в вашем случае проблема лечится — это посмотреть на то, что показывает программа SecurAble. В моем случае это выглядело так:
Итак, если у вас программа показывает такую же картинку, как показанная выше, то вы можете вылечить эту проблему. Однако нюанс заключается в том, что это установить нужный бит в регистре процессора можно только в БИОСе, поскольку вредный БИОС вашего ноутбука его выставляет в ноль, потом включает блокирующий бит и изменение этого бита более невозможно (до перезагрузки компа, где БИОС во время POST опять его сбросит и залочит).
Биос на нетбуке Acer Aspire производства Insyde, настройки его очень скудны и по F2 естественно мы не можем зайти в программу редактирования настроек БИОСа и включить виртуализацию там. Это было бы слишком просто.
Поэтому, мы будем дизассемблировать БИОС и менять его код, чтобы у нас бит был выставлен в 1. Если готовы, то читаем далее.
ПРЕДУПРЕЖДЕНИЕ: всё, описанное в этой статье, рассчитано на то, что вы знаете, что делаете. Всё на свой страх и риск! Если не уверены — не пытайтесь повторить это дома.
Итак, в чем же проблема?
Проблема, которую мы будем решать, для конечного пользователя компьютера выглядит так: При использовании гипервизора второго типа (например, VirtualBox)
- вы не можете запускать виртуалки с более, чем одним процессором
- вы не можете запускать 64-битные гостевые операционные системы внутри 32-битной хост ОС.
Вот такое сообщение вы можете видеть при попытке запуска виртуалки с числом процессоров, большим чем 1:
Аналогичное сообщение об ошибке вы также получаете, если собираетесь запускать 64-битную виртуальную машину (например, Debian amd64) с 32-разнядной хост ОС, например WinXP.
Можно ли вылечить это?
На этот вопрос можно ответить, проверив некоторые биты в некоторых словах состояния процессора. Самый простой способ убедиться, что в вашем случае проблема лечится — это посмотреть на то, что показывает программа SecurAble. В моем случае это выглядело так:
Итак, если у вас программа показывает такую же картинку, как показанная выше, то вы можете вылечить эту проблему. Однако нюанс заключается в том, что это установить нужный бит в регистре процессора можно только в БИОСе, поскольку вредный БИОС вашего ноутбука его выставляет в ноль, потом включает блокирующий бит и изменение этого бита более невозможно (до перезагрузки компа, где БИОС во время POST опять его сбросит и залочит).
Биос на нетбуке Acer Aspire производства Insyde, настройки его очень скудны и по F2 естественно мы не можем зайти в программу редактирования настроек БИОСа и включить виртуализацию там. Это было бы слишком просто.
Поэтому, мы будем дизассемблировать БИОС и менять его код, чтобы у нас бит был выставлен в 1. Если готовы, то читаем далее.
Уровни для Сокобана
2 min
Во времена XTшек и ДОС был у меня вариант Сокобана, реализованный в виде махонького бинаря, размером менее десяти килобайт. Называлось это чудо pusher.exe и выглядело вот так:
Это был простой уровень, но как насчет вот такого?
Это был простой уровень, но как насчет вот такого?