It is currently Fri Apr 10, 2020 8:55 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 15 posts ] 
Author Message
 Post subject: Bit reversal
PostPosted: Mon Sep 12, 2011 6:00 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3606
Location: Netherlands
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:
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 ?


Top
 Profile  
Reply with quote  
 Post subject: Re: Bit reversal
PostPosted: Mon Sep 12, 2011 9:38 am 
Offline
Addict
Addict
User avatar

Joined: Sat Aug 15, 2009 6:59 pm
Posts: 1252
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.


Top
 Profile  
Reply with quote  
 Post subject: Re: Bit reversal
PostPosted: Mon Sep 12, 2011 10:32 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3606
Location: Netherlands
Thanks Thorium.
The lookup table approach seems to work very fast
Code:
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))


Top
 Profile  
Reply with quote  
 Post subject: Re: Bit reversal
PostPosted: Mon Sep 12, 2011 8:10 pm 
Offline
User
User

Joined: Fri Jun 03, 2005 8:22 pm
Posts: 70
Location: Glos,Uk
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. :(


Top
 Profile  
Reply with quote  
 Post subject: Re: Bit reversal
PostPosted: Mon Sep 12, 2011 8:25 pm 
Offline
Addict
Addict
User avatar

Joined: Sat Aug 15, 2009 6:59 pm
Posts: 1252
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.


Top
 Profile  
Reply with quote  
 Post subject: Re: Bit reversal
PostPosted: Mon Sep 12, 2011 8:43 pm 
Offline
User
User

Joined: Fri Jun 03, 2005 8:22 pm
Posts: 70
Location: Glos,Uk
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. :(


Top
 Profile  
Reply with quote  
 Post subject: Re: Bit reversal
PostPosted: Sun Sep 18, 2011 1:16 am 
Offline
User
User

Joined: Sun Mar 02, 2008 4:28 pm
Posts: 13
Location: Palatine
What about the BSWAP instruction?


Top
 Profile  
Reply with quote  
 Post subject: Re: Bit reversal
PostPosted: Sun Sep 18, 2011 2:38 am 
Offline
PureBasic Bullfrog
PureBasic Bullfrog
User avatar

Joined: Wed Jul 06, 2005 5:42 am
Posts: 8049
Location: Fort Nelson, BC, Canada
bswap swaps bytes at a time, this operates at the single-bit level.

_________________
Veni, vidi, vici.


Top
 Profile  
Reply with quote  
 Post subject: Re: Bit reversal
PostPosted: Mon Sep 19, 2011 2:09 pm 
Offline
User
User

Joined: Sun Mar 02, 2008 4:28 pm
Posts: 13
Location: Palatine
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.


Top
 Profile  
Reply with quote  
 Post subject: Re: Bit reversal
PostPosted: Mon Sep 19, 2011 2:14 pm 
Offline
Addict
Addict
User avatar

Joined: Sat Aug 15, 2009 6:59 pm
Posts: 1252
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.


Top
 Profile  
Reply with quote  
 Post subject: Re: Bit reversal
PostPosted: Wed Sep 21, 2011 2:48 pm 
Offline
Addict
Addict
User avatar

Joined: Wed Aug 31, 2005 11:09 pm
Posts: 3695
Location: Italy
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"

_________________
[ My little PureBasic review ]


Top
 Profile  
Reply with quote  
 Post subject: Re: Bit reversal
PostPosted: Thu Aug 30, 2012 11:12 pm 
Offline
Enthusiast
Enthusiast

Joined: Fri Jul 25, 2003 11:24 pm
Posts: 532
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).


Top
 Profile  
Reply with quote  
 Post subject: Re: Bit reversal
PostPosted: Tue Sep 04, 2012 6:04 am 
Offline
Addict
Addict
User avatar

Joined: Sat Feb 19, 2005 5:05 pm
Posts: 1769
Location: Norway
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:
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


Top
 Profile  
Reply with quote  
 Post subject: Re: Bit reversal
PostPosted: Tue Sep 04, 2012 7:39 am 
Offline
Enthusiast
Enthusiast

Joined: Fri Jul 25, 2003 11:24 pm
Posts: 532
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).


Top
 Profile  
Reply with quote  
 Post subject: Re: Bit reversal
PostPosted: Wed Sep 05, 2012 1:34 am 
Offline
Addict
Addict
User avatar

Joined: Sat Feb 19, 2005 5:05 pm
Posts: 1769
Location: Norway
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.


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 15 posts ] 

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye