1 /**************************************************************************/ 2 /* */ 3 /* OCaml */ 4 /* */ 5 /* Xavier Leroy, projet Cristal, INRIA Rocquencourt */ 6 /* */ 7 /* Copyright 2003 Institut National de Recherche en Informatique et */ 8 /* en Automatique. */ 9 /* */ 10 /* All rights reserved. This file is distributed under the terms of */ 11 /* the GNU Lesser General Public License version 2.1, with the */ 12 /* special exception on linking described in the file LICENSE. */ 13 /* */ 14 /**************************************************************************/ 15 16 #include <string.h> 17 #include "caml/config.h" 18 19 typedef uintnat bngdigit; 20 typedef bngdigit * bng; 21 typedef unsigned int bngcarry; 22 typedef uintnat bngsize; 23 24 #define BNG_BITS_PER_DIGIT (sizeof(bngdigit) * 8) 25 #define BNG_BITS_PER_HALF_DIGIT (sizeof(bngdigit) * 4) 26 27 struct bng_operations { 28 29 /* {a,alen} := {a, alen} + carry. Return carry out. */ 30 bngcarry (*add_carry) 31 (bng a/*[alen]*/, bngsize alen, bngcarry carry); 32 #define bng_add_carry bng_ops.add_carry 33 34 /* {a,alen} := {a,alen} + {b,blen} + carry. Return carry out. 35 Require alen >= blen. */ 36 bngcarry (*add) 37 (bng a/*[alen]*/, bngsize alen, 38 bng b/*[blen]*/, bngsize blen, 39 bngcarry carry); 40 #define bng_add bng_ops.add 41 42 /* {a,alen} := {a, alen} - carry. Return carry out. */ 43 bngcarry (*sub_carry) 44 (bng a/*[alen]*/, bngsize alen, bngcarry carry); 45 #define bng_sub_carry bng_ops.sub_carry 46 47 /* {a,alen} := {a,alen} - {b,blen} - carry. Return carry out. 48 Require alen >= blen. */ 49 bngcarry (*sub) 50 (bng a/*[alen]*/, bngsize alen, 51 bng b/*[blen]*/, bngsize blen, 52 bngcarry carry); 53 #define bng_sub bng_ops.sub 54 55 /* {a,alen} := {a,alen} << shift. 56 Return the bits shifted out of the most significant digit of a. 57 Require 0 <= shift < BITS_PER_BNGDIGIT. */ 58 bngdigit (*shift_left) 59 (bng a/*[alen]*/, bngsize alen, 60 int shift); 61 #define bng_shift_left bng_ops.shift_left 62 63 /* {a,alen} := {a,alen} >> shift. 64 Return the bits shifted out of the least significant digit of a. 65 Require 0 <= shift < BITS_PER_BNGDIGIT. */ 66 bngdigit (*shift_right) 67 (bng a/*[alen]*/, bngsize alen, 68 int shift); 69 #define bng_shift_right bng_ops.shift_right 70 71 /* {a,alen} := {a,alen} + d * {b,blen}. Return carry out. 72 Require alen >= blen. 73 If alen > blen, the carry out returned is 0 or 1. 74 If alen == blen, the carry out returned is a full digit. */ 75 bngdigit (*mult_add_digit) 76 (bng a/*[alen]*/, bngsize alen, 77 bng b/*[blen]*/, bngsize blen, 78 bngdigit d); 79 #define bng_mult_add_digit bng_ops.mult_add_digit 80 81 /* {a,alen} := {a,alen} - d * {b,blen}. Return carry out. 82 Require alen >= blen. 83 If alen > blen, the carry out returned is 0 or 1. 84 If alen == blen, the carry out returned is a full digit. */ 85 bngdigit (*mult_sub_digit) 86 (bng a/*[alen]*/, bngsize alen, 87 bng b/*[blen]*/, bngsize blen, 88 bngdigit d); 89 #define bng_mult_sub_digit bng_ops.mult_sub_digit 90 91 /* {a,alen} := {a,alen} + {b,blen} * {c,clen}. Return carry out. 92 Require alen >= blen + clen. */ 93 bngcarry (*mult_add) 94 (bng a/*[alen]*/, bngsize alen, 95 bng b/*[blen]*/, bngsize blen, 96 bng c/*[clen]*/, bngsize clen); 97 #define bng_mult_add bng_ops.mult_add 98 99 /* {a,alen} := 2 * {a,alen} + {b,blen}^2. Return carry out. 100 Require alen >= 2 * blen. */ 101 bngcarry (*square_add) 102 (bng a/*[alen]*/, bngsize alen, 103 bng b/*[blen]*/, bngsize blen); 104 #define bng_square_add bng_ops.square_add 105 106 /* {a,len-1} := {b,len} / d. Return {b,len} modulo d. 107 Require d is normalized and MSD of b < d. 108 See div_rem_digit for a function that does not require d 109 to be normalized */ 110 bngdigit (*div_rem_norm_digit) 111 (bng a/*[len-1]*/, bng b/*[len]*/, bngsize len, bngdigit d); 112 #define bng_div_rem_norm_digit bng_ops.div_rem_norm_digit 113 114 /* {a,len-1} := {b,len} / d. Return {b,len} modulo d. 115 Require MSD of b < d. */ 116 bngdigit (*div_rem_digit) 117 (bng a/*[len-1]*/, bng b/*[len]*/, bngsize len, bngdigit d); 118 #define bng_div_rem_digit bng_ops.div_rem_digit 119 120 /* {n+dlen, nlen-dlen} := {n,nlen} / {d, dlen}. 121 {n, dlen} := {n,nlen} modulo {d, dlen}. 122 Require nlen > dlen and MSD of n < MSD of d (which implies d != 0). */ 123 void (*div_rem) 124 (bng n/*[nlen]*/, bngsize nlen, 125 bng d/*[nlen]*/, bngsize dlen); 126 #define bng_div_rem bng_ops.div_rem 127 }; 128 129 extern struct bng_operations bng_ops; 130 131 /* Initialize the BNG library */ 132 extern void bng_init(void); 133 134 /* {a,alen} := 0 */ 135 #define bng_zero(a,alen) memset((a), 0, (alen) * sizeof(bngdigit)) 136 137 /* {a,len} := {b,len} */ 138 #define bng_assign(a,b,len) memmove((a), (b), (len) * sizeof(bngdigit)) 139 140 /* Complement the digits of {a,len} */ 141 extern void bng_complement(bng a/*[alen]*/, bngsize alen); 142 143 /* Return number of significant digits in {a,alen}. */ 144 extern bngsize bng_num_digits(bng a/*[alen]*/, bngsize alen); 145 146 /* Return 1 if {a,alen} is 0, 0 otherwise. */ 147 #define bng_is_zero(a,alen) (bng_num_digits(a,alen) == 0) 148 149 /* Return 0 if {a,alen} = {b,blen} 150 <0 if {a,alen} < {b,blen} 151 >0 if {a,alen} > {b,blen}. */ 152 extern int bng_compare(bng a/*[alen]*/, bngsize alen, 153 bng b/*[blen]*/, bngsize blen); 154 155 /* Return the number of leading zero bits in digit d. */ 156 extern int bng_leading_zero_bits(bngdigit d); 157