123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848 |
- #include "lib9.h"
- #include "kernel.h"
- #include <isa.h>
- #include "interp.h"
- #include "runt.h"
- #include <mp.h>
- #include <libsec.h>
- #include "pool.h"
- #include "ipint.h"
- #include "raise.h"
- #include "ipintsmod.h"
- enum
- {
- MaxBigBytes = 1024
- };
- /* infinite precision integer */
- struct IPint
- {
- IPints_IPint x;
- mpint* b;
- };
- Type *TIPint;
- static uchar IPintmap[] = IPints_IPint_map;
- #define MP(x) checkIPint((x))
- void
- ipintsmodinit(void)
- {
- /* can be called from modinit, Keyring or Crypt */
- if(TIPint == nil)
- TIPint = dtype(freeIPint, sizeof(IPint), IPintmap, sizeof(IPintmap));
- builtinmod("$IPints", IPintsmodtab, IPintsmodlen);
- }
- //IPints_IPint*
- void*
- newIPint(mpint* b)
- {
- Heap *h;
- IPint *ip;
- if(b == nil)
- error(exHeap);
- h = heap(TIPint); /* TO DO: caller might lose other values if heap raises error here */
- ip = H2D(IPint*, h);
- ip->b = b;
- return (IPints_IPint*)ip;
- }
- mpint*
- checkIPint(void *a)
- {
- IPints_IPint *v;
- IPint *ip;
- v = a;
- ip = (IPint*)v;
- if(ip == H || ip == nil)
- error(exNilref);
- if(D2H(ip)->t != TIPint)
- error(exType);
- return ip->b; /* non-nil by construction */
- }
- void
- freeIPint(Heap *h, int swept)
- {
- IPint *ip;
- USED(swept);
- ip = H2D(IPint*, h);
- if(ip->b)
- mpfree(ip->b);
- freeheap(h, 0);
- }
- void
- IPint_iptob64z(void *fp)
- {
- F_IPint_iptob64 *f;
- mpint *b;
- char buf[MaxBigBytes]; /* TO DO: should allocate these */
- uchar *p;
- int n, o;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- b = MP(f->i);
- n = (b->top+1)*Dbytes;
- p = malloc(n+1);
- if(p == nil)
- error(exHeap);
- n = mptobe(b, p+1, n, nil);
- if(n < 0){
- free(p);
- return;
- }
- p[0] = 0;
- if(n != 0 && (p[1]&0x80)){
- /* force leading 0 byte for compatibility with older representation */
- o = 0;
- n++;
- }else
- o = 1;
- enc64(buf, sizeof(buf), p+o, n);
- retstr(buf, f->ret);
- free(p);
- }
- void
- IPint_iptob64(void *fp)
- {
- F_IPint_iptob64 *f;
- char buf[MaxBigBytes];
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- mptoa(MP(f->i), 64, buf, sizeof(buf));
- retstr(buf, f->ret);
- }
- void
- IPint_iptobytes(void *fp)
- {
- F_IPint_iptobytes *f;
- uchar buf[MaxBigBytes];
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- /* TO DO: two's complement or have ipmagtobe? */
- *f->ret = mem2array(buf, mptobe(MP(f->i), buf, sizeof(buf), nil)); /* for now we'll ignore sign */
- }
- void
- IPint_iptobebytes(void *fp)
- {
- F_IPint_iptobebytes *f;
- uchar buf[MaxBigBytes];
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- *f->ret = mem2array(buf, mptobe(MP(f->i), buf, sizeof(buf), nil));
- }
- void
- IPint_iptostr(void *fp)
- {
- F_IPint_iptostr *f;
- char buf[MaxBigBytes];
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- mptoa(MP(f->i), f->base, buf, sizeof(buf));
- retstr(buf, f->ret);
- }
- static IPints_IPint*
- strtoipint(String *s, int base)
- {
- char *p, *q;
- mpint *b;
- p = string2c(s);
- b = strtomp(p, &q, base, nil);
- if(b == nil)
- return H;
- while(*q == '=')
- q++;
- if(q == p || *q != 0){
- mpfree(b);
- return H;
- }
- return newIPint(b);
- }
- void
- IPint_b64toip(void *fp)
- {
- F_IPint_b64toip *f;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- *f->ret = strtoipint(f->str, 64);
- }
- void
- IPint_bytestoip(void *fp)
- {
- F_IPint_bytestoip *f;
- mpint *b;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- if(f->buf == H)
- error(exNilref);
- b = betomp(f->buf->data, f->buf->len, nil); /* for now we'll ignore sign */
- *f->ret = newIPint(b);
- }
- void
- IPint_bebytestoip(void *fp)
- {
- F_IPint_bebytestoip *f;
- mpint *b;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- if(f->mag == H)
- error(exNilref);
- b = betomp(f->mag->data, f->mag->len, nil);
- *f->ret = newIPint(b);
- }
- void
- IPint_strtoip(void *fp)
- {
- F_IPint_strtoip *f;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- *f->ret = strtoipint(f->str, f->base);
- }
- /* create a random integer */
- void
- IPint_random(void *fp)
- {
- F_IPint_random *f;
- mpint *b;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- release();
- b = mprand(f->nbits, genrandom, nil);
- acquire();
- *f->ret = newIPint(b);
- }
- /* number of bits in number */
- void
- IPint_bits(void *fp)
- {
- F_IPint_bits *f;
- int n;
- f = fp;
- *f->ret = 0;
- if(f->i == H)
- return;
- n = mpsignif(MP(f->i));
- if(n == 0)
- n = 1; /* compatibility */
- *f->ret = n;
- }
- /* create a new IP from an int */
- void
- IPint_inttoip(void *fp)
- {
- F_IPint_inttoip *f;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- *f->ret = newIPint(itomp(f->i, nil));
- }
- void
- IPint_iptoint(void *fp)
- {
- F_IPint_iptoint *f;
- f = fp;
- *f->ret = 0;
- if(f->i == H)
- return;
- *f->ret = mptoi(MP(f->i));
- }
- /* modular exponentiation */
- void
- IPint_expmod(void *fp)
- {
- F_IPint_expmod *f;
- mpint *ret, *mod, *base, *exp;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- base = MP(f->base);
- exp = MP(f->exp);
- if(f->mod != H)
- mod = MP(f->mod);
- else
- mod = nil;
- ret = mpnew(0);
- if(ret != nil)
- mpexp(base, exp, mod, ret);
- *f->ret = newIPint(ret);
- }
- /* multiplicative inverse */
- void
- IPint_invert(void *fp)
- {
- F_IPint_invert *f;
- mpint *ret;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- ret = mpnew(0);
- if(ret != nil)
- mpinvert(MP(f->base), MP(f->mod), ret);
- *f->ret = newIPint(ret);
- }
- /* basic math */
- void
- IPint_add(void *fp)
- {
- F_IPint_add *f;
- mpint *i1, *i2, *ret;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- i1 = MP(f->i1);
- i2 = MP(f->i2);
- ret = mpnew(0);
- if(ret != nil)
- mpadd(i1, i2, ret);
- *f->ret = newIPint(ret);
- }
- void
- IPint_sub(void *fp)
- {
- F_IPint_sub *f;
- mpint *i1, *i2, *ret;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- i1 = MP(f->i1);
- i2 = MP(f->i2);
- ret = mpnew(0);
- if(ret != nil)
- mpsub(i1, i2, ret);
- *f->ret = newIPint(ret);
- }
- void
- IPint_mul(void *fp)
- {
- F_IPint_mul *f;
- mpint *i1, *i2, *ret;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- i1 = MP(f->i1);
- i2 = MP(f->i2);
- ret = mpnew(0);
- if(ret != nil)
- mpmul(i1, i2, ret);
- *f->ret = newIPint(ret);
- }
- void
- IPint_div(void *fp)
- {
- F_IPint_div *f;
- mpint *i1, *i2, *quo, *rem;
- void *v;
- f = fp;
- v = f->ret->t0;
- f->ret->t0 = H;
- destroy(v);
- v = f->ret->t1;
- f->ret->t1 = H;
- destroy(v);
- i1 = MP(f->i1);
- i2 = MP(f->i2);
- quo = mpnew(0);
- if(quo == nil)
- error(exHeap);
- rem = mpnew(0);
- if(rem == nil){
- mpfree(quo);
- error(exHeap);
- }
- mpdiv(i1, i2, quo, rem);
- f->ret->t0 = newIPint(quo);
- f->ret->t1 = newIPint(rem);
- }
- void
- IPint_mod(void *fp)
- {
- F_IPint_mod *f;
- mpint *i1, *i2, *ret;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- i1 = MP(f->i1);
- i2 = MP(f->i2);
- ret = mpnew(0);
- if(ret != nil)
- mpmod(i1, i2, ret);
- *f->ret = newIPint(ret);
- }
- void
- IPint_neg(void *fp)
- {
- F_IPint_neg *f;
- mpint *ret;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- ret = mpcopy(MP(f->i));
- if(ret == nil)
- error(exHeap);
- ret->sign = -ret->sign;
- *f->ret = newIPint(ret);
- }
- /* copy */
- void
- IPint_copy(void *fp)
- {
- F_IPint_copy *f;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- *f->ret = newIPint(mpcopy(MP(f->i)));
- }
- /* equality */
- void
- IPint_eq(void *fp)
- {
- F_IPint_eq *f;
- f = fp;
- *f->ret = mpcmp(MP(f->i1), MP(f->i2)) == 0;
- }
- /* compare */
- void
- IPint_cmp(void *fp)
- {
- F_IPint_eq *f;
- f = fp;
- *f->ret = mpcmp(MP(f->i1), MP(f->i2));
- }
- /* shifts */
- void
- IPint_shl(void *fp)
- {
- F_IPint_shl *f;
- mpint *ret, *i;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- i = MP(f->i);
- ret = mpnew(0);
- if(ret != nil)
- mpleft(i, f->n, ret);
- *f->ret = newIPint(ret);
- }
- void
- IPint_shr(void *fp)
- {
- F_IPint_shr *f;
- mpint *ret, *i;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- i = MP(f->i);
- ret = mpnew(0);
- if(ret != nil)
- mpright(i, f->n, ret);
- *f->ret = newIPint(ret);
- }
- static void
- mpand(mpint *b, mpint *m, mpint *res)
- {
- int i;
- res->sign = b->sign;
- if(b->top == 0 || m->top == 0){
- res->top = 0;
- return;
- }
- mpbits(res, b->top*Dbits);
- res->top = b->top;
- for(i = b->top; --i >= 0;){
- if(i < m->top)
- res->p[i] = b->p[i] & m->p[i];
- else
- res->p[i] = 0;
- }
- mpnorm(res);
- }
- static void
- mpor(mpint *b1, mpint *b2, mpint *res)
- {
- mpint *t;
- int i;
- if(b2->top > b1->top){
- t = b1;
- b1 = b2;
- b2 = t;
- }
- if(b1->top == 0){
- mpassign(b2, res);
- return;
- }
- if(b2->top == 0){
- mpassign(b1, res);
- return;
- }
- mpassign(b1, res);
- for(i = b2->top; --i >= 0;)
- res->p[i] |= b2->p[i];
- mpnorm(res);
- }
- static void
- mpxor(mpint *b1, mpint *b2, mpint *res)
- {
- mpint *t;
- int i;
- if(b2->top > b1->top){
- t = b1;
- b1 = b2;
- b2 = t;
- }
- if(b1->top == 0){
- mpassign(b2, res);
- return;
- }
- if(b2->top == 0){
- mpassign(b1, res);
- return;
- }
- mpassign(b1, res);
- for(i = b2->top; --i >= 0;)
- res->p[i] ^= b2->p[i];
- mpnorm(res);
- }
- static void
- mpnot(mpint *b1, mpint *res)
- {
- int i;
- mpbits(res, Dbits*b1->top);
- res->sign = 1;
- res->top = b1->top;
- for(i = res->top; --i >= 0;)
- res->p[i] = ~b1->p[i];
- mpnorm(res);
- }
- /* bits */
- void
- IPint_and(void *fp)
- {
- F_IPint_and *f;
- mpint *ret, *i1, *i2;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- i1 = MP(f->i1);
- i2 = MP(f->i2);
- ret = mpnew(0);
- if(ret != nil)
- mpand(i1, i2, ret);
- *f->ret = newIPint(ret);
- }
- void
- IPint_ori(void *fp)
- {
- F_IPint_ori *f;
- mpint *ret, *i1, *i2;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- i1 = MP(f->i1);
- i2 = MP(f->i2);
- ret = mpnew(0);
- if(ret != nil)
- mpor(i1, i2, ret);
- *f->ret = newIPint(ret);
- }
- void
- IPint_xor(void *fp)
- {
- F_IPint_xor *f;
- mpint *ret, *i1, *i2;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- i1 = MP(f->i1);
- i2 = MP(f->i2);
- ret = mpnew(0);
- if(ret != nil)
- mpxor(i1, i2, ret);
- *f->ret = newIPint(ret);
- }
- void
- IPint_not(void *fp)
- {
- F_IPint_not *f;
- mpint *ret, *i1;
- void *v;
- f = fp;
- v = *f->ret;
- *f->ret = H;
- destroy(v);
- i1 = MP(f->i1);
- ret = mpnew(0);
- if(ret != nil)
- mpnot(i1, ret);
- *f->ret = newIPint(ret);
- }
- /*
- * primes
- */
- void
- IPints_probably_prime(void *fp)
- {
- F_IPints_probably_prime *f;
- f = fp;
- release();
- *f->ret = probably_prime(checkIPint(f->n), f->nrep);
- acquire();
- }
- void
- IPints_genprime(void *fp)
- {
- F_IPints_genprime *f;
- mpint *p;
- void *r;
- f = fp;
- r = *f->ret;
- *f->ret = H;
- destroy(r);
- p = mpnew(0);
- release();
- genprime(p, f->nbits, f->nrep);
- acquire();
- *f->ret = newIPint(p);
- }
- void
- IPints_genstrongprime(void *fp)
- {
- F_IPints_genstrongprime *f;
- mpint *p;
- void *r;
- f = fp;
- r = *f->ret;
- *f->ret = H;
- destroy(r);
- p = mpnew(0);
- release();
- genstrongprime(p, f->nbits, f->nrep);
- acquire();
- *f->ret = newIPint(p);
- }
- void
- IPints_gensafeprime(void *fp)
- {
- F_IPints_gensafeprime *f;
- mpint *p, *alpha;
- void *v;
- f = fp;
- v = f->ret->t0;
- f->ret->t0 = H;
- destroy(v);
- v = f->ret->t1;
- f->ret->t1 = H;
- destroy(v);
- p = mpnew(0);
- alpha = mpnew(0);
- release();
- gensafeprime(p, alpha, f->nbits, f->nrep);
- acquire();
- f->ret->t0 = newIPint(p);
- f->ret->t1 = newIPint(alpha);
- }
- void
- IPints_DSAprimes(void *fp)
- {
- F_IPints_DSAprimes *f;
- mpint *p, *q;
- Heap *h;
- void *v;
- f = fp;
- v = f->ret->t0;
- f->ret->t0 = H;
- destroy(v);
- v = f->ret->t1;
- f->ret->t1 = H;
- destroy(v);
- v = f->ret->t2;
- f->ret->t2 = H;
- destroy(v);
- h = heaparray(&Tbyte, SHA1dlen);
- f->ret->t2 = H2D(Array*, h);
- p = mpnew(0);
- q = mpnew(0);
- release();
- DSAprimes(q, p, f->ret->t2->data);
- acquire();
- f->ret->t0 = newIPint(q);
- f->ret->t1 = newIPint(p);
- }
|