Alternative approach to bitfields

Discussion in 'C++' started by W Karas, Jul 23, 2012.

1. W KarasGuest

The idea is to define the bitfields using a "map" structure of arrays of char, with each char corresponding to a bit in an unsigned integer. Here is some example code:

/* Notes
** 1. parameters to these macros may appear multiple times in the
** macro definition, so do not use expresions with side-effects as
** actual parameters.
** 2. If parameters to these macros are not in the correct range,
** results are undetermined.
*/

/* Get the value of the bitfield with the given WIDTH at the offset OFS in
** the rvalue RV of unsigned integer type UT.
*/
#define BF_GET_N(UT, RV, WIDTH, OFS) \
(((RV) >> (OFS)) & BF_H_MW(UT, WIDTH))

/* Logically OR the value VAL into lvalue LV after left-bit-shifting it
** by OFS bits.
*/
#define BF_OR_N(LV, OFS, VAL) \
{ BF_H_OR_N_EXPR(LV, OFS, VAL); }

/* Set the value VAL in the bitfield with the given WIDTH at the offset OFS
** in the lvalue LV of unsigned integer type UT.
*/
#define BF_SET_N(UT, LV, WIDTH, OFS, VAL) \
{ ((WIDTH) >= (sizeof(UT) * CHAR_BIT)) ? \
(*&(LV) = (VAL)) : \
(*&(LV) &= ~(BF_H_MW(UT, WIDTH) << (OFS)), \
BF_H_OR_N_EXPR(LV, OFS, VAL)); }

/* A "bitfield map structure" is recursively defined as a C/POD struct or
** union where each member is an array of char or a bitfield map structure.
** Each array of char represents a bitfield. The sizeof the array gives
** the width of the bitfield. The byte offset of the array from the
** start of the top-level structure gives the offset of the bitfield.
*/

/* Get the value of the bitfield in the rvalue RV of unsigned integer type
** UT corresponding to the field FLD in bitfield map structure MSTRU.
*/
#define BF_GET(UT, RV, MSTRU, FLD) \
BF_GET_N(UT, RV, BF_H_WIDTH(MSTRU, FLD), BF_H_OFS(MSTRU, FLD))

/* Logically OR the value VAL into value of the bitfield in the rvalue RV of
** unsigned integer type ** UT corresponding to the field FLD in bitfield map
** structure MSTRU.
*/
#define BF_OR(LV, MSTRU, FLD, VAL) \
BF_OR_N(LV, BF_H_OFS(MSTRU, FLD), VAL)

/* Set the value VAL in the bitfield in the rvalue RV of unsigned integer
** type UT corresponding to the field FLD in bitfield map structure MSTRU.
*/
#define BF_SET(UT, LV, MSTRU, FLD, VAL) \
BF_SET_N(UT, LV, BF_H_WIDTH(MSTRU, FLD), BF_H_OFS(MSTRU, FLD), VAL)

/* --------------------------------------------------------------------- */

/* "Private" macros, not meant for direct use. */

#include <limits.h>

/* Mask of WIDTH and type UT.
*/
#define BF_H_MW(UT, WIDTH) \
((UT) (((WIDTH) >= (sizeof(UT) * CHAR_BIT)) ? \
(~ (UT) 0) : ((((UT) 1) << (WIDTH)) - 1)))

/* BF_OR_N as expression not statement.
*/
#define BF_H_OR_N_EXPR(LV, OFS, VAL) \
(*&(LV) |= ((VAL) << (OFS)))

/* Returns offset of bitfield corresponding to char array FLD in bitfield
** map structure MSTRU.
*/
#define BF_H_WIDTH(MSTRU, FLD) \
(sizeof(((MSTRU *) 0x100)->FLD))

/* Returns width of bitfield corresponding to char array FLD in bitfield
** map structure MSTRU.
*/
#define BF_H_OFS(MSTRU, FLD) \
((((MSTRU *) 0x100)->FLD) - ((char *) 0x100))

/* These macros lay out the bit fields with higher offsets at higher
** significance, but the reverse is also possible.
*/

/* --------------------------------------------------------------------- */

/* Test code */

