PureBasic ASM Sample: Bit-Count

[Theo Gottwald]

Code: [Select]

EnableExplicit

Procedure.l PopCount0 (k.l)
   ! mov    eax, [p.v_k]
   ! popcnt eax, eax
   
   ProcedureReturn
EndProcedure


Procedure.l PopCount1 (k.l)
   ; -- wilbert
   
   !xor eax, eax
   !mov edx, [p.v_k]
   !and edx, edx
   !jz popcount_m2_done
   
   !popcount_m2_loop:
   !inc eax
   !lea ecx, [edx - 1]
   !and edx, ecx
   !jnz popcount_m2_loop
   
   !popcount_m2_done:
   ProcedureReturn
EndProcedure


Procedure.l PopCount2 (k.l)
   ; -- luis
   
   !mov edx, [p.v_k]
   !xor eax, eax
   !mov ecx, 32
   
   !popcount2:
   !shl edx, 1
   !adc eax, 0
   !dec ecx
   !jnz popcount2
   
   ProcedureReturn
EndProcedure


Procedure.l PopCount3 (k.l)
   ; -- luis
   
   !mov edx, [p.v_k]
   !xor eax, eax
   !mov ecx, 32
   
   !popcount3:
   !shl edx, 1
   !adc eax, 0
   !loop popcount3
   
   ProcedureReturn
EndProcedure


Procedure.l PopCount4 (k.l)
   ; -- LJ
   
   ! mov  edx, [p.v_k]
   ! xor  eax, eax
   ! mov  ecx, 32
   
   ! popcount_again:
   ! dec  ecx
   ! bt   edx, ecx
   ! jnc  popcount_notset
   ! inc  eax
   ! popcount_notset:   
   ! or   ecx, ecx
   ! jnz  popcount_again
   
   ProcedureReturn
EndProcedure


Procedure.l PopCount5 (v.l, i = 0)
   ; -- Trond
   
   If i < 32
      ProcedureReturn (v & 1 << i) >> i + PopCount5(v, i+1)
   EndIf
EndProcedure


Procedure.l PopCount6 (v.l)
   ; -- Trond
   
   Protected i.i, Agg.l
   
   For i = 0 To 31
      Agg + (v & 1 << i) >> i
   Next
   ProcedureReturn Agg
EndProcedure


Procedure.l Popcount7 (x.l)
   ; -- idle (adapted for 32 bit)
   
   ;x - (x >> 1) &  $55555555           
   !mov eax, [p.v_x]
   !mov edx, eax
   !shr edx, 1
   !and edx, 0x55555555
   !sub eax, edx
   ;x = (x & $33333333) + ((x >> 2) & $33333333)
   !mov edx, eax       ;x
   !and eax, 0x33333333
   !shr edx, 2
   !and edx, 0x33333333
   !add eax, edx
   ;x = (x + (x >> 4)) & $0f0f0f0f0f
   !mov edx, eax
   !shr edx, 4
   !add eax, edx
   !and eax, 0x0f0f0f0f
   ;x * 0x01010101 >> 24
   !imul eax, 0x01010101
   !shr eax, 24
   ProcedureReturn
EndProcedure

Procedure.l Popcount8(v.l)
    ; --- Trond without a loop
    Protected y.l
   
    y = (v & 1 <<  0) >>  0 +
        (v & 1 <<  1) >>  1 +
        (v & 1 <<  2) >>  2 +
        (v & 1 <<  3) >>  3 +
        (v & 1 <<  4) >>  4 +
        (v & 1 <<  5) >>  5 +
        (v & 1 <<  6) >>  6 +
        (v & 1 <<  7) >>  7 +
        (v & 1 <<  8) >>  8 +
        (v & 1 <<  9) >>  9 +
        (v & 1 << 10) >> 10 +
        (v & 1 << 11) >> 11 +
        (v & 1 << 12) >> 12 +
        (v & 1 << 13) >> 13 +
        (v & 1 << 14) >> 14 +
        (v & 1 << 15) >> 15 +
        (v & 1 << 16) >> 16 +
        (v & 1 << 17) >> 17 +
        (v & 1 << 18) >> 18 +
        (v & 1 << 19) >> 19 +
        (v & 1 << 20) >> 20 +
        (v & 1 << 21) >> 21 +
        (v & 1 << 22) >> 22 +
        (v & 1 << 23) >> 23 +
        (v & 1 << 24) >> 24 +
        (v & 1 << 25) >> 25 +
        (v & 1 << 26) >> 26 +
        (v & 1 << 27) >> 27 +
        (v & 1 << 28) >> 28 +
        (v & 1 << 29) >> 29 +
        (v & 1 << 30) >> 30 +
        (v & 1 << 31) >> 31
   
    ProcedureReturn y
EndProcedure


Procedure popcount9(i.l)
  Protected j.i
  j = (i >> 1) & $55555555;
  i = i - j; // (A)
  i = (i & $33333333) + ((i >> 2) & $33333333); // (B)
  i = (i & $0F0F0F0F) + ((i >> 4) & $0F0F0F0F); // (C)
  i = i * $01010101; // (D)
  ProcedureReturn i >> 24;
EndProcedure

Procedure NumOfBitsSet(N.q)
  ;=======================================================
  ;Counts the number of bits set in N and returns the
  ;count as an integer.
  ;=======================================================
  Protected Count.i
  If N < 0
    ProcedureReturn -1
  Else
    While N > 0
      If N & 1 = 1
        Count + 1
      EndIf
      N >> 1
    Wend
    ProcedureReturn Count
  EndIf
EndProcedure

