Зачем мне MDX
Я делаю читалку для Android.
Дошёл до офлайн-словарей. Форматов два ходовых, StarDict и MDX, делал сразу оба. StarDict хорошо задокументирован, с ним просто. MDX это формат словарей MDict, и с ним тоньше.
Сразу оговорюсь, чтобы не было ложного пафоса. Сам формат я не реверсил. MDX проприетарный, официальной спеки от создателей нет, но сообщество разобрало его давным-давно, есть подробное описание всех секций (спека writemdict). Я взял это описание и написал по нему свою реализацию. Работа была не «вскрыть секрет», а аккуратно реализовать чужое описание, включая ту часть, где начинается крипта.
Почему не готовые библиотеки. Java-парсеры под MDX есть, mdict4j и eb4j. Оба под GPL. Мне не подходит, лицензия обязала бы открыть код всей читалки. Плюс я специально держу приложение без внешних зависимостей. Значит, пишу свой парсер с нуля.
Дальше про то, как устроен формат, где я споткнулся, и почему пришлось руками писать RIPEMD-128.
Три секции
Файл MDX это три секции подряд.
Header. Четыре байта длины, дальше XML-строка в UTF-16LE с атрибутами словаря, дальше контрольная сумма ADLER32. Мне из атрибутов нужны версия движка, кодировка статей, формат разметки и флаг шифрования.
Keyword-секция. Блок метаданных, потом keyword index, потом keyword-блоки. Index это оглавление. Для каждого блока в нём записано число слов, первое и последнее слово, размеры блока в сжатом и распакованном виде.
Record-секция. Устроена так же, метаданные плюс таблица размеров, потом блоки со статьями.
Важное свойство. MDX умеет random access из коробки. Весь файл распаковывать не надо. В памяти я держу только index, то есть границы блоков. Пользователь ищет слово, я по границам нахожу нужный блок, распаковываю ровно его, обычно десятки килобайт, и читаю статью. У StarDict весь индекс висит в памяти, тут экономнее.
Сжатие
Каждый блок сжат отдельно, тип сжатия лежит в первых четырёх байтах. Ноль без сжатия, единица LZO, двойка zlib. Дальше ADLER32 распакованных данных и сами данные.
zlib берётся из JDK через Inflater, тут всё просто. LZO я не поддержал специально. Приличный Java-порт LZO снова под GPL, тащить нельзя. На практике не потеря, современные словари жмутся zlib, LZO это совсем старое. Контрольную сумму проверяю всегда. Словари от самодельных конвертеров любят нарушать спеку по мелочам, лучше упасть с понятной ошибкой, чем отдать пользователю кашу.
Шифрование
Взял два реальных словаря для проверки, Oxford Dictionary of English и Cambridge. Оба оказались зашифрованными, и это не совпадение, так сделана добрая половина словарей.
Шифрование в MDX задаётся битами в атрибуте Encrypted. Бит 0 шифрует сорокабайтовый заголовок keyword-секции алгоритмом Salsa20/8, ключ там завязан на регистрационный код словаря. Это я не трогаю, без ключа покупки не прочитать. Бит 1 шифрует сам keyword index, вот он встречается сплошь и рядом, защита от честных людей. Оба моих боевых словаря были именно с ним.
Устроено так. Index шифруется нибл-свопом и XOR по позиции и ключу, а ключ считается как RIPEMD-128 от контрольной суммы блока с солью. То есть чтобы прочитать даже оглавление словаря, нужен RIPEMD-128.
В стандартной библиотеке его нет, а тянуть Bouncy Castle ради одной хеш-функции глупо, когда приложение специально без зависимостей. Написал RIPEMD-128 руками по спеке, около сотни строк с таблицами сдвигов и раундовыми функциями.
С тестами вышел неловкий момент. Прогнал реализацию на официальных тест-векторах, один не сошёлся. Полез искать баг в раундах, готовый признать, что напортачил. Оказалось, я вбил в сам тест неправильное эталонное значение, а код считал верно с самого начала.
Грабля с сортировкой
По спеке блоки в index отсортированы, и нужный блок положено искать бинарным поиском. Меня уже учил StarDict. Правила сортировки у разных конвертеров разъезжаются, регистр, локаль, и бинарный поиск промахивается мимо слова, которое в словаре есть.
Поэтому бинарный поиск по блокам я не делаю. Блоков в реальном словаре максимум тысячи, границы и так лежат в памяти. Линейно прохожу по ним и сравниваю нормализованные границы, нижний регистр плюс обрезка пробелов. Это доли миллисекунды, зато сортировка конвертера меня уже не обманет.
Редиректы
Без этого словарь наполовину мёртвый. Часть статей это не текст, а редирект вида @@@LINK=слово. Так сделаны словоформы. Ищешь «colour», внутри редирект на «color». В самой спеке формата этого нет, это соглашение внутри текста статей, но встречается массово. Иду по редиректам с ограничением глубины и защитой от циклов, чтобы пара словарей со ссылками друг на друга по кругу не завесила поиск.
Итог
Парсер вышел под 400 строк на Kotlin, ноль новых зависимостей. MDX версии 2.0, сжатие zlib, кодировки UTF-8, UTF-16, GBK, Big5, шифрованный индекс, редиректы. LZO, третью версию формата и RegCode отклоняю с понятной ошибкой. Проверял на синтетических файлах по спеке и на боевых словарях.
Замеры. Oxford, 78 мегабайт, 243 тысячи слов. Cambridge, 24 мегабайта, 68 тысяч. Загрузка индекса и первый поиск от 20 до 270 миллисекунд, дальше поиск слова от 1 до 27 миллисекунд. По памяти почти ноль сверх файла, в куче только границы блоков.
Честное ограничение одно. Статьи в MDX это HTML, а показываю я их плоским текстом. Oxford так читается отлично, Cambridge с таблицами форм глагола местами слипается. Осознанный размен.
Вывод простой. Формат проприетарный, но не мистический, сообщество его давно расписало. Ничего героического я не сделал, просто реализовал описание сам, без GPL-библиотеки и без внешних зависимостей, а самой интересной частью оказалась крипта руками. Читалка называется MRead, лежит на GitHub, 4PDA и в RuStore. Дев-дневник и обратная связь у меня в телеге.
ссылка на оригинал статьи https://habr.com/ru/articles/1055436/