Jump to page: 1 2
Thread overview
std.intrinsic and bit arrays
Nov 22, 2005
Munchgreeble
Nov 22, 2005
Sean Kelly
Nov 23, 2005
Munchgreeble
Dec 04, 2005
Sean Kelly
Nov 22, 2005
Regan Heath
Nov 23, 2005
Munchgreeble
Nov 23, 2005
Regan Heath
Nov 23, 2005
Derek Parnell
Nov 23, 2005
Ben Hinkle
Nov 23, 2005
Tiago Gasiba
Nov 23, 2005
Don Clugston
Nov 23, 2005
Don Clugston
Nov 23, 2005
Munchgreeble
November 22, 2005
Wow. I am practically watering at the mouth. I've just discovered std.intrinsic Only the other day a colleague and I were debating what the best way was to find a bit in a bit array. Both of us lamenting that despite the fact that this problem comes up time and again in embedded code, you almost always end up doing a linear search - terribly inefficient when most processors have a dedicated instruction.

Imagine my delight when just now I discovered D gives you access to the dedicated CPU instruction to do just that. I'm over the moon =)

One thing I wasn't clear on though, how do these functions relate to bit arrays? Bit arrays seem like the obvious thing to use as arguments here - is it possible to use them instead? I was kind of hoping that bit arrays would provide a layer of abstraction on top of this stuff, whilst still allowing bit level operations. E.g. it would be nice to be able to do the below, instead of having to declare "bits" and "moreBits" as ints.

bit[32] bits;
bit[32] moreBits;
:
blah;
:
bits = bits ^ moreBits;

but I can live without bit arrays if needs be - it would just have been a nice to have.

Thanks =)

Munch


November 22, 2005
Munchgreeble@bigfoot.com wrote:
> 
> One thing I wasn't clear on though, how do these functions relate to bit arrays?
> Bit arrays seem like the obvious thing to use as arguments here - is it possible
> to use them instead? I was kind of hoping that bit arrays would provide a layer
> of abstraction on top of this stuff, whilst still allowing bit level operations.
> E.g. it would be nice to be able to do the below, instead of having to declare
> "bits" and "moreBits" as ints.

It's not an answer, but you can accomplish quite a bit via slicing and clever casting if you're willing to live some terrifying code:

void main() {
    uint x = 99;
    bit[] b = cast(bit[])(cast(bit*)&x)[0..(x.sizeof*8)];
    printf( "%u\n", b.length );
    uint y = cast(uint)*&b[0];
    printf( "%u\n", x );
    printf( "%u\n", y );
    for( int i = 7; i >= 0; --i )
        printf( "%.*s", b[i] ? "1" : "0" );
    printf( "\n" );
}


Sean
November 22, 2005
On Tue, 22 Nov 2005 22:34:41 +0000 (UTC), <Munchgreeble@bigfoot.com> wrote:
> Wow. I am practically watering at the mouth. I've just discovered std.intrinsic
> Only the other day a colleague and I were debating what the best way was to find
> a bit in a bit array. Both of us lamenting that despite the fact that this
> problem comes up time and again in embedded code, you almost always end up doing
> a linear search - terribly inefficient when most processors have a dedicated
> instruction.
>
> Imagine my delight when just now I discovered D gives you access to the
> dedicated CPU instruction to do just that. I'm over the moon =)
>
> One thing I wasn't clear on though, how do these functions relate to bit arrays?
> Bit arrays seem like the obvious thing to use as arguments here - is it possible
> to use them instead?

There are numerous posts on how bit arrays in D work, it seems people have a love/hate relationship with them, try a search you'll see what I mean.

> bit[32] bits;
> bit[32] moreBits;
> :
> blah;
> :
> bits = bits ^ moreBits;

I believe that once we get array operations the line above will be possible.

Regan
November 23, 2005
On Tue, 22 Nov 2005 22:34:41 +0000 (UTC), Munchgreeble@bigfoot.com wrote:

> Wow. I am practically watering at the mouth. I've just discovered std.intrinsic

I didn't realize it existed either. It's just what I needed too. I'd written a routine to read UTF text but needed to cater for endian-ness and bswap() is perfect for it. I'd done it the slow way with temporary variables :)

-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
23/11/2005 11:40:52 AM
November 23, 2005
In article <1202ie2xfdynb.1jhc1jr4s9zi2$.dlg@40tude.net>, Derek Parnell says...
>
>On Tue, 22 Nov 2005 22:34:41 +0000 (UTC), Munchgreeble@bigfoot.com wrote:
>
>> Wow. I am practically watering at the mouth. I've just discovered std.intrinsic
>
>I didn't realize it existed either. It's just what I needed too. I'd written a routine to read UTF text but needed to cater for endian-ness and bswap() is perfect for it. I'd done it the slow way with temporary variables :)

FWIW, std.stream.EndianStream could save you some trouble. It uses bswap, too. Check out std.stream.EndianStream.fixBO (where BO stands for byte-order not body-odour) for an endian-fixing routine that works for more than just 32 bits words.



November 23, 2005
Munchgreeble@bigfoot.com schrieb:

> Wow. I am practically watering at the mouth. I've just discovered std.intrinsic Only the other day a colleague and I were debating what the best way was to find a bit in a bit array. Both of us lamenting that despite the fact that this problem comes up time and again in embedded code, you almost always end up doing a linear search - terribly inefficient when most processors have a dedicated instruction.
> 
> Imagine my delight when just now I discovered D gives you access to the dedicated CPU instruction to do just that. I'm over the moon =)
> 

