bitrange.h

/*
Copyright 2013-present Barefoot Networks, Inc.
 
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
 
    http://www.apache.org/licenses/LICENSE-2.0
 
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
 
#ifndef LIB_BITRANGE_H_
#define LIB_BITRANGE_H_
 
#include <algorithm>
#include <iosfwd>
#include <limits>
#include <optional>
#include <utility>
 
#include "absl/numeric/bits.h"
#include "bitvec.h"
#include "exceptions.h"
#include "hash.h"
 
/* iterate over ranges of contiguous bits in a bitvector */
class bitranges {
    bitvec tmp;
    const bitvec &bits;
    struct iter {
        bool valid = true;
        bitvec::const_bitref ptr;
        std::pair<int, int> range;
 
        iter &operator++() {
            if (ptr) {
                range.first = range.second = ptr.index();
                while (++ptr && range.second + 1 == ptr.index()) ++range.second;
            } else {
                valid = false;
            }
            return *this;
        }
        std::pair<int, int> operator*() { return range; }
        bool operator==(iter &a) const { return valid == a.valid && ptr == a.ptr; }
        bool operator!=(iter &a) const { return !(*this == a); }
        explicit iter(bitvec::const_bitref p) : ptr(p) { ++*this; }
    };
 
 public:
    explicit bitranges(const bitvec &b) : bits(b) {}
    explicit bitranges(bitvec &&b) : tmp(b), bits(tmp) {}
    explicit bitranges(uintptr_t b) : tmp(b), bits(tmp) {}
    iter begin() const { return iter(bits.begin()); }
    iter end() const { return iter(bits.end()); }
};
 
class JSONGenerator;
class JSONLoader;
 
namespace BitRange {
 
namespace Detail {
constexpr inline int divideFloor(int dividend, int divisor) {
#if defined(__GNUC__) || defined(__clang__)
    // Code to enable compiler folding when the divisor is a power-of-two compile-time constant
    // In this case, compiler should fold to a right-shift
    // FIXME: Replace absl with std after moving to C++20
    unsigned u_divisor = static_cast<unsigned>(divisor);
    if (__builtin_constant_p(u_divisor) && absl::has_single_bit(u_divisor))
        return dividend >> (absl::bit_width(u_divisor) - 1);
#endif  // defined(__GNUC__) || defined(__clang__)
 
    const int quotient = dividend / divisor;
    const int remainder = dividend % divisor;
    if ((remainder != 0) && ((remainder < 0) != (divisor < 0))) return quotient - 1;
    return quotient;
}
 
constexpr int modulo(int dividend, int divisor) {
    return (dividend % divisor) * ((dividend < 0) != (divisor < 0) ? -1 : 1);
}
 
constexpr inline int moduloFloor(const int dividend, const int divisor) {
#if defined(__GNUC__) || defined(__clang__)
    // Code to enable compiler folding when the divisor is a power-of-two compile-time constant
    // In this case, compiler should fold to a bitwise-and
    // FIXME: Replace absl with std after moving to C++20
    if (__builtin_constant_p(divisor) && absl::has_single_bit(static_cast<unsigned>(divisor)))
        return dividend & (divisor - 1);
#endif  // defined(__GNUC__) || defined(__clang__)
 
    const int remainder = modulo(dividend, divisor);
    if (remainder == 0 || dividend >= 0) return remainder;
    return divisor - remainder;
}
}  // namespace Detail
 
struct FromTo {
    FromTo(int from, int to) : from(from), to(to) {}
    FromTo(const FromTo &) = delete;
    FromTo &operator=(const FromTo &) = delete;
    const int from;
    const int to;
};
 
struct StartLen {
    StartLen(int start, int len) : start(start), len(len) {}
    StartLen(const StartLen &) = delete;
    StartLen &operator=(const StartLen &) = delete;
    const int start;
    const int len;
};
 
struct ZeroToMax {};
 
struct MinToMax {};
 
void rangeToJSON(JSONGenerator &json, int lo, int hi);
std::pair<int, int> rangeFromJSON(JSONLoader &json);
 
}  // namespace BitRange
 
enum class RangeUnit : uint8_t {
    Bit = 0,
    Byte = 1  
};
 
enum class Endian : uint8_t {
    Network = 0,  
    Little = 1,   
};
 
template <RangeUnit Unit, Endian Order>
struct HalfOpenRange {
    static constexpr RangeUnit unit = Unit;
    static constexpr Endian order = Order;
 
