URL: https://www.opennet.me/cgi-bin/openforum/vsluhboard.cgi
Форум: vsluhforumID3
Нить номер: 107525
[ Назад ]

Исходное сообщение
"Декларативная спецификация парсинга бинарных файлов Kaitai S..."

Отправлено opennews , 12-Апр-16 18:45 
Проект 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


Содержание

Сообщения в этом обсуждении
"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено ferux , 12-Апр-16 18:45 
Это что, теперь для любителей подебажить бинарные форматы совсем не останется работы?!

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 12-Апр-16 19:15 
Останется, конечно — но жизнь можно слегка упростить :)
Все-таки куда удобнее смотреть сначала на дерево в визуализаторе (и править спецификацию формата до получения желаемого) и оперировать уже именованными примитивами - писать "header.field", а не "field = readSomeInteger()", боясь за то, что где-то может съехать какой-нибудь паддинг или что-то такое.

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Аноним , 12-Апр-16 18:56 
Очередной компилятор компиляторов? Описание формата в БНФ? Чем оно лучше bison?

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 12-Апр-16 19:26 
> Очередной компилятор компиляторов? Описание формата в БНФ? Чем оно лучше bison?

Очередной, в какой-то степени. К БНФ и bison оно, тем не менее, отношения почти не имеет. Парсинг всяких текстов (исходников ли, каких-нибудь текстовых форматов разметки), как правило, упирается в то, что один и тот же символ алфавита (буква "a", скажем), может иметь совершенно разную роль в зависимости от контекста - может быть частью литерала, идентификатором, названием тэга, частью ключевого слова и т.д., и этот самый контекст на самом деле весьма нетривиально вычислить. Умные люди для этого придумывают всякие LL-, LR-, LALR- и прочие SLR и т.д. lexx/yacc/bison/т.п. работают как раз в этих парадигмах и львиная доля усилий там тратится именно на то, чтобы понять - вот эта буква "a", что мы только что считали - это вообще что.

Парсинг бинарных форматов гораздо более тупой, с одной стороны, с другой - куда более error-prone. Когда мы читаем очередной байт - мы обычно наверняка уже знаем, что это за поле какой структуры. Почти никогда не бывает, что нам сначала надо прочитать какой-то гигантский кусок, а потом его проинтерпретировать. Проистекает это ровно из построения и применения этих самых форматов - их специально делают такими, чтобы их было удобно читать программно.

Написать на bison парсер бинарного формата вполне возможно, только никому в голову это не придет: это гигантский оверхед, который ничего полезного не даст в итоге. bison разложит все в некую структуру синтаксического дерева, которой потом еще придется выдирать ее неким отдельным преобразованием.


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Аноним , 12-Апр-16 19:26 
Ну все, postgres, mysql, oracle перейдут на него для хранения данных и... а не, C/C++ пока нету.

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 12-Апр-16 19:28 
> Ну все, postgres, mysql, oracle перейдут на него для хранения данных и...
> а не, C/C++ пока нету.

Форматы хранения MyISAM, InnoDB и SQLite, кстати, мы вполне умеем разбирать ;)


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Аноним , 12-Апр-16 19:33 
И для сборки всего, что его использует будет нужна Java.

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 12-Апр-16 19:39 
> И для сборки всего, что его использует будет нужна Java.

Либо JavaScript. Scala умеет компилироваться либо для JVM, либо для JavaScript-машин типа nodejs. Последнее, кстати, запускается радикально быстрее и сильно веселее в целом, если дергать его для десятка форматов из какого-нибудь Makefile, скажем.


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Crazy Alex , 12-Апр-16 20:04 
Хм, вообще-то нода запускается ни разу не быстро...

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 12-Апр-16 20:13 
> Хм, вообще-то нода запускается ни разу не быстро...

У меня получается что-то в районе ~400 ms на один запуск компилятора на JVM и ~160 ms на запуск компилятора под nodejs. Не сверхбыстро, но все же в 2.5 раза быстрее, чем JVM.


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Crazy Alex , 12-Апр-16 20:33 
У вас какой-то монстр, а не машина :-) с такой скоростью у меня на JVM даже hello world не взлетает, а на ноде - time nodejs -e 'console.log(1)'
даёт 0.4 секунды

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 12-Апр-16 20:48 
> У вас какой-то монстр, а не машина :-) с такой скоростью у
> меня на 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 total

JVM:

$ 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?


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено anonymous , 13-Апр-16 21:01 
>Последнее, кстати, запускается радикально быстрее

Была какая-то тулза для ускорения многократного запуска программ на Java за счет переиспользования JVM


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Аноним , 12-Апр-16 19:32 
Бинарный bison...
на Java...

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 12-Апр-16 19:35 
> Бинарный bison...
> на Java...

