lib/bitrange.h

/*
 * SPDX-FileCopyrightText: 2013 Barefoot Networks, Inc.
 * Copyright 2013-present Barefoot Networks, Inc.
 *
 * SPDX-License-Identifier: Apache-2.0
 */
 
#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"
 
namespace P4 {
 
/* 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);
}
 
}  // namespace P4
 
// Hashing specializations
namespace std {
template <P4::RangeUnit Unit, P4::Endian Order>
struct hash<P4::HalfOpenRange<Unit, Order>> {
    std::size_t operator()(const P4::HalfOpenRange<Unit, Order> &r) const {
        return P4::Util::Hash{}(r.lo, r.hi);
    }
};
 
template <P4::RangeUnit Unit, P4::Endian Order>
struct hash<P4::ClosedRange<Unit, Order>> {
    std::size_t operator()(const P4::ClosedRange<Unit, Order> &r) const {
        return P4::Util::Hash{}(r.lo, r.hi);
    }
};
}  // namespace std
 
namespace P4::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 P4::Util
 
#endif /* LIB_BITRANGE_H_ */