div_test.c raw

   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