Disclaimer. Данный цикл начинался в виде статей для журнала Sync Re-Started (SRS). Первая статья была опубликована в #5 в начале 2013 года. Вторая статья должна была попасть в #6, но scalesmann разрешил ее опубликовать пока не завоняла. Текст приводится по возможности без изменений (исправленные опечатки не в счет).

Другие статьи цикла:

1. Анализ форматов
2. Быстрая эмуляция AY/YM

Быстрый поиск в произвольных данных

Предисловие

Данная статья является небольшой зарисовкой на тему разработки ПО, алгоритмов и поиска решения задачи. Текстов программ (особенно на ассемблере) не будет, только маленькие кусочки псевдокода для пояснений. Задача решалась в рамках проекта ZXTune.

Суть задачи.

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

1. Простое решение.

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

#сканируем память по определенному адресу с определенной длиной
ScanData(dataStart, dataSize) : void
  #искать до самого конца бессмысленно
  #определяем минимальный размер данных для сканирования
  for cursor in 0..dataSize-MIN_SCAN_SIZE
    windowStart = dataStart + cursor
    windowSize = dataSize - cursor
    result_size = CheckFormats(windowStart, windowSize)
    if result_size != 0
      cursor = cursor + result_size
    else
      #неудача, делаем следующий шаг
      cursor = cursor + SCAN_STEP

#проверяем блок памяти всеми детекторами
CheckFormats(dataStart, dataSize) : integer
  for plugin in AllRegisteredPlugins
    result_size = plugin.Check(dataStart, dataSize)
    if result_size != 0
      return result_size
  return 0

Все понятно и очевидно. Смущает разве что линейно падающая скорость поиска при добавлении новых детекторов.
Такой алгоритм используется в риппере AYEmul. 13 поддерживаемых форматов одной категории (музыкальные модули) дают скорость поиска от 64кб/с до 1.3Мб/с в зависимости от включенности ресурсоемкого поиска Flash Tracker’a.

2. Описываем формат данными

Если посмотреть на код метода Check любого из плагинов, то станет заметно, что многие проверки являются проверками на равенство какого-либо байта по определенному смещению некоему значению. Именно такое наблюдение сделал в свое время Himik/ZxZ, описавший способ быстрой проверки соответствия формата по таблице. Таблица должна содержать последовательность кодов, часть из которых используется непосредственно для сравнения при проверке, часть из которых используется для управления курсором, выполняющим сравнение (пропустить байт, пропустить 2 байта и т.п.). Теперь каждый из методов Check разбился на две части- в первой вызывается некая общая функция проверки куска памяти на предмет соответствия формату, описание которого хранилось в таблице и передавалось в качестве аргумента, а во второй выполняется более детальная (и, соответственно, тяжелая) проверка.
Такой алгоритм используется в риппере Pusher. Более детальное описание приведено в статье “Автоопределение музыкальных форматов” ZX-Guide#4.5

3. Делаем описание более гибким

Как было замечено тем же Himik’ом, упомянутый выше способ подходил для детектирования разве что плееров, код которых содержал стабильные цепочки байт. Непосредственно для модулей такой метод не подходил — редко какой формат музыки содержит четкую сигнатуру. Да и ту разные кулхацкеры затирали в тщетных попытках спрятать свое творение от глаза более прозорливого кулхацкера:) На помощь приходит усложнение описания формата: помимо простейших предикатов (равенство определенному значению и равенство любому значению) необходимо вводить более сложные. Таковыми могут быть: принадлежность диапазону (наиболее очевидный предикат), битовые маски (некоторые биты байтов на определенных позициях могут быть одинаковыми в разных модулях), кратность какому-либо значению (если значение было степенью двойки, то этот случай покрывался битовой маской) и логические операции сочетаний вышеперечисленных предикатов. Теперь в полный рост встает проблема описания таких вот сложных форматов. Используемое на предыдущем этапе бинарное кодирование описания, напрямую интерпретируемое при проверке, кроме компактного представления (имеющего ценность разве что на реальном ZX Spectrum’e) и быстрой (по сравнению с первым методом) работой никаких достоинств не имеет, а крайне низкая сопровождаемость перечеркивает плюсы. Отсюда следует весьма простое следствие: описание формата должно быть в понятном человеку формате:

fb - байт в данной позиции должен быть равен 0xfb
0x - байт в данной позиции должен иметь нулевую старшую тетраду при произвольной младшей
? - любой байт
00-02 - байт может иметь значение от 0 до 2 включительно
%11xxxx00 - байт имеет 2 установленных старших бита и 2 сброшенных младших при произвольных остальных
*3 - байт должен быть кратен 3
'A - символ “A”

