Value Bits Vs Object Bits

[Tomás]

The quantity of bits used by an unsigned integer type in memory can be
determined by:
typedef unsigned long long UIntType;

CHAR_BIT * sizeof(UIntType )
However, what would be a good portable way to determine how many of these
bits are value bits? If possible, it would be nice to have it as a
compile time constant.
Here's something I played around with:
typedef unsigned long long UIntType;
unsigned GetQuantityValu eBits(void)
{
/* We know it's atleast 8 in anyway */

unsigned quantity = 8;

UIntType val = 128;

while (val <<= 1) ++quantity;

return quantity;
}
Also, we could determine the amount of non-value bits (trapping bits
perhaps) from:

sizeof(UIntType ) * CHAR_BIT - GetQuantityValu eBits()
-Tomás

[Hallvard B Furuseth]

Frederick Gotham writes:

Eric Sosman posted:

Somewhere along the line, somebody has snipped away the
comment that preceded the macro when originally posted:
(...)
Hehe... I found the code so confusing that I didn't pay attention to
the comments.

You know, some of us do it the other way around:-)
Anyhow, the macro is a stroke of genius. I wonder what other gems
Hallvard B Furuseth has come up with... ?
Not much if you mean C hacks. I just got so annoyed about the lack
of a log2 feature that I beat at it until something gave. For some
reason my most significant "hack" seems to be that one can use
struct align_TYPE_s { char c; TYPE align; };
... offsetof(struct align_TYPE_s, align) ...
instead of
sizeof(TYPE)
for the alignment of TYPE. I've sent that to the maintainers of
several programs where they cared about data size. I have no idea
why it's apparently not obvious.
A compile time "Log base 2" macro would be brilliant...

I gave that up since IMAX_BITS was hairy enough even when restricted to
(1<<k)-1 arguments. Silly of me. With a bunch of helper macros, it
works fine. Check me on this though, I've been staring at it too long:

/*
* Return (v ? floor(log2(v)) : 0) when 0 <= v < 1<<[8, 16, 32, 64].
* Inefficient algorithm, intended for compile-time constants.
*/
#define LOG2_8BIT(v) (8 - 90/(((v)/4+14)|1) - 2/((v)/2+1))
#define LOG2_16BIT(v) (8*((v)>255) + LOG2_8BIT((v) >>8*((v)>255) ))
#define LOG2_32BIT(v) \
(16*((v)>65535L ) + LOG2_16BIT((v)* 1L >>16*((v)>65535 L)))
#define LOG2_64BIT(v)\
(32*((v)/2L>>31 > 0) \
+ LOG2_32BIT((v)* 1L >>16*((v)/2L>>31 > 0) \

16*((v)/2L>>31 > 0)))
Above this, shifting int/long by at most 15/31 bits per operation
gets cumbersome. Also the parentheses nesting level is already
rather high. But if the compiler doesn't mind approx 14K macro
expansions and lots of parentheses, even for simple macro arguments:

/*
* Return (v ? floor(log2(v)) : 0) when 0 <= v < 1<<512.
* Huge computation, intended for compile-time constants.
*/
#define LOG2_512BIT(val )\
LOG2_TMP_FINISH (val,\
LOG2_TMP_CHUNK( 0, val,\
LOG2_TMP_CHUNK( 1, val,\
LOG2_TMP_CHUNK( 3, val,\
LOG2_TMP_CHUNK( 7, val,\
LOG2_TMP_CHUNK( 15, val,\
LOG2_TMP_CHUNK( 31, val, 0)))))))
#define LOG2_TMP_FINISH (val, known_bits)\
(LOG2_8BIT((val ) >> known_bits) + known_bits)
#define LOG2_TMP_CHUNK( ones, val, known_bits)\
(((val)*1L >>known_bits \8>>ones>>ones >>ones>>ones>>o nes>>ones>>ones >>ones \

0) * 8*(ones+1) + known_bits)

Still doesn't scale to "practicall y infinite" like IMAX_BITS does, but
I haven't seen a 1024-bit integer yet. (E.g. 4096 bits would need more
terms in LOG2_8BIT, 64 bit long long shifts, and 4 lines with >>ones.)

On the other hand - the computation doesn't have to be an _expression_.
By unpacking the above algorithm into intermediate enum constants, the
macro expansion is reduced from around 14K to around 0.8K. Also with
declarations we can get an error check by violating constraints if the
value is out of range:

