Bit reversal

Bare metal programming in PureBasic, for experienced users
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Bit reversal

Post by wilbert »

I was wondering what the fastest way is to reverse all 32 bits of a long.
A simple loop works but might not be very efficient

Code: Select all

Procedure.l ReverseBits(v.l)
  EnableASM
  MOV edx, v
  !xor eax, eax
  !mov ecx, 32
  !reverse_bits_loop:
  !shr edx, 1
  !rcl eax, 1
  !loop reverse_bits_loop
  DisableASM
  ProcedureReturn
EndProcedure
Any ideas for a faster way ?
Thorium
Addict
Addict
Posts: 1271
Joined: Sat Aug 15, 2009 6:59 pm

Re: Bit reversal

Post by Thorium »

There is no efficient way to reverse bit's on x86 CPU's. However there are some tricks: http://graphics.stanford.edu/~seander/b ... rseObvious

Scroll down to find some more methodes.
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: Bit reversal

Post by wilbert »

Thanks Thorium.
The lookup table approach seems to work very fast

Code: Select all

Global *BitReverseTable = AllocateMemory(511)
Global BitReverseTableAligned = (*BitReverseTable + 255) & $ffffff00

Procedure InitBitReverseTable()
  !mov eax, [v_BitReverseTableAligned]
  !mov al, 0
  !init_brt_loop0:
  !mov dl, al
  !mov cl, 8
  !init_brt_loop1:
  !shr dl, 1
  !rcl dh, 1
  !dec cl
  !jnz init_brt_loop1
  !mov [eax], dh
  !inc al
  !jnz init_brt_loop0
EndProcedure

InitBitReverseTable()

Procedure.l ReverseBits(v.l)
  EnableASM
  MOV eax, v
  !mov edx, [v_BitReverseTableAligned]
  !mov dl, al
  !mov al, [edx]
  !mov dl, ah
  !mov ah, [edx]
  !bswap eax
  !mov dl, al
  !mov al, [edx]
  !mov dl, ah
  !mov ah, [edx]
  DisableASM
  ProcedureReturn
EndProcedure

start = ElapsedMilliseconds()
For i = 0 To 10000000
  j = ReverseBits(i)
Next
stop = ElapsedMilliseconds()
time = stop-start 

MessageRequester("Time", Str(time))
ferty
User
User
Posts: 70
Joined: Fri Jun 03, 2005 8:22 pm
Location: Glos,Uk

Re: Bit reversal

Post by ferty »

