PureBasic Forums - English

http://www.purebasic.com
https://www.purebasic.fr/english/

Bit reversal

https://www.purebasic.fr/english/viewtopic.php?t=47524

Page 1 of 1

Bit reversal

Posted: Mon Sep 12, 2011 6:00 am
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 ?

Re: Bit reversal

Posted: Mon Sep 12, 2011 9:38 am
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.

Re: Bit reversal

Posted: Mon Sep 12, 2011 10:32 am
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))

Re: Bit reversal

Posted: Mon Sep 12, 2011 8:10 pm
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.

Re: Bit reversal

Posted: Mon Sep 12, 2011 8:25 pm
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.

Re: Bit reversal

Posted: Mon Sep 12, 2011 8:43 pm
by ferty
Ahh yes,I completely miss-read that,far to tired to be looking at all thing`s computer related tonight.

Re: Bit reversal

Posted: Sun Sep 18, 2011 1:16 am
by Harry0
What about the BSWAP instruction?

Re: Bit reversal

Posted: Sun Sep 18, 2011 2:38 am
by netmaestro
bswap swaps bytes at a time, this operates at the single-bit level.

Re: Bit reversal

Posted: Mon Sep 19, 2011 2:09 pm
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.

Re: Bit reversal

Posted: Mon Sep 19, 2011 2:14 pm
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.

Re: Bit reversal

Posted: Wed Sep 21, 2011 2:48 pm
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"

Re: Bit reversal

Posted: Thu Aug 30, 2012 11:12 pm
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.

Re: Bit reversal

Posted: Tue Sep 04, 2012 6:04 am
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

Re: Bit reversal

Posted: Tue Sep 04, 2012 7:39 am
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?

Re: Bit reversal

Posted: Wed Sep 05, 2012 1:34 am
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.
All times are UTC+01:00
Page 1 of 1

Powered by phpBB® Forum Software © phpBB Limited