/*
* Define Name = (val ? floor(log2(val) ) : 0) as an enum constant.
* Expects 0 <= val < 1<<512. Tries to force a compile error otherwise.
* Note: Uses some <Name>__<lett er/digit> identifiers.
*/
#define DEFINE_LOG2(Nam e, val)\
enum {\
Name##__5= LOG2_TMP_CHUNK( 31, val, 0),\
Name##__4= LOG2_TMP_CHUNK( 15, val, Name##__5),\
Name##__3= LOG2_TMP_CHUNK( 7, val, Name##__4),\
Name##__2= LOG2_TMP_CHUNK( 3, val, Name##__3),\
Name##__1= LOG2_TMP_CHUNK( 1, val, Name##__2),\
Name##__0= LOG2_TMP_CHUNK( 0, val, Name##__1),\
Name = LOG2_TMP_FINISH (val, Name##__0),\
Name##__c= (val)>>Name == !!(val) ? 1 : -999 \
};\
typedef struct{ int Name##__b:Name# #__c; } Name##__t[Name##__c]

--
Hallvard

[Frederick Gotham]

Hallvard B Furuseth posted:

For some reason my most significant "hack" seems to be that one can
use
struct align_TYPE_s { char c; TYPE align; };
... offsetof(struct align_TYPE_s, align) ...
instead of
sizeof(TYPE)
for the alignment of TYPE. I've sent that to the maintainers of
several programs where they cared about data size. I have no idea
why it's apparently not obvious.

Would the method you devised be preferable on a system where the
alignment requirements of a type are less than its actual size? (e.g. a
system where a double is 8 bytes, but need only be aligned on a 4-byte
boundary?)

Are you sure it's fully-portable? Could the implementation potentially
place the char directly behind a byte boundary, thus making your method
give an inaccurate alignment value of zero?

With a bunch of helper macros, it works fine. Check me on this
though, I've been staring at it too long:

Give me a few days to mull it over...

Have you been at this sort of stuff for many years? I thought I was
pretty handy at playing around with things like this, but your own
expertise astounds me.

I've been taking so long to reply to your posts because I'm staring at
the macros trying to get the faintest idea of how they work, and I still
haven't begun to comprehend!

Give me time though, and I might figure them out...
--

Frederick Gotham

[Michael Mair]

Frederick Gotham schrieb:

Hallvard B Furuseth posted:

For some reason my most significant "hack" seems to be that one can
use
struct align_TYPE_s { char c; TYPE align; };
... offsetof(struct align_TYPE_s, align) ...
instead of
sizeof(TYPE)
for the alignment of TYPE. I've sent that to the maintainers of
several programs where they cared about data size. I have no idea
why it's apparently not obvious.
Would the method you devised be preferable on a system where the
alignment requirements of a type are less than its actual size? (e.g. a
system where a double is 8 bytes, but need only be aligned on a 4-byte
boundary?)

Yes. This method _might_ then give you the minimal _sensible_
alignment.
It does so for all compilers I know -- sensible means that
there are systems without hard alignment requirements but
with preferred alignments for certain types which give you
advantages such as faster access.

Are you sure it's fully-portable? Could the implementation potentially
place the char directly behind a byte boundary, thus making your method
give an inaccurate alignment value of zero?
Read again. offsetof will give you zero for c and some value= (offsetof(..., c)+sizeof align_TYPE_inst ance.c) which is 1.

Of course, the implementation may give you a value greater
than sizeof align_TYPE_inst ance.align but this is improbable.

Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Hallvard B Furuseth]

Frederick Gotham writes:

>Hallvard B Furuseth posted:

>With a bunch of helper macros, it works fine. Check me on this
though, I've been staring at it too long:

Oh dear, I _was_ tired. "Check me on this" was not the best thing
to say about this one:

#define LOG2_8BIT(v) (8 - 90/(((v)/4+14)|1) - 2/((v)/2+1))

There is nothing to understand about that except to notice that it works
(up to v=255): I just ran a search of expressions like A-B/(v*C+D|E) and
A-B/(v/C+D|E), for some giving correct the floor(log2(n)) for n=1..v.

I only found variants correct for 6 bits and wanted 8, so I needed two
such terms. Quite possibly there are better types of expressions, or
some of the above form which I skipped. (Didn't bother to reduce the
search space to be small enough that I could check all possibilities.)

Have you been at this sort of stuff for many years? I thought I was
pretty handy at playing around with things like this, but your own
expertise astounds me.

Yes, I like playing around with stuff like that. Haven't done so much
for a while though.

I've been taking so long to reply to your posts because I'm staring at
the macros trying to get the faintest idea of how they work, and I
still haven't begun to comprehend!

Give me time though, and I might figure them out...

#define LOG2_16BIT(v) (8*((v)>255) + LOG2_8BIT((v) >>8*((v)>255) ))

8*((v)>255) === ((v)>255 ? 8 : 0). Since I'm using that twice, the
macro does the same as

#define LOG2_16BIT(v) \
((v) 255 ? 8 + LOG2_8BIT((v) >>8) : 0 + LOG2_8BIT((v) >>0))

Not sure if it's really any need to use such tricks to reduce the size
of the macro expansion. The expanded size just made me a bit nervous.

This does the same given a log2() valid for 32 bits, but more cumbersome
- to ensure that ints are shifted at most 15 bits and longs at most 31
bits. (v>>N 0) === (v>>N >= 1) === (v <= 1<<N) === log2(v) <= N
(if you ignore possible overflow in 1<<N):

#define LOG2_64BIT(v)\
(32*((v)/2L>>31 0) \
+ LOG2_32BIT((v)* 1L >>16*((v)/2L>>31 0) \

>>16*((v)/2L>>31 0)))

LOG2_512BIT() also does the same: 512-bit log2() based on 256-bit log2()
based on...based on 8-bit log2(), except it breaks up the shifts to stay
below 32-bit shifts. Note that (ones+1) is a power of 2.
The enum variant is equivalent, maybe it is easier to read.

Finally, "Name##__c= (val)>>Name == !!(val) ? 1 : -999" in the enum is 1
if the result is correct according to the spec and -999 otherwise. Used
to force a constraint violation in the typedef if the result is wrong.

--
Hallvard