c - 性能挑战 : NAL Unit Wrapping

Question

从我过去所见，StackOverflow 似乎喜欢编程挑战，例如 fast char to string exercise problem得到了几十个回应。这是一个优化挑战:采用一个非常简单的函数，看看您是否能想出更聪明的方法来实现它。

我有一个函数想要进一步优化很长一段时间，但我总是发现我的优化有一些漏洞导致输出不正确——在一些罕见的特殊情况下它们会失败。但是，鉴于功能，我一直认为应该能够做得比这更好。

该函数采用输入数据流(从熵的角度来看，实际上是随机位)并将其包装到 NAL 单元中。这涉及放置转义码:00 00 00、00 00 01、00 00 02 或 00 00 03 的任何字节序列都将替换为 00 00 03 XX，其中 XX 是原始序列的最后一个字节。正如人们所猜测的那样，考虑到这种序列的可能性，每 400 万字节的输入中只有大约 1 个被放置——所以这是一个挑战，其中一个人正在搜索大量数据并且几乎什么都不做它除非在极少数情况下。然而，因为“做某事”涉及到插入字节，所以这让事情变得有点棘手。目前未优化的代码如下C:

src 和 dst 是指向字节数组的指针，end 是指向输入数据末尾的指针。

int i_count = 0;
while( src < end )
{
    if( i_count == 2 && *src <= 0x03 )
    {
        *dst++ = 0x03;
        i_count = 0;
    }
    if( *src == 0 )
        i_count++;
    else
        i_count = 0;
    *dst++ = *src++;
}

此函数的常见输入大小范围大约在 1000 到 1000000 字节的数据之间。

我的最初想法包括一个函数，该函数(以某种方式)快速搜索输入以查找需要转义码的情况，以避免在不需要放置转义码的绝大多数输入中出现更复杂的逻辑。

---

Answer 1

嗯……这样的东西怎么样？

#define likely(x) __builtin_expect((x),1)
#define unlikely(x) __builtin_expect((x),0)

while( likely(src < end) )
{
    //Copy non-zero run
    int runlen = strlen( src );
    if( unlikely(src+runlen >= end) )
    {
        memcpy( dest, src, end-src );
        dest += end-src;
        src = end;
        break;
    }

    memcpy( dest, src, runlen );
    src += runlen;
    dest += runlen;

    //Deal with 0 byte
    if( unlikely(src[1]==0 && src[2]<=3 && src<=end-3) )
    {
        *dest++ = 0;
        *dest++ = 0;
        *dest++ = 3;
        *dest++ = *src++;
    }
    else
    {
        *dest++ = 0;
        src++;
    }
}

在 strcpy 和 memcpy 之间有一些重复的工作，但最好摆脱掉。