D - slicing bit arrays

Sean L. Palmer (63/63) Apr 16 2003 Is there a function in D that converts a slice of a bit array into an in...

Walter (9/72) May 09 2003 At the moment, you can't slice bit fields unless they align on a byte

Sean L. Palmer (28/114) May 09 2003 Argh... do you have any plans to expand bit array slicing capability?

Mark Evans (8/8) May 10 2003 If D is going to be a systems langugae then its bitfield support should ...

Sean L. Palmer (11/19) May 11 2003 Thanks, but I'm perfectly capable of writing this kind of stuff on my ow...

"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

"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

"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

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

"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

D Programming

C/C++ Programming

Other

D - slicing bit arrays