typedef struct
{
union
{
/* Array of 4 5-bit-wide bitfields (cool eh?). */
char fa[4][5];

struct
{
char f1[6], f2[14];
}
sm;
}
u;

char f3[12];
}
Map_bf;

#include <stdio.h>
#include <stdlib.h>

void bail(void)
{
printf("FAIL\n");
exit(1);
}

int main(void)
{
unsigned va[4], v1, v2, v3, i, v;

v = 0xabcd1234;

for (i = 0; i < 4; ++i)
va = BF_GET(unsigned, v, Map_bf, u.fa);
v3 = BF_GET(unsigned, v, Map_bf, f3);

if (v != 0xabcd1234)
bail();

v = 0x1234abcd;

for (i = 0; i < 4; ++i)
BF_SET(unsigned, v, Map_bf, u.fa, va)
BF_SET(unsigned, v, Map_bf, f3, v3);

if (v != 0xabcd1234)
bail();

v = 0xabcd1234;

v1 = BF_GET(unsigned, v, Map_bf, u.sm.f1);
v2 = BF_GET(unsigned, v, Map_bf, u.sm.f2);
v3 = BF_GET(unsigned, v, Map_bf, f3);

if (v != 0xabcd1234)
bail();

v = 0x1234abcd;

BF_SET(unsigned, v, Map_bf, u.sm.f1, v1)
BF_SET(unsigned, v, Map_bf, u.sm.f2, v2)
BF_SET(unsigned, v, Map_bf, f3, v3)

if (v != 0xabcd1234)
bail();

v = 0xabcd1234;

for (i = 0; i < 4; ++i)
va = BF_GET(unsigned, v, Map_bf, u.fa);
v3 = BF_GET(unsigned, v, Map_bf, f3);

v = 0;

for (i = 0; i < 4; ++i)
BF_OR(v, Map_bf, u.fa, va)
BF_OR(v, Map_bf, f3, v3)

if (v != 0xabcd1234)
bail();

v = 0xabcd1234;

v1 = BF_GET(unsigned, v, Map_bf, u.sm.f1);
v2 = BF_GET(unsigned, v, Map_bf, u.sm.f2);
v3 = BF_GET(unsigned, v, Map_bf, f3);

v = 0;

BF_OR(v, Map_bf, u.sm.f1, v1)
BF_OR(v, Map_bf, u.sm.f2, v2)
BF_OR(v, Map_bf, f3, v3)

if (v != 0xabcd1234)
bail();

printf("SUCCESS\n");

return(0);
}

W Karas, Jul 23, 2012

2. Jorgen GrahnGuest

On Mon, 2012-07-23, W Karas wrote:
> The idea is to define the bitfields using a "map" structure of arrays of char, with each char corresponding to
> a bit in an unsigned integer.

Why do we need an alternative? I didn't read the code carefully, but
I don't see what problem you're trying to solve.

....
> #define BF_SET_N(UT, LV, WIDTH, OFS, VAL) \
> { ((WIDTH) >= (sizeof(UT) * CHAR_BIT)) ? \
> (*&(LV) = (VAL)) : \
> (*&(LV) &= ~(BF_H_MW(UT, WIDTH) << (OFS)), \
> BF_H_OR_N_EXPR(LV, OFS, VAL)); }

....

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

Jorgen Grahn, Jul 23, 2012

3. W KarasGuest

On Monday, July 23, 2012 3:52:37 AM UTC-4, Jorgen Grahn wrote:
> On Mon, 2012-07-23, W Karas wrote:
> &gt; The idea is to define the bitfields using a &quot;map&quot; structure of arrays of char, with each char corresponding to
> &gt; a bit in an unsigned integer.
>
> Why do we need an alternative? I didn't read the code carefully, but
> I don't see what problem you're trying to solve.
>
> ...
> &gt; #define BF_SET_N(UT, LV, WIDTH, OFS, VAL) \
> &gt; { ((WIDTH) &gt;= (sizeof(UT) * CHAR_BIT)) ? \
> &gt; (*&amp;(LV) = (VAL)) : \
> &gt; (*&amp;(LV) &amp;= ~(BF_H_MW(UT, WIDTH) &lt;&lt; (OFS)), \
> &gt; BF_H_OR_N_EXPR(LV, OFS, VAL)); }
> ...
>
> /Jorgen
>
> --
> // Jorgen Grahn &lt;grahn@ Oo o. . .
> \X/ snipabacken.se&gt; O o .

