I'm trying to see if a struct came back as all 0xFF for the size of the struct.
memcmp seems like the obvious starting point, BUT I'd have to allocate a second memory block, populate it with 0xFF's. It just seems like a waste.
Does a standard function exist for this? Or should I just punt and iterate via a for loop?
The most obvious solution here seems to be to simply loop over the size of the struct and compare it byte-by-byte.
The approach of allocating a block of 0xFF followed by memcmp should achieve the same with but a higher space complexity.
I know no standard function for this.
I don't think that memcmp is always the right choice (it needs twice the memory bandwith).
I would write an iteration (even a very naive one). Most compilers optimize that very well (when asked). So they probably unroll your loops and may do word compares (even if you coded a naive byte iteration).
You might code specialized openmp variants (at least on GCC). See http://openmp.org/
If the structure is big (e.g. dozens of kilobytes, because of the cost of GPGPU <-> RAM data copy) and if you have lot of development time to waste, consider perhaps OpenCL (in particular if you have specialized hardware supporting it, e.g. GPGPUs). It might never worth the cost (unless you do something -which does not require a lot of memory bandwidth- on the CPU while the GPGPU is working)
I would code the naive loop, and won't bother optimizing by hand (unless benchmarking of compiler-optimized code suggests otherwise), because the bottleneck is probably the memory bandwidth.
The logical name for such a function would be memcchr - it is to memchr as strcspn is to strspn.
And look here: google results for memcchr show that it has been implemented under that name as part of the FreeBSD kernel, and they've made some attempt at optimizing it beyond the obvious 1-byte-at-a-time loop.
It will probably take some additional work to make this function suitable for use in any program other than the FreeBSD kernel.
There is memchr(), which does the opposite of what you're asking for - search for the first occurrence of a byte within a mem block. afaik, there isn't a standard function to search for a byte that doesn't match a specific one. for loop sounds like the way to go. Maybe go 32/64bits at a time to speed it up.
-- An extra bit of not-answer: memcmp is going to be slower than a for loop. First, you'll need to fill a block of memory the same size as your original block (this portion will probably take as long as a naive for loop). Then you need to read each memory block into registers to compare them. A for loop will have a value in a register and just read in one memory block to compare with the unchanging register.
I don't know if this would help with performance a lot, but you could follow this algorithm:
And continue in the same fashion until the end of the struct. If at any point the statement is false, you know the struct isn't all 0xFF. You would also need to handle it differently when the remaining portion of the struct is smaller than the first part checked, but that should be relatively simple.
In the end you've allocated 1 extra byte of memory and the algorithm is O(log n) (a slight improvement on what I've seen in the answers so far).
edit: As escrafford mentioned below, if you substitute "byte" for "word" in the above portion, it may run a little faster. I can't comment on how much speed you might gain, but it would increase the extra memory stored (albeit by a tiny amount on today's computers).
A dirty re-write of the code in Why does this implementation of strlen() work?. Did some quick tests; no guarantees.
This should return the number of 0xFF bytes; if it equals the number you started it with, you are in the safe. (Of course you could just let it return 0 or 1 as well.) Remove the printfs when satisfied.
#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;
}
I like Erik's suggestion, but it can be simplified in an interesting way as follows (not tested):
if((*pBytes == 0xFF) && (memcmp(pBytes, pBytes + 1, byteCount - 1) == 0)) // The byteCount bytes at pBytes are 0xFFs.
The condition will be true only if A) the first byte is 0xFF, and B) every other byte is equal to the byte before it. The combination means every byte is 0xFF.
Take a look into strspn function. But you need to place '\0' in the first byte after the struct under test in order to be able to use this function.
