LINUX.ORG.RU

Релиз Kaitai Struct v0.4

 , , , ,


2

3

Состоялся релиз v0.4 проекта Kaitai Struct — декларативного языка для описания форматов структур данных. Описание структуры составляется в виде файла .ksy (в простом YAML-подобном виде), а затем с помощью предлагаемого компилятора транслируется в исходный код парсинга (на данный момент поддерживаются C#, Java, JavaScript, Python, Ruby и предварительно — C++). Типичная сфера применения — разбор и импорт существующих бинарных форматов файлов (в том числе закрытых и проприетарных), сетевых пакетов (например, в составе IDS или систем мониторинга трафика) и т. п.

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

Инструментарий распространяется под GPLv3, используемые в компилируемом коде runtime-библиотеки — под MIT/Apache. Референсный компилятор написан на Scala, но существует версия для веба на JavaScript, работающая в браузере целиком на стороне клиента.

Из нововведений нового major-релиза можно отметить:

  • поддержку 2 новых целевых языков: полная поддержка C# и предварительная — C++ с STL;
  • полную поддержку JavaScript в runtime-библиотеке;
  • поддержку новых типов данных: числа с плавающей точкой и выделенные типы для массивов байт;
  • расширение встроенного языка выражений: добавлены операции для работы с массивами, преобразования типов данных, доступа к объекту потока и т. п.;
  • существенную переработку и унификацию runtime-библиотек всех поддерживаемых языков для приведения их всех к единому API (в рамках дозволенного правилами конкретных языков).

>>> Подробности

★★

Проверено: tailgunner ()
Последнее исправление: CYB3R (всего исправлений: 4)

А ksy - это единственный входной формат? Судя по примерам, читать его невозможно - какой-то XML без тегов.

tailgunner ★★★★★
()
Ответ на: комментарий от Quote

Спасибо за отзывы.

Смущают пока разрозненная документация

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

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

референсный компилятор на Scala

Это сложный вопрос. Как мне кажется - в 2016 году уже совсем не ужас-ужас. К сожалению, проект получился достаточно сложным. Текущая инкарнация KS на Scala - уже четвертая. Три предыдущих (какие-то наметки и попытки года эдак с 2008-2009) были написаны соответственно на Java, Ruby и еще раз на Ruby. Если очень интересно - могу прислать-поиграться третью инкарнацию (она даже частично совместима по синтаксису, но умеет компилироваться, кажется, только в Ruby-код).

Pure C компилятор - тоже совершенно не панацея в современном мире. Да, его будет чуть проще протащить в Linux-дистрибутивы, но на этом эйфория заканчивается. Люди на оффтопик-системах, особенно без C-компиляторов - начинают страдать (ну или начинает страдать релизер проекта, которому надо собрать бинарники на огромной туче разных платформ). А запускать это в браузере - так уже совсем из серии извращений (уж по сравнению со ScalaJS, который просто работает - так точно).

Разумеется, по большому счету - мне не столь интересен компилятор как таковой, сколько установление какого-то порядка и общеупотребительного стандарта описания бинарных файлов. Чтобы очередной проект вроде GIMP или OpenOffice, который захочет читать файлы от Photoshop или MS Word, не варился в собственном соку и не писал еще раз парсер с нуля, огребая все возможные грабли по пути, а работал над какой-то общей базой, которой бы пользовались все открытые проекты.

Было желание применить для потрошения бинарников, сжатых мешаниной из LZ77, deflate и ещё непойми чего, но, судя по всему, средствами одного лишь KS это пока тяжко.

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

GreyCat ★★
() автор топика
Ответ на: комментарий от tailgunner

А ksy - это единственный входной формат? Судя по примерам, читать его невозможно - какой-то XML без тегов.

Теоретически его можно переделать хоть в XML, хоть в JSON, хоть в какой-нибудь очередной нескучный C-подобный велосипед с фигурными скобочками.

Месяц назад мне писал один товарищ и говорил, что хочет реализовать поддержку всего того же, но в XML (типа, сделать .ksx). Т.е. вместо:

meta:
  id: hello_world
  endian: le
seq:
  - id: one
    type: u1
  - id: two
    type: u4
  - id: three
    type: goodbye_world
    if: two > 42
types:
  goodbye_world:
    seq:
      - id: four
        type: strz

предлагалось что-то вроде:

<kaitai-struct id="hello_world" endian="le">
  <seq>
    <attr id="one" type="u1"/>
    <attr id="two" type="u4"/>
    <attr id="three" type="goodbye_world" if="two &gt; 42"/>
  </seq>
  <types>
    <type id="goodbye_world">
      <seq>
        <attr id="four" type="strz"/>
      </seq>
    </type>
  </types>
</kaitai-struct>

По-моему, читаемость что у YAML, что у XML примерно одинаковая. Писать YAML руками существенно легче. Сделать визуальный редактор легко примерно одинаково для всего.

Но XML-товарищ так куда-то и пропал :(

GreyCat ★★
() автор топика
Ответ на: комментарий от GreyCat

По-моему, читаемость что у YAML, что у XML примерно одинаковая

У XML лучше, но не суть - человекочитаемых форматов (как в binpac, например) не планируется?

tailgunner ★★★★★
()
Ответ на: комментарий от tailgunner

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

struct hello_world [endian=le] {
  seq {
    u1 one;
    u4 two;
    goodbye_world three {
      if (two > 42);
    };
  }
  struct goodbye_world {
    seq {
      strz four;
    }
  }
}

Так сильно лучше?

GreyCat ★★
() автор топика
Ответ на: комментарий от GreyCat

Ну AVI-шку вообще просто распарсить, тем более там пример с PNG есть - они похожи. А вот чтобы по битам что-то искать - не видно. Если структурки по границе байта выровнены - это слишком просто. Я уже не говорю про всякие стоп-биты или stuffing-байты

ruzisufaka
()
Ответ на: комментарий от tailgunner

По количеству строчек, если что, получается:

  • YAML: 16
  • XML: 14 (но это без doctype, xmlns и прочей типовой мишуры)
  • C-style: 14 (или 12 в предложенном сокращенном варианте)

То есть как бы экономия есть, но в целом не в разы.

Как быть с более сложными случаями? Скажем, если поле нужно читать при условии foo > 42, через подпоток известной ограниченной длины buf_len, который предварительно перед чтением надо по-xor-ить через xor_key, а затем в итоге считать, что там внутри тип subtype и передать на парсинг в него. В ksy это делается так:

- id: some_field
  size: buf_len
  process: xor(xor_key)
  type: subtype
  if: foo > 42
GreyCat ★★
() автор топика
Ответ на: комментарий от tailgunner

И правда. На главной странице сайта Kaitai приведено описание GIF в ksy. Начни с того, что приведи аналогичное описание на Ragel.

Для тех случаев Ragel попросту избыточен. Там нет ничего, для чего бы потребовалось задействовать этот самый Ragel. Вот решение на чистом Си, вроде я нигде не напортачил http://melpon.org/wandbox/permlink/hOlohAk3tq5woD68

Писалось по мотивам https://github.com/kaitai-io/kaitai_struct_formats/blob/master/image/gif.ksy и https://www.w3.org/Graphics/GIF/spec-gif89a.txt

SZT ★★★★★
()
Ответ на: комментарий от GreyCat

То есть как бы экономия есть, но в целом не в разы.

Я не об экономии, а о читабельности. Впрочем, если целевой аудитории YAML читабельнее Си-подобного, окей.

Как быть с более сложными случаями? [...]

Я и половины терминологии не понял. Но, надеюсь, ты не станешь спорить, что всё это можно выразить через человекочитабельный синтаксис (YAML, как и XML, ориентирован на машину).

tailgunner ★★★★★
()
Ответ на: комментарий от GreyCat

Дело в том, что чистый C сильно отличается от всех до сих пор поддерживаемых языков, например, полностью ручным memory management и или, например, невозможностью работать со всем, как с выражением.

memory management не нужен, в моем коде нет ни одного malloc/free.

Даже договориться о том, как представлять те же самые строки или вложенные друг в друга объекты, выделять ли их в хипе или на стеке (и если на стеке - то у кого) - уже целая длинная песня.

Структурами парсить. См мой пример. И если функция разбора всего одна, вопрос «у кого на стеке» просто не возникает

Плюс совершенно другая модель прерывания работы и репортинга результатов (из-за отсутствия эксепшенов).

Если наступила нештатная ситуация, все делаем через goto в пределах одной функции. Эксепшены не нужны.

Никаких особых сложностей в ручном переписывании из gif.ksy в код на Си я не заметил. Я может быть даже мог бы помочь в реализации генерации кода в Си для KS, но Scala я совсем не знаю, и учить этот язык у меня нет никакого желания

SZT ★★★★★
()
Ответ на: комментарий от SZT

Начни с того, что приведи аналогичное описание на Ragel.

Вот решение на чистом Си

Вроде бы я просил Ragel, а ты запостил Си. Зачем - доказать, что на Си можно парсить бинари? Окей, можно. Продемонстрировать Си-скиллы? Я не впечатлен.

вроде я нигде не напортачил

Лень анализировать - на первый взгляд, ни endianness, ни валидацией ты не озаботился. Типично.

tailgunner ★★★★★
()
Ответ на: комментарий от tailgunner

Лень анализировать - на первый взгляд, ни endianness

Добавляется за пару минут. На little-endian машинах работает и так.

ни валидацией ты не озаботился.

А какая именно валидация тебе нужна? Вот эти if( ... ) goto fail;, этого разве мало? И где там валидация в https://github.com/kaitai-io/kaitai_struct_formats/blob/master/image/gif.ksy ?

SZT ★★★★★
()
Ответ на: комментарий от SZT

Лень анализировать - на первый взгляд, ни endianness

Добавляется за пару минут

Окей, ты блестяще доказал, что на Си можно написать парсер GIF. Тебя спрашивали о другом, но ты всё равно молодец.

И где там валидация в https://github.com/kaitai-io/kaitai_struct_formats/blob/master/image/gif.ksy ?

Почему ты ищешь ее там? Ищи в сгенерированном коде или рантайме.

tailgunner ★★★★★
()
Ответ на: комментарий от tailgunner

Окей, ты блестяще доказал, что на Си можно написать парсер GIF. Тебя спрашивали о другом, но ты всё равно молодец.

Не вопрос, могу и на Ragel. Просто Ragel не будет выигрышно смотреться в такой ситуации. Он тут явно избыточен. Ведь что тут требуется - требуется заматчить байты в некую структурку, потом в зависимости от того, какой битик вот в таком-то поле, мы разбираем следующий кусок байтов через эту или эту структуру. Это все отлично решается средствами С, без каких-либо вспомогательных инструментов. Хотя есть некоторые вещи, которые бы добавили мне проблем. Например:

  1. Нестандартные смещения чисел и нестандартные битности чисел, когда часть числа лежит в одном байте, часть в другом, при этом оно занимает больше бит, чем самый большой доступный в Си целочисленный тип. И обычные битфилды в пролете:
    typedef struct {
      uint64_t field65bit:65;
      unsigned __int128 field129bit:129;
    } Structure;
    
    Для решения такой задачи мне б пришлось через маски и сдвиги вычленять биты из типов меньшей разрядности, потом переводить в десятичную систему, используя длинную арифметику. Это бы сильно усложнило задачу
  2. Использование нестандартной https://en.wikipedia.org/wiki/Signed_number_representations (но это не такая уж большая проблема)
  3. Если бы применялись коды Рида-Соломона или нечто подобное, и стояла бы задача декодировать и поисправлять ошибки в этом битовом потоке, да и потом еще распарсить восстановленный после этого поток байтиков.

Почему ты ищешь ее там? Ищи в сгенерированном коде или рантайме.

Рантайм и сгенерированный код не знает о формате GIF ничего кроме того, что описано в самом .ksy файле для разбора этого GIF. И единственая валидация, которую можно сделать по данному описанию, это «unexpected end of file» и «GIF magic bytes not found». На сегодняшний день сушествует только два варианта: GIF89a GIF87a. Если посмотреть описание, то там вот эта вот часть 89a и 87a вообще не проверяется. Там далеко не полный разбор GIF формата производится. Например, если взять анимированный GIF, то туда будут упакованы несколько картинок, и у каждой картинки может быть свой color map (палитра), там этого попросту не учитывают. См. http://www.onicos.com/staff/iz/formats/gif.html

SZT ★★★★★
()
Последнее исправление: SZT (всего исправлений: 1)
Ответ на: комментарий от SZT

Не вопрос, могу и на Ragel

Ну так давай.

Это все отлично решается средствами С

Т.е. ты утверждаешь, что трудозатраты на написание ksy для GIF и парсера GIF на Си одинаковы? Без уверток, «да» или «нет».

tailgunner ★★★★★
()
Ответ на: комментарий от tailgunner

Ну так давай.

Может быть завтра, если мне не будет лень. Но Ragel тут явно оверкилл.

Т.е. ты утверждаешь, что трудозатраты на написание ksy для GIF и парсера GIF на Си одинаковы? Без уверток, «да» или «нет».

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

Однако, давайте рассмотрим такой сценарий:

  struct
  {
    uint16_t some_number1;
    uint1_t somedata[4*8]; // пока что мы не знаем, что тут за данные

    uint16_t some_number2;

    uint1_t bit :
     if (bit == 0) // А вот теперь знаем
     {
       somedata := uint16_t data[2];
     }
     else
     {
       somedata := uint32_t data;
     }
     
  } somestruct;
KS на данном этапе своего развития может с этим справиться?

И к слову

Окей, ты блестяще доказал, что на Си можно написать парсер GIF.

Я не ставил целью что-либо доказать или показать свои навыки программирования на Си. Скорее мне было интересно понять, что именно мешает создать в KS компилятор в Си. Как я убедился сам - ничего не мешает. Может быть этот код будет полезен в качестве примера, чтобы GreyCat реализовал компилятор в Си по такий же схеме, что и написанный мной код.

SZT ★★★★★
()
Последнее исправление: SZT (всего исправлений: 1)
Ответ на: комментарий от tailgunner

Т.е. ты утверждаешь, что трудозатраты на написание ksy для GIF и парсера GIF на Си одинаковы? Без уверток, «да» или «нет».

Думаю, что для честного сравнения надо сравнивать трудозатраты «на написание ksy» vs «на написание шести парсеров на C++, C#, Java, JavaScript, Ruby, Python». Скоро будет семи парсеров - еще на PHP.

GreyCat ★★
() автор топика
Ответ на: комментарий от SZT

Вот решение на чистом Си, вроде я нигде не напортачил

Скорее мне было интересно понять, что именно мешает создать в KS компилятор в Си. Как я убедился сам - ничего не мешает. Может быть этот код будет полезен в качестве примера, чтобы GreyCat реализовал компилятор в Си по такий же схеме, что и написанный мной код.

Спасибо, сейчас посмотрел код. Что хочу заметить:

  • Здесь нет возможности чтения из потока + чтения из буфера в памяти - только из буфера в памяти. Грузить все сразу в память - это иногда совсем не вариант (например, большие архивы или какой-нибудь 50-гигабайтный образ диска) - и долго, и бессмысленно - если задача - вытащить из него какой-нибудь один несчастный файлик на пару килобайт.
  • Typecasting в struct - плохая идея, как минимум нужна куча опций упаковки (и после этого каждый раз при доступе к таким struct все тормозит), как максимум - огромный зоопарк embedded-компиляторов чихать хотел на специфичные опции GCC и/или MSVC.
  • Самое главное - не получилось как такового API доступа к данным. Скажем, в любой из библиотек, сгенеренных KS сейчас, можно написать что-то типа `gif.block[1234]` и мы получим объект блока по порядковому номеру. Можно написать `gif.global_color_table[42].g` и получить доступ к зеленому компоненту цвета #42 из глобальной таблицы цветов. Здесь же такого нет - доступ к цвету есть только внутри процесса парсинга и только в момент нахождения указателя парсера на нужном цвете.

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

GreyCat ★★
() автор топика
Ответ на: комментарий от GreyCat

Здесь нет возможности чтения из потока + чтения из буфера в памяти - только из буфера в памяти.

Значит надо читать поток в буфер, и потом уже разбирать его

Грузить все сразу в память - это иногда совсем не вариант (например, большие архивы или какой-нибудь 50-гигабайтный образ диска)

Можно использовать отображение файла в память (mmap в *nix, MapViewOfFile в виндах) и тогда никаких проблем. Это уже будет забота ОС с ее механизмом подкачки.

Typecasting в struct - плохая идея, как минимум нужна куча опций упаковки

Тут не происходит прямого typecasting в struct, тут через memcpy в структуру загружается часть входного буфера (кстати этот memcpy вполне можно заменить чем-то другим, например чтением из Unix domain socket и тогда можно читать из некоего потока, а не из буфера в памяти). Если мы по условию не можем опираться на всякие #pragma pack для «уплотнения» структур, то придется от структур как таковых вообще отказаться, и делать memcpy прямо в тип нужной битности (прямой каст указателя и разыменование с unaligned read это UB)

Самое главное - не получилось как такового API доступа к данным. Скажем, в любой из библиотек, сгенеренных KS сейчас, можно написать что-то типа `gif.block[1234]` и мы получим объект блока по порядковому номеру. Можно написать `gif.global_color_table[42].g` и получить доступ к зеленому компоненту цвета #42 из глобальной таблицы цветов. Здесь же такого нет - доступ к цвету есть только внутри процесса парсинга и только в момент нахождения указателя парсера на нужном цвете.

Ну тут во-первых возникает закономерный вопрос: а насколько сильно подобное API раздует и усложнит итоговый код? Насколько это будет востребовано среди тех, кому нужно будет генерировать код в Си?
Релиз Kaitai Struct v0.4 (комментарий) :

А потом приходят злые эмбеддщики и говорят, что у них 2 килобайта памяти и килобайт 15-20 флешки под код

Вряд ли эмбеддщики будут сильно рады, им не нужно столь раздутое API.

А теперь насчет нужности `gif.block[1234]`. Под block у нас понимается то, что названо тут как Image Descriptor http://giflib.sourceforge.net/whatsinagif/bits_and_bytes.html. В Packed Field есть флаг, отвечающий на вопрос, будет или не будет у нас использоваться Local Color Table после Image Descriptor. Если будет, то следующий Image Descriptor будет идти не сразу же после предыдущего, а надо еще пропустить размер этого Local Color Table. Т.е. мы не можем за константное время получить gif.block[1234], необходимо перебирать последовательно все эти gif.block и смотреть, есть или нет там этой Local Color Table после чего делать или не делать нужные отступы под эту таблицу. Ну и потом еще должен идти Image Data, так что для получения следующего блока по-любому придется считать какие-то отступы. Время доступа будет O(n). А если мы знаем, где у нас gif.block[1233] и нам надо получить gif.block[1234] то это решается элементарно, можно сравнить это со связными списками. Притом это API для доступа к произвольному элементу будет скорее всего невостребовано, и лишь займет лишнее место. Если тому же эмбеддщику надо используя микроконтроллер воспроизвести анимированный gif на какой-нибудь экранчик, ему вот эти вот gif.block[1234] совершенно не нужны, ему будет достаточно последовательного чтения всех этих блоков, что-то типа итератора.

Чтобы угодить эмбеддщикам, неплохо было бы подумать над тем, чтобы генерировать более узкоспециализированные парсеры бинарных форматов.

Во-вторых, судя по статье на хабре https://habrahabr.ru/post/281595/ основная область применения это разбор неких проприетархых форматов, а не создание эффективного кода для разбора структур с цель последующего «боевого» применения. В таком случае не совсем понятно, зачем нужно делать компиляторы для C и C++. Да и компиляторы-то не особо нужны, вполне хватило бы интерпретатора

SZT ★★★★★
()
Последнее исправление: SZT (всего исправлений: 1)
Ответ на: комментарий от SZT

Можно использовать отображение файла в память (mmap в *nix, MapViewOfFile в виндах) и тогда никаких проблем. Это уже будет забота ОС с ее механизмом подкачки.

Скорее всего да, но до тех пор, пока такой механизм есть. Значит, надо иметь как минимум 2 варианта работы: «через mmap», «через буферизированное чтение + разбор из буфера».

Если мы по условию не можем опираться на всякие #pragma pack для «уплотнения» структур, то придется от структур как таковых вообще отказаться, и делать memcpy прямо в тип нужной битности (прямой каст указателя и разыменование с unaligned read это UB)

Ну, то есть мы и приходим ровно к тому, к чему приходят 95% людей, делающих это в C: пишется отдельный набор процедур типа «зачитать uint32_t в LE», «зачитать int16_t в BE» и т.д. И, внезапно, KS runtime - это и есть такой набор процедур.

Да, вероятно, для платформ, где можно опираться на форсирование packed struct - можно сделать оптимизацию - memcpy'ить + typecast'ить (т.е. по сути «парсить») не отдельные поля, а структуры фиксированного формата. Будет чуть быстрее, но принципиально механизм не меняется.

Ну тут во-первых возникает закономерный вопрос: а насколько сильно подобное API раздует и усложнит итоговый код? Насколько это будет востребовано среди тех, кому нужно будет генерировать код в Си?

Для подавляющего большинства языков средне-высокого уровня, типовые библиотеки работающие с форматами (см. те же libpng, libjpeg, libtiff, libogg и т.п.) предоставляют именно подобный API. В том числе для C.

Под block у нас понимается то, что названо тут как Image Descriptor

Вообще-то в gif.ksy, blocks - это массив всех блоков. И local_screen_descriptor - это всего лишь один из них. То, что в gif.ksy не описаны другие блоки - это недоработка gif.ksy, а не принципиальная позиция «мы ищем среди всех только такой».

Во-вторых, судя по статье на хабре https://habrahabr.ru/post/281595/ основная область применения это разбор неких проприетархых форматов, а не создание эффективного кода для разбора структур с цель последующего «боевого» применения.

Я не вижу тут сильного противоречия. Компиляторы C и C++ народ просит примерно в каждом упоминании KS. То, что вы предлагаете - по сути весьма экстремальный вариант, когда у угоду производительности нарушаются фундаментальные архитектурные принципы - сериализация/десериализация и какое-то действие над данными смешиваются в одном коде. Я не спорю, что иногда это нужно и оправданно, но считать это среднестатистично всех устраивающим случаем, как мне кажется, странно. Опять же, если посмотреть на большинство библиотек работы с бинарными файловыми форматами - типа приведенных выше - они построены по принципу API-к-структурам-данных.

GreyCat ★★
() автор топика
Ответ на: комментарий от GreyCat

Вообще-то в gif.ksy, blocks - это массив всех блоков. И local_screen_descriptor - это всего лишь один из них.

Т.е. выходит что я не могу пользуясь API просто взять и получить скажем 3-й кадр из gif, мне придется еще писать некий код, который бы перебирал в цикле все эти blocks начиная с первого и находить в них третий встретившийся блок с нужными свойствами? При этом каждый запрос n-того блока будет отбирать O(n) времени т.к. при каждом запросе block[n] надо пройтись по всем блокам, начиная с самого первого? По-моему это очень неэффективно.

SZT ★★★★★
()
Ответ на: комментарий от SZT

Blocks парсятся один раз, собираясь в массив, после чего к произвольному блоку по номеру можно обращаться за условно константное время. Выборка «n-ный по порядку block с заданными свойствами» в тупом варианте делается, разумеется, перебором всех blocks за O(n). Если это делается один-два раза - то 2*O(n), как известно, равносложно O(n). Если это надо делать чаще и это узкое место - разумеется, первое, что нужно сделать - завести где-то рядом отдельную структуру, которая будет содержать мэппинг «индекс кадра -> ссылка на block» и затем обращаться через этот мэппинг.

Теоретически это можно бы сделать даже средствами KS, добавив на один уровень с blocks то, что у нас называется instance примерно такого вида:

instances:
  frames:
    value: 'blocks.filter { |x| x.признак == нужное_значение }'

После такого - обращаясь к gif.frames[3] мы получаемый искомый «3-й по порядку кадр». Вычисление, кстати, lazy, поэтому не обращаясь к gif.frames мы даже эти самые O(n) не тратим.

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

GreyCat ★★
() автор топика
Ответ на: комментарий от SZT

Любопытный приём, разбираю его.

А что эта строчка делает, какой смысл в этой проверке:

  if( (dataptr + sizeof(gif)) > gifsz+gifsample ) goto fail;

* dataptr это указатель на gifsample, т.е. адрес gifsample/изображения.
* sizeof(gif) это размер структуры gif в байтах
* dataptr + sizeof(gif) это адрес gifsample + размер структуры gif в байтах
* gifsz это sizeof(gifsample), равен 916 байтам
* gifsample это адрес изображения.
* gifsz + gifsample это размер gifsample + его адрес.

Получается что проверяется:
(адрес gifsample + размер структуры gif) > (адрес gifsample + размер gifsample)

Могли бы вы прояснить смысл и цель этой проверки?

ProtoH
()
Ответ на: комментарий от ProtoH

dataptr это указатель на gifsample, т.е. адрес gifsample/изображения.

dataptr в ходе разбора смещается т.е. при каждом успешном чтении куска из входного файла, dataptr увеличивается на размер этого куска. А в самом начале dataptr равен адресу начала т.е. gifsample. gifsz это размер gif в байта. gifsz+gifsample это адрес конца того gif файла, который мы разбираем. dataptr + sizeof(gif)) это тот адрес, которому будет равен указатель dataptr после извлечения структуры gif из памяти:

  if( (dataptr + sizeof(gif)) > gifsz+gifsample ) goto fail;
  
  memcpy (&a, dataptr, sizeof(gif));
  dataptr += sizeof(gif);
Если мы при извлечении структуры gif пересекаем адрес границы конца файла (т.е. gifsz+gifsample) мы прочитаем какой-то мусор или будет ошибка сегментации. Эта проверка проверяет такой случай. Хотя тут на первом шаге хватило бы проверки вида if (sizeof(gif) > gifsz) т.к. dataptr и gifsample совпадают

SZT ★★★★★
()
Ответ на: комментарий от SZT

Если мы при извлечении структуры gif пересекаем адрес границы конца файла

Но до этой команды, нет никакого извлечения структуры gif:

size_t gifsz = sizeof(gifsample);

int main(void)
{
  uint8_t *dataptr = gifsample;
  
  gif a;
  if( (dataptr + sizeof(gif)) > gifsz+gifsample ) goto fail;


Даже эта проверка:
if (sizeof(gif) > gifsz)

не очень понятна.

ProtoH
()
Ответ на: комментарий от ProtoH

Но до этой команды, нет никакого извлечения структуры gif:

А оно и не должно быть до этой проверки. Это извлечение структуры

  memcpy (&a, dataptr, sizeof(gif));
идет сразу после условия. Надо сначала проверить, есть ли в нашем файле достаточное количество байт, чтобы мы могли прочитать из него в структуру gif, и только после этого через memcpy копируется часть файла в структуру и разбирается. Если размер структуры gif больше чем тот файл, разбор которого мы осуществляем, мы прекращаем парсинг этой самой структуры, т.к. смысла в этом никакого нет, goto fail;.

SZT ★★★★★
()
Последнее исправление: SZT (всего исправлений: 1)

Любопытно.

Мне на FOSDEM какой-то околоКДЕшник что-то такое проталкивал пару лет назад. Не помню чего это было и не знаю сделали ли они чего-нибудь. Целью было писать парсер закрытых форматов один раз и использовать потом в Калигре, ЛО и далее везде.

Почти десять лет назад натыкался на «визуальный редактор» написанный на жабе. Тормозной-падучий и на тот момент уже брошенный автором. Дата-что-то там, найти его заново не сумел.

В большинстве форматов, с которыми приходилось иметь дело использовалось сжатие. В нормальных LZ/deflate, у «затейников» по-разному. MS - две нестандартных вариации на тему LZ, Corel (не в CDR) - какой-то RLE на стероидах, Apple (Numbers/Pages etc) - вроде LZ с плюшками (не помню уже).
Для нормальных проще всего было бы дать возможность указать на необходимость вызова стандартных распаковщиков, для остальных без bitfields ловить нечего.
(В доки не смотрел, как вообще... можно заинлайнить один ksy внутри другого, чтобы для композитных форматов хернёй не заниматься?)

Затеете делать нормальный визуальный редактор — пинганите, помогу советом.

frob ★★★★★
()
Ответ на: комментарий от GreyCat

IMNSHO, есть противоречие между

Pure C компилятор - тоже совершенно не панацея в современном мире

и

…мне не столь интересен компилятор как таковой, сколько установление какого-то порядка и общеупотребительного стандарта

Чтобы «установить какой–то порядок» нужно сообщество, использующее данный стандарт. Чтобы появилось сообщество — нужны доступные инструменты, которые было бы желание использовать (think OllyDbg). Либо критическая масса наработок, востребованных настолько, что это оправдывает неудобства. Чтобы появились наработки — опять же, нужны удобные инструменты для тех, кто эти наработки создаёт. Граф замыкается. :D

Вопрос, сильно ли пересекаются множества низкоуровневых кодокопателей и любителей Scala и прочей функциональщины?

Вот, прям со своей колокольни: идея нравится, хотелось бы помочь, но как оно там всё фурычит — чисто колдунство. Даже для написания документации нужно хоть какое–то понимание внутреннего устройства и возможностей инструмента.

Пока что, в процессе создания и отладки шаблона компилятор используется часто и итеративно. Для визуализации тоже нужен компилятор, либо продукт его выхлопа для всех шаблонов в комплекте. Будь компилятор встраиваемой библиотекой — был бы смысл включать его в анализаторы/хексредакторы/и т.п. профильный софт. Использование JRE убивает этот вариант на корню (ну, разве что в Eclipse пропихнуть).

И, как показывает этот тред, предполагаемым пользователям проще наколхозить, а то и вовсе скопипастить из дизасма/hexrays кусок кода под задачу, непосредственно на сях, и не грузить голову лямбдами и ямбдлами :D

Текущая инкарнация KS на Scala - уже четвертая. Три предыдущих (какие-то наметки и попытки года эдак с 2008-2009) были написаны соответственно на Java, Ruby и еще раз на Ruby.

Не поверите, у меня крутится идея универсального скриптабельного инструмента примерно с тех же времён. К счастью, ни во что так и не вылившаяся — а то вышло бы ещё одно чудовище Франкенштейна, вроде вышеупомянутого QuickBMS. Который, в общем, работает и не так плох… если не обращать внимания на прибитость гвоздями к -m32 и пласты нетестируемого и неподдерживаемого кода…

…и вот вопрос, надо ли поддерживать их все, или поддерживать какие-то параметризуемые реализации…

Или таки дать пользователю самостоятельно определять processing, реализовав хотя бы минимум побитовой логики (не ксором единым!) и регистры. Хотя, так понимаю, есть желание уехать на «чисто декларативном» формате настолько далеко, насколько получится? Да, возможно реализовать какие–то базовые алгоритмы, но ведь это же для всех плафторм ещё и поддерживать придётся? Пусть даже и в форме биндингов к общеупотребимым библиотекам.

Quote
()
Ответ на: комментарий от Quote

Вопрос, сильно ли пересекаются множества низкоуровневых кодокопателей и любителей Scala и прочей функциональщины?

Кодокопателям нужны удобные инструменты, хоть на брэйнфаке написаные — пофиг.

frob ★★★★★
()
Ответ на: комментарий от frob

Мне на FOSDEM какой-то околоКДЕшник что-то такое проталкивал пару лет назад.

У KDEшников есть Okteta, внутри которой есть structure definitions. К сожалению, там как и в большинстве подобных инструментов, декларативность кончается, как только нужно сделать какой-нибудь банальный seek на смещение по прочитанному слову + 1 - и начинается банальный JavaScript.

Для нормальных проще всего было бы дать возможность указать на необходимость вызова стандартных распаковщиков, для остальных без bitfields ловить нечего.

Да и с bitfields скорее всего ситуация сильно не улучшится. Ну, будет какой-нибудь битовый поток, который мы разметим и красиво покажем (что, мол, вот - это - два битика, который отвечают за то, что следующие двадцать пять битиков считать литерально несжатой частью потока). Дальше есть две практические проблемы и одна идеологическая:

1. Как из этого красиво размеченного дерева объектов получить исходный поток байт, который рядовому человеку собственно нужен? Нужно написать какую-то функцию, которая соберет кусочки в поток - и в теории ее даже можно написать средства ksy, описав вычислимый instance.

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

3. Это все страшно неоптимально: мы зачем-то разметим в памяти практически каждый битик объектом (а это обычно что-то в районе 32-64 байта на такой битик), только для того, чтобы прогнать по этому функцию сборки. Вот SZT активно агитирует за подход, когда параллельно происходит чтение и какое-то действие (в данном случае - запись в новый поток распакованного, исходя из прочитанного) - и в данном случае я всеми руками за то, чтобы с ним согласиться. Как-то глупо тянуть собственную реализацию libz / lz / lzma / whatever, когда есть уже годами отлаженная и оптимизированная стандартная.

Даже когда речь идет о реверсинге каких-то проприетарных форматов - я сколько сталкивался с кастомными схемами сжатия: в подавляющем большинстве случаев проще вытащить распаковщик как есть из прошивки и просто вызывать. Собственно, KS этому совершенно не мешает и в любой момент можно переходить от структур к императивному языку (выдав raw byte array) и обратно (запросив разметку byte array новой структурой).

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

Да, можно использовать типы, определенные в одном ksy, в другом. Визуализатору можно указать много ksy: ksv file.bin format1.ksy format2.ksy... - парсинг начнется с format1.ksy, все остальные будут использованы по мере вызова из format1.ksy.

Затеете делать нормальный визуальный редактор — пинганите, помогу советом.

Принято :) «Визуальный редактор» - это в смысле когда вообще код писать руками не надо, а собирать структуры из блоков?

GreyCat ★★
() автор топика
Ответ на: комментарий от SZT

Если размер структуры gif больше чем тот файл, разбор которого мы осуществляем, мы прекращаем парсинг этой самой структуры, т.к. смысла в этом никакого нет

Кстати, при отладке или работе с незнакомым форматом это совершенно вредное поведение ;) В KS для этого есть опция --debug, которая как раз его переключает (т.е. заставляет делать best effort parsing - парсить, пока не упрешься в очередное поле, которое уже нельзя прочитать, потому что end of stream).