Only in unusual circumstances. Like bitfields cannot be used when optimization is enabled, as was (is?) true for many years with MS-C/C++ .

W Karas, Jul 23, 2012
4. Victor BazarovGuest

On 7/23/2012 10:10 AM, W Karas wrote:
> [..] Like bitfields cannot be used when optimization is enabled, as
> was (is?) true for many years with MS-C/C++ .

What?? Where did you get that information?

V
--

Victor Bazarov, Jul 23, 2012
5. W KarasGuest

On Monday, July 23, 2012 10:48:27 AM UTC-4, Victor Bazarov wrote:
> On 7/23/2012 10:10 AM, W Karas wrote:
> &gt; [..] Like bitfields cannot be used when optimization is enabled, as
> &gt; was (is?) true for many years with MS-C/C++ .
>
> What?? Where did you get that information?

From personal experience back in the mid 1990s. I assume it's fixed now, but MS did not seem to see it as a priority at the time so...

>
> V
> --

W Karas, Jul 23, 2012
6. GeoffGuest

On Mon, 23 Jul 2012 07:10:02 -0700 (PDT), W Karas <>
wrote:

>Only in unusual circumstances. Like bitfields cannot be used when optimization is enabled, as was (is?) true for many years with MS-C/C++ .

What optimization modes affect bitfields? I've never heard of any
problems with bitfields on any version of Microsoft's compilers.

Geoff, Jul 23, 2012
7. Victor BazarovGuest

On 7/23/2012 3:23 PM, W Karas wrote:
> On Monday, July 23, 2012 10:48:27 AM UTC-4, Victor Bazarov wrote:
>> On 7/23/2012 10:10 AM, W Karas wrote:
>> &gt; [..] Like bitfields cannot be used when optimization is enabled, as
>> &gt; was (is?) true for many years with MS-C/C++ .
>>
>> What?? Where did you get that information?

>
> From personal experience back in the mid 1990s. I assume it's fixed
> now, but MS did not seem to see it as a priority at the time so...

If you assume it's fixed now, what is your motivation for inventing such
an "alternative" as Jorgen put it? Is it just for exercise? Seems to
me something akin to implementing "a better quicksort" or "a more
reliable Bresenham's line drawing"...

V
--

Victor Bazarov, Jul 23, 2012
8. W KarasGuest

On Monday, July 23, 2012 4:52:07 PM UTC-4, Geoff wrote:
> On Mon, 23 Jul 2012 07:10:02 -0700 (PDT), W Karas ;
> wrote:
>
> &gt;Only in unusual circumstances. Like bitfields cannot be used when optimization is enabled, as was (is?) true for many years with MS-C/C++ .
>
> What optimization modes affect bitfields? I've never heard of any
> problems with bitfields on any version of Microsoft's compilers.

As best as I can recall now, any optimization for speed could cause code containing bitfields to result in incorrect object code.

W Karas, Jul 23, 2012
9. W KarasGuest

On Monday, July 23, 2012 4:55:19 PM UTC-4, Victor Bazarov wrote:
> On 7/23/2012 3:23 PM, W Karas wrote:
> &gt; On Monday, July 23, 2012 10:48:27 AM UTC-4, Victor Bazarov wrote:
> &gt;&gt; On 7/23/2012 10:10 AM, W Karas wrote:
> &gt;&gt; &amp;gt; [..] Like bitfields cannot be used when optimization isenabled, as
> &gt;&gt; &amp;gt; was (is?) true for many years with MS-C/C++ .
> &gt;&gt;
> &gt;&gt; What?? Where did you get that information?
> &gt;
> &gt; From personal experience back in the mid 1990s. I assume it's fixed
> &gt; now, but MS did not seem to see it as a priority at the time so...
>
> If you assume it's fixed now, what is your motivation for inventing such
> an &quot;alternative&quot; as Jorgen put it? Is it just for exercise? Seems to
> me something akin to implementing &quot;a better quicksort&quot; or &quot;a more
> reliable Bresenham's line drawing&quot;...
>
> V
> --

