Intervals.h

Go to the documentation of this file.

//===-- Intervals.h ---------------------------------------------*- C++ -*-===//
//
// Part of the LLZK Project, under the Apache License v2.0.
// See LICENSE.txt for license information.
// Copyright 2025 Veridise Inc.
// SPDX-License-Identifier: Apache-2.0
//
//===----------------------------------------------------------------------===//
 
#pragma once
 
#include "llzk/Util/Field.h"
 
#include <mlir/Support/LogicalResult.h>
 
#include <algorithm>
 
namespace llzk {
 
/* UnreducedInterval */
 
class Interval;

class UnreducedInterval {
public:
  UnreducedInterval(const llvm::DynamicAPInt &x, const llvm::DynamicAPInt &y) : a(x), b(y) {}
  UnreducedInterval(int64_t x, int64_t y) : a(x), b(y) {}
 
  /* Operations */

  Interval reduce(const Field &field) const;

  UnreducedInterval intersect(const UnreducedInterval &rhs) const;

  UnreducedInterval doUnion(const UnreducedInterval &rhs) const;

  UnreducedInterval computeLTPart(const UnreducedInterval &rhs) const;

  UnreducedInterval computeLEPart(const UnreducedInterval &rhs) const;

  UnreducedInterval computeGTPart(const UnreducedInterval &rhs) const;

  UnreducedInterval computeGEPart(const UnreducedInterval &rhs) const;
 
  UnreducedInterval operator-() const;
  friend UnreducedInterval operator+(const UnreducedInterval &lhs, const UnreducedInterval &rhs);
  friend UnreducedInterval operator-(const UnreducedInterval &lhs, const UnreducedInterval &rhs);
  friend UnreducedInterval operator*(const UnreducedInterval &lhs, const UnreducedInterval &rhs);
 
  /* Comparisons */
 
  bool overlaps(const UnreducedInterval &rhs) const;
 
  friend std::strong_ordering
  operator<=>(const UnreducedInterval &lhs, const UnreducedInterval &rhs);
 
  friend bool operator==(const UnreducedInterval &lhs, const UnreducedInterval &rhs) {
    return std::is_eq(lhs <=> rhs);
  };
 
  /* Utility for hashing unreduced intervals */
  struct Hash {
    unsigned operator()(const UnreducedInterval &ui) const {
      return llvm::hash_value(ui.a) ^ llvm::hash_value(ui.b);
    }
  };
 
  llvm::DynamicAPInt getLHS() const { return a; }
  llvm::DynamicAPInt getRHS() const { return b; }

  llvm::DynamicAPInt width() const;

  inline bool isEmpty() const { return width() == 0; }
 
  bool isNotEmpty() const { return !isEmpty(); }
 
  void print(llvm::raw_ostream &os) const { os << "Unreduced:[ " << a << ", " << b << " ]"; }
 
  friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const UnreducedInterval &ui) {
    ui.print(os);
    return os;
  }
 
private:
  llvm::DynamicAPInt a, b;
};
 
/* Interval */

class Interval {
public:
  enum class Type : std::uint8_t { TypeA = 0, TypeB, TypeC, TypeF, Empty, Degenerate, Entire };
  static constexpr std::array<std::string_view, 7> TypeNames = {"TypeA", "TypeB", "TypeC",
                                                                "TypeF", "Empty", "Degenerate",
                                                                "Entire"};
 
  static std::string_view TypeName(Type t) { return TypeNames.at(static_cast<size_t>(t)); }
 
  /* Static constructors for convenience */
 
  static Interval Empty(const Field &f) { return Interval(Type::Empty, f); }
 
  static Interval Degenerate(const Field &f, const llvm::DynamicAPInt &val) {
    return Interval(Type::Degenerate, f, val, val);
  }
 
  static Interval False(const Field &f) { return Interval::Degenerate(f, f.zero()); }
 
  static Interval True(const Field &f) { return Interval::Degenerate(f, f.one()); }
 
  static Interval Boolean(const Field &f) { return Interval::TypeA(f, f.zero(), f.one()); }
 
  static Interval Entire(const Field &f) { return Interval(Type::Entire, f); }
 
  static Interval TypeA(const Field &f, const llvm::DynamicAPInt &a, const llvm::DynamicAPInt &b) {
    return Interval(Type::TypeA, f, a, b);
  }
 
  static Interval TypeB(const Field &f, const llvm::DynamicAPInt &a, const llvm::DynamicAPInt &b) {
    return Interval(Type::TypeB, f, a, b);
  }
 
  static Interval TypeC(const Field &f, const llvm::DynamicAPInt &a, const llvm::DynamicAPInt &b) {
    return Interval(Type::TypeC, f, a, b);
  }
 
