PureBasic Forum
http://forums.purebasic.com/english/

Is there a BSR like opcode for x64
http://forums.purebasic.com/english/viewtopic.php?f=35&t=76153		 Page 1 of 1
Author:  Lord [ Sun Oct 25, 2020 12:09 pm ]
Post subject:  Is there a BSR like opcode for x64
Hi!

For a long time I used the bsr opcode to get the highest set bit.
But this opcode is only suitable for integers up to 32 bit length.

Now I need an equivalent command for integers up to 64 bit.
Is there such a command for x64-CPU? If so, how to use it?

So far I use the 32-bit variant like this:
Code:
Procedure GetHighestBit(value.l)
  ! MOV eax, [p.v_value]
  ! bsr eax, eax
  ProcedureReturn
EndProcedure
Note: the used CPU handles only
ARCH64, CLFSH, (F)CMOV, CX8, CX16, FXSR, MMX, MONITOR,
MSR, PAE, POPCNT, RDTSC, RDTSCP, SEP, SMX, SSE, SSE2,
SSE3, SSSE3, SSE4.1, SSE4.2, VMX
So no AVX and higher command sets are supported.

Second question:
How do I pass a variable in a structure and get the result back
in this structure? The structure could look like this:
Code:
Structure K
  A.i
  B.i
  A.I.
  D.i
EndStructure
The procedure should get the variable by K\A and return the result in K\B.
Currently the result is returned directly from the eax via ProcedureReturn.
Author:  wilbert [ Sun Oct 25, 2020 12:47 pm ]
Post subject:  Re: Is there a BSR like opcode for x64
Lord wrote:
For a long time I used the bsr opcode to get the highest set bit.
But this opcode is only suitable for integers up to 32 bit length.

Now I need an equivalent command for integers up to 64 bit.
Is there such a command for x64-CPU? If so, how to use it?

The command is the same
Code:
Procedure GetHighestBit(value.q)
  ! MOV rax, [p.v_value]
  ! bsr rax, rax
  ProcedureReturn
EndProcedure

(for both 32 and 64 bit the result is undefined if value is 0)
Author:  Lord [ Sun Oct 25, 2020 3:57 pm ]
Post subject:  Re: Is there a BSR like opcode for x64
Hi wilbert!

Thank you for your answer.
wilbert wrote:
...
The command is the same
...
OK, I see. That works fine.
wilbert wrote:
...
(for both 32 and 64 bit the result is undefined if value is 0)
Yes, I know. It's no problem with that.

Any chance to give the result back in a variable with a structure?
I would like to avoid a procedure and have the code inline.
How do I move StructuredVariable\A to rax and after bsr rax to
StructuredVariable\B?
Author:  idle [ Sun Oct 25, 2020 10:21 pm ]
Post subject:  Re: Is there a BSR like opcode for x64
use enableasm perhaps

Code:
Structure struct
  val.i
  bsr.i
EndStructure   

Macro _BSR(struct)
  EnableASM
  mov rax, struct\val
  bsr rax, rax
  mov struct\bsr, rax
  DisableASM
EndMacro

Global var.struct
var\val = 1024

_BSR(var)

Debug var\bsr

Author:  Lord [ Mon Oct 26, 2020 8:30 am ]
Post subject:  Re: Is there a BSR like opcode for x64
Hello idle!

Thank you for publishing your approach to this topic.
In the meantime I tried it again myself and came up with this piece of code:
Code:
Structure K
A.i
B.i
C.i
EndStructure

Define K.K
K\A=1024

! LEA rbp,[v_K]
! MOV rax, qword[rbp]
! BSR rax, rax
! MOV qword[rbp+8], rax

Debug K\B
Do I still have any precautions to take regarding stack or other things with my code?
Author:  idle [ Mon Oct 26, 2020 9:34 pm ]
Post subject:  Re: Is there a BSR like opcode for x64
if you want a general macro it's probably better to stick with the enableasm as it will load the variable in the scope
Code:
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
Macro eax : rax : EndMacro
CompilerEndIf

Macro _BSR(K)
  EnableASM
  mov eax, K\A
  bsr eax, eax
  mov K\B, eax
  DisableASM
