purify
C++ Purify implementation with native circuit and BPP support
Loading...
Searching...
No Matches
numeric.hpp
Go to the documentation of this file.
1// Copyright (c) 2026 Judica, Inc.
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or https://opensource.org/license/mit/.
4
9
10#pragma once
11
12#include "purify/common.hpp"
13#include "purify/uint.h"
14
15namespace purify {
16
17namespace detail {
18
19#if defined(__SIZEOF_INT128__) && !defined(_MSC_VER)
20#if defined(__clang__) || defined(__GNUC__)
21#pragma GCC diagnostic push
22#pragma GCC diagnostic ignored "-Wpedantic"
23#endif
24#endif
25
26// `UInt128` intentionally uses the compiler `__int128` extension when it is
27// available; the fallback branch below remains the standards-only path.
28class UInt128 {
29public:
30 [[nodiscard]] static UInt128 from_words(std::uint64_t hi, std::uint64_t lo) {
31#if defined(__SIZEOF_INT128__) && !defined(_MSC_VER)
32 return UInt128((static_cast<unsigned __int128>(hi) << 64) | lo);
33#else
34 return UInt128(hi, lo);
35#endif
36 }
37
38 [[nodiscard]] static UInt128 mul_u64(std::uint64_t lhs, std::uint64_t rhs) {
39#if defined(__SIZEOF_INT128__) && !defined(_MSC_VER)
40 return UInt128(static_cast<unsigned __int128>(lhs) * rhs);
41#else
42 constexpr std::uint64_t kMask32 = 0xffffffffULL;
43
44 std::uint64_t lhs_lo = lhs & kMask32;
45 std::uint64_t lhs_hi = lhs >> 32;
46 std::uint64_t rhs_lo = rhs & kMask32;
47 std::uint64_t rhs_hi = rhs >> 32;
48
49 std::uint64_t lo_lo = lhs_lo * rhs_lo;
50 std::uint64_t hi_lo = lhs_hi * rhs_lo;
51 std::uint64_t lo_hi = lhs_lo * rhs_hi;
52 std::uint64_t hi_hi = lhs_hi * rhs_hi;
53
54 std::uint64_t cross = (lo_lo >> 32) + (hi_lo & kMask32) + (lo_hi & kMask32);
55 return UInt128(hi_hi + (hi_lo >> 32) + (lo_hi >> 32) + (cross >> 32),
56 (lo_lo & kMask32) | (cross << 32));
57#endif
58 }
59
60 [[nodiscard]] UInt128 add_u64(std::uint64_t addend) const {
61#if defined(__SIZEOF_INT128__) && !defined(_MSC_VER)
62 return UInt128(value_ + addend);
63#else
64 UInt128 out = *this;
65 out.lo_ += addend;
66 out.hi_ += (out.lo_ < addend) ? 1U : 0U;
67 return out;
68#endif
69 }
70
71 [[nodiscard]] std::pair<UInt128, std::uint32_t> divmod_u32(std::uint32_t divisor) const {
72 assert(divisor != 0 && "UInt128::divmod_u32 requires a non-zero divisor");
73#if defined(__SIZEOF_INT128__) && !defined(_MSC_VER)
74 unsigned __int128 quotient = value_ / divisor;
75 return std::make_pair(UInt128(quotient), static_cast<std::uint32_t>(value_ % divisor));
76#else
77 constexpr std::uint64_t kMask32 = 0xffffffffULL;
78
79 std::uint64_t rem = 0;
80 auto step = [&](std::uint32_t word) {
81 std::uint64_t cur = (rem << 32) | word;
82 std::uint32_t qword = static_cast<std::uint32_t>(cur / divisor);
83 rem = cur % divisor;
84 return qword;
85 };
86
87 // `step()` mutates `rem`, so sequence each word explicitly instead of
88 // relying on constructor-argument evaluation order, which differs across
89 // compilers and broke the MSVC fallback decimal conversion path.
90 const std::uint32_t q3 = step(static_cast<std::uint32_t>(hi_ >> 32));
91 const std::uint32_t q2 = step(static_cast<std::uint32_t>(hi_ & kMask32));
92 const std::uint32_t q1 = step(static_cast<std::uint32_t>(lo_ >> 32));
93 const std::uint32_t q0 = step(static_cast<std::uint32_t>(lo_ & kMask32));
94
95 UInt128 quotient((static_cast<std::uint64_t>(q3) << 32) | q2, (static_cast<std::uint64_t>(q1) << 32) | q0);
96 return std::make_pair(quotient, static_cast<std::uint32_t>(rem));
97#endif
98 }
99
100 [[nodiscard]] std::uint64_t low64() const {
101#if defined(__SIZEOF_INT128__) && !defined(_MSC_VER)
102 return static_cast<std::uint64_t>(value_);
103#else
104 return lo_;
105#endif
106 }
107
108 [[nodiscard]] std::uint64_t high64() const {
109#if defined(__SIZEOF_INT128__) && !defined(_MSC_VER)
110 return static_cast<std::uint64_t>(value_ >> 64);
111#else
112 return hi_;
113#endif
114 }
115
116private:
117#if defined(__SIZEOF_INT128__) && !defined(_MSC_VER)
118 explicit UInt128(unsigned __int128 value) : value_(value) {}
119 unsigned __int128 value_ = 0;
120#else
121 UInt128(std::uint64_t hi, std::uint64_t lo) : lo_(lo), hi_(hi) {}
122 std::uint64_t lo_ = 0;
123 std::uint64_t hi_ = 0;
124#endif
125};
126
127#if defined(__SIZEOF_INT128__) && !defined(_MSC_VER)
128#if defined(__clang__) || defined(__GNUC__)
129#pragma GCC diagnostic pop
130#endif
131#endif
132
133[[nodiscard]] inline std::size_t bit_length_u64(std::uint64_t value) {
134 return value == 0 ? 0U : 64U - static_cast<std::size_t>(std::countl_zero(value));
135}
136
137template <std::size_t Words>
139 static constexpr bool kAvailable = false;
140};
141
142#define PURIFY_DEFINE_BIGUINT_C_BRIDGE(words, bits) \
143template <> \
144struct BigUIntCBridge<words> { \
145 static constexpr bool kAvailable = true; \
146 static void set_zero(std::uint64_t* out) { purify_u##bits##_set_zero(out); } \
147 static void set_u64(std::uint64_t* out, std::uint64_t value) { purify_u##bits##_set_u64(out, value); } \
148 static void from_bytes_be(std::uint64_t* out, const unsigned char* data, std::size_t size) { \
149 purify_u##bits##_from_bytes_be(out, data, size); \
150 } \
151 static bool is_zero(const std::uint64_t* value) { return purify_u##bits##_is_zero(value) != 0; } \
152 static int compare(const std::uint64_t* lhs, const std::uint64_t* rhs) { return purify_u##bits##_compare(lhs, rhs); } \
153 static void conditional_assign(std::uint64_t* value, const std::uint64_t* other, bool flag) { \
154 purify_u##bits##_conditional_assign(value, other, static_cast<int>(flag)); \
155 } \
156 static bool try_add_small(std::uint64_t* value, std::uint32_t addend) { \
157 return purify_u##bits##_try_add_small(value, addend) != 0; \
158 } \
159 static bool try_mul_small(std::uint64_t* value, std::uint32_t factor) { \
160 return purify_u##bits##_try_mul_small(value, factor) != 0; \
161 } \
162 static bool try_add(std::uint64_t* value, const std::uint64_t* addend) { \
163 return purify_u##bits##_try_add(value, addend) != 0; \
164 } \
165 static bool try_sub(std::uint64_t* value, const std::uint64_t* subtrahend) { \
166 return purify_u##bits##_try_sub(value, subtrahend) != 0; \
167 } \
168 static std::size_t bit_length(const std::uint64_t* value) { return purify_u##bits##_bit_length(value); } \
169 static bool bit(const std::uint64_t* value, std::size_t index) { return purify_u##bits##_bit(value, index) != 0; } \
170 static bool try_set_bit(std::uint64_t* value, std::size_t index) { \
171 return purify_u##bits##_try_set_bit(value, index) != 0; \
172 } \
173 static void shifted_left(std::uint64_t* out, const std::uint64_t* value, std::size_t bits_value) { \
174 purify_u##bits##_shifted_left(out, value, bits_value); \
175 } \
176 static void shifted_right(std::uint64_t* out, const std::uint64_t* value, std::size_t bits_value) { \
177 purify_u##bits##_shifted_right(out, value, bits_value); \
178 } \
179 static void shift_right_one(std::uint64_t* value) { purify_u##bits##_shift_right_one(value); } \
180 static void mask_bits(std::uint64_t* value, std::size_t bits_value) { purify_u##bits##_mask_bits(value, bits_value); } \
181 static std::uint32_t divmod_small(std::uint64_t* value, std::uint32_t divisor) { \
182 return purify_u##bits##_divmod_small(value, divisor); \
183 } \
184 static void to_bytes_be(unsigned char* out, const std::uint64_t* value) { purify_u##bits##_to_bytes_be(out, value); } \
185}
186
190
191#undef PURIFY_DEFINE_BIGUINT_C_BRIDGE
192
193struct FieldElementAccess;
194
195} // namespace detail
196
202template <std::size_t Words>
203struct BigUInt {
204 std::array<std::uint64_t, Words> limbs{};
205
207 static BigUInt zero() {
208 BigUInt out;
211 }
212 return out;
213 }
214
216 static BigUInt one() {
217 BigUInt out;
220 } else {
221 out.limbs[0] = 1;
222 }
223 return out;
224 }
225
227 static BigUInt from_u64(std::uint64_t value) {
228 BigUInt out;
231 } else {
232 out.limbs[0] = value;
233 }
234 return out;
235 }
236
238 static BigUInt from_bytes_be(const unsigned char* data, std::size_t size) {
239 BigUInt out;
242 } else {
243 for (std::size_t i = 0; i < size; ++i) {
244 out.mul_small(256);
245 out.add_small(data[i]);
246 }
247 }
248 return out;
249 }
250
252 static Result<BigUInt> try_from_hex(std::string_view hex) {
253 BigUInt out;
254 if (hex.size() >= 2 && hex[0] == '0' && (hex[1] == 'x' || hex[1] == 'X')) {
255 hex.remove_prefix(2);
256 }
257 for (char ch : hex) {
258 if (std::isspace(static_cast<unsigned char>(ch)) != 0) {
259 continue;
260 }
261 unsigned value;
262 if (ch >= '0' && ch <= '9') {
263 value = static_cast<unsigned>(ch - '0');
264 } else if (ch >= 'a' && ch <= 'f') {
265 value = static_cast<unsigned>(10 + ch - 'a');
266 } else if (ch >= 'A' && ch <= 'F') {
267 value = static_cast<unsigned>(10 + ch - 'A');
268 } else {
269 return unexpected_error(ErrorCode::InvalidHex, "BigUInt::try_from_hex:invalid_digit");
270 }
271 if (!out.try_mul_small(16) || !out.try_add_small(value)) {
272 return unexpected_error(ErrorCode::Overflow, "BigUInt::try_from_hex:overflow");
273 }
274 }
275 return out;
276 }
277
283 static BigUInt from_hex(std::string_view hex) {
284 Result<BigUInt> out = try_from_hex(hex);
285 assert(out.has_value() && "BigUInt::from_hex() requires valid in-range input");
286 return std::move(*out);
287 }
288
290 bool is_zero() const {
293 } else {
294 for (std::uint64_t limb : limbs) {
295 if (limb != 0) {
296 return false;
297 }
298 }
299 return true;
300 }
301 }
302
304 int compare(const BigUInt& other) const {
306 return detail::BigUIntCBridge<Words>::compare(limbs.data(), other.limbs.data());
307 } else {
308 std::uint64_t less = 0;
309 std::uint64_t greater = 0;
310 for (std::size_t i = Words; i != 0; --i) {
311 const std::size_t idx = i - 1;
312 const std::uint64_t undecided = (less | greater) ^ 1U;
313 less |= undecided * static_cast<std::uint64_t>(
314 limbs[idx] < other.limbs[idx]);
315 greater |= undecided * static_cast<std::uint64_t>(
316 limbs[idx] > other.limbs[idx]);
317 }
318 return static_cast<int>(greater) - static_cast<int>(less);
319 }
320 }
321
323 void conditional_assign(const BigUInt& other, bool flag) {
326 limbs.data(), other.limbs.data(), flag);
327 } else {
328 volatile std::uint64_t selected =
329 static_cast<std::uint64_t>(flag);
330 const std::uint64_t mask = 0U - selected;
331 for (std::size_t i = 0; i < Words; ++i) {
332 limbs[i] ^= mask & (limbs[i] ^ other.limbs[i]);
333 }
334 }
335 }
336
337 bool operator==(const BigUInt& other) const {
338 return compare(other) == 0;
339 }
340
341 bool operator!=(const BigUInt& other) const {
342 return !(*this == other);
343 }
344
345 bool operator<(const BigUInt& other) const {
346 return compare(other) < 0;
347 }
348
349 bool operator>=(const BigUInt& other) const {
350 return compare(other) >= 0;
351 }
352
354 bool try_add_small(std::uint32_t value) {
355 BigUInt out = *this;
357 if (!detail::BigUIntCBridge<Words>::try_add_small(out.limbs.data(), value)) {
358 return false;
359 }
360 } else {
361 std::uint64_t carry = value;
362 for (std::size_t i = 0; i < Words && carry != 0; ++i) {
363 std::uint64_t sum = out.limbs[i] + carry;
364 carry = (sum < out.limbs[i]) ? 1U : 0U;
365 out.limbs[i] = sum;
366 }
367 if (carry != 0) {
368 return false;
369 }
370 }
371 *this = out;
372 return true;
373 }
374
380 void add_small(std::uint32_t value) {
381 bool ok = try_add_small(value);
382 assert(ok && "BigUInt::add_small() overflow");
383 (void)ok;
384 }
385
387 bool try_mul_small(std::uint32_t value) {
388 BigUInt out = *this;
390 if (!detail::BigUIntCBridge<Words>::try_mul_small(out.limbs.data(), value)) {
391 return false;
392 }
393 } else {
394 std::uint64_t carry = 0;
395 for (std::size_t i = 0; i < Words; ++i) {
396 detail::UInt128 accum = detail::UInt128::mul_u64(out.limbs[i], value);
397 accum = accum.add_u64(carry);
398 out.limbs[i] = accum.low64();
399 carry = accum.high64();
400 }
401 if (carry != 0) {
402 return false;
403 }
404 }
405 *this = out;
406 return true;
407 }
408
414 void mul_small(std::uint32_t value) {
415 bool ok = try_mul_small(value);
416 assert(ok && "BigUInt::mul_small() overflow");
417 (void)ok;
418 }
419
421 bool try_add_assign(const BigUInt& other) {
422 BigUInt out = *this;
424 if (!detail::BigUIntCBridge<Words>::try_add(out.limbs.data(), other.limbs.data())) {
425 return false;
426 }
427 } else {
428 std::uint64_t carry = 0;
429 for (std::size_t i = 0; i < Words; ++i) {
430 std::uint64_t sum = out.limbs[i] + other.limbs[i];
431 std::uint64_t carry1 = (sum < out.limbs[i]) ? 1U : 0U;
432 std::uint64_t next = sum + carry;
433 std::uint64_t carry2 = (next < sum) ? 1U : 0U;
434 out.limbs[i] = next;
435 carry = carry1 | carry2;
436 }
437 if (carry != 0) {
438 return false;
439 }
440 }
441 *this = out;
442 return true;
443 }
444
450 void add_assign(const BigUInt& other) {
451 bool ok = try_add_assign(other);
452 assert(ok && "BigUInt::add_assign() overflow");
453 (void)ok;
454 }
455
457 bool try_sub_assign(const BigUInt& other) {
458 BigUInt out = *this;
460 if (!detail::BigUIntCBridge<Words>::try_sub(out.limbs.data(), other.limbs.data())) {
461 return false;
462 }
463 } else {
464 std::uint64_t borrow = 0;
465 for (std::size_t i = 0; i < Words; ++i) {
466 std::uint64_t rhs = other.limbs[i] + borrow;
467 std::uint64_t rhs_overflow = (rhs < other.limbs[i]) ? 1U : 0U;
468 std::uint64_t next = out.limbs[i] - rhs;
469 std::uint64_t needs_borrow = (out.limbs[i] < rhs) ? 1U : 0U;
470 out.limbs[i] = next;
471 borrow = rhs_overflow | needs_borrow;
472 }
473 if (borrow != 0) {
474 return false;
475 }
476 }
477 *this = out;
478 return true;
479 }
480
486 void sub_assign(const BigUInt& other) {
487 bool ok = try_sub_assign(other);
488 assert(ok && "BigUInt::sub_assign() underflow");
489 (void)ok;
490 }
491
493 std::size_t bit_length() const {
496 } else {
497 for (std::size_t i = Words; i != 0; --i) {
498 const std::size_t idx = i - 1;
499 if (limbs[idx] != 0) {
500 return idx * 64 + detail::bit_length_u64(limbs[idx]);
501 }
502 }
503 return 0;
504 }
505 }
506
508 bool bit(std::size_t index) const {
510 return detail::BigUIntCBridge<Words>::bit(limbs.data(), index);
511 } else {
512 std::size_t word = index / 64;
513 std::size_t shift = index % 64;
514 if (word >= Words) {
515 return false;
516 }
517 return ((limbs[word] >> shift) & 1U) != 0;
518 }
519 }
520
522 bool try_set_bit(std::size_t index) {
525 } else {
526 std::size_t word = index / 64;
527 std::size_t shift = index % 64;
528 if (word >= Words) {
529 return false;
530 }
531 limbs[word] |= (static_cast<std::uint64_t>(1) << shift);
532 return true;
533 }
534 }
535
541 void set_bit(std::size_t index) {
542 bool ok = try_set_bit(index);
543 assert(ok && "BigUInt::set_bit() index out of range");
544 (void)ok;
545 }
546
548 BigUInt shifted_left(std::size_t bits) const {
549 BigUInt out;
552 } else {
553 std::size_t word_shift = bits / 64;
554 std::size_t bit_shift = bits % 64;
555 for (std::size_t i = Words; i != 0; --i) {
556 const std::size_t idx = i - 1;
557 if (idx < word_shift) {
558 continue;
559 }
560 std::size_t src = idx - word_shift;
561 out.limbs[idx] |= limbs[src] << bit_shift;
562 if (bit_shift != 0 && src > 0) {
563 out.limbs[idx] |= limbs[src - 1] >> (64 - bit_shift);
564 }
565 }
566 }
567 return out;
568 }
569
571 BigUInt shifted_right(std::size_t bits) const {
572 BigUInt out;
575 } else {
576 std::size_t word_shift = bits / 64;
577 std::size_t bit_shift = bits % 64;
578 for (std::size_t i = 0; i < Words; ++i) {
579 std::size_t src = i + word_shift;
580 if (src >= Words) {
581 break;
582 }
583 out.limbs[i] |= limbs[src] >> bit_shift;
584 if (bit_shift != 0 && src + 1 < Words) {
585 out.limbs[i] |= limbs[src + 1] << (64 - bit_shift);
586 }
587 }
588 }
589 return out;
590 }
591
596 } else {
597 for (std::size_t i = 0; i < Words; ++i) {
598 std::uint64_t next = (i + 1 < Words) ? limbs[i + 1] : 0;
599 limbs[i] = (limbs[i] >> 1) | (next << 63);
600 }
601 }
602 }
603
605 void mask_bits(std::size_t bits) {
608 } else {
609 std::size_t full_words = bits / 64;
610 std::size_t extra_bits = bits % 64;
611 for (std::size_t i = full_words + (extra_bits != 0 ? 1 : 0); i < Words; ++i) {
612 limbs[i] = 0;
613 }
614 if (extra_bits != 0 && full_words < Words) {
615 std::uint64_t mask =
616 (extra_bits == 64) ? ~static_cast<std::uint64_t>(0) : ((static_cast<std::uint64_t>(1) << extra_bits) - 1);
617 limbs[full_words] &= mask;
618 }
619 }
620 }
621
623 std::uint32_t divmod_small(std::uint32_t divisor) {
626 } else {
627 std::uint64_t rem = 0;
628 for (std::size_t i = Words; i != 0; --i) {
629 const std::size_t idx = i - 1;
630 auto [quotient, next_rem] = detail::UInt128::from_words(rem, limbs[idx]).divmod_u32(divisor);
631 assert(quotient.high64() == 0 && "BigUInt::divmod_small() quotient must fit in 64 bits");
632 limbs[idx] = quotient.low64();
633 rem = next_rem;
634 }
635 return static_cast<std::uint32_t>(rem);
636 }
637 }
638
640 std::array<unsigned char, Words * 8> to_bytes_be() const {
641 std::array<unsigned char, Words * 8> out{};
644 } else {
645 for (std::size_t i = 0; i < Words; ++i) {
646 std::uint64_t limb = limbs[i];
647 for (std::size_t j = 0; j < 8; ++j) {
648 out[out.size() - 1 - (i * 8 + j)] = static_cast<unsigned char>(limb & 0xffU);
649 limb >>= 8;
650 }
651 }
652 }
653 return out;
654 }
655
657 std::string to_hex() const {
658 auto bytes = to_bytes_be();
659 std::ostringstream out;
660 bool started = false;
661 out << std::hex << std::nouppercase;
662 for (unsigned char byte : bytes) {
663 if (!started) {
664 if (byte == 0) {
665 continue;
666 }
667 out << static_cast<unsigned>(byte);
668 started = true;
669 } else {
670 out << std::setw(2) << std::setfill('0') << static_cast<unsigned>(byte);
671 }
672 }
673 return started ? out.str() : "0";
674 }
675
677 std::string to_decimal() const {
678 if (is_zero()) {
679 return "0";
680 }
681 BigUInt copy = *this;
682 std::vector<std::uint32_t> parts;
683 while (!copy.is_zero()) {
684 parts.push_back(copy.divmod_small(1000000000U));
685 }
686 std::ostringstream out;
687 out << parts.back();
688 for (std::size_t i = parts.size(); i > 1; --i) {
689 out << std::setw(9) << std::setfill('0') << parts[i - 2];
690 }
691 return out.str();
692 }
693};
694
696template <std::size_t OutWords, std::size_t InWords>
698 static_assert(OutWords >= InWords, "Cannot narrow with widen");
700 if constexpr (OutWords == 5 && InWords == 4) {
701 purify_u320_widen_u256(out.limbs.data(), value.limbs.data());
702 } else if constexpr (OutWords == 8 && InWords == 4) {
703 purify_u512_widen_u256(out.limbs.data(), value.limbs.data());
704 } else {
705 for (std::size_t i = 0; i < InWords; ++i) {
706 out.limbs[i] = value.limbs[i];
707 }
708 }
709 return out;
710}
711
713template <std::size_t OutWords, std::size_t InWords>
715 static_assert(OutWords <= InWords, "Cannot widen with narrow");
717 if constexpr (OutWords == 4 && InWords == 5) {
718 if (!purify_u256_try_narrow_u320(out.limbs.data(), value.limbs.data())) {
719 return unexpected_error(ErrorCode::NarrowingOverflow, "try_narrow:high_bits_set");
720 }
721 } else if constexpr (OutWords == 4 && InWords == 8) {
722 if (!purify_u256_try_narrow_u512(out.limbs.data(), value.limbs.data())) {
723 return unexpected_error(ErrorCode::NarrowingOverflow, "try_narrow:high_bits_set");
724 }
725 } else {
726 for (std::size_t i = 0; i < OutWords; ++i) {
727 out.limbs[i] = value.limbs[i];
728 }
729 for (std::size_t i = OutWords; i < InWords; ++i) {
730 if (value.limbs[i] != 0) {
731 return unexpected_error(ErrorCode::NarrowingOverflow, "try_narrow:high_bits_set");
732 }
733 }
734 }
735 return out;
736}
737
739template <std::size_t OutWords, std::size_t InWords>
742 assert(out.has_value() && "narrow() requires the source value to fit");
743 return std::move(*out);
744}
745
747template <std::size_t Words>
749 BigUInt<Words> quotient;
750 BigUInt<Words> remainder = numerator;
751 if constexpr (Words == 8) {
752 if (!purify_u512_try_divmod_same(quotient.limbs.data(), remainder.limbs.data(),
753 numerator.limbs.data(), denominator.limbs.data())) {
754 return unexpected_error(ErrorCode::DivisionByZero, "try_divmod_same:zero_denominator");
755 }
756 } else {
757 if (denominator.is_zero()) {
758 return unexpected_error(ErrorCode::DivisionByZero, "try_divmod_same:zero_denominator");
759 }
760 std::size_t n_bits = remainder.bit_length();
761 std::size_t d_bits = denominator.bit_length();
762 if (n_bits < d_bits) {
763 return std::make_pair(quotient, remainder);
764 }
765 std::size_t shift = n_bits - d_bits;
766 BigUInt<Words> shifted = denominator.shifted_left(shift);
767 for (std::size_t i = shift + 1; i != 0; --i) {
768 const std::size_t idx = i - 1;
769 if (remainder.compare(shifted) >= 0) {
770 bool sub_ok = remainder.try_sub_assign(shifted);
771 bool bit_ok = quotient.try_set_bit(idx);
772 assert(sub_ok && "divmod_same() subtraction should stay in range");
773 assert(bit_ok && "divmod_same() quotient bit index should stay in range");
774 if (!sub_ok || !bit_ok) {
775 return unexpected_error(ErrorCode::InternalMismatch, "try_divmod_same:internal_step");
776 }
777 }
778 if (idx != 0) {
779 shifted.shift_right_one();
780 }
781 }
782 }
783 return std::make_pair(quotient, remainder);
784}
785
787template <std::size_t Words>
788std::pair<BigUInt<Words>, BigUInt<Words>> divmod_same(const BigUInt<Words>& numerator, const BigUInt<Words>& denominator) {
789 Result<std::pair<BigUInt<Words>, BigUInt<Words>>> out = try_divmod_same(numerator, denominator);
790 assert(out.has_value() && "divmod_same() requires a non-zero denominator");
791 return std::move(*out);
792}
793
795template <std::size_t LeftWords, std::size_t RightWords>
798 if constexpr (LeftWords == 4 && RightWords == 4) {
799 purify_u512_multiply_u256(out.limbs.data(), lhs.limbs.data(), rhs.limbs.data());
800 } else {
801 for (std::size_t i = 0; i < LeftWords; ++i) {
802 std::uint64_t carry = 0;
803 for (std::size_t j = 0; j < RightWords; ++j) {
804 detail::UInt128 accum = detail::UInt128::mul_u64(lhs.limbs[i], rhs.limbs[j]);
805 accum = accum.add_u64(out.limbs[i + j]);
806 accum = accum.add_u64(carry);
807 out.limbs[i + j] = accum.low64();
808 carry = accum.high64();
809 }
810 out.limbs[i + RightWords] += carry;
811 }
812 }
813 return out;
814}
815
822
823class FieldElement;
824
826const UInt256& prime_p();
827
835public:
836 FieldElement();
837
839 static FieldElement zero();
840
842 static FieldElement one();
843
845 static FieldElement from_u64(std::uint64_t value);
846
848 static FieldElement from_int(std::int64_t value);
849
851 static Result<FieldElement> try_from_bytes32(const std::array<unsigned char, 32>& bytes);
852
858 static FieldElement from_bytes32(const std::array<unsigned char, 32>& bytes);
859
861 static Result<FieldElement> try_from_uint256(const UInt256& value);
862
868 static FieldElement from_uint256(const UInt256& value);
869
871 UInt256 to_uint256() const;
872
874 std::array<unsigned char, 32> to_bytes_be() const;
875
877 std::array<unsigned char, 32> to_bytes_le() const;
878
880 std::string to_hex() const;
881
883 std::string to_decimal() const;
884
886 bool is_zero() const;
887
889 bool is_one() const;
890
892 bool is_odd() const;
893
895 bool is_square() const;
896
898 FieldElement negate() const;
899
901 void conditional_assign(const FieldElement& other, bool flag);
902
905
907 FieldElement inverse() const;
908
910 std::optional<FieldElement> sqrt() const;
911
913 FieldElement pow(const UInt256& exponent) const;
914
916 friend bool operator==(const FieldElement& lhs, const FieldElement& rhs);
917
919 friend bool operator!=(const FieldElement& lhs, const FieldElement& rhs);
920
922 friend FieldElement operator+(const FieldElement& lhs, const FieldElement& rhs);
923
925 friend FieldElement operator-(const FieldElement& lhs, const FieldElement& rhs);
926
928 friend FieldElement operator*(const FieldElement& lhs, const FieldElement& rhs);
929
930private:
932 explicit FieldElement(const purify_scalar& raw) : value_(raw) {}
933
934 purify_scalar value_{};
935};
936
937namespace detail {
938
940 static const purify_scalar& raw(const FieldElement& value) noexcept {
941 return value.value_;
942 }
943
944 static FieldElement from_raw(const purify_scalar& raw) noexcept {
945 return FieldElement(raw);
946 }
947};
948
949} // namespace detail
950
952FieldElement square(const FieldElement& value);
953
955int legendre_symbol(const FieldElement& value);
956
957} // namespace purify
bool has_value() const noexcept
Definition expected.hpp:170
Field element modulo the backend scalar field used by this implementation.
Definition numeric.hpp:834
bool is_square() const
Returns true when the element is a quadratic residue in the field.
Definition numeric.cpp:116
bool is_one() const
Returns true when the element is one.
Definition numeric.cpp:108
std::array< unsigned char, 32 > to_bytes_le() const
Serializes the field element in little-endian form.
Definition numeric.cpp:90
static FieldElement from_bytes32(const std::array< unsigned char, 32 > &bytes)
Decodes a 32-byte big-endian field element.
Definition numeric.cpp:63
static FieldElement from_uint256(const UInt256 &value)
Converts a 256-bit unsigned integer into the scalar field representation.
Definition numeric.cpp:73
friend bool operator!=(const FieldElement &lhs, const FieldElement &rhs)
Compares two field elements for inequality.
Definition numeric.cpp:163
FieldElement inverse() const
Returns the multiplicative inverse modulo the field prime using the faster variable-time backend.
Definition numeric.cpp:137
friend FieldElement operator+(const FieldElement &lhs, const FieldElement &rhs)
Adds two field elements modulo the field prime.
Definition numeric.cpp:167
FieldElement pow(const UInt256 &exponent) const
Raises the element to an unsigned exponent via square-and-multiply.
Definition numeric.cpp:152
bool is_odd() const
Returns true when the canonical representative is odd.
Definition numeric.cpp:112
static FieldElement from_u64(std::uint64_t value)
Constructs a field element from an unsigned 64-bit integer.
Definition numeric.cpp:40
std::string to_hex() const
Formats the field element as lowercase hexadecimal.
Definition numeric.cpp:96
static Result< FieldElement > try_from_uint256(const UInt256 &value)
Converts a canonical 256-bit unsigned integer into the scalar field representation.
Definition numeric.cpp:69
std::optional< FieldElement > sqrt() const
Computes a square root when one exists, otherwise returns std::nullopt.
Definition numeric.cpp:143
friend bool operator==(const FieldElement &lhs, const FieldElement &rhs)
Compares two field elements for exact equality.
Definition numeric.cpp:159
std::string to_decimal() const
Formats the field element as an unsigned decimal string.
Definition numeric.cpp:100
static FieldElement one()
Returns the multiplicative identity of the scalar field.
Definition numeric.cpp:36
void conditional_assign(const FieldElement &other, bool flag)
Conditionally assigns other into *this when flag is true.
Definition numeric.cpp:127
static Result< FieldElement > try_from_bytes32(const std::array< unsigned char, 32 > &bytes)
Decodes a canonical 32-byte big-endian field element.
Definition numeric.cpp:53
FieldElement negate() const
Returns the additive inverse modulo the field prime.
Definition numeric.cpp:121
static FieldElement from_int(std::int64_t value)
Constructs a field element from a signed integer, reducing negatives modulo the field.
Definition numeric.cpp:46
UInt256 to_uint256() const
Exports the field element as a canonical 256-bit unsigned integer.
Definition numeric.cpp:79
bool is_zero() const
Returns true when the element is zero.
Definition numeric.cpp:104
static FieldElement zero()
Returns the additive identity of the scalar field.
Definition numeric.cpp:32
friend FieldElement operator-(const FieldElement &lhs, const FieldElement &rhs)
Subtracts two field elements modulo the field prime.
Definition numeric.cpp:173
std::array< unsigned char, 32 > to_bytes_be() const
Serializes the field element in big-endian form.
Definition numeric.cpp:84
friend FieldElement operator*(const FieldElement &lhs, const FieldElement &rhs)
Multiplies two field elements modulo the field prime.
Definition numeric.cpp:177
FieldElement inverse_consttime() const
Returns the multiplicative inverse modulo the field prime in constant time.
Definition numeric.cpp:131
static UInt128 mul_u64(std::uint64_t lhs, std::uint64_t rhs)
Definition numeric.hpp:38
std::pair< UInt128, std::uint32_t > divmod_u32(std::uint32_t divisor) const
Definition numeric.hpp:71
std::uint64_t low64() const
Definition numeric.hpp:100
std::uint64_t high64() const
Definition numeric.hpp:108
static UInt128 from_words(std::uint64_t hi, std::uint64_t lo)
Definition numeric.hpp:30
UInt128 add_u64(std::uint64_t addend) const
Definition numeric.hpp:60
Shared includes and foundational aliases for the Purify C++ implementation.
std::size_t bit_length_u64(std::uint64_t value)
Definition numeric.hpp:133
BigUInt< LeftWords+RightWords > multiply(const BigUInt< LeftWords > &lhs, const BigUInt< RightWords > &rhs)
Multiplies two fixed-width integers and returns the full-width product.
Definition numeric.hpp:796
BigUInt< OutWords > widen(const BigUInt< InWords > &value)
Widens an integer to a larger limb count by zero-extending high limbs.
Definition numeric.hpp:697
constexpr Unexpected< Error > unexpected_error(ErrorCode code, const char *context=nullptr)
Constructs an unexpected Error value from a machine-readable code.
Definition error.hpp:293
BigUInt< 8 > UInt512
512-bit unsigned integer used for private and packed public keys.
Definition numeric.hpp:821
const UInt256 & prime_p()
Returns the Purify base-field modulus.
Definition curve.cpp:204
Result< std::pair< BigUInt< Words >, BigUInt< Words > > > try_divmod_same(const BigUInt< Words > &numerator, const BigUInt< Words > &denominator)
Performs long division where numerator and denominator have the same width.
Definition numeric.hpp:748
BigUInt< 4 > UInt256
256-bit unsigned integer used for field elements and curve orders.
Definition numeric.hpp:817
BigUInt< OutWords > narrow(const BigUInt< InWords > &value)
Narrows an integer to a smaller limb count, requiring that no high bits are lost.
Definition numeric.hpp:740
FieldElement square(const FieldElement &value)
Squares a field element.
Definition numeric.cpp:183
Result< BigUInt< OutWords > > try_narrow(const BigUInt< InWords > &value)
Narrows an integer to a smaller limb count, rejecting truncated high bits.
Definition numeric.hpp:714
Expected< T, Error > Result
Expected-returning convenience alias for Purify value-producing APIs.
Definition error.hpp:99
std::pair< BigUInt< Words >, BigUInt< Words > > divmod_same(const BigUInt< Words > &numerator, const BigUInt< Words > &denominator)
Performs long division where numerator and denominator have the same width.
Definition numeric.hpp:788
BigUInt< 5 > UInt320
320-bit unsigned integer used during hash-to-curve sampling.
Definition numeric.hpp:819
int legendre_symbol(const FieldElement &value)
Returns 0 for zero, 1 for quadratic residues, and -1 for non-residues.
Definition numeric.cpp:190
#define PURIFY_DEFINE_BIGUINT_C_BRIDGE(words, bits)
Definition numeric.hpp:142
Little-endian fixed-width unsigned integer with simple arithmetic utilities.
Definition numeric.hpp:203
std::size_t bit_length() const
Returns the index of the highest set bit plus one.
Definition numeric.hpp:493
bool bit(std::size_t index) const
Returns the bit at the given little-endian bit index.
Definition numeric.hpp:508
static BigUInt zero()
Returns the additive identity.
Definition numeric.hpp:207
static BigUInt from_bytes_be(const unsigned char *data, std::size_t size)
Parses a big-endian byte string into the fixed-width integer.
Definition numeric.hpp:238
std::array< std::uint64_t, Words > limbs
Definition numeric.hpp:204
std::uint32_t divmod_small(std::uint32_t divisor)
Divides by a small unsigned value in place and returns the remainder.
Definition numeric.hpp:623
bool is_zero() const
Returns true when all limbs are zero.
Definition numeric.hpp:290
bool try_sub_assign(const BigUInt &other)
Subtracts another fixed-width integer when the minuend is large enough.
Definition numeric.hpp:457
bool try_mul_small(std::uint32_t value)
Multiplies by a small unsigned value in place when the result fits.
Definition numeric.hpp:387
void conditional_assign(const BigUInt &other, bool flag)
Constant-time conditional assignment for secret integers.
Definition numeric.hpp:323
void sub_assign(const BigUInt &other)
Subtracts another fixed-width integer in place.
Definition numeric.hpp:486
static BigUInt from_u64(std::uint64_t value)
Constructs a value from a single 64-bit limb.
Definition numeric.hpp:227
int compare(const BigUInt &other) const
Compares two fixed-width integers using unsigned ordering.
Definition numeric.hpp:304
void add_small(std::uint32_t value)
Adds a small unsigned value in place.
Definition numeric.hpp:380
bool operator==(const BigUInt &other) const
Definition numeric.hpp:337
void mul_small(std::uint32_t value)
Multiplies by a small unsigned value in place.
Definition numeric.hpp:414
void set_bit(std::size_t index)
Sets the bit at the given little-endian bit index.
Definition numeric.hpp:541
static BigUInt from_hex(std::string_view hex)
Parses a hexadecimal string with the precondition that the value fits exactly.
Definition numeric.hpp:283
static BigUInt one()
Returns the multiplicative identity.
Definition numeric.hpp:216
bool try_set_bit(std::size_t index)
Sets the bit at the given little-endian bit index when it is in range.
Definition numeric.hpp:522
bool operator!=(const BigUInt &other) const
Definition numeric.hpp:341
bool try_add_assign(const BigUInt &other)
Adds another fixed-width integer when the result fits.
Definition numeric.hpp:421
static Result< BigUInt > try_from_hex(std::string_view hex)
Parses a hexadecimal string, ignoring optional 0x and whitespace.
Definition numeric.hpp:252
BigUInt shifted_right(std::size_t bits) const
Returns a copy shifted right by the requested bit count.
Definition numeric.hpp:571
bool operator>=(const BigUInt &other) const
Definition numeric.hpp:349
void shift_right_one()
Shifts the value right by one bit in place.
Definition numeric.hpp:593
std::array< unsigned char, Words *8 > to_bytes_be() const
Serializes the value to a fixed-width big-endian byte array.
Definition numeric.hpp:640
bool operator<(const BigUInt &other) const
Definition numeric.hpp:345
void mask_bits(std::size_t bits)
Clears all bits above the requested width.
Definition numeric.hpp:605
BigUInt shifted_left(std::size_t bits) const
Returns a copy shifted left by the requested bit count.
Definition numeric.hpp:548
std::string to_decimal() const
Formats the value as an unsigned decimal string.
Definition numeric.hpp:677
void add_assign(const BigUInt &other)
Adds another fixed-width integer in place.
Definition numeric.hpp:450
std::string to_hex() const
Formats the value as lowercase hexadecimal without leading zero padding.
Definition numeric.hpp:657
bool try_add_small(std::uint32_t value)
Adds a small unsigned value in place when the result fits.
Definition numeric.hpp:354
static constexpr bool kAvailable
Definition numeric.hpp:139
static FieldElement from_raw(const purify_scalar &raw) noexcept
Definition numeric.hpp:944
static const purify_scalar & raw(const FieldElement &value) noexcept
Definition numeric.hpp:940
Opaque scalar storage compatible with secp256k1-zkp internal scalar storage.
Definition secp_bridge.h:22
Fixed-width unsigned integer helpers implemented in C for Purify.
int purify_u256_try_narrow_u512(uint64_t out[4], const uint64_t value[8])
Definition uint.c:183
void purify_u512_widen_u256(uint64_t out[8], const uint64_t value[4])
Definition uint.c:170
void purify_u320_widen_u256(uint64_t out[5], const uint64_t value[4])
Definition uint.c:165
void purify_u512_multiply_u256(uint64_t out[8], const uint64_t lhs[4], const uint64_t rhs[4])
Definition uint.c:263
int purify_u512_try_divmod_same(uint64_t quotient[8], uint64_t remainder[8], const uint64_t numerator[8], const uint64_t denominator[8])
Definition uint.c:194
int purify_u256_try_narrow_u320(uint64_t out[4], const uint64_t value[5])
Definition uint.c:175