Hi,I may be wrong(probably am)back in the day on the c64 I used to use eor #$ff to toggle all the bits on the 6502 cpu,I believe that XOR EAX,ffffffff is the equivalent simple toggling all the bits each time it is applied.
They Say You Never Stop Learning,Well I Can`t Seem To Start. :(
Thorium
Addict
Addict
Posts: 1271
Joined: Sat Aug 15, 2009 6:59 pm

Re: Bit reversal

Post by Thorium »

ferty wrote:Hi,I may be wrong(probably am)back in the day on the c64 I used to use eor #$ff to toggle all the bits on the 6502 cpu,I believe that XOR EAX,ffffffff is the equivalent simple toggling all the bits each time it is applied.
He dont want to toggle them. For that you can just use NEG.
He want's to reverse the order of the bits: bit 31 becomes bit 0, bit 30 becomes bit 1, bit 29 becomes bit 2, etc.
Unfortunatly there is no instruction for that on x86.
ferty
User
User
Posts: 70
Joined: Fri Jun 03, 2005 8:22 pm
Location: Glos,Uk

Re: Bit reversal

Post by ferty »

Ahh yes,I completely miss-read that,far to tired to be looking at all thing`s computer related tonight.
They Say You Never Stop Learning,Well I Can`t Seem To Start. :(
Harry0
User
User
Posts: 13
Joined: Sun Mar 02, 2008 4:28 pm
Location: Palatine

Re: Bit reversal

Post by Harry0 »

What about the BSWAP instruction?
User avatar
netmaestro
PureBasic Bullfrog
PureBasic Bullfrog
Posts: 8425
Joined: Wed Jul 06, 2005 5:42 am
Location: Fort Nelson, BC, Canada

Re: Bit reversal

Post by netmaestro »

bswap swaps bytes at a time, this operates at the single-bit level.
BERESHEIT
Harry0
User
User
Posts: 13
Joined: Sun Mar 02, 2008 4:28 pm
Location: Palatine

Re: Bit reversal

Post by Harry0 »

From the Flat Assembler doc's:

bswap reverses the byte order of a 32-bit general register: bits 0 through 7 are swapped with bits 24 through 31, and bits 8 through 15 are swapped with bits 16 through 23. This instruction is provided for converting little-endian values to big-endian format and vice versa.

bswap edx ; swap bytes in register

So it not only swaps bytes but also the bits in those bytes.
Thorium
Addict
Addict
Posts: 1271
Joined: Sat Aug 15, 2009 6:59 pm

Re: Bit reversal

Post by Thorium »

Harry0 wrote:From the Flat Assembler doc's:

bswap reverses the byte order of a 32-bit general register: bits 0 through 7 are swapped with bits 24 through 31, and bits 8 through 15 are swapped with bits 16 through 23. This instruction is provided for converting little-endian values to big-endian format and vice versa.

bswap edx ; swap bytes in register

So it not only swaps bytes but also the bits in those bytes.
No it doesnt, you missread it.

bswap is for converting endianess, which wouldnt work if the bits would be reversed.
User avatar
luis
Addict
Addict
Posts: 3876
Joined: Wed Aug 31, 2005 11:09 pm
Location: Italy

Re: Bit reversal

Post by luis »

Harry0 wrote: So it not only swaps bytes but also the bits in those bytes.
What you just quoted says another thing.
Swap a "group" of bits as a whole with another group of bits.

"bits 0 through 7 are swapped with bits 24 through 31, and bits 8 through 15 are swapped with bits 16 through 23"
"Have you tried turning it off and on again ?"
A little PureBasic review
oldefoxx
Enthusiast
Enthusiast
Posts: 532
Joined: Fri Jul 25, 2003 11:24 pm

Re: Bit reversal

Post by oldefoxx »

First, swap the byte order. Note that this does not reverse the bit order, but you are halfway there. Next have a 256 byte table set up that does reverse the bit order, byte by byte. 00h becomes 00h, 01h becomes 80h, 02h becomes 40h, and so on. Thus you have one instruction for reversing the bytes, and one table lookup for replacing each byte in turn, and a 256-byte table is not terribly long to work with. You could make it slightly smaller by recognizing that 00h remains 00h and ffh remains ffh. So do some of the other combos like 81h and 42h, but singling all them out takes more instructions and more time, and does not significantly help with regard to keeping the table easy to work through.
has-been wanna-be (You may not agree with what I say, but it will make you think).
User avatar
Rescator
Addict
Addict
Posts: 1769
Joined: Sat Feb 19, 2005 5:05 pm
Location: Norway

Re: Bit reversal

Post by Rescator »

I could have sworn I posted this once, but I guess I didn't! Odd!

Anyway! This code is pretty much the fastest, and although there may be a few faster asm variants out there (they are mostly identical) they give diminishing returns, and they may need certain CPU features. This is definitely one for your "toolbox".

This is 1035% (10.35x) faster vs the loop above.
And this is 211% (2.11x) faster vs the lookup table above.

Test was done using a normal executable (no debugging, aka Shift+F5 was used in the PB IDE).
Each procedure was looped 100 000 000 times to test cacheability/assemblyline performance.

438ms total (for the procedure in this post).
4533ms total (for the loop code in the original post of this thread)
925ms total (for the lookup code in the post further up)

PS! For more performance simply inline the contents of the procedure into you main code loop (that handles the data you are processing). Replace "ProcedureReturn" with "!MOV [p.v_value],eax" in that case.

Code: Select all

Procedure.l ReverseBits(value.l)
 !MOV eax,[p.v_value]
 !MOV edx,eax         ;Make a copy of the the data.
 !SHR eax,1           ;Move the even bits to odd positions.
 !AND edx,0x55555555  ;Isolate the odd bits by clearing even bits.
 !AND eax,0x55555555  ;Isolate the even bits (in odd positions now).
 !SHL edx,1           ;Move the odd bits to the even positions.
 !OR eax,edx          ;Merge the bits and complete the swap.
 !MOV edx,eax         ;Make a copy of the odd numbered bit pairs.
 !SHR eax,2           ;Move the even bit pairs to the odd positions.
 !AND edx,0x33333333  ;Isolate the odd pairs by clearing even pairs.
 !AND eax,0x33333333  ;Isolate the even pairs (in odd positions now).
 !SHL edx,2           ;Move the odd pairs to the even positions.
 !OR eax,edx          ;Merge the bits and complete the swap.
 !MOV edx,eax         ;Make a copy of the odd numbered nibbles.
 !SHR eax,4           ;Move the even nibbles to the odd position.
 !AND edx,0x0f0f0f0f  ;Isolate the odd nibbles.
 !AND eax,0x0f0f0f0f  ;Isolate the even nibbles (in odd position now).
 !SHL edx,4           ;Move the odd pairs to the even positions.
 !OR eax,edx          ;Merge the bits and complete the Swap.
 !BSWAP eax           ;Swap the bytes and words.
 ProcedureReturn
EndProcedure
oldefoxx
Enthusiast
Enthusiast
Posts: 532
Joined: Fri Jul 25, 2003 11:24 pm

Re: Bit reversal

Post by oldefoxx »

Too deep for me. I've looked at it, and I can't get a picture of what is going on. Oh wait a minute! What you are doing is swapping even and odd bits, putting them in the opposite order. Then you are swapping adjacent pairs, getting them in order. Then you are swapping
adjacent nybbles. getting them in order. Each swap takes the bits that are most outbound and moves them across to the opposite end.
Now that is rather impressive. Did you think of it, or is it something that you ran into before?
has-been wanna-be (You may not agree with what I say, but it will make you think).
User avatar
Rescator
Addict
Addict
Posts: 1769
Joined: Sat Feb 19, 2005 5:05 pm
Location: Norway

Re: Bit reversal

Post by Rescator »

Well! I actually did think about it and kinda messed around and got something working. (messy code, not that fast, and I'm not really a asm guy, but yeah BSWAP and shifting of bits and flipping nibbles was the key)

So I searched around on the net (easier to find things if you know what you are searching for, odd that) and sure enough my idea was not original, and this implementation exists in a classic book called Art of Assembly which the above is from. http://www.plantation-productions.com/Webster/ poke around there and you'll find a download. Awesome stuff.
Post Reply