Improving mask-to-bit macro

[Francois Grieu]

Hi,

in an embedded project, the hardware manufacturer has defined
hardware equates on the tune of

#define BIT2MASK(b) (1<<(b))

#define TIMER_CTRL_FOO BIT2MASK(0) // enable mask for feature FOO
#define TIMER_CTRL_BAR BIT2MASK(5) // enable mask for feature BAR
#define TIMER_CTRL_ZOO BIT2MASK(7) // enable mask for feature ZOO

I need to revert the effect of BIT2MASK, and get back at the bit number


When b is in range [0..7] this can be done with one of

// "straightforward"; first constant is octal for "clarity";
#define MASK2BIT(m) ((01623753433>>(m)%11*3)+5&7)

// short variant suggested by Harald van Dijk
#define MASK2BIT(m)(6773270%((m)+9)%8)

// alternate short variant
#define MASK2BIT(m)(478414%((m)+37)&7)


Can we extend this when b is in range [0..15], or better [0..31],
and still have a conformant and "pure" macro, which evaluate its
argument only once ?

Or/and can we generate a compile-time error when m is
not a power of two ?

Can things be made readable, perhaps at the price of removing the
"purity" requirement (which is admitedly pointless in my case) ?


TIA,
François Grieu

 

[James Dow Allen]

#define BIT2MASK(b) (1<<(b))

I need to revert the effect of BIT2MASK, and get back at the bit number

Can we ...
have a conformant and "pure" macro, which evaluate its
argument only once ?

I don't about "purity." Two reasons to avoid double evaluation in
#define MASK2BIT(m) ... ??
are
(a) there may be side-effects, e.g. with
MASK2BIT(m *= 2)
(b) execution speed
Start the macro with "(copy_of_m = m, " if (a) is your
concern.

Or/and can we generate a compile-time error when  m  is
not a power of two ?

((m) & (m)-1)) is the "not a power of two" condition.

If the compiler knows what m is, (b) above shouldn't be
a concern: MASK2BIT(m) will also be a compile-time constant.

Anyway, a similar question came up a few months ago. Look
for a thread with the subject
((m) /((m)%255+1)/255%255*8 + 7-100/((m)%255+14))
Or just use this subject line as your macro, substituting
(m)+1 for m.

The approach is due to Hallvard B Furuseth, which will
probably be an easier search term to Google than
((m) /((m)%255+1)/255%255*8 + 7-100/((m)%255+14))

James

 

[Francois Grieu]

James Dow Allen suggested:

> Start the macro with "(copy_of_m = m, "

Many reasons to avoid it:

1) the macro will then be unusable in a preprocessor
expression<ot>, or with inline assembly</ot>.

2) we need to declare copy_of_m.

3) many compilers will become unable to evaluate
the macro at compile time.

4) undefined behavior for MASK2BIT(BIT2MASK(MASK2BIT(8))).

> ((m) & (m)-1)) is the "not a power of two" condition.

Call me picky, but 0 is a relevant exception.


François Grieu

 

[Doug Miller]

James Dow Allen suggested:


Call me picky, but 0 is a relevant exception.

How is zero an exception? The expression returns zero whenever m is a power of
two, and non-zero whenever it is not, for all m >= 0:

0 & (-1) = 0
1 & 0 = 0
2 & 1 = 0
3 & 2 = 2
4 & 3 = 0
5 & 4 = 4
6 & 5 = 4
7 & 6 = 6
8 & 7 = 0
etc.

 

[Lew Pitcher]

How is zero an exception? The expression returns zero whenever m is a
power of two, and non-zero whenever it is not, for all m >= 0:

0 & (-1) = 0

Can you tell me what power you have to raise two to, to get a result of
zero?

2**0 = 1 nope. 1 != 0
2**1 = 2 nope. 2 != 0

So lets go the other way...

2**-1 = 0.5 nope. 0.5 != 0
2**-2 = 0.25 nope. 0.25 != 0

Hmmmm.... this is looking asymptotic at best.


--
Lew Pitcher

Master Codewright & JOAT-in-training | Registered Linux User #112576
http://pitcher.digitalfreehold.ca/ | GPG public key available by request
---------- Slackware - Because I know what I'm doing. ------

 

[Doug Miller]

Can you tell me what power you have to raise two to, to get a result of
zero?

2**0 = 1 nope. 1 != 0
2**1 = 2 nope. 2 != 0

So lets go the other way...

2**-1 = 0.5 nope. 0.5 != 0
2**-2 = 0.25 nope. 0.25 != 0

Hmmmm.... this is looking asymptotic at best.

Point taken. I haven't had enough coffee this morning, I guess...

 

[Dik T. Winter]

>
> How is zero an exception? The expression returns zero whenever m is a power
> of two, and non-zero whenever it is not, for all m >= 0:
>
> 0 & (-1) = 0
> 1 & 0 = 0

In what way is 0 a power of two?

 

