c++ - 将控制符号添加到字节流

Question

问题:有时我们必须将多个流交织成一个， 在这种情况下，有必要提供一种方法来识别 block 流中的边界。什么样的格式会好 为了这样的任务？ (所有处理都必须是纯顺序的，并且 i/o 操作是 block 状和对齐。)

1. 从解码方面来说，最好的方法是使用长度前缀 对于 block 。但是在编码端，它需要随机访问 输出文件(寻求流式开始并写入标题)，或 能够缓存整个流，这通常是不可能的。

2. 或者，我们可以添加长度 header (+一些标志)到 可缓存大小的 block 。它肯定是一个解决方案，但处理更多 比 [1] 复杂，尤其是在编码方面(假设 i/o 操作 使用对齐的固定大小块完成)。 好吧，一种可能的实现是将 0 字节写入缓冲区， 然后流式传输数据直到它被填满。所以 prefix byte = 0 意味着 接下来是 bufsize-1 字节的流数据， !=0 意味着 少了……在这种情况下我们可以插入另一个前缀 如果到达流结尾，则为字节。这只适用于 bufsize=32k 左右，因为否则 block 长度将需要 3+ 字节来存储， 处理流结束的情况会有问题 当缓冲区中只有一个字节的可用空间时。 (一个解决方案是为每个缓冲区存储 2 字节前缀 并在必要时添加第三个字节；另一个是提供一个2字节的编码 对于一些特殊的 block 长度，如 bufsize-2)。 无论哪种方式都不太好，因为即使每 64k 增加 1 个字节也会累积 大文件(每 100M 1526 字节)的显着数量。也硬编码 将 block 大小转换为格式也很糟糕。

3. 转义前缀。例如。 EC 4B A7 00 = EC 4B A7，EC 4B A7 01 = 流结束。 现在这真的很容易编码，但解码非常痛苦 - 需要 一个困惑的状态机甚至提取单个字节。 但总的来说它增加的开销最少，所以看起来我们仍然需要找到 缓冲解码的良好实现。

4. 具有所有相同字节的转义前缀(例如 FF FF FF)。更容易检查， 但是在流中运行相同的字节会产生巨大的开销(比如 25%)， 并且为转义码选择任何字节值也并非不可能。

5. 转义后缀。在标记之前存储有效载荷字节 - 然后是解码器 只需跳过屏蔽标记前的 1 个字节，以及控制代码的 4 个字节。 所以这基本上为解码器引入了一个固定的 4 字节延迟，而 [3] 有一个复杂的路径，其中标记字节必须一个一个地返回。 不过，使用 [3] 编码器要简单得多(它只需要写一个额外的 0 当标记匹配时)，这并没有真正简化缓冲区处理。

更新:实际上我很确定 [3] 或 [5] 是我会使用的选项， 我只列出了其他选项，希望得到更多的选择(例如，它 如果冗余度平均为每个 block 1 bit 就可以了)。所以主要问题 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

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

好处:

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

缺点:

• 如果您必须频繁地从一个流切换到另一个流，而每个流只有几个字节的数据，则该 block 可能没有得到充分利用。许多字节将是空的。
• 如果 block 大小太小(例如，如果您想解决上述问题)，您可能会从 header 中获得巨大的开销。