purify
C++ Purify implementation with native circuit and BPP support
Loading...
Searching...
No Matches
uint_impl.h
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
5#ifndef PURIFY_UINT_FN
6#error "PURIFY_UINT_FN must be defined before including uint_impl.h"
7#endif
8
9#ifndef PURIFY_UINT_WORDS
10#error "PURIFY_UINT_WORDS must be defined before including uint_impl.h"
11#endif
12
13int PURIFY_UINT_FN(try_add_small)(uint64_t value[PURIFY_UINT_WORDS], uint32_t addend);
14int PURIFY_UINT_FN(try_mul_small)(uint64_t value[PURIFY_UINT_WORDS], uint32_t factor);
15
17 size_t i;
18 for (i = 0; i < PURIFY_UINT_WORDS; ++i) {
19 out[i] = 0;
20 }
21}
22
23void PURIFY_UINT_FN(set_u64)(uint64_t out[PURIFY_UINT_WORDS], uint64_t value) {
25 out[0] = value;
26}
27
28void PURIFY_UINT_FN(from_bytes_be)(uint64_t out[PURIFY_UINT_WORDS], const unsigned char* data, size_t size) {
29 size_t i;
30 assert(size <= PURIFY_UINT_WORDS * sizeof(uint64_t));
32 for (i = 0; i < size; ++i) {
33 (void)PURIFY_UINT_FN(try_mul_small)(out, 256);
34 (void)PURIFY_UINT_FN(try_add_small)(out, data[i]);
35 }
36}
37
38int PURIFY_UINT_FN(is_zero)(const uint64_t value[PURIFY_UINT_WORDS]) {
39 uint64_t combined = 0;
40 size_t i;
41 for (i = 0; i < PURIFY_UINT_WORDS; ++i) {
42 combined |= value[i];
43 }
44 return combined == 0;
45}
46
47int PURIFY_UINT_FN(compare)(const uint64_t lhs[PURIFY_UINT_WORDS], const uint64_t rhs[PURIFY_UINT_WORDS]) {
48 uint64_t less = 0;
49 uint64_t greater = 0;
50 size_t i;
51 for (i = PURIFY_UINT_WORDS; i != 0; --i) {
52 size_t idx = i - 1u;
53 uint64_t undecided = (less | greater) ^ 1u;
54 less |= undecided & (uint64_t)(lhs[idx] < rhs[idx]);
55 greater |= undecided & (uint64_t)(lhs[idx] > rhs[idx]);
56 }
57 return (int)greater - (int)less;
58}
59
61 const uint64_t other[PURIFY_UINT_WORDS], int flag) {
62 volatile uint64_t selected = (uint64_t)(flag != 0);
63 const uint64_t mask = (uint64_t)0 - selected;
64 size_t i;
65 for (i = 0; i < PURIFY_UINT_WORDS; ++i) {
66 value[i] ^= mask & (value[i] ^ other[i]);
67 }
68}
69
70int PURIFY_UINT_FN(try_add_small)(uint64_t value[PURIFY_UINT_WORDS], uint32_t addend) {
71 uint64_t carry = addend;
72 size_t i;
73 for (i = 0; i < PURIFY_UINT_WORDS; ++i) {
74 uint64_t sum = value[i] + carry;
75 carry = sum < value[i] ? 1u : 0u;
76 value[i] = sum;
77 }
78 return carry == 0;
79}
80
81int PURIFY_UINT_FN(try_mul_small)(uint64_t value[PURIFY_UINT_WORDS], uint32_t factor) {
82 uint64_t carry = 0;
83 size_t i;
84 for (i = 0; i < PURIFY_UINT_WORDS; ++i) {
85 uint64_t hi = 0;
86 uint64_t lo = purify_uint_mul_u64(value[i], factor, &hi);
87 lo = purify_uint_add_u64_carry(lo, carry, &hi);
88 value[i] = lo;
89 carry = hi;
90 }
91 return carry == 0;
92}
93
94int PURIFY_UINT_FN(try_add)(uint64_t value[PURIFY_UINT_WORDS], const uint64_t addend[PURIFY_UINT_WORDS]) {
95 uint64_t carry = 0;
96 size_t i;
97 for (i = 0; i < PURIFY_UINT_WORDS; ++i) {
98 uint64_t sum = value[i] + addend[i];
99 uint64_t carry1 = sum < value[i] ? 1u : 0u;
100 uint64_t next = sum + carry;
101 uint64_t carry2 = next < sum ? 1u : 0u;
102 value[i] = next;
103 carry = carry1 | carry2;
104 }
105 return carry == 0;
106}
107
108int PURIFY_UINT_FN(try_sub)(uint64_t value[PURIFY_UINT_WORDS], const uint64_t subtrahend[PURIFY_UINT_WORDS]) {
109 uint64_t borrow = 0;
110 size_t i;
111 for (i = 0; i < PURIFY_UINT_WORDS; ++i) {
112 uint64_t rhs = subtrahend[i] + borrow;
113 uint64_t rhs_overflow = rhs < subtrahend[i] ? 1u : 0u;
114 uint64_t next = value[i] - rhs;
115 uint64_t needs_borrow = value[i] < rhs ? 1u : 0u;
116 value[i] = next;
117 borrow = rhs_overflow | needs_borrow;
118 }
119 return borrow == 0;
120}
121
122size_t PURIFY_UINT_FN(bit_length)(const uint64_t value[PURIFY_UINT_WORDS]) {
123 size_t i;
124 for (i = PURIFY_UINT_WORDS; i != 0; --i) {
125 size_t idx = i - 1u;
126 if (value[idx] != 0) {
127 return idx * 64u + purify_uint_bit_length_u64(value[idx]);
128 }
129 }
130 return 0;
131}
132
133int PURIFY_UINT_FN(bit)(const uint64_t value[PURIFY_UINT_WORDS], size_t index) {
134 size_t word = index / 64u;
135 size_t shift = index % 64u;
136 if (word >= PURIFY_UINT_WORDS) {
137 return 0;
138 }
139 return ((value[word] >> shift) & 1u) != 0;
140}
141
142int PURIFY_UINT_FN(try_set_bit)(uint64_t value[PURIFY_UINT_WORDS], size_t index) {
143 size_t word = index / 64u;
144 size_t shift = index % 64u;
145 if (word >= PURIFY_UINT_WORDS) {
146 return 0;
147 }
148 value[word] |= ((uint64_t)1u << shift);
149 return 1;
150}
151
152void PURIFY_UINT_FN(shifted_left)(uint64_t out[PURIFY_UINT_WORDS], const uint64_t value[PURIFY_UINT_WORDS], size_t bits) {
153 size_t word_shift = bits / 64u;
154 size_t bit_shift = bits % 64u;
155 size_t i;
157 for (i = PURIFY_UINT_WORDS; i != 0; --i) {
158 size_t src;
159 size_t idx = i - 1u;
160 if (idx < word_shift) {
161 continue;
162 }
163 src = idx - word_shift;
164 out[idx] |= value[src] << bit_shift;
165 if (bit_shift != 0 && src > 0) {
166 out[idx] |= value[src - 1] >> (64u - bit_shift);
167 }
168 }
169}
170
171void PURIFY_UINT_FN(shifted_right)(uint64_t out[PURIFY_UINT_WORDS], const uint64_t value[PURIFY_UINT_WORDS], size_t bits) {
172 size_t word_shift = bits / 64u;
173 size_t bit_shift = bits % 64u;
174 size_t i;
176 for (i = 0; i < PURIFY_UINT_WORDS; ++i) {
177 size_t src = i + word_shift;
178 if (src >= PURIFY_UINT_WORDS) {
179 break;
180 }
181 out[i] |= value[src] >> bit_shift;
182 if (bit_shift != 0 && src + 1 < PURIFY_UINT_WORDS) {
183 out[i] |= value[src + 1] << (64u - bit_shift);
184 }
185 }
186}
187
189 size_t i;
190 for (i = 0; i < PURIFY_UINT_WORDS; ++i) {
191 uint64_t next = i + 1 < PURIFY_UINT_WORDS ? value[i + 1] : 0;
192 value[i] = (value[i] >> 1) | (next << 63);
193 }
194}
195
196void PURIFY_UINT_FN(mask_bits)(uint64_t value[PURIFY_UINT_WORDS], size_t bits) {
197 const size_t total_bits = PURIFY_UINT_WORDS * 64u;
198 const size_t full_words = bits / 64u;
199 const size_t extra_bits = bits % 64u;
200 size_t i;
201 if (bits >= total_bits) {
202 return;
203 }
204 for (i = full_words + (extra_bits != 0 ? 1u : 0u); i < PURIFY_UINT_WORDS; ++i) {
205 value[i] = 0;
206 }
207 if (extra_bits != 0 && full_words < PURIFY_UINT_WORDS) {
208 uint64_t mask = ((uint64_t)1u << extra_bits) - 1u;
209 value[full_words] &= mask;
210 }
211}
212
213uint32_t PURIFY_UINT_FN(divmod_small)(uint64_t value[PURIFY_UINT_WORDS], uint32_t divisor) {
214 uint64_t rem = 0;
215 size_t i;
216 assert(divisor != 0);
217 for (i = PURIFY_UINT_WORDS; i != 0; --i) {
218 size_t idx = i - 1u;
219 uint32_t next_rem = 0;
220 uint64_t quotient = purify_uint_divmod_u32(rem, value[idx], divisor, &next_rem);
221 value[idx] = quotient;
222 rem = next_rem;
223 }
224 return (uint32_t)rem;
225}
226
227void PURIFY_UINT_FN(to_bytes_be)(unsigned char out[PURIFY_UINT_WORDS * 8], const uint64_t value[PURIFY_UINT_WORDS]) {
228 size_t i;
229 for (i = 0; i < PURIFY_UINT_WORDS; ++i) {
230 uint64_t limb = value[i];
231 size_t j;
232 for (j = 0; j < 8u; ++j) {
233 out[PURIFY_UINT_WORDS * 8u - 1u - (i * 8u + j)] = (unsigned char)(limb & 0xffu);
234 limb >>= 8;
235 }
236 }
237}
static size_t purify_uint_bit_length_u64(uint64_t value)
Definition uint.c:17
#define PURIFY_UINT_FN(name)
Definition uint.c:147
static uint64_t purify_uint_add_u64_carry(uint64_t value, uint64_t addend, uint64_t *hi)
Definition uint.c:54
static uint64_t purify_uint_divmod_u32(uint64_t hi, uint64_t lo, uint32_t divisor, uint32_t *rem_out)
Definition uint.c:110
static uint64_t purify_uint_mul_u64(uint64_t lhs, uint64_t rhs, uint64_t *hi)
Definition uint.c:33
#define PURIFY_UINT_WORDS
Definition uint.c:148
void PURIFY_UINT_FN from_bytes_be(uint64_t out[PURIFY_UINT_WORDS], const unsigned char *data, size_t size)
Definition uint_impl.h:28
size_t PURIFY_UINT_FN bit_length(const uint64_t value[PURIFY_UINT_WORDS])
Definition uint_impl.h:122
void PURIFY_UINT_FN to_bytes_be(unsigned char out[PURIFY_UINT_WORDS *8], const uint64_t value[PURIFY_UINT_WORDS])
Definition uint_impl.h:227
void PURIFY_UINT_FN mask_bits(uint64_t value[PURIFY_UINT_WORDS], size_t bits)
Definition uint_impl.h:196
int PURIFY_UINT_FN try_add(uint64_t value[PURIFY_UINT_WORDS], const uint64_t addend[PURIFY_UINT_WORDS])
Definition uint_impl.h:94
int PURIFY_UINT_FN bit(const uint64_t value[PURIFY_UINT_WORDS], size_t index)
Definition uint_impl.h:133
int PURIFY_UINT_FN is_zero(const uint64_t value[PURIFY_UINT_WORDS])
Definition uint_impl.h:38
int PURIFY_UINT_FN try_add_small(uint64_t value[PURIFY_UINT_WORDS], uint32_t addend)
Definition uint_impl.h:70
void PURIFY_UINT_FN shifted_left(uint64_t out[PURIFY_UINT_WORDS], const uint64_t value[PURIFY_UINT_WORDS], size_t bits)
Definition uint_impl.h:152
void PURIFY_UINT_FN set_u64(uint64_t out[PURIFY_UINT_WORDS], uint64_t value)
Definition uint_impl.h:23
int PURIFY_UINT_FN try_sub(uint64_t value[PURIFY_UINT_WORDS], const uint64_t subtrahend[PURIFY_UINT_WORDS])
Definition uint_impl.h:108
void PURIFY_UINT_FN shifted_right(uint64_t out[PURIFY_UINT_WORDS], const uint64_t value[PURIFY_UINT_WORDS], size_t bits)
Definition uint_impl.h:171
int PURIFY_UINT_FN compare(const uint64_t lhs[PURIFY_UINT_WORDS], const uint64_t rhs[PURIFY_UINT_WORDS])
Definition uint_impl.h:47
void PURIFY_UINT_FN conditional_assign(uint64_t value[PURIFY_UINT_WORDS], const uint64_t other[PURIFY_UINT_WORDS], int flag)
Definition uint_impl.h:60
void PURIFY_UINT_FN shift_right_one(uint64_t value[PURIFY_UINT_WORDS])
Definition uint_impl.h:188
int PURIFY_UINT_FN try_mul_small(uint64_t value[PURIFY_UINT_WORDS], uint32_t factor)
Definition uint_impl.h:81
uint32_t PURIFY_UINT_FN divmod_small(uint64_t value[PURIFY_UINT_WORDS], uint32_t divisor)
Definition uint_impl.h:213
void PURIFY_UINT_FN set_zero(uint64_t out[PURIFY_UINT_WORDS])
Definition uint_impl.h:16
int PURIFY_UINT_FN try_set_bit(uint64_t value[PURIFY_UINT_WORDS], size_t index)
Definition uint_impl.h:142