• Волновой метод построения цветовой гаммы

    image


    Привет, Хабр!


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


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

    Читать дальше →
  • Ускоряем неускоряемое или знакомимся с SIMD

      Есть класс задач, которые нельзя ускорить за счёт оптимизации алгоритмов, а ускорить надо. В этой практически тупиковой ситуации к нам на помощь приходят разработчики процессоров, которые сделали команды, позволяющие выполнять операции на большим количеством данных за одну операцию. В случае x86 процессоров это инструкции сделанные в расширениях MMX, SSE, SSE2, SSE3, SSE4, SSE4.1, SSE4.2, AVX, AVX2, AVX512.

      В качестве «подопытного кролика» я взял следующую задачу:
      Есть неупорядоченный массив 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»

      • Translation
      Недавно я начал разбираться с рендерингом «Ведьмака 3». В этой игре есть потрясающие приёмы рендеринга. Кроме того, она великолепна с точки зрения сюжета/музыки/геймплея.



      В этой статье я расскажу о решениях, использованных для рендеринга The Witcher 3. Она не будет такой всеобъемлющей, как анализ графики GTA V Адриана Корреже, по крайней мере, пока.

      Мы начнём с реверс-инжиниринга тональной коррекции.
      Читать дальше →
    • Мастер-класс «Почему Стив Джобс любил шрифты» (Алексей Каптерев)

      • Tutorial


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




      Шутка, написанная гарнитурой Times, на 10 % смешнее той, что написана гарнитурой Arial. Почему? Чёрт знает. Лучшее объяснение, которое я видел: юмор ассоциируется с агрессией, с остротой, с остроумием — а Times выглядит более острым, чем Arial.


      Ещё один любопытный эксперимент, в котором участвовало 45 тыс. человек. Заходишь на сайт, тебе показывают статью Дэвида Дойча, британского физика. В статье автор пишет, что сегодня очень трудно внезапно умереть. Например, от инфекционного заболевания или в уличной драке. Лет сто назад это случалось намного чаще. Главный вывод статьи — сейчас мир безопасен как никогда. В среднем, конечно, ведь где-то постоянно идут локальные военные конфликты.

      Читать дальше →
    • Стоимость операций в тактах ЦП

      • Translation
      Всем доброго! Вот мы и добрались до тематики С++ на наших курсах и по нашей старой доброй традиции делимся тем, что мы нашли достаточно интересным при подготовке программы и то, что будем затрагивать во время обучения.

      Инфографика:



      Когда нам нужно оптимизировать код, мы должны отпрофилировать его и упростить. Однако, иногда имеет смысл просто узнать приблизительную стоимость некоторых популярных операций, чтобы не делать с самого начала неэффективных вещей (и, надеюсь, не профилировать программу позже).
      Читать дальше →
    • Реверс-инжиниринг игры Lost Vikings

      • Translation
      После интересной обратной разработки игрового движка Comprehend (см. Recomprehend) я подбирал новый проект для реверс-инжиниринга игры под DOS. За долгие годы разные люди реверсировали множество старых популярных игр и опубликовали для них спецификации и инструменты. Например, на сайте shikadi.net есть куча информации об играх, в которые я играл в детстве.

      Я обнаружил, что для реверс-инжиниринга игры The Lost Vikings компании Blizzard (тогда она называлась Silicon and Synapse), похоже, не предпринималось никаких серьёзных попыток. Игра была выпущена в 1993 году, на закате эры DOS, и очень нравилась мне в юности. The Lost Vikings — это головоломка-платформер, в которой игрок управляет тремя викингами, каждый из которых имеет собственные умения. Викингам нужно объединить свои силы для решения загадок и прохождения уровней с различной тематикой: космический корабль, доисторический мир, Древний Египет. На изображении ниже показан первый уровень игры (источник: Strategy Wiki):

      image

      Казалось, что эту игру разобрать будет довольно просто. Уровни основаны на тайловых картах и содержат простые загадки: кнопки, включающие и отключающие объекты, передвижные ящики и поднимающий предметы кран. И на самом деле, бóльшая часть проекта по обратной разработке была достаточно прямолинейной. У игры есть один пакетный файл данных, содержащий сжатые блоки файлов. Блоки кодируют различные ресурсы игры, такие как спрайты, карты, звуки и т.д. Я написал несколько утилит, которые можно использовать для просмотра ресурсов игры: The Lost Vikings Tools.
      Читать дальше →
    • Задача с погрешностью и переполнением

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

        Суть задачи заключалась в следующем. Есть некое устройство (микроконтроллер), которое умеет обращаться только с 32-битными целыми значениями и не умеет работать с плавающей запятой.
        На таком аппарате есть таймер, который в секунду генерирует 32768 тиков. Необходимо написать функцию, переводящую тики в миллисекунды без потери точности (желательно с округлением).
        Читать дальше →
      • Правда о PCM компании Numonyx: революция, которой не случилось

          Анекдот вместо предисловия:
          — Вы слышали, Иванов выиграл в лотерею «Волгу».
          — Вообще-то не Иванов, а Рабинович, не «Волгу», а сто рублей, не в лотерею, а в преферанс, и не выиграл, а проиграл.


          На днях на Хабре появилась ссылка на сногсшибательную новость: в технологии производства памяти произошла революция, и скоро у нас будет единая память супер-пупер память на основе халькогенидных материалов, использующая фазовые переходы, вызванные нагревом при пропускании через ячейку электрического тока. Работает быстро как DRAM, да еще и энергонезависимая, как Flash.

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

          На вполне резонный вопрос с галерки: «А ты собсно кто такой, чтобы нам твою якобы правду слушать?» могу ответить, что я работаю отделе разработки компании-производителя памяти (в том числе и PCM) и по долгу службы «держу руку на пульсе».
          Читать дальше →
        • Типографская раскладка в линуксе

            xkeyboard-config с версии 1.5 содержит дополнительный уровень с полезными юникодными символами, который можно прилепить к любой раскладке. Собственно, я поучаствовал в процессе его добавления туда. Этот набор символов был написан несколько лет назад под впечатлением от раскладки Ильи Бирмана, потом постоянно переделывался и стабилизировался.
            Читать дальше →
          • Автоматическая оптимизация алгоритмов с помощью быстрого возведения матриц в степень

              Пусть мы хотим вычислить десятимиллионное число Фибоначчи программой на Python. Функция, использующая тривиальный алгоритм, на моём компьютере будет производить вычисления более 25 минут. Но если применить к функции специальный оптимизирующий декоратор, функция вычислит ответ всего за 18 секунд (в 85 раз быстрее):


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

              Эта статья расскажет о том, в каких случаях и каким образом декоратору удаётся делать подобные оптимизации. Также вы сможете сами скачать и протестировать библиотеку cpmoptimize, содержащую данный декоратор.
              Читать дальше →
            • Секреты тернарного оператора

                Каждый уважающий себя программист С\С++ знает что такое тернарный оператор и большинство использовало его хотя бы раз в своих программах. Но знаете ли вы все секреты тернарного оператора? Какие потенциальные опасности сопряжены с его использованием и какие, казалось бы не связанные с его прямым предназначением, возможности в нем таятся? Эта статья дает вам возможность проверить свои знания и, возможно, узнать что-то новое.
                Читать дальше →
              • Android компонент с нуля

                Всем привет! Создание собственных компонентов интерфейса часто является необходимостью чтобы выделиться из общей массы похожих программ. В этой статье как раз рассматривается создание простого, нестандартного компонента на примере кнопки-таймера.
                Читать дальше →
              • Теория относительности в картинках

                • Tutorial
                В своей статье я хотел бы рассказать о теории относительности. Эта теория не требуется в представлении. С самого своего создания она была окутана ореолом тайны, поскольку полностью подрывает наши привычные представления о пространстве и времени. Все мы в школе учили формулы теории относительности, но мало кто действительно понимал их. И это не удивительно, ведь человеку, чтобы по-настоящему понять какую-то теорию во всей её красоте, полноте и непротиворечивости, не достаточно знать формулы. Нужно иметь какой-то визуальный ориентир, нужна динамика, чтобы было что-то, что можно повертеть в руках. Я решил восполнить этот пробел и написал небольшую программку, в которой можно «повертеть в руках» пространство-время. Мы, как настоящие исследователи, с помощью небольших экспериментов попытаемся выяснить основные свойства этой загадочной материи.
                Под катом много картинок (и ни одной формулы).
                Читать дальше →
              • Используем быстрое возведение матриц в степень для написания очень быстрого интерпретатора простого языка программирования

                Недавно на хабре появилась неплохая статья про вычисление N-ного числа фибоначи за O(log N) арифметических операций. Разумный вопрос, всплывший в комментариях, был: «зачем это может пригодиться на практике». Само по себе вычисление N-ого числа фибоначи может и не очень интересно, однако подход с матрицами, использованный в статье, на практике может применяться для гораздо более широкого круга задач.

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

                loop 1000000000
                  loop 1000000000
                    loop 1000000000
                      a += 1
                      b += a
                    end
                  end
                end
                end
                


                Незамедлительно выведет a = 1000000000000000000000000000, b = 500000000000000000000000000500000000000000000000000000, несмотря на то, что если бы программа выполнялась наивно, интерпретатору необходимо было бы выполнить октиллион операций.
                Читать дальше →
              • Ломаем BIOS: включение поддержки виртуализации VT-x на нетбуке Acer Aspire One

                  В данной статье мы расскажем вам пошагово о том, как допилить напильником свой нетбук или ноутбук, в котором по какому-то недоразумению выключен и залочен в таком состоянии бит 2 в MSR 0x3A — попросту говоря, у вас есть в процессоре поддержка виртуализации, но она заблокирована биосом.

                  ПРЕДУПРЕЖДЕНИЕ: всё, описанное в этой статье, рассчитано на то, что вы знаете, что делаете. Всё на свой страх и риск! Если не уверены — не пытайтесь повторить это дома.

                  Итак, в чем же проблема?


                  Проблема, которую мы будем решать, для конечного пользователя компьютера выглядит так: При использовании гипервизора второго типа (например, VirtualBox)
                  • вы не можете запускать виртуалки с более, чем одним процессором
                  • вы не можете запускать 64-битные гостевые операционные системы внутри 32-битной хост ОС.


                  Вот такое сообщение вы можете видеть при попытке запуска виртуалки с числом процессоров, большим чем 1:
                  image

                  Аналогичное сообщение об ошибке вы также получаете, если собираетесь запускать 64-битную виртуальную машину (например, Debian amd64) с 32-разнядной хост ОС, например WinXP.

                  Можно ли вылечить это?


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

                  Итак, если у вас программа показывает такую же картинку, как показанная выше, то вы можете вылечить эту проблему. Однако нюанс заключается в том, что это установить нужный бит в регистре процессора можно только в БИОСе, поскольку вредный БИОС вашего ноутбука его выставляет в ноль, потом включает блокирующий бит и изменение этого бита более невозможно (до перезагрузки компа, где БИОС во время POST опять его сбросит и залочит).

                  Биос на нетбуке Acer Aspire производства Insyde, настройки его очень скудны и по F2 естественно мы не можем зайти в программу редактирования настроек БИОСа и включить виртуализацию там. Это было бы слишком просто.

                  Поэтому, мы будем дизассемблировать БИОС и менять его код, чтобы у нас бит был выставлен в 1. Если готовы, то читаем далее.
                  Читать дальше →
                • Уровни для Сокобана

                    Во времена XTшек и ДОС был у меня вариант Сокобана, реализованный в виде махонького бинаря, размером менее десяти килобайт. Называлось это чудо pusher.exe и выглядело вот так:



                    Это был простой уровень, но как насчет вот такого?
                    Читать дальше →
                  • Детектор границ Канни

                    Доброго времени суток!

                    Последнее время, на Хабре часто стал упоминаться алгоритм выделения границ Канни (который, к моему удивлению, переводится дословно: хитрый). Итак, я созрел поделиться с общественностью своим опытом реализации этого детектора.
                    Читать дальше →
                  • M for Mice

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

                    Experimental set


                    Вечером в четверг я отлаживал небольшую программку для контроллера: состояние аналоговых джойстиков пересылалось с отладочной платы по УАРТ в комп. Компы нынче КОМ-портами оснащают редко, поэтому я работал через переходник USB-COM. Я пытался понять, почему столбик данных в Comport Toolkit приходит неровным, когда мои размышления были грубо прерваны Синим Экраном Смерти.
                    Читать дальше →