17c478bd9Sstevel@tonic-gate /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
27c478bd9Sstevel@tonic-gate /* All Rights Reserved */
37c478bd9Sstevel@tonic-gate
47c478bd9Sstevel@tonic-gate
57c478bd9Sstevel@tonic-gate /*
67c478bd9Sstevel@tonic-gate * Copyright (c) 1980 Regents of the University of California.
77c478bd9Sstevel@tonic-gate * All rights reserved. The Berkeley software License Agreement
87c478bd9Sstevel@tonic-gate * specifies the terms and conditions for redistribution.
97c478bd9Sstevel@tonic-gate */
107c478bd9Sstevel@tonic-gate /* Portions Copyright(c) 1988, Sun Microsystems Inc. */
117c478bd9Sstevel@tonic-gate /* All Rights Reserved */
127c478bd9Sstevel@tonic-gate
137c478bd9Sstevel@tonic-gate /*
147c478bd9Sstevel@tonic-gate * Copyright (c) 1997, by Sun Microsystems, Inc.
157c478bd9Sstevel@tonic-gate * All rights reserved.
167c478bd9Sstevel@tonic-gate */
177c478bd9Sstevel@tonic-gate
18*981fe1b1SJohn Levon /*
19*981fe1b1SJohn Levon * Copyright (c) 2018, Joyent, Inc.
20*981fe1b1SJohn Levon */
217c478bd9Sstevel@tonic-gate
227c478bd9Sstevel@tonic-gate /* LINTLIBRARY */
237c478bd9Sstevel@tonic-gate
247c478bd9Sstevel@tonic-gate #include <mp.h>
257c478bd9Sstevel@tonic-gate #include <stdio.h>
267c478bd9Sstevel@tonic-gate #include <stdlib.h>
277c478bd9Sstevel@tonic-gate #include <sys/types.h>
287c478bd9Sstevel@tonic-gate #include "libmp.h"
297c478bd9Sstevel@tonic-gate
307c478bd9Sstevel@tonic-gate static void m_div(MINT *, MINT *, MINT *, MINT *);
317c478bd9Sstevel@tonic-gate
327c478bd9Sstevel@tonic-gate void
mp_mdiv(MINT * a,MINT * b,MINT * q,MINT * r)337c478bd9Sstevel@tonic-gate mp_mdiv(MINT *a, MINT *b, MINT *q, MINT *r)
347c478bd9Sstevel@tonic-gate {
357c478bd9Sstevel@tonic-gate MINT x, y;
367c478bd9Sstevel@tonic-gate int sign;
377c478bd9Sstevel@tonic-gate
387c478bd9Sstevel@tonic-gate sign = 1;
397c478bd9Sstevel@tonic-gate x.len = y.len = 0;
407c478bd9Sstevel@tonic-gate _mp_move(a, &x);
417c478bd9Sstevel@tonic-gate _mp_move(b, &y);
427c478bd9Sstevel@tonic-gate if (x.len < 0) {
437c478bd9Sstevel@tonic-gate sign = -1;
447c478bd9Sstevel@tonic-gate x.len = -x.len;
457c478bd9Sstevel@tonic-gate }
467c478bd9Sstevel@tonic-gate if (y.len < 0) {
477c478bd9Sstevel@tonic-gate sign = -sign;
487c478bd9Sstevel@tonic-gate y.len = -y.len;
497c478bd9Sstevel@tonic-gate }
507c478bd9Sstevel@tonic-gate _mp_xfree(q);
517c478bd9Sstevel@tonic-gate _mp_xfree(r);
527c478bd9Sstevel@tonic-gate m_div(&x, &y, q, r);
537c478bd9Sstevel@tonic-gate if (sign == -1) {
547c478bd9Sstevel@tonic-gate q->len = -q->len;
557c478bd9Sstevel@tonic-gate r->len = -r->len;
567c478bd9Sstevel@tonic-gate }
577c478bd9Sstevel@tonic-gate _mp_xfree(&x);
587c478bd9Sstevel@tonic-gate _mp_xfree(&y);
597c478bd9Sstevel@tonic-gate }
607c478bd9Sstevel@tonic-gate
617c478bd9Sstevel@tonic-gate static int
m_dsb(int qx,int n,short * a,short * b)627c478bd9Sstevel@tonic-gate m_dsb(int qx, int n, short *a, short *b)
637c478bd9Sstevel@tonic-gate {
647c478bd9Sstevel@tonic-gate int borrow;
657c478bd9Sstevel@tonic-gate int s3b2shit;
667c478bd9Sstevel@tonic-gate int j;
677c478bd9Sstevel@tonic-gate short fifteen = 15;
687c478bd9Sstevel@tonic-gate short *aptr, *bptr;
697c478bd9Sstevel@tonic-gate #ifdef DEBUGDSB
707c478bd9Sstevel@tonic-gate (void) printf("m_dsb %d %d %d %d\n", qx, n, *a, *b);
717c478bd9Sstevel@tonic-gate #endif
727c478bd9Sstevel@tonic-gate
737c478bd9Sstevel@tonic-gate borrow = 0;
747c478bd9Sstevel@tonic-gate aptr = a;
757c478bd9Sstevel@tonic-gate bptr = b;
767c478bd9Sstevel@tonic-gate for (j = n; j > 0; j--) {
777c478bd9Sstevel@tonic-gate #ifdef DEBUGDSB
787c478bd9Sstevel@tonic-gate (void) printf("1 borrow=%x %d %d %d\n", borrow, (*aptr * qx),
797c478bd9Sstevel@tonic-gate *bptr, *aptr);
807c478bd9Sstevel@tonic-gate #endif
817c478bd9Sstevel@tonic-gate borrow -= (*aptr++) * qx - *bptr;
827c478bd9Sstevel@tonic-gate #ifdef DEBUGDSB
837c478bd9Sstevel@tonic-gate (void) printf("2 borrow=%x %d %d %d\n", borrow, (*aptr * qx),
847c478bd9Sstevel@tonic-gate *bptr, *aptr);
857c478bd9Sstevel@tonic-gate #endif
867c478bd9Sstevel@tonic-gate *bptr++ = (short)(borrow & 077777);
877c478bd9Sstevel@tonic-gate #ifdef DEBUGDSB
887c478bd9Sstevel@tonic-gate (void) printf("3 borrow=%x %d %d %d\n", borrow, (*aptr * qx),
897c478bd9Sstevel@tonic-gate *bptr, *aptr);
907c478bd9Sstevel@tonic-gate #endif
917c478bd9Sstevel@tonic-gate if (borrow >= 0) borrow >>= fifteen; /* 3b2 */
927c478bd9Sstevel@tonic-gate else borrow = 0xfffe0000 | (borrow >> fifteen);
937c478bd9Sstevel@tonic-gate #ifdef DEBUGDSB
947c478bd9Sstevel@tonic-gate (void) printf("4 borrow=%x %d %d %d\n", borrow, (*aptr * qx),
957c478bd9Sstevel@tonic-gate *bptr, *aptr);
967c478bd9Sstevel@tonic-gate #endif
977c478bd9Sstevel@tonic-gate }
987c478bd9Sstevel@tonic-gate borrow += *bptr;
997c478bd9Sstevel@tonic-gate *bptr = (short)(borrow & 077777);
100*981fe1b1SJohn Levon if (borrow >= 0) s3b2shit = borrow >> fifteen; /* 3b2 */
101*981fe1b1SJohn Levon else s3b2shit = 0xfffe0000 | (borrow >> fifteen);
1027c478bd9Sstevel@tonic-gate if (s3b2shit == 0) {
1037c478bd9Sstevel@tonic-gate #ifdef DEBUGDSB
1047c478bd9Sstevel@tonic-gate (void) printf("mdsb 0\n");
1057c478bd9Sstevel@tonic-gate #endif
1067c478bd9Sstevel@tonic-gate return (0);
1077c478bd9Sstevel@tonic-gate }
1087c478bd9Sstevel@tonic-gate borrow = 0;
1097c478bd9Sstevel@tonic-gate aptr = a;
1107c478bd9Sstevel@tonic-gate bptr = b;
1117c478bd9Sstevel@tonic-gate for (j = n; j > 0; j--) {
1127c478bd9Sstevel@tonic-gate borrow += *aptr++ + *bptr;
1137c478bd9Sstevel@tonic-gate *bptr++ = (short)(borrow & 077777);
1147c478bd9Sstevel@tonic-gate if (borrow >= 0) borrow >>= fifteen; /* 3b2 */
1157c478bd9Sstevel@tonic-gate else borrow = 0xfffe0000 | (borrow >>fifteen);
1167c478bd9Sstevel@tonic-gate }
1177c478bd9Sstevel@tonic-gate #ifdef DEBUGDSB
1187c478bd9Sstevel@tonic-gate (void) printf("mdsb 1\n");
1197c478bd9Sstevel@tonic-gate #endif
1207c478bd9Sstevel@tonic-gate return (1);
1217c478bd9Sstevel@tonic-gate }
1227c478bd9Sstevel@tonic-gate
1237c478bd9Sstevel@tonic-gate static int
m_trq(short v1,short v2,short u1,short u2,short u3)1247c478bd9Sstevel@tonic-gate m_trq(short v1, short v2, short u1, short u2, short u3)
1257c478bd9Sstevel@tonic-gate {
1267c478bd9Sstevel@tonic-gate short d;
1277c478bd9Sstevel@tonic-gate int x1;
1287c478bd9Sstevel@tonic-gate int c1;
1297c478bd9Sstevel@tonic-gate
1307c478bd9Sstevel@tonic-gate c1 = u1 * 0100000 + u2;
1317c478bd9Sstevel@tonic-gate if (u1 == v1) {
1327c478bd9Sstevel@tonic-gate d = 077777;
1337c478bd9Sstevel@tonic-gate } else {
1347c478bd9Sstevel@tonic-gate d = (short)(c1 / v1);
1357c478bd9Sstevel@tonic-gate }
1367c478bd9Sstevel@tonic-gate do {
1377c478bd9Sstevel@tonic-gate x1 = c1 - v1 * d;
1387c478bd9Sstevel@tonic-gate x1 = x1 * 0100000 + u3 - v2 * d;
1397c478bd9Sstevel@tonic-gate --d;
1407c478bd9Sstevel@tonic-gate } while (x1 < 0);
1417c478bd9Sstevel@tonic-gate #ifdef DEBUGMTRQ
1427c478bd9Sstevel@tonic-gate (void) printf("mtrq %d %d %d %d %d %d\n", v1, v2, u1, u2, u3, (d+1));
1437c478bd9Sstevel@tonic-gate #endif
1447c478bd9Sstevel@tonic-gate return ((int)d + 1);
1457c478bd9Sstevel@tonic-gate }
1467c478bd9Sstevel@tonic-gate
1477c478bd9Sstevel@tonic-gate static void
m_div(MINT * a,MINT * b,MINT * q,MINT * r)1487c478bd9Sstevel@tonic-gate m_div(MINT *a, MINT *b, MINT *q, MINT *r)
1497c478bd9Sstevel@tonic-gate {
1507c478bd9Sstevel@tonic-gate MINT u, v, x, w;
1517c478bd9Sstevel@tonic-gate short d;
1527c478bd9Sstevel@tonic-gate short *qval;
1537c478bd9Sstevel@tonic-gate short *uval;
1547c478bd9Sstevel@tonic-gate int j;
1557c478bd9Sstevel@tonic-gate int qq;
1567c478bd9Sstevel@tonic-gate int n;
1577c478bd9Sstevel@tonic-gate short v1;
1587c478bd9Sstevel@tonic-gate short v2;
1597c478bd9Sstevel@tonic-gate
1607c478bd9Sstevel@tonic-gate u.len = v.len = x.len = w.len = 0;
1617c478bd9Sstevel@tonic-gate if (b->len == 0) {
1627c478bd9Sstevel@tonic-gate _mp_fatal("mdiv divide by zero");
1637c478bd9Sstevel@tonic-gate return;
1647c478bd9Sstevel@tonic-gate }
1657c478bd9Sstevel@tonic-gate if (b->len == 1) {
1667c478bd9Sstevel@tonic-gate r->val = _mp_xalloc(1, "m_div1");
1677c478bd9Sstevel@tonic-gate mp_sdiv(a, b->val[0], q, r->val);
1687c478bd9Sstevel@tonic-gate if (r->val[0] == 0) {
1697c478bd9Sstevel@tonic-gate free(r->val);
1707c478bd9Sstevel@tonic-gate r->len = 0;
1717c478bd9Sstevel@tonic-gate } else {
1727c478bd9Sstevel@tonic-gate r->len = 1;
1737c478bd9Sstevel@tonic-gate }
1747c478bd9Sstevel@tonic-gate return;
1757c478bd9Sstevel@tonic-gate }
1767c478bd9Sstevel@tonic-gate if (a -> len < b -> len) {
1777c478bd9Sstevel@tonic-gate q->len = 0;
1787c478bd9Sstevel@tonic-gate r->len = a->len;
1797c478bd9Sstevel@tonic-gate r->val = _mp_xalloc(r->len, "m_div2");
1807c478bd9Sstevel@tonic-gate for (qq = 0; qq < r->len; qq++) {
1817c478bd9Sstevel@tonic-gate r->val[qq] = a->val[qq];
1827c478bd9Sstevel@tonic-gate }
1837c478bd9Sstevel@tonic-gate return;
1847c478bd9Sstevel@tonic-gate }
1857c478bd9Sstevel@tonic-gate x.len = 1;
1867c478bd9Sstevel@tonic-gate x.val = &d;
1877c478bd9Sstevel@tonic-gate n = b->len;
1887c478bd9Sstevel@tonic-gate d = 0100000 / (b->val[n - 1] + 1);
1897c478bd9Sstevel@tonic-gate mp_mult(a, &x, &u); /* subtle: relies on mult allocing extra space */
1907c478bd9Sstevel@tonic-gate mp_mult(b, &x, &v);
1917c478bd9Sstevel@tonic-gate #ifdef DEBUG_MDIV
1927c478bd9Sstevel@tonic-gate (void) printf(" u=%s\n", mtox(&u));
1937c478bd9Sstevel@tonic-gate (void) printf(" v=%s\n", mtox(&v));
1947c478bd9Sstevel@tonic-gate #endif
1957c478bd9Sstevel@tonic-gate v1 = v.val[n - 1];
1967c478bd9Sstevel@tonic-gate v2 = v.val[n - 2];
1977c478bd9Sstevel@tonic-gate qval = _mp_xalloc(a -> len - n + 1, "m_div3");
1987c478bd9Sstevel@tonic-gate uval = u.val;
1997c478bd9Sstevel@tonic-gate for (j = a->len - n; j >= 0; j--) {
2007c478bd9Sstevel@tonic-gate qq = m_trq(v1, v2, uval[j + n], uval[j + n - 1],
2017c478bd9Sstevel@tonic-gate uval[j + n - 2]);
2027c478bd9Sstevel@tonic-gate if (m_dsb(qq, n, v.val, uval + j))
2037c478bd9Sstevel@tonic-gate qq -= 1;
2047c478bd9Sstevel@tonic-gate qval[j] = (short)qq;
2057c478bd9Sstevel@tonic-gate }
2067c478bd9Sstevel@tonic-gate x.len = n;
2077c478bd9Sstevel@tonic-gate x.val = u.val;
2087c478bd9Sstevel@tonic-gate _mp_mcan(&x);
2097c478bd9Sstevel@tonic-gate #ifdef DEBUG_MDIV
2107c478bd9Sstevel@tonic-gate (void) printf(" x=%s\n", mtox(&x));
2117c478bd9Sstevel@tonic-gate (void) printf(" d(in)=%d\n", (d));
2127c478bd9Sstevel@tonic-gate #endif
2137c478bd9Sstevel@tonic-gate mp_sdiv(&x, d, &w, &d);
2147c478bd9Sstevel@tonic-gate #ifdef DEBUG_MDIV
2157c478bd9Sstevel@tonic-gate (void) printf(" w=%s\n", mtox(&w));
2167c478bd9Sstevel@tonic-gate (void) printf(" d(out)=%d\n", (d));
2177c478bd9Sstevel@tonic-gate #endif
2187c478bd9Sstevel@tonic-gate r->len = w.len;
2197c478bd9Sstevel@tonic-gate r->val = w.val;
2207c478bd9Sstevel@tonic-gate q->val = qval;
2217c478bd9Sstevel@tonic-gate qq = a->len - n + 1;
2227c478bd9Sstevel@tonic-gate if (qq > 0 && qval[qq - 1] == 0)
2237c478bd9Sstevel@tonic-gate qq -= 1;
2247c478bd9Sstevel@tonic-gate q->len = qq;
2257c478bd9Sstevel@tonic-gate if (qq == 0)
2267c478bd9Sstevel@tonic-gate free(qval);
2277c478bd9Sstevel@tonic-gate if (x.len != 0)
2287c478bd9Sstevel@tonic-gate _mp_xfree(&u);
2297c478bd9Sstevel@tonic-gate _mp_xfree(&v);
2307c478bd9Sstevel@tonic-gate }
231