EndMacro

Structure K
A.i
B.i
C.i
EndStructure

Define K.K
K\A=1024

_BSR(K)

Debug K\B

Procedure foo(Val)
  Protected T.k
  T\A = Val
  _BSR(T)
  Debug T\B
EndProcedure

foo(1<<48)
Author:  Lord [ Tue Oct 27, 2020 11:21 am ]
Post subject:  Re: Is there a BSR like opcode for x64
idle wrote:
if you want a general macro ...
Not really.
To make it long:
I looked for a fast way to "decode" a Kekule number.
I wanted to get for a given person with a Kekule number the generation
and the position of this person in this generation.

Right now I have this (with your help):
Code:
EnableExplicit

Structure K
  K.q ; Kekule, first=1
  G.q ; Generation, first=1
  P.q ; Position; first =0
EndStructure

Define K.K

Procedure DecodeKekule(*K.K)
  If *K\K>1
    ! MOV rax, qword[v_K]
    ! bsr rax, rax
    ! MOV qword[v_K+8], rax
   
    ! MOV r8, 1
    ! MOV rcx, qword[v_K+8]
    ! SHL r8, cl
    ! NOT r8
    ! MOV rax, qword[v_K]
    ! AND rax, r8
    ! MOV qword[v_K+16], rax
   
    ! ADD qword[v_K+8], 1
    ProcedureReturn #True
  ElseIf *K\K=1
    ! MOV qword[v_K+8], 1
    ProcedureReturn #True
  Else
    ! MOV qword[v_K+8], 0
    ProcedureReturn #False
  EndIf
EndProcedure

; Test
K\K=15
DecodeKekule(@K)
MessageRequester("KekuleDecode: "+K\K, "Generation: "+Str(K\G)+", Postion: "+K\P)
Author:  wilbert [ Tue Oct 27, 2020 12:30 pm ]
Post subject:  Re: Is there a BSR like opcode for x64
[v_K] refers to a global variable, not to *K.
To refer to *K and shorten your procedure a bit, you can do it like this
Code:
Procedure DecodeKekule(*K.K)
  If *K\K>1
    !mov rdx, [p.p_K]       ; rdx -> *K
    !mov rax, [rdx]
    !bsr rcx, rax
    !btr rax, rcx
    !add rcx, 1
    !mov [rdx + 8], rcx
    !mov [rdx + 16], rax
    ProcedureReturn #True
  ElseIf *K\K=1
    *K\G = 1
    ProcedureReturn #True
  Else
    *K\G = 0
    ProcedureReturn #False
  EndIf
EndProcedure
Author:  Lord [ Tue Oct 27, 2020 1:28 pm ]
Post subject:  Re: Is there a BSR like opcode for x64
Hi wilbert!

Thank you for your help.
wilbert wrote:
[v_K] refers to a global variable, not to *K.
...
Didn't notice this. I transferred the code from plain inline to a Procedure.

wilbert wrote:
...
To refer to *K and shorten your procedure a bit, you can do it like this
...
It's not only shorter, but also faster.
32 Generations(4294967296 People): 28061 ms to 21349 ms.

Now I have to look what you do with that 'btr'. :D
Author:  wilbert [ Tue Oct 27, 2020 1:49 pm ]
Post subject:  Re: Is there a BSR like opcode for x64
Lord wrote:
Now I have to look what you do with that 'btr'. :D

btr = bit test and reset
It tests the specified bit number and resets the bit.
The test result is returned in the carry flag but in this case it can be ignored since you don't need that.
You only need to reset the specified bit number.
Author:  Lord [ Tue Oct 27, 2020 2:03 pm ]
Post subject:  Re: Is there a BSR like opcode for x64
Hi wilbert!

wilbert wrote:
...
btr = bit test and reset
It tests the specified bit number and resets the bit.
The test result is returned in the carry flag but in this case it can be ignored since you don't need that.
You only need to reset the specified bit number.
Thank you for explaining that to me.
Nice 'shortcut'. :)
Page 1 of 1 All times are UTC + 1 hour
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/