1 // Copyright 2022 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 // This file is a self-contained test for a copy of
6 // the division algorithm in build-goboring.sh,
7 // to verify that is correct. The real algorithm uses u128
8 // but this copy uses u32 for easier testing.
9 // s/32/128/g should be the only difference between the two.
10 //
11 // This is the dumbest possible division algorithm,
12 // but any crypto code that depends on the speed of
13 // division is equally dumb.
14
15 //go:build ignore
16
17 #include <stdio.h>
18 #include <stdint.h>
19
20 #define nelem(x) (sizeof(x)/sizeof((x)[0]))
21
22 typedef uint32_t u32;
23
24 static u32 div(u32 x, u32 y, u32 *rp) {
25 int n = 0;
26 while((y>>(32-1)) != 1 && y < x) {
27 y<<=1;
28 n++;
29 }
30 u32 q = 0;
31 for(;; n--, y>>=1, q<<=1) {
32 if(x>=y) {
33 x -= y;
34 q |= 1;
35 }
36 if(n == 0)
37 break;
38 }
39 if(rp)
40 *rp = x;
41 return q;
42 }
43
44 u32 tests[] = {
45 0,
46 1,
47 2,
48 3,
49 4,
50 5,
51 6,
52 7,
53 8,
54 9,
55 10,
56 11,
57 31,
58 0xFFF,
59 0x1000,
60 0x1001,
61 0xF0F0F0,
62 0xFFFFFF,
63 0x1000000,
64 0xF0F0F0F0,
65 0xFFFFFFFF,
66 };
67
68 int
69 main(void)
70 {
71 for(int i=0; i<nelem(tests); i++)
72 for(int j=0; j<nelem(tests); j++) {
73 u32 n = tests[i];
74 u32 d = tests[j];
75 if(d == 0)
76 continue;
77 u32 r;
78 u32 q = div(n, d, &r);
79 if(q != n/d || r != n%d)
80 printf("div(%x, %x) = %x, %x, want %x, %x\n", n, d, q, r, n/d, n%d);
81 }
82 return 0;
83 }
84
View as plain text