libosl-dev 0.6.0-3 / usr / include / osl / misc / bitOp.h

#ifndef OSL_MISC_BITOP_H
#define OSL_MISC_BITOP_H

#include "osl/config.h"
#include <cassert>
namespace osl
{
  namespace misc
  {
  /**
   * x86 bsf 命令
   */
  template <class Integer> struct Bsf;

  template <> 
  struct Bsf<unsigned int>
  {
    static int bsf(unsigned int mask)
    {
      assert(mask);
#ifdef __x86_64__
      int ret;
      __asm__("bsfl %1,%0" : "=r"(ret) : "r"(mask));
      return ret;
#else /* これ以下は 32bit 環境 */
#  ifdef __i386__
      int ret;
      __asm__("bsfl %1,%0" : "=r"(ret) : "r"(mask));
      return ret;
#  elif defined __GNUC__
      return __builtin_ctzl(mask);
#  else
      for (int i=0;i<32;i++)
	if (mask & (1<<i))
	  return i;
#  endif
#endif
      assert(0);
      return -1;
    }
  };
  template <> 
  struct Bsf<unsigned short>
  {
    static unsigned short bsf(unsigned short mask)
    {
      assert(mask);
#ifdef __x86_64__
      unsigned short ret;
      __asm__("bsfw %1,%0" : "=r"(ret) : "r"(mask));
      return ret;
#else /* これ以下は 32bit 環境 */
#  ifdef __i386__
      unsigned short ret;
      __asm__("bsfw %1,%0" : "=r"(ret) : "r"(mask));
      return ret;
#  else
      return __builtin_ctzl(mask);
#  endif
#endif
    }
  };
  
  template <> 
  struct Bsf<unsigned long long>
  {
    static int bsf(unsigned long long mask)
    {
      assert(mask);
#ifdef __x86_64__
      long long ret;
      __asm__("bsfq %1,%0" : "=r"(ret) : "r"(mask));
      return static_cast<int>(ret);
#else /* これ以下は 32bit 環境 */
      unsigned int mask32 = static_cast<unsigned int>(mask);
      if (mask32)
	return Bsf<unsigned int>::bsf(mask32);
      mask32 = static_cast<unsigned int>(mask >> 32);
      return 32+Bsf<unsigned int>::bsf(mask32);
#endif
    }
  };

  template <class Integer> struct Bsr;

  template <> 
  struct Bsr<unsigned int>
  {
    static int bsr(unsigned int mask)
    {
      assert(mask);
#ifdef __x86_64__
      int ret;
      __asm__("bsrl %1,%0" : "=r"(ret) : "r"(mask));
      return ret;
#else /* これ以下は 32bit 環境 */
#  ifdef __i386__
      int ret;
      __asm__("bsrl %1,%0" : "=r"(ret) : "r"(mask));
      return ret;
#  elif __GNUC__
      return __builtin_clzl(mask);
#  else
      for (int i=31; i>=0; --i)
	if (mask & (1<<i))
	  return i;
#  endif
#endif
      assert(0);
      return -1;
    }
  };
  
  template <> 
  struct Bsr<unsigned long long>
  {
    static int bsr(unsigned long long mask)
    {
      assert(mask);
#ifdef __x86_64__
      long long ret;
      __asm__("bsrq %1,%0" : "=r"(ret) : "r"(mask));
      return static_cast<int>(ret);
#else /* これ以下は 32bit 環境 */
      unsigned int mask32 = static_cast<unsigned int>(mask >> 32);
      if (mask32)
	return 32+Bsr<unsigned int>::bsr(mask32);
      mask32 = static_cast<unsigned int>(mask);
      return Bsr<unsigned int>::bsr(mask32);
#endif
    }
  };
  
  struct BitOp
  {
    template <class Integer>
    static int bsf(Integer mask)
    {
      return Bsf<Integer>::bsf(mask);
    }
    template <class Integer>
    static int bsr(Integer mask)
    {
      return Bsr<Integer>::bsr(mask);
    }
    template <class Integer>
    static int takeOneBit(Integer& mask){
      assert(mask);
      const int num=bsf(mask);
      mask &= mask-1;
      return num;
    }

    template <class Integer>
    static int
#ifdef __GNUC__
	__attribute__ ((const))
#endif
    countBit(Integer mask)
    {
      int count=0;
      while (mask) 
      {
	++count;
	mask &= (mask-1);
      }
      return count;
    }
    template <class Integer>
    static bool hasMultipleBit(Integer mask){
      assert(mask);
      return (mask & (mask-1));
    }
    /**
     * non-zeroのmaskのsetされているビットをLSBから探し，そのビットだけがsetされたmaskを返す.
     */
    template <class Integer>
    static Integer lowestBit(Integer mask){
      assert(mask);
      return static_cast<Integer>(mask & (-mask));
    }
  };
  
#if 0
  /**
   * bit数が多い時は?
   * population countは
   * Cray, CDC Cyber series, Alliant FX/80.
   * UltraSPARC, Alpha 21264
   * Intel x86 has the parity of a byte
   *#define bitcount(n)                                                     \
   * (tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111), \
   * tmp = ((tmp + (tmp >> 3)) & 030707070707),                        \
   * tmp =  (tmp + (tmp >> 6)),                                        \
   * tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077)
   *
   */
  inline int countBitDense(unsigned int mask)
  {
    mask = ((mask>>1)&0x55555555)+(mask&0x55555555);
    mask = ((mask>>2)&0x33333333)+(mask&0x33333333);
    mask = ((mask>>4)+mask)&0xf0f0f0f;
    mask = (mask>>8)+mask;
    return ((mask>>16)+mask)&0x3f;
  }
#endif
  } // namespace misc
} // namespace osl
#endif // _BITOP_H
// ;;; Local Variables:
// ;;; mode:c++
// ;;; c-basic-offset:2
// ;;; End: