Author: Dann Corbit
Date: 13:10:10 02/17/04
Go up one level in this thread
/* =========== */
/* From this: */
/* =========== */
typedef unsigned __int64 BITBOARD;
typedef union tag_bu {
BITBOARD b;
unsigned long w[2];
} BU;
static int dieter_popc(BU a)
{
unsigned long w;
int n = 0;
w = a.w[0];
if (w)
do
n++;
while ((w &= w - 1) != 0);
w = a.w[1];
if (w)
do
n++;
while ((w &= w - 1) != 0);
return n;
}
static int bitfiddling(BU bb)
{
unsigned long u,
v;
v = bb.w[1];
u = bb.w[0];
u = (u&0x55555555) + ((u>>1)&0x55555555);
v = (v&0x55555555) + ((v>>1)&0x55555555);
u = (u & 0x33333333) + ((u >> 2) & 0x33333333)
+ (v & 0x33333333) + ((v >> 2) & 0x33333333);
u = (u&0x0f0f0f0f) + ((u>>4)&0x0f0f0f0f);
u += u >> 8;
u += u >> 16;
return u & 0xff;
}
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(void)
{
BU a;
int c;
srand((unsigned) time(NULL));
a.w[0] = rand();
a.w[1] = rand();
c = dieter_popc(a);
printf("count of 0x%08x%08x is %d\n", a.w[0], a.w[1], c);
c = bitfiddling(a);
printf("count of 0x%08x%08x is %d\n", a.w[0], a.w[1], c);
return 0;
}
;===============
; We get this:
;===============
; Listing generated by Microsoft (R) Optimizing Compiler Version 13.10.3077
TITLE .\bits-db.c
.386P
include listing.inc
if @Version gt 510
.model FLAT
else
; COMDAT ??_C@_0BL@CMAKNOFI@count?5of?50x?$CF08x?$CF08x?5is?5?$CFd?6?$AA@
CONST SEGMENT DWORD USE32 PUBLIC 'CONST'
CONST ENDS
; COMDAT _dieter_popc
_TEXT SEGMENT PARA USE32 PUBLIC 'CODE'
_TEXT ENDS
; COMDAT _bitfiddling
_TEXT SEGMENT PARA USE32 PUBLIC 'CODE'
_TEXT ENDS
; COMDAT _main
_TEXT SEGMENT PARA USE32 PUBLIC 'CODE'
_TEXT ENDS
FLAT GROUP _DATA, CONST, _BSS
ASSUME CS: FLAT, DS: FLAT, SS: FLAT
endif
INCLUDELIB LIBC
INCLUDELIB OLDNAMES
PUBLIC ??_C@_0BL@CMAKNOFI@count?5of?50x?$CF08x?$CF08x?5is?5?$CFd?6?$AA@ ;
`string'
EXTRN _time:NEAR
EXTRN _srand:NEAR
EXTRN _rand:NEAR
EXTRN _printf:NEAR
; COMDAT ??_C@_0BL@CMAKNOFI@count?5of?50x?$CF08x?$CF08x?5is?5?$CFd?6?$AA@
CONST SEGMENT
??_C@_0BL@CMAKNOFI@count?5of?50x?$CF08x?$CF08x?5is?5?$CFd?6?$AA@ DB 'coun'
DB 't of 0x%08x%08x is %d', 0aH, 00H ; `string'
; Function compile flags: /Ogty
; File c:\tmp\bits-db.c
CONST ENDS
; COMDAT _bitfiddling
_TEXT SEGMENT
_bb$ = 8 ; size = 8
_bitfiddling PROC NEAR ; COMDAT
; 27 : unsigned long u,
; 28 : v;
; 29 : v = bb.w[1];
; 30 : u = bb.w[0];
; 31 : u = (u&0x55555555) + ((u>>1)&0x55555555);
mov eax, DWORD PTR _bb$[esp-4]
mov ecx, eax
and eax, 1431655765 ; 55555555H
shr ecx, 1
and ecx, 1431655765 ; 55555555H
add ecx, eax
; 32 : v = (v&0x55555555) + ((v>>1)&0x55555555);
mov eax, DWORD PTR _bb$[esp]
mov edx, eax
and eax, 1431655765 ; 55555555H
shr edx, 1
and edx, 1431655765 ; 55555555H
add edx, eax
; 33 : u = (u & 0x33333333) + ((u >> 2) & 0x33333333)
; 34 : + (v & 0x33333333) + ((v >> 2) & 0x33333333);
mov eax, ecx
shr eax, 2
and eax, 858993459 ; 33333333H
push esi
mov esi, edx
shr esi, 2
and ecx, 858993459 ; 33333333H
and esi, 858993459 ; 33333333H
add eax, esi
add eax, ecx
and edx, 858993459 ; 33333333H
add eax, edx
; 35 : u = (u&0x0f0f0f0f) + ((u>>4)&0x0f0f0f0f);
mov ecx, eax
and eax, 252645135 ; 0f0f0f0fH
shr ecx, 4
and ecx, 252645135 ; 0f0f0f0fH
add ecx, eax
; 36 : u += u >> 8;
mov eax, ecx
shr eax, 8
add ecx, eax
; 37 : u += u >> 16;
mov eax, ecx
shr eax, 16 ; 00000010H
add eax, ecx
; 38 : return u & 0xff;
and eax, 255 ; 000000ffH
pop esi
; 39 : }
ret 0
_bitfiddling ENDP
; Function compile flags: /Ogty
_TEXT ENDS
; COMDAT _dieter_popc
_TEXT SEGMENT
_a$ = 8 ; size = 8
_dieter_popc PROC NEAR ; COMDAT
; 10 : unsigned long w;
; 11 : int n = 0;
; 12 : w = a.w[0];
mov ecx, DWORD PTR _a$[esp-4]
xor eax, eax
; 13 : if (w)
test ecx, ecx
je SHORT $L552
npad 6
$L550:
; 14 : do
; 15 : n++;
; 16 : while ((w &= w - 1) != 0);
lea edx, DWORD PTR [ecx-1]
inc eax
and ecx, edx
jne SHORT $L550
$L552:
; 17 : w = a.w[1];
mov ecx, DWORD PTR _a$[esp]
; 18 : if (w)
test ecx, ecx
je SHORT $L556
$L554:
; 19 : do
; 20 : n++;
; 21 : while ((w &= w - 1) != 0);
lea edx, DWORD PTR [ecx-1]
inc eax
and ecx, edx
jne SHORT $L554
$L556:
; 22 : return n;
; 23 : }
ret 0
_dieter_popc ENDP
_TEXT ENDS
PUBLIC _main
; Function compile flags: /Ogty
; COMDAT _main
_TEXT SEGMENT
_main PROC NEAR ; COMDAT
; 47 : {
push esi
push edi
; 48 : BU a;
; 49 : int c;
; 50 : srand((unsigned) time(NULL));
push 0
call _time
push eax
call _srand
add esp, 8
; 51 : a.w[0] = rand();
call _rand
mov esi, eax
; 52 : a.w[1] = rand();
call _rand
mov edi, eax
; 53 : c = dieter_popc(a);
xor eax, eax
test esi, esi
mov ecx, esi
je SHORT $L1339
$L1337:
lea edx, DWORD PTR [ecx-1]
inc eax
and ecx, edx
jne SHORT $L1337
$L1339:
test edi, edi
mov ecx, edi
je SHORT $L1343
$L1341:
lea edx, DWORD PTR [ecx-1]
inc eax
and ecx, edx
jne SHORT $L1341
$L1343:
; 54 : printf("count of 0x%08x%08x is %d\n", a.w[0], a.w[1], c);
push eax
push edi
push esi
push OFFSET
FLAT:??_C@_0BL@CMAKNOFI@count?5of?50x?$CF08x?$CF08x?5is?5?$CFd?6?$AA@
call _printf
; 55 : c = bitfiddling(a);
push edi
push esi
call _bitfiddling
; 56 : printf("count of 0x%08x%08x is %d\n", a.w[0], a.w[1], c);
push eax
push edi
push esi
push OFFSET
FLAT:??_C@_0BL@CMAKNOFI@count?5of?50x?$CF08x?$CF08x?5is?5?$CFd?6?$AA@
call _printf
add esp, 40 ; 00000028H
pop edi
; 57 : return 0;
xor eax, eax
pop esi
; 58 : }
ret 0
_main ENDP
_TEXT ENDS
END
;=====================================
; And with SSE2 enabled, we get this:
;=====================================
; Listing generated by Microsoft (R) Optimizing Compiler Version 13.10.3077
TITLE .\bits-db.c
.386P
include listing.inc
if @Version gt 510
.model FLAT
else
; COMDAT ??_C@_0BL@CMAKNOFI@count?5of?50x?$CF08x?$CF08x?5is?5?$CFd?6?$AA@
CONST SEGMENT DWORD USE32 PUBLIC 'CONST'
CONST ENDS
; COMDAT _dieter_popc
_TEXT SEGMENT PARA USE32 PUBLIC 'CODE'
_TEXT ENDS
; COMDAT _bitfiddling
_TEXT SEGMENT PARA USE32 PUBLIC 'CODE'
_TEXT ENDS
; COMDAT _main
_TEXT SEGMENT PARA USE32 PUBLIC 'CODE'
_TEXT ENDS
FLAT GROUP _DATA, CONST, _BSS
ASSUME CS: FLAT, DS: FLAT, SS: FLAT
endif
INCLUDELIB LIBC
INCLUDELIB OLDNAMES
PUBLIC ??_C@_0BL@CMAKNOFI@count?5of?50x?$CF08x?$CF08x?5is?5?$CFd?6?$AA@ ;
`string'
EXTRN _time:NEAR
EXTRN _srand:NEAR
EXTRN _rand:NEAR
EXTRN _printf:NEAR
; COMDAT ??_C@_0BL@CMAKNOFI@count?5of?50x?$CF08x?$CF08x?5is?5?$CFd?6?$AA@
CONST SEGMENT
??_C@_0BL@CMAKNOFI@count?5of?50x?$CF08x?$CF08x?5is?5?$CFd?6?$AA@ DB 'coun'
DB 't of 0x%08x%08x is %d', 0aH, 00H ; `string'
; Function compile flags: /Ogty
; File c:\tmp\bits-db.c
CONST ENDS
; COMDAT _bitfiddling
_TEXT SEGMENT
_bb$ = 8 ; size = 8
_bitfiddling PROC NEAR ; COMDAT
; 27 : unsigned long u,
; 28 : v;
; 29 : v = bb.w[1];
; 30 : u = bb.w[0];
; 31 : u = (u&0x55555555) + ((u>>1)&0x55555555);
mov eax, DWORD PTR _bb$[esp-4]
mov ecx, eax
and eax, 1431655765 ; 55555555H
shr ecx, 1
and ecx, 1431655765 ; 55555555H
add ecx, eax
; 32 : v = (v&0x55555555) + ((v>>1)&0x55555555);
mov eax, DWORD PTR _bb$[esp]
mov edx, eax
and eax, 1431655765 ; 55555555H
shr edx, 1
and edx, 1431655765 ; 55555555H
add edx, eax
; 33 : u = (u & 0x33333333) + ((u >> 2) & 0x33333333)
; 34 : + (v & 0x33333333) + ((v >> 2) & 0x33333333);
mov eax, ecx
shr eax, 2
and eax, 858993459 ; 33333333H
push esi
mov esi, edx
shr esi, 2
and ecx, 858993459 ; 33333333H
and esi, 858993459 ; 33333333H
add eax, esi
add eax, ecx
and edx, 858993459 ; 33333333H
add eax, edx
; 35 : u = (u&0x0f0f0f0f) + ((u>>4)&0x0f0f0f0f);
mov ecx, eax
and eax, 252645135 ; 0f0f0f0fH
shr ecx, 4
and ecx, 252645135 ; 0f0f0f0fH
add ecx, eax
; 36 : u += u >> 8;
mov eax, ecx
shr eax, 8
add ecx, eax
; 37 : u += u >> 16;
mov eax, ecx
shr eax, 16 ; 00000010H
add eax, ecx
; 38 : return u & 0xff;
and eax, 255 ; 000000ffH
pop esi
; 39 : }
ret 0
_bitfiddling ENDP
; Function compile flags: /Ogty
_TEXT ENDS
; COMDAT _dieter_popc
_TEXT SEGMENT
_a$ = 8 ; size = 8
_dieter_popc PROC NEAR ; COMDAT
; 10 : unsigned long w;
; 11 : int n = 0;
; 12 : w = a.w[0];
mov ecx, DWORD PTR _a$[esp-4]
xor eax, eax
; 13 : if (w)
test ecx, ecx
je SHORT $L552
npad 6
$L550:
; 14 : do
; 15 : n++;
; 16 : while ((w &= w - 1) != 0);
lea edx, DWORD PTR [ecx-1]
add eax, 1
and ecx, edx
jne SHORT $L550
$L552:
; 17 : w = a.w[1];
mov ecx, DWORD PTR _a$[esp]
; 18 : if (w)
test ecx, ecx
je SHORT $L556
$L554:
; 19 : do
; 20 : n++;
; 21 : while ((w &= w - 1) != 0);
lea edx, DWORD PTR [ecx-1]
add eax, 1
and ecx, edx
jne SHORT $L554
$L556:
; 22 : return n;
; 23 : }
ret 0
_dieter_popc ENDP
_TEXT ENDS
PUBLIC _main
; Function compile flags: /Ogty
; COMDAT _main
_TEXT SEGMENT
_main PROC NEAR ; COMDAT
; 47 : {
push esi
push edi
; 48 : BU a;
; 49 : int c;
; 50 : srand((unsigned) time(NULL));
push 0
call _time
push eax
call _srand
add esp, 8
; 51 : a.w[0] = rand();
call _rand
mov esi, eax
; 52 : a.w[1] = rand();
call _rand
mov edi, eax
; 53 : c = dieter_popc(a);
xor eax, eax
test esi, esi
mov ecx, esi
je SHORT $L1339
$L1337:
lea edx, DWORD PTR [ecx-1]
add eax, 1
and ecx, edx
jne SHORT $L1337
$L1339:
test edi, edi
mov ecx, edi
je SHORT $L1343
$L1341:
lea edx, DWORD PTR [ecx-1]
add eax, 1
and ecx, edx
jne SHORT $L1341
$L1343:
; 54 : printf("count of 0x%08x%08x is %d\n", a.w[0], a.w[1], c);
push eax
push edi
push esi
push OFFSET
FLAT:??_C@_0BL@CMAKNOFI@count?5of?50x?$CF08x?$CF08x?5is?5?$CFd?6?$AA@
call _printf
; 55 : c = bitfiddling(a);
push edi
push esi
call _bitfiddling
; 56 : printf("count of 0x%08x%08x is %d\n", a.w[0], a.w[1], c);
push eax
push edi
push esi
push OFFSET
FLAT:??_C@_0BL@CMAKNOFI@count?5of?50x?$CF08x?$CF08x?5is?5?$CFd?6?$AA@
call _printf
add esp, 40 ; 00000028H
pop edi
; 57 : return 0;
xor eax, eax
pop esi
; 58 : }
ret 0
_main ENDP
_TEXT ENDS
END
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.