rank_64bit.hpp

Go to the documentation of this file.

#pragma once

#include <cstdint>
#include <tudocomp/util.hpp>

namespace tdc {

    constexpr uint8_t rank1_8bit[] = {
        0, 1, 1, 2, 1, 2, 2, 3,
        1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4,
        2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4,
        2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5,
        3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4,
        2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5,
        3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5,
        3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6,
        4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4,
        2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5,
        3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5,
        3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6,
        4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5,
        3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6,
        4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6,
        4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7,
        5, 6, 6, 7, 6, 7, 7, 8
    };

    inline constexpr uint8_t rank1(uint8_t v) {
        return rank1_8bit[v];
    }

    inline constexpr uint8_t rank1(uint16_t v) {
        return __builtin_popcount(v);
    }

    inline constexpr uint8_t rank1(uint32_t v) {
        return __builtin_popcount(v);
    }

    inline constexpr uint8_t rank1(uint64_t v) {
        return __builtin_popcountll(v);
    }

    template<typename uint_t>
    inline constexpr uint8_t rank1(uint_t v, uint8_t m) {
        DCHECK(m <= msbf<uint_t>::pos) << "m=" << m;
        const uint_t mask =
            std::numeric_limits<uint_t>::max() >> (msbf<uint_t>::pos-m);
        return rank1(uint_t(v & mask));
    }

    template<typename uint_t>
    inline constexpr uint8_t rank1(uint_t v, uint8_t l, uint8_t m) {
        DCHECK(l <= msbf<uint_t>::pos &&
               m <= msbf<uint_t>::pos &&
               l <= m) << "l=" << l << ",m=" << m;

        const uint_t mask_m =
            std::numeric_limits<uint_t>::max() >> (msbf<uint_t>::pos-m);
        const uint_t mask_l =
            std::numeric_limits<uint_t>::max() << l;
        return rank1(uint_t(v & mask_m & mask_l));
    }

    template<typename uint_t>
    inline constexpr uint8_t rank0(uint_t v) {
        return msbf<uint_t>::pos + 1 - rank1(v);
    }

    template<typename uint_t>
    inline constexpr uint8_t rank0(uint_t v, uint8_t m) {
        return (m + 1) - rank1(v, m);
    }

    template<typename uint_t>
    inline constexpr uint8_t rank0(uint_t v, uint8_t l, uint8_t m) {
        return (m - l + 1) - rank1(v, l, m);
    }

} //ns