#ifndef SLEELA_UNSIGNED_INTEGER_H #define SLEELA_UNSIGNED_INTEGER_H #include #include #include #include #include #include #include namespace sleela { /* * Width-parameterized unsigned integer value foundation for compiler/runtime integration. * Bytes are little-endian. Every value is normalized to exactly ceil(width/8) * bytes and unused high bits are always cleared. */ class UnsignedInteger { public: static constexpr std::size_t kMaximumWidth = 1048576; static bool isValidTypeName(const std::string& name) noexcept { if (name.size() < 2 || name[0] != 'U' || (name.size() > 2 && name[1] == '0')) return false; std::size_t width = 0; for (std::size_t i = 1; i < name.size(); ++i) { if (name[i] < '0' || name[i] > '9') return false; const unsigned digit = static_cast(name[i] - '0'); if (width > 104857 || (width == 104857 && digit > 6)) return false; width = width * 10 + digit; } return width >= 1 && width <= kMaximumWidth; } explicit UnsignedInteger(std::size_t width, std::uint8_t fill = 0) : width_(width), bytes_(byteCount(width), fill) { normalize(); } static UnsignedInteger fromDecimal(std::size_t width, const std::string& text) { if (text.empty()) throw std::invalid_argument("empty unsigned integer"); UnsignedInteger value(width); for (char c : text) { if (c < '0' || c > '9') throw std::invalid_argument("invalid unsigned decimal"); value.multiplySmall(10); value.addSmall(static_cast(c - '0')); } return value; } static UnsignedInteger fromBytes(std::size_t width, const std::vector& bytes) { UnsignedInteger value(width); if (bytes.size() != value.bytes_.size()) throw std::invalid_argument("serialized unsigned integer has incorrect byte length"); value.bytes_ = bytes; if (value.exceedsWidth()) throw std::out_of_range("serialized unsigned integer exceeds declared width"); return value; } std::size_t width() const noexcept { return width_; } const std::vector& bytes() const noexcept { return bytes_; } std::vector toBytes() const { return bytes_; } bool isZero() const noexcept { return std::all_of(bytes_.begin(), bytes_.end(), [](std::uint8_t b) { return b == 0; }); } int compare(const UnsignedInteger& other) const { requireSameWidth(other); for (std::size_t i = bytes_.size(); i-- > 0;) { if (bytes_[i] < other.bytes_[i]) return -1; if (bytes_[i] > other.bytes_[i]) return 1; } return 0; } UnsignedInteger add(const UnsignedInteger& other) const { requireSameWidth(other); if (addWouldOverflow(other)) throw std::overflow_error("unsigned integer addition overflow"); UnsignedInteger out(width_); unsigned carry = 0; for (std::size_t i = 0; i < bytes_.size(); ++i) { unsigned sum = static_cast(bytes_[i]) + other.bytes_[i] + carry; out.bytes_[i] = static_cast(sum & 0xffu); carry = sum >> 8; } out.normalize(); return out; } // Subtraction is checked: unsigned underflow is an error, never wraparound. UnsignedInteger subtract(const UnsignedInteger& other) const { requireSameWidth(other); if (compare(other) < 0) throw std::underflow_error("unsigned integer underflow"); UnsignedInteger out(width_); int borrow = 0; for (std::size_t i = 0; i < bytes_.size(); ++i) { int d = static_cast(bytes_[i]) - static_cast(other.bytes_[i]) - borrow; if (d < 0) { d += 256; borrow = 1; } else borrow = 0; out.bytes_[i] = static_cast(d); } out.normalize(); return out; } bool addWouldOverflow(const UnsignedInteger& other) const { requireSameWidth(other); unsigned carry = 0; for (std::size_t i = 0; i < bytes_.size(); ++i) { unsigned sum = static_cast(bytes_[i]) + other.bytes_[i] + carry; carry = sum >> 8; if (i + 1 == bytes_.size() && (width_ % 8) != 0) { const unsigned mask = (1u << (width_ % 8)) - 1u; if ((sum & ~mask) != 0) return true; } } return carry != 0; } UnsignedInteger multiply(const UnsignedInteger& other) const { requireSameWidth(other); UnsignedInteger result(width_), addend(*this); for (std::size_t bit = 0; bit < width_; ++bit) { if (other.bitAt(bit)) { if (result.addWouldOverflow(addend)) throw std::overflow_error("unsigned integer multiplication overflow"); result = result.add(addend); } bool remaining = false; for (std::size_t next = bit + 1; next < width_; ++next) if (other.bitAt(next)) { remaining = true; break; } if (remaining) addend = addend.shiftLeftOneChecked(); } return result; } std::pair divideAndRemainder(const UnsignedInteger& divisor) const { requireSameWidth(divisor); if (divisor.isZero()) throw std::domain_error("unsigned integer division by zero"); UnsignedInteger quotient(width_), remainder(width_); for (std::size_t bit = width_; bit-- > 0;) { const bool highCarry = remainder.bitAt(width_ - 1); remainder = remainder.shiftLeftOneModulo(); if (bitAt(bit)) remainder.bytes_[0] |= 1u; if (highCarry || remainder.compare(divisor) >= 0) { remainder = remainder.subtractModulo(divisor); quotient.setBit(bit); } } return {quotient, remainder}; } UnsignedInteger divide(const UnsignedInteger& divisor) const { return divideAndRemainder(divisor).first; } UnsignedInteger modulo(const UnsignedInteger& divisor) const { return divideAndRemainder(divisor).second; } UnsignedInteger bitwiseAnd(const UnsignedInteger& other) const { requireSameWidth(other); UnsignedInteger out(width_); for (std::size_t i=0;i(~bytes_[i]); out.normalize(); return out; } UnsignedInteger shiftLeft(std::size_t amount) const { if (amount >= width_) return UnsignedInteger(width_); UnsignedInteger out(*this); while (amount--) out=out.shiftLeftOneModulo(); return out; } UnsignedInteger shiftRight(std::size_t amount) const { if (amount >= width_) return UnsignedInteger(width_); UnsignedInteger out(*this); while (amount--) { unsigned carry=0; for (std::size_t i=out.bytes_.size();i-- > 0;) { unsigned cur=out.bytes_[i]; out.bytes_[i]=static_cast((cur>>1)|(carry<<7)); carry=cur&1u; } } out.normalize(); return out; } std::string toDecimal() const { if (isZero()) return "0"; std::vector work = bytes_; std::string result; while (std::any_of(work.begin(), work.end(), [](std::uint8_t b) { return b != 0; })) { unsigned remainder = 0; for (std::size_t i = work.size(); i-- > 0;) { unsigned current = (remainder << 8) | work[i]; work[i] = static_cast(current / 10); remainder = current % 10; } result.push_back(static_cast('0' + remainder)); } std::reverse(result.begin(), result.end()); return result; } private: static std::size_t byteCount(std::size_t width) { if (width == 0 || width > kMaximumWidth) throw std::out_of_range("unsigned integer width must be in 1..1048576"); return (width + 7) / 8; } void requireSameWidth(const UnsignedInteger& other) const { if (width_ != other.width_) throw std::invalid_argument("unsigned integer width mismatch"); } void normalize() noexcept { if (bytes_.empty() || width_ % 8 == 0) return; bytes_.back() &= static_cast((1u << (width_ % 8)) - 1u); } bool bitAt(std::size_t bit) const noexcept { return (bytes_[bit/8] & static_cast(1u << (bit%8))) != 0; } void setBit(std::size_t bit) noexcept { bytes_[bit/8] |= static_cast(1u << (bit%8)); } UnsignedInteger subtractModulo(const UnsignedInteger& other) const { UnsignedInteger out(width_); int borrow=0; for(std::size_t i=0;i(bytes_[i])-static_cast(other.bytes_[i])-borrow; if(d<0){d+=256;borrow=1;}else borrow=0; out.bytes_[i]=static_cast(d); } out.normalize(); return out; } UnsignedInteger shiftLeftOneModulo() const { UnsignedInteger out(width_); unsigned carry=0; for(std::size_t i=0;i(bytes_[i])<<1)|carry; out.bytes_[i]=static_cast(cur&0xffu); carry=cur>>8; } out.normalize(); return out; } UnsignedInteger shiftLeftOneChecked() const { if ((width_%8)==0) { if (bytes_.back()&0x80u) throw std::overflow_error("unsigned integer multiplication overflow"); } else if (bytes_.back() & static_cast(1u << ((width_%8)-1))) { throw std::overflow_error("unsigned integer multiplication overflow"); } return shiftLeftOneModulo(); } void multiplySmall(unsigned factor) { unsigned carry = 0; for (std::size_t i = 0; i < bytes_.size(); ++i) { unsigned product = static_cast(bytes_[i]) * factor + carry; bytes_[i] = static_cast(product & 0xffu); carry = product >> 8; } if (carry != 0 || exceedsWidth()) throw std::out_of_range("unsigned integer value exceeds declared width"); normalize(); } void addSmall(unsigned value) { unsigned carry = value; for (std::size_t i = 0; i < bytes_.size() && carry; ++i) { unsigned sum = static_cast(bytes_[i]) + carry; bytes_[i] = static_cast(sum & 0xffu); carry = sum >> 8; } if (carry != 0 || exceedsWidth()) throw std::out_of_range("unsigned integer value exceeds declared width"); normalize(); } bool exceedsWidth() const noexcept { if (width_ % 8 == 0) return false; const unsigned mask = (1u << (width_ % 8)) - 1u; return (static_cast(bytes_.back()) & ~mask) != 0; } std::size_t width_; std::vector bytes_; }; } // namespace sleela #endif