1 #include "os.h" 2 #include <mp.h> 3 #include "dat.h" 4 5 static mpdigit _mptwodata[1] = { 2 }; 6 static mpint _mptwo = 7 { 8 1, 9 1, 10 1, 11 _mptwodata, 12 MPstatic 13 }; 14 mpint *mptwo = &_mptwo; 15 16 static mpdigit _mponedata[1] = { 1 }; 17 static mpint _mpone = 18 { 19 1, 20 1, 21 1, 22 _mponedata, 23 MPstatic 24 }; 25 mpint *mpone = &_mpone; 26 27 static mpdigit _mpzerodata[1] = { 0 }; 28 static mpint _mpzero = 29 { 30 1, 31 1, 32 0, 33 _mpzerodata, 34 MPstatic 35 }; 36 mpint *mpzero = &_mpzero; 37 38 static int mpmindigits = 33; 39 40 // set minimum digit allocation 41 void 42 mpsetminbits(int n) 43 { 44 if(n < 0) 45 sysfatal("mpsetminbits: n < 0"); 46 if(n == 0) 47 n = 1; 48 mpmindigits = DIGITS(n); 49 } 50 51 // allocate an n bit 0'd number 52 mpint* 53 mpnew(int n) 54 { 55 mpint *b; 56 57 if(n < 0) 58 sysfatal("mpsetminbits: n < 0"); 59 60 b = mallocz(sizeof(mpint), 1); 61 setmalloctag(b, getcallerpc(&n)); 62 if(b == nil) 63 sysfatal("mpnew: %r"); 64 n = DIGITS(n); 65 if(n < mpmindigits) 66 n = mpmindigits; 67 b->p = (mpdigit*)mallocz(n*Dbytes, 1); 68 if(b->p == nil) 69 sysfatal("mpnew: %r"); 70 b->size = n; 71 b->sign = 1; 72 73 return b; 74 } 75 76 // guarantee at least n significant bits 77 void 78 mpbits(mpint *b, int m) 79 { 80 int n; 81 82 n = DIGITS(m); 83 if(b->size >= n){ 84 if(b->top >= n) 85 return; 86 memset(&b->p[b->top], 0, Dbytes*(n - b->top)); 87 b->top = n; 88 return; 89 } 90 b->p = (mpdigit*)realloc(b->p, n*Dbytes); 91 if(b->p == nil) 92 sysfatal("mpbits: %r"); 93 memset(&b->p[b->top], 0, Dbytes*(n - b->top)); 94 b->size = n; 95 b->top = n; 96 } 97 98 void 99 mpfree(mpint *b) 100 { 101 if(b == nil) 102 return; 103 if(b->flags & MPstatic) 104 sysfatal("freeing mp constant"); 105 memset(b->p, 0, b->size*Dbytes); // information hiding 106 free(b->p); 107 free(b); 108 } 109 110 void 111 mpnorm(mpint *b) 112 { 113 int i; 114 115 for(i = b->top-1; i >= 0; i--) 116 if(b->p[i] != 0) 117 break; 118 b->top = i+1; 119 if(b->top == 0) 120 b->sign = 1; 121 } 122 123 mpint* 124 mpcopy(mpint *old) 125 { 126 mpint *new; 127 128 new = mpnew(Dbits*old->size); 129 new->top = old->top; 130 new->sign = old->sign; 131 memmove(new->p, old->p, Dbytes*old->top); 132 return new; 133 } 134 135 void 136 mpassign(mpint *old, mpint *new) 137 { 138 mpbits(new, Dbits*old->top); 139 new->sign = old->sign; 140 new->top = old->top; 141 memmove(new->p, old->p, Dbytes*old->top); 142 } 143 144 // number of significant bits in mantissa 145 int 146 mpsignif(mpint *n) 147 { 148 int i, j; 149 mpdigit d; 150 151 if(n->top == 0) 152 return 0; 153 for(i = n->top-1; i >= 0; i--){ 154 d = n->p[i]; 155 for(j = Dbits-1; j >= 0; j--){ 156 if(d & (((mpdigit)1)<<j)) 157 return i*Dbits + j + 1; 158 } 159 } 160 return 0; 161 } 162 163 // k, where n = 2**k * q for odd q 164 int 165 mplowbits0(mpint *n) 166 { 167 int k, bit, digit; 168 mpdigit d; 169 170 if(n->top==0) 171 return 0; 172 k = 0; 173 bit = 0; 174 digit = 0; 175 d = n->p[0]; 176 for(;;){ 177 if(d & (1<<bit)) 178 break; 179 k++; 180 bit++; 181 if(bit==Dbits){ 182 if(++digit >= n->top) 183 return 0; 184 d = n->p[digit]; 185 bit = 0; 186 } 187 } 188 return k; 189 } 190 191