Например, описание формата для ASC Sound Master v1.x в подобной нотации:

#начальная скорость. Значение в диапазоне от 3 до 50
03-32
#позиция зацикливания. Значение в диапазоне от 0 до 99
00-63
#смещение таблицы паттернов.
#LE машинное слово с нулевым значением старшего байта
0a-ac 00
#смещение таблицы семплов.
#LE машинное слово со старшим байтом в определенном диапазоне
? 00-35
#смещение таблицы орнаментов. Аналогично
? 00-37
#количество позиций. Значение в диапазоне от 1 до 100
01-64
#первая позиция из списка. Значение в дипазоне от 0 до 31
00-1f

Описание формата для упакованных Hrust2.1 блоков:

#сигнатура
'h'r'2
#поле флага/версии- установленный старший бит означает отсутствие компрессии
%x0110001

Описание формата для архивов типа LHA:

#поле размера- любые 2 байта
??
#метод сжатия - 5 символов
'-('l|'p)('z|'h|'m)('s|'d|'0-'7)'-
#прочие атрибуты- любые 12 байт
?{12}
#атрибуты - старшие 2 бита равны 0
%00xxxxxx
#уровень от 0 до 3
00-03

Лирическое отступление. Такой вот (псевдо)язык для описания какой-либо узкоспециализированной задачи в умных книгах называется DSL — Domain-Specific Language (предметно-ориентированный язык). В данном случае, предметной областью является формат бинарных данных.

4. В погоне за ускорением. Первый шаг..

После введения текстового описания, качество детектирования резко возросло (одно дело найти ошибку в километрах проверок в коде, совсем другое- в небольшой строке), но сильно упала скорость. Профилирование показало узкое место- интерпретация текстового представления формата при проверке его соответствия. Очевидный шаг — компиляция текстового представления в более понятное машине бинарное. Как и в случае системы плагинов, призовем на помощь ООП. Псевдокод:

interface Format
  Check(memStart, memSize) : bool

CreateFormat(text) : Format

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

5. Поворотный момент. Все гениальное- просто!

Полученное на предыдущем шаге ускорение сканирования примерно на 30% не только придало бодрость духа, но и открыло путь к следующей, ключевой оптимизации.
Если внимательно посмотреть на алгоритм сканирования, то можно предположить, что бОльшая часть проверок является лишней. Предположим, мы ищем данные, всегда начинающиеся с цепочки байт 0x01,0x02,0x03,0x04. Для чего же тогда постоянно звать хоть и облегченный, но все еще довольно тяжеловесный детектор для данных, априори не подходящих под данный критерий (например, последовательность нулей)? Финт ушами, и в интерфейс добавляется маленькая, но мощная функция:

interface Format
  Check(memStart, memSize) : bool
  Search(memStart, memSize) : integer

Суть этой функции проста и может быть литературно описана так: “скажи, когда тебя позвать в следующий раз для проверки?”. Т.е. возвращает смещение от memStart, на котором имеет смысл делать детальные проверки. Ну или вернет memSize для индикации того, что в данном блоке памяти больше искать нечего и можно вообще данный детектор больше не звать.
Разумеется, функция сканирования, вызывающая плагины, изрядно усложнилась- для каждого плагина теперь требуется хранить смещение, начиная с которого его имеет смысл вызывать:

ScanData(dataStart, dataSize) : void
  #ассоциируем каждый плагин со смещением, начиная с которого можно проверять
  ScanStatus : AssocMap[ Plugin => offset ]
  #инициализация- вначале можно проверять все- нулевое смещение
  for plugin in AllRegisteredPlugins
    ScanStatus[plugin] = 0
  #главный цикл сканирования
  for cursor in 0..dataSize - MIN_SCAN_SIZE
    #перебираем ассоциативный массив
    for pair in ScanStatus
      #если формат за пределами видимости, пропускаем
          if pair.Offset > cursor
        continue
      windowStart = dataStart + cursor
      windowSize = dataSize - cursor
      nextMatch = pair.Plugin.Format.Search(windowStart, windowSize)
      #быстрая проверка и детальный анализ
      if 0 == nextMatch and pair.Plugin.Check(windowStart, windowSize)
        #найдено- пропускаем обнаруженный блок
        cursor += result_size
        #и заново проверяем все плагины
        break
      #не найдено, в следующий раз проверим через nextMatch байт
      pair.Offset = cursor + nextMatch
    #переходим сразу к ближайшему плагину- пропускаем неопознанные данные
    cursor = cursor + min(ScanStatus.Offsets)

