Page 1 of 1

Is there a BSR like opcode for x64

Posted: Sun Oct 25, 2020 12:09 pm
by Lord
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: Select all

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: Select all

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.

Re: Is there a BSR like opcode for x64

Posted: Sun Oct 25, 2020 12:47 pm
by wilbert
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: Select all

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)

Re: Is there a BSR like opcode for x64

Posted: Sun Oct 25, 2020 3:57 pm
by Lord
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?

Re: Is there a BSR like opcode for x64

Posted: Sun Oct 25, 2020 10:21 pm
by idle
use enableasm perhaps

Code: Select all

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 


Re: Is there a BSR like opcode for x64

Posted: Mon Oct 26, 2020 8:30 am
by Lord
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: Select all

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?

Re: Is there a BSR like opcode for x64

Posted: Mon Oct 26, 2020 9:34 pm
by idle
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: Select all

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) 

Re: Is there a BSR like opcode for x64

Posted: Tue Oct 27, 2020 11:21 am
by Lord
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: Select all

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)

Re: Is there a BSR like opcode for x64

Posted: Tue Oct 27, 2020 12:30 pm
by wilbert
[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: Select all

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

Re: Is there a BSR like opcode for x64

Posted: Tue Oct 27, 2020 1:28 pm
by Lord
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

Re: Is there a BSR like opcode for x64

Posted: Tue Oct 27, 2020 1:49 pm
by wilbert
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.

Re: Is there a BSR like opcode for x64

Posted: Tue Oct 27, 2020 2:03 pm
by Lord
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'. :)