На Scala, на самом деле :)


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Аноним , 12-Апр-16 19:37 
Ааа, ну это многое объясняет.

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено serg , 20-Апр-16 21:34 
Господа! Если время старта/компиляции критично, то можно файлы *.class скормить компилятору gcj (все про него забыли). Получится нативный исполняемый бинарь, который порадует вас не только быстрым стартом, но и шустрым исполнением кода.

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 20-Апр-16 21:52 
> Господа! Если время старта/компиляции критично, то можно файлы *.class скормить компилятору
> gcj (все про него забыли). Получится нативный исполняемый бинарь, который порадует
> вас не только быстрым стартом, но и шустрым исполнением кода.

Эм, вы сами пробовали? Нативный бинарь получается размером эдак мегабайт 30-35, JIT в нем отсутствует начисто, внутри по сути примерно такая же виртуальная машина, стартап там тоже мягко говоря небыстрый и сама программа работает, как правило, в несколько раз медленнее того, как она работает в JVM.

Плюс, пардон, когда я последний раз туда смотрел, там не то, что Java 7 не поддерживалась, даже Java 6 местами не была реализована.


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Crazy Alex , 12-Апр-16 20:03 
Хм, правильно, конечно. Если б ещё было на чём-то человеческом (читай - компилируемом в шустрый бинарь, не требующий VM), а не Scala... Но, в конце концов, ничего идеального не бывает, если сделают выхлоп в виде C и C++ - то, в общем, вполне юзабельно. Да и удачный формат и большая  библиотека описаний в таких вещах важнее языка реализации, а здесь, вроде, есть кому эти описания клепать.

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 12-Апр-16 20:07 
> Хм, правильно, конечно. Если б ещё было на чём-то человеческом (читай -
> компилируемом в шустрый бинарь, не требующий VM), а не Scala... Но,
> в конце концов, ничего идеального не бывает, если сделают выхлоп в
> виде C и C++ - то, в общем, вполне юзабельно. Да
> и удачный формат и большая  библиотека описаний в таких вещах
> важнее языка реализации, а здесь, вроде, есть кому эти описания клепать.

Поддержку C++ мы делаем уже месяц как, но, как выясняется, это несколько сложнее, чем казалось на первый взгляд.

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


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Crazy Alex , 12-Апр-16 20:28 
Ну и я примерно о том же. Спасибо за интересный инструмент, а нужно ли будет его (и кому) реализовывать на других языках - будет видно.

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено fi , 13-Апр-16 01:01 
После RabbitMQ на Erlang стало фиолетово что там внутри готовой прикладухи круться. :)))
Чего и вам желаю!

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Аноним , 12-Апр-16 20:07 
Не взлетит. Тем более с таким языком разметки, тем более оно не тьюринг-полное ни разу.

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 12-Апр-16 20:51 
> Не взлетит. Тем более с таким языком разметки, тем более оно не
> тьюринг-полное ни разу.

Оно с одной стороны и не планируется тьюринг-полное, это по логике своей — DSL, с четко ограниченной областью применения.


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Аноним , 12-Апр-16 21:14 
> DSL

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


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Алконим , 20-Апр-16 20:21 
Для парсинга *любого* бинарника нужна машина тюринга. Бинарь частично упакованый gzip или зашифрованый ssl, смогёт?

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Anonymous_1 , 12-Апр-16 21:55 
Прикольная штука, взял на заметку.

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено None , 12-Апр-16 22:26 
Ожидаю сравнения с ASN.1

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Crazy Alex , 12-Апр-16 23:28 
Не надо с ним сравнивать. С ним вообще связываться не надо - оно не человеческое.

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 13-Апр-16 08:21 
> Ожидаю сравнения с ASN.1

ASN.1 можно сравнивать с protobuf или, скажем, как продвинутый вариант bencoded или BSON. Т.е. это все варианты серилизации каких-то структур данных из памяти в поток и обратно, причем сам механизм сериализации фиксированный. KS — это инструментарий для парсинга произвольных потоков. Скажем, PNG-файл или там какие-нибудь пакеты из сетевого трафика.


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Аноним , 13-Апр-16 01:06 
> Первый публичный релиз поддерживает Java, JavaScript, Python, Ruby, ожидается поддержка C, C++ и C#.

