Alternative approach to bitfields

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[i] = BF_GET(unsigned, v, Map_bf, u.fa[i]); 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[i], va[i]) 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[i] = BF_GET(unsigned, v, Map_bf, u.fa[i]); v3 = BF_GET(unsigned, v, Map_bf, f3); v = 0; for (i = 0; i < 4; ++i) BF_OR(v, Map_bf, u.fa[i], va[i]) 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); }

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 .

On Monday, July 23, 2012 3:52:37 AM UTC-4, Jorgen Grahn wrote: > 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 . Only in unusual circumstances. Like bitfields cannot be used when optimization is enabled, as was (is?) true for many years with MS-C/C++ .

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 -- I do not respond to top-posted replies, please don't ask

On Monday, July 23, 2012 10:48:27 AM UTC-4, Victor Bazarov wrote: > 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? 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 > -- > I do not respond to top-posted replies, please don't ask

On Mon, 23 Jul 2012 07:10:02 -0700 (PDT), W Karas <wkaras@yahoo.com> 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.

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: >> > [..] 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? > > 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 -- I do not respond to top-posted replies, please don't ask

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: > > >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.

On Monday, July 23, 2012 4:55:19 PM UTC-4, Victor Bazarov wrote: > 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 fi= xed > > now, but MS did not seem to see it as a priority at the time so... >=20 > If you assume it's fixed now, what is your motivation for inventing s= uch=20 > an "alternative" as Jorgen put it? Is it just for exercise? S= eems to=20 > me something akin to implementing "a better quicksort" or &quot= ;a more=20 > reliable Bresenham's line drawing"... >=20 > V > --=20 > I do not respond to top-posted replies, please don't ask The code is meant to demonstrate (in a fairly short and simple way) an appr= oach, more so than to be a substitute for language-provided bitfields. I u= sed this approach for structures (of bitfields) that were multiples of 10 b= ytes long. The bitfields could be up to 32 bits wide, and could straddle 3= 2-bit boundaries. The ability to have arrays and unions was useful in thes= e structures. I used templates rather than macros (much cleaner), but was = disappointed at how easily both the compilers we use would "give up" (not f= ully inline) in the face of several nested levels of inline function calls. BTW I have implemented a "better" QuickSort. Instead of recursion, it uses= an explicit, resizeable stack in dynamic storage. It's useful for environ= ments without VM-base resizing process call stacks.

On Mon, 23 Jul 2012 16:03:53 -0700 (PDT), W Karas <wkaras@yahoo.com> wrote: >On Monday, July 23, 2012 4:55:19 PM UTC-4, Victor Bazarov wrote: >> 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 >> -- >> I do not respond to top-posted replies, please don't ask > >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 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).

On Monday, July 23, 2012 11:54:17 PM UTC-4, robert...@yahoo.com wrote: > On Mon, 23 Jul 2012 16:03:53 -0700 (PDT), W Karas=20 > wrote: >=20 > >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 Baza= rov wrote: > >> &gt;&gt; On 7/23/2012 10:10 AM, W Karas wrote: > >> &gt;&gt; &amp;gt; [..] Like bitfields cannot be used= when optimization is enabled, 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 assum= e it&#39;s fixed > >> &gt; now, but MS did not seem to see it as a priority at the= time so... > >>=20 > >> If you assume it&#39;s fixed now, what is your motivation fo= r inventing such=20 > >> an &quot;alternative&quot; as Jorgen put it? Is it just= for exercise? Seems to=20 > >> me something akin to implementing &quot;a better quicksort&a= mp;quot; or &quot;a more=20 > >> reliable Bresenham&#39;s line drawing&quot;... > >>=20 > >> V > >> --=20 > >> I do not respond to top-posted replies, please don&#39;t ask > > > >The code is meant to demonstrate (in a fairly short and simple way) a= n approach, more so than to be a substitute for language-provided bitfields= .. I used this approach for structures (of bitfields) that were multiples o= f 10 bytes long. The bitfields could be up to 32 bits wide, and could stra= ddle 32-bit boundaries. The ability to have arrays and unions was useful i= n these structures. I used templates rather than macros (much cleaner), bu= t 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 re= cursion, it uses an explicit, resizeable stack in dynamic storage. It'= s useful for environments without VM-base resizing process call stacks. >=20 >=20 > 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=3Dpartition(p) smallpart,largepart=3Dorderbysize(leftpart,rightpart) quicksort(smallpart) p=3Dlargepart } } ( from http://coding.derkeiler.com/Archive/General/comp.programming/2008-01= /msg00337.html )

On Tue, 24 Jul 2012 11:19:32 -0700 (PDT), W Karas <wkaras@yahoo.com> wrote: >On Monday, July 23, 2012 11:54:17 PM UTC-4, robert...@yahoo.com wrote: >> On Mon, 23 Jul 2012 16:03:53 -0700 (PDT), W Karas >> wrote: >> >> >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 is enabled, 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&#39;s fixed >> >> &gt; now, but MS did not seem to see it as a priority at the time so... >> >> >> >> If you assume it&#39;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&#39;s line drawing&quot;... >> >> >> >> V >> >> -- >> >> I do not respond to top-posted replies, please don&#39;t ask >> > >> >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 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 ) That's correct. As usual for Quicksort you should also avoid Quicksorting small partitions (often n<5), and clean those up en-mass with a final insertion sort pass over the dataset. Wait a minute - I *thought* that bit of pseudo-code looked familiar... ;-)