64 bit, registers and commands.

[Chris Burton]

Hello, I'm somewhat new to assembly language (took a class in college for programming a mac classic). I am interested in performing bitwise manipulation on QUAD Integer sized data in assembly language.

I'm running windows 7, 64 bit, and powerbasic 5.02. One of the functions I'd like to get working is BSF. It scans the register for the first nonzero bit and returns it. Currently I must load the 2 halves of the 64 bit integer and analyze them seperately and then decide which number I should return. It ends up being more complex than a simple BSF EAX, [EBX] instruction. I am completely unfamiliar with the MMX instructions and registers, but if those will do what I need, I'm all ears.

Thanks for the help,
Chris

[John Gleason]

I didn't see any MMX instruction for this app. Maybe something like this:

#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN () AS LONG
    LOCAL q AS QUAD, firstBit, ii AS LONG
    LOCAL outStr AS STRING
    outStr = STRING$(&h00000712, "#")
   DO
     q += &h100000000  'test the 1st few hi bits of the quad
    !add ii, 1         ;counter
    !mov eax, q        ;lo 4 bytes of quad
    !bsf ecx, eax      ;bit scan forward
    !jnz short foundLo
    !mov eax, q[4]     ;hi 4 bytes of quad
    !bsf ecx, eax      ;scan
    !jz short notFound ;no bits set
    !add ecx, 32       ;wasn't in lo 32 bits so add len of LONG--32 bits
  foundLo:
    !add ecx, 1        ;number bits 1 to 32 to distinguish from finding 1st bit set which is "0" (zero) bit
    !mov firstBit, ecx ;save in firstbit
  notFound:
     MID$(outStr, ii) = MKBYT$(firstBit)
     !mov firstBit, 0  ;reset
   LOOP UNTIL q > &h071100000000

  REPLACE ANY CHR$(0 TO 63) WITH CHR$(16 TO 79) IN outStr
  ? outStr
END FUNCTION

[Michael Mattias]

I am interested in performing bitwise manipulation on QUAD Integer sized data in assembly language.

If you are not married to assembly language, all the PB-Intrinsic bit-manipulation statements, functions and operators work just fine on QUAD integers. (Several work on even larger size chunks of data).

And you can treat any chunk of data as an array (or Array) of quad integers...

  LOCAL pQ  AS QUAD 
  LOCAL aQ() AS QUAD 

  MyDataIn$ =   someLongStringOfcharacters
  IF LEN(MyDataIn$) MOD 8  THEN 
          MyDataIn$ =   MyDataIn$ & STRING$ ( LEN(MyDataIn$) MOD 8), 0) 
  END IF 
  pQ  = STRPTR (myDataIn$)
  FOR Z = 1 TO LEN(MyDataIn$ MOD 8) 
     @pq  =  the next 64 bits
     Manipulate @pQ here 
     INCR  pQ   ' advance to next 64 bits
  NEXT 
  ***** OR  ********
  REDIM  aQ( (LEN(MyDataIn$) MOD 8) -1)  AT STRPTR (MyDataIn$) 
  FOR Z = LBOUND(aQ,1) TO UBOUND (aQ,1) 
       aQ(Z) =  64 bits as a QUAD 
  ....

MCM

[Jeff Blakeney]

BitNum = 64 - INSTR(BIN$(HI(DWORD, qTemp), 32) + BIN$(LO(DWORD, qTemp), 32), "1")

Not necessarily the fastest but definitely easy.

[Paul Dixon]

PBCC5 program
FUNCTION PBMAIN () AS LONG

a&&=&h8f00000000000200

!mov eax,-1                 'assume failure
!test dword ptr a&&,-1      'any bits set in low dword?
!jz short skip              'no, do high dword
!bsf eax,a&&[0]             'get result from low dword
!jmp short xit              'done
skip:
!test dword ptr a&&[4],-1   'any bits set in high dword?
!jz short xit               'no, quit with fail
!bsf eax,a&&[4]             'get result from high dword
!add eax,32                 'add 32 to account for low dword
xit:
'eax contains bit number or -1 if no bits set
!mov b&,eax
PRINT b&

WAITKEY$

END FUNCTION

[Chris Burton]

FUNCTION FirstBit(BYVAL BitBrd AS QUAD) AS LONG
   DIM BoardPointer AS LONG PTR
   'this routine scans a 64 bit word looking for the LSB
   'EAX, EBX are modified
   'zero flag is modified
   BoardPointer = VARPTR(BitBrd)
   ! push EBX
   ! push EAX
   ! MOV EBX, BoardPointer
'try first 32 bit half
   ! BSF EAX, [EBX]
   ! JNZ done
'try second 32 bit half
   ! BSF EAX, [EBX + 4]
   ! JZ  done
   ! ADD EAX, 32
done:
   ! MOV FUNCTION, EAX
   ! pop EAX
   ! pop EBX
END FUNCTION

Is the function I am currently using. It just seems excessive when there is an assmebly instruction built for it. If 64 bit registers were excessible, this function becomes BSF RAX, [RBX]; MOV FUNCTION, RAX. I think RAX is the name of the 64 bit register...

The focus on speed is due to the number of times this function gets called, which is hundreds of times for each trip through the main loop. Hrm...vexing the registers are right there just a bit out of reach. I guess I'll just have to wait until the next pbcc version.

