memcmp() - compare buffer for 0

[Mark]

Hello,

#define MAX_LEN 6
unsigned char buf[MAX_LEN];
unsigned char zerobuf[MAX_LEN] = { 0 };

if (memcmp(buf, zerobuf, MAX_LEN) == 0)
puts("buf is empty");
else
puts("buf is not empty");

Is there another way to compare the input buffer for being equal to some
pattern (all zeros in this case), i.e. ti avoid having additional array
zerobuf? I think memcmp(buf, "0", MAX_LEN) isn't valid.

Thanks.

Mark

 

[Ike Naar]

Hello,

#define MAX_LEN 6
unsigned char buf[MAX_LEN];
unsigned char zerobuf[MAX_LEN] = { 0 };

if (memcmp(buf, zerobuf, MAX_LEN) == 0)
puts("buf is empty");
else
puts("buf is not empty");

Is there another way to compare the input buffer for being equal to some
pattern (all zeros in this case), i.e. ti avoid having additional array
zerobuf? I think memcmp(buf, "0", MAX_LEN) isn't valid.

That's correct, memcmp(buf, "0", MAX_LEN) doesn't work.
One reason it won't work is that the character '0' is not the same
as a zero byte ('\0'). Another problem is that the array "0" has
less than MAX_LEN elements so there's the danger of reading beyond
the end of that array.

One other way to do it, that does not use an additional array,
is a simple linear search for the first nonzero element:

size_t i = 0;
while (i != MAX_LEN && buf == 0) ++i;
if (i == MAX_LEN) puts("all zeroes"); else puts("not all zeroes");

Yet another way is to sort the buf array in descending order and
check whether buf[0] equals zero. If it does, the array contains
only zeroes.

There must be at least fifty other ways to do it.

 

[Keith Thompson]

#define MAX_LEN 6
unsigned char buf[MAX_LEN];
unsigned char zerobuf[MAX_LEN] = { 0 };

if (memcmp(buf, zerobuf, MAX_LEN) == 0)
puts("buf is empty");
else
puts("buf is not empty");

Is there another way to compare the input buffer for being equal to some
pattern (all zeros in this case), i.e. ti avoid having additional array
zerobuf? I think memcmp(buf, "0", MAX_LEN) isn't valid.

If your compiler supports compound literals (a "new" feature in C99),
you can do something like this:

if (memcmp(buf, (char[MAX_LEN]){ 0 }, MAX_LEN) == 0)
puts("buf is empty");
else
puts("buf is not empty");

In the more general case -- well, it depends on just what the more
general case turns out to be. This may be a specific example of a
more general problem, but it's hard to tell what that more general
problem is.

(Note that an array is never really "empty". Your array is full; it
just happens to be full of zeros.)

 

[Eric Sosman]

Hello,

#define MAX_LEN 6
unsigned char buf[MAX_LEN];
unsigned char zerobuf[MAX_LEN] = { 0 };

if (memcmp(buf, zerobuf, MAX_LEN) == 0)
puts("buf is empty");
else
puts("buf is not empty");

Is there another way to compare the input buffer for being equal to some
pattern (all zeros in this case), i.e. ti avoid having additional array
zerobuf? I think memcmp(buf, "0", MAX_LEN) isn't valid.

You think rightly, as others have explained.

To use memcmp(), you'll need to compare to a region of memory as
long as the test region, pre-initialized to the desired value. That's
inescapable: it's how memcmp() operates.

Alternatively, you could write a simple isAllZero() function that
just looped through the test region comparing each byte to the desired
value. That would surely use less data memory, but it's impossible to
tell without measurement whether it would be faster or slower.

The strspn() function might *almost* be made to work, if only you
weren't looking for zeroes. As things stand, I see no way to employ it.

 

[Mark Adler]

Is there another way to compare the input buffer for being equal to
some pattern (all zeros in this case), i.e. ti avoid having additional
array zerobuf?

I'm surprised that no one offered the obvious answer that uses memcmp()
without another array:

if (MAX_LEN > 0 && buf[0] == 0 && memcmp(buf, buf + 1, MAX_LEN - 1) == 0)
puts("buf is all zeros");
else
puts("buf has at least one non-zero value");

Though it's probably faster to compare each entry to zero, or even
faster to recast to an array of large integers and compare those to
zero.

Mark

 

[Ian Collins]

Is there another way to compare the input buffer for being equal to
some pattern (all zeros in this case), i.e. ti avoid having additional
array zerobuf?