; ---- Initialisation ----
Define.i i, x, rep=10000000
Define.i t0, t1, t2, t3, t4, t5, t6, t7, t8, t9, ta

Dim Rnd.l(rep)
For i = 1 To rep
   Rnd(i) = Random(2147483647)
Next


; ---- Small check whether all procedures return the same results ----
For i = 1 To 100
   x = PopCount0(Rnd(i))
   If x <> PopCount1(Rnd(i)) Or
      x <> PopCount2(Rnd(i)) Or
      x <> PopCount3(Rnd(i)) Or
      x <> PopCount4(Rnd(i)) Or
      x <> PopCount5(Rnd(i)) Or
      x <> PopCount6(Rnd(i)) Or
      x <> PopCount7(Rnd(i)) Or
      x <> PopCount8(Rnd(i)) Or
      x <> PopCount9(Rnd(i)) Or
      x <> NumOfBitsSet(Rnd(i))
     
      MessageRequester("Error",
                       "Different results for PopCount(" + Rnd(i) + ")")
      End
   EndIf
Next   


; ---- Speed test ----
t0 = ElapsedMilliseconds()
For i = 1 To rep
   x = PopCount0(Rnd(i))
Next   
t0 = ElapsedMilliseconds() - t0

t1 = ElapsedMilliseconds()
For i = 1 To rep
   x = PopCount1(Rnd(i))
Next   
t1 = ElapsedMilliseconds() - t1

t2 = ElapsedMilliseconds()
For i = 1 To rep
   x = PopCount2(Rnd(i))
Next   
t2 = ElapsedMilliseconds() - t2

t3 = ElapsedMilliseconds()
For i = 1 To rep
   x = PopCount3(Rnd(i))
Next   
t3 = ElapsedMilliseconds() - t3

t4 = ElapsedMilliseconds()
For i = 1 To rep
   x = PopCount4(Rnd(i))
Next   
t4 = ElapsedMilliseconds() - t4

t5 = ElapsedMilliseconds()
For i = 1 To rep
   x = PopCount5(Rnd(i))
Next   
t5 = ElapsedMilliseconds() - t5

t6 = ElapsedMilliseconds()
For i = 1 To rep
   x = PopCount6(Rnd(i))
Next   
t6 = ElapsedMilliseconds() - t6

t7 = ElapsedMilliseconds()
For i = 1 To rep
   x = PopCount7(Rnd(i))
Next   
t7 = ElapsedMilliseconds() - t7

t8 = ElapsedMilliseconds()
For i = 1 To rep
   x = PopCount8(Rnd(i))
Next   
t8 = ElapsedMilliseconds() - t8

t9 = ElapsedMilliseconds()
For i = 1 To rep
   x = PopCount9(Rnd(i))
Next   
t9 = ElapsedMilliseconds() - t9

ta = ElapsedMilliseconds()
For i = 1 To rep
   x = NumOfBitsSet(Rnd(i))
Next   
ta = ElapsedMilliseconds() - ta

MessageRequester("PopCount speed test",
                 "t0 = " + t0 + " ms     (" + Int(100*t0/t1) + "%) (Intel)" + #LF$ +
                 "t1 = " + t1 + " ms   (100%) (wilbert)" + #LF$ +
                 "t2 = " + t2 + " ms   (" + Int(100*t2/t1) + "%) (luis)" + #LF$ +
                 "t3 = " + t3 + " ms   (" + Int(100*t3/t1) + "%) (luis2)" + #LF$ +
                 "t4 = " + t4 + " ms   (" + Int(100*t4/t1) + "%) Little John)" + #LF$ +
                 "t5 = " + t5 + " ms   (" + Int(100*t5/t1) + "%) (Trond)" + #LF$ +
                 "t6 = " + t6 + " ms   (" + Int(100*t6/t1) + "%) (Trond2)" + #LF$ +
                 "t7 = " + t7 + " ms   (" + Int(100*t7/t1) + "%) (idle)" + #LF$ +
                 "t8 = " + t8 + " ms   (" + Int(100*t8/t1) + "%) (said version of trond unrolled)" + #LF$ +
                 "t9 = " + t9 + " ms   (" + Int(100*t9/t1) + "%) (idle-PB)" + #LF$ +
                 "ta = " + ta + " ms   (" + Int(100*ta/t1) + "%) (davido)")

or in x64

Code: [Select]

Procedure PopCount64(x.q)
  !mov rax, [p.v_x]
  !mov rdx, rax
  !shr rdx, 1
  !and rdx, [popcount64_v55]
  !sub rax, rdx
  ;x = (x & $3333333333333333) + ((x >> 2) & $3333333333333333)
  !mov rdx, rax       ;x
  !and rax, [popcount64_v33]
  !shr rdx, 2
  !and rdx, [popcount64_v33]
  !add rax, rdx
  ;x = (x + (x >> 4)) & $0f0f0f0f0f0f0f0f0f0f
  !mov rdx, rax
  !shr rdx, 4
  !add rax, rdx
  !and rax, [popcount64_v0f]
  ;x * $0101010101010101 >> 56
  !imul rax, [popcount64_v01]
  !shr rax, 56
  ProcedureReturn
  !popcount64_v01: dq 0x0101010101010101
  !popcount64_v0f: dq 0x0f0f0f0f0f0f0f0f
  !popcount64_v33: dq 0x3333333333333333
  !popcount64_v55: dq 0x5555555555555555
EndProcedure
;---------------------------------------------
x = Random($FFFFFFFF)
Debug Bin(x)
Debug Popcount64(x)
from: PureBasic Forum