1 #include "lib9.h"
2 #include "kernel.h"
3 #include <isa.h>
4 #include "interp.h"
5 #include "runt.h"
6 #include <mp.h>
7 #include <libsec.h>
8 #include "pool.h"
9 #include "ipint.h"
10 #include "raise.h"
11
12 #include "ipintsmod.h"
13
14 enum
15 {
16 MaxBigBytes = 1024
17 };
18
19 /* infinite precision integer */
20 struct IPint
21 {
22 IPints_IPint x;
23 mpint* b;
24 };
25
26 Type *TIPint;
27 static uchar IPintmap[] = IPints_IPint_map;
28
29 #define MP(x) checkIPint((x))
30
31 void
ipintsmodinit(void)32 ipintsmodinit(void)
33 {
34 /* can be called from modinit, Keyring or Crypt */
35 if(TIPint == nil)
36 TIPint = dtype(freeIPint, sizeof(IPint), IPintmap, sizeof(IPintmap));
37 builtinmod("$IPints", IPintsmodtab, IPintsmodlen);
38 }
39
40 //IPints_IPint*
41 void*
newIPint(mpint * b)42 newIPint(mpint* b)
43 {
44 Heap *h;
45 IPint *ip;
46
47 if(b == nil)
48 error(exHeap);
49 h = heap(TIPint); /* TO DO: caller might lose other values if heap raises error here */
50 ip = H2D(IPint*, h);
51 ip->b = b;
52 return (IPints_IPint*)ip;
53 }
54
55 mpint*
checkIPint(void * a)56 checkIPint(void *a)
57 {
58 IPints_IPint *v;
59 IPint *ip;
60
61 v = a;
62 ip = (IPint*)v;
63 if(ip == H || ip == nil)
64 error(exNilref);
65 if(D2H(ip)->t != TIPint)
66 error(exType);
67 return ip->b; /* non-nil by construction */
68 }
69
70 void
freeIPint(Heap * h,int swept)71 freeIPint(Heap *h, int swept)
72 {
73 IPint *ip;
74
75 USED(swept);
76 ip = H2D(IPint*, h);
77 if(ip->b)
78 mpfree(ip->b);
79 freeheap(h, 0);
80 }
81
82 void
IPint_iptob64z(void * fp)83 IPint_iptob64z(void *fp)
84 {
85 F_IPint_iptob64 *f;
86 mpint *b;
87 char buf[MaxBigBytes]; /* TO DO: should allocate these */
88 uchar *p;
89 int n, o;
90 void *v;
91
92 f = fp;
93 v = *f->ret;
94 *f->ret = H;
95 destroy(v);
96
97 b = MP(f->i);
98 n = (b->top+1)*Dbytes;
99 p = malloc(n+1);
100 if(p == nil)
101 error(exHeap);
102 n = mptobe(b, p+1, n, nil);
103 if(n < 0){
104 free(p);
105 return;
106 }
107 p[0] = 0;
108 if(n != 0 && (p[1]&0x80)){
109 /* force leading 0 byte for compatibility with older representation */
110 o = 0;
111 n++;
112 }else
113 o = 1;
114 enc64(buf, sizeof(buf), p+o, n);
115 retstr(buf, f->ret);
116 free(p);
117 }
118
119 void
IPint_iptob64(void * fp)120 IPint_iptob64(void *fp)
121 {
122 F_IPint_iptob64 *f;
123 char buf[MaxBigBytes];
124 void *v;
125
126 f = fp;
127 v = *f->ret;
128 *f->ret = H;
129 destroy(v);
130
131 mptoa(MP(f->i), 64, buf, sizeof(buf));
132 retstr(buf, f->ret);
133 }
134
135 void
IPint_iptobytes(void * fp)136 IPint_iptobytes(void *fp)
137 {
138 F_IPint_iptobytes *f;
139 uchar buf[MaxBigBytes];
140 void *v;
141
142 f = fp;
143 v = *f->ret;
144 *f->ret = H;
145 destroy(v);
146
147 /* TO DO: two's complement or have ipmagtobe? */
148 *f->ret = mem2array(buf, mptobe(MP(f->i), buf, sizeof(buf), nil)); /* for now we'll ignore sign */
149 }
150
151 void
IPint_iptobebytes(void * fp)152 IPint_iptobebytes(void *fp)
153 {
154 F_IPint_iptobebytes *f;
155 uchar buf[MaxBigBytes];
156 void *v;
157
158 f = fp;
159 v = *f->ret;
160 *f->ret = H;
161 destroy(v);
162
163 *f->ret = mem2array(buf, mptobe(MP(f->i), buf, sizeof(buf), nil));
164 }
165
166 void
IPint_iptostr(void * fp)167 IPint_iptostr(void *fp)
168 {
169 F_IPint_iptostr *f;
170 char buf[MaxBigBytes];
171 void *v;
172
173 f = fp;
174 v = *f->ret;
175 *f->ret = H;
176 destroy(v);
177
178 mptoa(MP(f->i), f->base, buf, sizeof(buf));
179 retstr(buf, f->ret);
180 }
181
182 static IPints_IPint*
strtoipint(String * s,int base)183 strtoipint(String *s, int base)
184 {
185 char *p, *q;
186 mpint *b;
187
188 p = string2c(s);
189 b = strtomp(p, &q, base, nil);
190 if(b == nil)
191 return H;
192 while(*q == '=')
193 q++;
194 if(q == p || *q != 0){
195 mpfree(b);
196 return H;
197 }
198 return newIPint(b);
199 }
200
201 void
IPint_b64toip(void * fp)202 IPint_b64toip(void *fp)
203 {
204 F_IPint_b64toip *f;
205 void *v;
206
207 f = fp;
208 v = *f->ret;
209 *f->ret = H;
210 destroy(v);
211
212 *f->ret = strtoipint(f->str, 64);
213 }
214
215 void
IPint_bytestoip(void * fp)216 IPint_bytestoip(void *fp)
217 {
218 F_IPint_bytestoip *f;
219 mpint *b;
220 void *v;
221
222 f = fp;
223 v = *f->ret;
224 *f->ret = H;
225 destroy(v);
226
227 if(f->buf == H)
228 error(exNilref);
229
230 b = betomp(f->buf->data, f->buf->len, nil); /* for now we'll ignore sign */
231 *f->ret = newIPint(b);
232 }
233
234 void
IPint_bebytestoip(void * fp)235 IPint_bebytestoip(void *fp)
236 {
237 F_IPint_bebytestoip *f;
238 mpint *b;
239 void *v;
240
241 f = fp;
242 v = *f->ret;
243 *f->ret = H;
244 destroy(v);
245
246 if(f->mag == H)
247 error(exNilref);
248
249 b = betomp(f->mag->data, f->mag->len, nil);
250 *f->ret = newIPint(b);
251 }
252
253 void
IPint_strtoip(void * fp)254 IPint_strtoip(void *fp)
255 {
256 F_IPint_strtoip *f;
257 void *v;
258
259 f = fp;
260 v = *f->ret;
261 *f->ret = H;
262 destroy(v);
263
264 *f->ret = strtoipint(f->str, f->base);
265 }
266
267 /* create a random integer */
268 void
IPint_random(void * fp)269 IPint_random(void *fp)
270 {
271 F_IPint_random *f;
272 mpint *b;
273 void *v;
274
275 f = fp;
276 v = *f->ret;
277 *f->ret = H;
278 destroy(v);
279
280 release();
281 b = mprand(f->nbits, genrandom, nil);
282 acquire();
283 *f->ret = newIPint(b);
284 }
285
286 /* number of bits in number */
287 void
IPint_bits(void * fp)288 IPint_bits(void *fp)
289 {
290 F_IPint_bits *f;
291 int n;
292
293 f = fp;
294 *f->ret = 0;
295 if(f->i == H)
296 return;
297
298 n = mpsignif(MP(f->i));
299 if(n == 0)
300 n = 1; /* compatibility */
301 *f->ret = n;
302 }
303
304 /* create a new IP from an int */
305 void
IPint_inttoip(void * fp)306 IPint_inttoip(void *fp)
307 {
308 F_IPint_inttoip *f;
309 void *v;
310
311 f = fp;
312 v = *f->ret;
313 *f->ret = H;
314 destroy(v);
315
316 *f->ret = newIPint(itomp(f->i, nil));
317 }
318
319 void
IPint_iptoint(void * fp)320 IPint_iptoint(void *fp)
321 {
322 F_IPint_iptoint *f;
323
324 f = fp;
325 *f->ret = 0;
326 if(f->i == H)
327 return;
328 *f->ret = mptoi(MP(f->i));
329 }
330
331 /* modular exponentiation */
332 void
IPint_expmod(void * fp)333 IPint_expmod(void *fp)
334 {
335 F_IPint_expmod *f;
336 mpint *ret, *mod, *base, *exp;
337 void *v;
338
339 f = fp;
340 v = *f->ret;
341 *f->ret = H;
342 destroy(v);
343
344 base = MP(f->base);
345 exp = MP(f->exp);
346 if(f->mod != H)
347 mod = MP(f->mod);
348 else
349 mod = nil;
350 ret = mpnew(0);
351 if(ret != nil)
352 mpexp(base, exp, mod, ret);
353 *f->ret = newIPint(ret);
354 }
355
356 /* multiplicative inverse */
357 void
IPint_invert(void * fp)358 IPint_invert(void *fp)
359 {
360 F_IPint_invert *f;
361 mpint *ret;
362 void *v;
363
364 f = fp;
365 v = *f->ret;
366 *f->ret = H;
367 destroy(v);
368
369 ret = mpnew(0);
370 if(ret != nil)
371 mpinvert(MP(f->base), MP(f->mod), ret);
372 *f->ret = newIPint(ret);
373 }
374
375 /* basic math */
376 void
IPint_add(void * fp)377 IPint_add(void *fp)
378 {
379 F_IPint_add *f;
380 mpint *i1, *i2, *ret;
381 void *v;
382
383 f = fp;
384 v = *f->ret;
385 *f->ret = H;
386 destroy(v);
387
388 i1 = MP(f->i1);
389 i2 = MP(f->i2);
390 ret = mpnew(0);
391 if(ret != nil)
392 mpadd(i1, i2, ret);
393
394 *f->ret = newIPint(ret);
395 }
396 void
IPint_sub(void * fp)397 IPint_sub(void *fp)
398 {
399 F_IPint_sub *f;
400 mpint *i1, *i2, *ret;
401 void *v;
402
403 f = fp;
404 v = *f->ret;
405 *f->ret = H;
406 destroy(v);
407
408 i1 = MP(f->i1);
409 i2 = MP(f->i2);
410 ret = mpnew(0);
411 if(ret != nil)
412 mpsub(i1, i2, ret);
413
414 *f->ret = newIPint(ret);
415 }
416 void
IPint_mul(void * fp)417 IPint_mul(void *fp)
418 {
419 F_IPint_mul *f;
420 mpint *i1, *i2, *ret;
421 void *v;
422
423 f = fp;
424 v = *f->ret;
425 *f->ret = H;
426 destroy(v);
427
428 i1 = MP(f->i1);
429 i2 = MP(f->i2);
430 ret = mpnew(0);
431 if(ret != nil)
432 mpmul(i1, i2, ret);
433
434 *f->ret = newIPint(ret);
435 }
436 void
IPint_div(void * fp)437 IPint_div(void *fp)
438 {
439 F_IPint_div *f;
440 mpint *i1, *i2, *quo, *rem;
441 void *v;
442
443 f = fp;
444 v = f->ret->t0;
445 f->ret->t0 = H;
446 destroy(v);
447 v = f->ret->t1;
448 f->ret->t1 = H;
449 destroy(v);
450
451 i1 = MP(f->i1);
452 i2 = MP(f->i2);
453 quo = mpnew(0);
454 if(quo == nil)
455 error(exHeap);
456 rem = mpnew(0);
457 if(rem == nil){
458 mpfree(quo);
459 error(exHeap);
460 }
461 mpdiv(i1, i2, quo, rem);
462
463 f->ret->t0 = newIPint(quo);
464 f->ret->t1 = newIPint(rem);
465 }
466 void
IPint_mod(void * fp)467 IPint_mod(void *fp)
468 {
469 F_IPint_mod *f;
470 mpint *i1, *i2, *ret;
471 void *v;
472
473 f = fp;
474 v = *f->ret;
475 *f->ret = H;
476 destroy(v);
477
478 i1 = MP(f->i1);
479 i2 = MP(f->i2);
480 ret = mpnew(0);
481 if(ret != nil)
482 mpmod(i1, i2, ret);
483
484 *f->ret = newIPint(ret);
485 }
486 void
IPint_neg(void * fp)487 IPint_neg(void *fp)
488 {
489 F_IPint_neg *f;
490 mpint *ret;
491 void *v;
492
493 f = fp;
494 v = *f->ret;
495 *f->ret = H;
496 destroy(v);
497
498 ret = mpcopy(MP(f->i));
499 if(ret == nil)
500 error(exHeap);
501 ret->sign = -ret->sign;
502
503 *f->ret = newIPint(ret);
504 }
505
506 /* copy */
507 void
IPint_copy(void * fp)508 IPint_copy(void *fp)
509 {
510 F_IPint_copy *f;
511 void *v;
512
513 f = fp;
514 v = *f->ret;
515 *f->ret = H;
516 destroy(v);
517
518 *f->ret = newIPint(mpcopy(MP(f->i)));
519 }
520
521
522 /* equality */
523 void
IPint_eq(void * fp)524 IPint_eq(void *fp)
525 {
526 F_IPint_eq *f;
527
528 f = fp;
529 *f->ret = mpcmp(MP(f->i1), MP(f->i2)) == 0;
530 }
531
532 /* compare */
533 void
IPint_cmp(void * fp)534 IPint_cmp(void *fp)
535 {
536 F_IPint_eq *f;
537
538 f = fp;
539 *f->ret = mpcmp(MP(f->i1), MP(f->i2));
540 }
541
542 /* shifts */
543 void
IPint_shl(void * fp)544 IPint_shl(void *fp)
545 {
546 F_IPint_shl *f;
547 mpint *ret, *i;
548 void *v;
549
550 f = fp;
551 v = *f->ret;
552 *f->ret = H;
553 destroy(v);
554
555 i = MP(f->i);
556 ret = mpnew(0);
557 if(ret != nil)
558 mpleft(i, f->n, ret);
559 *f->ret = newIPint(ret);
560 }
561 void
IPint_shr(void * fp)562 IPint_shr(void *fp)
563 {
564 F_IPint_shr *f;
565 mpint *ret, *i;
566 void *v;
567
568 f = fp;
569 v = *f->ret;
570 *f->ret = H;
571 destroy(v);
572
573 i = MP(f->i);
574 ret = mpnew(0);
575 if(ret != nil)
576 mpright(i, f->n, ret);
577 *f->ret = newIPint(ret);
578 }
579
580 static void
mpand(mpint * b,mpint * m,mpint * res)581 mpand(mpint *b, mpint *m, mpint *res)
582 {
583 int i;
584
585 res->sign = b->sign;
586 if(b->top == 0 || m->top == 0){
587 res->top = 0;
588 return;
589 }
590 mpbits(res, b->top*Dbits);
591 res->top = b->top;
592 for(i = b->top; --i >= 0;){
593 if(i < m->top)
594 res->p[i] = b->p[i] & m->p[i];
595 else
596 res->p[i] = 0;
597 }
598 mpnorm(res);
599 }
600
601 static void
mpor(mpint * b1,mpint * b2,mpint * res)602 mpor(mpint *b1, mpint *b2, mpint *res)
603 {
604 mpint *t;
605 int i;
606
607 if(b2->top > b1->top){
608 t = b1;
609 b1 = b2;
610 b2 = t;
611 }
612 if(b1->top == 0){
613 mpassign(b2, res);
614 return;
615 }
616 if(b2->top == 0){
617 mpassign(b1, res);
618 return;
619 }
620 mpassign(b1, res);
621 for(i = b2->top; --i >= 0;)
622 res->p[i] |= b2->p[i];
623 mpnorm(res);
624 }
625
626 static void
mpxor(mpint * b1,mpint * b2,mpint * res)627 mpxor(mpint *b1, mpint *b2, mpint *res)
628 {
629 mpint *t;
630 int i;
631
632 if(b2->top > b1->top){
633 t = b1;
634 b1 = b2;
635 b2 = t;
636 }
637 if(b1->top == 0){
638 mpassign(b2, res);
639 return;
640 }
641 if(b2->top == 0){
642 mpassign(b1, res);
643 return;
644 }
645 mpassign(b1, res);
646 for(i = b2->top; --i >= 0;)
647 res->p[i] ^= b2->p[i];
648 mpnorm(res);
649 }
650
651 static void
mpnot(mpint * b1,mpint * res)652 mpnot(mpint *b1, mpint *res)
653 {
654 int i;
655
656 mpbits(res, Dbits*b1->top);
657 res->sign = 1;
658 res->top = b1->top;
659 for(i = res->top; --i >= 0;)
660 res->p[i] = ~b1->p[i];
661 mpnorm(res);
662 }
663
664 /* bits */
665 void
IPint_and(void * fp)666 IPint_and(void *fp)
667 {
668 F_IPint_and *f;
669 mpint *ret, *i1, *i2;
670 void *v;
671
672 f = fp;
673 v = *f->ret;
674 *f->ret = H;
675 destroy(v);
676
677 i1 = MP(f->i1);
678 i2 = MP(f->i2);
679 ret = mpnew(0);
680 if(ret != nil)
681 mpand(i1, i2, ret);
682 *f->ret = newIPint(ret);
683 }
684
685 void
IPint_ori(void * fp)686 IPint_ori(void *fp)
687 {
688 F_IPint_ori *f;
689 mpint *ret, *i1, *i2;
690 void *v;
691
692 f = fp;
693 v = *f->ret;
694 *f->ret = H;
695 destroy(v);
696
697 i1 = MP(f->i1);
698 i2 = MP(f->i2);
699 ret = mpnew(0);
700 if(ret != nil)
701 mpor(i1, i2, ret);
702 *f->ret = newIPint(ret);
703 }
704
705 void
IPint_xor(void * fp)706 IPint_xor(void *fp)
707 {
708 F_IPint_xor *f;
709 mpint *ret, *i1, *i2;
710 void *v;
711
712 f = fp;
713 v = *f->ret;
714 *f->ret = H;
715 destroy(v);
716
717 i1 = MP(f->i1);
718 i2 = MP(f->i2);
719 ret = mpnew(0);
720 if(ret != nil)
721 mpxor(i1, i2, ret);
722 *f->ret = newIPint(ret);
723 }
724
725 void
IPint_not(void * fp)726 IPint_not(void *fp)
727 {
728 F_IPint_not *f;
729 mpint *ret, *i1;
730 void *v;
731
732 f = fp;
733 v = *f->ret;
734 *f->ret = H;
735 destroy(v);
736
737 i1 = MP(f->i1);
738 ret = mpnew(0);
739 if(ret != nil)
740 mpnot(i1, ret);
741 *f->ret = newIPint(ret);
742 }
743
744 /*
745 * primes
746 */
747
748 void
IPints_probably_prime(void * fp)749 IPints_probably_prime(void *fp)
750 {
751 F_IPints_probably_prime *f;
752
753 f = fp;
754 release();
755 *f->ret = probably_prime(checkIPint(f->n), f->nrep);
756 acquire();
757 }
758
759 void
IPints_genprime(void * fp)760 IPints_genprime(void *fp)
761 {
762 F_IPints_genprime *f;
763 mpint *p;
764 void *r;
765
766 f = fp;
767 r = *f->ret;
768 *f->ret = H;
769 destroy(r);
770 p = mpnew(0);
771 release();
772 genprime(p, f->nbits, f->nrep);
773 acquire();
774 *f->ret = newIPint(p);
775 }
776
777 void
IPints_genstrongprime(void * fp)778 IPints_genstrongprime(void *fp)
779 {
780 F_IPints_genstrongprime *f;
781 mpint *p;
782 void *r;
783
784 f = fp;
785 r = *f->ret;
786 *f->ret = H;
787 destroy(r);
788 p = mpnew(0);
789 release();
790 genstrongprime(p, f->nbits, f->nrep);
791 acquire();
792 *f->ret = newIPint(p);
793 }
794
795 void
IPints_gensafeprime(void * fp)796 IPints_gensafeprime(void *fp)
797 {
798 F_IPints_gensafeprime *f;
799 mpint *p, *alpha;
800 void *v;
801
802 f = fp;
803 v = f->ret->t0;
804 f->ret->t0 = H;
805 destroy(v);
806 v = f->ret->t1;
807 f->ret->t1 = H;
808 destroy(v);
809
810 p = mpnew(0);
811 alpha = mpnew(0);
812 release();
813 gensafeprime(p, alpha, f->nbits, f->nrep);
814 acquire();
815 f->ret->t0 = newIPint(p);
816 f->ret->t1 = newIPint(alpha);
817 }
818
819 void
IPints_DSAprimes(void * fp)820 IPints_DSAprimes(void *fp)
821 {
822 F_IPints_DSAprimes *f;
823 mpint *p, *q;
824 Heap *h;
825 void *v;
826
827 f = fp;
828 v = f->ret->t0;
829 f->ret->t0 = H;
830 destroy(v);
831 v = f->ret->t1;
832 f->ret->t1 = H;
833 destroy(v);
834 v = f->ret->t2;
835 f->ret->t2 = H;
836 destroy(v);
837
838 h = heaparray(&Tbyte, SHA1dlen);
839 f->ret->t2 = H2D(Array*, h);
840
841 p = mpnew(0);
842 q = mpnew(0);
843 release();
844 DSAprimes(q, p, f->ret->t2->data);
845 acquire();
846 f->ret->t0 = newIPint(q);
847 f->ret->t1 = newIPint(p);
848 }
849