I'm surprised that no one offered the obvious answer that uses memcmp()
without another array:

if (MAX_LEN> 0&& buf[0] == 0&& memcmp(buf, buf + 1, MAX_LEN - 1) == 0)
puts("buf is all zeros");
else
puts("buf has at least one non-zero value");

Though it's probably faster to compare each entry to zero, or even
faster to recast to an array of large integers and compare those to
zero.

Usual alignment caveats apply!

 

[Ben Bacarisse]

Hello,

#define MAX_LEN 6
unsigned char buf[MAX_LEN];
unsigned char zerobuf[MAX_LEN] = { 0 };

if (memcmp(buf, zerobuf, MAX_LEN) == 0)
puts("buf is empty");
else
puts("buf is not empty");

Is there another way to compare the input buffer for being equal to some
pattern (all zeros in this case), i.e. ti avoid having additional array
zerobuf? I think memcmp(buf, "0", MAX_LEN) isn't valid.

You think rightly, as others have explained.

To use memcmp(), you'll need to compare to a region of memory as
long as the test region, pre-initialized to the desired value. That's
inescapable: it's how memcmp() operates.

There's a memcmp method that does not quite fit that description, though
it is not likely to useful.

In the same way that an object can be copied by successively doubling
the copy region, so a region can be compared for all bytes the same by
doubling the compare region (and it can be altered to handle longer
patterns than all-bytes the same)

assert(BUF_SZ != 0);
size_t clen = 1;
while (2*clen < BUF_SZ)
if (memcmp(buf, buf + clen, clen) == 0)
clen *= 2;
else return false;
return memcmp(buf, buf + clen, BUF_SZ - clen) == 0 && buf[0] == target;

Rather like the previous suggestion to change a O(n) algorithm (a
simple loop) into a O(n log(n)) one (sort and test buf[0]), this is no
more than an exercise in possibilities.

 

[Ben Bacarisse]

Is there another way to compare the input buffer for being equal to
some pattern (all zeros in this case), i.e. ti avoid having additional
array zerobuf?

I'm surprised that no one offered the obvious answer that uses memcmp()
without another array:

if (MAX_LEN> 0&& buf[0] == 0&& memcmp(buf, buf + 1, MAX_LEN - 1) == 0)
puts("buf is all zeros");
else
puts("buf has at least one non-zero value");

Though it's probably faster to compare each entry to zero, or even
faster to recast to an array of large integers and compare those to
zero.

Usual alignment caveats apply!

Are there any in this case?

 

[Ian Collins]

On 2011-10-10 14:38:59 -0700, Mark said:
Is there another way to compare the input buffer for being equal to
some pattern (all zeros in this case), i.e. ti avoid having additional
array zerobuf?

I'm surprised that no one offered the obvious answer that uses memcmp()
without another array:

if (MAX_LEN> 0&& buf[0] == 0&& memcmp(buf, buf + 1, MAX_LEN - 1) == 0)
puts("buf is all zeros");
else
puts("buf has at least one non-zero value");

Though it's probably faster to compare each entry to zero, or even
faster to recast to an array of large integers and compare those to
zero.

Usual alignment caveats apply!

Are there any in this case?

What if the buffer is at an odd address?

 

[Ben Bacarisse]

On 10/11/11 05:35 PM, Mark Adler wrote:
On 2011-10-10 14:38:59 -0700, Mark said:
Is there another way to compare the input buffer for being equal to
some pattern (all zeros in this case), i.e. ti avoid having additional
array zerobuf?

I'm surprised that no one offered the obvious answer that uses memcmp()
without another array:

if (MAX_LEN> 0&& buf[0] == 0&& memcmp(buf, buf + 1, MAX_LEN - 1) == 0)
puts("buf is all zeros");
else
puts("buf has at least one non-zero value");

Though it's probably faster to compare each entry to zero, or even
faster to recast to an array of large integers and compare those to
zero.

Usual alignment caveats apply!

Are there any in this case?

What if the buffer is at an odd address?

Yes, I missed the last sentence right up to the point I hit send! Then
I what what was being proposed (and you were commenting on).

 

[Ben Bacarisse]

I'm surprised that no one offered the obvious answer that uses
memcmp() without another array:

I can't speak for others, but I didn't because I didn't think it was
assured to work. I assumed (wrongly, of course) that memcmp would be
undefined when applied to overlapping regions. I isn't, so it's a fine
solution.