[Nick Keighley]

 > >James Dow Allen suggested:
 > >
 > > > ((m) & (m)-1)) is the "not a power of two" condition.
 > >
 > >Call me picky, but 0 is a relevant exception.
 >
 > How is zero an exception? The expression returns zero whenever m is a power
 > of two, and non-zero whenever it is not, for all m >= 0:
 >
 > 0 & (-1) = 0
 > 1 & 0 = 0

In what way is 0 a power of two?

pow (2, -INF)

 

[Phil Carmody]

Hi,

in an embedded project, the hardware manufacturer has defined
hardware equates on the tune of

#define BIT2MASK(b) (1<<(b))

#define TIMER_CTRL_FOO BIT2MASK(0) // enable mask for feature FOO
#define TIMER_CTRL_BAR BIT2MASK(5) // enable mask for feature BAR
#define TIMER_CTRL_ZOO BIT2MASK(7) // enable mask for feature ZOO

I need to revert the effect of BIT2MASK, and get back at the bit number


When b is in range [0..7] this can be done with one of

// "straightforward"; first constant is octal for "clarity";
#define MASK2BIT(m) ((01623753433>>(m)%11*3)+5&7)

// short variant suggested by Harald van Dijk
#define MASK2BIT(m)(6773270%((m)+9)%8)

// alternate short variant
#define MASK2BIT(m)(478414%((m)+37)&7)


Can we extend this when b is in range [0..15], or better [0..31],
and still have a conformant and "pure" macro, which evaluate its
argument only once ?

What's wrong with inline functions. If you aren't satisfied with
your compiler's ability to inline functions, complain to your provider.

Using an external lookup table of size 37 (bytes), yes.
Either Terje Mathisen or myself, or both, have posted such code
to comp.lang.asm.x86.

Basically you squish all 32 5-bit values into a single 32-bit value
(presuming existence of leading zeroes too), and then permute them.

So IIRC, it's something like:
#define DODGYMACRO(v) (lookup[(MAGIC>>((v)%37))&0x1f])

MAGIC can probably be generated using any LFSR, just rotate it
so that the leading zeroes are in the right position. (Namely hanging
off the top).

16-bits can be done using a table of size 17.

Or/and can we generate a compile-time error when m is
not a power of two ?

Without multiple use of the original parameter, probably not.

Phil

 

[Francois Grieu]

>> in an embedded project, the hardware manufacturer has defined
>> hardware equates on the tune of
>>
>> #define BIT2MASK(b) (1<<(b))
>>
>> #define TIMER_CTRL_FOO BIT2MASK(0) // enable mask for feature FOO
>> #define TIMER_CTRL_BAR BIT2MASK(5) // enable mask for feature BAR
>> #define TIMER_CTRL_ZOO BIT2MASK(7) // enable mask for feature ZOO
>>
>> I need to revert the effect of BIT2MASK, and get back at the bit
>> number
>>
>> When b is in range [0..7] this can be done with one of
>>
>> // "straightforward"; first constant is octal for "clarity";
>> #define MASK2BIT(m) ((01623753433>>(m)%11*3)+5&7)
>>
>> // short variant suggested by Harald van Dijk
>> #define MASK2BIT(m)(6773270%((m)+9)%8)
>>
>> // alternate short variant
>> #define MASK2BIT(m)(478414%((m)+37)&7)
>>
>>
>> Can we extend this when b is in range [0..15], or better [0..31],
>> and still have a conformant and "pure" macro, which evaluate its
>> argument only once ?

> What's wrong with inline functions?

Several things:

A) the C preprocessor does not know them, this I can't
use them in the condition for a #if

B) the only supported compiler for my target CPU is stuck to C89.
<ot>
C) I use MASK2BIT in inline assembly, for an instruction which
syntax requires a bit number (note: this also precludes use
of the selection operator, and any assignment)

> If you aren't satisfied with your compiler's ability to inline
> functions, complain to your provider.

I complained that the compiler barks at enum{foo,}; because of
the extra comma, twice, with no result. All black holes in the
universe will have evaporated long before inline support is added.

> Basically you squish all 32 5-bit values into a single 32-bit value
> (presuming existence of leading zeroes too), and then permute them.
>
> So IIRC, it's something like:
> #define DODGYMACRO(v) (lookup[(MAGIC>>((v)%37))&0x1f])

That is a reasonable avenue for a run-time evaluation (although
for small arguments the technique in my original post is faster
and more compact on many platforms). But most compilers that I
practice are unable to evaluate this at compile time when v is
a constant. And again, no preprocessor can.

The rest of my original question remains:
François Grieu

 

[Tim Rentsch]

Phil Carmody wrote: [snip]

So IIRC, it's something like:
#define DODGYMACRO(v) (lookup[(MAGIC>>((v)%37))&0x1f])

