32 bit versions for bitscan64

[mcostalba]

1. why does bsf call itself ?

In C++ you can overload on argument type, so perhaps there is a

Code: Select all

int bsf(U32);

somewhere....

[Aleks Peshkov]

Code: Select all

    inline U32 lo&#40;U64 b&#41; &#123; return small_cast<U32>&#40;b&#41;; &#125;
    inline U32 hi&#40;U64 b&#41; &#123; return static_cast<U32>&#40;b >> 32&#41;; &#125;

    inline index_t bsf&#40;U64 value&#41; &#123;
        U32 lo = &#58;&#58;lo&#40;value&#41;;
        return bsf&#40;lo ? lo &#58; hi&#40;value&#41;) + &#40;lo ? 0 &#58; 32&#41;;
    &#125;

1. why does bsf call itself ?

A bsf(U64) function calls a different bsf(U32) function.

2. i cannot find a small_cast operator (although i know what it should do)
Well, it is my own operator.

Code: Select all

template <typename T>
inline T universe&#40;) &#123; return static_cast<T>(~static_cast<T>&#40;0&#41;); &#125;

template <typename T, typename N>
inline T small_cast&#40;N n&#41; &#123; return static_cast<T>&#40;n & universe<T>()); &#125;

3. and what is the issue between the _trivial_ c version and the c++ version ? In other words, what makes the c++ version more complex than the pure c version?

Sorry, I did not assume anyone take my code literaly and did not want to open discussion about C++ syntax tricks.

4.i thought explicit putting the (reduced)type in front of more complex type is enough for type conversion downwards.

Simple cast to smaller type should emit a warning in any compiler. And at least Visual C++ debug build tests and breaks an execution of a program when silent conversion losers significant bits.

[mcostalba]

Well, it is my own operator.

Code: Select all

template <typename T>
inline T universe&#40;) &#123; return static_cast<T>(~static_cast<T>&#40;0&#41;); &#125;

template <typename T, typename N>
inline T small_cast&#40;N n&#41; &#123; return static_cast<T>&#40;n & universe<T>()); &#125;

Well I sometimes find myself to indulge on C++ obscurities but indeed you beat me hands down !

Simple cast to smaller type should emit a warning in any compiler. And at least Visual C++ debug build tests and breaks an execution of a program when silent conversion losers significant bits.

A cast is not a silent conversion and does not make the compiler emit any warning.

Code: Select all

void test (U64 b) {

   U32 a = b; // This is a warning
   U32 c = (U32)b; // This is not !
}

[Desperado]

Thx! Aleks for the really fast reply .
(i thought of some things you mentioned, all hiden in your objects )

but now for marco, some _UNTESTED_ code (and maybe not really outworked code). but it should give the right direction...and maybe it can
be used like it is.

Code: Select all

BTB_T only_pop1(BTB_T &bb)
	{
	 UI_32 *ptr = (UI_32*)&bb;

	 ULONG id=64;

	 _BitScanForward(&id,*(ptr)) ? id : _BitScanForward(&id,*(ptr+=1));

	 return(*ptr^=BB(id));
	}


ULONG pop_and_index1(BTB_T &bb)
	{
	 UI_32 *ptr = (UI_32*)&bb;

	 ULONG id=64;

	 _BitScanForward(&id,*(ptr)) ? id : _BitScanForward(&id,*(ptr+=1));
	 
	 *ptr^=(BB(id));

	 return(ptr==(UI_32*)&bb ? id : 32+id);
	}

This has to be validated of course (if it works, not time yet to do), and if so of course some instructions may be saved by tuning.

today no more time left for this... til tomorrow

[mcostalba]

How is defined:

Code: Select all

BB(id)

[Desperado]

Oh...

#define BB(SQ64) ((UI_64) 1 << (SQ64))

cheers

[mcostalba]

At first glance this seems wrong:

Code: Select all

_BitScanForward(&id,*(ptr+=1)); 

You may not want to update the pointer, perhaps this one:

