View mode: basic / threaded / horizontal-split · Log in · Help
November 22, 2005
std.intrinsic and bit arrays
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
Re: std.intrinsic and bit arrays
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
Re: std.intrinsic and bit arrays
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
Re: std.intrinsic and bit arrays
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
Re: std.intrinsic and bit arrays
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
Re: std.intrinsic and bit arrays
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
Re: std.intrinsic and bit arrays
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
Re: std.intrinsic and bit arrays
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
Re: std.intrinsic and bit arrays
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
Re: std.intrinsic and bit arrays
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
Top | Discussion index | About this forum | D home