On 1/1/19 8:33 AM, Richard W.M. Jones wrote:
It's useful to be able to search for the next non-zero entry in a bitmap. This commit adds a ‘bitmap_next’ function to do that. Because the bitmap is just a uint8_t buffer, using fast string functions we should be able to do this quickly even if the bitmap is sparse. (However the actual implementation is not optimized since that is quite complicated - see to-do comments in common/include/nextnonzero.h).
I wasn't confident about the correctness of the code and so this commit also adds some unit tests covering all of the bitmap code. ---
+#define NBDKIT_NEXTNONZERO_H + +/* Given a byte buffer, return a pointer to the first non-zero byte, + * or return NULL if we reach the end of the buffer. + * + * XXX: Even with -O3 -mavx2, gcc 8.2.1 makes a terrible job with this
maybe s/makes/does/
+ * loop, compiling it completely naively. QEMU has an AVX2 + * implementation of a similar loop. + *
+/* Unit tests of the bitmap code. */ +
+ + /* Check the values of all bits. */ + for (i = j = 0; i < nr_blocks; ++i) { + if (i == blks[j]) { /* previously set bit */ + vexp = (j & 1) == 0 ? 1 : (1<<bpb) - 1; + v = bitmap_get_blk (&bm, blks[j], 0); + assert (v == vexp); + ++j; + } + else { /* unset bit, except it to be zero */
s/except/expect/
+ v = bitmap_get_blk (&bm, i, 0); + assert (v == 0); + } + } +
Otherwise looks good. -- Eric Blake, Principal Software Engineer Red Hat, Inc. +1-919-301-3226 Virtualization: qemu.org | libvirt.org