mask.h
Go to the documentation of this file.
#ifndef OSL_MISC_MASK_H
#define OSL_MISC_MASK_H
#include "osl/config.h"
#include <cassert>
#include <iosfwd>
namespace osl
{
namespace misc
{
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));
}
template <class Integer>
static Integer lowestBit(Integer mask){
assert(mask);
return static_cast<Integer>(mask & (-mask));
}
};
#if 0
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 misc
{
template <class Integer>
class GeneralMask
{
Integer mask;
private:
GeneralMask(Integer value) : mask(value) {}
public:
GeneralMask() : mask(0) {}
static const GeneralMask makeDirect(Integer value) { return GeneralMask(value); }
GeneralMask& operator&=(const GeneralMask& r)
{
mask &= r.mask;
return *this;
}
GeneralMask& operator|=(const GeneralMask& r)
{
mask |= r.mask;
return *this;
}
GeneralMask& operator^=(const GeneralMask& r)
{
mask ^= r.mask;
return *this;
}
GeneralMask& operator-=(const GeneralMask& r)
{
mask -= r.mask;
return *this;
}
GeneralMask& operator+=(const GeneralMask& r)
{
mask += r.mask;
return *this;
}
GeneralMask& operator<<=(int shift)
{
mask <<= shift;
return *this;
}
GeneralMask& operator>>=(int shift)
{
mask >>= shift;
return *this;
}
const GeneralMask operator~() const { return GeneralMask(~mask); }
int bsf() const { return BitOp::bsf(mask); }
int bsr() const { return BitOp::bsr(mask); }
int takeOneBit() { return BitOp::takeOneBit(mask); }
bool hasMultipleBit() const { return BitOp::hasMultipleBit(mask); }
int countBit2() const {
assert(mask);
return (mask & (mask-1)) ? 2 : 1;
}
int
#ifdef __GNUC__
__attribute__ ((pure))
#endif
countBit() const { return BitOp::countBit(mask); }
GeneralMask lowestBit() const { return BitOp::lowestBit(mask); }
bool none() const { return mask == 0; }
bool any() const { return ! none(); }
Integer value() const { return mask; }
};
template <class Integer> inline
bool operator==(const GeneralMask<Integer>& l, const GeneralMask<Integer>& r)
{
return l.value() == r.value();
}
template <class Integer> inline
bool operator!=(const GeneralMask<Integer>& l, const GeneralMask<Integer>& r)
{
return ! (l == r);
}
template <class Integer> inline
bool operator<(const GeneralMask<Integer>& l, const GeneralMask<Integer>& r)
{
return l.value() < r.value();
}
template <class Integer> inline
const GeneralMask<Integer> operator&(GeneralMask<Integer> l,
GeneralMask<Integer> r) {
GeneralMask<Integer> result = l;
return result &= r;
}
template <class Integer> inline
const GeneralMask<Integer> operator|(GeneralMask<Integer> l,
GeneralMask<Integer> r) {
GeneralMask<Integer> result = l;
return result |= r;
}
template <class Integer> inline
const GeneralMask<Integer> operator^(GeneralMask<Integer> l,
GeneralMask<Integer> r) {
GeneralMask<Integer> result = l;
return result ^= r;
}
template <class Integer> inline
const GeneralMask<Integer> operator<<(GeneralMask<Integer> m, int shift) {
GeneralMask<Integer> result = m;
return result <<= shift;
}
template <class Integer> inline
const GeneralMask<Integer> operator>>(GeneralMask<Integer> m, int shift) {
GeneralMask<Integer> result = m;
return result >>= shift;
}
typedef GeneralMask<unsigned long long> Mask64;
typedef unsigned long long mask_int_t;
typedef GeneralMask<mask_int_t> mask_t;
std::ostream& operator<<(std::ostream&, const mask_t&);
} // namespace misc
using misc::mask_int_t;
using misc::mask_t;
using misc::Mask64;
using misc::BitOp;
} // namespace osl
#endif
// ;;; Local Variables:
// ;;; mode:c++
// ;;; c-basic-offset:2
// ;;; End:
osl::misc::GeneralMask
Definition mask.h:213
osl::misc::GeneralMask::operator|=
GeneralMask & operator|=(const GeneralMask &r)
Definition mask.h:225
osl::misc::GeneralMask::none
bool none() const
Definition mask.h:297
osl::misc::GeneralMask< unsigned long long >::mask
unsigned long long mask
Definition mask.h:214
osl::misc::GeneralMask::operator+=
GeneralMask & operator+=(const GeneralMask &r)
Definition mask.h:240
osl::misc::GeneralMask::operator<<=
GeneralMask & operator<<=(int shift)
Definition mask.h:245
osl::misc::GeneralMask::makeDirect
static const GeneralMask makeDirect(Integer value)
Definition mask.h:219
osl::misc::GeneralMask::GeneralMask
GeneralMask(Integer value)
Definition mask.h:216
osl::misc::GeneralMask::operator~
const GeneralMask operator~() const
Definition mask.h:255
osl::misc::GeneralMask::bsr
int bsr() const
Definition mask.h:258
osl::misc::GeneralMask< unsigned long long >::value
unsigned long long value() const
Definition mask.h:299
osl::misc::GeneralMask::operator>>=
GeneralMask & operator>>=(int shift)
Definition mask.h:250
osl::misc::GeneralMask::hasMultipleBit
bool hasMultipleBit() const
non-zeroのmaskが複数ビットセットされているかどうかを返す.
Definition mask.h:272
osl::misc::GeneralMask::any
bool any() const
Definition mask.h:298
osl::misc::GeneralMask::countBit
int countBit() const
mask にセットされているビットの数を数える． あまり速くない．
Definition mask.h:290
osl::misc::GeneralMask::operator-=
GeneralMask & operator-=(const GeneralMask &r)
Definition mask.h:235
osl::misc::GeneralMask::countBit2
int countBit2() const
non-zeroのmaskにセットされているビットの数を2まで数える．
Definition mask.h:278
osl::misc::GeneralMask::operator^=
GeneralMask & operator^=(const GeneralMask &r)
Definition mask.h:230
osl::misc::GeneralMask::bsf
int bsf() const
Definition mask.h:257
osl::misc::GeneralMask::takeOneBit
int takeOneBit()
non-zeroのmaskのsetされているビットをLSBから探し，その番号を返す 副作用としてmaskの対応するビットをクリアする
Definition mask.h:265
osl::misc::GeneralMask::lowestBit
GeneralMask lowestBit() const
non-zeroのmaskのsetされているビットをLSBから探し，そのビットだけがsetされたmaskを返す.
Definition mask.h:296
osl::misc::GeneralMask::GeneralMask
GeneralMask()
Definition mask.h:218
osl::misc::GeneralMask::operator&=
GeneralMask & operator&=(const GeneralMask &r)
Definition mask.h:220
config.h
osl::misc
Definition basic_type.h:66
osl::misc::operator==
bool operator==(const GeneralMask< Integer > &l, const GeneralMask< Integer > &r)
Definition mask.h:303
osl::misc::operator^
const GeneralMask< Integer > operator^(GeneralMask< Integer > l, GeneralMask< Integer > r)
Definition mask.h:331
osl::misc::operator<
bool operator<(const GeneralMask< Integer > &l, const GeneralMask< Integer > &r)
Definition mask.h:313
osl::misc::mask_t
GeneralMask< mask_int_t > mask_t
Definition mask.h:351
osl::misc::operator!=
bool operator!=(const GeneralMask< Integer > &l, const GeneralMask< Integer > &r)
Definition mask.h:308
osl::misc::mask_int_t
unsigned long long mask_int_t
Definition mask.h:350
osl::misc::operator>>
const GeneralMask< Integer > operator>>(GeneralMask< Integer > m, int shift)
Definition mask.h:342
osl::misc::operator|
const GeneralMask< Integer > operator|(GeneralMask< Integer > l, GeneralMask< Integer > r)
Definition mask.h:325
osl::misc::Mask64
GeneralMask< unsigned long long > Mask64
Definition mask.h:347
osl::misc::operator&
const GeneralMask< Integer > operator&(GeneralMask< Integer > l, GeneralMask< Integer > r)
Definition mask.h:319
osl::misc::operator<<
const GeneralMask< Integer > operator<<(GeneralMask< Integer > m, int shift)
Definition mask.h:337
osl
Definition additionalEffect.h:6
osl::__attribute__
const PtypeO PTYPEO_EDGE __attribute__((unused))
osl::BitOp::bsf
static int bsf(Integer mask)
Definition mask.h:138
osl::BitOp::takeOneBit
static int takeOneBit(Integer &mask)
Definition mask.h:148
osl::BitOp::bsr
static int bsr(Integer mask)
Definition mask.h:143
osl::BitOp::hasMultipleBit
static bool hasMultipleBit(Integer mask)
Definition mask.h:171
osl::BitOp::lowestBit
static Integer lowestBit(Integer mask)
non-zeroのmaskのsetされているビットをLSBから探し，そのビットだけがsetされたmaskを返す.
Definition mask.h:179
osl::BitOp::countBit
static int countBit(Integer mask)
Definition mask.h:160
osl::misc::BitOp
Definition mask.h:136
osl::misc::BitOp::bsf
static int bsf(Integer mask)
Definition mask.h:138
osl::misc::BitOp::takeOneBit
static int takeOneBit(Integer &mask)
Definition mask.h:148
osl::misc::BitOp::bsr
static int bsr(Integer mask)
Definition mask.h:143
osl::misc::BitOp::hasMultipleBit
static bool hasMultipleBit(Integer mask)
Definition mask.h:171
osl::misc::BitOp::lowestBit
static Integer lowestBit(Integer mask)
non-zeroのmaskのsetされているビットをLSBから探し，そのビットだけがsetされたmaskを返す.
Definition mask.h:179
osl::misc::BitOp::countBit
static int countBit(Integer mask)
Definition mask.h:160
osl::misc::Bsf< unsigned int >::bsf
static int bsf(unsigned int mask)
Definition mask.h:19
osl::misc::Bsf< unsigned long long >::bsf
static int bsf(unsigned long long mask)
Definition mask.h:68
osl::misc::Bsf< unsigned short >::bsf
static unsigned short bsf(unsigned short mask)
Definition mask.h:46
osl::misc::Bsf
x86 bsf 命令
Definition mask.h:14
osl::misc::Bsr< unsigned int >::bsr
static int bsr(unsigned int mask)
Definition mask.h:90
osl::misc::Bsr< unsigned long long >::bsr
static int bsr(unsigned long long mask)
Definition mask.h:118
osl::misc::Bsr
Definition mask.h:85