![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to bignum.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / cfront / libC / bignum|
Return to bignum.c CVS log | Up to [Research Unix] / researchv10no / cmd / cfront / libC / bignum |
1.1 root 1:
2: //
3: // C++ multiple precision integer arithmetic library.
4: //
5: // Integers are encoded as INT_REPs. An INT_REP contains a
6: // reference count, to be used by the user data structure
7: // INT. The beg pointer points to the beginning of the
8: // heap allocated array of longs; last points to beg plus
9: // the length of the array. Integers are represented in
10: // base 2^16, with the least significant digit written at
11: // beg, the next at beg+1, etc. The wt pointer points
12: // to the long after the most significant digit. Negatives
13: // are stored in twos complement notation, with the most
14: // significant digit a long -1.
15: // Examples:
16: // 12345678901(10) <=> 2dfdc1c35 <=> beg-> 1c35,dfdc,2
17: // 3950617284 <=> eb79a2c4 <=> beg-> a2c4,eb79
18: // -3950617284 <=> <=> beg-> 5d3c,1486,-1
19: // The representations are always normalized to the shortest
20: // equivalent representation. Thus, zero has length 0;
21: // beg-> 5d3c,0,0 becomes beg->5d3c, and beg-> ffff,-1 becomes
22: // beg-> -1.
23: //
24: // 2^16 was chosen as the base since it is the largest base
25: // in which single precision operations can be carried out
26: // using machine longs (assuming longs have >= 32 bits).
27: // (This is not entirely true, as an operation in division
28: // potentially produces a value of more than 32 bits; a trick
29: // is used to avoid this problem.) Most of the algorithms
30: // are inherently independent of BASE, as long as BASE^2
31: // fits in a long. However, there are some short cuts used
32: // that make use of the fact that the digits contain 16 bits
33: // and that a long corresponds to 2 digits.
34: //
35:
36: #include "bignum.h"
37: #include <ctype.h>
38:
39: extern "C" {
40: extern int strlen(const char*);
41: extern char *realloc (char *, int);
42: extern void exit(int);
43: }
44:
45: #define NUMHDS 64 /* No. of INT_REPs allocated in a block. */
46: #define BASE 65536 /* Base BASE arithmetic : 2^16 */
47: #define BlockLen 9 /* Maximum no. of decimal digits fitting in a long. */
48:
49: inline int Min(int a,int b) { return(a < b ? a : b); }
50: inline int Max(int a,int b) { return(a > b ? a : b); }
51:
52: #define equalsOne(r) ((r->wt == r->beg+1) && (*(r->beg) == 1))
53: #define MakeZero(t) t->beg=new long[0];t->wt=t->last=t->beg
54:
55: enum Mode {
56: decimal, hexadecimal, octal
57: };
58:
59: static INT_REP *hfree; // Pointer to free list of headers.
60: static INT_REP OneRep("1"); // Representation of 1.
61: static INT_REP TwoRep("2"); // Representation of 2.
62: static INT_REP *Remainder; // Remainder from division, if requested.
63: static INT_REP BigTen(1000000000L); // Largest power of 10 fitting in long.
64: INT_REP ZeroRep(0, 0); // Representation of 0.
65: static INT Zero; // Guarantees refcnt of ZeroRep always > 0.
66:
67:
68: /* IROutBuf:
69: * Construct for handling reverse strings of
70: * indefinite length.
71: */
72:
73: #define IRBufSize 256
74:
75: struct IROutBuf {
76: char *beg;
77: char *last;
78: char *wt;
79:
80: IROutBuf() { beg = new char[IRBufSize]; wt = beg; last = beg + IRBufSize; }
81: ~IROutBuf() { delete beg; }
82:
83: int Length () { return ((int)(wt - beg)); }
84:
85: void Flush (register iostream &i)
86: {
87: register char *p = wt;
88:
89: while (p > beg) {
90: i.put(*(--p));
91: }
92: wt = beg;
93: }
94:
95: void Flush (register OutFn outf)
96: {
97: register char *p = wt;
98:
99: while (p > beg) {
100: (*outf)(*(--p));
101: }
102: (*outf)('\0');
103: wt = beg;
104: }
105:
106: void Flush (register char *buf, int len)
107: {
108: register char *p = wt;
109: register char *endp = wt - len;
110:
111: while (p > endp) {
112: *buf++ = *(--p);
113: }
114: *buf = '\0';
115: wt = beg;
116: }
117:
118: void Put (char c)
119: {
120: int newsize, oldsize;
121:
122: if (wt == last) { // Need more storage.
123: oldsize = (int)(last - beg);
124: newsize = oldsize + IRBufSize;
125: beg = realloc (beg, newsize);
126: last = beg + newsize;
127: wt = beg + oldsize;
128: }
129: *wt++ = c;
130: }
131:
132: };
133: static IROutBuf obuf;
134:
135: /* Fatal:
136: * Fatal error; print message and exit.
137: */
138: static void
139: Fatal (char *msg)
140: {
141:
142: fprintf (stderr, "bignum - %s\n", msg);
143: exit (1);
144: }
145:
146: /* MakeLong:
147: * Convert decimal string to unsigned long.
148: * We assume that the decimal will fit.
149: */
150: unsigned long MakeLong (char *sp, char *ep)
151: {
152: unsigned long ret = 0;
153: int c;
154:
155: while (sp < ep) {
156: c = *sp++;
157: if(!isdigit(c))
158: Fatal ("MakeLong - illegal decimal digit.");
159:
160: ret = 10*ret + (c - '0');
161: }
162: return(ret);
163:
164: }
165:
166: /* HighBit:
167: * Given positive long v < 2^16,
168: * return number of bits val must be left
169: * shifted to be >= 2^15.
170: */
171: int HighBit (register long v)
172: {
173: register int ret = 0;
174:
175: while ((v & 0x8000) == 0) {
176: v <<= 1;
177: ret++;
178: }
179:
180: return (ret);
181: }
182:
183: /* Shift:
184: * Given an array of longs, all < 2^16, left shift them shift
185: * bits, putting numfill of the resultant words in the storage
186: * supplied by fill, using 16 bits per long.
187: */
188: void Shift (long *sp, long *ep, int shift, long *fill, int numfill)
189: {
190: long val;
191:
192: // Easy case; no shifting, just copy.
193: if (shift == 0) {
194: while (numfill--)
195: *fill++ = (sp >= ep ? *sp-- : 0);
196: return;
197: }
198:
199: *fill = ((*sp--) << shift) & 0xFFFF;
200: while (numfill--) {
201: val = (sp >= ep ? *sp-- : 0);
202: *fill++ |= (val >> (16 - shift)) & 0xFFFF;
203: if (numfill == 0)
204: break;
205: *fill = (val << shift) & 0xFFFF;
206: }
207:
208: }
209:
210: /* IRMorehd:
211: * Allocate more headers.
212: */
213: void INT_REP::IRMorehd ()
214: {
215: register INT_REP *h, *kk;
216:
217: hfree = h = (INT_REP *)new char [sizeof(INT_REP) * NUMHDS];
218: if(hfree == 0)
219: Fatal ("IRMorehd : no more memory");
220:
221: // Link the headers together using the wt pointer.
222: kk = h;
223: while (h < hfree + NUMHDS) {
224: h->wt = ((long *)++kk);
225: h++;
226: }
227: h--;
228: h->wt = ((long *)0);
229: }
230:
231: /* IRAllocRep:
232: * Return next available header;
233: * allocate more if necessary.
234: */
235: static inline INT_REP *IRAllocRep () {
236: register INT_REP *next;
237:
238: if (hfree == 0) {
239: INT_REP::IRMorehd ();
240: }
241: next = hfree;
242: hfree = (INT_REP *)(next->wt);
243: return (next);
244: }
245:
246: /* StripZero:
247: * Strip trailing zeros and reset wt pointer.
248: */
249: void INT_REP::StripZero()
250: {
251: register long *pp;
252:
253: if(wt == beg)
254: return;
255: pp = wt - 1;
256: while ((*pp == 0) && (pp > beg))
257: pp--;
258: if (*pp != 0)
259: pp++;
260: wt = pp;
261: }
262:
263: /* StripMinus:
264: * If this is negative,
265: * strip trailing -1's and reset wt pointer.
266: */
267: void INT_REP::StripMinus()
268: {
269: register long *pp;
270:
271: if(isNegative()) {
272: pp = wt - 1; // Points at -1.
273: if (pp > beg) {
274: pp--;
275: while ((*pp == (BASE-1)) && (pp > beg))
276: pp--;
277: if (*pp != (BASE-1))
278: pp++;
279: *pp++ = -1;
280: wt = pp;
281: }
282: }
283: }
284:
285: /* Twos:
286: * Return largest power of 2 dividing this.
287: * Assume this is nonzero.
288: */
289: int INT_REP::Twos()
290: {
291: register int ret = 0;
292: register long *p, val;
293:
294: p = beg;
295: while(*p == 0) {
296: ret += 16;
297: p++;
298: }
299:
300: val = *p;
301: while ((val & 0x1) == 0) {
302: val >>= 1;
303: ret++;
304: }
305:
306: return (ret);
307: }
308:
309: /* FillLong:
310: * Use long to fill this.
311: * Assume storage has already been allocated.
312: */
313: inline void INT_REP::FillLong(unsigned long val)
314: {
315: beg[0] = val & 0xFFFF;
316: beg[1] = (val >> 16) & 0xFFFF;
317: if (val & 0xFFFF0000)
318: wt = beg + 2;
319: else if (val & 0xFFFF)
320: wt = beg + 1;
321: else
322: wt = beg;
323: }
324:
325: /* Trunc:
326: * Use low order digits to fill a long.
327: * If digits are lost, set error = 1;
328: * else error = 0.
329: */
330: long INT_REP::Trunc(int &error)
331: {
332: long ret = 0;
333: int len;
334: register long *ptr;
335:
336: error = 0;
337: if(isZero())
338: return(ret);
339:
340: len = Length();
341: ptr = beg;
342:
343: if (isNegative()) {
344: if (len == 1)
345: ret = -1;
346: else {
347: ret = *ptr++;
348: ret |= (*ptr << 16) & 0x7FFFFFFF;
349: if ((len > 3) || ((*ptr & 0x8000) == 0))
350: error = 1;
351: }
352: }
353: else {
354: ret = *ptr++;
355: if (len > 1) {
356: ret |= *ptr << 16;
357: if ((len > 2) || (*ptr & 0x8000))
358: error = 1;
359: }
360: }
361:
362: return (ret);
363: }
364:
365: /* Comp:
366: * this < b => -1
367: * this == b => 0
368: * this > b => 1
369: */
370: int INT_REP::Comp(INT_REP *b)
371: {
372: INT_REP *diff;
373: int df;
374:
375: diff = Sub(b);
376: if (diff->isZero())
377: df = 0;
378: else if (diff->isNegative())
379: df = -1;
380: else
381: df = 1;
382:
383: delete diff;
384: return (df);
385: }
386:
387:
388: /* Add:
389: * Return new rep, which is the sum of
390: * this and b.
391: */
392: INT_REP *INT_REP::Add(INT_REP *b)
393: {
394: register INT_REP *p;
395: register long n;
396: register int carry;
397: int size;
398: long *ap, *bp, *pp;
399:
400: if ((this == 0) || (b == 0))
401: Fatal ("Add - Null pointers.");
402:
403: if (isZero()) {
404: p = new INT_REP(b);
405: return (p);
406: }
407: if (b->isZero()) {
408: p = new INT_REP(this);
409: return (p);
410: }
411:
412: size = Max (Length(), b->Length());
413: p = new INT_REP(size);
414:
415: ap = this->beg;
416: bp = b->beg;
417: pp = p->beg;
418: carry = 0;
419: while(--size >= 0){
420: n = (ap == wt ? 0 : *ap++) + (bp == b->wt ? 0 : *bp++) + carry;
421: if (n >= BASE) {
422: carry = 1;
423: n -= BASE;
424: }
425: else if (n < 0) {
426: carry = -1;
427: n += BASE;
428: }
429: else carry = 0;
430: *pp++ = n;
431: }
432: p->wt = pp;
433: if(carry != 0)
434: p->Putc(carry);
435:
436: // Remove trailing zeros.
437: p->StripZero();
438:
439: // Remove redundant -1's in front of terminating -1.
440: p->StripMinus();
441:
442: return(p);
443: }
444:
445: /* Sub:
446: * Return new rep, which is the difference of
447: * this and b.
448: */
449: INT_REP *INT_REP::Sub(INT_REP *b)
450: {
451: INT_REP *nb, *diff;
452:
453: if ((this == 0) || (b == 0))
454: Fatal ("Sub - Null pointers.");
455:
456: nb = new INT_REP (b);
457: nb->Chsign();
458:
459: diff = Add(nb);
460: delete nb;
461: return (diff);
462: }
463:
464: /* DivMod:
465: * Return new rep, which is:
466: * mode == 0 => quotient of this and ddivr;
467: * mode == 1 => remainder of quotient of this and ddivr;
468: * mode == 2 => quotient of this and ddivr, with the
469: * remainder stored in Remainder.
470: * Based on the multiple precision division algorithm
471: * in Knuth, v.2.
472: */
473: INT_REP *INT_REP::DivMod(INT_REP *ddivr, int mode)
474: {
475: register INT_REP *quot, *divd, *divr;
476: long *quotp, *divrp, *divdp;
477: int remsign, divsign, offset;
478: long carry, borrow;
479: long *ap, q;
480: unsigned long uval, delta;
481: long val;
482: int divlen, n, exp;
483: long varray[2], uarray[3];
484:
485: if ((this == 0) || (ddivr == 0))
486: Fatal ("DivMod - Null arguments.");
487:
488: if (ddivr->isZero())
489: Fatal ("DivMod : divide by zero.");
490:
491: // Make divisor and dividend positive.
492: Remainder = 0;
493: divsign = remsign = 0;
494: if (ddivr->isNegative ()) {
495: divr = new INT_REP(ddivr);
496: divr->Chsign();
497: divsign = ~divsign;
498: }
499: else
500: divr = ddivr;
501:
502: divd = new INT_REP(this);
503: if (divd->isNegative()) {
504: divd->Chsign();
505: divsign = ~divsign;
506: remsign = ~remsign;
507: }
508:
509: offset = divd->Length() - divr->Length();
510: if(offset < 0) {
511: quot = new INT_REP(0);
512: goto ddone;
513: }
514:
515: // Allocate quotient.
516: quot = new INT_REP (offset + 1);
517: quot->wt = quot->last;
518:
519: val = *(divr->wt - 1); // Most significant "digit" in divisor.
520: divlen = divr->Length();
521:
522: // If divisor is 1 digit, handle specially.
523: if (divlen == 1) {
524: quotp = quot->beg + offset;
525: divdp = divd->beg + offset;
526: carry = 0;
527:
528: while (offset-- >= 0) {
529: uval = carry*BASE + *divdp--;
530: *quotp-- = uval/val;
531: carry = uval%val;
532: }
533:
534: // Set remainder.
535: divd->beg[0] = carry;
536: divd->wt = divd->beg + 1;
537:
538: goto ddone;
539: }
540:
541: // General case.
542: // Initialize. We are essentially finding the least power of 2
543: // that we can multiply times the most significant digit of the divisor
544: // and make it >= BASE/2. The algorithm then guarantees that our
545: // "guess" for the quotient will be at most two greater than the
546: // correct answer.
547:
548: divd->Putc (0);
549: exp = HighBit (val); // 0 <= exp < 16.
550: Shift (divr->wt - 1, divr->beg, exp, varray, 2);
551: divdp = divd->wt - 1;
552: divd->wt -= offset;
553: quotp = quot->wt - 1;
554:
555: // fprintf(stderr, "exp = %d , v1 = %x, v2 = %x\n", exp, varray[0], varray[1]);
556: while (offset-- >= 0) {
557: // divd->Prt();
558: Shift (divdp, divd->beg, exp, uarray, 3);
559: // fprintf(stderr, "u1 = %x, u2 = %x, u3 = %x\n", uarray[0], uarray[1], uarray[2]);
560:
561: // Guess a quotient.
562: if (uarray[0] == varray[0])
563: q = BASE-1;
564: else
565: q = ((unsigned long)(BASE*uarray[0] + uarray[1]))/varray[0];
566: // fprintf(stderr, "initial q = %x\n",q);
567:
568: // Adjust.
569: // while q*v1 > (BASE*u0 + u1 - q*v0)BASE + u2, decrement q.
570: // To avoid an overflow problem, first check if
571: // (BASE*u0 + u1 - q*v0) >= BASE; if it is, the right side is
572: // >= BASE^2, while the left is < BASE^2 and we are done.
573: // Otherwise, the right side is < BASE^2, and we can do an
574: // ordinary arithmetic check.
575: while (1) {
576: delta = BASE*uarray[0] + uarray[1] - q*varray[0];
577: if (delta >= BASE)
578: break;
579: if ((unsigned long)(varray[1]*q) <= (unsigned long)(delta*BASE+uarray[2]))
580: break;
581: q--;
582: }
583: // fprintf(stderr, "final q = %x\n",q);
584:
585: // Multiply divisor by q, and subtract from dividend.
586: n = divlen;
587: carry = 0;
588: borrow = 0;
589: ap = divdp - n;
590: divrp = divr->beg;
591:
592: while (n >= 0) {
593: if (n > 0)
594: uval = q*(*divrp++) + carry;
595: else
596: uval = carry;
597:
598: if (uval >= BASE) {
599: carry = uval/BASE;
600: uval %= BASE;
601: }
602: else
603: carry = 0;
604:
605: val = (*ap) - uval - borrow;
606: // fprintf(stderr, "n = %d, borrow = %x, carry = %x\n",
607: // n, borrow, carry);
608: // fprintf(stderr, "*ap = %x, val = %x, uval = %x\n",
609: // *ap, val, uval);
610: if (val < 0) {
611: val += BASE;
612: borrow = 1;
613: }
614: else
615: borrow = 0;
616:
617: *ap++ = val;
618: n--;
619: }
620:
621: // If guess is still too high (remainder negative => had to borrow),
622: // subtract one from quotient and add one copy of divisor
623: // back into remainder.
624: if (borrow) {
625: *quotp-- = q - 1;
626: n = divlen;
627: carry = 0;
628: ap = divdp - n;
629: divrp = divr->beg;
630:
631: while (n >= 0) {
632: if (n > 0)
633: uval = (*ap) + (*divrp++) + carry;
634: else
635: uval = (*ap) + carry;
636: // fprintf(stderr, "borrow n = %d, carry = %x, *ap = %x, uval = %x\n",
637: // n, carry, *ap, uval);
638:
639: if (uval >= BASE) {
640: uval -= BASE;
641: carry = 1;
642: }
643: else
644: carry = 0;
645:
646: *ap++ = uval;
647: n--;
648: }
649: }
650: else
651: *quotp-- = q;
652:
653: divdp--;
654: }
655:
656: ddone:
657: if (divr != ddivr) delete divr;
658: switch (mode) {
659: case 0 : // Return quotient; delete remainder.
660: delete divd;
661: break;
662: case 1 : // Return remainder; delete quotient and pretend
663: // that the remainder is the quotient.
664: delete quot;
665: quot = divd;
666: divsign = remsign;
667: break;
668: case 2 : // Return quotient; store remainder in Remainder.
669: divd->StripZero();
670: if (remsign < 0) divd->Chsign(); // Use correct sign.
671: Remainder = divd;
672: break;
673: }
674:
675: // Remove prefix zeros.
676: quot->StripZero();
677: if (divsign < 0) quot->Chsign(); // Use correct sign.
678:
679: return (quot);
680: }
681:
682: /* Exp:
683: * Return new rep, which is the first argument
684: * raised to the second argument power.
685: */
686: INT_REP *INT_REP::Exp(INT_REP *exp)
687: {
688: INT_REP *r;
689: INT_REP *e;
690: INT_REP *p;
691: INT_REP *t, *cp, *e1;
692: int neg = 0;
693:
694: r = new INT_REP(&OneRep);
695:
696: // Check for special cases.
697: if((exp->isZero()) || equalsOne(this))
698: return (r);
699: if(isZero()) {
700: r->SetZero();
701: return (r);
702: }
703:
704: // Create copies of arguments.
705: p = new INT_REP(this);
706: e = new INT_REP(exp);
707:
708: // Check for negative exponent.
709: if (e->isNegative()) {
710: neg++;
711: e->Chsign();
712: }
713:
714: // Compute exponentiation.
715: while (e->isNonzero()) {
716: e1 = e->DivMod(&TwoRep,2);
717: delete e;
718: e = e1;
719:
720: if (Remainder->isNonzero()) {
721: e1 = p->Mult(r);
722: delete r;
723: r = e1;
724: }
725: delete Remainder;
726:
727: t = new INT_REP(p);
728: cp = p->Mult(t);
729: delete p;
730: delete t;
731: p = cp;
732: }
733:
734: delete e;
735: delete p;
736:
737: // Adjust for negative exponent.
738: if (neg) {
739: t = OneRep.Div(r);
740: delete r;
741: return (t);
742: }
743: else
744: return (r);
745:
746: }
747:
748: /* Mult:
749: * Return new rep, which is the product of
750: * this and ddivr.
751: */
752: INT_REP *INT_REP::Mult(INT_REP *q)
753: {
754: register INT_REP *mp,*mq,*mr;
755: int sign,offset,carry;
756: unsigned long mt;
757: long cq, cp, mcr;
758: long *pptr, *qptr, *rptr;
759:
760: if ((this == 0) || (q == 0))
761: Fatal ("Mult - Null pointers.");
762:
763: offset = sign = 0;
764: if (isNegative()) {
765: mp = new INT_REP (this);
766: mp->Chsign();
767: sign = ~sign;
768: }
769: else
770: mp = this;
771:
772: if (q->isNegative()) {
773: mq = new INT_REP (q);
774: mq->Chsign();
775: sign = ~sign;
776: }
777: else
778: mq = q;
779:
780: mr = new INT_REP (mp->Length() + mq->Length());
781: mr->Zero();
782: qptr = mq->beg;
783: while (qptr < mq->wt) {
784: cq = *qptr++;
785: pptr = mp->beg;
786: rptr = mr->beg + offset;
787: carry = 0;
788: while (pptr < mp->wt) {
789: cp = *pptr++;
790: mcr = (rptr == mr->wt ? 0 : *rptr);
791: mt = cp*cq + carry + mcr;
792: carry = mt>>16; // mt/BASE.
793: mr->Alterc(mt&0xFFFF, rptr++); // mt%BASE.
794: }
795: offset++;
796: if(carry != 0){
797: mcr = (rptr == mr->wt ? 0 : *rptr);
798: mr->Alterc(mcr+carry, rptr); // Why is mcr+carry < BASE?
799: }
800: }
801:
802: if(sign < 0){
803: mr->Chsign();
804: }
805: if(mp != this) delete mp;
806: if(mq != q) delete mq;
807:
808: return (mr);
809: }
810:
811: /* INT_REP:
812: * Create new rep, with
813: * size bytes of storage.
814: * If setRef == 0, do not initialize refcnt. This is used by
815: * ZeroRep in case it gets initialized after some INT with
816: * no arguments.
817: */
818: INT_REP::INT_REP (int size, int setRef)
819: {
820: long *ptr;
821:
822: if (this == 0)
823: this = IRAllocRep ();
824:
825: ptr = new long[(unsigned)size];
826: if (ptr == 0)
827: Fatal ("INT_REP - Out of memory.");
828:
829: wt = beg = ptr;
830: last = ptr + size;
831: if (setRef) refcnt = 0;
832: }
833:
834: /* INT_REP:
835: * Create new rep,
836: * using supplied long.
837: */
838: INT_REP::INT_REP (long val)
839: {
840: int neg = 0;
841: int size = 2; // Number of longs needed to store positive 32 bits.
842:
843: if (this == 0)
844: this = IRAllocRep ();
845:
846: if (val == 0) { // If zero, ...
847: MakeZero (this);
848: return;
849: }
850:
851: if (val < 0) {
852: neg++;
853: size++; // May need extra word for sign.
854: }
855: beg = new long[size];
856: if (beg == 0)
857: Fatal ("INT_REP - Out of memory.");
858: last = beg + size;
859: refcnt = 0;
860:
861: // Store bits.
862: FillLong((unsigned long)val);
863:
864: // If negative, add sign, and strip redundant signs.
865: if (neg) {
866: Putc(-1);
867: StripMinus();
868: }
869:
870: }
871:
872: /* INT_REP:
873: * Create new rep,
874: * duplicating old rep.
875: */
876: INT_REP::INT_REP (INT_REP *old)
877: {
878: long *ptr, *oldptr;
879: int size = old->Length();
880:
881: if (this == 0)
882: this = IRAllocRep ();
883:
884: ptr = new long[(unsigned)size];
885: if (ptr == 0)
886: Fatal ("INT_REP - Out of memory.");
887: beg = ptr;
888: wt = last = ptr + size;
889: refcnt = 0;
890:
891: oldptr = old->beg;
892: while (ptr < last) {
893: *ptr++ = *oldptr++;
894: }
895: }
896:
897: /* INT_REP:
898: * Create new rep,
899: * from ascii representation s.
900: */
901: INT_REP::INT_REP (char *s)
902: {
903: register char *optr;
904: short minus = 0;
905: Mode mode;
906: int size;
907:
908: if (this == 0)
909: this = IRAllocRep ();
910: refcnt = 0;
911:
912: // Handle NULL pointer or NULL string.
913: if ((s == (char *)0) || (*s == '\0')) {
914: MakeZero(this);
915: return;
916: }
917:
918: // Check for sign.
919: if (*s == '-') {
920: s++;
921: minus = 1;
922: }
923:
924: // Determine mode.
925: if (*s == '0') {
926: s++;
927: if (*s == '\0') {
928: MakeZero(this);
929: return;
930: }
931: else if ((*s == 'x') || (*s == 'X')) {
932: s++;
933: mode = hexadecimal;
934: }
935: else
936: mode = octal;
937: }
938: else
939: mode = decimal;
940:
941: // Find end of string.
942: optr = s;
943: while(*optr) optr++;
944: if (s == optr)
945: Fatal ("INT_REP : Improper string.");
946:
947: // Fill representation, using correct mode.
948: if (mode == decimal)
949: FillDec (s, optr);
950: else {
951: // Allocate enough space.
952: size = (strlen(s) + 3)/4;
953: beg = new long[size];
954: if (beg == 0)
955: Fatal ("INT_REP - Out of memory.");
956: last = beg + size;
957:
958: // Fill.
959: if (mode == hexadecimal)
960: FillHex(s, optr);
961: else
962: FillOct(s, optr);
963:
964: // Remove extraneous zeros.
965: StripZero();
966: }
967:
968: // Correct for sign.
969: if (minus)
970: Chsign ();
971: }
972:
973: /* ~INT_REP:
974: * destructor.
975: */
976: INT_REP::~INT_REP ()
977: {
978: if(beg) delete beg;
979:
980: // Put back on free list.
981: wt = (long *)hfree;
982: hfree = this;
983: this = 0;
984: }
985:
986: /* More:
987: * Obtain more storage for this,
988: * using realloc, and resetting
989: * pointers.
990: */
991: void INT_REP::More()
992: {
993: register unsigned size;
994: register long *p;
995:
996: if ((size = (last - beg) * 2) == 0)
997: size = 1;
998: p = (long *)realloc((char *)beg, (unsigned)(size*sizeof(long)));
999: if(p == 0)
1000: Fatal ("More: realloc failed");
1001:
1002: wt = p + (wt - beg);
1003: beg = p;
1004: last = p + size;
1005: }
1006:
1007: /* Zero:
1008: * Zero out all the storage.
1009: */
1010: void INT_REP::Zero()
1011: {
1012: register long *pp;
1013:
1014: for (pp = beg; pp < last;)
1015: *pp++ = 0;
1016: }
1017:
1018:
1019: /* Prt:
1020: * Print internal information;
1021: * for debugging.
1022: */
1023: void INT_REP::Prt()
1024: {
1025: long *ptr = beg;
1026:
1027: while (ptr != wt)
1028: fprintf(stderr, "%x,", *ptr++);
1029: fprintf (stderr, " : this = %x, beg = %x, last = %x, wt = %x\n",
1030: this, beg, last, wt);
1031: }
1032:
1033: /* PutDec:
1034: * Store decimal representation of this in obuf.
1035: * NOTE : The routine destroys this.
1036: */
1037: INT_REP *INT_REP::PutDec ()
1038: {
1039: register INT_REP *divd = this, *div, *mod;
1040: register long val;
1041: int count;
1042:
1043: while (1) {
1044: div = divd->DivMod (&BigTen, 2);
1045: mod = Remainder;
1046: // div->Prt();
1047: // mod->Prt();
1048:
1049: // Store remainder.
1050: val = 0;
1051: switch (mod->Length()) {
1052: case 2 :
1053: val = (mod->beg[1]) << 16;
1054: /* Fall through. */
1055: case 1 :
1056: val |= (mod->beg[0]);
1057: }
1058: // fprintf (stderr, "val = %d (0x%x)\n",val, val);
1059: delete mod;
1060: delete divd;
1061:
1062: count = BlockLen;
1063: while (val) {
1064: obuf.Put((char)(val%10 + '0'));
1065: val /= 10;
1066: count--;
1067: }
1068:
1069: if (div->isZero())
1070: return (div);
1071:
1072: while (count--)
1073: obuf.Put('0');
1074: divd = div;
1075: }
1076:
1077: }
1078:
1079: /* PutHex:
1080: * Store hexadecimal representation of this in obuf.
1081: */
1082: INT_REP *INT_REP::PutHex ()
1083: {
1084: register unsigned long *ptr = (unsigned long *)beg;
1085: register unsigned long val, digit;
1086: register int count;
1087:
1088: while (1) {
1089: val = *ptr++;
1090: count = 4; // 4 hex digits per long
1091:
1092: while (val) {
1093: if ((digit = (val & 0xF)) < 10)
1094: obuf.Put((char)(digit + '0'));
1095: else
1096: obuf.Put((char)(digit + ('A' - 10)));
1097: val >>= 4;
1098: count--;
1099: }
1100:
1101: if (ptr == (unsigned long *) wt)
1102: return (this);
1103:
1104: while (count--)
1105: obuf.Put ('0');
1106: }
1107: }
1108:
1109: /* PutOct:
1110: * Store octal representation of this in obuf.
1111: */
1112: INT_REP *INT_REP::PutOct ()
1113: {
1114: register unsigned long *ptr = (unsigned long *)beg;
1115: register unsigned long val = 0;
1116: register int count;
1117: register int numbits = 0;
1118:
1119: while (1) {
1120: val |= (*ptr++) << numbits;
1121: if (numbits == 2)
1122: count = 6;
1123: else
1124: count = 5;
1125: numbits += 16;
1126:
1127: while (val && count) {
1128: obuf.Put((char)((val & 0x7) + '0'));
1129: val >>= 3;
1130: numbits -= 3;
1131: count--;
1132: }
1133:
1134: if (ptr == (unsigned long *) wt)
1135: return (this);
1136:
1137: if (count) {
1138: numbits -= (count * 3);
1139: while (count--)
1140: obuf.Put ('0');
1141: }
1142: }
1143: }
1144:
1145: /* Print:
1146: * Print INT_REP.
1147: * We use the output mode supplied by the iostream.
1148: * After taking care of 0 and the minus sign,
1149: * we use the appropriate function to store the
1150: * representation in obuf.
1151: * Finally, we flush obuf onto the iostream.
1152: */
1153: void INT_REP::Print(iostream &i)
1154: {
1155: register INT_REP *divd;
1156: #ifdef HEX
1157: register long *rp;
1158: #endif HEX
1159:
1160: if (Length() == 0) {
1161: i.put('0');
1162: return;
1163: }
1164:
1165: divd = new INT_REP (this);
1166: if (isNegative()) {
1167: divd->Chsign();
1168: i.put('-');
1169: }
1170:
1171:
1172: // Print.
1173: #ifdef PRE6
1174: switch (i.convbase()) {
1175: case 0 :
1176: case 10 :
1177: divd = divd->PutDec ();
1178: break;
1179: case 8 :
1180: divd = divd->PutOct ();
1181: break;
1182: case 16 :
1183: divd = divd->PutHex ();
1184: break;
1185: }
1186: #else
1187: switch (i.flags()) {
1188: default :
1189: case ios::dec :
1190: divd = divd->PutDec ();
1191: break;
1192: case ios::oct :
1193: divd = divd->PutOct ();
1194: break;
1195: case ios::hex :
1196: divd = divd->PutHex ();
1197: break;
1198: }
1199: #endif
1200:
1201: delete divd;
1202: obuf.Flush(i);
1203: #ifdef HEX
1204: rp = wt - 1;
1205: while (rp >= beg)
1206: printf("%04x", *rp--);
1207: printf("\n");
1208: #endif HEX
1209:
1210: }
1211:
1212: /* Print:
1213: * Print INT_REP.
1214: * We use the output function supplied by the user.
1215: * The mode parameter determines the output mode.
1216: * After taking care of 0 and the minus sign,
1217: * we use the appropriate function to store the
1218: * representation in obuf.
1219: * Finally, we flush obuf using the user's function.
1220: */
1221: void INT_REP::Print(OutFn outf, int mode)
1222: {
1223: register INT_REP *divd;
1224:
1225: if (Length() == 0) {
1226: (*outf)('0');
1227: (*outf)('\0');
1228: return;
1229: }
1230:
1231: divd = new INT_REP (this);
1232: if (isNegative()) {
1233: divd->Chsign();
1234: (*outf)('-');
1235: }
1236:
1237: // Print.
1238: switch (mode) {
1239: case 0 :
1240: divd = divd->PutDec ();
1241: break;
1242: case 1 :
1243: divd = divd->PutOct ();
1244: break;
1245: case 2 :
1246: divd = divd->PutHex ();
1247: break;
1248: }
1249:
1250: delete divd;
1251: obuf.Flush(outf);
1252:
1253: }
1254:
1255: /* Store:
1256: * Store representation of this in given buffer,
1257: * null terminated.
1258: * Buflen tells how many characters are in the user's
1259: * buffer; -1 => unspecified.
1260: * Representation is base 10 <=> mode = 0
1261: * base 8 <=> mode = 1
1262: * base 16 <=> mode = 2
1263: * Return number of (non-null) characters.
1264: */
1265: int INT_REP::Store (char *buf, int buflen, int mode)
1266: {
1267: register INT_REP *divd;
1268: int length;
1269:
1270: if (buflen == 0)
1271: return (0);
1272: else if (buflen == 1) {
1273: *buf = '\0';
1274: return (0);
1275: }
1276:
1277: if (isZero()) {
1278: *buf++ = '0';
1279: *buf = '\0';
1280: return (1);
1281: }
1282:
1283: divd = new INT_REP (this);
1284: if (isNegative())
1285: divd->Chsign();
1286:
1287: // Print.
1288: switch (mode) {
1289: case 0 :
1290: divd = divd->PutDec ();
1291: break;
1292: case 1 :
1293: divd = divd->PutOct ();
1294: break;
1295: case 2 :
1296: divd = divd->PutHex ();
1297: break;
1298: }
1299: delete divd;
1300:
1301: // If necessary, add minus sign.
1302: if (isNegative())
1303: obuf.Put('-');
1304:
1305: // Compute number of characters to store.
1306: length = obuf.Length ();
1307: if ((buflen > 0) && (length + 1 > buflen))
1308: length = buflen - 1;
1309:
1310: obuf.Flush(buf, length);
1311:
1312: return (length);
1313:
1314: }
1315:
1316: /* Chsign:
1317: * Change sign of the rep.
1318: */
1319: void INT_REP::Chsign ()
1320: {
1321: register long carry;
1322: register long ct;
1323: register long *readp;
1324:
1325: if (Length () == 0) return;
1326:
1327: carry = 0;
1328: readp = beg;
1329: while (readp != wt) {
1330: ct = BASE - *readp - carry;
1331:
1332: if(ct >= BASE) {
1333: ct -= BASE;
1334: if (ct == 1) {
1335: *readp = 1;
1336: return;
1337: }
1338: else if (carry == 1) {
1339: wt = readp;
1340: return;
1341: }
1342: else
1343: carry = 0;
1344: }
1345: else
1346: carry = 1;
1347:
1348: *readp++ = ct;
1349: }
1350: readp--;
1351: if (*readp == BASE-1)
1352: *readp = -1;
1353: else
1354: Putc(-1);
1355:
1356: }
1357:
1358: /* FillDec:
1359: * Use decimal representation to fill this.
1360: * sp points to first character, ep points
1361: * to terminating NULL. Use standard decimal
1362: * to binary conversion. Assume no
1363: * storage has already been allocated.
1364: */
1365: void INT_REP::FillDec(char *sp, char *ep)
1366: {
1367: char *pp;
1368: INT_REP *u, *newi, *product;
1369: unsigned long val;
1370:
1371: // Create utility INT_REP.
1372: u = new INT_REP(2);
1373:
1374: // Determine leftmost block of characters.
1375: pp = sp + ((int)(ep - sp))%BlockLen;
1376:
1377: // Convert to an INT_REP.
1378: val = MakeLong(sp, pp);
1379: u->FillLong (val);
1380: sp = pp;
1381: newi = new INT_REP (u);
1382:
1383: while (sp < ep) {
1384: product = newi->Mult(&BigTen);
1385: delete newi;
1386: val = MakeLong(sp, sp+BlockLen);
1387: u->FillLong (val);
1388: sp += BlockLen;
1389: newi = product->Add(u);
1390: delete product;
1391: }
1392:
1393: // Copy newi into this.
1394: beg = newi->beg;
1395: last = newi->last;
1396: wt = newi->wt;
1397: newi->beg = 0;
1398:
1399: // Delete temporaries.
1400: delete newi;
1401: delete u;
1402:
1403: }
1404:
1405: /* FillHex:
1406: * Use hex representation to fill this.
1407: * sp points to first character, ep points
1408: * to terminating NULL. Assume adequate
1409: * storage has already been allocated.
1410: */
1411: void INT_REP::FillHex(char *sp, char *ep)
1412: {
1413: long *lptr = beg;
1414: long word = 0;
1415: long c;
1416: short shift = 0;
1417:
1418: while (ep > sp) {
1419: c = *(--ep);
1420: if(!isxdigit(c))
1421: Fatal ("FillHex - Illegal hex character.");
1422: if (isdigit(c))
1423: c -= '0';
1424: else if (islower(c))
1425: c -= 'a' - 10;
1426: else
1427: c -= 'A' - 10;
1428:
1429: word |= c << shift;
1430: shift += 4;
1431: if (shift == 16) {
1432: shift = 0;
1433: *lptr++ = word;
1434: word = 0;
1435: }
1436: }
1437:
1438: // Add incomplete word.
1439: if (shift)
1440: *lptr++ = word;
1441:
1442: // Set wt.
1443: wt = lptr;
1444: }
1445:
1446: /* FillOct:
1447: * Use octal representation to fill this.
1448: * sp points to first character, ep points
1449: * to terminating NULL. Assume adequate
1450: * storage has already been allocated.
1451: */
1452: void INT_REP::FillOct(char *sp, char *ep)
1453: {
1454: long *lptr = beg;
1455: long word = 0;
1456: long c;
1457: short shift = 0;
1458:
1459: while (ep > sp) {
1460: c = *(--ep);
1461: if(!isdigit(c) || (c > '7'))
1462: Fatal ("FillOct - Illegal octal character.");
1463:
1464: c -= '0';
1465: word |= c << shift;
1466: shift += 3;
1467: if (shift >= 16) {
1468: *lptr++ = word & 0xFFFF;
1469: shift -= 16;
1470: word = c >> (3 - shift);
1471: }
1472: }
1473:
1474: // Add incomplete word.
1475: if (shift)
1476: *lptr++ = word;
1477:
1478: // Set wt.
1479: wt = lptr;
1480:
1481: }
1482:
1483: /* And:
1484: * Bit-wise and.
1485: */
1486: INT_REP *INT_REP::And(INT_REP *b)
1487: {
1488: INT_REP *newi;
1489: int length;
1490: long *ap, *bp, *pp;
1491:
1492: if (isZero() || b->isZero())
1493: return (&ZeroRep);
1494:
1495: length = Min(Length(), b->Length());
1496: newi = new INT_REP(length);
1497:
1498: ap = beg;
1499: bp = b->beg;
1500: pp = newi->beg;
1501:
1502: while (length-- > 0)
1503: *pp++ = (*ap++) & (*bp++);
1504: newi->wt = pp;
1505:
1506: // Strip trailing zeros.
1507: newi->StripZero();
1508:
1509: return (newi);
1510: }
1511:
1512: /* Or:
1513: * Bit-wise or.
1514: */
1515: INT_REP *INT_REP::Or(INT_REP *b)
1516: {
1517: INT_REP *newi;
1518: int length;
1519: long *ap, *bp, *pp;
1520:
1521: if (isZero()) {
1522: newi = new INT_REP(b);
1523: return newi;
1524: }
1525: if (b->isZero()) {
1526: newi = new INT_REP(this);
1527: return newi;
1528: }
1529:
1530: if (isNegative()) {
1531: if(b->isNegative())
1532: length = Min(Length(), b->Length());
1533: else
1534: length = Length();
1535: }
1536: else {
1537: if(b->isNegative())
1538: length = b->Length();
1539: else
1540: length = Max(Length(), b->Length());
1541: }
1542: newi = new INT_REP(length);
1543:
1544: ap = beg;
1545: bp = b->beg;
1546: pp = newi->beg;
1547:
1548: while (length-- > 0)
1549: *pp++ = (ap < wt ? *ap++ : 0) & (bp < b->wt ? *bp++ : 0);
1550: newi->wt = pp;
1551:
1552: // Strip possible trailing -1's.
1553: newi->StripMinus();
1554:
1555: return (newi);
1556:
1557: }
1558:
1559: /* Xor:
1560: * Bit-wise xor.
1561: */
1562: INT_REP *INT_REP::Xor(INT_REP *b)
1563: {
1564: INT_REP *newi;
1565: INT_REP *pos, *neg;
1566: long *ap, *bp, *pp;
1567: long extval;
1568: int length;
1569:
1570: if (isZero()) {
1571: newi = new INT_REP(b);
1572: return newi;
1573: }
1574: if (b->isZero()) {
1575: newi = new INT_REP(this);
1576: return newi;
1577: }
1578:
1579: if(isNegative() == b->isNegative()) { // Same sign.
1580: length = Max(Length(), b->Length());
1581: newi = new INT_REP(length);
1582:
1583: ap = beg;
1584: bp = b->beg;
1585: pp = newi->beg;
1586: if(isNegative())
1587: extval = -1;
1588: else
1589: extval = 0;
1590:
1591: while (length-- > 0)
1592: *pp++ = ((ap < wt ? *ap++ : extval) ^ (bp < b->wt ? *bp++ : extval)) & 0xFFFF;
1593: newi->wt = pp;
1594:
1595: // Remove trailing zeros.
1596: newi->StripZero();
1597: }
1598: else { // Different sign.
1599: // Set neg pointing to negative value, pos pointing to positive.
1600: if (isNegative()) {
1601: neg = this;
1602: pos = b;
1603: }
1604: else {
1605: neg = b;
1606: pos = this;
1607: }
1608:
1609: length = Max(pos->Length()+1, neg->Length());
1610: newi = new INT_REP(length);
1611:
1612: ap = pos->beg;
1613: bp = neg->beg;
1614: pp = newi->beg;
1615:
1616: while (--length > 0)
1617: *pp++ = ((ap < pos->wt ? *ap++ : 0) ^ (bp < neg->wt ? *bp++ : -1)) & 0xFFFF;
1618: *pp++ = -1;
1619: newi->wt = pp;
1620:
1621: // Remove trailing -1's.
1622: newi->StripMinus();
1623: }
1624:
1625: return (newi);
1626: }
1627:
1628: /* Not:
1629: * Bit-wise not.
1630: */
1631: INT_REP *INT_REP::Not()
1632: {
1633: int length;
1634: long *ap, *pp;
1635: INT_REP *newi;
1636:
1637: if (isZero()) {
1638: newi = new INT_REP(1);
1639: newi->Putc(-1);
1640: return (newi);
1641: }
1642:
1643: if (isNegative()) {
1644: length = Length() - 1;
1645: newi = new INT_REP(length);
1646:
1647: ap = beg;
1648: pp = newi->beg;
1649: while(length--)
1650: *pp++ = (~(*ap++)) & 0xFFFF;
1651: newi->wt = pp;
1652: }
1653: else {
1654: length = Length();
1655: newi = new INT_REP(length+1);
1656:
1657: ap = beg;
1658: pp = newi->beg;
1659: while(length--)
1660: *pp++ = (~(*ap++)) & 0xFFFF;
1661: *pp++ = -1;
1662: newi->wt = pp;
1663: }
1664:
1665: return (newi);
1666: }
1667:
1668: /* LeftShift:
1669: * Bit-wise left shift.
1670: */
1671: INT_REP *INT_REP::LeftShift(INT_REP *b)
1672: {
1673: long shift;
1674: INT_REP *bb, *newi;
1675: int error;
1676:
1677: shift = b->Trunc(error);
1678: if (!error) // Shift can be represented as a long.
1679: return(LeftShift(shift));
1680:
1681: if (isZero()) {
1682: newi = new INT_REP(this);
1683: return newi;
1684: }
1685: if (b->isNegative()) {
1686: bb = new INT_REP(b);
1687: bb->Chsign();
1688: newi = RightShift(bb);
1689: delete bb;
1690: return (newi);
1691: }
1692:
1693: bb = TwoRep.Exp(b);
1694: newi = Mult(bb);
1695: delete bb;
1696: return (newi);
1697:
1698: }
1699:
1700: INT_REP *INT_REP::LeftShift(long shift)
1701: {
1702: INT_REP *newi;
1703: int length;
1704: int bitshift;
1705: long val;
1706: long *ap, *pp;
1707:
1708: // Special cases.
1709: if ((shift == 0) || isZero()) {
1710: newi = new INT_REP(this);
1711: return newi;
1712: }
1713: if (shift < 0) {
1714: return (RightShift(-1*shift));
1715: }
1716:
1717: length = Length() + ((shift + 15)>>4); // (shift + 15)/16.
1718: bitshift = shift & 0xF; // shift%16.
1719: newi = new INT_REP(length);
1720: newi->wt = newi->last;
1721:
1722: // Initialize.
1723: ap = wt-1;
1724: pp = newi->last - 1;
1725:
1726: // Shift.
1727: if(bitshift) {
1728: if (isNegative())
1729: *pp = -1;
1730: else
1731: *pp = 0;
1732:
1733: while (ap >= beg) {
1734: val = *(ap--) & 0xFFFF;
1735: *pp-- |= val >> (16 - bitshift);
1736: *pp = (val << bitshift) & 0xFFFF;
1737: }
1738: }
1739: else {
1740: while (ap >= beg) {
1741: *pp-- = *ap--;
1742: }
1743: pp++;
1744: }
1745:
1746: // Fill with 0's.
1747: while (pp > newi->beg)
1748: *(--pp) = 0;
1749:
1750:
1751: if (isNegative())
1752: newi->StripMinus();
1753: else
1754: newi->StripZero();
1755:
1756: return (newi);
1757: }
1758:
1759: /* RightShift:
1760: * Bit-wise right shift.
1761: */
1762: INT_REP *INT_REP::RightShift(INT_REP *b)
1763: {
1764: long shift;
1765: INT_REP *bb, *newi;
1766: int error;
1767:
1768: shift = b->Trunc(error);
1769: if (!error) // Shift can be represented as a long.
1770: return(RightShift(shift));
1771:
1772: if (isZero()) {
1773: newi = new INT_REP(this);
1774: return newi;
1775: }
1776: if (b->isNegative()) {
1777: bb = new INT_REP(b);
1778: bb->Chsign();
1779: newi = LeftShift(bb);
1780: delete bb;
1781: return (newi);
1782: }
1783:
1784: bb = TwoRep.Exp(b);
1785: newi = Div(bb);
1786: delete bb;
1787: return (newi);
1788:
1789: }
1790:
1791: INT_REP *INT_REP::RightShift(long shift)
1792: {
1793: INT_REP *newi;
1794: int length;
1795: int offset, bitshift;
1796: long val;
1797: long *ap, *pp;
1798:
1799: // Special cases.
1800: if ((shift == 0) || isZero()) {
1801: newi = new INT_REP(this);
1802: return newi;
1803: }
1804: if (shift < 0) {
1805: return (LeftShift(-1*shift));
1806: }
1807:
1808: offset = shift>>4; // shift/16.
1809: // If offset >= Length(), shifting produces either 0 or -1.
1810: if (offset >= Length()) {
1811: if (isNegative()) {
1812: newi = new INT_REP(1);
1813: newi->Putc(-1);
1814: return newi;
1815: }
1816: else {
1817: newi = new INT_REP(0);
1818: return newi;
1819: }
1820: }
1821:
1822: length = Length() - offset;
1823: bitshift = shift & 0xF; // shift%16.
1824: newi = new INT_REP(length);
1825: newi->wt = newi->last;
1826:
1827: // Initialize.
1828: ap = beg + offset;
1829: pp = newi->beg;
1830:
1831: // Shift.
1832: if (bitshift) {
1833: *pp = (*ap++ >> bitshift) & 0xFFFF;
1834:
1835: while (ap < wt) {
1836: val = *ap++ & 0xFFFF;
1837: *pp++ |= (val << (16 - bitshift)) & 0xFFFF;
1838: *pp = (val >> bitshift);
1839: }
1840:
1841: if (isNegative()) {
1842: *pp = -1;
1843: newi->StripMinus();
1844: }
1845: else
1846: newi->StripZero();
1847: }
1848: else {
1849: while (ap < wt)
1850: *pp++ = *ap++;
1851: }
1852:
1853: return (newi);
1854: }
1855:
1856: /* GCD:
1857: * Returns greatest common divisor.
1858: */
1859: INT_REP *INT_REP::GCD(INT_REP *b)
1860: {
1861: INT_REP *newi;
1862: INT_REP *t, *u, *v, *tmp;
1863: int k, l;
1864:
1865: // If this or b is 0.
1866: if (isZero()) {
1867: newi = new INT_REP (b);
1868: if (b->isNegative())
1869: newi->Chsign();
1870: return (newi);
1871: }
1872: if (b->isZero()) {
1873: newi = new INT_REP (this);
1874: if (this->isNegative())
1875: newi->Chsign();
1876: return (newi);
1877: }
1878:
1879: // Make this and b positive.
1880: if (isNegative()) {
1881: u = new INT_REP (this);
1882: u->Chsign();
1883: }
1884: else
1885: u = this;
1886: if (b->isNegative()) {
1887: v = new INT_REP (b);
1888: v->Chsign();
1889: }
1890: else
1891: v = b;
1892:
1893: // Compute highest power of 2 dividing both this and b;
1894: // divide out this power.
1895: k = Min (Twos(), b->Twos());
1896: tmp = u->RightShift(k);
1897: if (u != this) delete u;
1898: u = tmp;
1899: tmp = v->RightShift(k);
1900: if (v != b) delete v;
1901: v = tmp;
1902:
1903: // Initialize.
1904: if (u->isOdd()) {
1905: t = new INT_REP (v);
1906: t->Chsign();
1907: }
1908: else
1909: t = new INT_REP (u);
1910:
1911: // Loop.
1912: while (t->isNonzero()) {
1913:
1914: // Remove powers of 2 from t.
1915: l = t->Twos();
1916: tmp = t->RightShift (l);
1917: delete t;
1918: t = tmp;
1919:
1920: if (t->isNegative()) {
1921: delete v;
1922: v = new INT_REP (t);
1923: v->Chsign();
1924: }
1925: else {
1926: delete u;
1927: u = new INT_REP (t);
1928: }
1929:
1930: delete t;
1931: t = u->Sub(v);
1932: }
1933:
1934: // Add in power of 2 computed above.
1935: newi = u->LeftShift (k);
1936:
1937: delete u;
1938: delete v;
1939:
1940: return (newi);
1941: }
1942:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.