    using FromTo = BitRange::FromTo;
    using StartLen = BitRange::StartLen;
    using ZeroToMax = BitRange::ZeroToMax;
    using MinToMax = BitRange::MinToMax;
 
    HalfOpenRange() : lo(0), hi(0) {}
    HalfOpenRange(int lo, int hi) : lo(lo), hi(hi) {}
    HalfOpenRange(FromTo &&fromTo)  // NOLINT(runtime/explicit)
        : lo(fromTo.from), hi(fromTo.to + 1) {}
    HalfOpenRange(StartLen &&startLen)  // NOLINT(runtime/explicit)
        : lo(startLen.start), hi(startLen.start + startLen.len) {}
    HalfOpenRange(ZeroToMax &&)  // NOLINT(runtime/explicit)
        : lo(0), hi(std::numeric_limits<int>::max()) {}
    HalfOpenRange(MinToMax &&)  // NOLINT(runtime/explicit)
        : lo(std::numeric_limits<int>::min()), hi(std::numeric_limits<int>::max()) {}
    explicit HalfOpenRange(std::pair<int, int> range) : lo(range.first), hi(range.second) {}
 
    ssize_t size() const { return ssize_t(hi) - ssize_t(lo); }
 
    HalfOpenRange canonicalize() const {
        if (empty()) return HalfOpenRange(0, 0);
        return *this;
    }
 
    HalfOpenRange<RangeUnit::Bit, Order> resizedToBits(int size) const {
        if (empty()) return HalfOpenRange<RangeUnit::Bit, Order>(0, size);
        auto asBits = toUnit<RangeUnit::Bit>();
        return {asBits.lo, asBits.lo + size};
    }
 
    HalfOpenRange resizedToBytes(int size) const {
        const int resizedLo = empty() ? 0 : lo;
        if (Unit == RangeUnit::Byte) return {resizedLo, resizedLo + size};
        return {resizedLo, resizedLo + size * 8};
    }
 
    HalfOpenRange<RangeUnit::Bit, Order> shiftedByBits(int offset) const {
        if (empty()) return HalfOpenRange<RangeUnit::Bit, Order>();
        auto asBits = toUnit<RangeUnit::Bit>();
        return {asBits.lo + offset, asBits.hi + offset};
    }
 
    HalfOpenRange<Unit, Order> shiftedByBytes(int offset) const {
        if (empty()) return HalfOpenRange();
        if (Unit == RangeUnit::Byte) return {lo + offset, hi + offset};
        return {lo + offset * 8, hi + offset * 8};
    }
 
    int loByte() const {
        if (empty()) return 0;
        return Unit == RangeUnit::Byte ? lo : BitRange::Detail::divideFloor(lo, 8);
    }
 
    int hiByte() const {
        if (empty()) return 0;
        return Unit == RangeUnit::Byte ? hi - 1 : BitRange::Detail::divideFloor(hi - 1, 8);
    }
 
    int nextByte() const { return empty() ? 0 : hiByte() + 1; }
 
    bool isLoAligned() const {
        return (empty() || Unit == RangeUnit::Byte) ? true
                                                    : BitRange::Detail::moduloFloor(lo, 8) == 0;
    }
 
    bool isHiAligned() const {
        return (empty() || Unit == RangeUnit::Byte) ? true
                                                    : BitRange::Detail::moduloFloor(hi, 8) == 0;
    }
 
    bool operator==(HalfOpenRange other) const {
        if (empty()) return other.empty();
        return other.lo == lo && other.hi == hi;
    }
    bool operator!=(HalfOpenRange other) const { return !(*this == other); }
 
    bool empty() const { return lo == hi; }
 
    bool contains(int index) const { return index >= lo && index < hi; }
 
    bool contains(HalfOpenRange other) const { return intersectWith(other) == other; }
 
    bool overlaps(HalfOpenRange a) const { return !intersectWith(a).empty(); }
    bool overlaps(int l, int h) const { return !intersectWith(l, h).empty(); }
 
    HalfOpenRange intersectWith(HalfOpenRange a) const { return intersectWith(a.lo, a.hi); }
    HalfOpenRange intersectWith(int l, int h) const {
        HalfOpenRange rv = {std::max(lo, l), std::min(hi, h)};
        if (rv.hi <= rv.lo) return {0, 0};
        return rv;
    }
    HalfOpenRange operator&(HalfOpenRange a) const { return intersectWith(a); }
    HalfOpenRange operator&=(HalfOpenRange a) {
        *this = intersectWith(a);
        return *this;
    }
 
