我想看看一个结构体返回的大小是否都是0xFF。memcmp看起来像是一个明显的起点,但是我必须分配第二个内存块,用0xFF填充它。这看起来像是一种浪费。有没有一个标准的函数可以实现这个呢?或者我应该通过一个for循环进行迭代吗?
0xFF
memcmp
pw136qt21#
在Why does this implementation of strlen() work?中重写代码。做了一些快速测试;没有任何保证。本项应返回的字节数为0xFF;如果它等于开始时的数字,那么您就进入了保险箱。(当然,您也可以让它返回0或1。)满意时删除printf。
0
1
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; }
zzoitvuj2#
我喜欢Erik的建议,但它可以用一种有趣的方式简化如下(未经测试):如果((*pBytes == 0xFF)&&(memcmp(pBytes,pBytes + 1,byteCount - 1)== 0))//pBytes处的字节计数字节为0xFF。仅当A)第一个字节为0xFF,且B)每隔一个字节等于其前一个字节时,条件才为真。这种组合意味着每个字节都为0xFF。
esyap4oy3#
看一看strspn函数。但是你需要把'\0'放在被测结构体后面的第一个字节中,这样才能使用这个函数。
zynd9foi4#
这里最明显的解决方案似乎是简单地循环遍历结构体的大小,并逐字节比较它。分配0xFF的块,随后分配memcmp的块的方法应当实现相同的效果,但是具有更高的空间复杂度。
wqsoz72f5#
我不知道这个函数的标准函数。我不认为memcmp总是正确的选择(它需要两倍的内存带宽)。我会写一个迭代(即使是一个非常简单的迭代)。大多数编译器都能很好地优化(当被要求时)。所以他们可能会展开你的循环,并可能会做字比较(即使你编写了一个简单的字节迭代)。您可以编写专门的openmp变体(至少在GCC上)。如果结构很大(例如几十KB,因为GPGPU <->RAM数据复制的成本),如果你有很多开发时间可以浪费,也许可以考虑OpenCL(特别是如果你有专门的硬件支持它,例如GPGPU)。它可能永远不值得这样的成本(除非你在GPGPU工作的时候在CPU上做一些事情--不需要很多内存带宽)我会编写简单的循环,并且不会麻烦手工优化(除非编译器优化代码的基准测试建议不这样做),因为瓶颈可能是内存带宽。
wbrvyc0a6#
这样一个函数的逻辑名称是memcchr-它对于memchr的意义就像strcspn对于strspn的意义一样。看这里:google results for memcchr表明它已经作为FreeBSD内核一部分在这个名称下实现,而且他们已经做了一些尝试来优化它,使其超越明显的一次一个字节的循环。要使这个函数适用于FreeBSD内核以外的任何程序,可能还需要做一些额外的工作。
memcchr
memchr
strcspn
strspn
jfgube3f7#
还有memchr(),它的作用与你所要求的相反a-在mem块中搜索一个字节的第一次出现。afaik,没有一个标准的函数来搜索一个与特定字节不匹配的字节。for循环听起来像是要走的路。也许一次搜索32/64位以加快速度。--额外的一点不回答:memcmp比for循环要慢。首先,你需要填充一个与原始内存块大小相同的内存块(这一部分可能会花费与普通for循环一样长的时间)。然后,你需要将每个内存块读入寄存器进行比较。for循环将寄存器中的值与一个内存块进行比较。
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”,它可能会运行得更快一些。我不能评论你可能会获得多少速度,但它会增加额外的存储空间(尽管在今天的计算机上增加的量很小)。
8条答案
按热度按时间pw136qt21#
在Why does this implementation of strlen() work?中重写代码。做了一些快速测试;没有任何保证。
本项应返回的字节数为
0xFF
;如果它等于开始时的数字,那么您就进入了保险箱。(当然,您也可以让它返回0
或1
。)满意时删除printf
。zzoitvuj2#
我喜欢Erik的建议,但它可以用一种有趣的方式简化如下(未经测试):
如果((*pBytes == 0xFF)&&(memcmp(pBytes,pBytes + 1,byteCount - 1)== 0))//pBytes处的字节计数字节为0xFF。
仅当A)第一个字节为0xFF,且B)每隔一个字节等于其前一个字节时,条件才为真。这种组合意味着每个字节都为0xFF。
esyap4oy3#
看一看strspn函数。但是你需要把'\0'放在被测结构体后面的第一个字节中,这样才能使用这个函数。
zynd9foi4#
这里最明显的解决方案似乎是简单地循环遍历结构体的大小,并逐字节比较它。
分配
0xFF
的块,随后分配memcmp
的块的方法应当实现相同的效果,但是具有更高的空间复杂度。wqsoz72f5#
我不知道这个函数的标准函数。
我不认为
memcmp
总是正确的选择(它需要两倍的内存带宽)。我会写一个迭代(即使是一个非常简单的迭代)。大多数编译器都能很好地优化(当被要求时)。所以他们可能会展开你的循环,并可能会做字比较(即使你编写了一个简单的字节迭代)。
您可以编写专门的openmp变体(至少在GCC上)。
如果结构很大(例如几十KB,因为GPGPU <->RAM数据复制的成本),如果你有很多开发时间可以浪费,也许可以考虑OpenCL(特别是如果你有专门的硬件支持它,例如GPGPU)。它可能永远不值得这样的成本(除非你在GPGPU工作的时候在CPU上做一些事情--不需要很多内存带宽)
我会编写简单的循环,并且不会麻烦手工优化(除非编译器优化代码的基准测试建议不这样做),因为瓶颈可能是内存带宽。
wbrvyc0a6#
这样一个函数的逻辑名称是
memcchr
-它对于memchr
的意义就像strcspn
对于strspn
的意义一样。看这里:google results for memcchr表明它已经作为FreeBSD内核一部分在这个名称下实现,而且他们已经做了一些尝试来优化它,使其超越明显的一次一个字节的循环。
要使这个函数适用于FreeBSD内核以外的任何程序,可能还需要做一些额外的工作。
jfgube3f7#
还有memchr(),它的作用与你所要求的相反a-在mem块中搜索一个字节的第一次出现。afaik,没有一个标准的函数来搜索一个与特定字节不匹配的字节。for循环听起来像是要走的路。也许一次搜索32/64位以加快速度。
--额外的一点不回答:memcmp比for循环要慢。首先,你需要填充一个与原始内存块大小相同的内存块(这一部分可能会花费与普通for循环一样长的时间)。然后,你需要将每个内存块读入寄存器进行比较。for循环将寄存器中的值与一个内存块进行比较。
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”,它可能会运行得更快一些。我不能评论你可能会获得多少速度,但它会增加额外的存储空间(尽管在今天的计算机上增加的量很小)。