123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190 |
- #include "os.h"
- #include <mp.h>
- #include "dat.h"
- static mpdigit _mptwodata[1] = { 2 };
- static mpint _mptwo =
- {
- 1,
- 1,
- 1,
- _mptwodata,
- MPstatic
- };
- mpint *mptwo = &_mptwo;
- static mpdigit _mponedata[1] = { 1 };
- static mpint _mpone =
- {
- 1,
- 1,
- 1,
- _mponedata,
- MPstatic
- };
- mpint *mpone = &_mpone;
- static mpdigit _mpzerodata[1] = { 0 };
- static mpint _mpzero =
- {
- 1,
- 1,
- 0,
- _mpzerodata,
- MPstatic
- };
- mpint *mpzero = &_mpzero;
- static int mpmindigits = 33;
- // set minimum digit allocation
- void
- mpsetminbits(int n)
- {
- if(n < 0)
- sysfatal("mpsetminbits: n < 0");
- if(n == 0)
- n = 1;
- mpmindigits = DIGITS(n);
- }
- // allocate an n bit 0'd number
- mpint*
- mpnew(int n)
- {
- mpint *b;
- if(n < 0)
- sysfatal("mpsetminbits: n < 0");
- b = mallocz(sizeof(mpint), 1);
- setmalloctag(b, getcallerpc(&n));
- if(b == nil)
- sysfatal("mpnew: %r");
- n = DIGITS(n);
- if(n < mpmindigits)
- n = mpmindigits;
- b->p = (mpdigit*)mallocz(n*Dbytes, 1);
- if(b->p == nil)
- sysfatal("mpnew: %r");
- b->size = n;
- b->sign = 1;
- return b;
- }
- // guarantee at least n significant bits
- void
- mpbits(mpint *b, int m)
- {
- int n;
- n = DIGITS(m);
- if(b->size >= n){
- if(b->top >= n)
- return;
- memset(&b->p[b->top], 0, Dbytes*(n - b->top));
- b->top = n;
- return;
- }
- b->p = (mpdigit*)realloc(b->p, n*Dbytes);
- if(b->p == nil)
- sysfatal("mpbits: %r");
- memset(&b->p[b->top], 0, Dbytes*(n - b->top));
- b->size = n;
- b->top = n;
- }
- void
- mpfree(mpint *b)
- {
- if(b == nil)
- return;
- if(b->flags & MPstatic)
- sysfatal("freeing mp constant");
- memset(b->p, 0, b->size*Dbytes); // information hiding
- free(b->p);
- free(b);
- }
- void
- mpnorm(mpint *b)
- {
- int i;
- for(i = b->top-1; i >= 0; i--)
- if(b->p[i] != 0)
- break;
- b->top = i+1;
- if(b->top == 0)
- b->sign = 1;
- }
- mpint*
- mpcopy(mpint *old)
- {
- mpint *new;
- new = mpnew(Dbits*old->size);
- new->top = old->top;
- new->sign = old->sign;
- memmove(new->p, old->p, Dbytes*old->top);
- return new;
- }
- void
- mpassign(mpint *old, mpint *new)
- {
- mpbits(new, Dbits*old->top);
- new->sign = old->sign;
- new->top = old->top;
- memmove(new->p, old->p, Dbytes*old->top);
- }
- // number of significant bits in mantissa
- int
- mpsignif(mpint *n)
- {
- int i, j;
- mpdigit d;
- if(n->top == 0)
- return 0;
- for(i = n->top-1; i >= 0; i--){
- d = n->p[i];
- for(j = Dbits-1; j >= 0; j--){
- if(d & (((mpdigit)1)<<j))
- return i*Dbits + j + 1;
- }
- }
- return 0;
- }
- // k, where n = 2**k * q for odd q
- int
- mplowbits0(mpint *n)
- {
- int k, bit, digit;
- mpdigit d;
- if(n->top==0)
- return 0;
- k = 0;
- bit = 0;
- digit = 0;
- d = n->p[0];
- for(;;){
- if(d & (1<<bit))
- break;
- k++;
- bit++;
- if(bit==Dbits){
- if(++digit >= n->top)
- return 0;
- d = n->p[digit];
- bit = 0;
- }
- }
- return k;
- }
|