Page 1 of 1

BITR - nice one !!

PostPosted: Mon Sep 16, 2013 1:48 am
by hewsmike
Just expressing my happiness at finding this instruction at assembly level. :-)

While it seems quite simple and mundane at a glance, for FFT's ( my special interest ) this will readily take on the role of permuting the indices of an input vector. A traditional/significant first part of an FFT for a given transform length is to perform a special shuffling of the elements of an input vector, which can be encoded as a bit-reversal upon a particular length operand.

Thus for say an N-bit index ( where N is at least 1 and not greater than 32 ) on some register RX :

LSR RX, RX, #(32-N);

Graphically :

|---(32-N) zero bits ----|------------------ N original bits --------------|

flipped to

|------------------ N reversed bits -------------|---(32-N) zero bits ----|

slid to

|---(32-N) zero bits ----|------------------ N reversed bits -------------|

..... where LSR is performed because BITR operates on a complete 32-bit operand, and thus you want the upper N bits of the reversed index to slide ( back ) down to the lowest N positions. Now depending upon your data type one could suitably adjust the LSR's immediate for said type's length to obtain an address/offset.

If I've read matters correctly then these two operations run at one cycle each.

Cheers, Mike.

Re: BITR - nice one !!

PostPosted: Mon Sep 16, 2013 7:50 am
by ysapir
Yes, this instruction was probably included thinking about the FFT application, and indeed, in the 2D-FFT demo that we release a while ago, we used it precisely for this purpose and similar to the way you described.

Re: BITR - nice one !!

PostPosted: Wed Sep 18, 2013 3:17 am
by notzed
What a strange coincidence. For some unknown reason whilst in the shower at some point literally in the last couple of days I was thinking "i wonder why they included a bitr instruction specifically, given how small the instruction set is". I was nearly going to post a query about it.

Well now I know I guess.

I was thinking some sort of bitstream/codec processing, or perhaps cryptographic algorithm - but this makes more sense.

Re: BITR - nice one !!

PostPosted: Thu Sep 19, 2013 12:40 am
by hewsmike
Yeah, I had a similiar 'epiphany' about that instruction. :-)

From my assembler experience one would typically/usually rotate/shift one bit out of a register to carry bit, and then rotate/shift ( the other way ) from carry bit into another register. Repeat in a loop by however many places are relevant, or unroll the loop if you know it is short anyway. Thus it is so neat to have this single one-cycle operation.

Cheers, Mike.

( edit ) Note to other readers : bit reversal is not the same as complement.

Re: BITR - nice one !!

PostPosted: Tue Sep 24, 2013 6:10 am
by notzed
I remember why i was thinking about it now - counting bits. Since there's no bit counting instruction or the others like ffs/clz it seemed odd for bitr to make it, but now i think about it it's the easiest to implement in hardware.

That bit-tricks page has examples for all these though.

The carry bit doesn't seem useful for anything other than conditional moves and branches. No addc or rorx/rolx, and the shift instructions don't do anything interesting to it either.