Wow!!! Me too! I'm speechless... Amazing! Thanks for posting this message - you've opened my eyes! :)
Now (forgive my ignorance) I feel that I must ask the following:
If there are functions to find/set/reset bits, is there any function to count bits?

For example, how can I do this efficiently:

  ulong  x = 0x1234;  // whatever...
  bitcount(x) -> 5;   // there are 5 ones in x

Thanks,
Tiago

-- 
Tiago Gasiba (M.Sc.) - http://www.gasiba.de
Everything should be made as simple as possible, but not simpler.
November 23, 2005
Tiago Gasiba wrote:
> Munchgreeble@bigfoot.com schrieb:
> 
> 
>>Wow. I am practically watering at the mouth. I've just discovered
>>std.intrinsic Only the other day a colleague and I were debating what the
>>best way was to find a bit in a bit array. Both of us lamenting that
>>despite the fact that this problem comes up time and again in embedded
>>code, you almost always end up doing a linear search - terribly
>>inefficient when most processors have a dedicated instruction.
>>
>>Imagine my delight when just now I discovered D gives you access to the
>>dedicated CPU instruction to do just that. I'm over the moon =)
>>
> 
> 
> Wow!!! Me too! I'm speechless... Amazing! Thanks for posting this message - you've opened my eyes! :)
> Now (forgive my ignorance) I feel that I must ask the following:
> If there are functions to find/set/reset bits, is there any function to count bits?
> 
> For example, how can I do this efficiently:
> 
>   ulong  x = 0x1234;  // whatever...
>   bitcount(x) -> 5;   // there are 5 ones in x

That should be a standard function too. There's no instrinsic for it, though, because x86 has no instruction for that (some other CPUs do, though, it's typically called "population count" or POPC -- stupid name, bitcount is much better).

You add neighbouring bits, then add neighbouring pairs, nibbles, bytes, and words:

// Calculates the number of set bits in a 32-bit integer.
int bitcount(uint x)
{
// add neighbouring bits. Each bit is 0 or 1.
x = ((x&0xAAAAAAAA)>>1) +(x&0x55555555);
// now each two bits of x is a number 00,01 or 10.
// now add neighbouring pairs
x = ((x&0xCCCCCCCC)>>2) + (x&0x33333333);
// now each nibble holds 0000-0100. Adding them wont
// overflow any more, so we don't need to mask any more
// Now add the nibbles
x += (x>>4);
// each byte is a number from 00000000 to 00001000.
// now add the bytes
x += (x>>8);
// now add the words
x += (x>>16);
return x;
}

Nifty, eh? On paper, it doesn't look as fast as a table lookup, but it adds 4 bytes at once, and it has no cache problems, so in real problems it should be faster. (Note that if you do a simple speed test, a table lookup will look deceptively good because the table will stay in the cache. You need to profile a realistic program).

I did not make it up, I read it on a newsgroup long ago. But I recreated it from memory, so it's completely public domain.

I have a few of these bit functions (all in C++), I should convert them to D and submit them to Phobos. Especially since they even have unit tests -- a rarity for my C++ code :-)
November 23, 2005
Wow, now that's what I call casting =) It would have taken me quite a long time to almost get to that stage, give up and post to the newsgroup, so thanks - much appreciated.

It's not pretty I'll grant you, but you can usually encapsulate that stuff and cover it with comments, so I'm happy - thanks.

One thing I'm not clear on - does the slicing cost anything at run time? I'm guessing not since all the limits are calculable at compile time?

Regards

Munch

Sean Kelly wrote:

> Munchgreeble@bigfoot.com wrote:
> 
>>
>> One thing I wasn't clear on though, how do these functions relate to bit arrays?
>> Bit arrays seem like the obvious thing to use as arguments here - is it possible
>> to use them instead? I was kind of hoping that bit arrays would provide a layer
>> of abstraction on top of this stuff, whilst still allowing bit level operations.
> 
> It's not an answer, but you can accomplish quite a bit via slicing and clever casting if you're willing to live some terrifying code:
> 
> void main() {
>     uint x = 99;
>     bit[] b = cast(bit[])(cast(bit*)&x)[0..(x.sizeof*8)];
>     printf( "%u\n", b.length );
>     uint y = cast(uint)*&b[0];
>     printf( "%u\n", x );
>     printf( "%u\n", y );
>     for( int i = 7; i >= 0; --i )
>         printf( "%.*s", b[i] ? "1" : "0" );
>     printf( "\n" );
> }
> 
> 
> Sean
November 23, 2005
Don Clugston wrote:
> 
> I have a few of these bit functions (all in C++), I should convert them to D and submit them to Phobos. Especially since they even have unit tests -- a rarity for my C++ code :-)

I just put them into MathExtra on dsource.org. Not that they belong there, but anyway...
November 23, 2005
Great! And thanks for posting the algorithm - I must confess I've always used a 16-bit wide table lookup for bit counting.

Cheers

Munch

Don Clugston wrote:

> Don Clugston wrote:
> 
>>
>> I have a few of these bit functions (all in C++), I should convert them to D and submit them to Phobos. Especially since they even have unit tests -- a rarity for my C++ code :-)
> 
> 
> I just put them into MathExtra on dsource.org. Not that they belong there, but anyway...
« First   ‹ Prev
1 2