www.digitalmars.com         C & C++   DMDScript  

D - slicing bit arrays

reply "Sean L. Palmer" <palmer.sean verizon.net> writes:
Is there a function in D that converts a slice of a bit array into an int?
Or stores a part of an int into a region of memory?  This could be D's
equivalent to bitfields.

Problem is that bitfields really should be declarative, not commands.  I'd
much rather state once that x is the number formed by bits 7 thru 12 of the
integer at this location than state it every time I want to work with that
location x.

But I can imagine some applications for it, for general-purpose bitmap
conversion.  Compression algorithms.  SIMD ops are good at doing this sort
of thing.  Grab some memory and rearrange it, shift it, shuffle it around a
bit, and store it somewhere else.  The shifting and masking will deal with
the alignment requirements.

Some ops work best with compile-time constant operands.  This would be one
hell of a language primitive feature.  General purpose bit mover.  The
actual mechanism of moving the bits is hidden so that it could be done with
any resource available.  This could be implemented as an alternate way to
move data from memory location to register, for compile-time constant
offsets and sizes it is pretty fast.

bit[256] x;
const int foooffset = 6;
const int foosize = 4;
const int feeoffset = 10;
const int feesize = 5;
bit[] foo = (bit[foosize])x[foooffset .. foooffset+foosize]; // foo becomes
offset 6 thru 9 of whatever's in x

int value = foo[]; // hmm wouldn't want an accidental conversion of the
*pointer* to the value, now would we?
int value2 = x[feeoffset .. feeoffset + feesize]; // grab bits 10 thru 14 of
x

typing D's start .. end ranges.  Test if bits x[feeoffset ..
feeoffset+feesize] are all set
{

use alias to declare a temporary of inferred type.

not a type.  But it seems handy.
    x_foo[] = (x_fee[] << 1) | (x_fee[] >> (feesize-1));   // funky way to
pull off a rol
}

Does that compile?  ;)

But I'd rather have:

bit x[bit[6] reserved; ubit[4] foo; bit[5] fee];
if (~x.fee[])
{
    x.foo[] = x.fee[] <>< 1;
}

Wouldn't you?  With ints as template parameters that can get powerful.

template endianness(int size)
{
    void convert(bit[size] value)
    {
         for (i in 0 .. size by 8)
            value[i .. i + 8] <-> value[size - i - 8 .. size - i]    //
obviously I mean to end here... why quibble about semicolons?
    }
}

int k = 0x04030201;
with instance(endianness(k.size*8)) convert(k);
assert(k == 0x01020304);

That should go in Phobos.

Wow, this has been fun.

Sean
Apr 16 2003
parent reply "Walter" <walter digitalmars.com> writes:
At the moment, you can't slice bit fields unless they align on a byte
boundary.

"Sean L. Palmer" <palmer.sean verizon.net> wrote in message
news:b7le1s$31kf$1 digitaldaemon.com...

 Is there a function in D that converts a slice of a bit array into an int?
 Or stores a part of an int into a region of memory?  This could be D's
 equivalent to bitfields.

 Problem is that bitfields really should be declarative, not commands.  I'd
 much rather state once that x is the number formed by bits 7 thru 12 of


the

 integer at this location than state it every time I want to work with that
 location x.

 But I can imagine some applications for it, for general-purpose bitmap
 conversion.  Compression algorithms.  SIMD ops are good at doing this sort
 of thing.  Grab some memory and rearrange it, shift it, shuffle it around


a

 bit, and store it somewhere else.  The shifting and masking will deal with
 the alignment requirements.

 Some ops work best with compile-time constant operands.  This would be one
 hell of a language primitive feature.  General purpose bit mover.  The
 actual mechanism of moving the bits is hidden so that it could be done


with

 any resource available.  This could be implemented as an alternate way to
 move data from memory location to register, for compile-time constant
 offsets and sizes it is pretty fast.

 bit[256] x;
 const int foooffset = 6;
 const int foosize = 4;
 const int feeoffset = 10;
 const int feesize = 5;
 bit[] foo = (bit[foosize])x[foooffset .. foooffset+foosize]; // foo


becomes

 offset 6 thru 9 of whatever's in x

 int value = foo[]; // hmm wouldn't want an accidental conversion of the
 *pointer* to the value, now would we?
 int value2 = x[feeoffset .. feeoffset + feesize]; // grab bits 10 thru 14


of

 x

 typing D's start .. end ranges.  Test if bits x[feeoffset ..
 feeoffset+feesize] are all set
 {

 use alias to declare a temporary of inferred type.

 not a type.  But it seems handy.
     x_foo[] = (x_fee[] << 1) | (x_fee[] >> (feesize-1));   // funky way to
 pull off a rol
 }

 Does that compile?  ;)

 But I'd rather have:

 bit x[bit[6] reserved; ubit[4] foo; bit[5] fee];
 if (~x.fee[])
 {
     x.foo[] = x.fee[] <>< 1;
 }

 Wouldn't you?  With ints as template parameters that can get powerful.

 template endianness(int size)
 {
     void convert(bit[size] value)
     {
          for (i in 0 .. size by 8)
             value[i .. i + 8] <-> value[size - i - 8 .. size - i]    //
 obviously I mean to end here... why quibble about semicolons?
     }
 }

 int k = 0x04030201;
 with instance(endianness(k.size*8)) convert(k);
 assert(k == 0x01020304);

 That should go in Phobos.

 Wow, this has been fun.

 Sean
