Branch data Line data Source code
1 : : // Copyright 2011-2021 David Robillard <d@drobilla.net>
2 : : // SPDX-License-Identifier: ISC
3 : :
4 : : #undef NDEBUG
5 : :
6 : : #include "../src/bigint.h"
7 : :
8 : : #include <assert.h>
9 : : #include <stdbool.h>
10 : : #include <stdint.h>
11 : : #include <stdlib.h>
12 : : #include <string.h>
13 : :
14 : : /* Some test data borrowed from http://github.com/google/double-conversion
15 : : which uses a completely different bigint representation (so if these agree,
16 : : everything is probably fine). Others cases are either made up to hit the
17 : : edges of the implementation, or interesting cases collected from testing the
18 : : decimal implementation. Almost everything here uses the hex representation
19 : : so it's easy to dump into Python as a sanity check. */
20 : :
21 : : static void
22 : 540 : exess_bigint_set_hex_string(ExessBigint* num, const char* const str)
23 : : {
24 : 540 : exess_bigint_zero(num);
25 : :
26 : : // Read digits from right to left until we run off the beginning
27 : 540 : const int length = (int)strlen(str);
28 : 540 : char digit_buf[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
29 : 540 : int i = length - 8;
30 [ + + ]: 1704 : for (; i >= 0; i -= 8) {
31 : 1164 : memcpy(digit_buf, str + i, 8);
32 : 1164 : num->bigits[num->n_bigits++] = (Bigit)strtoll(digit_buf, NULL, 16);
33 : : }
34 : :
35 : : // Read leftovers into MSB if necessary
36 [ + + ]: 540 : if (i > -8) {
37 : 479 : memset(digit_buf, 0, sizeof(digit_buf));
38 : 479 : memcpy(digit_buf, str, 8U + (unsigned)i);
39 : 479 : num->bigits[num->n_bigits++] = (Bigit)strtoll(digit_buf, NULL, 16);
40 : : }
41 : :
42 : 540 : exess_bigint_clamp(num);
43 : 540 : }
44 : :
45 : : static ExessBigint
46 : 538 : bigint_from_hex(const char* str)
47 : : {
48 : : ExessBigint num;
49 : 538 : exess_bigint_set_hex_string(&num, str);
50 : 538 : return num;
51 : : }
52 : :
53 : : static bool
54 : 189 : check_hex_equals(const char* const str, const ExessBigint* const num)
55 : : {
56 : 189 : const ExessBigint expected = bigint_from_hex(str);
57 : :
58 : 189 : return exess_bigint_compare(&expected, num) == 0;
59 : : }
60 : :
61 : : #define CHECK_HEXEQ(str, num) assert(check_hex_equals(str, num))
62 : :
63 : : #define CHECK_SET(setter, value, expected) \
64 : : do { \
65 : : ExessBigint num; \
66 : : exess_bigint_set_##setter(&num, value); \
67 : : CHECK_HEXEQ(expected, &num); \
68 : : } while (0)
69 : :
70 : : static void
71 : 1 : test_set(void)
72 : : {
73 [ - + ]: 1 : CHECK_SET(u32, 0, "0");
74 [ - + ]: 1 : CHECK_SET(u32, 0xA, "A");
75 [ - + ]: 1 : CHECK_SET(u32, 0x20, "20");
76 [ - + ]: 1 : CHECK_SET(u32, 0x12345678, "12345678");
77 : :
78 [ - + ]: 1 : CHECK_SET(u64, 0, "0");
79 [ - + ]: 1 : CHECK_SET(u64, 0xA, "A");
80 [ - + ]: 1 : CHECK_SET(u64, 0x20, "20");
81 [ - + ]: 1 : CHECK_SET(u64, 0x12345678, "12345678");
82 [ - + ]: 1 : CHECK_SET(u64, 0xFFFFFFFFFFFFFFFFULL, "FFFFFFFFFFFFFFFF");
83 [ - + ]: 1 : CHECK_SET(u64, 0x123456789ABCDEF0ULL, "123456789ABCDEF0");
84 [ - + ]: 1 : CHECK_SET(u64, 0x123456789ABCDEF0ULL, "123456789ABCDEF0");
85 : :
86 [ - + ]: 1 : CHECK_SET(decimal_string, "0", "0");
87 [ - + ]: 1 : CHECK_SET(decimal_string, "1", "1");
88 [ - + ]: 1 : CHECK_SET(decimal_string, "01234567890", "499602D2");
89 [ - + ]: 1 : CHECK_SET(decimal_string, "12345", "3039");
90 [ - + ]: 1 : CHECK_SET(decimal_string, "12345EOF", "3039");
91 [ - + ]: 1 : CHECK_SET(decimal_string, "12345.67890", "3039");
92 [ - + ]: 1 : CHECK_SET(decimal_string, "12345.67890EOF", "3039");
93 [ - + ]: 1 : CHECK_SET(decimal_string, "012345678901", "2DFDC1C35");
94 [ - + ]: 1 : CHECK_SET(decimal_string, "12345.678901", "3039");
95 [ - + ]: 1 : CHECK_SET(decimal_string,
96 : : "340282366920938463463374607431768211456",
97 : : "100000000000000000000000000000000");
98 : :
99 [ - + ]: 1 : CHECK_SET(hex_string, "0", "0");
100 [ - + ]: 1 : CHECK_SET(hex_string, "123456789ABCDEF0", "123456789ABCDEF0");
101 : :
102 : 1 : const ExessBigint orig = bigint_from_hex("123456789ABCDEF01");
103 : : ExessBigint copy;
104 : 1 : exess_bigint_set(©, &orig);
105 [ - + ]: 1 : CHECK_HEXEQ("123456789ABCDEF01", ©);
106 : 1 : }
107 : :
108 : : static void
109 : 19 : check_left_shifted_bigit(const char* value,
110 : : const unsigned amount,
111 : : const unsigned index,
112 : : const Bigit expected)
113 : : {
114 : 19 : const ExessBigint num = bigint_from_hex(value);
115 : 19 : const Bigit actual = exess_bigint_left_shifted_bigit(&num, amount, index);
116 : :
117 [ - + ]: 19 : assert(expected == actual);
118 : 19 : }
119 : :
120 : : static void
121 : 1 : test_left_shifted_bigit(void)
122 : : {
123 : 1 : check_left_shifted_bigit("0", 100, 1, 0x0);
124 : 1 : check_left_shifted_bigit("1", 0, 0, 0x1);
125 : 1 : check_left_shifted_bigit("1", 1, 0, 0x2);
126 : 1 : check_left_shifted_bigit("1", 4, 0, 0x10);
127 : 1 : check_left_shifted_bigit("1", 32, 0, 0x0);
128 : 1 : check_left_shifted_bigit("1", 32, 1, 0x1);
129 : 1 : check_left_shifted_bigit("1", 64, 0, 0x0);
130 : 1 : check_left_shifted_bigit("1", 64, 1, 0x0);
131 : 1 : check_left_shifted_bigit("1", 64, 2, 0x1);
132 : 1 : check_left_shifted_bigit("123456789ABCDEF", 64, 0, 0x0);
133 : 1 : check_left_shifted_bigit("123456789ABCDEF", 64, 1, 0x0);
134 : 1 : check_left_shifted_bigit("123456789ABCDEF", 64, 2, 0x89ABCDEF);
135 : 1 : check_left_shifted_bigit("123456789ABCDEF", 64, 3, 0x1234567);
136 : 1 : check_left_shifted_bigit("123456789ABCDEF", 64, 4, 0x0);
137 : 1 : check_left_shifted_bigit("123456789ABCDEF", 65, 0, 0x0);
138 : 1 : check_left_shifted_bigit("123456789ABCDEF", 65, 1, 0x0);
139 : 1 : check_left_shifted_bigit("123456789ABCDEF", 65, 2, 0x13579BDE);
140 : 1 : check_left_shifted_bigit("123456789ABCDEF", 65, 3, 0x2468ACF);
141 : 1 : check_left_shifted_bigit("123456789ABCDEF", 65, 4, 0x0);
142 : 1 : }
143 : :
144 : : static void
145 : 9 : check_shift_left(const char* value, const unsigned amount, const char* expected)
146 : : {
147 : 9 : ExessBigint num = bigint_from_hex(value);
148 : 9 : exess_bigint_shift_left(&num, amount);
149 [ - + ]: 9 : CHECK_HEXEQ(expected, &num);
150 : 9 : }
151 : :
152 : : static void
153 : 1 : test_shift_left(void)
154 : : {
155 : 1 : check_shift_left("0", 100, "0");
156 : 1 : check_shift_left("1", 1, "2");
157 : 1 : check_shift_left("1", 4, "10");
158 : 1 : check_shift_left("1", 32, "100000000");
159 : 1 : check_shift_left("1", 64, "10000000000000000");
160 : 1 : check_shift_left("123456789ABCDEF", 0, "123456789ABCDEF");
161 : 1 : check_shift_left("123456789ABCDEF", 64, "123456789ABCDEF0000000000000000");
162 : 1 : check_shift_left("123456789ABCDEF", 65, "2468ACF13579BDE0000000000000000");
163 : 1 : check_shift_left("16B8B5E06EDC79", 23, "B5C5AF0376E3C800000");
164 : 1 : }
165 : :
166 : : static void
167 : 6 : check_add_u32(const char* value, const uint32_t rhs, const char* expected)
168 : : {
169 : 6 : ExessBigint num = bigint_from_hex(value);
170 : 6 : exess_bigint_add_u32(&num, rhs);
171 [ - + ]: 6 : CHECK_HEXEQ(expected, &num);
172 : 6 : }
173 : :
174 : : static void
175 : 1 : test_add_u32(void)
176 : : {
177 : 1 : check_add_u32("0", 1, "1");
178 : 1 : check_add_u32("1", 1, "2");
179 : 1 : check_add_u32("FFFFFFF", 1, "10000000");
180 : 1 : check_add_u32("FFFFFFFFFFFFFF", 1, "100000000000000");
181 : :
182 : 1 : check_add_u32("10000000000000000000000000000000000080000000",
183 : : 0x80000000,
184 : : "10000000000000000000000000000000000100000000");
185 : :
186 : 1 : check_add_u32("10000000000000000000000000000000000000000000",
187 : : 0x1,
188 : : "10000000000000000000000000000000000000000001");
189 : 1 : }
190 : :
191 : : static void
192 : 15 : check_add(const char* lhs_hex, const char* rhs_hex, const char* expected)
193 : : {
194 : 15 : ExessBigint lhs = bigint_from_hex(lhs_hex);
195 : 15 : const ExessBigint rhs = bigint_from_hex(rhs_hex);
196 : :
197 : 15 : exess_bigint_add(&lhs, &rhs);
198 [ - + ]: 15 : CHECK_HEXEQ(expected, &lhs);
199 : 15 : }
200 : :
201 : : static void
202 : 1 : test_add(void)
203 : : {
204 : 1 : check_add("1", "0", "1");
205 : 1 : check_add("1", "1", "2");
206 : 1 : check_add("FFFFFFF", "1", "10000000");
207 : 1 : check_add("FFFFFFFFFFFFFF", "1", "100000000000000");
208 : 1 : check_add("1", "1000000000000", "1000000000001");
209 : 1 : check_add("FFFFFFF", "1000000000000", "100000FFFFFFF");
210 : :
211 : 1 : check_add("10000000000000000000000000000000000000000000",
212 : : "1",
213 : : "10000000000000000000000000000000000000000001");
214 : :
215 : 1 : check_add("10000000000000000000000000000000000000000000",
216 : : "1000000000000",
217 : : "10000000000000000000000000000001000000000000");
218 : :
219 : 1 : check_add("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
220 : : "1000000000000",
221 : : "1000000000000000000000000000000FFFFFFFFFFFF");
222 : :
223 : 1 : check_add("10000000000000000000000000",
224 : : "1000000000000",
225 : : "10000000000001000000000000");
226 : :
227 : 1 : check_add(
228 : : "1", "10000000000000000000000000000", "10000000000000000000000000001");
229 : :
230 : 1 : check_add("FFFFFFF",
231 : : "10000000000000000000000000000",
232 : : "1000000000000000000000FFFFFFF");
233 : :
234 : 1 : check_add("10000000000000000000000000000000000000000000",
235 : : "10000000000000000000000000000",
236 : : "10000000000000010000000000000000000000000000");
237 : :
238 : 1 : check_add("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
239 : : "10000000000000000000000000000",
240 : : "100000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFF");
241 : :
242 : 1 : check_add("10000000000000000000000000",
243 : : "10000000000000000000000000000",
244 : : "10010000000000000000000000000");
245 : 1 : }
246 : :
247 : : static void
248 : 16 : check_subtract(const char* lhs_hex, const char* rhs_hex, const char* expected)
249 : : {
250 : 16 : ExessBigint lhs = bigint_from_hex(lhs_hex);
251 : 16 : const ExessBigint rhs = bigint_from_hex(rhs_hex);
252 : :
253 : 16 : exess_bigint_subtract(&lhs, &rhs);
254 [ - + ]: 16 : CHECK_HEXEQ(expected, &lhs);
255 : 16 : }
256 : :
257 : : static void
258 : 1 : test_subtract(void)
259 : : {
260 : 1 : check_subtract("1", "0", "1");
261 : 1 : check_subtract("2", "0", "2");
262 : 1 : check_subtract("10000000", "1", "FFFFFFF");
263 : 1 : check_subtract("1FFFFFFFF00000000", "FFFFFFFF", "1FFFFFFFE00000001");
264 : 1 : check_subtract("100000000000000", "1", "FFFFFFFFFFFFFF");
265 : 1 : check_subtract("1000000000001", "1000000000000", "1");
266 : 1 : check_subtract("100000FFFFFFF", "1000000000000", "FFFFFFF");
267 : :
268 : 1 : check_subtract(
269 : : "11F2678326EA00000000", "0878678326EAC9000000", "979FFFFFFFF37000000");
270 : :
271 : 1 : check_subtract("10000000000000000000000000000000000000000001",
272 : : "00000000000000000000000000000000000000000001",
273 : : "10000000000000000000000000000000000000000000");
274 : :
275 : 1 : check_subtract("10000000000000000000000000000001000000000000",
276 : : "00000000000000000000000000000001000000000000",
277 : : "10000000000000000000000000000000000000000000");
278 : :
279 : 1 : check_subtract("1000000000000000000000000000000FFFFFFFFFFFF",
280 : : "0000000000000000000000000000001000000000000",
281 : : " FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
282 : :
283 : 1 : check_subtract("10000000000000000000000000",
284 : : "00000000000001000000000000",
285 : : " FFFFFFFFFFFFF000000000000");
286 : :
287 : 1 : check_subtract("10000000000000000000000000",
288 : : "1000000000000000000000000",
289 : : "F000000000000000000000000");
290 : :
291 : 1 : check_subtract("FFFFFFF000000000000000",
292 : : "0000000000000800000000",
293 : : "FFFFFFEFFFFFF800000000");
294 : :
295 : 1 : check_subtract("10000000000000000000000000000000000000000000",
296 : : "00000000000000000000000000000000000800000000",
297 : : "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF800000000");
298 : :
299 : 1 : check_subtract("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
300 : : "000000000000000000000000000000000800000000",
301 : : "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFFF");
302 : 1 : }
303 : :
304 : : static void
305 : 10 : check_subtract_left_shifted(const char* lhs_hex,
306 : : const char* rhs_hex,
307 : : const unsigned amount,
308 : : const char* expected)
309 : : {
310 : 10 : ExessBigint lhs = bigint_from_hex(lhs_hex);
311 : 10 : const ExessBigint rhs = bigint_from_hex(rhs_hex);
312 : :
313 : 10 : exess_bigint_subtract_left_shifted(&lhs, &rhs, amount);
314 [ - + ]: 10 : CHECK_HEXEQ(expected, &lhs);
315 : 10 : }
316 : :
317 : : static void
318 : 1 : test_subtract_left_shifted(void)
319 : : {
320 : 1 : check_subtract_left_shifted("1", "0", 1, "1");
321 : 1 : check_subtract_left_shifted("10000000", "1", 1, "FFFFFFE");
322 : 1 : check_subtract_left_shifted("100000000", "40000000", 2, "0");
323 : 1 : check_subtract_left_shifted("1000000000000000", "400000000000000", 2, "0");
324 : 1 : check_subtract_left_shifted("1000000000000000", "800000000000000", 1, "0");
325 : 1 : check_subtract_left_shifted("1000000000000000", "F", 16, "FFFFFFFFFF10000");
326 : 1 : check_subtract_left_shifted("1000000000000000", "F", 24, "FFFFFFFF1000000");
327 : 1 : check_subtract_left_shifted("100000000000000", "1", 0, "FFFFFFFFFFFFFF");
328 : 1 : check_subtract_left_shifted("100000000000000", "1", 56, "0");
329 : :
330 : 1 : check_subtract_left_shifted(
331 : : "11F2678326EA00000000", "43C33C1937564800000", 1, "979FFFFFFFF37000000");
332 : 1 : }
333 : :
334 : : static void
335 : 20 : check_multiply_u32(const char* value, const uint32_t rhs, const char* expected)
336 : : {
337 : 20 : ExessBigint num = bigint_from_hex(value);
338 : 20 : exess_bigint_multiply_u32(&num, rhs);
339 [ - + ]: 20 : CHECK_HEXEQ(expected, &num);
340 : 20 : }
341 : :
342 : : static void
343 : 1 : test_multiply_u32(void)
344 : : {
345 : 1 : check_multiply_u32("0", 0x25, "0");
346 : 1 : check_multiply_u32("123456789ABCDEF", 0, "0");
347 : 1 : check_multiply_u32("123456789ABCDEF", 1, "123456789ABCDEF");
348 : 1 : check_multiply_u32("2", 0x5, "A");
349 : 1 : check_multiply_u32("10000000", 0x9, "90000000");
350 : 1 : check_multiply_u32("100000000000000", 0xFFFF, "FFFF00000000000000");
351 : 1 : check_multiply_u32("100000000000000", 0xFFFFFFFF, "FFFFFFFF00000000000000");
352 : 1 : check_multiply_u32("1234567ABCD", 0xFFF, "12333335552433");
353 : 1 : check_multiply_u32("1234567ABCD", 0xFFFFFFF, "12345679998A985433");
354 : 1 : check_multiply_u32("FFFFFFFFFFFFFFFF", 0x2, "1FFFFFFFFFFFFFFFE");
355 : 1 : check_multiply_u32("FFFFFFFFFFFFFFFF", 0x4, "3FFFFFFFFFFFFFFFC");
356 : 1 : check_multiply_u32("FFFFFFFFFFFFFFFF", 0xF, "EFFFFFFFFFFFFFFF1");
357 : 1 : check_multiply_u32("FFFFFFFFFFFFFFFF", 0xFFFFFF, "FFFFFEFFFFFFFFFF000001");
358 : 1 : check_multiply_u32("377654D193A171", 10000000, "210EDD6D4CDD2580EE80");
359 : 1 : check_multiply_u32("2E3F36D108373C00000", 10, "1CE78242A52285800000");
360 : :
361 : 1 : check_multiply_u32(
362 : : "10000000000000000000000000", 0x00000002, "20000000000000000000000000");
363 : :
364 : 1 : check_multiply_u32(
365 : : "10000000000000000000000000", 0x0000000F, "F0000000000000000000000000");
366 : :
367 : 1 : check_multiply_u32("FFFF0000000000000000000000000",
368 : : 0xFFFF,
369 : : "FFFE00010000000000000000000000000");
370 : :
371 : 1 : check_multiply_u32("FFFF0000000000000000000000000",
372 : : 0xFFFFFFFF,
373 : : "FFFEFFFF00010000000000000000000000000");
374 : :
375 : 1 : check_multiply_u32("FFFF0000000000000000000000000",
376 : : 0xFFFFFFFF,
377 : : "FFFEFFFF00010000000000000000000000000");
378 : 1 : }
379 : :
380 : : static void
381 : 19 : check_multiply_u64(const char* value, const uint64_t rhs, const char* expected)
382 : : {
383 : 19 : ExessBigint num = bigint_from_hex(value);
384 : 19 : exess_bigint_multiply_u64(&num, rhs);
385 [ - + ]: 19 : CHECK_HEXEQ(expected, &num);
386 : 19 : }
387 : :
388 : : static void
389 : 1 : test_multiply_u64(void)
390 : : {
391 : 1 : check_multiply_u64("0", 0x25, "0");
392 : 1 : check_multiply_u64("123456789ABCDEF", 0, "0");
393 : 1 : check_multiply_u64("123456789ABCDEF", 1, "123456789ABCDEF");
394 : 1 : check_multiply_u64("2", 0x5, "A");
395 : 1 : check_multiply_u64("10000000", 0x9, "90000000");
396 : 1 : check_multiply_u64("100000000000000", 0xFFFF, "FFFF00000000000000");
397 : 1 : check_multiply_u64("1234567ABCD", 0xFFF, "12333335552433");
398 : 1 : check_multiply_u64("1234567ABCD", 0xFFFFFFFFFFULL, "1234567ABCBDCBA985433");
399 : 1 : check_multiply_u64("FFFFFFFFFFFFFFFF", 0x2, "1FFFFFFFFFFFFFFFE");
400 : 1 : check_multiply_u64("FFFFFFFFFFFFFFFF", 0x4, "3FFFFFFFFFFFFFFFC");
401 : 1 : check_multiply_u64("FFFFFFFFFFFFFFFF", 0xF, "EFFFFFFFFFFFFFFF1");
402 : :
403 : 1 : check_multiply_u64(
404 : : "100000000000000", 0xFFFFFFFFFFFFFFFFULL, "FFFFFFFFFFFFFFFF00000000000000");
405 : :
406 : 1 : check_multiply_u64("FFFFFFFFFFFFFFFF",
407 : : 0xFFFFFFFFFFFFFFFFULL,
408 : : "FFFFFFFFFFFFFFFE0000000000000001");
409 : :
410 : 1 : check_multiply_u64(
411 : : "10000000000000000000000000", 0x00000002, "20000000000000000000000000");
412 : :
413 : 1 : check_multiply_u64(
414 : : "10000000000000000000000000", 0x0000000F, "F0000000000000000000000000");
415 : :
416 : 1 : check_multiply_u64("FFFF0000000000000000000000000",
417 : : 0xFFFF,
418 : : "FFFE00010000000000000000000000000");
419 : :
420 : 1 : check_multiply_u64("FFFF0000000000000000000000000",
421 : : 0xFFFFFFFF,
422 : : "FFFEFFFF00010000000000000000000000000");
423 : :
424 : 1 : check_multiply_u64("FFFF0000000000000000000000000",
425 : : 0xFFFFFFFFFFFFFFFFULL,
426 : : "FFFEFFFFFFFFFFFF00010000000000000000000000000");
427 : :
428 : 1 : check_multiply_u64(
429 : : "377654D193A171", 0x8AC7230489E80000ULL, "1E10EE4B11D15A7F3DE7F3C7680000");
430 : 1 : }
431 : :
432 : : static void
433 : 44 : check_multiply_pow10(const char* value,
434 : : const unsigned exponent,
435 : : const char* expected)
436 : : {
437 : 44 : ExessBigint num = bigint_from_hex(value);
438 : 44 : exess_bigint_multiply_pow10(&num, exponent);
439 [ - + ]: 44 : CHECK_HEXEQ(expected, &num);
440 : 44 : }
441 : :
442 : : static void
443 : 1 : test_multiply_pow10(void)
444 : : {
445 : 1 : check_multiply_pow10("0", 10, "0");
446 : 1 : check_multiply_pow10("1234", 0, "1234");
447 : 1 : check_multiply_pow10("4D2", 1, "3034");
448 : 1 : check_multiply_pow10("4D2", 2, "1E208");
449 : 1 : check_multiply_pow10("4D2", 3, "12D450");
450 : 1 : check_multiply_pow10("4D2", 4, "BC4B20");
451 : 1 : check_multiply_pow10("4D2", 5, "75AEF40");
452 : 1 : check_multiply_pow10("4D2", 6, "498D5880");
453 : 1 : check_multiply_pow10("4D2", 7, "2DF857500");
454 : 1 : check_multiply_pow10("4D2", 8, "1CBB369200");
455 : 1 : check_multiply_pow10("4D2", 9, "11F5021B400");
456 : 1 : check_multiply_pow10("4D2", 10, "B3921510800");
457 : 1 : check_multiply_pow10("4D2", 11, "703B4D2A5000");
458 : 1 : check_multiply_pow10("4D2", 12, "4625103A72000");
459 : 1 : check_multiply_pow10("4D2", 13, "2BD72A24874000");
460 : 1 : check_multiply_pow10("4D2", 14, "1B667A56D488000");
461 : 1 : check_multiply_pow10("4D2", 15, "11200C7644D50000");
462 : 1 : check_multiply_pow10("4D2", 16, "AB407C9EB0520000");
463 : 1 : check_multiply_pow10("4D2", 17, "6B084DE32E3340000");
464 : 1 : check_multiply_pow10("4D2", 18, "42E530ADFCE0080000");
465 : 1 : check_multiply_pow10("4D2", 19, "29CF3E6CBE0C0500000");
466 : 1 : check_multiply_pow10("4D2", 20, "1A218703F6C783200000");
467 : 1 : check_multiply_pow10("4D2", 21, "1054F4627A3CB1F400000");
468 : 1 : check_multiply_pow10("4D2", 22, "A3518BD8C65EF38800000");
469 : 1 : check_multiply_pow10("4D2", 23, "6612F7677BFB5835000000");
470 : 1 : check_multiply_pow10("4D2", 24, "3FCBDAA0AD7D17212000000");
471 : 1 : check_multiply_pow10("4D2", 25, "27DF68A46C6E2E74B4000000");
472 : 1 : check_multiply_pow10("4D2", 26, "18EBA166C3C4DD08F08000000");
473 : 1 : check_multiply_pow10("4D2", 27, "F9344E03A5B0A259650000000");
474 : 1 : check_multiply_pow10("4D2", 28, "9BC0B0C2478E6577DF20000000");
475 : 1 : check_multiply_pow10("4D2", 29, "61586E796CB8FF6AEB740000000");
476 : 1 : check_multiply_pow10("4D2", 30, "3CD7450BE3F39FA2D32880000000");
477 : 1 : check_multiply_pow10("4D2", 31, "26068B276E7843C5C3F9500000000");
478 : :
479 : 1 : check_multiply_pow10("4D2",
480 : : 50,
481 : : "149D1B4CFED03B23AB5F4E1196EF45C0"
482 : : "8000000000000");
483 : :
484 : 1 : check_multiply_pow10("4D2",
485 : : 100,
486 : : "5827249F27165024FBC47DFCA9359BF3"
487 : : "16332D1B91ACEECF471FBAB06D9B2000"
488 : : "0000000000000000000000");
489 : :
490 : 1 : check_multiply_pow10("4D2",
491 : : 305,
492 : : "AFBA390D657B0829339F5B98DC852A89"
493 : : "682758E01829EADFD016D1528D4D548B"
494 : : "80894B9ED9C2EC6A9CABB4881302A637"
495 : : "9FF3058908FEAC310C52FCA009799718"
496 : : "8260B0B2E2EC96E471B7892AD9B4F9F9"
497 : : "A448CBF150D2E87F3934000000000000"
498 : : "00000000000000000000000000000000"
499 : : "00000000000000000000000000000000");
500 : :
501 : 1 : check_multiply_pow10("123456789ABCDEF0", 0, "123456789ABCDEF0");
502 : 1 : check_multiply_pow10("123456789ABCDEF0",
503 : : 44,
504 : : "51A1AD66ACE4E5C79209330F58F52DE3"
505 : : "7CEFFF1F000000000000");
506 : 1 : check_multiply_pow10("123456789ABCDEF0",
507 : : 88,
508 : : "16E0C6D18F4BFA7D0289B88382F56151"
509 : : "EB9DA5DB09D56C9BA5D8305619CEE057"
510 : : "4F00000000000000000000000");
511 : 1 : check_multiply_pow10("123456789ABCDEF0",
512 : : 132,
513 : : "6696B1DA27BEA173B5EFCAABBB8492A9"
514 : : "2AE3D97F7EE3C7314FB7E2FF8AEFD329"
515 : : "F5F8202C22650BB79A7D9F3867F00000"
516 : : "00000000000000000000000000000");
517 : 1 : check_multiply_pow10("123456789ABCDEF0",
518 : : 176,
519 : : "1CC05FF0499D8BC7D8EBE0C6DC2FDC09"
520 : : "E93765F3448235FB16AD09D98BBB3A0A"
521 : : "843372D33A318EE63DAE6998DA59EF34"
522 : : "B15C40A65B9B65ABF3CAF00000000000"
523 : : "00000000000000000000000000000000"
524 : : "00");
525 : 1 : check_multiply_pow10("123456789ABCDEF0",
526 : : 220,
527 : : "80ED0FD9A6C0F56A495F466320D34E22"
528 : : "507FAA83F0519E7FF909FDDBDA184682"
529 : : "BB70D38D43284C828A3681540722E550"
530 : : "960567BAB1C25389C1BE7705228BE8CC"
531 : : "AF3EBD382829DF000000000000000000"
532 : : "00000000000000000000000000000000"
533 : : "000000");
534 : 1 : check_multiply_pow10("123456789ABCDEF0",
535 : : 264,
536 : : "2421FD0F55C486D05211339D45EC2DC4"
537 : : "12AE7A64DDFE619DA81B73C069088D3E"
538 : : "83D7AA9F99B571815DE939A5275FB4A6"
539 : : "9D8930798C01FB96781B9D633BB59AD5"
540 : : "A7F322A7EC14154D1B8B5DF1718779A5"
541 : : "2291FE0F000000000000000000000000"
542 : : "00000000000000000000000000000000"
543 : : "00000000000");
544 : 1 : check_multiply_pow10("123456789ABCDEF0",
545 : : 308,
546 : : "A206620F35C83E9E780ECC07DCAF13BB"
547 : : "0A7EE2E213747914340BC172D783BA56"
548 : : "661E8DCFFD03C398BD66F5570F445AC6"
549 : : "737126283C64AE1A289B9D8BB4531033"
550 : : "8C3E34DE2D534187092ABA1F4706100E"
551 : : "ECF66D14059461A05A9BEBBCCBA0F693"
552 : : "F0000000000000000000000000000000"
553 : : "00000000000000000000000000000000"
554 : : "000000000000000");
555 : 1 : }
556 : :
557 : : static void
558 : 18 : check_divmod(const char* lhs_hex,
559 : : const char* rhs_hex,
560 : : const uint32_t expected_divisor,
561 : : const char* expected_mod_hex)
562 : : {
563 : 18 : ExessBigint lhs = bigint_from_hex(lhs_hex);
564 : 18 : const ExessBigint rhs = bigint_from_hex(rhs_hex);
565 : 18 : const uint32_t divisor = exess_bigint_divmod(&lhs, &rhs);
566 : :
567 [ - + ]: 18 : assert(divisor == expected_divisor);
568 [ - + ]: 18 : CHECK_HEXEQ(expected_mod_hex, &lhs);
569 : 18 : }
570 : :
571 : : static void
572 : 1 : test_divmod(void)
573 : : {
574 : 1 : check_divmod("A", "2", 5, "0");
575 : 1 : check_divmod("B", "2", 5, "1");
576 : 1 : check_divmod("C", "2", 6, "0");
577 : 1 : check_divmod("A", "1234567890", 0, "A");
578 : 1 : check_divmod("FFFFFFFF", "3", 0x55555555, "0");
579 : 1 : check_divmod("12345678", "3789012", 5, "D9861E");
580 : 1 : check_divmod("70000001", "1FFFFFFF", 3, "10000004");
581 : 1 : check_divmod("28000000", "12A05F20", 2, "2BF41C0");
582 : 1 : check_divmod("FFFFFFFFF", "FFFFFFFF", 16, "F");
583 : 1 : check_divmod("100000000000001", "FFFFFFF", 0x10000001, "2");
584 : 1 : check_divmod("40000000000002", "2FAF0800000000", 1, "1050F800000002");
585 : 1 : check_divmod("40000000000000", "40000000000000", 1, "0");
586 : :
587 : 1 : check_divmod("43DE72C3DF858FC278A361EEB5A000000",
588 : : "80000000000000000000000000000000",
589 : : 8,
590 : : "3DE72C3DF858FC278A361EEB5A000000");
591 : :
592 : 1 : check_divmod(
593 : : "B5C5AF0376E3C800000", "43C33C1937564800000", 2, "2E3F36D108373800000");
594 : :
595 : 1 : check_divmod("A0000000000000000000000000000000"
596 : : "00000000000000000000000000000000"
597 : : "00000000000000000000000000000000"
598 : : "000000000000000000000000000000",
599 : : "20000000000000000000000000000000"
600 : : "00000000000000000000000000000000"
601 : : "00000000000000000000000000000000"
602 : : "000000000000000000000000000000",
603 : : 5,
604 : : "0");
605 : :
606 : 1 : check_divmod("A0000000000000000000000000000000"
607 : : "00000000000000000000000000000000"
608 : : "00000000000000000000000000000000"
609 : : "000000000000000000000000000001",
610 : : "20000000000000000000000000000000"
611 : : "00000000000000000000000000000000"
612 : : "00000000000000000000000000000000"
613 : : "000000000000000000000000000000",
614 : : 5,
615 : : "1");
616 : :
617 : 1 : check_divmod("B6080000000000000000000000000000"
618 : : "00000000000000000000000000000000"
619 : : "00000000000000000000000000000000"
620 : : "000000000000000000000000000000FF"
621 : : "F",
622 : : "A0000000000000000000000000000000"
623 : : "00000000000000000000000000000000"
624 : : "00000000000000000000000000000000"
625 : : "000000000000000000000000000000",
626 : : 0x1234,
627 : : "FFF");
628 : :
629 : 1 : check_divmod("B6080000000000000000000000000000"
630 : : "00000000000000000000000000000000"
631 : : "00000000000000000000000000000000"
632 : : "00000000000000000000000000000000"
633 : : "0",
634 : : "9FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
635 : : "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
636 : : "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
637 : : "FFFFFFFFFFFFFFFFFFFFFFFFFFF001",
638 : : 0x1234,
639 : : "1232DCC");
640 : 1 : }
641 : :
642 : : static void
643 : 13 : check_compare(const char* lhs_hex, const char* rhs_hex, const int expected_cmp)
644 : : {
645 : 13 : const ExessBigint lhs = bigint_from_hex(lhs_hex);
646 : 13 : const ExessBigint rhs = bigint_from_hex(rhs_hex);
647 : 13 : const int cmp = exess_bigint_compare(&lhs, &rhs);
648 : :
649 [ - + ]: 13 : assert(cmp == expected_cmp);
650 : :
651 [ + + ]: 13 : if (cmp) {
652 : 8 : const int rcmp = exess_bigint_compare(&rhs, &lhs);
653 [ - + ]: 8 : assert(rcmp == -cmp);
654 : : }
655 : 13 : }
656 : :
657 : : static void
658 : 1 : test_compare(void)
659 : : {
660 : 1 : check_compare("1", "1", 0);
661 : 1 : check_compare("0", "1", -1);
662 : 1 : check_compare("F", "FF", -1);
663 : 1 : check_compare("F", "FFFFFFFFF", -1);
664 : 1 : check_compare("10000000000000000", "10000000000000000", 0);
665 : 1 : check_compare("10000000000000000", "10000000000000001", -1);
666 : 1 : check_compare("FFFFFFFFFFFFFFFFF", "100000000000000000", -1);
667 : 1 : check_compare("10000000000000000", "10000000000000001", -1);
668 : 1 : check_compare("1234567890ABCDEF12345", "1234567890ABCDEF12345", 0);
669 : 1 : check_compare("1234567890ABCDEF12345", "1234567890ABCDEF12346", -1);
670 : :
671 : 1 : const char* const huge = "123456789ABCDEF0123456789ABCDEF0"
672 : : "123456789ABCDEF0123456789ABCDEF0"
673 : : "123456789ABCDEF0123456789ABCDEF0"
674 : : "123456789ABCDEF0123456789ABCDEF0";
675 : :
676 : 1 : const char* const huger = "123456789ABCDEF0123456789ABCDEF0"
677 : : "123456789ABCDEF0123456789ABCDEF0"
678 : : "123456789ABCDEF0123456789ABCDEF0"
679 : : "123456789ABCDEF0123456789ABCDEF1";
680 : :
681 : 1 : check_compare(huge, huge, 0);
682 : 1 : check_compare(huger, huger, 0);
683 : 1 : check_compare(huge, huger, -1);
684 : 1 : }
685 : :
686 : : static void
687 : 29 : check_plus_compare(const char* l_hex,
688 : : const char* p_hex,
689 : : const char* c_hex,
690 : : const int expected_cmp)
691 : : {
692 : 29 : const ExessBigint l = bigint_from_hex(l_hex);
693 : 29 : const ExessBigint p = bigint_from_hex(p_hex);
694 : 29 : const ExessBigint c = bigint_from_hex(c_hex);
695 : 29 : const int cmp = exess_bigint_plus_compare(&l, &p, &c);
696 : 29 : const int rcmp = exess_bigint_plus_compare(&p, &l, &c);
697 : :
698 [ - + ]: 29 : assert(cmp == expected_cmp);
699 [ - + ]: 29 : assert(rcmp == expected_cmp);
700 : 29 : }
701 : :
702 : : static void
703 : 1 : test_plus_compare(void)
704 : : {
705 : 1 : check_plus_compare("1", "0", "1", 0);
706 : 1 : check_plus_compare("0", "0", "1", -1);
707 : 1 : check_plus_compare("FFFFFFFFF", "F", "F", 1);
708 : 1 : check_plus_compare("F", "F", "800000000", -1);
709 : 1 : check_plus_compare("F", "F", "80000000000000000", -1);
710 : 1 : check_plus_compare("800000000", "F", "80000000000000000", -1);
711 : 1 : check_plus_compare("2D79883D20000", "2D79883D20000", "5AF3107A40000", 0);
712 : 1 : check_plus_compare("20000000000000", "1", "20000000000000", +1);
713 : :
714 : 1 : check_plus_compare(
715 : : "0588A503282FE00000", "0588A503282FE00000", "0AD78EBC5AC6200000", +1);
716 : :
717 : 1 : check_plus_compare("2F06018572BEADD1280000000",
718 : : "0204FCE5E3E25026110000000",
719 : : "4000000000000000000000000",
720 : : -1);
721 : :
722 : 1 : check_plus_compare("1234567890ABCDEF12345",
723 : : "000000000000000000001",
724 : : "1234567890ABCDEF12345",
725 : : +1);
726 : :
727 : 1 : check_plus_compare("1234567890ABCDEF12344",
728 : : "000000000000000000001",
729 : : "1234567890ABCDEF12345",
730 : : 0);
731 : :
732 : 1 : check_plus_compare("123456789000000000000",
733 : : "0000000000ABCDEF12345",
734 : : "1234567890ABCDEF12345",
735 : : 0);
736 : :
737 : 1 : check_plus_compare("123456789000000000000",
738 : : "0000000000ABCDEF12344",
739 : : "1234567890ABCDEF12345",
740 : : -1);
741 : :
742 : 1 : check_plus_compare("123456789000000000000",
743 : : "0000000000ABCDEF12346",
744 : : "1234567890ABCDEF12345",
745 : : 1);
746 : :
747 : 1 : check_plus_compare("123456789100000000000",
748 : : "0000000000ABCDEF12345",
749 : : "1234567890ABCDEF12345",
750 : : 1);
751 : :
752 : 1 : check_plus_compare("123456788900000000000",
753 : : "0000000000ABCDEF12345",
754 : : "1234567890ABCDEF12345",
755 : : -1);
756 : :
757 : 1 : check_plus_compare("12345678900000000000000000000",
758 : : "0000000000ABCDEF1234500000000",
759 : : "1234567890ABCDEF1234500000000",
760 : : 0);
761 : :
762 : 1 : check_plus_compare("12345678900000000000000000000",
763 : : "0000000000ABCDEF1234400000000",
764 : : "1234567890ABCDEF1234500000000",
765 : : -1);
766 : :
767 : 1 : check_plus_compare("12345678900000000000000000000",
768 : : "0000000000ABCDEF1234600000000",
769 : : "1234567890ABCDEF1234500000000",
770 : : 1);
771 : :
772 : 1 : check_plus_compare("12345678910000000000000000000",
773 : : "0000000000ABCDEF1234500000000",
774 : : "1234567890ABCDEF1234500000000",
775 : : 1);
776 : 1 : check_plus_compare("12345678890000000000000000000",
777 : : "0000000000ABCDEF1234500000000",
778 : : "1234567890ABCDEF1234500000000",
779 : : -1);
780 : :
781 : 1 : check_plus_compare("12345678900000000000000000000",
782 : : "000000000000000000ABCDEF12345",
783 : : "123456789000000000ABCDEF12345",
784 : : 0);
785 : :
786 : 1 : check_plus_compare("12345678900000000000000000000",
787 : : "000000000000000000ABCDEF12346",
788 : : "123456789000000000ABCDEF12345",
789 : : 1);
790 : :
791 : 1 : check_plus_compare("12345678900000000000000000000",
792 : : "000000000000000000ABCDEF12344",
793 : : "123456789000000000ABCDEF12345",
794 : : -1);
795 : :
796 : 1 : check_plus_compare("12345678900000000000000000000",
797 : : "000000000000000000ABCDEF12345",
798 : : "12345678900000ABCDEF123450000",
799 : : -1);
800 : :
801 : 1 : check_plus_compare("12345678900000000000000000000",
802 : : "000000000000000000ABCDEF12344",
803 : : "12345678900000ABCDEF123450000",
804 : : -1);
805 : :
806 : 1 : check_plus_compare("12345678900000000000000000000",
807 : : "000000000000000000ABCDEF12345",
808 : : "12345678900000ABCDEF123450001",
809 : : -1);
810 : :
811 : 1 : check_plus_compare("12345678900000000000000000000",
812 : : "00000000000000ABCDEF123460000",
813 : : "12345678900000ABCDEF123450000",
814 : : 1);
815 : 1 : }
816 : :
817 : : static void
818 : 8 : check_pow10(const unsigned exponent, const char* expected)
819 : : {
820 : : ExessBigint num;
821 : 8 : exess_bigint_set_pow10(&num, exponent);
822 [ - + ]: 8 : CHECK_HEXEQ(expected, &num);
823 : 8 : }
824 : :
825 : : static void
826 : 1 : test_set_pow10(void)
827 : : {
828 : 1 : check_pow10(0, "1");
829 : 1 : check_pow10(1, "A");
830 : 1 : check_pow10(2, "64");
831 : 1 : check_pow10(5, "186A0");
832 : 1 : check_pow10(8, "5F5E100");
833 : 1 : check_pow10(16, "2386F26FC10000");
834 : 1 : check_pow10(30, "C9F2C9CD04674EDEA40000000");
835 : 1 : check_pow10(31, "7E37BE2022C0914B2680000000");
836 : 1 : }
837 : :
838 : : int
839 : 1 : main(void)
840 : : {
841 : 1 : test_set();
842 : 1 : test_left_shifted_bigit();
843 : 1 : test_shift_left();
844 : 1 : test_add_u32();
845 : 1 : test_add();
846 : 1 : test_subtract();
847 : 1 : test_subtract_left_shifted();
848 : 1 : test_multiply_u32();
849 : 1 : test_multiply_u64();
850 : 1 : test_multiply_pow10();
851 : 1 : test_divmod();
852 : 1 : test_compare();
853 : 1 : test_plus_compare();
854 : 1 : test_set_pow10();
855 : :
856 : 1 : return 0;
857 : : }
|
