C++ 如何检查内存块中的所有字节是否为零

How to check whether all bytes in a memory block are zero

提问by Ansgar Lampe

I have a block of memory with elements of fixed size, say 100 bytes, put into it one after another, all with the same fixed length, so memory looks like this

我有一块内存，其中包含固定大小的元素，比如 100 个字节，一个接一个地放入其中，所有元素都具有相同的固定长度，所以内存看起来像这样

<element1(100 bytes)><element2(100 bytes)><element3(100 bytes)>...

In some situations I need to determine whether all bytes of a certain element are set to the 0-byte because that has a special meaning (I didn't say it was a good idea, but that is the situation I am in).

在某些情况下，我需要确定某个元素的所有字节是否都设置为 0 字节，因为这具有特殊含义（我没有说这是个好主意，但这就是我所处的情况）。

The question is, how do I do that efficiently. Further: is there a simple function to do it. For setting bytes to zero I can used memset or bzero, but I don't know of any function for checking for zero.

问题是，我如何有效地做到这一点。进一步：是否有一个简单的功能来做到这一点。要将字节设置为零，我可以使用 memset 或 bzero，但我不知道任何用于检查零的函数。

At the moment I am using a loop for the check

目前我正在使用循环进行检查

char *elementStart = memoryBlock + elementNr*fixedElementSize;
bool special = true;
for ( size_t curByteNr=0; curByteNr<fixedElementSize; ++curByteNr )
{
  special &= (*(elementStart+curByteNr)) == 0;
}

Of course, I could loop with a bigger offset and check several bytes at once with a mword or some other suited bigger type. And I guess that would be rather efficient, but I would like to know whether there is a function to take that burden from me.

当然，我可以使用更大的偏移量进行循环，并使用 mword 或其他适合的更大类型一次检查多个字节。我想这会相当有效，但我想知道是否有一个功能可以减轻我的负担。

Suggested functions:

建议功能：

• !memcmp (compareBlock, myBlock, fixedElementSize)

• !memcmp (compareBlock, myBlock, fixedElementSize)

采纳答案by wallyk

The obvious portable, high efficiency method is:

明显的便携、高效的方法是：

char testblock [fixedElementSize];
memset (testblock, 0, sizeof testblock);

if (!memcmp (testblock, memoryBlock + elementNr*fixedElementSize, fixedElementSize)
   // block is all zero
else  // a byte is non-zero

The library function memcmp()in most implementations will use the largest, most efficient unit size it can for the majority of comparisons.

memcmp()大多数实现中的库函数将使用最大、最有效的单元大小进行大多数比较。

For more efficiency, don't set testblockat runtime:

为了提高效率，不要testblock在运行时设置：

static const char testblock [100];

By definition, static variables are automatically initialized to zero unless there is an initializer.

根据定义，除非有初始化程序，否则静态变量会自动初始化为零。

回答by mihaif

You could perhaps actually use memcmp without having to allocate a zero-valued array, like this:

您实际上可以使用 memcmp 而不必分配零值数组，如下所示：

static int memvcmp(void *memory, unsigned char val, unsigned int size)
{
    unsigned char *mm = (unsigned char*)memory;
    return (*mm == val) && memcmp(mm, mm + 1, size - 1) == 0;
}

The standard for memcmp does not say anything about overlapping memory regions.

memcmp 的标准没有说明重叠内存区域。

回答by underscore_d

I can't believe no one posted this yet... a solution that actually looks like C++ and isn't UB for breaking aliasing rules:

我不敢相信还没有人发布这个......一个实际上看起来像 C++ 并且不是用于打破别名规则的 UB 的解决方案：

#include <algorithm> // std::all_of
#include <cstddef>   // std::size_t

// You might only need this
bool
memory_is_all_zeroes(unsigned char const* const begin,
                     std::size_t          const bytes)
{
    return std::all_of( begin, begin + bytes,
                        [](unsigned char const byte) { return byte == 0; } );
}

// but here's this as a bonus
template<typename T_Element, std::size_t T_count>
bool
array_is_all_zeroes( T_Element const (& array)[T_count] )
{
    auto const begin = reinterpret_cast<unsigned char const*>(array);
    auto const bytes = T_count * sizeof(T_Element);

    return memory_is_all_zeroes(begin, bytes);
}

int
main()
{
    int const blah[1000]{0};

    return !array_is_all_zeroes(blah);
}

This might not satisfy some people's assumptions about efficiency (which are just that, assumptions, until profiled), but I think being valid and idiomatic code are much in its favour.

这可能无法满足某些人对效率的假设（这只是假设，直到被分析），但我认为有效和惯用的代码非常有利于它。

回答by Lucian

AFAIK there is no automatically function to check memory.

AFAIK 没有自动检查内存的功能。

You could use | to speed up the for-loop, no need for "=="

你可以使用 | 加速for循环，不需要“==”

char *elementStart = memoryBlock + elementNr*fixedElementSize;
char special = 0;
for ( size_t curByteNr=0; curByteNr<fixedElementSize; ++curByteNr )
{
  special |= (*(elementStart+curByteNr));
}

and also can you use long for even more speed

你也可以使用 long 来获得更快的速度

char *elementStart = memoryBlock + elementNr*fixedElementSize;
long special = 0;
for ( size_t curByteNr=0; curByteNr<fixedElementSize; curByteNr += sizeof(long) )
{
   special |= *(long*)(elementStart+curByteNr);
}

WARNING: the above code is not tested. Please test it first so that the sizeof and casting operator works

警告：上面的代码没有经过测试。请先测试它，以便 sizeof 和 cast 操作符工作

回答by Flinsch

It is not possible to check all 100 bytes at the same time. So, you (or any utility functions) have to iterate through the data in any case. But, besides having a step size bigger than 1 byte, you could do some more optimizations: For example, you could breakas soon as you find a non-zero value. Well, the time complexity would still be O(n), I know.

不可能同时检查所有 100 个字节。因此，您（或任何实用程序函数）在任何情况下都必须遍历数据。但是，除了步长大于 1 字节之外，您还可以进行更多优化：例如，您可以break在找到非零值后立即执行。好吧，我知道时间复杂度仍然是O(n)。

回答by lalebarde

I have tested some solutions proposed here and checked memcmpsource codewhich is not optimized for the OP needs since it has an additional requirement to perform sorting, leading it to compare unsigned charone by one.

我已经测试了这里提出的一些解决方案，并检查了未针对 OP 需求进行优化的memcmp源代码，因为它有一个额外的要求来执行排序，导致它进行unsigned char一一比较。

In the following, I propose an optimized function check_memory_zeroedwhich performs most of the check on the biggest aligned int available, making it portable, and I compare it with the other solutions proposed in this thread. Time measurement is performed and results printed.

在下文中，我提出了一个优化函数check_memory_zeroed，该函数对可用的最大对齐 int 执行大部分检查，使其可移植，并将其与该线程中提出的其他解决方案进行比较。执行时间测量并打印结果。

It shows that the proposed solution is near twice better than wallyk's obvious portable high efficiency methodand does not need to create an additional array, and six times better than char by char comparison or mihaif's shifted array which saves RAM compared to wallyk's one.

结果表明，所提出的解决方案比 wallyk明显的便携式高效方法好近两倍，并且不需要创建额外的数组，比 char by char 比较或 mihaif 的移位数组好六倍，与 wallyk 的方法相比，节省了 RAM。

I have also tested my solution without aligning the words check_memory_zeroed_bigestint_not_alignedand surprisingly, it performs even better. If someone has an explanation, he is welcome.

我还测试了我的解决方案，但没有对齐文字check_memory_zeroed_bigestint_not_aligned，令人惊讶的是，它的表现甚至更好。如果有人有解释，欢迎他。

Here is the code with functional and performance tests on a 1Gb table (the proposed optimized function is the fisrt one : check_memory_zeroed):

这是在 1Gb 表上进行功能和性能测试的代码（建议的优化函数是第一个：check_memory_zeroed）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include <assert.h>
#include <time.h>

#define BIG_TAB_SIZE 1000000000

typedef intmax_t biggestint;

int check_memory_zeroed (void* ptr, size_t size)
{
    if (ptr == NULL) return -1;
    int bis = sizeof(biggestint);
    char* pc = (char*) ptr;
    biggestint* pbi0 = (biggestint*) pc;
    if ((size_t) pc % bis) /* is aligned ? */
        pbi0 = (biggestint*) (pc + (bis - ((size_t) pc % bis))); /* minimal pointer larger than ptr but aligned */
    assert ((size_t) pbi0 % bis == 0); /* check that pbi0 is aligned */
    for (char* p = pc; p < (char*) pbi0; p++)
        if(*p) return 0; /* check beginning of non aligned array */
    biggestint* pbi = pbi0;
    biggestint* pbiUpper = ((biggestint*) (pc + size)) - 1;
    for (;pbi <= pbiUpper; pbi++)
        if(*pbi) return 0; /* check with the biggest int available most of the array : its aligned part */
    for (char* p = (char*) pbi; p < pc + size; p++)
        if(*p) return 0; /* check end of non aligned array */
    return 1;
}

int check_memory_zeroed_bigestint_not_aligned (void* ptr, size_t size)
{
    if (ptr == NULL) return -1;
    biggestint* pbi = (biggestint*) ptr;
    biggestint* pbiUpper = ((biggestint*) (((char*) ptr) + size)) - 1;
    for (;pbi <= pbiUpper; pbi++)
        if(*pbi) return 0; /* check with the biggest int available most of the array, but without aligning it */
    for (char* p = (char*) pbi; p < ((char*) ptr) + size; p++)
        if(*p) return 0; /* check end of non aligned array */
    return 1;
}

int check_memory_zeroed_by_char (void* ptr, size_t size)
{
    if (ptr == NULL) return -1;
    for (char* p = (char*) ptr; p < ((char*) ptr) + size; p++)
        if(*p) return 0;
    return 1;
}

/* variant of wallyk solution */
int check_memory_zeroed_by_memcmp_and_testblock (void* ptr, size_t size)
{
    void* testblock = malloc(size);
    if (ptr == NULL || testblock == NULL) return -1;
    memset (testblock, 0, sizeof(testblock));
    int res = ! memcmp (testblock, ptr, size);
    free (testblock);
    return res;
}

/* variant of mihaif solution */
int check_memory_zeroed_by_memcmp_with_shifted_array (void* ptr, size_t size)
{
    if (ptr == NULL) return -1;
    char* pc = (char*) ptr;
    return (*pc) || memcmp(pc, pc + 1, size - 1);
}

int test() {
    /* check_memory_zeroed (void* ptr, size_t size) */
    char tab[16];
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++) {
            for (int k = 0; k < 16; k++) tab[k] = (k >= i && k < 16 - j) ? 0 : 100 + k;
            assert(check_memory_zeroed(tab + i, 16 - j - i));
            if (i > 0) assert(tab[i-1] == 100 + i - 1);
            if (j > 0) assert(tab[16 - j] == 100 + 16 - j);
            for (int k = i; k < 16 - j; k++) {
                tab[k] = 200+k;
                assert(check_memory_zeroed(tab + i, 16 - j - i) == 0);
                tab[k] = 0;
            }
        }
    char* bigtab = malloc(BIG_TAB_SIZE);
    clock_t t = clock();
    printf ("Comparison of different solutions execution time for checking an array has all its values null\n");
    assert(check_memory_zeroed(bigtab, BIG_TAB_SIZE) != -1);
    t = clock() - t;
    printf ("check_memory_zeroed optimized : %f seconds\n",((float)t)/CLOCKS_PER_SEC);
    assert(check_memory_zeroed_bigestint_not_aligned(bigtab, BIG_TAB_SIZE) != -1);
    t = clock() - t;
    printf ("check_memory_zeroed_bigestint_not_aligned : %f seconds\n",((float)t)/CLOCKS_PER_SEC);
    assert(check_memory_zeroed_by_char(bigtab, BIG_TAB_SIZE) != -1);
    t = clock() - t;
    printf ("check_memory_zeroed_by_char : %f seconds\n",((float)t)/CLOCKS_PER_SEC);
    assert(check_memory_zeroed_by_memcmp_and_testblock(bigtab, BIG_TAB_SIZE) != -1);
    t = clock() - t;
    printf ("check_memory_zeroed_by_memcmp_and_testblock by wallyk : %f seconds\n",((float)t)/CLOCKS_PER_SEC);
    assert(check_memory_zeroed_by_memcmp_with_shifted_array(bigtab, BIG_TAB_SIZE) != -1);
    t = clock() - t;
    printf ("check_memory_zeroed_by_memcmp_with_shifted_array by mihaif : %f seconds\n",((float)t)/CLOCKS_PER_SEC);
    free (bigtab);

    return 0;
}

int main(void) {
    printf("Size of intmax_t = %lu\n", sizeof(intmax_t));
    test();
    return 0;
}

And the results for comparison of different solutions execution time for checking an array has all its values null:

并且用于检查数组的不同解决方案执行时间的比较结果的所有值都为空：

• Size of intmax_t = 8
• check_memory_zeroed optimized : 0.331238 seconds
• check_memory_zeroed_bigestint_not_aligned : 0.260504 seconds
• check_memory_zeroed_by_char : 1.958392 seconds
• check_memory_zeroed_by_memcmp_and_testblock by wallyk : 0.503189 seconds
• check_memory_zeroed_by_memcmp_with_shifted_array by mihaif : 2.012257 seconds

• intmax_t 的大小 = 8
• check_memory_zeroed 优化：0.331238 秒
• check_memory_zeroed_bigestint_not_aligned：0.260504 秒
• check_memory_zeroed_by_char ：1.958392 秒
• check_memory_zeroed_by_memcmp_and_testblock by wallyk：0.503189 秒
• mihaif 的 check_memory_zeroed_by_memcmp_with_shifted_array：2.012257 秒

回答by MaximG

I can't recall a standard library function which could do this for you. If you are not sure this causes any performance issues I'd just use the loop, maybe replace char* with int* as already suggested.

我不记得可以为您执行此操作的标准库函数。如果您不确定这会导致任何性能问题，我只会使用循环，也许按照已经建议的那样将 char* 替换为 int*。

If you do have to optimize you could unroll the loop:

如果您必须优化，您可以展开循环：

bool allZeroes(char* buffer)
{
    int* p = (int*)buffer;   // you better make sure your block starts on int boundary
    int acc = *p;
    acc |= *++p;
    acc |= *++p;
    ...
    acc |= *++p;    // as many times as needed

    return acc == 0;
}

You may need to add special handling for the end of buffer if it's size is not a multiple of sizeof(int), but it could be more efficient to allocate a slightly larger block with some padding bytes set to 0.

如果缓冲区的大小不是 sizeof(int) 的倍数，您可能需要为缓冲区末尾添加特殊处理，但分配一些填充字节设置为 0 的稍大块可能会更有效。

If your blocks are large you could treat them as a sequence of smaller blocks and loop over them, using the code above for each small block.

如果您的块很大，您可以将它们视为一系列较小的块并循环遍历它们，对每个小块使用上面的代码。

I would be curious to know how this solution compares with std::upper_bound(begin,end,0)and memcmp.

我很想知道这个解决方案如何与std::upper_bound(begin,end,0)和进行比较memcmp。

EDIT

编辑

Did a quick check how a home-grown implementation compares with memcmp, used VS2010 for that.

快速检查了本地实现与 memcmp 的比较，为此使用了 VS2010。

In short:

简而言之：

1) in debug mode home-grown can be twice as fast as memcmp

