[ccan] [PATCH] maskn & bitops: add new modules

[Cody P Schafer]

On Wed, Jul 9, 2014 at 6:41 AM, David Gibson
<david at gibson.dropbear.id.au> wrote:
> On Tue, Jul 08, 2014 at 07:23:41PM -0400, Cody P Schafer wrote:
>> 'maskn' provides generation of n-bit masks from a given range.
>> 'bitops' provides some generic bit operations that maskn needs.
>>
>> Both operate on 32-bit values only (that's just what I needed at this
>> point).
>>
>> bitops currently has some not-so-great detection of features to support
>> the the intrinsics provided by IAR's C compiler for ARM. Not sure how
>> we want to handle that. "HAVE_CLZ and HAVE_RBIT" doesn't seem like it
>> will be useful for other compilers, and we'll still end up with similar
>> ifdefs to generate the builtin_clz/builtin_ctz macros (not to mention
>> the need to include intrinsics.h).
>>
>> Additionally, there is some overlap between ilog and bitops that would
>> be good to remove.
>
> [snip]
>> diff --git a/ccan/bitops/_info b/ccan/bitops/_info
>> new file mode 100644
>> index 0000000..12e8f7f
>> --- /dev/null
>> +++ b/ccan/bitops/_info
>> @@ -0,0 +1,29 @@
>> +#include "config.h"
>> +#include <string.h>
>
> Should have stdio.h too, for puts() / printf().  ccanlint now includes
> that in the template, but only recently.
>

Ack.

> [snip]
>> +unsigned fls_m1_32(uint32_t v)
>
> This could really do with a descriptive comment.

Yep. It's really just something I needed the maskn stuff to work.
It's really just find first set (looks like I miss-named it too) with
it's outputs (% 33) rotated by 1.

>
>> +{
>> +     if (!v)
>> +             return 32;
>> +     return ((CHAR_BIT * sizeof(v)) - clz_32(v)) - 1;
>> +}
>> diff --git a/ccan/bitops/bitops.h b/ccan/bitops/bitops.h
>> new file mode 100644
>> index 0000000..3863a86
>> --- /dev/null
>> +++ b/ccan/bitops/bitops.h
>> @@ -0,0 +1,19 @@
>> +/* CC0 (Public Domain) - see LICENSE file for details */
>> +#ifndef CCAN_BITOPS_H_
>> +#define CCAN_BITOPS_H_
>> +
>> +#include <stdint.h>
>> +#include <ccan/compiler/compiler.h>
>> +
>> +/* assert(bits > 0) */
>> +#define bit_mask_nz(bits) ((UINTMAX_C(1) << ((bits) - 1) << 1) - 1)
>> +static inline uintmax_t bit_mask(unsigned bits)
>> +{
>> +     return bits ? bit_mask_nz(bits) : 0;
>> +}
>
> Um.. I _think_ this is just returning a mask with the low N bits set.
> In which case there are simpler options.  Say, (~(UINTMAX_MAX << (bits)))
>

(UINTMAX_MAX << (bits)) is undefined when (bits >= CHAR_BIT *
sizeof(UINTMAX_MAX)), which prevents me from generating masks that
take up an entire uintmax_t. That said, uint32_t probably isn't
uintmax_t, so we won't run into any issues with the current code.

>> +
>> +unsigned fls_m1_32(uint32_t v) CONST_FUNCTION;
>> +unsigned clz_32(uint32_t v) CONST_FUNCTION;
>> +unsigned ctz_32(uint32_t v) CONST_FUNCTION;
>
> Shouldn't these be inlines?  At least the builtin versions; seems a
> bit silly to use the one-instruction versions when available, then
> wrap then in a function call.
>

I end up using lto anyhow, so making the header more complicated
wasn't a priority.

>> +
>> +#endif
>> diff --git a/ccan/bitops/test/run-no-builtin.c b/ccan/bitops/test/run-no-builtin.c
>> new file mode 100644
>> index 0000000..5871a1f
>> --- /dev/null
>> +++ b/ccan/bitops/test/run-no-builtin.c
>> @@ -0,0 +1,4 @@
>> +#include <ccan/bitops/bitops.h>
>> +#undef builtin_clz
>> +#undef builtin_ctz
>> +#include "run.h"
>
> This seems really fragile.  A rearrangement of what's in the .c versus
> the .h could easily mean this silently uses the builtin versions, so
> not testing what you're trying to test.

But I'm not seeing an alternative that lets me avoid doing the
preprocessor's work it self (by manually copy-pasting the contents of
run.h). Do you see one?

> [snip]
>> diff --git a/ccan/maskn/LICENSE b/ccan/maskn/LICENSE
>> new file mode 120000
>> index 0000000..7455044
>> --- /dev/null
>> +++ b/ccan/maskn/LICENSE
>> @@ -0,0 +1 @@
>> +../../licenses/LGPL-3
>> \ No newline at end of file
>> diff --git a/ccan/maskn/_info b/ccan/maskn/_info
>> new file mode 100644
>> index 0000000..2d44b6f
>> --- /dev/null
>> +++ b/ccan/maskn/_info
>> @@ -0,0 +1,41 @@
>> +#include "config.h"
>> +#include <string.h>
>
> stdio, again.
>
>> +
>> +/**
>> + * maskn - generate masks of N bits for a given range
>> + *
>> + * Masks of N bits as opposed to arbitrary masks (where any bits can be 0 or
>> + * 1), here only the trailing bits are 0, all others are 1.
>> + *
>> + * This ends up assisting in interfacing with hardware that has the ability to
>> + * match via masks. The current functions generate the largest mask-ranges that
>> + * are within the given range and are fixed to one edge.
>
> Maybe it's just me, but for the life of me I can't figure out what
> that's saying.
>
> What's the relation of the output mask to the given range?

Given a range [a, b] (the ranges are inclusive), the code generates a
mask that always includes 'a', never includes anything before 'a', and
tries to include as much of (a, b] as possible, but never includes
anything beyond 'b'.