if (MAX_LEN > 0 && buf[0] == 0 && memcmp(buf, buf + 1, MAX_LEN - 1) == 0)
puts("buf is all zeros");
else
puts("buf has at least one non-zero value");

<snip>

 

[bartek szurgot]

if (MAX_LEN > 0 && buf[0] == 0 && memcmp(buf, buf + 1, MAX_LEN - 1) == 0)
puts("buf is all zeros");
else
puts("buf has at least one non-zero value");

Though it's probably faster to compare each entry to zero, or even
faster to recast to an array of large integers and compare those to zero.

i've checked 512MB array of zeros and on my PC simple "for(...)
if(!zero) return false" was over twice as fast (~0.41 vs. ~0.11)
as memcmp (used as above).

i strongly suggest for() since it is both faster and easier for the
reader to understand.

 

[James Kuyper]

I'm surprised that no one offered the obvious answer that uses memcmp()
without another array:

For me, the reason I didn't suggest that was because it wasn't obvious
to me.

if (MAX_LEN > 0 && buf[0] == 0 && memcmp(buf, buf + 1, MAX_LEN - 1) == 0)
puts("buf is all zeros");
else
puts("buf has at least one non-zero value");

While I admire your ingenuity in coming up with that approach, I'd still
favor the simpler, more direct approach:

 

[Ben Bacarisse]

if (MAX_LEN > 0 && buf[0] == 0 && memcmp(buf, buf + 1, MAX_LEN - 1) == 0)
puts("buf is all zeros");
else
puts("buf has at least one non-zero value");

Though it's probably faster to compare each entry to zero, or even
faster to recast to an array of large integers and compare those to zero.

i've checked 512MB array of zeros and on my PC simple "for(...)
if(!zero) return false" was over twice as fast (~0.41 vs. ~0.11)
as memcmp (used as above).

i strongly suggest for() since it is both faster and easier for the
reader to understand.

Just another few data points: I see the plain loop version as being 14
times *slower* than the memcmp version for 512MB, provided I don't
optimise! At gcc -O1 and above the memcmp takes twice the time the
plain loops does. The reason seems to be that gcc replaces memcmp with
a repz cmpsb instruction (plus housekeeping gubbins) and these string
instructions have a reputation for being slow.

The memcmp method is still four times faster than the loop (on this
data, on this machine, with the library, with... etc) provided gcc can
be told not to inline it to cmpsb instruction.

To summarise:
for loop memcmp
gcc unoptimised 13.333s 0.932s
gcc optimising 4.160s 8.250s

I'd post the CPU, gcc version and so on but I think the real messages is
*measure*. You can still be surprised after <mumble> years in this
field.

 

[Mark Adler]

What if the buffer is at an odd address?

You do a few single-byte compares at the beginning and end as
necessary, and do the rest in the middle with larger word compares.

Mark

 

[James Kuyper]

How does it make sense that "the buffer is at odd address"?

C allows implementations to have restrictions, called "alignment
requirements" on where in memory objects of a certain type can be
stored. While there is no portable C meaning to the concept of an "odd
address", it is in fact usually the case that associated with every
address is a number, and on some platforms the addresses associated with
odd numbers could fail to meet the alignment requirements of the "large
integers" referred to below. Such restrictions are actually commonplace.

On 10/11/11 10:11 PM, Ben Bacarisse wrote:

On 10/11/11 05:35 PM, Mark Adler wrote:
On 2011-10-10 14:38:59 -0700, Mark said:
Is there another way to compare the input buffer for being equal to
some pattern (all zeros in this case), i.e. ti avoid having
additional
array zerobuf?

I'm surprised that no one offered the obvious answer that uses
memcmp()
without another array:

if (MAX_LEN> 0&& buf[0] == 0&& memcmp(buf, buf + 1, MAX_LEN - 1)
== 0)
puts("buf is all zeros");
else
puts("buf has at least one non-zero value");

Though it's probably faster to compare each entry to zero, or even
faster to recast to an array of large integers and compare those to
zero.

If the "large integers" he's referring to have alignment requirements,
there's no guarantee that buf satisfies those requirements. If it does
not, the "cast" he's referring to in "recast" will have undefined behavior.

 

[Ben Bacarisse]

Top posting messes up the discussion. I've moved your remark to where I
would have put it and I think you'll see that it makes things
simpler to follow.

On 10/11/11 10:11 PM, Ben Bacarisse wrote:

On 10/11/11 05:35 PM, Mark Adler wrote:
On 2011-10-10 14:38:59 -0700, Mark said:

if (MAX_LEN> 0&& buf[0] == 0&& memcmp(buf, buf + 1, MAX_LEN - 1)
== 0)
puts("buf is all zeros");
else
puts("buf has at least one non-zero value");

Though it's probably faster to compare each entry to zero, or even
faster to recast to an array of large integers and compare those to
zero.

Usual alignment caveats apply!

Are there any in this case?

What if the buffer is at an odd address?

Yes, I missed the last sentence right up to the point I hit send! Then
I [saw] what was being proposed (and you were commenting on).

How does it make sense that "the buffer is at odd address"?

Mark was suggesting testing for zero in bigger chunk by doing something
like this:

long long int *ip = (void *)buf;
for (size_t i; i < something && *ip == 0; i++);

but that does not work reliably on machines that need long long ints to
be aligned more strictly than char arrays. The classic example is when
buf is placed at an odd address rather than an even one.

[I've also cut out material that I don't think is needed and marked the
edits. These are things that keep Usenet posts readable in their own.]

 

[Mark Adler]

You do a few single-byte compares at the beginning and end as
necessary, and do the rest in the middle with larger word compares.

For example:

int isallz(char *buf, size_t len)
{
long *wide;

while ((size_t)buf & (sizeof(long) - 1))
if (len--, *buf++)
return 0;
wide = (long *)buf;
while (len >= sizeof(long))
if (len -= sizeof(long), *wide++)
return 0;
buf = (char *)wide;
while (len)
if (len--, *buf++)
return 0;
return 1;
}

This could be made faster by avoiding the len increments, but this is
just to illustrate the idea.

Mark

 

[bartek szurgot]

Just another few data points: I see the plain loop version as being 14
times *slower* than the memcmp version for 512MB, provided I don't
optimise! At gcc -O1 and above the memcmp takes twice the time the
plain loops does. The reason seems to be that gcc replaces memcmp with
a repz cmpsb instruction (plus housekeeping gubbins) and these string
instructions have a reputation for being slow.

The memcmp method is still four times faster than the loop (on this
data, on this machine, with the library, with... etc) provided gcc can
be told not to inline it to cmpsb instruction.

To summarise:
for loop memcmp
gcc unoptimised 13.333s 0.932s
gcc optimising 4.160s 8.250s

I'd post the CPU, gcc version and so on but I think the real messages is
*measure*. You can still be surprised after <mumble> years in this
field.

i was surprised with your results even more than with my own. i
already removed test code i've wrote before posting my last message and
so i had to rewrite it once more... and bang! it looks like i had a bug
(probably #ifndef instead of #ifdef for switching implementations with
-D), because now i'm getting similar computation times i got before, but
both versions are faster for memcmp(). namely:

for() memcmp()
-g3 ~1.2 ~0.11
-O3 ~0.4 ~0.11

i think this can be ok, since it would be reasonable that call to ext.
library lasts the same amount of time, regardless of release/debug
builds and hand-made code to be faster, when optimized.

source code for this is:
http://pastebin.com/sP9hexnW#
(note: this code is only a PoC - it does not check all errors)

can you check your code as well, please?

any way the conclusion is 100% right. it is always worth checking, even
if you think you know the results. hardware is changing and it may
affect results a lot.

 

[BartC]

if (MAX_LEN > 0 && buf[0] == 0 && memcmp(buf, buf + 1, MAX_LEN - 1) == 0)
puts("buf is all zeros");
else
puts("buf has at least one non-zero value");

Though it's probably faster to compare each entry to zero, or even
faster to recast to an array of large integers and compare those to zero.

i've checked 512MB array of zeros and on my PC simple "for(...)
if(!zero) return false" was over twice as fast (~0.41 vs. ~0.11)
as memcmp (used as above).

i strongly suggest for() since it is both faster and easier for the
reader to understand.

The reader doesn't need to understand it. Just wrap the whole thing in a
function, for example:

int checkallzeros(void *buffer, int nchars); /* or some such name */

then the reader just sees:

if (checkallzeros(buf, MAX_LEN)) ...

Inside checkallzeros(), just put whatever code is best.

This does make it more difficult to have a fixed-length zero array to
compare against, if that is the method, but not impossible. You can use a
static zero array up to certain limit, then some other method, or check a
section at a time, whatever. But the method is hidden, and can be maintained
more easily.

(And if you do have a 512MB array, then you might find it wasteful (in space
and bandwidth) to reserve another 512MB reference array consisting of zeros
to compare against.)