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
22typedef uint32_t u32;
23
24static 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
44u32 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
68int
69main(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}
View as plain text