1) 在调试模式下，自制的速度是 memcmp 的两倍

2) in release with full optimization memcmp has an edge on the blocks which start with non-0s. As the length of the zero-filled preamble increases it starts losing, then somehow magically gets almost as fast as homegrown, about only 10% slower.

2) 在完全优化的版本中，memcmp 在以非 0 开头的块上具有优势。随着零填充前导码的长度增加，它开始丢失，然后不知何故神奇地变得几乎和本土一样快，仅慢了 10%。

So depending on your data patterns and need/desire to optimize you could get some extra performance from rolling out your own method, but memcmp is a rather reasonable solution.

因此，根据您的数据模式和优化的需要/愿望，您可以通过推出自己的方法获得一些额外的性能，但 memcmp 是一个相当合理的解决方案。

Will put the code and results on github in case you could use them.

将代码和结果放在github上，以防您可以使用它们。

回答by fmuecke

The following will iterate through the memory of a structure. Only disadvantage is that it does a bytewise check.

下面将遍历一个结构的内存。唯一的缺点是它会进行逐字节检查。

#include <iostream>

struct Data { int i; bool b; };

template<typename T>
bool IsAllZero(T const& data)
{
    auto pStart = reinterpret_cast<const char*>(&data);
    for (auto pData = pStart; pData < pStart+sizeof(T); ++pData)
    {
        if (*pData)
            return false;
    }

    return true;
}