GreyCat ★★
() автор топика
Ответ на: комментарий от Quote

Вопрос, сильно ли пересекаются множества низкоуровневых кодокопателей и любителей Scala и прочей функциональщины?

У меня встречный вопрос: сколько низкоуровневых кодокопателей умеют и хотят писать компиляторы? В самой Scala ничего страшного нет - вполне себе мейнстримный язык уже. Чтобы пользоваться каким-нибудь новым модным инструментом (ну, не знаю там, взять Heron, Spark или еще-одним-MQ-на-Erlang) - совершенно не обязательно прямо сейчас бросаться его дописывать.

Вот, прям со своей колокольни: идея нравится, хотелось бы помочь, но как оно там всё фурычит — чисто колдунство. Даже для написания документации нужно хоть какое–то понимание внутреннего устройства и возможностей инструмента.

Вы не обижайтесь, но пока это больше похоже на отговорку. Я уже на вполне живых примерах людей, пришедших в проект видел, что если есть желание помочь - то все вполне реально. Хочешь поддержку нового языка - welcome - тебе не нужно знать вообще ничего из Scala, нужно как раз хорошо знать свой целевой язык - примерно 70% работы по поддержке нового языка - писать, проверять код на нем самом (а не на Scala!) и думать, как совместить концепции KS и своего языка.

