Проект Kaitai представил (http://kaitai.io/) первый публичный релиз спецификации парсинга произвольных бинарных файлов и инструментария к нему: Kaitai Struct 0.2 (https://github.com/kaitai-io/kaitai_struct). Kaitai Struct предлагается использовать в качестве формального описания любых бинарных форматов.Формат описывается в виде файла .ksy (который представляет собой YAML специального вида), который можно не только использовать в качестве документации, но и сразу же скомпилировать с помощью специального компилятора (ksc). На выходе компилятора — исходные коды библиотеки на одном из поддерживаемых языков, которая автоматически будет выполнять парсинг описанного в .ksy формата. Первый публичный релиз поддерживает Java, JavaScript, Python, Ruby, ожидается поддержка C, C++ и C#.
Заявляется, что сгенерированные таким образом парсеры, как правило, не уступают парсерам, написанным вручную, а зачастую и превосходят их — за счет более корректной обработки исключительных ситуаций, гарантированно корректно реализованной кросс-платформенности, отсутствия человеческого фактора и т.д.
Целевая область применения подобных решений — быстрая разработка кросс-платформенных, кросс-языковых реализаций парсеров бинарных форматов, реверс-инжиниринг бинарных форматов, создание единой базы знаний о применяемых в тех или иных областях знаний бинарных форматах.
Ближайшие аналоги такого подхода — система диссекторов (https://www.wireshark.org/docs/wsdg_html_chunked/ChapterDiss...) в Wireshark, ряд проприетарных hex-редакторов (таких, как 010 Editor (http://www.sweetscape.com/010editor/), Synalysis (http://www.synalysis.net/), Hexinator (https://hexinator.com/)), система шаблонизации в Okteta (https://docs.kde.org/stable5/en/kdesdk/okteta/tools-structur...) (но все они занимаются лишь описанием и визуализацией, а не парсингом как таковым) и ряд библиотек для одиночных языков, например Preon (https://github.com/preon/preon) для Java или jBinary (https://github.com/jDataView/jBinary) для JavaScript.
URL: http://kaitai.io/
Новость: http://www.opennet.me/opennews/art.shtml?num=44226
Это что, теперь для любителей подебажить бинарные форматы совсем не останется работы?!
Останется, конечно — но жизнь можно слегка упростить :)
Все-таки куда удобнее смотреть сначала на дерево в визуализаторе (и править спецификацию формата до получения желаемого) и оперировать уже именованными примитивами - писать "header.field", а не "field = readSomeInteger()", боясь за то, что где-то может съехать какой-нибудь паддинг или что-то такое.
Очередной компилятор компиляторов? Описание формата в БНФ? Чем оно лучше bison?
> Очередной компилятор компиляторов? Описание формата в БНФ? Чем оно лучше bison?Очередной, в какой-то степени. К БНФ и bison оно, тем не менее, отношения почти не имеет. Парсинг всяких текстов (исходников ли, каких-нибудь текстовых форматов разметки), как правило, упирается в то, что один и тот же символ алфавита (буква "a", скажем), может иметь совершенно разную роль в зависимости от контекста - может быть частью литерала, идентификатором, названием тэга, частью ключевого слова и т.д., и этот самый контекст на самом деле весьма нетривиально вычислить. Умные люди для этого придумывают всякие LL-, LR-, LALR- и прочие SLR и т.д. lexx/yacc/bison/т.п. работают как раз в этих парадигмах и львиная доля усилий там тратится именно на то, чтобы понять - вот эта буква "a", что мы только что считали - это вообще что.
Парсинг бинарных форматов гораздо более тупой, с одной стороны, с другой - куда более error-prone. Когда мы читаем очередной байт - мы обычно наверняка уже знаем, что это за поле какой структуры. Почти никогда не бывает, что нам сначала надо прочитать какой-то гигантский кусок, а потом его проинтерпретировать. Проистекает это ровно из построения и применения этих самых форматов - их специально делают такими, чтобы их было удобно читать программно.
Написать на bison парсер бинарного формата вполне возможно, только никому в голову это не придет: это гигантский оверхед, который ничего полезного не даст в итоге. bison разложит все в некую структуру синтаксического дерева, которой потом еще придется выдирать ее неким отдельным преобразованием.
Ну все, postgres, mysql, oracle перейдут на него для хранения данных и... а не, C/C++ пока нету.
> Ну все, postgres, mysql, oracle перейдут на него для хранения данных и...
> а не, C/C++ пока нету.Форматы хранения MyISAM, InnoDB и SQLite, кстати, мы вполне умеем разбирать ;)
И для сборки всего, что его использует будет нужна Java.
> И для сборки всего, что его использует будет нужна Java.Либо JavaScript. Scala умеет компилироваться либо для JVM, либо для JavaScript-машин типа nodejs. Последнее, кстати, запускается радикально быстрее и сильно веселее в целом, если дергать его для десятка форматов из какого-нибудь Makefile, скажем.
Хм, вообще-то нода запускается ни разу не быстро...
> Хм, вообще-то нода запускается ни разу не быстро...У меня получается что-то в районе ~400 ms на один запуск компилятора на JVM и ~160 ms на запуск компилятора под nodejs. Не сверхбыстро, но все же в 2.5 раза быстрее, чем JVM.
У вас какой-то монстр, а не машина :-) с такой скоростью у меня на JVM даже hello world не взлетает, а на ноде - time nodejs -e 'console.log(1)'
даёт 0.4 секунды
> У вас какой-то монстр, а не машина :-) с такой скоростью у
> меня на JVM даже hello world не взлетает, а на ноде
> - time nodejs -e 'console.log(1)'
> даёт 0.4 секундыНоутбук не первой свежести, на средненьком i5. nodejs:
$ time nodejs -e 'console.log(1)'
0,06s user 0,00s system 98% cpu 0,061 totalJVM:
$ echo 'class Main { public static void main(String[] args) { System.out.println(1); }}' >/tmp/Main.java
$ javac /tmp/Main.java
$ time java -cp /tmp Main
0,07s user 0,00s system 112% cpu 0,068 totalКакие 400 ms?
>Последнее, кстати, запускается радикально быстрееБыла какая-то тулза для ускорения многократного запуска программ на Java за счет переиспользования JVM
Бинарный bison...
на Java...
> Бинарный bison...
> на Java...На Scala, на самом деле :)
Ааа, ну это многое объясняет.
Господа! Если время старта/компиляции критично, то можно файлы *.class скормить компилятору gcj (все про него забыли). Получится нативный исполняемый бинарь, который порадует вас не только быстрым стартом, но и шустрым исполнением кода.
> Господа! Если время старта/компиляции критично, то можно файлы *.class скормить компилятору
> gcj (все про него забыли). Получится нативный исполняемый бинарь, который порадует
> вас не только быстрым стартом, но и шустрым исполнением кода.Эм, вы сами пробовали? Нативный бинарь получается размером эдак мегабайт 30-35, JIT в нем отсутствует начисто, внутри по сути примерно такая же виртуальная машина, стартап там тоже мягко говоря небыстрый и сама программа работает, как правило, в несколько раз медленнее того, как она работает в JVM.
Плюс, пардон, когда я последний раз туда смотрел, там не то, что Java 7 не поддерживалась, даже Java 6 местами не была реализована.
Хм, правильно, конечно. Если б ещё было на чём-то человеческом (читай - компилируемом в шустрый бинарь, не требующий VM), а не Scala... Но, в конце концов, ничего идеального не бывает, если сделают выхлоп в виде C и C++ - то, в общем, вполне юзабельно. Да и удачный формат и большая библиотека описаний в таких вещах важнее языка реализации, а здесь, вроде, есть кому эти описания клепать.
> Хм, правильно, конечно. Если б ещё было на чём-то человеческом (читай -
> компилируемом в шустрый бинарь, не требующий VM), а не Scala... Но,
> в конце концов, ничего идеального не бывает, если сделают выхлоп в
> виде C и C++ - то, в общем, вполне юзабельно. Да
> и удачный формат и большая библиотека описаний в таких вещах
> важнее языка реализации, а здесь, вроде, есть кому эти описания клепать.Поддержку C++ мы делаем уже месяц как, но, как выясняется, это несколько сложнее, чем казалось на первый взгляд.
Scala, в целом, на мой взгляд наименьшее зло. В конце концов, никто не мешает оставив ровно тот же формат писать альтернативные компиляторы на любых других языках, генерируя парсеры на любых других языках. Ничего сверхсложного в компиляторе (кроме, пожалуй, парсера выражений, который умеет ограниченно выражения компилировать на все поддерживаемые языки), в конце концов, нет.
Ну и я примерно о том же. Спасибо за интересный инструмент, а нужно ли будет его (и кому) реализовывать на других языках - будет видно.
После RabbitMQ на Erlang стало фиолетово что там внутри готовой прикладухи круться. :)))
Чего и вам желаю!
Не взлетит. Тем более с таким языком разметки, тем более оно не тьюринг-полное ни разу.
> Не взлетит. Тем более с таким языком разметки, тем более оно не
> тьюринг-полное ни разу.Оно с одной стороны и не планируется тьюринг-полное, это по логике своей — DSL, с четко ограниченной областью применения.
> DSLНу так я о том и говорю, что "для парсинга произвольных бинарных файлов" оно непригодно (например, оно не осилит битстрим, в котором встречаются закодированные хаффманом значения). А жаль.
Для парсинга *любого* бинарника нужна машина тюринга. Бинарь частично упакованый gzip или зашифрованый ssl, смогёт?
Прикольная штука, взял на заметку.
Ожидаю сравнения с ASN.1
Не надо с ним сравнивать. С ним вообще связываться не надо - оно не человеческое.
> Ожидаю сравнения с ASN.1ASN.1 можно сравнивать с protobuf или, скажем, как продвинутый вариант bencoded или BSON. Т.е. это все варианты серилизации каких-то структур данных из памяти в поток и обратно, причем сам механизм сериализации фиксированный. KS — это инструментарий для парсинга произвольных потоков. Скажем, PNG-файл или там какие-нибудь пакеты из сетевого трафика.
> Первый публичный релиз поддерживает Java, JavaScript, Python, Ruby, ожидается поддержка C, C++ и C#.Должно быть ровно наоборот.
Как насчет сравнения с BinPac ? https://github.com/bro/binpac/blob/master/README
Присоединяюсь к вопросу. С binpac работать приходилось, отличная штука, которая может и файлы и поток парсить. Какие части декларативно никак не сделать (редко, но бывает) - можно вручную попарсить, есть встроенные в binpac средства для связи с ручным парсером. А если внутри того, что парсишь вручную снова можно декларативно парсить - тоже не проблема, легко и обратно к декларативному парсингу вернуться
> Присоединяюсь к вопросу. С binpac работать приходилось, отличная штука, которая может и
> файлы и поток парсить. Какие части декларативно никак не сделать (редко,
> но бывает) - можно вручную попарсить, есть встроенные в binpac средства
> для связи с ручным парсером. А если внутри того, что парсишь
> вручную снова можно декларативно парсить - тоже не проблема, легко и
> обратно к декларативному парсингу вернутьсяА вот это хороший вопрос :) В целом, да, проекты весьма похожие. Если смотреть на самый верхний уровень, то:
1. binpac на самом деле как бы мертв. Сейчас из этого семейства жив, как подсказали, binpac++ AKA Spicy — http://www.icir.org/hilti/
2. binpac таргетируется ровно на один язык — на C++.
3. Spicy таргетируется даже не на язык, а на промежуточный код платформы clang, соответственно, в теории сможет поддерживать все языки, поддерживаемые clang — но на практике это сейчас и в обозримом будущем, насколько я понимаю, это C / C++ / Objective C / Swift.
4. Все выражения binpac/Spicy — это по сути просто выражения на C / C++ — со всеми плюсами и минусами. Т.е. можно делать что угодно, но из-за этого за рамки C++ без радикальной переделки языка не выйдешь.
5. В binpac все относительно плохо с верификацией, формальной спецификацией и покрытием тестами (де факто ее/его нет). В Spicy — все сильно лучше, но там сам проект пока скорее на стадии ранней альфы.
6. Язык в KS — YAML специального вида, язык в binpac/Spicy — текстовый, C-подобный.Если спуститься ниже, на технический уровень, то:
1. Разумеется, есть ряд концептуальных отличий в применяемых подходах. Например, в KS есть концепция процессинга буферов — можно сказать, что вот здесь внутри этого массива байтов — поток, соответствующий zlib-сжатию. В binpac, насколько я понимаю, все такие вещи делаются исключительно внешними средствами — буфер надо экспортировать в C, позвать zlib, передать обратно вручную.
2. binpac на сейчас, разумеется, гораздо более mature; в KS пока нет, скажем, толком bitfields (но скоро будут), весьма ограниченные аналоги bitpac'овского &check, нет никаких ручек для performance fine-tuning типа bitpac'овского &chunked и т.д. Большей частью это связано с тем, что не хочется гнаться за специализированными фичами, а обеспечить их более-менее хорошую реализацию для всех поддерживаемых языков.
А как на счёт генератора бинарного потока? Или парсер может в обе стороны?Интересуюсь потому что у на есть проект где надо работать с бинарным древним форматом высокой сложности, но нужно не только разбирать данные, но и создавать в бинарном формате.
Было бы приятно описать формат и сгенерить сопутствующие структуры вместо ручного создания всего необходимого.
Генератора пока нет — есть далекоидущая цель сделать это где-нибудь ко второй major версии. По большому счету в декларативном формате эта задача упирается в необходимость (и возможность) символического вывода: например, если где-то объявлено число x, а где-то есть строка str длиной (2 * x + 3), т.е. str.length = 2 * x + 3. Значит, при записи нужно развернуть формулу и записывать x = (str.length - 3) / 2. И, внезапно, иногда решений может вообще не быть, а иногда их может быть бесконечно много.
Подхватываете флаг преона? великое дело, имхо
от преона не забудьте взять легкую расширяемость - всех извращений не предусмотришь.
для бигдаты было бы полезно простую интеграцию в виде преобразования в avro, например. прекрасно те же cdr разбирать. там за такой разбор с медиейшеном платят ой как много.
> Подхватываете флаг преона? великое дело, имхо
> от преона не забудьте взять легкую расширяемость - всех извращений не предусмотришь.Тут в какой-то степени двоякая ситуация. С одной стороны — никто не запрещает в императивном уже режиме из языка дергать парсеры как угодно и комбинировать их результаты. Это по сути примерно то же самое, что есть в Preon — и это все можно, но (1) оно будет привязано к одному конкретному языку, (2) это императивно, а не декларативно.
С другой стороны — по идее нужна какая-то более гибкая расширяемость, но оставаясь в декларативных рамках. Очень много что дают value instances (по сути внутри там — некий язык выражений, который гарантированно компилируется в соответствующее выражение на Java/JS/Python/Ruby), но они тоже не панацея, плюс они решают только задачу чтения (бинарник => классы), но не записи (классы => бинарник). Нужно придумывать что-то еще.
> для бигдаты было бы полезно простую интеграцию в виде преобразования в avro,
> например.Avro — в смысле, с генерируемых классах сразу Avro-аннотации генерировать, как-то так?
> прекрасно те же cdr разбирать. там за такой разбор с
> медиейшеном платят ой как много.CDR — имеются в виду всякие логи сотовых операторов и прочая биллинг-ориентированная тематика?
> Avro — в смысле, с генерируемых классах сразу Avro-аннотации генерировать, как-то
> так?В идеале + код. Если говорим о Hadoop семействе, то оптимально - InputFormat c выходом Avro объектов. Кроме самого Hadoop-а это практически автоматом даст интеграцию с Spark и Hive
> CDR — имеются в виду всякие логи сотовых операторов и прочая биллинг-ориентированная
> тематика?Сырые логи с оборудования. Навскидку http://bill-parser.googlecode.com/svn/trunk/doc/CDR_Descript...
При этом CDR - это вершина айсберга. Там еще траффик, технические логи итд
ну и дела:
seq:
- id: image_width
type: u2
- id: image_height
type: u2
- id: flags
type: u1
- id: bg_color_index
type: u1
- id: pixel_aspect_ratio
type: u1не лучше ли как-нибудь так:
seq
u16 image_width
u16 image_height
u8 flags
u8 bg_color_index
u8 pixel_aspect_ratio
первый вариант - валидный YAML, второй - очередной нескучный велосипед.
Можно было и валиндный yaml:seq:
image_width: u2
image_height: u2
flags: u1
bg_color_index: u1
pixel_aspect_ratio: u1только это не расширяемо.
> Можно было и валиндный yaml:
> seq:
> image_width: u2
> image_height: u2
> flags: u1
> bg_color_index: u1
> pixel_aspect_ratio: u1
> только это не расширяемо.Главная проблема здесь в том, что у вас получился map под названием seq, в котором порядок элементов не определен. А нам он важен, т.к. нам их надо парсить именно в определенной последовательности.
В этом и преимущество велосипедных DSL - больше возможности для краткости.