Wire Sysio Wire Sysion 1.0.0
Loading...
Searching...
No Matches
test_zm.cpp
Go to the documentation of this file.
1#include <stdio.h>
2#include "zm.h"
3#include <iostream>
4#include <sstream>
5#include <cybozu/benchmark.hpp>
6
7using namespace mie;
8
9#define NUM_OF_ARRAY(x) (sizeof(x) / sizeof(*x))
10
11static int s_errNum = 0;
12static int s_testNum = 0;
13
14#define TEST_EQUAL(x, y) { s_testNum++; if (x != y) { s_errNum++; printf("%s(%d): err %s != %s\n", __FILE__, __LINE__, #x, #y); std::cout << "lhs=" << (x) << "\nrhs=" << (y) << std::endl; } }
15#define TEST_ASSERT(x) { s_testNum++; if (!(x)) { s_errNum++; printf("%s(%d): err assert %s\n", __FILE__, __LINE__, #x); } }
16
17#define FATAL_EXIT(msg) { printf("%s(%d): err %s\n", __FILE__, __LINE__, msg); exit(1); }
18
19struct V {
20 int n;
21 unsigned int p[16];
22};
23
24void testAddSub()
25{
26 static const struct {
27 V a;
28 V b;
29 V c;
30 } tbl[] = {
31 {
32 { 1, { 123, } },
33 { 1, { 456, } },
34 { 1, { 579, } },
35 },
36 {
37 { 1, { 0xffffffff, } },
38 { 1, { 3, } },
39 { 2, { 2, 1 } },
40 },
41 {
42 { 3, { 0xffffffff, 1, 0xffffffff } },
43 { 2, { 1, 0xfffffffe, } },
44 { 4, { 0, 0, 0, 1 } },
45 },
46 {
47 { 3, { 0xffffffff, 5, 0xffffffff } },
48 { 2, { 1, 0xfffffffe, } },
49 { 4, { 0, 4, 0, 1 } },
50 },
51 {
52 { 3, { 0xffffffff, 5, 0xffffffff } },
53 { 1, { 1, } },
54 { 3, { 0, 6, 0xffffffff } },
55 },
56 {
57 { 3, { 1, 0xffffffff, 1 } },
58 { 3, { 0xffffffff, 0, 1 } },
59 { 3, { 0, 0, 3 } },
60 },
61 {
62 { 1, { 1 } },
63 { 3, { 0xffffffff, 0xffffffff, 0xffffffff } },
64 { 4, { 0, 0, 0, 1 } },
65 },
66 {
67 { 1, { 0xffffffff } },
68 { 1, { 0xffffffff } },
69 { 2, { 0xfffffffe, 1 } },
70 },
71 {
72 { 2, { 0xffffffff, 0xffffffff } },
73 { 2, { 0xffffffff, 0xffffffff } },
74 { 3, { 0xfffffffe, 0xffffffff, 1 } },
75 },
76 {
77 { 3, { 0xffffffff, 0xffffffff, 0xffffffff } },
78 { 3, { 0xffffffff, 0xffffffff, 0xffffffff } },
79 { 4, { 0xfffffffe, 0xffffffff, 0xffffffff, 1 } },
80 },
81 {
82 { 4, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
83 { 4, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
84 { 5, { 0xfffffffe, 0xffffffff, 0xffffffff, 0xffffffff, 1 } },
85 },
86 {
87 { 5, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
88 { 5, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
89 { 6, { 0xfffffffe, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 1 } },
90 },
91 {
92 { 6, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
93 { 6, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
94 { 7, { 0xfffffffe, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 1 } },
95 },
96 {
97 { 7, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
98 { 8, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
99 { 8, { 0xfffffffe, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 1 } },
100 },
101 {
102 { 8, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
103 { 8, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
104 { 9, { 0xfffffffe, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 1 } },
105 },
106 {
107 { 9, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
108 { 9, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
109 {10, { 0xfffffffe, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 1 } },
110 },
111 {
112 {10, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
113 {10, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
114 {11, { 0xfffffffe, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 1 } },
115 },
116 {
117 {11, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
118 {11, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
119 {12, { 0xfffffffe, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 1 } },
120 },
121 {
122 {12, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
123 {12, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
124 {13, { 0xfffffffe, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 1 } },
125 },
126 {
127 {13, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
128 {13, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
129 {14, { 0xfffffffe, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 1 } },
130 },
131 };
132 for (size_t i = 0; i < NUM_OF_ARRAY(tbl); i++) {
133 Vuint x, y, z, t;
134 x.set(tbl[i].a.p, tbl[i].a.n);
135 y.set(tbl[i].b.p, tbl[i].b.n);
136 z.set(tbl[i].c.p, tbl[i].c.n);
137 Vuint::add(t, x, y);
138 TEST_EQUAL(t, z);
139
140 Vuint::add(t, y, x);
141 TEST_EQUAL(t, z);
142
143 Vuint::sub(t, z, x);
144 TEST_EQUAL(t, y);
145 }
146 {
147 const uint32_t in[] = { 0xffffffff, 0xffffffff };
148 const uint32_t out[] = { 0xfffffffe, 0xffffffff, 1 };
149 Vuint x, y;
150 x.set(in, 2);
151 y.set(out, 3);
152 Vuint::add(x, x, x);
153 TEST_EQUAL(x, y);
154 Vuint::sub(x, x, x);
155 y.clear();
156 TEST_EQUAL(x, y);
157 }
158 {
159 const uint32_t t0[] = {1, 2};
160 const uint32_t t1[] = {3, 4, 5};
161 const uint32_t t2[] = {4, 6, 5};
162 Vuint x, y, z;
163 z.set(t2, 3);
164
165 x.set(t0, 2);
166 y.set(t1, 3);
167 Vuint::add(x, x, y);
168 TEST_EQUAL(x, z);
169
170 x.set(t0, 2);
171 y.set(t1, 3);
172 Vuint::add(x, y, x);
173 TEST_EQUAL(x, z);
174
175 x.set(t0, 2);
176 y.set(t1, 3);
177 Vuint::add(y, x, y);
178 TEST_EQUAL(y, z);
179
180 x.set(t0, 2);
181 y.set(t1, 3);
182 Vuint::add(y, y, x);
183 TEST_EQUAL(y, z);
184 }
185}
186
187void testMul1()
188{
189 static const struct {
190 V a;
191 unsigned int b;
192 V c;
193 } tbl[] = {
194 {
195 { 1, { 12, } },
196 5,
197 { 1, { 60, } },
198 },
199 {
200 { 1, { 1234567, } },
201 1,
202 { 1, { 1234567, } },
203 },
204 {
205 { 1, { 1234567, } },
206 89012345,
207 { 2, { 0x27F6EDCF, 0x63F2, } },
208 },
209 {
210 { 3, { 0xffffffff, 0xffffffff, 0xffffffff, } },
211 0xffffffff,
212 { 4, { 0x00000001, 0xffffffff, 0xffffffff, 0xfffffffe } },
213 },
214 {
215 { 3, { 0xffffffff, 0xffffffff, 0xffffffff, } },
216 1,
217 { 3, { 0xffffffff, 0xffffffff, 0xffffffff, } },
218 },
219 {
220 { 2, { 0xffffffff, 1 } },
221 0xffffffff,
222 { 3, { 0x00000001, 0xfffffffd, 1 } },
223 },
224 };
225 for (size_t i = 0; i < NUM_OF_ARRAY(tbl); i++) {
226 Vuint x, z, t;
227 unsigned int y;
228 x.set(tbl[i].a.p, tbl[i].a.n);
229 y = tbl[i].b;
230 z.set(tbl[i].c.p, tbl[i].c.n);
231 Vuint::mul(t, x, y);
232 TEST_EQUAL(t, z);
233
234 Vuint::mul(x, x, y);
235 TEST_EQUAL(x, z);
236 }
237}
238
239void testMul2()
240{
241 static const struct {
242 V a;
243 V b;
244 V c;
245 } tbl[] = {
246 {
247 { 1, { 12, } },
248 { 1, { 5, } },
249 { 1, { 60, } },
250 },
251 {
252 { 1, { 1234567, } },
253 { 1, { 89012345, } },
254 { 2, { 0x27F6EDCF, 0x63F2, } },
255 },
256 {
257 { 3, { 0xffffffff, 0xffffffff, 0xffffffff, } },
258 { 1, { 0xffffffff, } },
259 { 4, { 0x00000001, 0xffffffff, 0xffffffff, 0xfffffffe } },
260 },
261 {
262 { 2, { 0xffffffff, 1 } },
263 { 1, { 0xffffffff, } },
264 { 3, { 0x00000001, 0xfffffffd, 1 } },
265 },
266 {
267 { 2, { 0xffffffff, 1 } },
268 { 1, { 0xffffffff, } },
269 { 3, { 0x00000001, 0xfffffffd, 1 } },
270 },
271 {
272 { 2, { 1, 1 } },
273 { 2, { 1, 1 } },
274 { 3, { 1, 2, 1 } },
275 },
276 {
277 { 3, { 0xffffffff, 0xffffffff, 1 } },
278 { 2, { 0xffffffff, 0xffffffff } },
279 { 5, { 1, 0, 0xfffffffd, 0xffffffff, 1 } },
280 },
281 };
282 for (size_t i = 0; i < NUM_OF_ARRAY(tbl); i++) {
283 Vuint x, y, z, t;
284 x.set(tbl[i].a.p, tbl[i].a.n);
285 y.set(tbl[i].b.p, tbl[i].b.n);
286 z.set(tbl[i].c.p, tbl[i].c.n);
287 Vuint::mul(t, x, y);
288 TEST_EQUAL(t, z);
289
290 Vuint::mul(t, y, x);
291 TEST_EQUAL(t, z);
292 }
293 {
294 const uint32_t in[] = { 0xffffffff, 1 };
295 const uint32_t out[] = { 1, 0xfffffffc, 3 };
296 Vuint x, y, z;
297 y.set(out, 3);
298 x.set(in, 2);
299 z = x;
300 Vuint::mul(x, x, x);
301 TEST_EQUAL(x, y);
302
303 x.set(in, 2);
304 Vuint::mul(x, x, z);
305 TEST_EQUAL(x, y);
306
307 x.set(in, 2);
308 Vuint::mul(x, z, x);
309 TEST_EQUAL(x, y);
310
311 x.set(in, 2);
312 Vuint::mul(x, z, z);
313 TEST_EQUAL(x, y);
314 }
315 {
316 Vuint a("285434247217355341057");
317 a *= a;
318 TEST_EQUAL(a, Vuint("81472709484538325259309302444004789877249"));
319 }
320}
321
322void testDiv1()
323{
324 static const struct {
325 V a;
326 unsigned int b;
327 unsigned int r;
328 V c;
329 } tbl[] = {
330 {
331 { 1, { 100, } },
332 1, 0,
333 { 1, { 100, } },
334 },
335 {
336 { 1, { 100, } },
337 100, 0,
338 { 1, { 1, } },
339 },
340 {
341 { 1, { 100, } },
342 101, 100,
343 { 1, { 0, } },
344 },
345 {
346 { 1, { 100, } },
347 2, 0,
348 { 1, { 50, } },
349 },
350 {
351 { 1, { 100, } },
352 3, 1,
353 { 1, { 33, } },
354 },
355 {
356 { 2, { 0xffffffff, 0xffffffff } },
357 1, 0,
358 { 2, { 0xffffffff, 0xffffffff, } },
359 },
360 {
361 { 2, { 0xffffffff, 0xffffffff } },
362 123, 15,
363 { 2, { 0x4d0214d0, 0x214d021 } },
364 },
365 };
366 for (size_t i = 0; i < NUM_OF_ARRAY(tbl); i++) {
367 Vuint x, z, t;
368 unsigned int b, r, u;
369 x.set(tbl[i].a.p, tbl[i].a.n);
370 b = tbl[i].b;
371 r = tbl[i].r;
372 z.set(tbl[i].c.p, tbl[i].c.n);
373
374 u = (unsigned int)Vuint::div1(&t, x, b);
375 TEST_EQUAL(t, z);
376 TEST_EQUAL(u, r);
377
378 u = (unsigned int)Vuint::div1(&x, x, b);
379 TEST_EQUAL(x, z);
380 TEST_EQUAL(u, r);
381 }
382}
383
384
385
386void testDiv2()
387{
388 static const struct {
389 V x;
390 V y;
391 V q;
392 V r;
393 } tbl[] = {
394 {
395 { 1, { 100 } },
396 { 1, { 3 } },
397 { 1, { 33 } },
398 { 1, { 1 } },
399 },
400 {
401 { 2, { 1, 1 } },
402 { 2, { 0, 1 } },
403 { 1, { 1 } },
404 { 1, { 1 } },
405 },
406 {
407 { 2, { 0xffffffff, 0xffffffff } },
408 { 2, { 0, 1 } },
409 { 1, { 0xffffffff } },
410 { 1, { 0xffffffff } },
411 },
412 {
413 { 2, { 0xffffffff, 0xffffffff } },
414 { 2, { 0xffffffff, 1 } },
415 { 1, { 0x80000000 } },
416 { 1, { 0x7fffffff } },
417 },
418 {
419 { 3, { 0xffffffff, 0xffffffff, 0xffffffff } },
420 { 2, { 0xffffffff, 1 } },
421 { 2, { 0x40000000, 0x80000000 } },
422 { 1, { 0x3fffffff } },
423 },
424 {
425 { 4, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
426 { 3, { 1, 0, 1 } },
427 { 2, { 0xffffffff, 0xffffffff } },
428 { 1, { 0 } },
429 },
430 {
431 { 4, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
432 { 3, { 1, 0xffffffff, 0xffffffff } },
433 { 2, { 0, 1 } },
434 { 2, { 0xffffffff, 0xfffffffe } },
435 },
436 {
437 { 4, { 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff } },
438 { 3, { 1, 0, 0xffffffff } },
439 { 2, { 1, 1 } },
440 { 2, { 0xfffffffe, 0xfffffffe } },
441 },
442 {
443 { 4, { 0xffffffff, 0xffffffff, 0xffffffff, 1 } },
444 { 3, { 1, 0, 0xffffffff } },
445 { 1, { 2 } },
446 { 3, { 0xfffffffd, 0xffffffff, 1 } },
447 },
448 {
449 { 4, { 0, 0, 1, 1 } },
450 { 2, { 1, 1 } },
451 { 3, { 0, 0, 1 } },
452 { 1, { 0 } },
453 },
454 {
455 { 3, { 5, 5, 1} },
456 { 2, { 1, 2 } },
457 { 1, { 0x80000002 } },
458 { 1, { 0x80000003, } },
459 },
460 {
461 { 2, { 5, 5} },
462 { 2, { 1, 1 } },
463 { 1, { 5 } },
464 { 1, { 0, } },
465 },
466 {
467 { 2, { 5, 5} },
468 { 2, { 2, 1 } },
469 { 1, { 4 } },
470 { 1, { 0xfffffffd, } },
471 },
472 {
473 { 3, { 5, 0, 5} },
474 { 3, { 2, 0, 1 } },
475 { 1, { 4 } },
476 { 2, { 0xfffffffd, 0xffffffff } },
477 },
478 {
479 { 2, { 4, 5 } },
480 { 2, { 5, 5 } },
481 { 1, { 0 } },
482 { 2, { 4, 5 } },
483 },
484 };
485 for (size_t i = 0; i < NUM_OF_ARRAY(tbl); i++) {
486 Vuint x, y, q, r;
487 x.set(tbl[i].x.p, tbl[i].x.n);
488 y.set(tbl[i].y.p, tbl[i].y.n);
489 q.set(tbl[i].q.p, tbl[i].q.n);
490 r.set(tbl[i].r.p, tbl[i].r.n);
491
492 Vuint qt, rt;
493 Vuint::div(&qt, rt, x, y);
494 TEST_EQUAL(qt, q);
495 TEST_EQUAL(rt, r);
496
497 Vuint::mul(y, y, qt);
498 Vuint::add(y, y, rt);
499 TEST_EQUAL(x, y);
500
501 x.set(tbl[i].x.p, tbl[i].x.n);
502 y.set(tbl[i].y.p, tbl[i].y.n);
503 Vuint::div(&x, rt, x, y);
504 TEST_EQUAL(x, q);
505 TEST_EQUAL(rt, r);
506
507 x.set(tbl[i].x.p, tbl[i].x.n);
508 y.set(tbl[i].y.p, tbl[i].y.n);
509 Vuint::div(&y, rt, x, y);
510 TEST_EQUAL(y, q);
511 TEST_EQUAL(rt, r);
512
513 x.set(tbl[i].x.p, tbl[i].x.n);
514 y.set(tbl[i].y.p, tbl[i].y.n);
515 Vuint::div(&x, y, x, y);
516 TEST_EQUAL(x, q);
517 TEST_EQUAL(y, r);
518
519 x.set(tbl[i].x.p, tbl[i].x.n);
520 y.set(tbl[i].y.p, tbl[i].y.n);
521 Vuint::div(&y, x, x, y);
522 TEST_EQUAL(y, q);
523 TEST_EQUAL(x, r);
524 }
525 {
526 const uint32_t in[] = { 1, 1 };
527 Vuint x, y, z;
528 x.set(in, 2);
529 Vuint::div(&x, y, x, x);
530 z.set(1);
531 TEST_EQUAL(x, z);
532 z.clear();
533 TEST_EQUAL(y, z);
534
535 Vuint::div(&y, x, x, x);
536 z.set(1);
537 TEST_EQUAL(y, z);
538 z.clear();
539 TEST_EQUAL(x, z);
540 }
541}
542
543void testDiv3()
544{
545 const struct {
546 const char *x;
547 const char *y;
548 const char *r;
549 } tbl[] = {
550 {
551 "1448106640508192452750709206294683535529268965445799785581837640324321797831381715960812126274894517677713278300997728292641936248881345120394299128611830",
552 "82434016654300679721217353503190038836571781811386228921167322412819029493183",
553 "72416512377294697540770834088766459385112079195086911762075702918882982361282"
554 },
555 {
556 "97086308670107713719105336221824613370040805954034005192338040686500414395543303807941158656814978071549225072789349941064484974666540443679601226744652",
557 "82434016654300679721217353503190038836571781811386228921167322412819029493183",
558 "41854959563040430269871677548536437787164514279279911478858426970427834388586",
559 },
560 {
561 "726838724295606887174238120788791626017347752989142414466410919788841485181240131619880050064495352797213258935807786970844241989010252",
562 "82434016654300679721217353503190038836571781811386228921167322412819029493183",
563 "81378967132566843036693176764684783485107373533583677681931133755003929106966",
564 },
565 {
566 "85319207237201203511459960875801690195851794174784746933408178697267695525099750",
567 "82434016654300679721217353503190038836571781811386228921167322412819029493183",
568 "82434016654300679721217353503190038836571781811386228921167322412819029148528",
569 },
570 {
571 "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
572 "0x100000000000000000000000000000000000000000000000001",
573 "1606938044258990275541962092341162602522202993782724115824640",
574 },
575 {
576 "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
577 "0x1000000000000000000000000000000000000000000000000000000000000000000000000000000001",
578 "34175792574734561318320347298712833833643272357332299899995954578095372295314880347335474659983360",
579 },
580 {
581 "0xfffffffffffff000000000000000000000000000000000000000000000000000000000000000000",
582 "0x100000000000000000000000000000000000000000000000000000000000000000001",
583 "7558907585412001237250713901367146624661464598973016020495791084036551510708977665",
584 },
585 {
586 "0xfffffffffffff000000000000000000000000000000000000000000000000000000000000000000",
587 "0xfffffffffffff0000000000000000000000000000000000000000000000000000000000000001",
588 "521481209941628322292632858916605385658190900090571826892867289394157573281830188869820088065",
589 },
590 };
591 mie::Vuint x, y, r;
592 for (size_t i = 0; i < NUM_OF_ARRAY(tbl); i++) {
593 x.set(tbl[i].x);
594 y.set(tbl[i].y);
595 r.set(tbl[i].r);
596 x %= y;
597 TEST_EQUAL(x, r);
598 }
599}
600
601void testString()
602{
603 const struct {
604 uint32_t v[5];
605 size_t vn;
606 const char *str;
607 const char *hex;
608 } tbl[] = {
609 { { 0 }, 0, "0", "0x0" },
610 { { 12345 }, 1, "12345", "0x3039" },
611 { { 0xffffffff }, 1, "4294967295", "0xffffffff" },
612 { { 0, 1 }, 2, "4294967296", "0x100000000" },
613 { { 0, 0, 0, 0, 1 }, 5, "340282366920938463463374607431768211456", "0x100000000000000000000000000000000" },
614 };
615 for (size_t i = 0; i < NUM_OF_ARRAY(tbl); i++) {
616 Vuint x, y;
617 x.set(tbl[i].v,tbl[i].vn);
618 TEST_EQUAL(x.toString(10), tbl[i].str);
619 y.set(tbl[i].str);
620 TEST_EQUAL(x, y);
621 x = 1;
622 x.set(tbl[i].hex);
623 TEST_EQUAL(x, y);
624 }
625}
626
627void testZmZ()
628{
629 const Vuint m = 13;
630 ZmZ<>::setModulo(m);
631 TEST_EQUAL(ZmZ<>::getModulo(), m);
632 ZmZ<> x(2);
633 x *= 10;
634 TEST_EQUAL(x, 7);
635 x -= 10;
636 TEST_EQUAL(x, 10);
637 x = -1;
638 TEST_EQUAL(x, 12);
639 x = 4;
640 x.inverse();
641 TEST_EQUAL(x, 10);
642}
643
644void testZmZsub()
645{
646 const uint32_t tbl1[] = { 0, 0, 1 };
647 const uint32_t tbl2[] = { 0, 1 };
648 const uint32_t tbl3[] = { 1, 0xffffffff };
649 Vuint m;
650 m.set(tbl1, 3);
651 ZmZ<>::setModulo(m);
652 ZmZ<> x, y, z;
653 x = 1;
654 y.set(tbl2, 2);
655 x = x - y;
656 z.set(tbl3, 2);
657 TEST_EQUAL(x, z);
658 x = 0;
659 y = 4;
660 ZmZ<>::sub(y, x, y);
661 TEST_EQUAL(y, ZmZ<>("0xfffffffffffffffc"));
662}
663
664void testInverse()
665{
666 const Vuint m("1461501637330902918203684832716283019655932542983");
667 ZmZ<>::setModulo(m);
668 ZmZ<> x, y, z;
669 x = 1;
670 y.set("1461501637330902918203684832716283019655932542927");
671 y = x - y;
672 TEST_EQUAL(y, 57);
673 x.set("51309926569953339959415154564163853983901484416");
674 y = x;
675 y.inverse();
676 z.set("123456789");
677 TEST_EQUAL(y, z);
678 z = 1 / z;
679 TEST_EQUAL(z, x);
680 y = 3;
681 y /= x;
682 z.set("370370367");
683 TEST_EQUAL(y, z);
684}
685
686void testPow()
687{
688 Vuint m = 2, d = 2;
689 for (size_t i = 0; i < 160 - 1; i++) {
690 m *= d;
691 }
692 m += 7;
693 ZmZ<>::setModulo(m);
694 TEST_EQUAL(m, Vuint("1461501637330902918203684832716283019655932542983"));
695
696 ZmZ<> x, y = ZmZ<>(m) - 1;
697 x = 3;
698 x = mie::power(x, y);
699 TEST_EQUAL(x, 1);
700 CYBOZU_BENCH("power", x = mie::power, x, y);
701}
702
703void testShift()
704{
705 Vuint x("123423424918471928374192874198274981274918274918274918243");
706 Vuint y, z;
707
708 // shl
709 for (size_t i = 1; i < sizeof(mie::Unit) * 8; i++) {
710 Vuint::shlBit(y, x, i);
711 z = x * (mie::Unit(1) << i);
712 TEST_EQUAL(y, z);
713 y = x << i;
714 TEST_EQUAL(y, z);
715 y = x;
716 y <<= i;
717 TEST_EQUAL(y, z);
718 }
719 for (size_t i = 0; i < 4; i++) {
720 Vuint::shlUnit(y, x, i);
721 Vuint s = power(Vuint(2), Vuint(i * sizeof(mie::Unit) * 8));
722 z = x * s;
723 TEST_EQUAL(y, z);
724 y = x << (i * sizeof(mie::Unit) * 8);
725 TEST_EQUAL(y, z);
726 y = x;
727 y <<= (i * sizeof(mie::Unit) * 8);
728 TEST_EQUAL(y, z);
729 }
730 for (size_t i = 0; i < 100; i++) {
731 y = x << i;
732 Vuint s = power(Vuint(2), Vuint(i));
733 z = x * s;
734 TEST_EQUAL(y, z);
735 y = x;
736 y <<= i;
737 TEST_EQUAL(y, z);
738 }
739
740 // shr
741 for (size_t i = 1; i < sizeof(mie::Unit) * 8; i++) {
742 Vuint::shrBit(y, x, i);
743 z = x / (mie::Unit(1) << i);
744 TEST_EQUAL(y, z);
745 y = x >> i;
746 TEST_EQUAL(y, z);
747 y = x;
748 y >>= i;
749 TEST_EQUAL(y, z);
750 }
751 for (size_t i = 0; i < 3; i++) {
752 Vuint::shrUnit(y, x, i);
753 Vuint s = power(Vuint(2), Vuint(i * sizeof(mie::Unit) * 8));
754 z = x / s;
755 TEST_EQUAL(y, z);
756 y = x >> (i * sizeof(mie::Unit) * 8);
757 TEST_EQUAL(y, z);
758 y = x;
759 y >>= (i * sizeof(mie::Unit) * 8);
760 TEST_EQUAL(y, z);
761 }
762 for (size_t i = 0; i < 100; i++) {
763 y = x >> i;
764 Vuint s = power(Vuint(2), Vuint(i));
765 z = x / s;
766 TEST_EQUAL(y, z);
767 y = x;
768 y >>= i;
769 TEST_EQUAL(y, z);
770 }
771 {
772 Vuint a = 0, zero = 0;
773 a <<= sizeof(Vuint::T) * 8;
774 TEST_EQUAL(a, zero);
775 }
776}
777
778void testBitLen()
779{
780 {
781 Vuint zero = 0;
782 TEST_EQUAL(zero.bitLen(), 0);
783 zero <<= (sizeof(Vuint::T)*8 - 1);
784 TEST_EQUAL(zero.bitLen(), 0);
785 zero <<= (sizeof(Vuint::T)*8);
786 TEST_EQUAL(zero.bitLen(), 0);
787 }
788
789 {
790 Vuint a = 1;
791 TEST_EQUAL(a.bitLen(), 1);
792 a = 2;
793 TEST_EQUAL(a.bitLen(), 2);
794 a = 3;
795 TEST_EQUAL(a.bitLen(), 2);
796 a = 4;
797 TEST_EQUAL(a.bitLen(), 3);
798 }
799
800 {
801 Vuint a = 5;
802 const size_t msbindex = a.bitLen();
803 const size_t width = 100;
804 const size_t time = 3;
805 for (size_t i = 0; i < time; ++i) {
806 a <<= width;
807 TEST_EQUAL(a.bitLen(), msbindex + width*(i + 1));
808 }
809
810 for (size_t i = 0; i < time*2; ++i) {
811 a >>= width/2;
812 TEST_EQUAL(a.bitLen(), msbindex + width*time - (width/2)*(i + 1));
813 }
814 a >>= width;
815 TEST_EQUAL(a.bitLen(), 0);
816 }
817
818 {
819 Vuint b("12"), c("345"), d("67890");
820 size_t bl = b.bitLen(), cl = c.bitLen(), dl = d.bitLen();
821 TEST_ASSERT((b*c).bitLen() <= bl + cl);
822 TEST_ASSERT((c*d).bitLen() <= cl + dl);
823 TEST_ASSERT((b*c*d).bitLen() <= bl + cl + dl);
824 }
825}
826
827void testTestBit()
828{
829 {
830 Vuint a;
831 a.set("0x1234567890abcdef");
832 bool tvec[] = {
833 1,1,1,1,0 ,1,1,1,1,0
834 ,1,1,0,0,1 ,1,1,1,0,1
835 ,0,1,0,1,0 ,0,0,0,1,0
836 ,0,1,0,0,0 ,1,1,1,1,0
837 ,0,1,1,0,1 ,0,1,0,0,0
838 ,1,0,1,1,0 ,0,0,1,0,0
839 ,1
840 };
841 TEST_EQUAL(a.bitLen(), sizeof(tvec)/sizeof(*tvec));
842 for (int i = (int)a.bitLen() - 1; i >= 0; --i) {
843 TEST_EQUAL(a.testBit(i), tvec[i]);
844 }
845 }
846}
847
848void bench()
849{
850 Vuint m("16798108731015832284940804142231733909759579603404752749028378864165570215949");
851 ZmZ<>::setModulo(m);
852 const char *str = "82434016654300679721217353503190038836571781811386228921167322412819029493182";
853 Vuint a(str), b(a);
854 CYBOZU_BENCH("Vuint:mul", Vuint::mul, b, a, a);
855}
856
857void sample()
858{
859 using namespace mie;
860 Vuint x(1);
861 Vuint y("123456789");
862 Vuint z;
863
864 x = 1; // set by int
865 y.set("123456789"); // set by decimal
866 z.set("0xffffffff"); // set by hex
867 x += z;
868
869 x = 2;
870 y = 250;
871 x = power(x, y);
872 Vuint r, q;
873 r = x % y;
874 q = x / y;
875 TEST_EQUAL(q * y + r, x);
876
877 Vuint::div(&q, r, x, y); // get both r and q
878 TEST_EQUAL(q * y + r, x);
879
880 Vuint m;
881 m = power(Vuint(2), Vuint(160)) + Vuint(7);
882 ZmZ<>::setModulo(m);
883 ZmZ<> a, b(m - 1);
884 a = 3;
885 a = power(a, b);
886 TEST_EQUAL(a, 1);
887}
888
889void testVsint()
890{
891 const struct {
892 int a;
893 int b;
894 int add, sub, mul, q, r;
895 } tbl[] = {
896#if 1 // like Python
897 { 13, 5, 18, 8, 65, 2, 3 },
898 { 13, -5, 8, 18, -65, -3, -2 },
899 { -13, 5, -8, -18, -65, -3, 2 },
900 { -13, -5, -18, -8, 65, 2, -3 },
901
902 { 5, 13, 18, -8, 65, 0, 5 },
903 { 5, -13, -8, 18, -65, -1, -8 },
904 { -5, 13, 8, -18, -65, -1, 8 },
905 { -5, -13, -18, 8, 65, 0, -5 },
906#else // like C
907 { 13, 5, 18, 8, 65, 2, 3 },
908 { 13, -5, 8, 18, -65, -2, 3 },
909 { -13, 5, -8, -18, -65, -2, -3 },
910 { -13, -5, -18, -8, 65, 2, -3 },
911
912 { 5, 13, 18, -8, 65, 0, 5 },
913 { 5, -13, -8, 18, -65, 0, 5 },
914 { -5, 13, 8, -18, -65, 0, -5 },
915 { -5, -13, -18, 8, 65, 0, -5 },
916#endif
917 };
918 for (size_t i = 0; i < NUM_OF_ARRAY(tbl); i++) {
919 Vsint a = tbl[i].a;
920 Vsint b = tbl[i].b;
921 Vsint add = a + b;
922 Vsint sub = a - b;
923 Vsint mul = a * b;
924 Vsint q = a / b;
925 Vsint r = a % b;
926 TEST_EQUAL(add, tbl[i].add);
927 TEST_EQUAL(sub, tbl[i].sub);
928 TEST_EQUAL(mul, tbl[i].mul);
929 TEST_EQUAL(q, tbl[i].q);
930 TEST_EQUAL(r, tbl[i].r);
931 TEST_EQUAL(q * b + r, a);
932 }
933 TEST_EQUAL(Vsint("15") / Vsint("3"), Vsint("5"));
934 TEST_EQUAL(Vsint("15") / Vsint("-3"), Vsint("-5"));
935 TEST_EQUAL(Vsint("-15") / Vsint("3"), Vsint("-5"));
936 TEST_EQUAL(Vsint("-15") / Vsint("-3"), Vsint("5"));
937
938 TEST_EQUAL(Vsint("15") % Vsint("3"), Vsint("0"));
939 TEST_EQUAL(Vsint("15") % Vsint("-3"), Vsint("0"));
940 TEST_EQUAL(Vsint("-15") % Vsint("3"), Vsint("0"));
941 TEST_EQUAL(Vsint("-15") % Vsint("-3"), Vsint("0"));
942
943 TEST_EQUAL(Vsint("-0") + Vsint("-3"), Vsint("-3"));
944 TEST_EQUAL(Vsint("-0") - Vsint("-3"), Vsint("3"));
945 TEST_EQUAL(Vsint("-3") + Vsint("-0"), Vsint("-3"));
946 TEST_EQUAL(Vsint("-3") - Vsint("-0"), Vsint("-3"));
947
948 TEST_EQUAL(Vsint("-0") + Vsint("3"), Vsint("3"));
949 TEST_EQUAL(Vsint("-0") - Vsint("3"), Vsint("-3"));
950 TEST_EQUAL(Vsint("3") + Vsint("-0"), Vsint("3"));
951 TEST_EQUAL(Vsint("3") - Vsint("-0"), Vsint("3"));
952
953 TEST_EQUAL(Vsint("0"), Vsint("0"));
954 TEST_EQUAL(Vsint("0"), Vsint("-0"));
955 TEST_EQUAL(Vsint("-0"), Vsint("0"));
956 TEST_EQUAL(Vsint("-0"), Vsint("-0"));
957
958 TEST_ASSERT(Vsint("2") < Vsint("3"));
959 TEST_ASSERT(Vsint("-2") < Vsint("3"));
960 TEST_ASSERT(Vsint("-5") < Vsint("-3"));
961 TEST_ASSERT(Vsint("-0") < Vsint("1"));
962 TEST_ASSERT(Vsint("-1") < Vsint("-0"));
963
964 TEST_ASSERT(Vsint("5") > Vsint("3"));
965 TEST_ASSERT(Vsint("5") > Vsint("-3"));
966 TEST_ASSERT(Vsint("-2") > Vsint("-3"));
967 TEST_ASSERT(Vsint("3") > Vsint("-0"));
968 TEST_ASSERT(Vsint("-0") > Vsint("-1"));
969
970 {
971 const struct {
972 const char *str;
973 int s;
974 int shl;
975 int shr;
976 } tbl[] = {
977 { "0", 1, 0, 0 },
978 { "-0", 1, 0, 0 },
979 { "1", 1, 2, 0 },
980 { "-1", 1, -2, 0 },
981 { "12345", 3, 98760, 1543 },
982 { "-12345", 3, -98760, 0 },
983 };
984 for (size_t i = 0; i < NUM_OF_ARRAY(tbl); i++) {
985 Vsint a = Vsint(tbl[i].str);
986 Vsint shl = a << tbl[i].s;
987 TEST_EQUAL(shl, tbl[i].shl);
988 if (!a.isNegative()) {
989 Vsint shr = a >> tbl[i].s;
990 TEST_EQUAL(shr, tbl[i].shr);
991 }
992 }
993 }
994}
995
996void testAdd2()
997{
998 Vuint x, y, z, w;
999 x.set("2416089439321382744001761632872637936198961520379024187947524965775137204955564426500438089001375107581766516460437532995850581062940399321788596606850");
1000 y.set("2416089439321382743300544243711595219403446085161565705825288050160594425031420687263897209379984490503106207071010949258995096347962762372787916800000");
1001 z.set("701217389161042716795515435217458482122236915614542779924143739236540879621390617078660309389426583736855484714977636949000679806850");
1002 Vuint::sub(w, x, y);
1003 TEST_EQUAL(w, z);
1004
1005 Vsint a, c, d;
1006
1007 a.set("-2416089439321382744001761632872637936198961520379024187947524965775137204955564426500438089001375107581766516460437532995850581062940399321788596606850");
1008 c.set("2416089439321382743300544243711595219403446085161565705825288050160594425031420687263897209379984490503106207071010949258995096347962762372787916800000");
1009 a = a + c;
1010
1011 d.set("-701217389161042716795515435217458482122236915614542779924143739236540879621390617078660309389426583736855484714977636949000679806850");
1012 TEST_EQUAL(a, d);
1013}
1014
1015void testStream()
1016{
1017 {
1018 Vuint x, y, z, w;
1019 x.set("12345678901232342424242423423429922");
1020 y.set("23423423452424242343");
1021 std::ostringstream oss;
1022 oss << x << ' ' << y;
1023 std::istringstream iss(oss.str());
1024 iss >> z >> w;
1025 TEST_EQUAL(x, z);
1026 TEST_EQUAL(y, w);
1027 }
1028 {
1029 Vuint x, y, z, w;
1030 x.set("0x100");
1031 y.set("123");
1032 std::ostringstream oss;
1033 oss << x << ' ' << y;
1034 std::istringstream iss(oss.str());
1035 iss >> z >> w;
1036 TEST_EQUAL(x, z);
1037 TEST_EQUAL(y, w);
1038 }
1039 {
1040 Vsint x, y, z, w;
1041 x.set("12345678901232342424242423423429922");
1042 y.set("-23423423452424242343");
1043 std::ostringstream oss;
1044 oss << x << ' ' << y;
1045 std::istringstream iss(oss.str());
1046 iss >> z >> w;
1047 TEST_EQUAL(x, z);
1048 TEST_EQUAL(y, w);
1049 }
1050}
1051
1052int main()
1053{
1054 mie::zmInit();
1055 testAdd2();
1056 testAddSub();
1057 testMul1();
1058 testMul2();
1059 testDiv1();
1060 testDiv2();
1061 testDiv3();
1062 testString();
1063 testZmZ();
1064 testZmZsub();
1065 testInverse();
1066 testPow();
1067 testShift();
1068 testBitLen();
1069 testTestBit();
1070 testVsint();
1071 testStream();
1072 sample();
1073#ifdef NDEBUG
1074 bench();
1075#endif
1076 printf("err=%d(test=%d)\n", s_errNum, s_testNum);
1077}
benchmark.hpp
measure exec time of function
CYBOZU_BENCH
#define CYBOZU_BENCH(msg, func,...)
Definition benchmark.hpp:140
r
const mie::Vuint & r
Definition bn.cpp:28
width
int width
Definition catch_reporter_console.cpp:187
mie::VsintT::set
void set(value_type x)
Definition zm.h:982
mie::ZmZ::setModulo
static void setModulo(const V &m)
Definition zm.h:1331
mie::ZmZ::sub
static void sub(ZmZ &out, const ZmZ &x, const ZmZ &y)
Definition zm.h:1243
mie::ZmZ::set
void set(const ZmZ &x)
Definition zm.h:1197
tbl
const struct Ptn tbl[]
mie
Definition zm.h:60
mie::zmInit
void zmInit()
Definition zm.cpp:557
mie::Unit
uint32_t Unit
Definition zm.h:66
mie::power
T power(const T &x, const S &y)
Definition zm.h:1389
mie::Vsint
VsintT< Vuint > Vsint
Definition zm.h:1162
mie::Vuint
VuintT< local::FixedBuffer< mie::Unit, MIE_ZM_VUINT_BIT_LEN > > Vuint
Definition zm.h:1161
a
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition pointer.h:1181
add
int add(int a, int b)
Definition static_buf.cpp:29
uint32_t
unsigned int uint32_t
Definition stdint.h:126
V
Definition test_zm.cpp:19
V::n
int n
Definition test_zm.cpp:20
V::p
unsigned int p[16]
Definition test_zm.cpp:21
mie::VuintT::shrUnit
static void shrUnit(VuintT &out, const VuintT &x, size_t n)
Definition zm.h:780
mie::VuintT::div1
static T div1(VuintT *q, const VuintT &x, T y)
Definition zm.h:642
mie::VuintT::add
static void add(VuintT &out, const VuintT &x, const VuintT &y)
Definition zm.h:564
mie::VuintT::clear
void clear()
Definition zm.h:406
mie::VuintT::shlUnit
static void shlUnit(VuintT &out, const VuintT &x, size_t n)
Definition zm.h:743
mie::VuintT::shlBit
static void shlBit(VuintT &out, const VuintT &x, size_t n)
Definition zm.h:757
mie::VuintT::bitLen
size_t bitLen() const
Definition zm.h:526
mie::VuintT::shrBit
static void shrBit(VuintT &out, const VuintT &x, size_t n)
Definition zm.h:798
mie::VuintT::set
void set(T x)
Definition zm.h:341
mie::VuintT::toString
std::string toString(int base=10) const
Definition zm.h:407
mie::VuintT::T
Buffer::value_type T
Definition zm.h:323
mie::VuintT::mul
static void mul(VuintT &out, const VuintT &x, const VuintT &y)
Definition zm.h:613
mie::VuintT::sub
static void sub(VuintT &out, const VuintT &x, const VuintT &y)
Definition zm.h:597
mie::VuintT::div
static bool div(VuintT *q, VuintT &r, const VuintT &x, const VuintT &y)
Definition zm.h:661
mie::local::inversible::inverse
MIE_FORCE_INLINE void inverse()
Definition zm.h:171
testPow
void testPow()
Definition test_zm.cpp:686
bench
void bench()
Definition test_zm.cpp:848
NUM_OF_ARRAY
#define NUM_OF_ARRAY(x)
Definition test_zm.cpp:9
testTestBit
void testTestBit()
Definition test_zm.cpp:827
testMul1
void testMul1()
Definition test_zm.cpp:187
testInverse
void testInverse()
Definition test_zm.cpp:664
testString
void testString()
Definition test_zm.cpp:601
TEST_EQUAL
#define TEST_EQUAL(x, y)
Definition test_zm.cpp:14
testStream
void testStream()
Definition test_zm.cpp:1015
sample
void sample()
Definition test_zm.cpp:857
testMul2
void testMul2()
Definition test_zm.cpp:239
TEST_ASSERT
#define TEST_ASSERT(x)
Definition test_zm.cpp:15
testAdd2
void testAdd2()
Definition test_zm.cpp:996
testZmZsub
void testZmZsub()
Definition test_zm.cpp:644
testZmZ
void testZmZ()
Definition test_zm.cpp:627
testShift
void testShift()
Definition test_zm.cpp:703
testBitLen
void testBitLen()
Definition test_zm.cpp:778
testAddSub
void testAddSub()
Definition test_zm.cpp:24
testDiv1
void testDiv1()
Definition test_zm.cpp:322
testVsint
void testVsint()
Definition test_zm.cpp:889
testDiv2
void testDiv2()
Definition test_zm.cpp:386
main
int main()
Definition test_zm.cpp:1052
testDiv3
void testDiv3()
Definition test_zm.cpp:543
mul
void mul(const Operand &op)
Definition xbyak_mnemonic.h:496
shl
void shl(const Operand &op, const Reg8 &_cl)
Definition xbyak_mnemonic.h:724
shr
void shr(const Operand &op, const Reg8 &_cl)
Definition xbyak_mnemonic.h:729
sub
void sub(const Operand &op, uint32 imm)
Definition xbyak_mnemonic.h:745
d
CK_ULONG d
Definition yubihsm_pkcs11.c:1238
s
char * s
Definition yubihsm_pkcs11.c:524