Да и по большому счету в Scala нет ничего страшного. Поддержку C# у нас сделал примерно за 2-3 недели человек, который до этого кроме C# толком ничего не видел и не признавал.

Пока что, в процессе создания и отладки шаблона компилятор используется часто и итеративно. Для визуализации тоже нужен компилятор, либо продукт его выхлопа для всех шаблонов в комплекте.

Так точно. Вас так сильно смущает необходимость дописать в Makefile (или его аналог) очередное правило для ksy -> .ваш-язык? Или то, что визуализатор (в его текущей инкарнации) прямо таки литерально запускает компилятор, абсолютно ничего не предполагая о его внутреннем устройстве?

Будь компилятор встраиваемой библиотекой — был бы смысл включать его в анализаторы/хексредакторы/и т.п. профильный софт. Использование JRE убивает этот вариант на корню (ну, разве что в Eclipse пропихнуть).

Ой, бросьте. Вот был компилятор написан на C или на C++ - кому было бы сильно легче? Лидирующих IDE сейчас примерно 3-4: MSVS, IDEA, Eclipse, в какой-то степени - Xcode. Кому из них полегчало бы, если бы была библиотека на C? MSVS написана на C# (и extensions к ней пишутся преимущественно на .NET-платформе), IDEA и Eclipse - на JRE, Xcode - может быть, но что-то мне подсказывает, что и там тупо проще запустить компилятор, как отдельный процесс.

