Is there a BSR like opcode for x64

Bare metal programming in PureBasic, for experienced users
Lord
Enthusiast
Enthusiast
Posts: 731
Joined: Tue May 26, 2009 2:11 pm

Is there a BSR like opcode for x64

Post 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.
Image
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3734
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: Is there a BSR like opcode for x64

Post 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)
macOS 10.15 Catalina, Windows 10
Lord
Enthusiast
Enthusiast
Posts: 731
Joined: Tue May 26, 2009 2:11 pm

Re: Is there a BSR like opcode for x64

Post 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?
Image
User avatar
idle
Addict
Addict
Posts: 3632
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Is there a BSR like opcode for x64

Post 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 

Lord
Enthusiast
Enthusiast
Posts: 731
Joined: Tue May 26, 2009 2:11 pm

Re: Is there a BSR like opcode for x64

Post 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?
Image
User avatar
idle
Addict
Addict
Posts: 3632
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Is there a BSR like opcode for x64

Post 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) 
Lord
Enthusiast
Enthusiast
Posts: 731
Joined: Tue May 26, 2009 2:11 pm

Re: Is there a BSR like opcode for x64

Post 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)
Image
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3734
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: Is there a BSR like opcode for x64

Post 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
macOS 10.15 Catalina, Windows 10
Lord
Enthusiast
Enthusiast
Posts: 731
Joined: Tue May 26, 2009 2:11 pm

Re: Is there a BSR like opcode for x64

Post 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
Image
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3734
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: Is there a BSR like opcode for x64

Post 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.
macOS 10.15 Catalina, Windows 10
Lord
Enthusiast
Enthusiast
Posts: 731
Joined: Tue May 26, 2009 2:11 pm

Re: Is there a BSR like opcode for x64

Post 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'. :)
Image
Post Reply