May 09 2003
parent reply "Sean L. Palmer" <palmer.sean verizon.net> writes:
Argh... do you have any plans to expand bit array slicing capability?

You gotta admit a general purpose bit manipulator would be way cool.

I could write these manipulators in C really easily.  Recognizing the
various cases and emitting custom asm for each one would be straightforward.
Recognizing the special case of constant offsets or sizes would be awesome
if it were done by the compiler because doing that kind of stuff manually is
tedious and error prone (and not very portable, or readable).

This seems like a code generation issue that is turning into a language
semantics issue.

And being able to convert a bit slice into an int is trivial once you can
move bits:  Just shifts and masks.  It's what bit fields do in C.

I guess I'm not ready to give up bitfields yet;  in fact I want to take them
farther!

Sean

"Walter" <walter digitalmars.com> wrote in message
news:b9gpa1$ott$2 digitaldaemon.com...

 At the moment, you can't slice bit fields unless they align on a byte
 boundary.

 "Sean L. Palmer" <palmer.sean verizon.net> wrote in message
 news:b7le1s$31kf$1 digitaldaemon.com...

 Is there a function in D that converts a slice of a bit array into an




int?

 Or stores a part of an int into a region of memory?  This could be D's
 equivalent to bitfields.

 Problem is that bitfields really should be declarative, not commands.




I'd

 much rather state once that x is the number formed by bits 7 thru 12 of


 the

 integer at this location than state it every time I want to work with




that

 location x.

 But I can imagine some applications for it, for general-purpose bitmap
 conversion.  Compression algorithms.  SIMD ops are good at doing this




sort

 of thing.  Grab some memory and rearrange it, shift it, shuffle it




around

 a

 bit, and store it somewhere else.  The shifting and masking will deal




with

 the alignment requirements.

 Some ops work best with compile-time constant operands.  This would be




one

 hell of a language primitive feature.  General purpose bit mover.  The
 actual mechanism of moving the bits is hidden so that it could be done


 with

 any resource available.  This could be implemented as an alternate way




to

 move data from memory location to register, for compile-time constant
 offsets and sizes it is pretty fast.

 bit[256] x;
 const int foooffset = 6;
 const int foosize = 4;
 const int feeoffset = 10;
 const int feesize = 5;
 bit[] foo = (bit[foosize])x[foooffset .. foooffset+foosize]; // foo


 becomes

 offset 6 thru 9 of whatever's in x

 int value = foo[]; // hmm wouldn't want an accidental conversion of the
 *pointer* to the value, now would we?
 int value2 = x[feeoffset .. feeoffset + feesize]; // grab bits 10 thru




14

 of

 x

 typing D's start .. end ranges.  Test if bits x[feeoffset ..
 feeoffset+feesize] are all set
 {





idea.

 use alias to declare a temporary of inferred type.





It's

 not a type.  But it seems handy.
     x_foo[] = (x_fee[] << 1) | (x_fee[] >> (feesize-1));   // funky way




to

 pull off a rol
 }

 Does that compile?  ;)

 But I'd rather have:

 bit x[bit[6] reserved; ubit[4] foo; bit[5] fee];
 if (~x.fee[])
 {
     x.foo[] = x.fee[] <>< 1;
 }

 Wouldn't you?  With ints as template parameters that can get powerful.

 template endianness(int size)
 {
     void convert(bit[size] value)
     {
          for (i in 0 .. size by 8)
             value[i .. i + 8] <-> value[size - i - 8 .. size - i]    //
 obviously I mean to end here... why quibble about semicolons?
     }
 }

 int k = 0x04030201;
 with instance(endianness(k.size*8)) convert(k);
 assert(k == 0x01020304);

 That should go in Phobos.

 Wow, this has been fun.

 Sean
May 09 2003
parent reply Mark Evans <Mark_member pathlink.com> writes:
If D is going to be a systems langugae then its bitfield support should at least
equal, but hopefully surpass C.

Sean maybe as a stopgap you could link to one of these libs.  There are many bit
vector libraries out there.  -Mark

http://www.boost.org/libs/dynamic_bitset/dynamic_bitset.html
http://www.embedded.com/1999/9907/9907feat2.htm
http://www.csd.uwo.ca/~jamie/BitVectors/README.html
http://www.csd.uwo.ca/~jamie/BitVectors/SeeAlso.html
May 10 2003
parent "Sean L. Palmer" <palmer.sean verizon.net> writes:
Thanks, but I'm perfectly capable of writing this kind of stuff on my own.
I usually need performance more than general-purposeness so if the compiler
won't auto-generate the optimal code I need to do it myself.  I could get a
ways using templates (I wrote a template-based color-space converter once;
converted between all sorts of color bit formats) but I think that's a
losing battle.

Sean

"Mark Evans" <Mark_member pathlink.com> wrote in message
news:b9kf9u$16gi$1 digitaldaemon.com...

 If D is going to be a systems langugae then its bitfield support should at


least

 equal, but hopefully surpass C.

 Sean maybe as a stopgap you could link to one of these libs.  There are


many bit

 vector libraries out there.  -Mark

 http://www.boost.org/libs/dynamic_bitset/dynamic_bitset.html
 http://www.embedded.com/1999/9907/9907feat2.htm
 http://www.csd.uwo.ca/~jamie/BitVectors/README.html
 http://www.csd.uwo.ca/~jamie/BitVectors/SeeAlso.html
May 11 2003