Куда еще имеет смысл встраивать компилятор и зачем встраивать, если можно вызвать (или даже еще банальнее - если можно на коленке написать интерпретатор)?

И, как показывает этот тред, предполагаемым пользователям проще наколхозить, а то и вовсе скопипастить из дизасма/hexrays кусок кода под задачу, непосредственно на сях, и не грузить голову лямбдами и ямбдлами :D

Использовать то, что знаешь и чем пользуешься - всегда проще, чем изучать что-то новое. Лямбды тут вроде бы совсем не при чем.

вроде вышеупомянутого QuickBMS. Который, в общем, работает и не так плох…

Да как раз скорее плох. Как только возникает мысль плавного перехода от этих вот кулхацкерских потуг типа «я заменил текстуру на стенке в моей любимой игре» до чего-то чуть более серьезного, типа «хочу разбирать файловую систему в моем новом инструменте» - QuickBMS внезапно оказывается как-то не у дел. И все наработки, которые там были, скорее всего придется выкинуть и переделать, т.к. автоматом это во что-то не конвертировать.

Или таки дать пользователю самостоятельно определять processing, реализовав хотя бы минимум побитовой логики (не ксором единым!) и регистры.

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

GreyCat ★★
() автор топика
Ответ на: комментарий от GreyCat