Должно быть ровно наоборот.


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Аноним , 13-Апр-16 01:42 
Как насчет сравнения с BinPac ? https://github.com/bro/binpac/blob/master/README

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Влад , 13-Апр-16 01:58 
Присоединяюсь к вопросу. С binpac работать приходилось, отличная штука, которая может и файлы и поток парсить. Какие части декларативно никак не сделать (редко, но бывает) - можно вручную попарсить, есть встроенные в binpac средства для связи с ручным парсером. А если внутри того, что парсишь вручную снова можно декларативно парсить - тоже не проблема, легко и обратно к декларативному парсингу вернуться

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 13-Апр-16 09:04 
> Присоединяюсь к вопросу. С 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 и т.д. Большей частью это связано с тем, что не хочется гнаться за специализированными фичами, а обеспечить их более-менее хорошую реализацию для всех поддерживаемых языков.


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено qpq , 13-Апр-16 02:09 
А как на счёт генератора бинарного потока? Или парсер может в обе стороны?

Интересуюсь потому что у на есть проект где надо работать с бинарным древним форматом высокой сложности, но нужно не только разбирать данные, но и создавать в бинарном формате.

Было бы приятно описать формат и сгенерить сопутствующие структуры вместо ручного создания всего необходимого.


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 14-Апр-16 10:42 
Генератора пока нет — есть далекоидущая цель сделать это где-нибудь ко второй major версии. По большому счету в декларативном формате эта задача упирается в необходимость (и возможность) символического вывода: например, если где-то объявлено число x, а где-то есть строка str длиной (2 * x + 3), т.е. str.length = 2 * x + 3. Значит, при записи нужно развернуть формулу и записывать x = (str.length - 3) / 2. И, внезапно, иногда решений может вообще не быть, а иногда их может быть бесконечно много.

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено j , 13-Апр-16 02:11 
Подхватываете флаг преона? великое дело, имхо
от преона не забудьте взять легкую расширяемость - всех извращений не предусмотришь.
для бигдаты было бы полезно простую интеграцию в виде преобразования в avro, например. прекрасно те же cdr разбирать. там за такой разбор с медиейшеном платят ой как много.

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 13-Апр-16 10:06 
> Подхватываете флаг преона? великое дело, имхо
> от преона не забудьте взять легкую расширяемость - всех извращений не предусмотришь.

Тут в какой-то степени двоякая ситуация. С одной стороны — никто не запрещает в императивном уже режиме из языка дергать парсеры как угодно и комбинировать их результаты. Это по сути примерно то же самое, что есть в Preon — и это все можно, но (1) оно будет привязано к одному конкретному языку, (2) это императивно, а не декларативно.

С другой стороны — по идее нужна какая-то более гибкая расширяемость, но оставаясь в декларативных рамках. Очень много что дают value instances (по сути внутри там — некий язык выражений, который гарантированно компилируется в соответствующее выражение на Java/JS/Python/Ruby), но они тоже не панацея, плюс они решают только задачу чтения (бинарник => классы), но не записи (классы => бинарник). Нужно придумывать что-то еще.

> для бигдаты было бы полезно простую интеграцию в виде преобразования в avro,
> например.

Avro — в смысле, с генерируемых классах сразу Avro-аннотации генерировать, как-то так?

> прекрасно те же cdr разбирать. там за такой разбор с
> медиейшеном платят ой как много.

CDR — имеются в виду всякие логи сотовых операторов и прочая биллинг-ориентированная тематика?


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено j , 13-Апр-16 22:53 
> Avro — в смысле, с генерируемых классах сразу Avro-аннотации генерировать, как-то
> так?

В идеале + код. Если говорим о Hadoop семействе, то оптимально - InputFormat c выходом Avro объектов. Кроме самого Hadoop-а это практически автоматом даст интеграцию с Spark и Hive

> CDR — имеются в виду всякие логи сотовых операторов и прочая биллинг-ориентированная
> тематика?

Сырые логи с оборудования. Навскидку http://bill-parser.googlecode.com/svn/trunk/doc/CDR_Descript...

При этом CDR - это вершина айсберга. Там еще траффик, технические логи итд



"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Срп , 13-Апр-16 02:36 
ну и дела:
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


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Аноним , 13-Апр-16 06:48 
первый вариант - валидный YAML, второй - очередной нескучный велосипед.

"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Анонимомус , 13-Апр-16 13:28 
Можно было и валиндный yaml:

seq:
  image_width: u2
  image_height: u2
  flags: u1
  bg_color_index: u1
  pixel_aspect_ratio: u1

только это не расширяемо.


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено GreyCat , 13-Апр-16 13:30 
> Можно было и валиндный yaml:
> seq:
>   image_width: u2
>   image_height: u2
>   flags: u1
>   bg_color_index: u1
>   pixel_aspect_ratio: u1
> только это не расширяемо.

Главная проблема здесь в том, что у вас получился map под названием seq, в котором порядок элементов не определен. А нам он важен, т.к. нам их надо парсить именно в определенной последовательности.


"Декларативная спецификация парсинга бинарных файлов Kaitai S..."
Отправлено Никто , 13-Апр-16 17:53 
В этом и преимущество велосипедных DSL - больше возможности для краткости.