Очень давно изучал юзал такую библиотеку : III ASN.1 Tool. Тот проект, в котором это использовалось, был этим самым «продакшн», Voip и все остальные навороты вплоть до платы с крутым по тем временам Analog Device.

Не только мертв, но ещё и исправно работает.

Последний коммит в 2013. Как язык его уже никто не развивает и развивать не будет. Там, где оно еще применяется, в 95% случаев плюют на декларативность и тупо засовывают в grammar C++ код. Вот яркий пример. ASN.1, вроде бы отличный повод сделать декларативный спецификацию формат. Что мы видим на практике? Сплошные %header{} и %code{}.

Или вот еще пример - UDP. Казалось бы - проще некуда. Бери и разбирай декларативно. Но почему-то там до сих пор болтается вручную написанный разбиратель пакета на чистом C++. Императивный, разумеется.

А производительность сравнивали?

У нас для этих целей есть бенчмарки. В них мы сравниваем наши собственные реализации между собой, ну и еще недавно мерялись с fastparse, который тоже научился бинарные данные парсить. Соревнуясь на Java, Fastparse мы обогнали в ~40 раз (на C++ - в 200-300, но сравнивать Java vs C++ не столь интересно).

Бенчмарки у BinPAC как находились в состоянии «хорошо бы, чтобы кто-нибудь сделал» уже много лет, так и находятся. Если вы владеете BinPAC и поможете с ним - я более, чем готов выступить с нашей стороны, было бы очень интересно.

Чудесно, это инструмент для работы с ASN.1. Им можно парсить, внезапно, только протоколы, основанные на ASN.1. Попробуйте им распарсить, скажем, файловую систему типа ext2 или там какой-нибудь медиаконтейнер типа tiff, ogg или mkv.

наверное надо сделать спек. TIFа на ASN.1 Ну или язык изобрести, готовый для канпиляции. я слышал что это полезно в крипто-протоколах, а для ширпотреба - слишком хлопотно...хотя я не в теме уже, да и не был...

чтобы быть более-менее zero-copy

Нужно ссылаться на содержимое исходного буфера, и никогда не копировать строки/блобы в heap. Например, для xml так достигают parsing speed approaching that of strlen function executed on the same data.

http://rapidxml.sourceforge.net/manual.html#namespacerapidxml_1performance_ch...

http://rapidxml.sourceforge.net/manual.html#namespacerapidxml_1differences

http://www.aosabook.org/en/posa/parsing-xml-at-the-speed-of-light.html

Для ссылок можно использовать http://en.cppreference.com/w/cpp/string/basic_string_view или же (в случае старого стандарта) http://www.boost.org/doc/libs/1_62_0/libs/range/doc/html/range/reference/util...

Если вы владеете BinPAC и поможете с ним

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

Можно начать, например, с вот такого примитивного формата:

meta:
  id: test_format
  endian: le
seq:
  - id: files
    type: file
    repeat: eos
types:
  file:
    seq:
      - id: len
        type: u4
      - id: name
        type: str
        size: len
        encoding: UTF-8

Здесь объявляется массив files, состоящий из элементов типа file, повторяющихся до конца входного стрима (repeat: eos). Каждый file состоит из длины len (u4 = unsigned int, 4 bytes) и собственно названия файла name (строки в UTF-8 длины len байт).

Во что превращается это, если скомпилировать этот ksy в C++ сейчас, можно посмотреть на http://kaitai.io/repl/

Вопрос: как бы вы изменили генерируемый файл, дабы избежать копирования строк и вектора?

Ну, если нам хочется сравнить - надо либо найти, либо создать что-то, что будет описано и в KS, и в BinPAC. У KS есть вот такая коллекция форматов. Про BinPAC я знаю по сути единственный Bro, который его использует, и там, соответственно, только всякие сетевые пакеты, да и то, в очень многих случаях используется не BinPAC в чистом виде, а либо вручную написанные парсеры на C++, либо весьма .pac с кучей header-code, плотно встроенные в инфраструктуру Bro и толком оттуда не выдираемые.