Вопрос, сильно ли пересекаются множества низкоуровневых кодокопателей и любителей Scala и прочей функциональщины?

У меня встречный вопрос: сколько низкоуровневых кодокопателей умеют и хотят писать компиляторы?

О том и речь. Точек пересечения в обоих случаях — единицы. =(

Продолжу цепочку вопросов: а как вы себе представляете (будущих?) пользователей KS? Кто эти люди и зачем он им нужен?

Использовать то, что знаешь и чем пользуешься - всегда проще, чем изучать что-то новое. Лямбды тут вроде бы совсем не при чем.

Хм. Полагаю, изначальный посыл был не понят. Наверное, из–за термина «прочая функциональщина», показавшегося оскорбительным. Проблема не в Scala и не в Ruby. Проблема в том, что всем этим вместе, как оно есть сейчас, не очень–то удобно пользоваться.

Вас так сильно смущает необходимость дописать в Makefile (или его аналог) очередное правило для ksy -> .ваш-язык?
Лидирующих IDE сейчас примерно 3-4: MSVS, IDEA, Eclipse, в какой-то степени - Xcode.

Чувакам с MSVS/IDEA/Eclipse/Xcode не нужны какие–то мутные .ksy–файлы, у них есть libsomething и libsmthelse. И даже если найдётся какой–нибудь эксклюзивный формат — опять же, им не нужен компилятор, достаточно раз в релиз делать выхлоп по всем форматам для всех платформ и класть на гитхаб. Всё. И добавлять в Makefile строчку, чтобы потом к исходникам притащить компилятор и JRE становится совершенно незачем.

Вся мощь и красота KS, IMHO, как раз и заключается в возможности последовательного динамического разбора и визуализации. То, что на выходе ещё получается готовый парсер — бонус, причём бонус офигенный, но процессу собственно разбора не способствующий.

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

Повторюсь: IMHO, чтобы KS выстрелил как «общеупотребительный стандарт» референсом должна быть встраиваемая библиотека, которую легко добавить куда угодно и получить «из коробки» поддержку кучи форматов. Пусть не универсальный компилятор, пусть «интерпретатор, который можно написать на коленке». Но лёгкий, с минимумом зависимостей и впихиваемый хоть в суперкомбайн для реверсинга всего и вся, хоть в мимимишный хипстерский хекс–редактор, хоть в «super–analyzer by Vasya[OMFGTeam]», хоть в плагин для FAR/TotalCmd, IDA или Olly. Чтобы уже пользователи этих продуктов могли допиливать библиотеку .ksy–файлов по мере возникающих потребностей.

Который, в общем, работает и не так плох…

Да как раз скорее плох.

Извиняюсь, забыл табличку. Впрочем, по сравнению с подобными проектами, будь то UN-PACK (by Snow Panther), UniExtract, MultiEx, тысячи их — QuickBMS уже выглядит как шаг вперёд. :)

