Is there a BSR like opcode for x64

Lord · **Joined:** Tue May 26, 2009 2:11 pm **Posts:** 673

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.

wilbert · **Posted:** Sun Oct 25, 2020 12:47 pm

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)

Lord · **Joined:** Tue May 26, 2009 2:11 pm **Posts:** 673

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?

idle · **Posted:** Sun Oct 25, 2020 10:21 pm

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 

Lord · **Joined:** Tue May 26, 2009 2:11 pm **Posts:** 673

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?

idle · **Posted:** Mon Oct 26, 2020 9:34 pm

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) 

Lord · **Joined:** Tue May 26, 2009 2:11 pm **Posts:** 673

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)

wilbert · **Posted:** Tue Oct 27, 2020 12:30 pm

[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

Lord · **Joined:** Tue May 26, 2009 2:11 pm **Posts:** 673

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'.

wilbert · **Posted:** Tue Oct 27, 2020 1:49 pm

Lord wrote:

Now I have to look what you do with that 'btr'.

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.

Lord · **Joined:** Tue May 26, 2009 2:11 pm **Posts:** 673

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'.

PureBasic Forum

Is there a BSR like opcode for x64

Who is online