int main()
{
    Data data1;// = {0}; // will most probably have some content
    Data data2 = {0}; // all zeroes

    std::cout << "data1: " << IsAllZero(data1) << "\ndata2: " << IsEmptyStruct(data2);

    return 0;
};

回答by lovesh

Well if you just want to decide whether a single element is all 0s you can create a 100byte element with all 1s. Now when you want to check whether an element is all 0s just binary AND (&)the content of the element and the element you created(all 1s). now if the result of binary AND is zerothe element you checked had all 0s otherwise it was not all 0s

好吧，如果您只想确定单个元素是否全为 0，则可以create a 100byte element with all 1s。现在，当您要检查元素是否全为 0 时，只需检查元素binary AND (&)的内容和您创建的元素（全为 1）。现在if the result of binary AND is zero你检查的元素全是 0 否则它不是全 0

the creation of a 100 byte element with all 1s seems costly but if you have a large number of elements to check then its actually better

创建一个全为 1 的 100 字节元素似乎代价高昂，但如果您要检查大量元素，那么它实际上更好

you can create the 100 byte element with all 1s as void *elem; elem=malloc(100);now set all bits to 1(use ~(elem&0))

您可以创建全为 1 的 100 字节元素，因为void *elem; elem=malloc(100);现在将所有位设置为 1（使用~(elem&0)）

回答by kravemir

What about using long intand binary oroperator.

使用long int和二元or运算符怎么样。

unsigned long long int *start, *current, *end, value = 0;
// set start,end
for(current = start; current!=end; current++) {
value |= *current;
}
bool AllZeros = !value;