The code is meant to demonstrate (in a fairly short and simple way) an approach, more so than to be a substitute for language-provided bitfields. I used this approach for structures (of bitfields) that were multiples of 10 bytes long. The bitfields could be up to 32 bits wide, and could straddle 32-bit boundaries. The ability to have arrays and unions was useful in these structures. I used templates rather than macros (much cleaner), but was disappointed at how easily both the compilers we use would "give up" (not fully inline) in the face of several nested levels of inline function calls.

BTW I have implemented a "better" QuickSort. Instead of recursion, it usesan explicit, resizeable stack in dynamic storage. It's useful for environments without VM-base resizing process call stacks.

W Karas, Jul 24, 2012
10. W KarasGuest

On Monday, July 23, 2012 11:54:17 PM UTC-4, wrote:
> On Mon, 23 Jul 2012 16:03:53 -0700 (PDT), W Karas
> wrote:
>
> &gt;On Monday, July 23, 2012 4:55:19 PM UTC-4, Victor Bazarov wrote:
> &gt;&gt; On 7/23/2012 3:23 PM, W Karas wrote:
> &gt;&gt; &amp;gt; On Monday, July 23, 2012 10:48:27 AM UTC-4, Victor Bazarov wrote:
> &gt;&gt; &amp;gt;&amp;gt; On 7/23/2012 10:10 AM, W Karas wrote:
> &gt;&gt; &amp;gt;&amp;gt; &amp;amp;gt; [..] Like bitfields cannot be usedwhen optimization is enabled, as
> &gt;&gt; &amp;gt;&amp;gt; &amp;amp;gt; was (is?) true for many years withMS-C/C++ .
> &gt;&gt; &amp;gt;&amp;gt;
> &gt;&gt; &amp;gt;&amp;gt; What?? Where did you get that information?
> &gt;&gt; &amp;gt;
> &gt;&gt; &amp;gt; From personal experience back in the mid 1990s. I assume it&amp;#39;s fixed
> &gt;&gt; &amp;gt; now, but MS did not seem to see it as a priority at thetime so...
> &gt;&gt;
> &gt;&gt; If you assume it&amp;#39;s fixed now, what is your motivation for inventing such
> &gt;&gt; an &amp;quot;alternative&amp;quot; as Jorgen put it? Is it justfor exercise? Seems to
> &gt;&gt; me something akin to implementing &amp;quot;a better quicksort&amp;quot; or &amp;quot;a more
> &gt;&gt; reliable Bresenham&amp;#39;s line drawing&amp;quot;...
> &gt;&gt;
> &gt;&gt; V
> &gt;&gt; --
> &gt;&gt; I do not respond to top-posted replies, please don&amp;#39;t ask
> &gt;
> &gt;The code is meant to demonstrate (in a fairly short and simple way) an approach, more so than to be a substitute for language-provided bitfields.. I used this approach for structures (of bitfields) that were multiples of 10 bytes long. The bitfields could be up to 32 bits wide, and could straddle 32-bit boundaries. The ability to have arrays and unions was useful in these structures. I used templates rather than macros (much cleaner), but was disappointed at how easily both the compilers we use would &quot;giveup&quot; (not fully inline) in the face of several nested levels of inlinefunction calls.
> &gt;
> &gt;BTW I have implemented a &quot;better&quot; QuickSort. Instead of recursion, it uses an explicit, resizeable stack in dynamic storage. It's useful for environments without VM-base resizing process call stacks.
>
>
> Why? Properly implemented Quicksort (semi-recursive, recurse on the
> smaller partition only), does not usually have a big stack frame, and
> a quite limited recursion depth ( lg(n) - so even a billion items will
> result in no more than 30 levels).

Cool, thanks, that handn't occurred to me, I assume you mean like:

quicksort(partition p)
{
loop while ((size of p) > 1)
{
leftpart,rightpart=partition(p)
smallpart,largepart=orderbysize(leftpart,rightpart)
quicksort(smallpart)
p=largepart
}
}

( from http://coding.derkeiler.com/Archive/General/comp.programming/2008-01/msg00337.html )

W Karas, Jul 24, 2012