• bearophile (27/27) Nov 19 2007 Until D gains C-style bitfields it can be created a compile-time functio...
• Jarrett Billingsley (76/110) Nov 19 2007 I actually came up with this for a D OS kernel my friends and I are work...
• bearophile (24/24) Nov 20 2007 Thank you very much Jarrett Billingsley, that's even better. I'll use a ...
• Jarrett Billingsley (6/18) Nov 20 2007 Cool :)
• bearophile (198/202) Nov 20 2007 But later I have changed it again. I have changed the first part of the ...
• Jarrett Billingsley (10/25) Nov 21 2007 This isn't an entirely unbiased comparison. If you used dmd and dmc, or...
• bearophile (6/11) Nov 22 2007 I have tested what I use. I'll try gdc if I succed its installation, but...
• bearophile (115/115) Nov 27 2007 For reference, this is my last version so far, I think this solves both ...

bearophile <bearophileHUGS lycos.com> writes:

Until D gains C-style bitfields it can be created a compile-time function that
returns the pairs of methods that take/return ubyte/ushort/uint/ulong, to be
used by a mixin. Something like:

union TyIntFloat {
  int      i;                 // as integer
  float    f;                 // as float 
  // as bit fields:
  mixin(Bitfields!("i       
                   sign 1
                   biasedexponent 8
                   significand 23"));
}

Here "i" is the name of the unsigned integral variable to be splitted in bit
fields.
std.string.split works at compile time too, it can be used to split the input
string.
Something like that can be useful in Tango too (if not already present), but I
presume it's difficult to make it optimize the code produced.

That
Bitfields!("i sign 1 biasedexponent 8 significand 23")
is supposed to return a string of code that contains six methods like:
"
uint sign()                 { return i & ...; }
void sign(uint x)           { i = ...; }
uint biasedexponent()       { return ...; }
void biasedexponent(uint x) { i = ...; }
uint significand()          { return ...; }
void significand(uint x)    { i = ...; }
"

The sum of the numbers is cheeked to be 8, 16, 32 or 64. According to such
total that "i" variable and the input/output values have type as ubyte, ushort,
uint or ulong.

Bye and thank you,
bearophile

"Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:

"bearophile" <bearophileHUGS lycos.com> wrote in message 
news:fhrpoi$1i2a$1 digitalmars.com...
 Until D gains C-style bitfields it can be created a compile-time function 
 that returns the pairs of methods that take/return 
 ubyte/ushort/uint/ulong, to be used by a mixin. Something like:

 union TyIntFloat {
  int      i;                 // as integer
  float    f;                 // as float
  // as bit fields:
  mixin(Bitfields!("i
                   sign 1
                   biasedexponent 8
                   significand 23"));
 }

 Here "i" is the name of the unsigned integral variable to be splitted in 
 bit fields.
 std.string.split works at compile time too, it can be used to split the 
 input string.
 Something like that can be useful in Tango too (if not already present), 
 but I presume it's difficult to make it optimize the code produced.

 That
 Bitfields!("i sign 1 biasedexponent 8 significand 23")
 is supposed to return a string of code that contains six methods like:
 "
 uint sign()                 { return i & ...; }
 void sign(uint x)           { i = ...; }
 uint biasedexponent()       { return ...; }
 void biasedexponent(uint x) { i = ...; }
 uint significand()          { return ...; }
 void significand(uint x)    { i = ...; }
 "

 The sum of the numbers is cheeked to be 8, 16, 32 or 64. According to such 
 total that "i" variable and the input/output values have type as ubyte, 
 ushort, uint or ulong.

 Bye and thank you,
 bearophile

I actually came up with this for a D OS kernel my friends and I are working 
on.  It looks like this:

struct SomeStruct
{
    uint flags;
    mixin(Bitfield!(flags, "sign", 1, "biasedExponent", 8, "significand", 
23));
}

The implementation:

template Bitfield(alias data, Args...)
{
    static assert(!(Args.length & 1), "Bitfield arguments must be an even 
number");
    const char[] Bitfield = BitfieldShim!((typeof(data)).stringof, data, 
Args).Ret;
}

// Odd bug in D templates -- putting "data.stringof" as a template argument 
gives it the
// string of the type, rather than the string of the symbol.  This shim 
works around that.
template BitfieldShim(char[] typeStr, alias data, Args...)
{
    const char[] Name = data.stringof;
    const char[] Ret = BitfieldImpl!(typeStr, Name, 0, Args).Ret;
}

template BitfieldImpl(char[] typeStr, char[] nameStr, int offset, Args...)
{
    static if(Args.length == 0)
        const char[] Ret = "";
    else
    {
        const char[] Name = Args[0];
        const int Size = Args[1];
        const int Mask = Bitmask!(Size);

        const char[] Getter = "public " ~ typeStr ~ " " ~ Name ~ "() { 
return ( " ~
            nameStr ~ " >> " ~ Itoh!(offset) ~ " ) & " ~ Itoh!(Mask) ~ 
"; }";

        const char[] Setter = "public void " ~ Name ~ "(" ~ typeStr ~ " val) 
{ " ~
            nameStr ~ " = (" ~ nameStr ~ " & " ~ Itoh!(~(Mask << offset)) ~ 
") | ((val & " ~
            Itoh!(Mask) ~ ") << " ~ Itoh!(offset) ~ "); }";

        const char[] Ret = Getter ~ Setter ~ BitfieldImpl!(typeStr, nameStr, 
offset + Size, Args[2 .. $]).Ret;
    }
}

template Itoa(int i)
{
    static if(i < 0)
        const char[] Itoa = "-" ~ IntToStr!(-i, 10);
    else
        const char[] Itoa = IntToStr!(i, 10);
}

template Itoh(int i)
{
    const char[] Itoh = "0x" ~ IntToStr!(i, 16);
}

template Digits(int i)
{
    const char[] Digits = "0123456789abcdefghijklmnopqrstuvwxyz"[0 .. i];
}

template IntToStr(ulong i, int base)
{
    static if(i >= base)
        const char[] IntToStr = IntToStr!(i / base, base) ~ Digits!(base)[i 
% base];
    else
        const char[] IntToStr = "" ~ Digits!(base)[i % base];
}

template Bitmask(int size)
{
    const int Bitmask = (1 << size) - 1;
} 

bearophile <bearophileHUGS lycos.com> writes:

Thank you very much Jarrett Billingsley, that's even better. I'll use a
modified version of it in my code (with your name attached). Lately I tend to
use compile-time functions more than templates, because I think they are a bit
more readable. I have added another test, on the sum of the lens to see if they
are equal to data.sizeof*8, because I like to avoid bugs all the times it's
possible:

template Bitfield(alias data, Args...) {
    static assert(!(Args.length & 1), "Bitfield arguments must be an even
number");
    static assert(data.sizeof*8 == _SumLens!(Args),
                  "The sum of bit fields is different from data.sizeof*8");
    const char[] Bitfield = _BitfieldShim!((typeof(data)).stringof, data,
Args).Ret;
}

private template _SumLens(Args...) {
    static if(Args.length == 0)
        const uint _SumLens = 0;
    else
        const uint _SumLens = Args[1] + _SumLens!(Args[2 .. $]);
}

I have also added a newline at the end of Getter and Setter, so the methods
become listed in separated lines and you can see them better if you print the
whole string result:

const char[] Getter = "public " ~ typeStr ~ " " ~ Name ~ "() { return ( " ~
    nameStr ~ " >> " ~ Itoh!(offset) ~ " ) & " ~ Itoh!(Mask) ~ "; }\n";

const char[] Setter = "public void " ~ Name ~ "(" ~ typeStr ~ " val) { " ~
    nameStr ~ " = (" ~ nameStr ~ " & " ~ Itoh!(~(Mask << offset)) ~
    ") | ((val & " ~ Itoh!(Mask) ~ ") << " ~ Itoh!(offset) ~ "); }\n";

Currently I am writing the module tests for Bitfield(), to see if it works when
data is a ubyte/ushort/ulong too.
I don't know if I'll need to make it optimize some the produced code, probably
the compiler is enough to optimize it in most cases.
I'd also like to do some speed comparison with the bitfields management of GCC.

Bye,
bearophile

"Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:

"bearophile" <bearophileHUGS lycos.com> wrote in message 
news:fhufar$2hu$1 digitalmars.com...
 Thank you very much Jarrett Billingsley, that's even better. I'll use a 
 modified version of it in my code (with your name attached). Lately I tend 
 to use compile-time functions more than templates, because I think they 
 are a bit more readable. I have added another test, on the sum of the lens 
 to see if they are equal to data.sizeof*8, because I like to avoid bugs 
 all the times it's possible:

Cool :)

 Currently I am writing the module tests for Bitfield(), to see if it works 
 when data is a ubyte/ushort/ulong too.
 I don't know if I'll need to make it optimize some the produced code, 
 probably the compiler is enough to optimize it in most cases.
 I'd also like to do some speed comparison with the bitfields management of 
 GCC.

If you're using it in a struct, I'd be very surprised if the call weren't 
optimized out, in which case I'd expect the performance to be about the same 
as C bitfields. 

bearophile <bearophileHUGS lycos.com> writes:

Jarrett Billingsley:

 Cool :)

But later I have changed it again. I have changed the first part of the
Bitfield code to this, because sometimes you don't need to access the whole
data:

template Bitfield(alias data, Args...) {
    static assert(!(Args.length & 1), "Bitfield arguments must be an even
number");
    static assert(data.sizeof*8 >= _SumLens!(Args),
                  "The sum of bit fields is bigger than data.sizeof*8");
    const char[] Bitfield = _BitfieldShim!((typeof(data)).stringof, data,
Args).Ret;
}

private template _SumLens(Args...) {
    static if(Args.length == 0)
        const uint _SumLens = 0;
    else {
        static assert(Args[1] > 0, "Bitfield '" ~ Args[0] ~ "' is <= 0");
        const uint _SumLens = Args[1] + _SumLens!(Args[2 .. $]);
    }
}


 If you're using it in a struct, I'd be very surprised if the call weren't 
 optimized out, in which case I'd expect the performance to be about the same 
 as C bitfields.

The calls become inlined, but the results may surprise you anyway :-)
For the speed tests I have used this simple D code on a very old PC:

import std.stdio;

// Bitfield code here...

struct INTORFLOAT {
    uint i;
    mixin(Bitfield!(i, "sign", 1, "biasedexponent", 8, "significand", 23));
}

void main() {
    ulong tot;
    INTORFLOAT f;
    const N = 25;

    uint v[N] = [1628676761, 1620574103, 1237153253, 1098880307, 87513741,
                 13181925, 14686126, 7429435, 16286706, 6474381,
                 4879794, 7734725, 3745958, 13353858, 4236193,
                 7587, 4309, 28846, 7313, 14516,
                 126, 143, 171, 221, 156];

    for(int j = 0; j < 10_000_000; j++)
        for(int i = 0; i < N; i++) {
            f.i = v[i];
            f.biasedexponent = f.biasedexponent / 2;
            tot += f.biasedexponent + f.sign;
            //printf("%d %d\n", f.i, tot);
        }

   printf("%d\n", tot);
}


The C code:

#include <stdio.h>

#define N 25

typedef union {
    unsigned int i;
    struct {
        unsigned int sign: 1;
        unsigned int biasedexponent: 8;
        unsigned int significand: 23;
    } bits;
} INTORFLOAT;

int main(void) {
    int i, j;
    unsigned long long tot = 0;
    INTORFLOAT f;

    unsigned int v[N] = {1628676761, 1620574103, 1237153253, 1098880307,
87513741,
                         13181925, 14686126, 7429435, 16286706, 6474381,
                         4879794, 7734725, 3745958, 13353858, 4236193,
                         7587, 4309, 28846, 7313, 14516,
                         126, 143, 171, 221, 156};

    for(j = 0; j < 10000000; j++)
        for(i = 0; i < N; i++) {
            f.i = v[i];
            f.bits.biasedexponent = f.bits.biasedexponent / 2; // line1
            tot += f.bits.biasedexponent + f.bits.sign; // line2
            //printf("%d %d\n", f.i, tot);
        }

   printf("%d\n", tot);
}


I have compiled them with:
DMD: v1.023
dmd -O -inline -release bitfields1.d

gcc: V. 3.4.2 (mingw-special)
gcc -O3 -s bitfields1.c -o bitfields1


Bitfield produces the following getters and setters:
public uint sign() { return (i >> 0x0) & 0x1; }
public void sign(uint val) { i = (i & 0xfffffffffffffffe) | ((val & 0x1) <<
0x0); }
public uint biasedexponent() { return (i >> 0x1) & 0xff; }
public void biasedexponent(uint val) { i = (i & 0xfffffffffffffe01) | ((val &
0xff) << 0x1); }
public uint significand() { return (i >> 0x9) & 0x7fffff; }
public void significand(uint val) { i = (i & 0x1ff) | ((val & 0x7fffff) <<
0x9); }

The C code runs about 2.5 times faster than the D code (on a faster CPU the
difference is probably smaller). (The numerical output of the code is
fortunately the same!). I have tested that the methods (member functions)
actually become inlined.
Removing line1 and line2 from both the C and D code the running time becomes
(much smaller and) equal between D and C, so I presume the D slowdown is just
in the reading/writing of the bit fields.

The Bitfield code can be improved (but such improvement of the templates has
resulted hairy, because the code has to adapt to data of different sizeof) to
produce a method like this:

public void biasedexponent(uint val) { i = (i & 0xfffffe01) | ((val & 0xff) <<
0x1); }

With that the running time of the D code becomes just about 2 times the C code.


Just for reference the ASM code of the following C code:

#include <stdio.h>

#define N 25

typedef union {
    unsigned int i;
    struct {
        unsigned int sign: 1;
        unsigned int biasedexponent: 8;
        unsigned int significand: 23;
    } bits;
} INTORFLOAT;

int main(void) {
    int i;
    unsigned long tot = 0;
    INTORFLOAT f;

    unsigned int v[N] = {1628676761, 1620574103, 1237153253, 1098880307,
87513741,
                         13181925, 14686126, 7429435, 16286706, 6474381,
                         4879794, 7734725, 3745958, 13353858, 4236193,
                         7587, 4309, 28846, 7313, 14516,
                         126, 143, 171, 221, 156};

    for(i = 0; i < N; i++) {
        f.i = v[i];
        f.bits.biasedexponent = f.bits.biasedexponent / 2; // line1
        tot += f.bits.biasedexponent + f.bits.sign; // line2
    }

   printf("%d\n", tot);
}


Produced by:
gcc -O3 -S bitfields2.c -o bitfields2.asm

Is:

	.file	"bitfields2.c"
	.def	___main;	.scl	2;	.type	32;	.endef
	.data
	.align 4
LC0:
	.long	1628676761
	.long	1620574103
	.long	1237153253
	.long	1098880307
	.long	87513741
	.long	13181925
	.long	14686126
	.long	7429435
	.long	16286706
	.long	6474381
	.long	4879794
	.long	7734725
	.long	3745958
	.long	13353858
	.long	4236193
	.long	7587
	.long	4309
	.long	28846
	.long	7313
	.long	14516
	.long	126
	.long	143
	.long	171
	.long	221
	.long	156
	.section .rdata,"dr"
LC1:
	.ascii "%d\12\0"
	.text
	.p2align 4,,15
.globl _main
	.def	_main;	.scl	2;	.type	32;	.endef
_main:
	pushl	%ebp
	movl	$16, %eax
	movl	%esp, %ebp
	pushl	%ebx
	subl	$132, %esp
	andl	$-16, %esp
	call	__alloca
	call	___main
	movl	$100, %ecx
	leal	-120(%ebp), %eax
	movl	$LC0, %edx
	movl	%ecx, 8(%esp)
	xorl	%ebx, %ebx
	movl	%edx, 4(%esp)
	movl	%eax, (%esp)
	call	_memcpy
	xorl	%ecx, %ecx
	.p2align 4,,15
L5:
	movl	-120(%ebp,%ecx,4), %edx
	incl	%ecx
	movl	%edx, %eax
	shrl	$2, %eax
	andl	$1, %edx
	andl	$127, %eax
	addl	%edx, %eax
	addl	%eax, %ebx
	cmpl	$24, %ecx
	jle	L5
	movl	%ebx, 4(%esp)
	movl	$LC1, (%esp)
	call	_printf
	movl	-4(%ebp), %ebx
	leave
	ret
	.def	_memcpy;	.scl	3;	.type	32;	.endef
	.def	_printf;	.scl	3;	.type	32;	.endef

I have no good way to see the ASM generated by dmd yet (I may buy Walter's
utility). (Maybe some of you can show that asm, but remember to remove the
outer j loop as in the C version).

My obvious conclusion is that I hope to see built-in bitfields in D ;-)
The D docs say they aren't used often, but now and then I translate C code to D
and I don't want to write many (slow) getter and setter properties like that :-)

Bye,
bearophile

"Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:

"bearophile" <bearophileHUGS lycos.com> wrote in message 
news:fi0054$2q9t$1 digitalmars.com...

 I have compiled them with:
 DMD: v1.023
 dmd -O -inline -release bitfields1.d

 gcc: V. 3.4.2 (mingw-special)
 gcc -O3 -s bitfields1.c -o bitfields1

 ...
 Just for reference the ASM code of the following C code:
 ...
 I have no good way to see the ASM generated by dmd yet (I may buy Walter's 
 utility). (Maybe some of you can show that asm, but remember to remove the 
 outer j loop as in the C version).

This isn't an entirely unbiased comparison.  If you used dmd and dmc, or gcc 
and gdc, that would take out at least one very large variable: that dmd and 
gcc have two completely different backends and optimizers.  From anecdotal 
evidence I'd say the gcc (and by proxy, gdc) backend is far more mature than 
dmd's when it comes to optimization.

 My obvious conclusion is that I hope to see built-in bitfields in D ;-)
 The D docs say they aren't used often, but now and then I translate C code 
 to D and I don't want to write many (slow) getter and setter properties 
 like that :-)

I agree.  Bitfields are "seldom used" but when you need them for system 
programming (which is what D is supposed to be for!) they're an awful pain 
to have to emulate. 

bearophile <bearophileHUGS lycos.com> writes:

Jarrett Billingsley:
 This isn't an entirely unbiased comparison.  If you used dmd and dmc, or gcc 
 and gdc, that would take out at least one very large variable: that dmd and 
 gcc have two completely different backends and optimizers.  From anecdotal 
 evidence I'd say the gcc (and by proxy, gdc) backend is far more mature than 
 dmd's when it comes to optimization.

I have tested what I use. I'll try gdc if I succed its installation, but I
think its install procedure is more complex.

If you look at the ShedSkin installer I have helped for, you can see the
not-win version is just the Python files and the C++ classes, while the Windows
version is a WinRar-created (very compressed) "installer" that contains the
same things plus the whole necessary parts of MinGW alredy set to go.
Installing ShedSkin on Win is 1 click or little more. I presume dmd on Win can
reach the same level of user-frieldlness... :-)

http://sourceforge.net/project/showfiles.php?group_id=142788

Bye,
bearophile

bearophile <bearophileHUGS lycos.com> writes:

For reference, this is my last version so far, I think this solves both a bug,
and makes it faster at runtime, but it needs much more testing:

// By Jarrett Billingsley <kb3ctd2 yahoo.com>
// Improved by leonardo maffi, V1.1, Nov 26 2007
// This code needs much more testing

template Bitfield(alias data, Args...) {
    static assert(!(Args.length & 1), "Bitfield arguments must be an even
number");
    static assert(data.sizeof*8 >= _SumLens!(Args),
                  "The sum of bit fields is bigger than data.sizeof*8");
    const char[] Bitfield = _BitfieldShim!((typeof(data)).stringof, data,
Args).Ret;
}

private template _SumLens(Args...) {
    static if(Args.length == 0)
        const uint _SumLens = 0;
    else {
        static assert(Args[1] > 0, "Bitfield '" ~ Args[0] ~ "' is <= 0");
        const uint _SumLens = Args[1] + _SumLens!(Args[2 .. $]);
    }
}

// Odd bug in D templates -- putting "data.stringof" as a template argument
// gives it the string of the type, rather than the string of the symbol.
// This shim works around that.
private template _BitfieldShim(char[] typeStr, alias data, Args...) {
    const char[] Name = data.stringof;
    const char[] Ret = _BitfieldImpl!(data, typeStr, Name, 0, Args).Ret;
}

private template _BitfieldImpl(alias data, char[] typeStr, char[] nameStr, int
offset, Args...) {
    static if(Args.length == 0)
        const char[] Ret = "";
    else {
        const char[] Name = Args[0];
        const int Size = Args[1];

        static if (data.sizeof < 8) {
            const int Mask = _bitmask32(Size);
            const char[] Shift1 = "0x" ~ _intToStr32(~(Mask << offset), 16);
        } else {
            const long Mask = _bitmask64(Size);
            const char[] Shift1 = "0x" ~ _intToStr64(~(Mask << offset), 16);
        }

        const char[] Getter = "public " ~ typeStr ~ " " ~ Name ~ "() { return
(" ~
            nameStr ~ " >> " ~ _itoh(offset) ~ ") & " ~ _itoh(Mask) ~ "; }\n";

        const char[] Setter = "public void " ~ Name ~ "(" ~ typeStr ~ " val) {
" ~
            nameStr ~ " = (" ~ nameStr ~ " & " ~ Shift1 ~
            ") | ((val & " ~ _itoh(Mask) ~ ") << " ~ _itoh(offset) ~ "); }\n\n";

        const char[] Ret = Getter ~ Setter ~
                           _BitfieldImpl!(data, typeStr, nameStr, offset +
Size, Args[2 .. $]).Ret;
    }
}

private int _bitmask32(int size) {
    return (1 << size) - 1;
}

private long _bitmask64(long size) {
    return (1L << size) - 1;
}

private char[] _itoa(long i) {
    if (i < 0)
        return "-" ~ _intToStr64(-i, 10);
    else
        return _intToStr64(i, 10);
}

private char[] _itoh(long i) {
    return "0x" ~ _intToStr64(i, 16);
}

private char[] _intToStr32(uint i, int base) {
    const CONV_CHARS = "0123456789abcdefghijklmnopqrstuvwxyz";
    if (i >= base)
        return _intToStr32(i / base, base) ~ CONV_CHARS[i % base];
    else
        return "" ~ CONV_CHARS[i % base];
}

private char[] _intToStr64(ulong i, int base) {
    const CONV_CHARS = "0123456789abcdefghijklmnopqrstuvwxyz";
    if (i >= base)
        return _intToStr64(i / base, base) ~ CONV_CHARS[i % base];
    else
        return "" ~ CONV_CHARS[i % base];
}

//=======================================================================

struct SomeStruct {
    uint flags;
    mixin(Bitfield!(flags, "sign", 1, "biasedExponent", 8, "significand", 23));
}

import std.stdio;

void main() {
    uint flags;
    char[] r1a = Bitfield!(flags, "sign", 1, "biasedExponent", 8,
"significand", 23);
    char[] r1b =
"public uint sign() { return (flags >> 0x0) & 0x1; }
public void sign(uint val) { flags = (flags & 0xfffffffe) | ((val & 0x1) <<
0x0); }

public uint biasedExponent() { return (flags >> 0x1) & 0xff; }
public void biasedExponent(uint val) { flags = (flags & 0xfffffe01) | ((val &
0xff) << 0x1); }

public uint significand() { return (flags >> 0x9) & 0x7fffff; }
public void significand(uint val) { flags = (flags & 0x1ff) | ((val & 0x7fffff)
<< 0x9); }

";
    assert(r1a == r1b);

    //writefln( Bitfield!(flags, "sign", 1, "biasedExponent", 8, "significand",
24) ); // raises error

    ubyte otto;
    char[] r2a = Bitfield!(otto, "sign", 1, "seven", 7);
    char[] r2b =
"public ubyte sign() { return (otto >> 0x0) & 0x1; }
public void sign(ubyte val) { otto = (otto & 0xfffffffe) | ((val & 0x1) <<
0x0); }

public ubyte seven() { return (otto >> 0x1) & 0x7f; }
public void seven(ubyte val) { otto = (otto & 0xffffff01) | ((val & 0x7f) <<
0x1); }

";
    assert(r2a == r2b);

    ubyte d1;
    writefln(Bitfield!(d1, "f1", 3, "s1", 5));

    ushort d2;
    writefln(Bitfield!(d2, "f2", 9, "s2", 7));

    uint d3;
    writefln(Bitfield!(d3, "f3", 17, "s3", 15));

    ulong d4;
    writefln(Bitfield!(d4, "f4", 31, "s4", 33));
}

Bye,
bearophile