Или таки дать пользователю самостоятельно определять processing…

И получится в лучшем случае haXe, в худшем - какой-то совершенно отдельный минималистичный императивный язык

А по–моему, наоборот. В худшем случае, получится haXe, который по сложности требуемого разбора недалеко ушёл от прародителя — ECMAscript, да и излишен абсолютно. А требуется минимальный набор команд, являющийся общим знаменателем для всех поддерживаемых платформ, но позволяющий реализовать распаковщик либо криптопримитив. Эдакий платформо–абстрагированный ассемблер, чуть сложнее брейнфака.

С которым людям придется еще отдельно точно так же разбираться, отдельно мучаться с регистрами и его опкодами и т.д.

При этом, .ksy–синтаксис уже сам по себе язык. Небольшой, декларативный и основанный на YAML, но тем не менее, «приходится разбираться».

Quote
()
Ответ на: комментарий от GreyCat

Okteta

Не уверен. Вроде речь шла про что-то чего ещё не совсем есть. Попробую в сентябре узнать, как друг из отпуска вернётся, может он чего вспомнит.

bitfields

Не стану скрывать: я скептически отношусь к перспективам широкого использования этого ПО за пределами разбора форматов/протоколов.
Теоретически возможно, что кто-то воспользуется распаковкой с дописыванием транслятора из получающегося выхлопа в свою модель и получит «фильтр импорта». Но для простых и/или распространённых форматов сложно увидеть выгоду, а сложные для начала надо описать в ksy и не слишком понятно насколько сложно будет транслировать. Хотя представить себе «давайте не будем тянуть libpng, libjpg ...(длинный список)... , а вместо этого возьмём кайтай и пачку ksy» где-то где туго с доступной памятью я наверное могу.

bitfields
2 (провернуть фарш назад)

Ну, разжимать проще чем сжимать, это понятно.
Как-то сложно представить себе LZ-подобное (да пусть даже и не примитивное RLE) сжатие описанное только структурами данных.

Вообще, чтобы записать более-менее сложный формат надо как правило знать о нём гораздо больше, чем для того чтобы его достаточно адекватно прочитать. Простейший пример — вычисляемая неизвестным способом контрольная сумма: при чтении на неё можно забить, а для записи надо знать как посчитать.

bitfields
1 (как из этого красиво размеченого ...)

Давайте на примерах... Чтобы было веселей возьмём MS Visio VSD... =)

Это CFB-контейнер. Прежде чем удастся хоть что-то полезное сделать, надо из него выдернуть отдельные потоки. Если разбирать CFB на уровне KS, то разобранное надо правильным собирать, чтобы передать дальше.
Основной поток можно довольно просто разрезать на «заголовок», «данные» и что-то вроде ToC. KSY для этого вполне подойдёт. ToC указывает на блоки (смещение/длина) в «данных» и содержит информацию о том как эти блоки трактовать (пока всё нормально с т.з. описания в KSY).
Дальше хуже: часть блоков сжата нестандартным вариантом LZ. Значит надо или описать это в KSY (биты в токенах) или добавить где-то как-то функцию для распаковки (ну и упаковки, если толщина кишок позволяет).
Распакованные блоки надо парсить дальше. В этих блоках следующий уровень «засад»: для начала часть из них полные аналоги ToC. Блоки надо порезать на «записи» и в этой части всё нормально, за исключением того, что большие блобы могут быть разбиты на несколько последовательных записей, из которых данные блоба надо будет выковыривать и собирать вместе... чтобы получить НЕЧТО, что возможно тоже надо будет разбирать (ладно, если это PNG, можно просто сказать «а вот тут PNG» и затихнуть в углу, а если «неизвестный науке зверь»? =)

Как видно происходят неоднократные выдирание-складывание данных, так что без передачи их туда-сюда не обойтись.

bitfileds
3 (страшно неоптимально... проще вытащить распаковщик)

Откуда вытащить распаковщик для Apple Pages? =)

ТрусЫ и крестик...
Если KS предназначен для разбора, то надо предоставлять возможность взять что-то покрытое загадочными пупырышками и разобрать на лапки и глазки. Потом, когда понятно как оно устроено, где «неонка» и откуда «возникает синкдоха отвечания», можно написать функцию распаковки или чего ещё понадобится, для оптимизации. Но сначала-то надо это как-то разобрать...

Если же KS для того, чтобы вколотить формат разобранный где-то ещё в KSY, то встаёт вопрос надо ли на это вообще тратить время.

использовать типы

Это хорошо. В целом было бы неплохо иметь возможность ссылаться на любые описанные типы без необходимости их перечислять при запуске, но это уже мелочи.

«Визуальный редактор» - это в смысле когда вообще код писать руками не надо, а собирать структуры из блоков?

Если под «кодом» понимается KSY, то почему бы и не писать, кому удобно-привычно. Вопрос в том, чтобы видеть что из этого получается прямо там где пишешь. И иметь возможность сказать: «вот тут у нас 5 (50... 500...) файлов в этом формате, проверяй на них всё что меняем/добавляем и показывай, если на каком-то сломался разбор». Или «вот тут у нас будет такая структура, покажи все варианты значений для вот этого элемента из таких-то файлов».

«Командная строка» в редакторе с возможностью указать смещение и написать (в виде KSY) чего там по нашему мнению находится, подойдёт хотя бы как PoC.

С тем чтобы полезным образом визуализировать хаос вроде VSD или тем паче FreeHand, видимо придётся экспериментировать.

frob ★★★★★
()
Ответ на: комментарий от GreyCat

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

Кстати, файловая система это тема. Вот предположим у нас есть такая ФС (сам вот только что придумал):

0x4d,0x79,0x46,0x53  | -> MyFs (header)


0x46,0x69,0x6c,0x65, |
0x6e,0x61,0x6d,0x65, | -> Имя файла (asciiz:"Filename_1")
0x5f,0x31,0x00       |

