---

BitOps.h

Go to the documentation of this file.

#ifndef CLASSLIB_BIT_OPS_H
# define CLASSLIB_BIT_OPS_H

//<<<<<< INCLUDES                                                       >>>>>>

# include "classlib/utils/BitTraits.h"
# include "classlib/utils/BitPattern.h"
# include <algorithm>

namespace lat {
//<<<<<< PUBLIC DEFINES                                                 >>>>>>
//<<<<<< PUBLIC CONSTANTS                                               >>>>>>
//<<<<<< PUBLIC TYPES                                                   >>>>>>
//<<<<<< PUBLIC VARIABLES                                               >>>>>>
//<<<<<< PUBLIC FUNCTIONS                                               >>>>>>
//<<<<<< CLASS DECLARATIONS                                             >>>>>>

template <class T> class BitOps
{
public:
    // Various math ops

    static T            count (T n);
    static T            reverse (T n);
    static T            rzero (T n);
    static T            log2 (T n);
    static bool         islog2 (T n);
    static T            ceil2 (T n);
    static bool         parity (T n);
    static T            mortonInterleave (T x, T y);
    static void         mortonSplit (T n, T &x, T &y);
    static void         swap (T &x, T &y);

    // Bit extraction from a bit array of words T; requested bits may
    // (4, 5) or may not (2, 3) straddle `T' word boundaries; `count'
    // must be less than BitTraits<T>::Bits; bounded versions return 0
    // if `from > maxbit'; otherwise `from+count' must be less than or
    // equal to `maxbit'.  No attention is paid to word byte order.
    // See also BitIterator.
    static T            extract                 (T n, unsigned int from,
                                                 unsigned int count);

    static T            extractSafe             (const T *restrict p,
                                                 unsigned int from,
                                                 unsigned int count);
    static T            extractUnstraddled      (const T *restrict p,
                                                 unsigned int maxbit,
                                                 unsigned int from,
                                                 unsigned int count);
    // may straddle, except for the last array element
    static T            extractStraddledSafe    (const T *restrict p,
                                                 unsigned int from,
                                                 unsigned int count);
    static T            extract                 (const T *restrict p,
                                                 unsigned int maxbit,
                                                 unsigned int from,
                                                 unsigned int count);
};


template <unsigned int B> struct BitOpsMagic {
    template <class T> struct Type {
        // the binary magic number bit patterns
        enum { Pattern    = BitPattern<T,BitPattern<T,1,1,B>::Pattern,B*2,
                                       BitTraits<T>::Bits/(B*2)>::Pattern };
        enum { RevPattern = ~ Pattern };
    };
};

template <> struct BitOpsMagic<1> {
    template <class T> struct Type {
        enum { Pattern    = BitPattern<T,1,2,BitTraits<T>::Bits/2>::Pattern };
        enum { RevPattern = ~ Pattern };
    };
};

//<<<<<< INLINE PUBLIC FUNCTIONS                                        >>>>>>
//<<<<<< INLINE MEMBER FUNCTIONS                                        >>>>>>


template <class T> inline void
BitOps<T>::swap (T &x, T &y)
{ x ^= y; y ^= x; x ^= y; }


template <unsigned int B> struct BitOpsCount {
    template <class T> struct Op : BitOpsMagic<B>::template Type<T> {
        enum { Pattern = BitOpsMagic<B>::template Type<T>::Pattern };
        static T compute (T n) {
            n = BitOpsCount<B/2>::template Op<T>::compute (n);
            return ((n >> B) & Pattern) + (n & Pattern);
        }
    };
};

template <> struct BitOpsCount<1> {
    template <class T> struct Op : BitOpsMagic<1>::template Type<T> {
        enum { Pattern = BitOpsMagic<1>::template Type<T>::Pattern };
        static T compute (T n)
        { return ((n >> 1) & Pattern) + (n & Pattern); }
    };
};

template <class T> inline T
BitOps<T>::count (T n)
{ return BitOpsCount<BitTraits<T>::Bits/2>::template Op<T>::compute (n); }


template <unsigned int B> struct BitOpsReverse {
    template <class T> struct Op : BitOpsMagic<B>::template Type<T> {
        enum { Pattern = BitOpsMagic<B>::template Type<T>::Pattern };
        enum { RevPattern = BitOpsMagic<B>::template Type<T>::RevPattern };
        static T compute (T n) {
            n = BitOpsReverse<B/2>::template Op<T>::compute (n);
            n = ((n >> B) & Pattern) | ((n << B) & RevPattern);
            return n;
        }
    };
};

template <> struct BitOpsReverse<1> {
    template <class T> struct Op : BitOpsMagic<1>::template Type<T> {
        enum { Pattern = BitOpsMagic<1>::template Type<T>::Pattern };
        enum { RevPattern = BitOpsMagic<1>::template Type<T>::RevPattern };
        static T compute (T n)
        { return ((n >> 1) & Pattern) | ((n << 1) & RevPattern); }
    };
};

template <class T> inline T
BitOps<T>::reverse (T n)
{ return BitOpsReverse<BitTraits<T>::Bits/2>::template Op<T>::compute (n); }


template <unsigned int B> struct BitOpsRZero {
    template <class T> struct Op : BitOpsMagic<B>::template Type<T> {
        enum { Pattern = BitOpsMagic<B>::template Type<T>::Pattern };
        static T compute (T n, unsigned int c) {
            return n & Pattern
                ? BitOpsRZero<B/2>::template Op<T>::compute (n << B, c - B)
                : BitOpsRZero<B/2>::template Op<T>::compute (n, c);
        }
    };
};

template <> struct BitOpsRZero<1> {
    template <class T> struct Op : BitOpsMagic<1>::template Type<T> {
        enum { Pattern = BitOpsMagic<1>::template Type<T>::Pattern };
        static T compute (T n, unsigned int c) {
            if (n & Pattern)
            {
                n <<= 1;
                c--;
            }
            return n ? c-1 : c;
        }
    };
};

template <class T> inline T
BitOps<T>::rzero (T n)
{ return BitOpsRZero<BitTraits<T>::Bits/2>::template Op<T>::compute
      (n, BitTraits<T>::Bits); }


template <unsigned int B> struct BitOpsLog2 {
    template <class T> struct Op : BitOpsMagic<B>::template Type<T> {
        enum { RevPattern = BitOpsMagic<B>::template Type<T>::RevPattern };
        static T compute (T n, unsigned int c) {
            return n & RevPattern
                ? BitOpsLog2<B/2>::template Op<T>::compute (n >> B, c | B)
                : BitOpsLog2<B/2>::template Op<T>::compute (n, c);
        }
    };
};

template <> struct BitOpsLog2<1> {
    template <class T> struct Op : BitOpsMagic<1>::template Type<T> {
        enum { RevPattern = BitOpsMagic<1>::template Type<T>::RevPattern };
        static T compute (T n, unsigned int c)
        { return c | (n & RevPattern ? 1 : 0); }
    };
};

template <class T> inline T
BitOps<T>::log2 (T n)
{ return BitOpsLog2<BitTraits<T>::Bits/2>::template Op<T>::compute (n, 0); }


template <class T> inline bool
BitOps<T>::islog2 (T n)
{ return (n & (n - 1)) == 0; }


template <unsigned int B> struct BitOpsCeil2 {
    template <class T> struct Op : BitOpsMagic<B>::template Type<T> {
        static T compute (T n)
        { n = BitOpsCeil2<B/2>::template Op<T>::compute (n); return n | (n >> B); }
    };
};

template <> struct BitOpsCeil2<1> {
    template <class T> struct Op : BitOpsMagic<1>::template Type<T> {
        static T compute (T n)
        { return n | (n >> 1); }
    };
};

template <class T> inline T
BitOps<T>::ceil2 (T n)
{ return BitOpsCeil2<BitTraits<T>::Bits/2>::template Op<T>::compute (n-1)+1; }


template <unsigned int B> struct BitOpsParity {
    template <class T> struct Op : BitOpsMagic<B>::template Type<T> {
        /* n ^= n >> 16; n ^= n >> 8; n ^= n >> 4; n ^= n >> 2; n ^= n >> 1; */
        static T compute (T n)
        { return BitOpsParity<B/2>::template Op<T>::compute (n ^ (n >> B)); }
    };
};

template <> struct BitOpsParity<1> {
    template <class T> struct Op : BitOpsMagic<1>::template Type<T> {
        static T compute (T n)
        { return n ^ (n >> 1); }
    };
};

template <class T> inline bool
BitOps<T>::parity (T n)
{ return BitOpsParity<BitTraits<T>::Bits/2>::template Op<T>::compute (n) & 1; }


template <unsigned int B> struct BitOpsMortonInterleave {
    template <class T> struct Op : BitOpsMagic<B>::template Type<T> {
        enum { Pattern = BitOpsMagic<B>::template Type<T>::Pattern };
        static T compute (T n)
        { return BitOpsMortonInterleave<B/2>::template Op<T>::compute ((n | (n << B)) & Pattern); }
    };
};

template <> struct BitOpsMortonInterleave<1> {
    template <class T> struct Op : BitOpsMagic<1>::template Type<T> {
        enum { Pattern = BitOpsMagic<1>::template Type<T>::Pattern };
        static T compute (T n)
        { return (n | (n << 1)) & Pattern; }
    };
};

template <unsigned int B> struct BitOpsMortonExtract {
    template <class T> struct Op : BitOpsMagic<B>::template Type<T> {
        enum { Pattern = BitOpsMagic<B>::template Type<T>::Pattern };
        static T compute (T n) {
            n = BitOpsMortonExtract<B/2>::template Op<T>::compute (n) & Pattern;
            return n | (n >> B);
        }
    };
};

template <> struct BitOpsMortonExtract<1> {
    template <class T> struct Op : BitOpsMagic<1>::template Type<T> {
        enum { Pattern = BitOpsMagic<1>::template Type<T>::Pattern };
        static T compute (T n)
        { n &= Pattern; return n | (n >> 1); }
    };
};

template <class T> inline T
BitOps<T>::mortonInterleave (T x, T y)
{ return BitOpsMortonInterleave<BitTraits<T>::Bits/4>::template Op<T>::compute (x)
      | (BitOpsMortonInterleave<BitTraits<T>::Bits/4>::template Op<T>::compute (y) << 1); }

template <class T> inline void
BitOps<T>::mortonSplit (T n, T &x, T &y)
{
    x = BitOpsMortonExtract<BitTraits<T>::Bits/4>::template Op<T>::compute (n);
    y = BitOpsMortonExtract<BitTraits<T>::Bits/4>::template Op<T>::compute (n >> 1);
}


template <class T> inline T
BitOps<T>::extract (T n, unsigned int from, unsigned int count)
{
    enum { AllOnes = BitPattern<T,0xff,8,BitTraits<T>::Bytes>::Pattern };
    return (n >> (BitTraits<T>::Bits - from - count)) & ~(AllOnes << count);
}

template <class T> inline T
BitOps<T>::extractSafe (const T *restrict p, unsigned int from,
                         unsigned int count)
{
    return extract (* (p + from/BitTraits<T>::Bits),
                    from % BitTraits<T>::Bits,
                    count);
}

template <class T> inline T
BitOps<T>::extractUnstraddled (const T *restrict p, unsigned int maxbit,
                               unsigned int from, unsigned int count)
{ return from > maxbit ? 0 : extractSafe (p, from, count); }

template <class T> inline T
BitOps<T>::extractStraddledSafe (const T *restrict p, unsigned int from,
                                 unsigned int count)
{
    unsigned int count_word_1 = std::min(count,
                                         BitTraits<T>::Bits
                                         - from % BitTraits<T>::Bits);
    unsigned int count_word_2 = count - count_word_1;

    return (extractSafe (p, from, count_word_1) << count_word_2
            | extractSafe (p, from+count_word_1, count_word_2));
}

template <class T> inline T
BitOps<T>::extract (const T *restrict p, unsigned int maxbit,
                    unsigned int from, unsigned int count)
{ return from > maxbit ? 0 : extractStraddledSafe (p, from, count); }

} // namespace lat
#endif // CLASSLIB_BIT_OPS_H

---