That is a reasonable avenue for a run-time evaluation (although
for small arguments the technique in my original post is faster
and more compact on many platforms). But most compilers that I
practice are unable to evaluate this at compile time when v is
a constant. And again, no preprocessor can.

The rest of my original question remains:

I'm confused about just what it is you're looking for...

#define NOT_A_FINITE_INTEGER_POWER_OF_TWO(k) \
( !(k) || (k) & (k)-1 )

#if NOT_A_FINITE_INTEGER_POWER_OF_TWO( some_constant_expression )
#error "hey buddy, you messed up"
#endif

Or if you want a compile-time error without always having to
do a #if, there are several well known tricks for getting
compilers to complain in regular code (eg, declaring an array
with a bound of either 1 or -1 depending on the value of
the macro call).

Isn't the point of having a macro is that the macro call
is readable without having to always reconstruct or
puzzle out the macro body? Did you miss James Allen's
comments on the bit-counting macro? Spelling that out
a bit:

/* Number of bits in any value (1<<b)-1 where 0 <= b < 3E+10 */
#define IMAX_BITS(m) \
((m) /((m)%0x3fffffffL+1) /0x3fffffffL %0x3fffffffL *30 \
+ (m)%0x3fffffffL /((m)%31+1)/31%31*5 + 4-12/((m)%31+3))

#define MASK2BIT(mask) IMAX_BITS( (mask)-1 )

Do these solve your problem? If not, can you explain why
not?

 

[Francois Grieu]

Tim Rentsch wrote :

>> Phil Carmody wrote: > [snip]

>>> So IIRC, it's something like:
>>> #define DODGYMACRO(v) (lookup[(MAGIC>>((v)%37))&0x1f])

>> That is a reasonable avenue for a run-time evaluation (although
>> for small arguments the technique in my original post is faster
>> and more compact on many platforms). But most compilers that I
>> practice are unable to evaluate this at compile time when v is
>> a constant. And again, no preprocessor can.
>>
>> The rest of my original question remains:

>
> I'm confused about just what it is you're looking for...

A variant of my MASK2BIT() macro that
- performs as the original for inputs 1<<0 to 1<<7
- works for inputs up to at least 1<<15
- including in an expression following #if
- including under C89
<ot>- including with my inline assembler</ot>
- if possible gives a compile-time error when given
something else than a power of two, or outside the
safe input range
- if possible evaluates the argument only once
- if possible has an easy to understand definition.

>
> #define NOT_A_FINITE_INTEGER_POWER_OF_TWO(k) \
> ( !(k) || (k) & (k)-1 )
>
> #if NOT_A_FINITE_INTEGER_POWER_OF_TWO( some_constant_expression )
> #error "hey buddy, you messed up"
> #endif
>
> Or if you want a compile-time error without always having to
> do a #if, there are several well known tricks for getting
> compilers to complain in regular code (eg, declaring an array
> with a bound of either 1 or -1 depending on the value of
> the macro call).

That one fails the "usable in #if" requirement. This could be solved
if the preprocessor barks at division by 0, as well as the compiler
in constant expressions, which I'm willing to assume.

>
> Isn't the point of having a macro is that the macro call
> is readable without having to always reconstruct or
> puzzle out the macro body?

Yes. I was thinking of a readable macro definition.

> Did you miss James Allen's comments on the bit-counting macro?

[snip]

Yes! I initialy did not understand James Allen's idea!!
After reading your post, I do!!! All in all this gives:

// return x given m = (1UL<<x)-1 for some wide range of x
#define COUNTIT(m) \
((m)/((m)%255+1)/255%255*8+7-100/((m)%255+14))

// return 1 if k is a power of two, else 0
#define IS_A_POWER_OF_TWO(k) \
((k)&&!((k)&((k)-1)))

// reverse the effect of BIT2MASK
// raise a compile time alarm if input is not a power of two
#define MASK2BIT(mask) \
COUNTIT((mask)-1/IS_A_POWER_OF_TWO(mask))

> Do these solve your problem?

Yes, up to and including 1<<15 on my platform, and 1<<30 or 1u<<31
for GCC.
Note: <ot>my inline assembler does not like suffixed constants,
and </ot>my compiler thinks 1<<16 is 0.


Many thanks!!!

François Grieu

 

[Tim Rentsch]

Tim Rentsch wrote :

Or/and can we generate a compile-time error when m is
not a power of two ?

#define NOT_A_FINITE_INTEGER_POWER_OF_TWO(k) \
( !(k) || (k) & (k)-1 )

#if NOT_A_FINITE_INTEGER_POWER_OF_TWO( some_constant_expression )
#error "hey buddy, you messed up"
#endif

[snip]

That one fails the "usable in #if" requirement. This could be solved
if the preprocessor barks at division by 0, as well as the compiler
in constant expressions, which I'm willing to assume.

Surely it's easy to turn the above example into
one where either the result is one (meaning the
argument is a power of two) or a divide by zero
occurs... right?