Как проверить, что все байты в блоке памяти равны нулю

Ответ 1

Очевидный переносимый, высокоэффективный метод:

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

Функция библиотеки memcmp() в большинстве реализаций будет использовать самый большой, самый эффективный размер единицы, который он может использовать для большинства сравнений.

Для большей эффективности не устанавливайте testblock во время выполнения:

static const char testblock [100];

По определению статические переменные автоматически инициализируются до нуля, если нет инициализатора.

Ответ 2

Возможно, вы действительно можете использовать 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;
}

Стандарт memcmp ничего не говорит о перекрывающихся областях памяти.

Ответ 3

AFAIK автоматическая функция проверки памяти отсутствует.

Вы можете использовать | для ускорения цикла for, нет необходимости в "=="

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

а также вы можете использовать длинную для еще большей скорости

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

ПРЕДУПРЕЖДЕНИЕ: вышеуказанный код не проверен. Сначала проверьте его, чтобы оператор sizeof и casting работал

Ответ 4

Невозможно одновременно проверить все 100 байтов. Таким образом, вы (или любые служебные функции) должны перебирать данные в любом случае. Но, помимо размера шага больше 1 байт, вы можете сделать еще несколько оптимизаций: например, вы могли бы break, как только найдете ненулевое значение. Ну, сложность времени все равно будет O (n), я знаю.

Ответ 5

Я не могу вспомнить стандартную библиотечную функцию, которая могла бы сделать это для вас. Если вы не уверены, что это вызывает какие-либо проблемы с производительностью, я бы просто использовал цикл, возможно, заменил char * на int *, как уже было предложено.

Если вам нужно оптимизировать, вы можете развернуть цикл:

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;
}

Вам может потребоваться добавить специальную обработку для конца буфера, если размер не является кратным sizeof (int), но может быть более эффективным выделить немного больший блок с некоторыми байтами заполнения, установленными на 0.

Если ваши блоки большие, вы можете рассматривать их как последовательность меньших блоков и перебирать их, используя приведенный выше код для каждого небольшого блока.

Мне было бы интересно узнать, как это решение сравнивается с std::upper_bound(begin,end,0) и memcmp.

ИЗМЕНИТЬ

Произошла быстрая проверка того, как домашняя реализация сравнивается с memcmp, для этого используется VS2010.

Короче:

1) в режиме отладки доморощенные могут быть в два раза быстрее, чем memcmp

2) в выпуске с полной оптимизацией memcmp имеет край на блоках, которые начинаются с не-0. По мере увеличения длины преамбулы с нулевым заполнением он начинает проигрывать, а затем как-то волшебным образом становится почти таким же быстрым, как и доморощенный, примерно на 10% медленнее.

Таким образом, в зависимости от ваших шаблонов данных и необходимости/желания оптимизировать вы можете получить дополнительную производительность от развертывания собственного метода, но memcmp - довольно разумное решение.

Поместите код и результаты на github, если вы сможете их использовать.

Ответ 6

Как насчет использования 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;

Ответ 7

Следующее будет проходить через память структуры. Единственным недостатком является то, что он выполняет выборочную проверку.

#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;
};

Ответ 8

Я не могу поверить, что никто еще не опубликовал это... решение, которое на самом деле похоже на С++ и не является 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 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);
}

Это может не удовлетворять некоторым предположениям об эффективности (которые есть только предположения, до тех пор, пока они не профилируются), но я считаю, что действительный и идиоматический код в значительной степени в его пользу.

Ответ 9

Хорошо, если вы просто хотите решить, есть ли один элемент - все 0, вы можете create a 100byte element with all 1s. Теперь, когда вы хотите проверить, является ли элемент всего 0s только binary AND (&) содержимым элемента и созданного вами элемента (все 1s). теперь if the result of binary AND is zero элемент, который вы проверили, имел все 0s, в противном случае это было не все 0s

создание 100-байтового элемента со всеми 1-м кажется дорогостоящим, но если у вас есть большое количество элементов для проверки, тогда его действительно лучше

вы можете создать 100-байтовый элемент со всеми 1s как void *elem; elem=malloc(100); теперь установите все биты в 1 (используйте ~(elem&0))