    HalfOpenRange unionWith(HalfOpenRange a) const { return unionWith(a.lo, a.hi); }
    HalfOpenRange unionWith(int l, int h) const {
        if (empty()) return {l, h};
        if (l == h) return *this;
        return HalfOpenRange(std::min(lo, l), std::max(hi, h));
    }
    HalfOpenRange operator|(HalfOpenRange a) const { return unionWith(a); }
    HalfOpenRange operator|=(HalfOpenRange a) {
        *this = unionWith(a);
        return *this;
    }
 
    template <Endian DestOrder>
    HalfOpenRange<Unit, DestOrder> toOrder(int spaceSize) const {
        if (DestOrder == Order) return HalfOpenRange<Unit, DestOrder>(lo, hi);
        switch (DestOrder) {
            case Endian::Network:
            case Endian::Little:
                return HalfOpenRange<Unit, DestOrder>(spaceSize - hi, spaceSize - lo);
        }
        BUG("Unexpected ordering");
    }
 
    template <RangeUnit DestUnit>
    HalfOpenRange<DestUnit, Order> toUnit() const {
        if (DestUnit == Unit) return HalfOpenRange<DestUnit, Order>(lo, hi);
        if (empty()) return HalfOpenRange<DestUnit, Order>();
        switch (DestUnit) {
            case RangeUnit::Bit:
                return HalfOpenRange<DestUnit, Order>(lo * 8, hi * 8);
            case RangeUnit::Byte:
                return HalfOpenRange<DestUnit, Order>(loByte(), nextByte());
        }
        BUG("Unexpected unit");
    }
 
    void toJSON(JSONGenerator &json) const { BitRange::rangeToJSON(json, lo, hi); }
    static HalfOpenRange fromJSON(JSONLoader &json) {
        return HalfOpenRange(BitRange::rangeFromJSON(json));
    }
 
    bool operator<(const HalfOpenRange &other) const {
        if (lo != other.lo) return lo < other.lo;
        return hi < other.hi;
    }
 
    friend size_t hash_value(const HalfOpenRange &r) { return Util::Hash{}(r.lo, r.hi); }
 
    int lo;
 
    int hi;
};
 
template <RangeUnit Unit, Endian Order>
struct ClosedRange {
    static constexpr RangeUnit unit = Unit;
    static constexpr Endian order = Order;
 
    using FromTo = BitRange::FromTo;
    using StartLen = BitRange::StartLen;
    using ZeroToMax = BitRange::ZeroToMax;
    using MinToMax = BitRange::MinToMax;
 
    ClosedRange() : lo(0), hi(0) {}  // FIXME: default is [0,0]? This is just wrong ...
    constexpr ClosedRange(int lo, int hi) : lo(lo), hi(hi) {}
    ClosedRange(FromTo &&fromTo)  // NOLINT(runtime/explicit)
        : lo(fromTo.from), hi(fromTo.to) {}
    ClosedRange(StartLen &&startLen)  // NOLINT(runtime/explicit)
        : lo(startLen.start), hi(startLen.start + startLen.len - 1) {}
    ClosedRange(ZeroToMax &&)  // NOLINT(runtime/explicit)
        : lo(0), hi(std::numeric_limits<int>::max() - 1) {}
    ClosedRange(MinToMax &&)  // NOLINT(runtime/explicit)
        : lo(std::numeric_limits<int>::min()), hi(std::numeric_limits<int>::max() - 1) {}
    explicit ClosedRange(std::pair<int, int> range) : lo(range.first), hi(range.second) {}
    ClosedRange(const HalfOpenRange<Unit, Order> &r)  // NOLINT(runtime/explicit)
        : lo(r.lo), hi(r.hi - 1) {
        BUG_CHECK(!r.empty(), "can't convert empty range to Closed");
    }
 
    ssize_t size() const { return ssize_t(hi) - ssize_t(lo) + 1; }
 
    ClosedRange<RangeUnit::Bit, Order> resizedToBits(int size) const {
        BUG_CHECK(size != 0, "Resizing ClosedRange to zero size");
        auto asBits = toUnit<RangeUnit::Bit>();
        return {asBits.lo, asBits.lo + size - 1};
    }
 
    ClosedRange resizedToBytes(int size) const {
        BUG_CHECK(size != 0, "Resizing ClosedRange to zero size");
        if (Unit == RangeUnit::Byte) return {lo, lo + size - 1};
        return {lo, lo + size * 8 - 1};
    }
 
    ClosedRange<RangeUnit::Bit, Order> shiftedByBits(int offset) const {
        auto asBits = toUnit<RangeUnit::Bit>();
        return {asBits.lo + offset, asBits.hi + offset};
    }
 