Есть какие-то идеи? Когда мы гонялись с FastParse, мы сравнивали скорость парсинга MIDI-файлов. Может быть у коллег можно каких-нибудь примеров попросить?

Битовые поля

А вот такую структуру как описать?

(1 bit) Latitude Hemisphere
(7 bit) Latitude Degrees
(6 bit) Latitude Minutes
(5 bit) Latitude Fractional part
(1 bit) Longitude Hemisphere
(8 bit) Longitude Degrees
(6 bit) Longitude Minutes
(5 bit) Longitude Fraction
(1 bit) Spare

я бы взял HDF5 или другой всеядный формат с хорошим парсером. Наверное, в R&D это интересная задача, но если взять реальные парсеры, скажем метео GRIB, все привязываются к ошибкам парсера, с точностью до версии релиза...

Долго и муторно, но можно. Это ровно 40 бит, то есть 5 байт, то есть все aligned.

seq:
  - id: b0
    type: u1
  - id: b1
    type: u1
  - id: b2
    type: u1
  - id: b3
    type: u1
  - id: b4
    type: u1
instances:
  latitude_hemisphere:
    value: (b0 & 0b10000000) >> 7
  latitude_degrees:
    value: (b0 & 0b01111111)
  latitude_minutes:
    value: (b1 & 0b11111100) >> 2
  latitude_fractional_part:
    value: ((b1 & 0b00000011) << 3) + ((b2 & 0b11100000) >> 5)

и т.д. для всех частей. По идее, когда доделаем issue #9, это все должно превратиться что-то типа

seq:
  - id: latitude_hemisphere
    type: b1
  - id: latitude_degrees
    type: b7
  - id: latitude_minutes
    type: b6
  - id: latitude_fractional_part
    type: b5
# ...

Откуда формат, кстати, если не секрет?

Хм, можете как-то пояснить, какое отношение ваш комментарий имеет к тому, на что он отвечает? HDF5 - в этом контексте - по сути, то же самое, что и Protobuf, ASN.1, Avro, Thrift и все такое. Каким образом рассматривание специфичного парсера такого формата поможет улучшить KS?

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

Кстати, битовые операторы, кажется, в документации не описаны. Можно ли не один байт использовать, а несколько, например все пять и описать для них несколько пятибайтовых битовых маски?

Асимптотически, это потребует O(log(N)) аллокаций и O(N) копирований структуры file_t, где N - это число файлов. Имена файлов не копируются.

Ещё немного, и вы изобретёте паттерн-матчинг binaries из эрланга, только неудобно и ограниченно.

inb4: зато у нас генерится код на 70 языках

Jack of all trades, master of none?

Это важно для видео и аудио, без этого у какого-нибудь .h264 даже высоту и ширину не распарсить https://stackoverflow.com/questions/12018535/get-the-width-height-of-the-vide...

Ещё немного, и вы изобретёте паттерн-матчинг binaries из эрланга, только неудобно и ограниченно.

Паттерн-матчинг эрланга ничем не отличается от любых других parser combinators - на хаскеле ли, скале, питоне или джаваскрипте. Все их плюсы и минусы в целом известны. Я вот выше упоминал сравнение с fastparse - мы в ~40 раз его быстрее на той же платформе (JVM).

Jack of all trades, master of none?

Постановка задачи на самом деле разная. У KS - цель - предоставить API для работы с форматом. А дальше - что с этим API будут делать - дело пользователя. В том числе не возбраняется вариант «ничего не делать, посмотреть глазками в визуализаторе».

У parser combinators - задача - схватить на лету и выдать матч здесь и сейчас. В итоге на некоторых задачах, где не нужно загружать и парсить все в памяти - они быстрее, но некоторые задачи («посмотреть глазками») с их помощью делать малореально.

Кстати, битовые операторы, кажется, в документации не описаны.