  static Interval TypeF(const Field &f, const llvm::DynamicAPInt &a, const llvm::DynamicAPInt &b) {
    return Interval(Type::TypeF, f, a, b);
  }

  Interval() : Interval(Type::Entire, Field::getField("bn128")) {}

  UnreducedInterval toUnreduced() const;

  UnreducedInterval firstUnreduced() const;

  UnreducedInterval secondUnreduced() const;
 
  template <std::pair<Type, Type>... Pairs>
  static bool areOneOf(const Interval &a, const Interval &b) {
    return ((a.ty == std::get<0>(Pairs) && b.ty == std::get<1>(Pairs)) || ...);
  }

  Interval join(const Interval &rhs) const;

  Interval intersect(const Interval &rhs) const;

  Interval difference(const Interval &other) const;
 
  /* arithmetic ops */
 
  Interval operator-() const;
  Interval operator~() const;
  friend Interval operator+(const Interval &lhs, const Interval &rhs);
  friend Interval operator-(const Interval &lhs, const Interval &rhs);
  friend Interval operator*(const Interval &lhs, const Interval &rhs);
  friend Interval operator%(const Interval &lhs, const Interval &rhs);
  friend Interval operator&(const Interval &lhs, const Interval &rhs);
  friend Interval operator|(const Interval &lhs, const Interval &rhs);
  friend Interval operator^(const Interval &lhs, const Interval &rhs);
  friend Interval operator<<(const Interval &lhs, const Interval &rhs);
  friend Interval operator>>(const Interval &lhs, const Interval &rhs);
 
  /* boolean ops */
  friend Interval boolAnd(const Interval &lhs, const Interval &rhs);
  friend Interval boolOr(const Interval &lhs, const Interval &rhs);
  friend Interval boolXor(const Interval &lhs, const Interval &rhs);
  friend Interval boolNot(const Interval &iv);
 
  /* Checks and Comparisons */
 
  inline bool isEmpty() const { return ty == Type::Empty; }
  inline bool isNotEmpty() const { return !isEmpty(); }
  inline bool isDegenerate() const { return ty == Type::Degenerate; }
  inline bool isEntire() const { return ty == Type::Entire; }
  inline bool isTypeA() const { return ty == Type::TypeA; }
  inline bool isTypeB() const { return ty == Type::TypeB; }
  inline bool isTypeC() const { return ty == Type::TypeC; }
  inline bool isTypeF() const { return ty == Type::TypeF; }
 
  inline bool isBoolFalse() const { return *this == Interval::False(field.get()); }
  inline bool isBoolTrue() const { return *this == Interval::True(field.get()); }
  inline bool isBoolEither() const { return *this == Interval::Boolean(field.get()); }
  inline bool isBoolean() const { return isBoolFalse() || isBoolTrue() || isBoolEither(); }
 
  template <Type... Types> bool is() const { return ((ty == Types) || ...); }
 
  bool operator==(const Interval &rhs) const { return ty == rhs.ty && a == rhs.a && b == rhs.b; }
 
  /* Getters */
 
  const Field &getField() const { return field.get(); }
 
  llvm::DynamicAPInt width() const;
 
  llvm::DynamicAPInt lhs() const { return a; }
  llvm::DynamicAPInt rhs() const { return b; }
 
  /* Utility */
  struct Hash {
    unsigned operator()(const Interval &i) const {
      return std::hash<const Field *> {}(&i.field.get()) ^ std::hash<Type> {}(i.ty) ^
             llvm::hash_value(i.a) ^ llvm::hash_value(i.b);
    }
  };
 
  void print(llvm::raw_ostream &os) const;
 
  friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const Interval &i) {
    i.print(os);
    return os;
  }
 
private:
  Interval(Type t, const Field &f) : field(f), ty(t), a(f.zero()), b(f.zero()) {}
  Interval(Type t, const Field &f, const llvm::DynamicAPInt &lhs, const llvm::DynamicAPInt &rhs)
      : field(f), ty(t), a(f.reduce(lhs)), b(f.reduce(rhs)) {}
 
  std::reference_wrapper<const Field> field;
  Type ty;
  llvm::DynamicAPInt a, b;
};

mlir::FailureOr<Interval> feltDiv(const Interval &lhs, const Interval &rhs);

mlir::FailureOr<Interval> unsignedIntDiv(const Interval &lhs, const Interval &rhs);

mlir::FailureOr<Interval> signedIntDiv(const Interval &lhs, const Interval &rhs);

Interval signedMod(const Interval &lhs, const Interval &rhs);
 
} // namespace llzk