Thanks for the help,
Chris

[John Gleason]

Chris, until the day 64-bit arrives, you may want consider a MACRO or MACRO FUNCTION for a nice speed improvement as shown in the demo below.

#COMPILE EXE
#DIM ALL

FUNCTION FirstBit(BYVAL BitBrd AS QUAD) AS LONG
   DIM BoardPointer AS LONG PTR
   'this routine scans a 64 bit word looking for the LSB
   'EAX, EBX are modified
   'zero flag is modified
   BoardPointer = VARPTR(BitBrd)
   ! push EBX
   ! push EAX
   ! MOV EBX, BoardPointer
'try first 32 bit half
   ! BSF EAX, [EBX]
   ! JNZ done
'try second 32 bit half
   ! BSF EAX, [EBX + 4]
   ! JZ  done
   ! ADD EAX, 32
done:
   ! MOV FUNCTION, EAX
   ! pop EAX
   ! pop EBX
END FUNCTION

MACRO FUNCTION mfFirstBit(bitBrd)
   MACROTEMP outL, done
   LOCAL outL AS LONG

   'this routine scans a 64 bit word looking for the LSB
   'EAX, ECX are modified
   'zero flag is modified
   outL = VARPTR(BitBrd)
   ! mov ECX, outL
'try first 32 bit half
   ! BSF EAX, [ECX]
   ! JNZ short done
'try second 32 bit half
   ! BSF EAX, [ECX + 4]
   ! JZ short done
   ! ADD EAX, 32
done:
   ! mov outL, eax

END MACRO = outL

MACRO mFirstBit(bitBrd, outL)
   MACROTEMP done

   'this routine scans a 64 bit word looking for the LSB
   'EAX, ECX are modified
   'zero flag is modified
   outL = VARPTR(BitBrd)
   ! mov ECX, outL
'try first 32 bit half
   ! BSF EAX, [ECX]
   ! JNZ short done
'try second 32 bit half
   ! BSF EAX, [ECX + 4]
   ! JZ short done
   ! ADD EAX, 32
done:
   ! mov outL, eax

END MACRO

FUNCTION PBMAIN () AS LONG
   LOCAL t, t2, t3 AS QUAD, ii, x AS LONG
   DIM qArr(1000000) AS QUAD
   'test 2 functions to improve speed
   '1st make some quad numbers to test

   FOR ii = 1 TO 1000000
      qArr(ii) = RND * 1000000000000000000
   NEXT

   'dry run
   FOR ii = 1 TO 1000000
      x = FirstBit(qArr(ii))
      mFirstBit(qArr(ii), x)
      x = mfFirstBit(qArr(ii))
   NEXT

   'test FirstBit()
   TIX t
   TIX t
   FOR ii = 1 TO 1000000
      x = FirstBit(qArr(ii))
   NEXT
   TIX END t
   ? STR$(t) & " Original function"

   'test mFirstBit()
   TIX t3
   FOR ii = 1 TO 1000000
      mFirstBit(qArr(ii), x)
   NEXT
   TIX END t3
   ? STR$(t3) & " Multi-line macro"

   'test mfFirstBit()
   TIX t2
   FOR ii = 1 TO 1000000
      x = mfFirstBit(qArr(ii))
   NEXT
   TIX END t2
   ? STR$(t2) & " Multi-line macro function"
   ? "The macro function was" & STR$((t/t2 - 1) * 100, 3) & "% faster"
   ? "The macro was" & STR$((t/t3 - 1) * 100, 3) & "% faster"

   'test to see if mfFirstBit() = FirstBit()
   TIX t
   FOR ii = 1 TO 1000000
      x = mfFirstBit(qArr(ii))
      IF x <> FirstBit(qArr(ii)) THEN ? "<>": EXIT FUNCTION
      mFirstBit(qArr(ii), x)
      IF x <> FirstBit(qArr(ii)) THEN ? "<>": EXIT FUNCTION
   NEXT
   TIX END t
   ? "All 3 functions found the LSB equally."
   WAITKEY$
END FUNCTION

[Chris Burton]

WOW!

I can't believe the difference!! The macro function blew the [standard] assembly away. 498% faster!!

Now I truly know the depths that my knowledge is lacking. Time to do some reading.

Thanks for the code demo to open my eyes to the power of macros.

-Chris

[Michael Mattias]

>The macro function blew the assembly away



Those MACROs *are* assembly language.

[John Gleason]

>The macro function blew the assembly away



Those MACROs *are* assembly language.

With a 498% speed increase, I'm surprised Chris got out as coherent a sentence as 'e did!

An editor might do something like this: "The macro function blew the assembly [standard function] away."

However, I don't know what a good editor would do.

[Chris Burton]

Now, if I understand the code changes correctly, 2 changes of substance were made. By using the macro, i remove 1 function call. And by returning the data to the parameter outL, I save 1 memory write?

And yea, I was incoherent in my haste to implement the macro in the app. 490% in the test wast good, but I was just as happy with 10% overall speed bump to the real app.

Thanks again for the help. Now I'm on the hunt for other places where this new tool in my toolbox can be applied.

-Chris

[Michael Mattias]

An editor might do something like this: "The macro function blew the assembly [standard function] away."

However, I don't know what a good editor would do

"Better coding technique dramatically improved performance."