Добавление управляющих символов в поток байтов

Question

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

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

2. Кроме того, мы можем добавить заголовки длины (+ некоторые флаги) к блоки кэшируемого размера. Это, безусловно, решение, но обработка намного больше сложнее, чем [1], особенно при кодировании (при условии, что операции ввода-вывода сделано с выровненными блоками фиксированного размера). Ну, одна из возможных реализаций - записать 0 байт в буфер, затем поток данных до его заполнения. Таким образом, префикс байта = 0 будет означать, что затем идут потоковые данные bufsize-1, и! = 0 будет означать, что там меньше ... в этом случае мы сможем вставить другой префикс байт, если достигнут конец потока. Это будет работать только с bufsize = 32k или так, потому что в противном случае длина блока потребовала бы 3+ байта для хранения, и была бы проблема с обработкой случая с концом потока когда в буфере есть только один байт свободного места. (Одним из решений этой проблемы будет сохранение 2-байтовых префиксов для каждого буфера и добавление 3-го байта при необходимости; другое - обеспечить 2-байтовую кодировку. для некоторых специальных длин блоков, таких как bufsize-2). В любом случае это не так хорошо, потому что даже 1 дополнительный байт на 64 Кб накопит на заметное количество с большими файлами (1526 байт на 100M). Также жесткое кодирование размера блока в формат тоже плохо.

3. Префикс Escape. Например. EC 4B A7 00 = EC 4B A7, EC 4B A7 01 = конец потока. Теперь это действительно легко кодировать, но декодирование довольно болезненно - требует грязный конечный автомат даже для извлечения отдельных байтов. Но в целом это добавляет минимум накладных расходов, так что, похоже, нам все еще нужно найти хорошая реализация для буферизованного декодирования.

4. Префикс Escape со всеми одинаковыми байтами (например, FF FF FF). Гораздо проще проверить, но выполнение одного и того же байта в потоке может привести к огромным издержкам (например, 25%), и не исключено, что для управляющего кода выбрано любое значение байта.

5. Постфикс Escape. Сохраните байт полезной нагрузки перед маркером - затем декодером просто нужно пропустить 1 байт перед замаскированным маркером и 4 байта для контрольного кода. Так что это в основном вводит фиксированную 4-байтовую задержку для декодера, в то время как [3] имеет сложный путь, где байты маркера должны быть возвращены один за другим. Тем не менее, с [3] кодировщик намного проще (просто нужно написать дополнительный 0 когда маркер совпадает), и это на самом деле не упрощает обработку буфера.

Обновление: На самом деле я уверен, что вариант [3] или [5] я бы использовал, Я только перечислил другие варианты в надежде получить больше альтернатив (например, это было бы хорошо, если бы избыточность была в среднем 1 бит на блок). Итак, главный вопрос atm - это способ анализа потока для [3] ... текущий конечный автомат выглядит так:

int saved_c;
int o_last, c_last;
int GetByte( FILE* f ) {
  int c;

  Start:
  if( o_last>=10 ) {
    if( c_last>=(o_last-10) ) { c=saved_c; o_last=0; }
    else c=byte("\xEC\x4B\xA7"[c_last++]);
  } else {
    c = getc(f); 
    if( o_last<3 ) {
      if( char(c)==("\xEC\x4B\xA7"[o_last]) ) { o_last++; goto Start; } 
      else if( o_last>0 ) { saved_c=c; c_last=0; o_last+=10; goto Start; } // 11,12
      // else just return c
    } else {
      if( c>0 ) { c=-1-c, o_last=0; printf( "c=%i\n", c ); }
      else { saved_c=0xA7; c_last=0; o_last+=10-1; goto Start; } // 12
    }
  }

  return c;
}

и, конечно, уродливо (и медленно)

Answer 1

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

Преимущества:

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

Недостатки:

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

Answer 2

Так что я закончил тем, что использовал в моем реальном проекте уродливый парсер из OP
(http://encode.ru/threads/1231-lzma-recompressor)

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

Answer 3

С точки зрения простоты последовательного чтения и записи, я бы взял решение 1 и просто использовал короткий буфер, ограниченный 256 байтами.Тогда у вас есть длина в один байт, за которой следуют данные.Если один поток имеет более 256 последовательных байтов, вы просто записываете другой заголовок длины и данные.

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