    ClosedRange shiftedByBytes(int offset) const {
        if (Unit == RangeUnit::Byte) return {lo + offset, hi + offset};
        return {lo + offset * 8, hi + offset * 8};
    }
 
    int loByte() const {
        return Unit == RangeUnit::Byte ? lo : BitRange::Detail::divideFloor(lo, 8);
    }
 
    int hiByte() const {
        return Unit == RangeUnit::Byte ? hi : BitRange::Detail::divideFloor(hi, 8);
    }
 
    int nextByte() const { return hiByte() + 1; }
 
    bool isLoAligned() const {
        return Unit == RangeUnit::Byte ? true : BitRange::Detail::moduloFloor(lo, 8) == 0;
    }
 
    bool isHiAligned() const {
        return Unit == RangeUnit::Byte ? true : BitRange::Detail::moduloFloor(hi + 1, 8) == 0;
    }
 
    bool operator==(ClosedRange other) const { return (other.lo == lo) && (other.hi == hi); }
    bool operator!=(ClosedRange other) const { return !(*this == other); }
 
    bool contains(int index) const { return (index >= lo) && (index <= hi); }
 
    bool contains(ClosedRange other) const {
        auto intersection = intersectWith(other);
        return intersection.lo == other.lo && intersection.size() == other.size();
    }
 
    bool overlaps(ClosedRange a) const { return !intersectWith(a).empty(); }
    bool overlaps(int l, int h) const { return !intersectWith(l, h).empty(); }
 
    HalfOpenRange<Unit, Order> intersectWith(ClosedRange a) const {
        return intersectWith(a.lo, a.hi);
    }
    HalfOpenRange<Unit, Order> intersectWith(int l, int h) const {
        return HalfOpenRange<Unit, Order>(lo, hi + 1)
            .intersectWith(HalfOpenRange<Unit, Order>(l, h + 1));
    }
    HalfOpenRange<Unit, Order> operator&(ClosedRange a) const { return intersectWith(a); }
    HalfOpenRange<Unit, Order> operator&=(ClosedRange a) {
        *this = intersectWith(a);
        return *this;
    }
 
    ClosedRange unionWith(ClosedRange a) const { return unionWith(a.lo, a.hi); }
    ClosedRange unionWith(int l, int h) const {
        return ClosedRange(std::min(lo, l), std::max(hi, h));
    }
    ClosedRange operator|(ClosedRange a) const { return unionWith(a); }
    ClosedRange operator|=(ClosedRange a) {
        *this = unionWith(a);
        return *this;
    }
 
    template <Endian DestOrder>
    ClosedRange<Unit, DestOrder> toOrder(int spaceSize) const {
        BUG_CHECK(spaceSize > 0, "Can't represent an empty range");
        if (DestOrder == Order) return ClosedRange<Unit, DestOrder>(lo, hi);
        switch (DestOrder) {
            case Endian::Network:
            case Endian::Little:
                return ClosedRange<Unit, DestOrder>((spaceSize - 1) - hi, (spaceSize - 1) - lo);
        }
        BUG("Unexpected ordering");
    }
 
    template <RangeUnit DestUnit>
    ClosedRange<DestUnit, Order> toUnit() const {
        if (DestUnit == Unit) return ClosedRange<DestUnit, Order>(lo, hi);
        switch (DestUnit) {
            case RangeUnit::Bit:
                return ClosedRange<DestUnit, Order>(lo * 8, hi * 8 + 7);
            case RangeUnit::Byte:
                return ClosedRange<DestUnit, Order>(loByte(), hiByte());
        }
        BUG("Unexpected unit");
    }
 
    void toJSON(JSONGenerator &json) const { BitRange::rangeToJSON(json, lo, hi); }
    static ClosedRange fromJSON(JSONLoader &json) {
        return ClosedRange(BitRange::rangeFromJSON(json));
    }
 
    bool operator<(const ClosedRange &other) const {
        if (lo != other.lo) return lo < other.lo;
        return hi < other.hi;
    }
 
    friend size_t hash_value(const ClosedRange &r) { return Util::Hash{}(r.lo, r.hi); }
 
    cstring formatAsSlice(int spaceSize) const {
        auto r = toOrder<Endian::Little>(spaceSize);
        auto hi = r.hi;
        auto lo = r.lo;
        if (Unit == RangeUnit::Byte) {
            lo = lo * 8;
            hi = hi * 8 + 7;
        } else {
            BUG_CHECK(Unit == RangeUnit::Bit, "mismatch range units");
        }
        std::stringstream out;
        out << "[" << hi << ":" << lo << "]";
        return cstring(out.str());
    }
 
