将控制符号添加到字节流中

Question

问题:有时我们必须将多个流交织成一个，在这种情况下，需要提供一种方法来识别流中的块边界。什么样的格式适合这样的任务？(所有处理都必须是完全连续的，i/o操作是分块和对齐的。)

1. 从解码端来说，最好的方法是为块设置长度前缀。但是在编码方面，它需要对输出文件的随机访问(寻求流开始和写入头)，或者能够缓存整个流，也就是说，通常情况下，我们可以将长度头(+一些标志)添加到可缓存大小的块中。这当然是一个解决方案，但是处理要比1复杂得多，特别是在编码方面(假设i/o操作是用对齐的固定大小的块完成的)。一个可能的实现是将一个0字节写入缓冲区，然后流数据直到它被填充。所以前缀字节=0意味着接下来有bufsize-1字节的流数据，而!=0意味着有更少的.在这种情况下，如果到达流结束，我们将能够插入另一个前缀字节.这将只适用于bufsize=32k左右，因为否则块长度将需要存储3+字节，并且当缓冲区中只有一个字节的空闲空间时，处理流尾的情况会出现问题。(解决方案之一是在每个缓冲区中存储2个字节前缀，并在必要时添加3个字节；另一个解决方案是为一些特殊的块长度(如bufsize-2)提供2字节编码)。无论哪种情况，它都不是很好，因为即使是每64k就有一个额外的字节，对于大文件(每100米1526字节)，也会累积到一个明显的数字。此外，硬编码块大小为格式也是不好的。
2. 逃逸前缀。例如：EC 4B A7 00 = EC 4B A7，EC 4B A7 01 =端流.现在，这真的很容易编码，但解码是相当痛苦的-需要一个混乱的状态机，甚至提取单个字节。但是总的来说，它增加的开销最少，因此我们似乎仍然需要为所有相同字节的缓冲decoding.
3. Escape前缀找到一个良好的实现(例如。( FF)。检查起来要容易得多，但是在流中运行相同的字节会产生巨大的开销(比如25%)，而且对于为转义代码选择的任何字节值也不太可能。
4. escape postfix。在标记之前存储有效负载字节-然后解码器只需在掩码标记之前跳过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

因此，在我的实际项目中，我使用了来自OP的丑陋解析器。

( http://encode.ru/threads/1231-lzma-recompressor )

但现在看来，实际的答案似乎是让数据类型处理程序任意终止其流，这意味着在未压缩数据的情况下可以转义编码，但是当流中使用某种熵编码时，通常可以合并更有效的EOF代码。

Answer 2

使用固定大小的块(例如1KB )如何？每个块将包含一个字节(或4个字节)，指示它是哪个流，然后它只跟踪数据。

好处：

，

• ，您不必关注数据本身。数据不能意外地触发系统的任何行为(例如，意外终止流)，
• i在编码时不需要随机文件访问。特别是，您不存储块的长度，因为它是固定的。
• ，如果数据损坏，系统可以在下一个块中恢复。

缺点：

如果您必须从流切换到流，且每个流只有几个字节的数据，则

• 可能会使用不足。很多字节将为空。
• 如果块大小太小(例如，如果您想解决上述问题)，您可以从报头获得巨大的开销。

。

Answer 3

从顺序读写简单的角度来看，我采用解决方案1，只使用一个限制在256字节的短缓冲区。然后你有一个字节的长度，然后是数据。如果单个流有超过256个连续字节，则只需写出另一个长度头和数据。

如果您有任何进一步的要求，尽管您可能需要做一些更详细的事情。例如，随机访问读取可能需要一个无法在真实数据中复制的神奇数字(或者当它出现在真实数据中时总是转义)。