0x00, 0x00           | -> 16-bit unsigned value - адрес начала файла "Filename_1" относительно конца описания

0x46,0x69,0x6c,0x65, |
0x6e,0x61,0x6d,0x65, | -> Имя файла (asciiz:"Filename_2")
0x5f,0x32,0x00       |

0x20, 0x00           | -> 16-bit signed value - адрес начала файла "Filename_2" относительно конца описания

0x00                 | -> Конец описания
Далее должны идти сами файлы, но фокус весь в том, что файлы могут быть хитрым образом фрагментированы, информация о том, где будет следующий кусок (если он есть) будет кодироваться в некоем заголовке в самом каждом куске файла. Т.е. у каждого куска файла будет некий бит отвечает на вопрос, есть ли у этого файла еще фрагменты. И этот фрагмент может быть размещен перед самой «головой» файла. Фактически, это может выглядеть как-нибудь так
  +-------------------------+
  |                         |
  |  { {заголовок {   адрес_хвоста   } }файл1(начало) }
  |  { {заголовок {больше_нет_частей } }файл2(конец)  }<-+
  +->{ {заголовок {больше_нет_частей } }файл1(конец)  }  |
     { {заголовок {   адрес_хвоста   } }файл2(начало) }  |
                            |                            |
                            +----------------------------+
А в самом «описании» в файловой системе нет никакой информации ни о фактическом размере файла, ни о числе и расположении фрагментов. Только имя самого файла и адрес «головы». Более того, если есть два файла, у которых например отличаются только первые 100 байт, а вся последующая часть полностью совпадает, они вполне могут ссылаться на одну и ту же область памяти, и это не будет являться ошибкой файловой системы. Может ли KS эту ситуацию «разрулить»?

SZT ★★★★★
()

Да, кстати. В рамках квадратно–гнездовой ковровой бомбардировки:

— cast XVilka

— cast ValdikSS

И ещё вопрос: уютного чатика у проекта ещё нет? Ну там, конфа в Tox, Jabber или на IRC?

Или всё общение слать почтой автору? :D

Quote
()
Ответ на: комментарий от Quote

И ещё вопрос: уютного чатика у проекта ещё нет? Ну там, конфа в Tox, Jabber или на IRC?
Или всё общение слать почтой автору? :D

Пока есть e-mail'ы, github и twitter. За все время человек 5 уже спрашивало про чатики / мейллисты / форумы / что-нибудь такое - но после вопроса «что вам будет удобно - давайте создам» - люди куда-то исчезали. Итак, что вам было бы удобно? ;)

GreyCat ★★
() автор топика
Ответ на: комментарий от SZT

Может ли KS эту ситуацию «разрулить»?

С рекурсивными ссылками и чтением произвольных мест из файловой системы как раз абсолютно никаких проблем нет.

Это будет что-то типа:

types:
  fragment:
    seq:
      - id: frag_size
        type: u4
      - id: next_frag_ofs
        type: u4
      - id: contents
        size: frag_size
    instances:
      next_frag:
        pos: next_frag_ofs
        type: fragment
        if: next_frag_ofs != 0 # ну или еще какое-нибудь условие на битик "есть ли еще фрагменты"

Проблемы в версии 0.4 будут с куда более прозаичными вещами: чтение «до 0x00 в каком-то поле» требует конструкцию repeat-until, которая в 0.4 не вошла.

GreyCat ★★
() автор топика
Ответ на: комментарий от GreyCat

но после вопроса «что вам будет удобно - давайте создам» -
люди куда-то исчезали. Итак, что вам было бы удобно?

А если Quite теперь исчезнет?.. =)

frob ★★★★★
()
Ответ на: комментарий от GreyCat

но после вопроса «что вам будет удобно - давайте создам» - люди куда-то исчезали. Итак, что вам было бы удобно? ;)

Не дождётесь! :D

Думаю, было бы вежливо первым делом поинтересоваться у Дэниела и Накамуры.

Персонально нам удобно любое из вышеперечисленного. В качестве основного мессенджера используется tox, но он пока всё ещё не очень пользователедружелюбен и для удержания конфы придётся поднимать бота.

Канал на IRC обычно не требует лишних телодвижений, поскольку ChanServ. На FreeNode, например, есть SSL, поддержка UTF–8 и вход через веб.

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

Quote
()
Ответ на: комментарий от frob

Вообще, чтобы записать более-менее сложный формат надо как правило знать о нём гораздо больше, чем для того чтобы его достаточно адекватно прочитать.

Именно. Собственно, задача вполне себе классическая и хорошо исследованная - это вывод обратной функции. Это ровно то, чем «запись» отличается от «чтения». Огромное количество тех, кто уже ходил по этому пути (типа Preon и Construct) делают очень банально: заставляют человека писать вручную обе функции преобразования - и назад, и вперед. В идеале бы, конечно, для простых вещей типа:

seq:
  - id: len
    type: u4
  - id: some_buf
    size: len + 5

уметь выводить, что поле «len» - зависимое от длины поля «some_buf» и при записи достаточно записать в some_buf какой-то массив, а в len само подставится его длина минус 5.

Дальше хуже: часть блоков сжата нестандартным вариантом LZ. Значит надо или описать это в KSY (биты в токенах) или добавить где-то как-то функцию для распаковки (ну и упаковки, если толщина кишок позволяет).

Вот в этот момент я явно вижу тот водораздел, где абсолютно нет смысла пытаться прыгать выше головы. Компрессия в чистом виде (поток байт туда - поток байт обратно) - это то, что надо делать где-то отдельно, а не средствами KSY. Сделанное «отдельно» можно привнести в рантайм KS, а можно, на самом деле, и не привносить. Ну, будет не один красивый гигантский .ksy, который парсит формат Visio от начала до самых глубокин, а будет 2-3 отдельных подформата. Если тебе нужна только часть функций, скажем, какое-нибудь извлечение метаинформации - то ты скорее всего обойдешься одним из этих подформатов (верхнего уровня) и не будешь думать об этом кастомном LZ-сжатии. Если нужно лезть глубже - будь добр, принеси (или перепиши) функцию этого сжатия-разжатия на своем языке и вызови KS дважды:

def uncompress_custom_lz(buf):
    # ...

visio_file = MsVisioFile.from_file("foo.vsd")
compr_block = visio_file.blocks[42]
uncompr_block = uncompress_custom_lz(compr_block)
parsed_block = MsVisioBlockFooBar(KaitaiStream(compr_block))

В этих блоках следующий уровень «засад»:

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

Откуда вытащить распаковщик для Apple Pages? =)
ТрусЫ и крестик...

Все очень просто: есть два, на мой по крайней мере взгляд, совершенно разных вида разбора: исследование white box (т.е. по большому счету у нас есть доступ к исходному алгоритму, мы лезем туда дизассемблером-отладчиком и копаемся) и black box (к исходному алгоритму не лезем, все чисто на догадках). KS есть смысл использовать для black box. Разбор механизма сжатия почти всегда сильно проще и быстрее сделать как white box - т.е. тупо влезть в Apple Pages хоть теми же уже упомянутыми IDA/hexrays/radare и выдрать эти функции «как есть». Выдираются они, как правило, хорошо, т.к. это совершенно обособленный кусок программы, у которого на входе - поток, на выходе - поток.

Если под «кодом» понимается KSY, то почему бы и не писать, кому удобно-привычно. Вопрос в том, чтобы видеть что из этого получается прямо там где пишешь. И иметь возможность сказать: «вот тут у нас 5 (50... 500...) файлов в этом формате, проверяй на них всё что меняем/добавляем и показывай, если на каком-то сломался разбор». Или «вот тут у нас будет такая структура, покажи все варианты значений для вот этого элемента из таких-то файлов».

Принято, в целом идеи интересные. До сих пор это делалось в паре нескольких открытых окошек: текстовый редактор с .ksy + визуализатор, либо ksy + простенький скриптик на 3 строчки + результат его запуска. Поредактировал -> проверил -> поредактировал -> проверил -> ...

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