    int lo;
 
    int hi;
};
 
template <RangeUnit Unit, Endian Order>
std::pair<HalfOpenRange<Unit, Order>, HalfOpenRange<Unit, Order>> operator-(
    HalfOpenRange<Unit, Order> left, HalfOpenRange<Unit, Order> right) {
    HalfOpenRange<Unit, Order> empty = {0, 0};
    HalfOpenRange<Unit, Order> intersect = left.intersectWith(right);
    if (intersect.empty())
        return left.lo < right.lo ? std::make_pair(left, empty) : std::make_pair(empty, left);
 
    HalfOpenRange<Unit, Order> lower =
        left.lo == intersect.lo ? empty : BitRange::FromTo(left.lo, intersect.lo - 1);
    HalfOpenRange<Unit, Order> upper =
        left.hi == intersect.hi ? empty : BitRange::FromTo(intersect.hi, left.hi - 1);
 
    return {lower, upper};
}
 
template <RangeUnit Unit, Endian Order>
std::pair<HalfOpenRange<Unit, Order>, HalfOpenRange<Unit, Order>> operator-(
    ClosedRange<Unit, Order> left, ClosedRange<Unit, Order> right) {
    return toHalfOpenRange(left) - toHalfOpenRange(right);
}
 
template <RangeUnit Unit, Endian Order>
HalfOpenRange<Unit, Order> toHalfOpenRange(ClosedRange<Unit, Order> closedRange) {
    return HalfOpenRange<Unit, Order>(closedRange.lo, closedRange.hi + 1);
}
 
template <RangeUnit Unit, Endian Order>
std::optional<ClosedRange<Unit, Order>> toClosedRange(HalfOpenRange<Unit, Order> halfOpenRange) {
    if (halfOpenRange.empty()) return std::nullopt;
    return ClosedRange<Unit, Order>(halfOpenRange.lo, halfOpenRange.hi - 1);
}
 
using nw_bitrange = ClosedRange<RangeUnit::Bit, Endian::Network>;
using le_bitrange = ClosedRange<RangeUnit::Bit, Endian::Little>;
 
using nw_byterange = ClosedRange<RangeUnit::Byte, Endian::Network>;
using le_byterange = ClosedRange<RangeUnit::Byte, Endian::Little>;
 
using nw_bitinterval = HalfOpenRange<RangeUnit::Bit, Endian::Network>;
using le_bitinterval = HalfOpenRange<RangeUnit::Bit, Endian::Little>;
 
using nw_byteinterval = HalfOpenRange<RangeUnit::Byte, Endian::Network>;
using le_byteinterval = HalfOpenRange<RangeUnit::Byte, Endian::Little>;
 
std::ostream &toStream(std::ostream &out, RangeUnit unit, Endian order, int lo, int hi,
                       bool closed);
 
template <RangeUnit Unit, Endian Order>
std::ostream &operator<<(std::ostream &out, const HalfOpenRange<Unit, Order> &range) {
    return toStream(out, Unit, Order, range.lo, range.hi, false);
}
 
template <RangeUnit Unit, Endian Order>
std::ostream &operator<<(std::ostream &out, const ClosedRange<Unit, Order> &range) {
    return toStream(out, Unit, Order, range.lo, range.hi, true);
}
 
// Hashing specializations
namespace std {
template <RangeUnit Unit, Endian Order>
struct hash<HalfOpenRange<Unit, Order>> {
    std::size_t operator()(const HalfOpenRange<Unit, Order> &r) const {
        return Util::Hash{}(r.lo, r.hi);
    }
};
 
template <RangeUnit Unit, Endian Order>
struct hash<ClosedRange<Unit, Order>> {
    std::size_t operator()(const ClosedRange<Unit, Order> &r) const {
        return Util::Hash{}(r.lo, r.hi);
    }
};
}  // namespace std
 
namespace Util {
template <RangeUnit Unit, Endian Order>
struct Hasher<HalfOpenRange<Unit, Order>> {
    size_t operator()(const HalfOpenRange<Unit, Order> &r) const {
        return Util::Hash{}(r.lo, r.hi);
    }
};
 
template <RangeUnit Unit, Endian Order>
struct Hasher<ClosedRange<Unit, Order>> {
    size_t operator()(const ClosedRange<Unit, Order> &r) const { return Util::Hash{}(r.lo, r.hi); }
};
}  // namespace Util
 
#endif /* LIB_BITRANGE_H_ */