Не описаны :( Как почти и весь язык выражений. Декларируется только, что он похож на C / Java / JavaScript / Python / Ruby.

Можно ли не один байт использовать, а несколько, например все пять и описать для них несколько пятибайтовых битовых маски?

Все пять сразу - нет. Было бы 1, 2, 4 или 8 - тогда можно было бы зачитать числом через u1/u2/u4/u8, и потом накладывать на это число длинные битовые маски. А так - можно извратиться через 1 + 4 и какое-то промежуточное вычислимое значение, типа такого:

seq:
  - id: b1
    type: u1
  - id: b25
    type: u4be
instances:
  b15:
    value: (b1 << 32) | b25
  some_foo:
    value: (b15 & 0x0ff0000000) >> 28

и т.п.

Клёвая штука! Спасибо! Я даже не представлял, что бывают такие инструменты и костылил ручками.

Можете ли вы добавить в примеры парсер .blend-файла из Blender 3D?

Спасибо.

Кстати, а почему тогда бы не подтянуть glib? И так много где используется. Или хотите меньше зависимостей для сгенерированного парсера?

Последний коммит в 2013. Как язык его уже никто не развивает и развивать не будет. Там, где оно еще применяется, в 95% случаев плюют на декларативность и тупо засовывают в grammar C++ код.

Всегда ли есть способ обойтись одной лишь декларативностью? Рассмотрим например очередной прототип примитивной файловой системы, где для простоты не будет никакой фрагментации, и файлы целиком будут идти сплошным куском, длина имени файла ограничена в 4 байта и структуры, описыващие файлы, отсортированы по именам файлов:

used bytes | text description          | d
-----------+---------------------------+---------------
0..3       | ASCII header "MyFS"       |\ struct header
4..7       | uint32_t numoffiles = 3   |/
8..11      | ASCII file_1 name "aaaa"  |\
12..15     | uint32_t file_1_start = 0 | > struct file 
16..19     | uint32_t file_1_len   = 10|/
20..23     | ASCII file_2 name "bbbb"  |\
24..27     | uint32_t file_2_start = 11| > struct file
28..31     | uint32_t file_2_len   = 7 |/
32..35     | ASCII file_3 name "сссc"  |\
36..39     | uint32_t file_3_start = 18| > struct file
40..43     | uint32_t file_3_len   = 3 |/
// конец описания = 44
44..53     | file_1_data {binary blob} | 10 byte blob
54..60     | file_2_data {binary blob} | 7  byte blob
61..63     | file_3_data {binary blob} | 3  byte blob

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

Можно ли конкретно очертить круг задач, которые должны быть решаемыми через KS, и которые уже выходят за рамки?

Паттерн-матчинг эрланга ничем не отличается от любых других parser combinators

Неверно.

Ключевая фраза - «И чтобы всем нравилось». glib, к сожалению, даже не в 40-50% проектов используется - хорошо если в 5-7%. Хотя, да, наверное, с glib надо начинать.

О реализации

А почему вообще битовые маски привязаны к стандартным типам?
Если забыть про производительность, то простейший способ реализовать маски любой длины - представить каждый байт в виде последовательности восьми нулей и единиц, сделать из них длинную строку, выбирать подстроки нужной длины, и превращать их обратно в байты с добавлением слева нужных нулей. Чисто строчные операции, медленные по сравнению с битовыми операциями, но очень наглядные и удобные в использовании.
битовая строка, полученная из пяти байт, будет например
$bitstring = '01100101011101010101001010101010'
маски можно описать

«Latitude Hemisphere» = substr(0,1)
«Latitude Degrees» = substr(1,7)
«Latitude Minutes» = substr(8,6)

bitseq 5 bytes:
  - id: Latitude_Hemisphere
    type: c1
  - id: Latitude_Degrees
    type: c7
  - id: Latitude_Minutes
    type: c6
instances:
  Latitude_Hemisphere:
    value: Latitude_Hemisphere
  Latitude_Degrees:
    value: Latitude_Degrees
  Latitude_Minutes:
    value: Latitude_Minutes

(1 bit) Latitude Hemisphere
(7 bit) Latitude Degrees
(6 bit) Latitude Minutes

Можно для C сделать несколько вариантов, с glib, klib, и что там ещё бывает.

Kaitai

Заполярные виабу?

В реализации можно сразу эффективного кода накодгенить, а описывать через произвольные 01 удобно, да. Для удобства всё равно стоит добавить битпарсеры с произвольным числом бит на значение и всяким https://en.wikipedia.org/wiki/Exponential-Golomb_coding

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

«Редактор» - это в смысле какой-то из «визуализаторов»?

По хорошему, это все должно сводиться к чему-то типа:

seq:
  - id: latitude_hemisphere
    type: b1
  - id: latitude_degrees
    type: b7
  - id: latitude_minutes
    type: b6

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

Можете ли вы добавить в примеры парсер .blend-файла из Blender 3D?

.blend-файлы - очень простые (в плане общей структуры) и весьма сложные одновременно (просто в плане количества подструктур: их там под 800 штук). Вот самый-самый скелет:

meta:
  id: blender_blend
  endian: le
seq:
  - id: header
    type: header
  - id: blocks
    type: file_block
    repeat: eos
types:
  header:
    seq:
      - id: magic
        contents: BLENDER
      - id: ptr_size_id
        type: u1
        enum: ptr_size
        doc: Size of a pointer; all pointers in the file are stored in this format
      - id: endian
        type: u1
        doc: Type of byte ordering used
        enum: endian
      - id: version
        type: str
        size: 3
        encoding: ASCII
        doc: Blender version used to save this file
    instances:
      psize:
        value: 'ptr_size_id == ptr_size::bits_64 ? 8 : 4'
        doc: Number of bytes that a pointer occupies
  file_block:
    seq:
      - id: code
        type: str
        size: 4
        encoding: ASCII
        doc: Identifier of the file block
      - id: size
        type: u4
        doc: Total length of the data after the header of file block
      - id: mem_addr
        size: _root.header.psize
        doc: Memory address the structure was located when written to disk
      - id: sdna_index
        type: u4
        doc: Index of the SDNA structure
      - id: count
        type: u4
        doc: Number of structure located in this file-block
      - id: body
        size: size
enums:
  ptr_size:
    0x5f: bits_32
    0x2d: bits_64
  endian:
    0x56: be
    0x76: le

Давайте так: вы попробуете начать его детализировать, а если что-то будет не получаться - я присоединюсь? Я так понимаю, что начинать надо с чтения http://www.atmind.nl/blender/mystery_ot_blend.html , а затем переходить сразу к соответствующему коду https://github.com/dfelinto/blender/blob/master/source/blender/blenloader/int...

еще про форматы. в90х начинал программировать с парсера tif, потом сделал парсер автокада, потом начал делать step. Все эти задачи закрывались с выходом стандартного парсера, пусть и криво реализованного. Как вы считаете, что легче? Написать спецификацию grib2 на декларативном языке или разобраться с существующим парсером, для примера таким: ftp://ftp.cpc.ncep.noaa.gov/wd51we/wgrib/wgrib.c

битпарсеры с произвольным числом бит на значение и всяким https://en.wikipedia.org/wiki/Exponential-Golomb_coding

Вот, кстати, тоже относительно больной вопрос, как удобно сделать всякие variable-length чтение и запись... Даже не обязательно bit-level, хотя бы byte-level.

Вот скажи честно, ты мазохист? Мог бы сразу написать, что в первую очередь инструмент для реверсинга проприетарных форматов игорей, ВНок и прочих вирусов; тогда тебе хотя бы про протобуф, асн.1 и прочее не по теме не рассказывали бы. Ладно, на оф. сайте; но тут-то кого стесняться?

По-моему, вопрос надо ставить «что проще: разобраться с декларативной спецификацией или разобраться с написанном на конкретном языке программирования императивным алгоритмом». И, как мне кажется, ответ очевиден: декларативную спецификацию читать в разы легче.

А вот например доступ по a.b.c.d когда b undefined

Ну у них уж какая-то совсем универсальная штука, одна стилистика на все языки, в сисярпе можно сказать var x = a?.b?.c?.d, а по-уму вообще структур нагенерить и пометить Serializable их, шоб стандартными средствами все это разруливать.

Не все вещи декларативно описать легче, чем императивно. Например, хеш-таблица требует наличия хеш функции. Хотел бы я посмотреть на декларативное описание MD5 например

Так вот, как вы предлагаете декларативно описать то, что тут вот файлы по имени отсортированы, и чтобы по этому декларативному описанию был сгенерирован код, который бы применял двоичный поиск для вытаскивания файла из ФС?

Вы сейчас опять же притягиваете за уши какие-то дополнительные действия над загруженными данными, требуя от меня сделать их с некоей мифической декларативностью. На практике все банально и просто: декларативность - в том, что вы только что описали. Что есть такие-то структуры байтов. Дать к ним обращаться как myfs.file[42] - входит в задачу KS. А вот искать по имени файла и тем более делать это эффективно - задача уже того, кто будет использовать предлагаемый API.

Можно ли конкретно очертить круг задач, которые должны быть решаемыми через KS, и которые уже выходят за рамки?

Круг очень простой: уметь предоставлять доступ к структурам - так, как они сериализованы в файле/потоке. Встроенный язык выражений и все вокруг него не претендует быть каким-то магическим новым функциональным языком, который решит все проблемы человечества - он сознательно весьма минималистичный. Единственная задача, которую он решает - собственно парсинг самого файла.

При чем тут хеш-таблицы или MD5, если речь вроде бы о формате сериализации?

Примеры или пояснения какие-то будут?

Вау, ничего себе штука. Афтар, пул реквесты принимаешь? Есть с чем помочь по JVM/Scala?

Спасибо! Только что досмотрел. Попробую подытожить, что предлагается:

1. Отказаться от парсинга из istream. Вместо этого парсинг идет из некоей самодельной структуры buffer_view_t, которая есть просто указатель + длина.

2. Отказаться от class и сделать все через struct, т.е. public. Зачем - пока не очень понятно. Соответственно, удалить геттеры.

3. Отказаться от std::string (и забить, по крайней мере пока, на кодировки) - использовать buffer_view_t и для строчек, и для массивов байт. Честно говоря, пока все равно не понятно - зачем? std::string по сути - то же самое. При желании можно у него двигать внутренние указатели по массиву байт.

4. Перейти от парадигмы «класс включает методы, чтобы парсить себя» к «есть куча статических методов parse, которые имеют на входе buffer_view_t, а на выходе - запрошенный struct + обновленный buffer_view_t».

5. Отказаться от exceptions и решать ошибочные ситуации через assert.

6. Использовать extended initializer lists, что C++11, но, по идее, это можно обойти через явные временные переменные.

Я более-менее прав?

Есть с чем помочь по JVM/Scala?

Задач более, чем дофига - https://github.com/kaitai-io/kaitai_struct/issues - хотелок у народа с каждым днем все больше. Недавно вот любители криптографии пришли, например. Welcome :)

Хеш-таблицы с MD5 могут использоваться при сериализации, например в файловой системе, чтобы быстро находить файл

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

Во-вторых, даже если это потребуется - ну, будет дополнительная функция в языке, чего в этом такого? У нас вот сейчас криптографию en masse хотят принести - там и так сильно больше, чем просто хэши...

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

«старый и работающий везде» (не требующий даже C++03)

У вас там stdint.h, а заодно линуксовые хедеры.

и забить, по крайней мере пока, на кодировки

Где-то треть японских форматов отвалится, либо придётся приделывать внешние кодировки. В mmd-форматах японские названия в разных кодировках (ShiftJIS и UTF16) используются для сопоставления костей модели/анимации, например. Причём если в vmd/pmd всегда шифтжис, то в pmx строки могут быть и в том и в том формате (не будь намешано, можно было бы mojibake в качестве ключей и использовать). И это ещё не самый дикий случай, ковыряя VN и игры чего только не встречал.

В целом, можно переписать лучше, вам нужны PR?