«Командная строка» в редакторе с возможностью указать смещение и написать (в виде KSY) чего там по нашему мнению находится, подойдёт хотя бы как PoC.

Честно говоря, не понял. В каком редакторе, какая командная строка, зачем?

Вы, кстати, 010 и Hexinator, наверняка видели?

GreyCat ★★
() автор топика
Ответ на: комментарий от Quote

Думаю, было бы вежливо первым делом поинтересоваться у Дэниела и Накамуры.

Спрашивал, у них большого энтузиазма к интерактивному общению не заметно. Кроме того, Дэниел живет в UTC+11, Накамура, насколько я понимаю, в UTC+9 и это тоже прилично урезает возможность интерактива с Москвой или Европой. Кроме того, Накамура мне несколько раз явно писал, что в принципе против чатов по идеологическим соображениям. Ну, его право.

Персонально нам удобно любое из вышеперечисленного.

С точки зрения массовости (и, как следствие, хоть какой-то пользы для коммьюнити) я сейчас, к сожалению, вижу что дико популярным становится gitter (мне лично не нравится, но что делать), на втором месте, наверное, IRC и XMPP примерно поровну. Проекты типа Radare сидят олдскульно на Freenode. tox в реальной жизни я не видел примерно нигде.

В общем, не знаю %)

GreyCat ★★
() автор топика
Ответ на: комментарий от anonymous

Когда-нибудь, если все будет хорошо - будет. Присоединяйтесь, давайте вместе делать. Это не так сложно, как кажется.

GreyCat ★★
() автор топика
Ответ на: комментарий от Quote

Продолжу цепочку вопросов: а как вы себе представляете (будущих?) пользователей KS? Кто эти люди и зачем он им нужен?

Можно вводить кучу классификаций, но в первую очередь, как мне кажется - это два вида разработчиков:

1. Те, кому надо встроить поддержку какого-то формата в свой софт; они возьмут готовый .ksy и основная их проблема - разобраться во внутренней логике формата, чтобы решить свою конкретную задачу. 2. Те, кому нужен удобный инструмент для реверс-инжиниринга неизвестного формата (причем дальнейшие цели могут быть совершенно различные: он написание вокруг получившегося .ksy скриптика в 2 строчки типа «выдрать файлы из прошивки роутера» до точно такой же полноценной поддержки формата в каком-нибудь массовом серверном или десктопном софте).

Проблема не в Scala и не в Ruby. Проблема в том, что всем этим вместе, как оно есть сейчас, не очень–то удобно пользоваться.

Возвращаемся к началу разговора. Вот есть gcc - вполне себе популярный компилятор. 99.9% народа вызывают его как процесс командной строки (скорее всего через систему сборки типа Makefile или проекта в IDE). В чем отличие от ksc?

Чувакам с MSVS/IDEA/Eclipse/Xcode не нужны какие–то мутные .ksy–файлы, у них есть libsomething и libsmthelse. И даже если найдётся какой–нибудь эксклюзивный формат — опять же, им не нужен компилятор, достаточно раз в релиз делать выхлоп по всем форматам для всех платформ и класть на гитхаб. Всё. И добавлять в Makefile строчку, чтобы потом к исходникам притащить компилятор и JRE становится совершенно незачем.

Да, собственно, вообще не проблема. Проблема в том, что есть попытки коммьюнити ковырять какие-то полузакрытые форматы типа тех же форматов Photoshop, всяких офисов, уже упомянутого Visio, кучи всяких коммерческих аудио-видео-фото редакторов и т.д. и т.п. — и тут налицо дикое распыление усилий (все пишут на разных языках, одно и то же надо вручную переписать много раз, проекты не могут просто так взять и воспользоваться плодами трудом друг друга). Логичный, как мне кажется шаг - выделить всю эту деятельность по работе с форматами в отдельную кросс-языковую сущность.

Ну, банально вот, посмотреть на то, что происходит с инструментами для прошивок роутеров - бардак же. Каждый переписывает все те же 20-30 скриптов по сборке-разборке прошивок то на Python, то на C++, то на PHP, то на Perl, то на каком-нибудь Go или Rust. Ошибки плодятся и множатся (а еще и мигрируют из проекта в проект), общий КПД плохой, у каждого конкретного представителя этой тусовки нет полной поддержки всего.

Разборка сетевых протоколов - по сути то же, но в профиль. Каждый второй пишет собственную реализацию разбора Ethernet/TCP/UDP/ICMP, привнося собственную долю ошибок, набивая собственные шишки. Зачем все это?

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

Что такое «встраиваемая библиотека» и что такое «поддержка кучи форматов»? И чем она отличается от запуска ksc и использования результатов его работы?

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

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

При этом, .ksy–синтаксис уже сам по себе язык. Небольшой, декларативный и основанный на YAML, но тем не менее, «приходится разбираться».

Разумеется, но тут речь о том, что параллельно с .ksy человеку нужно будет изучить еще один, совершенно другой подход (не декларативный, а сугубо императивный), со своим отдельным инструментарием и подходами.

GreyCat ★★
() автор топика
Ответ на: комментарий от GreyCat

Собрать потоки из частей - тоже по идее нет проблем.

Визуализировать всё это будет непросто — дополнительный уровень преобразований получается.

Разбор механизма сжатия почти всегда сильно проще и быстрее сделать как white box - т.е. тупо влезть в Apple Pages хоть теми же уже упомянутыми IDA/hexrays/radare и выдрать эти функции «как есть».

И как долго пройдёт от момента использования выдранных функций в свободном софте до предсказуемой реакции правообладателя?

В каком редакторе, какая командная строка, зачем?

В визуальном. Вместо контекстных менюшек на правой кнопке мыши.

Вы, кстати, 010 и Hexinator, наверняка видели?

Не видел =)
Я себе сделал небольшой редактор под свои задачи с теми функциями, которых очень хотелось при разборах, но нигде не нашлось. Коряво и быдлокодисто, зато делает то что надо мне.

frob ★★★★★
()
Ответ на: комментарий от frob

Собрать потоки из частей - тоже по идее нет проблем.

Визуализировать всё это будет непросто — дополнительный уровень преобразований получается.

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

И как долго пройдёт от момента использования выдранных функций в свободном софте до предсказуемой реакции правообладателя?

Ровно столько же, если декомпрессию сделать любыми другими средствами - «декларативным языком», «метаассемблером», «переписал алгоритм своими словами на другом языке» и т.д. Если будут претензии - то скорее всего в плане патентованности алгоритмов сжатия и нарушения патентов. Эта проблема - общая для всех способов.

Не видел =)

Вообще хотя бы для расширения кругозора - сильно рекомендовал бы ознакомиться. Идеи KS в том числе оттуда заимствованы (особенно визуализатора).

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

А где-то на него посмотреть можно?

GreyCat ★★
() автор топика
Ответ на: комментарий от GreyCat

Если вы про визуализатор - то я не вижу разницы

Про него конечно...
Если файл устроен просто, допустим «заголовок»/«данные»/«хвост», то показать это деревом (весь файл корень, а части — потомки) можно без каких-либо проблем. Получится наглядно.
А если взять какой-нибудь контейнер, хотя бы тот же CFB, то увидеть «FAT в файле» приятно, но дальше с ним надо что-то делать. Практически — показывать как из имеющегося дерева выбрать части и собрать из них другое дерево.
Для уже разобранных и/или документированных контейнеров можно было бы дать возможность переключаться между «слоями», а для неизвестного — представляется что-то вроде горизонтальной версии диаграм вроде тех какими иллюстрируют криптографические алгоритмы.

Ровно столько же, если декомпрессию сделать любыми другими средствами

Первым версиям vsdump скоро 10 лет. Первым релизам libvisio — 6. Разбор как blackbox, никаких вопросов от MS.

А где-то на него посмотреть можно?

https://github.com/renyxa/re-lab/tree/master/colupatr

frob ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.