Blob
1 #include "os.h"2 #include <mp.h>3 #include "dat.h"5 static mpdigit _mptwodata[1] = { 2 };6 static mpint _mptwo =7 {8 1,9 1,10 1,11 _mptwodata,12 MPstatic13 };14 mpint *mptwo = &_mptwo;16 static mpdigit _mponedata[1] = { 1 };17 static mpint _mpone =18 {19 1,20 1,21 1,22 _mponedata,23 MPstatic24 };25 mpint *mpone = &_mpone;27 static mpdigit _mpzerodata[1] = { 0 };28 static mpint _mpzero =29 {30 1,31 1,32 0,33 _mpzerodata,34 MPstatic35 };36 mpint *mpzero = &_mpzero;38 static int mpmindigits = 33;40 // set minimum digit allocation41 void42 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 }51 // allocate an n bit 0'd number52 mpint*53 mpnew(int n)54 {55 mpint *b;57 if(n < 0)58 sysfatal("mpsetminbits: n < 0");60 b = mallocz(sizeof(mpint), 1);61 if(b == nil)62 sysfatal("mpnew: %r");63 n = DIGITS(n);64 if(n < mpmindigits)65 n = mpmindigits;66 b->p = (mpdigit*)mallocz(n*Dbytes, 1);67 if(b->p == nil)68 sysfatal("mpnew: %r");69 b->size = n;70 b->sign = 1;72 return b;73 }75 // guarantee at least n significant bits76 void77 mpbits(mpint *b, int m)78 {79 int n;81 n = DIGITS(m);82 if(b->size >= n){83 if(b->top >= n)84 return;85 memset(&b->p[b->top], 0, Dbytes*(n - b->top));86 b->top = n;87 return;88 }89 b->p = (mpdigit*)realloc(b->p, n*Dbytes);90 if(b->p == nil)91 sysfatal("mpbits: %r");92 memset(&b->p[b->top], 0, Dbytes*(n - b->top));93 b->size = n;94 b->top = n;95 }97 void98 mpfree(mpint *b)99 {100 if(b == nil)101 return;102 if(b->flags & MPstatic)103 sysfatal("freeing mp constant");104 memset(b->p, 0, b->size*Dbytes); // information hiding105 free(b->p);106 free(b);107 }109 void110 mpnorm(mpint *b)111 {112 int i;114 for(i = b->top-1; i >= 0; i--)115 if(b->p[i] != 0)116 break;117 b->top = i+1;118 if(b->top == 0)119 b->sign = 1;120 }122 mpint*123 mpcopy(mpint *old)124 {125 mpint *new;127 new = mpnew(Dbits*old->size);128 new->top = old->top;129 new->sign = old->sign;130 memmove(new->p, old->p, Dbytes*old->top);131 return new;132 }134 void135 mpassign(mpint *old, mpint *new)136 {137 mpbits(new, Dbits*old->top);138 new->sign = old->sign;139 new->top = old->top;140 memmove(new->p, old->p, Dbytes*old->top);141 }143 // number of significant bits in mantissa144 int145 mpsignif(mpint *n)146 {147 int i, j;148 mpdigit d;150 if(n->top == 0)151 return 0;152 for(i = n->top-1; i >= 0; i--){153 d = n->p[i];154 for(j = Dbits-1; j >= 0; j--){155 if(d & (((mpdigit)1)<<j))156 return i*Dbits + j + 1;157 }158 }159 return 0;160 }162 // k, where n = 2**k * q for odd q163 int164 mplowbits0(mpint *n)165 {166 int k, bit, digit;167 mpdigit d;169 if(n->top==0)170 return 0;171 k = 0;172 bit = 0;173 digit = 0;174 d = n->p[0];175 for(;;){176 if(d & (1<<bit))177 break;178 k++;179 bit++;180 if(bit==Dbits){181 if(++digit >= n->top)182 return 0;183 d = n->p[digit];184 bit = 0;185 }186 }187 return k;188 }