Code: Select all

_BitScanForward(&id,*(ptr+1)); 

Also this one is not very clear

Code: Select all

*ptr^=(BB(id)); 

Because ptr points to a 32bit quantity while BB() is a 64 bits.

[Desperado]

Well , i _want_ to update the pointer -> ptr+=1 !

so i can update the upper half of the 64 bit value,
(the pointer is only conditionally updated (i think), if the right exression
is executed)

and you are right, in this case instead of BB(x) there should
be used

#define BIT32(X) ((UI_32)1 << (X))...

where x is:

(0...x...31)

i have to go...

[mcostalba]

I have tested the below version on my Intel Core 2 Duo but with no results, perhaps a very very slightly increase but well below 1%

Code: Select all

Square pop_1st_bit(Bitboard* bb) {

  uint32_t* ptr = (uint32_t*)bb;
  unsigned long id;

  if (*ptr)
  {
      _BitScanForward(&id, *ptr);
      *ptr ^= &#40;1 << id&#41;;
  &#125;
  else
  &#123;
      ptr += 1;
      _BitScanForward&#40;&id, *ptr&#41;;
      *ptr ^= &#40;1 << id&#41;;
      id += 32;
  &#125;
  return Square&#40;id&#41;;
&#125;

This is the disassembled code (MSVC):

Code: Select all

Square pop_1st_bit(Bitboard* bb) {
0040E760  push        ecx  

  uint32_t* ptr = (uint32_t*)bb;
  unsigned long id;

  if (*ptr)
0040E761  mov         edx,dword ptr [esi]  
0040E763  push        edi  
  {
      _BitScanForward(&id, *ptr);
      *ptr ^= &#40;1 << id&#41;;
0040E764  mov         edi,1  
0040E769  test        edx,edx  
0040E76B  je          pop_1st_bit+1Bh &#40;40E77Bh&#41;  
0040E76D  bsf         eax,edx  
0040E770  mov         ecx,eax  
0040E772  shl         edi,cl  
0040E774  xor         edi,edx  
0040E776  mov         dword ptr &#91;esi&#93;,edi  
0040E778  pop         edi  
  &#125;
  return Square&#40;id&#41;;
&#125;
0040E779  pop         ecx  
0040E77A  ret  
  &#125;
  else
  &#123;
      ptr += 1;
      _BitScanForward&#40;&id, *ptr&#41;;
0040E77B  mov         edx,dword ptr &#91;esi+4&#93;  
0040E77E  bsf         ecx,edx  
      *ptr ^= &#40;1 << id&#41;;
0040E781  shl         edi,cl  
0040E783  mov         eax,ecx  
0040E785  xor         edi,edx  
0040E787  mov         dword ptr &#91;esi+4&#93;,edi  
      id += 32;
0040E78A  add         eax,20h  
0040E78D  pop         edi  
  &#125;
  return Square&#40;id&#41;;
&#125;
0040E78E  pop         ecx  
0040E78F  ret  

[Gerd Isenberg]

Hi Marco,

first i have to correct my last post !!!

Putting the table to global scope, everything changes!

!oups, how that? You forgot const? Have you inspected assembly?

This is how Matt's routine should look like in x86-32. If you have 64 mov [mem], someconst instructions before, you may use a char array, or use static const, but I guess const should be fine for compile time initialization.

Code: Select all

; input  edx:ecx bb
; output eax bit
mov  eax, ecx
sub  ecx, 1
mov  ebx, edx
sbb  edx, 0
xor  eax, ecx
xor  eax, ebx
xor  eax, edx
imul eax, 78291ACFH
shr  eax, 26
mov  eax, dword ptr [lookup + 4*eax] ; movzx  eax, byte ptr [lookup + eax]
// ~ 12 cycles

The result seems to be equal(about)....(for _bitscan alone_)
BUT on _anti_ bitscan machine.

The bsf approach may suffer from miss-predicted branches. 32-bit bsf K7/K8 is alone 8 cycles vector path.