C语言 如何有效地将内存块与单个字节进行比较?

oewdyzsn  于 2022-12-03  发布在  其他
关注(0)|答案(8)|浏览(176)

我想看看一个结构体返回的大小是否都是0xFF
memcmp看起来像是一个明显的起点,但是我必须分配第二个内存块,用0xFF填充它。这看起来像是一种浪费。
有没有一个标准的函数可以实现这个呢?或者我应该通过一个for循环进行迭代吗?

pw136qt2

pw136qt21#

Why does this implementation of strlen() work?中重写代码。做了一些快速测试;没有任何保证。
本项应返回的字节数为0xFF;如果它等于开始时的数字,那么您就进入了保险箱。(当然,您也可以让它返回01。)满意时删除printf

#define LONGPTR_MASK (sizeof(long) - 1)

int find_no_ff (const char *memory, size_t length)
{
    const char *p;
    const unsigned long *lp;
    size_t remain = length, to_do;

    printf ("non-aligned, start:\n");
    /* Test the first few bytes until we have an aligned p */
    for (p = memory; (uintptr_t)p & LONGPTR_MASK; p++)
    {
        printf ("testing %02X\n", *p & 0xff);
        if (*p != '\xFF')
            return (p - memory);
        remain--;
    }

    printf ("passed.\n");

    printf ("aligned:\n");
    to_do = remain/sizeof(long);
    remain -= (to_do*sizeof(long));

    /* Scan the rest of the string using word sized operation */
    for (lp = (const unsigned long *)p; to_do--; lp++)
    {
        printf ("testing %08lX\n", *lp);
        if (*lp +1)
            return p - memory;
    }
    printf ("passed.\n");

    p = (const char *)lp;

    printf ("non-aligned, end:\n");
    /* Test the last bytes until we have an aligned p */
    while (remain--)
    {
        printf ("testing %02X\n", *p & 0xff);
        if (*p != '\xFF')
            return (p - memory);
        p++;
    }
    printf ("passed.\n");
    return p - memory;
}

int main (void)
{
    char data[] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,  0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };

    printf ("input size: %ld\n", sizeof(data));
    printf ("test result: %d\n", find_no_ff (data, sizeof(data)));

    return 0;
}
zzoitvuj

zzoitvuj2#

我喜欢Erik的建议,但它可以用一种有趣的方式简化如下(未经测试):
如果((*pBytes == 0xFF)&&(memcmp(pBytes,pBytes + 1,byteCount - 1)== 0))//pBytes处的字节计数字节为0xFF。
仅当A)第一个字节为0xFF,且B)每隔一个字节等于其前一个字节时,条件才为真。这种组合意味着每个字节都为0xFF。

esyap4oy

esyap4oy3#

看一看strspn函数。但是你需要把'\0'放在被测结构体后面的第一个字节中,这样才能使用这个函数。

zynd9foi

zynd9foi4#

这里最明显的解决方案似乎是简单地循环遍历结构体的大小,并逐字节比较它。
分配0xFF的块,随后分配memcmp的块的方法应当实现相同的效果,但是具有更高的空间复杂度。

wqsoz72f

wqsoz72f5#

我不知道这个函数的标准函数。
我不认为memcmp总是正确的选择(它需要两倍的内存带宽)。
我会写一个迭代(即使是一个非常简单的迭代)。大多数编译器都能很好地优化(当被要求时)。所以他们可能会展开你的循环,并可能会做字比较(即使你编写了一个简单的字节迭代)。
您可以编写专门的openmp变体(至少在GCC上)。
如果结构很大(例如几十KB,因为GPGPU <->RAM数据复制的成本),如果你有很多开发时间可以浪费,也许可以考虑OpenCL(特别是如果你有专门的硬件支持它,例如GPGPU)。它可能永远不值得这样的成本(除非你在GPGPU工作的时候在CPU上做一些事情--不需要很多内存带宽)
我会编写简单的循环,并且不会麻烦手工优化(除非编译器优化代码的基准测试建议不这样做),因为瓶颈可能是内存带宽。

wbrvyc0a

wbrvyc0a6#

这样一个函数的逻辑名称是memcchr-它对于memchr的意义就像strcspn对于strspn的意义一样。
看这里:google results for memcchr表明它已经作为FreeBSD内核一部分在这个名称下实现,而且他们已经做了一些尝试来优化它,使其超越明显的一次一个字节的循环。
要使这个函数适用于FreeBSD内核以外的任何程序,可能还需要做一些额外的工作。

jfgube3f

jfgube3f7#

还有memchr(),它的作用与你所要求的相反a-在mem块中搜索一个字节的第一次出现。afaik,没有一个标准的函数来搜索一个与特定字节不匹配的字节。for循环听起来像是要走的路。也许一次搜索32/64位以加快速度。
--额外的一点不回答:memcmp比for循环要慢。首先,你需要填充一个与原始内存块大小相同的内存块(这一部分可能会花费与普通for循环一样长的时间)。然后,你需要将每个内存块读入寄存器进行比较。for循环将寄存器中的值与一个内存块进行比较。

bfrts1fy

bfrts1fy8#

我不知道这是否对性能有很大帮助,但您可以遵循以下算法:
1.将结构的第一个字节与已分配内存0xFF的1个字节进行比较
1.比较结构的第2个字节与结构的第1个字节
1.将结构的字节3-4与结构的字节1-2进行比较
1.将结构的字节5-8与结构的字节1-4进行比较
然后以同样的方式继续,直到结构体的结尾。如果在任何一点上,语句为假,就可以知道结构体不全是0xFF。当结构体的剩余部分小于第一个被检查的部分时,也需要用不同的方法来处理它,但这应该相对简单。
最后,你已经分配了1个额外的字节的内存,算法是O(log n)(比我在目前的答案中看到的略有改进)。
编辑:正如escrawford在下面提到的,如果你用“byte”代替上面部分中的“word”,它可能会运行得更快一些。我不能评论你可能会获得多少速度,但它会增加额外的存储空间(尽管在今天的计算机上增加的量很小)。

相关问题