unsigned_integer.h
impl/frontend/unsigned_integer.h · 292 line(s) · c
#ifndef SLEELA_UNSIGNED_INTEGER_H
#define SLEELA_UNSIGNED_INTEGER_H
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
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<unsigned>(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<unsigned>(c - '0'));
}
return value;
}
static UnsignedInteger fromBytes(std::size_t width, const std::vector<std::uint8_t>& 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<std::uint8_t>& bytes() const noexcept { return bytes_; }
std::vector<std::uint8_t> 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<unsigned>(bytes_[i]) + other.bytes_[i] + carry;
out.bytes_[i] = static_cast<std::uint8_t>(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<int>(bytes_[i]) - static_cast<int>(other.bytes_[i]) - borrow;
if (d < 0) { d += 256; borrow = 1; } else borrow = 0;
out.bytes_[i] = static_cast<std::uint8_t>(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<unsigned>(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<UnsignedInteger, UnsignedInteger> 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_.size();++i) out.bytes_[i]=bytes_[i]&other.bytes_[i];
return out;
}
UnsignedInteger bitwiseOr(const UnsignedInteger& other) const {
requireSameWidth(other); UnsignedInteger out(width_);
for (std::size_t i=0;i<bytes_.size();++i) out.bytes_[i]=bytes_[i]|other.bytes_[i];
out.normalize(); return out;
}
UnsignedInteger bitwiseXor(const UnsignedInteger& other) const {
requireSameWidth(other); UnsignedInteger out(width_);
for (std::size_t i=0;i<bytes_.size();++i) out.bytes_[i]=bytes_[i]^other.bytes_[i];
out.normalize(); return out;
}
UnsignedInteger bitwiseNot() const {
UnsignedInteger out(width_);
for (std::size_t i=0;i<bytes_.size();++i) out.bytes_[i]=static_cast<std::uint8_t>(~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<std::uint8_t>((cur>>1)|(carry<<7));
carry=cur&1u;
}
}
out.normalize(); return out;
}
std::string toDecimal() const {
if (isZero()) return "0";
std::vector<std::uint8_t> 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<std::uint8_t>(current / 10);
remainder = current % 10;
}
result.push_back(static_cast<char>('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<std::uint8_t>((1u << (width_ % 8)) - 1u);
}
bool bitAt(std::size_t bit) const noexcept {
return (bytes_[bit/8] & static_cast<std::uint8_t>(1u << (bit%8))) != 0;
}
void setBit(std::size_t bit) noexcept { bytes_[bit/8] |= static_cast<std::uint8_t>(1u << (bit%8)); }
UnsignedInteger subtractModulo(const UnsignedInteger& other) const {
UnsignedInteger out(width_); int borrow=0;
for(std::size_t i=0;i<bytes_.size();++i) {
int d=static_cast<int>(bytes_[i])-static_cast<int>(other.bytes_[i])-borrow;
if(d<0){d+=256;borrow=1;}else borrow=0;
out.bytes_[i]=static_cast<std::uint8_t>(d);
}
out.normalize(); return out;
}
UnsignedInteger shiftLeftOneModulo() const {
UnsignedInteger out(width_); unsigned carry=0;
for(std::size_t i=0;i<bytes_.size();++i) {
unsigned cur=(static_cast<unsigned>(bytes_[i])<<1)|carry;
out.bytes_[i]=static_cast<std::uint8_t>(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<std::uint8_t>(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<unsigned>(bytes_[i]) * factor + carry;
bytes_[i] = static_cast<std::uint8_t>(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<unsigned>(bytes_[i]) + carry;
bytes_[i] = static_cast<std::uint8_t>(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<unsigned>(bytes_.back()) & ~mask) != 0;
}
std::size_t width_;
std::vector<std::uint8_t> bytes_;
};
} // namespace sleela
#endif