Остается самый интересный вопрос: что внутри метода Search? Ответ напрашивается банальный- поиск. Реализация “в лоб” — наивный алгоритм поиска за O(nm):

Search(dataStart, dataSize) : integer
  #образец больше блока данных- пропускаем все
  if dataSize < PatternSize
    return dataSize
  #окно поиска
  for cursor in 0..dataSize-PatternSize
    #применяем поочередно предикаты к соответствующим байтам окна
    for idx in 0..PatternSize
      #несоответствие- прекращаем поиск и сдвигаем окно
      if !Pattern[idx].Match(dataStart[cursor + idx])
        break;
    #если дошли до конца образца- значит нашли соответствие
    if idx != PatternSize
      return cursor
  return dataSize

Pattern и PatternSize — соответственно, массив предикатов и его размер.
Прозорливый читатель может заметить, что в коде выше вызов Check — лишний. Это оставлено специально для бОльшей наглядности описания.

6. Новый виток оптимизации.

Полученное на предыдущем этапе ускорение в 3 раза — не предел. Как несложно догадаться, улучшения будут касаться алгоритма поиска. Эту задачу, в общем случае, можно свести к задаче поиска подстроки в строке. А значит, воспользоваться весьма богатым инструментарием алгоритмов, разработанных для этой цели. Есть только одно “но”: поиск нечеткий, поэтому далеко не все алгоритмы подойдут. Мне удалось адаптировать для этой цели алгоритм Бойера-Мура. Его турбо-версия по каким-то причинам не подошла (сейчас уже не помню по каким). Поскольку объяснять суть работы алгоритма в формате данной статьи весьма сложно, а результат все равно будет непонятен, я этого делать не буду:) Если кто заинтересуется, с удовольствием объясню все на примере конкретного кода и статей, по которым я сам все изучал. Скажу лишь одно- конечный (на данный момент) вариант быстрее первоначального в 3..4 раза. Точная цифра неизвестна, ибо имеется статистика только общего времени поиска на эталонных данных, а число детекторов постоянно увеличивается. Например, самая первая версия использовала 25 детекторов и тратила на обработку эталонных тестовых данных 32 минуты. На момент написания статьи (октябрь-декабрь 2012, прим.ред), используется 72 детектора и тратится 11 минут (скорость поиска около 2Мб/с). И это все притом, что объем анализируемых данных с тех пор увеличился за счет новых плагинов для сжатых блоков и архивов, результат распаковки которых также анализируется.
Скорость работы не так сильно зависит от количества детекторов, как от их качества. Более того, добавление новых высококачественных детекторов может ускорить поиск, ибо не будет тратиться время на анализ данных. Качеством детектора назовем величину, обратно зависящую вероятности срабатывания на произвольных данных (логарифм по основанию 2 от соотношения общего числа комбинаций входных значений к сработавшим комбинациям — это позволит вместо длинной арифметики и делений-умножений обойтись логарифмами и сложениями-вычитаниями).
Например, для вышеприведенных примеров.
ASC Sound Master 1.x:
длина образца: 10 символов (80 бит)
варианты для каждого символа образца: 48,100,163,1,256,54,256,56,100,32
показатель качества: 80-(сумма всех log2 для каждого числа вариантов равна ~59)=~21
Hrust2:
длина образца: 4 символа (32 бита)
варианты для каждого символа образца: 1,1,1,2
показатель качества: 32-0-0-0-1=31
LHA:
длина образца: 21 символ (168 бит)
варианты для каждого символа образца: 256,256,1,2,3,10,1,12x256,64,4
показатель качества: 168-8-8-0-1-1.585-3.322-0-12x8-6-2 = ~42

Можно заметить, что формат LHA является наиболее качественным, за ним, несмотря на простоту, следует формат Hrust2, а ASC Sound Master обладает самым низкокачественным форматом. Данный эмпирический вывод вполне себе подтверждается замерами в боевых условиях- эффективности детекторов получились 57% (ASC), 99% (Hrust2) и 100% (LHA) соответственно (соотношение “правильных” срабатываний детектора к общему числу срабатываний).
Помимо качества, на скорость поиска (хотя и в меньшей степени) оказывает влияние размер образца (чем длиннее, тем лучше) и его периодичность (особенности алгоритма Бойера-Мура, использующего поиск суффиксов образца).

7. Что дальше?

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

Заключение.

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