17c478bdstevel@tonic-gate/*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
27c478bdstevel@tonic-gate/*	  All Rights Reserved  	*/
37c478bdstevel@tonic-gate
47c478bdstevel@tonic-gate
57c478bdstevel@tonic-gate/*
67c478bdstevel@tonic-gate * Copyright (c) 1980 Regents of the University of California.
77c478bdstevel@tonic-gate * All rights reserved.  The Berkeley software License Agreement
87c478bdstevel@tonic-gate * specifies the terms and conditions for redistribution.
97c478bdstevel@tonic-gate */
107c478bdstevel@tonic-gate/* 	Portions Copyright(c) 1988, Sun Microsystems Inc.	*/
117c478bdstevel@tonic-gate/*	All Rights Reserved					*/
127c478bdstevel@tonic-gate
137c478bdstevel@tonic-gate/*
147c478bdstevel@tonic-gate * Copyright (c) 1997, by Sun Microsystems, Inc.
157c478bdstevel@tonic-gate * All rights reserved.
167c478bdstevel@tonic-gate */
177c478bdstevel@tonic-gate
187c478bdstevel@tonic-gate#ident	"%Z%%M%	%I%	%E% SMI"	/* SVr4.0 1.1	*/
197c478bdstevel@tonic-gate
207c478bdstevel@tonic-gate/* LINTLIBRARY */
217c478bdstevel@tonic-gate
227c478bdstevel@tonic-gate#include <mp.h>
237c478bdstevel@tonic-gate#include "libmp.h"
247c478bdstevel@tonic-gate#include <sys/types.h>
257c478bdstevel@tonic-gate#include <stdlib.h>
267c478bdstevel@tonic-gate
277c478bdstevel@tonic-gatestatic void
287c478bdstevel@tonic-gatem_add(MINT *a, MINT *b, MINT *c)
297c478bdstevel@tonic-gate{
307c478bdstevel@tonic-gate	int carry, i;
317c478bdstevel@tonic-gate	int x;
327c478bdstevel@tonic-gate	short *cval;
337c478bdstevel@tonic-gate
347c478bdstevel@tonic-gate	cval = _mp_xalloc(a->len + 1, "m_add");
357c478bdstevel@tonic-gate	carry = 0;
367c478bdstevel@tonic-gate	for (i = 0; i < b->len; i++) {
377c478bdstevel@tonic-gate		x = carry + a->val[i] + b->val[i];
387c478bdstevel@tonic-gate		if (x & 0100000) {
397c478bdstevel@tonic-gate			carry = 1;
407c478bdstevel@tonic-gate			cval[i] = (short)(x & 077777);
417c478bdstevel@tonic-gate		} else {
427c478bdstevel@tonic-gate			carry = 0;
437c478bdstevel@tonic-gate			cval[i] = (short)x;
447c478bdstevel@tonic-gate		}
457c478bdstevel@tonic-gate	}
467c478bdstevel@tonic-gate	for (; i < a->len; i++) {
477c478bdstevel@tonic-gate		x = carry + a->val[i];
487c478bdstevel@tonic-gate		if (x & 0100000) {
497c478bdstevel@tonic-gate			cval[i] = (short)(x & 077777);
507c478bdstevel@tonic-gate		} else {
517c478bdstevel@tonic-gate			carry = 0;
527c478bdstevel@tonic-gate			cval[i] = (short)x;
537c478bdstevel@tonic-gate		}
547c478bdstevel@tonic-gate	}
557c478bdstevel@tonic-gate	if (carry == 1) {
567c478bdstevel@tonic-gate		cval[i] = 1;
577c478bdstevel@tonic-gate		c->len = i + 1;
587c478bdstevel@tonic-gate	} else {
597c478bdstevel@tonic-gate		c->len = a->len;
607c478bdstevel@tonic-gate	}
617c478bdstevel@tonic-gate	c->val = cval;
627c478bdstevel@tonic-gate	if (c->len == 0) {
637c478bdstevel@tonic-gate		free(cval);
647c478bdstevel@tonic-gate	}
657c478bdstevel@tonic-gate}
667c478bdstevel@tonic-gate
677c478bdstevel@tonic-gatevoid
687c478bdstevel@tonic-gatemp_madd(MINT *a, MINT *b, MINT *c)
697c478bdstevel@tonic-gate{
707c478bdstevel@tonic-gate	MINT x, y;
717c478bdstevel@tonic-gate	int sign;
727c478bdstevel@tonic-gate
737c478bdstevel@tonic-gate	x.len = y.len = 0;
747c478bdstevel@tonic-gate	_mp_move(a, &x);
757c478bdstevel@tonic-gate	_mp_move(b, &y);
767c478bdstevel@tonic-gate	_mp_xfree(c);
777c478bdstevel@tonic-gate	sign = 1;
787c478bdstevel@tonic-gate	if (x.len >= 0) {
797c478bdstevel@tonic-gate		if (y.len >= 0) {
807c478bdstevel@tonic-gate			if (x.len >= y.len) {
817c478bdstevel@tonic-gate				m_add(&x, &y, c);
827c478bdstevel@tonic-gate			} else {
837c478bdstevel@tonic-gate				m_add(&y, &x, c);
847c478bdstevel@tonic-gate			}
857c478bdstevel@tonic-gate		} else {
867c478bdstevel@tonic-gate			y.len = -y.len;
877c478bdstevel@tonic-gate			mp_msub(&x, &y, c);
887c478bdstevel@tonic-gate		}
897c478bdstevel@tonic-gate	} else {
907c478bdstevel@tonic-gate		if (y.len <= 0) {
917c478bdstevel@tonic-gate			x.len = -x.len;
927c478bdstevel@tonic-gate			y.len = -y.len;
937c478bdstevel@tonic-gate			sign = -1;
947c478bdstevel@tonic-gate			mp_madd(&x, &y, c);
957c478bdstevel@tonic-gate		} else {
967c478bdstevel@tonic-gate			x.len = -x.len;
977c478bdstevel@tonic-gate			mp_msub(&y, &x, c);
987c478bdstevel@tonic-gate		}
997c478bdstevel@tonic-gate	}
1007c478bdstevel@tonic-gate	c->len = sign * c->len;
1017c478bdstevel@tonic-gate	_mp_xfree(&x);
1027c478bdstevel@tonic-gate	_mp_xfree(&y);
1037c478bdstevel@tonic-gate}
1047c478bdstevel@tonic-gate
1057c478bdstevel@tonic-gatestatic void
1067c478bdstevel@tonic-gatem_sub(MINT *a, MINT *b, MINT *c)
1077c478bdstevel@tonic-gate{
1087c478bdstevel@tonic-gate	int x, i;
1097c478bdstevel@tonic-gate	int borrow;
1107c478bdstevel@tonic-gate	short one;
1117c478bdstevel@tonic-gate	MINT mone;
1127c478bdstevel@tonic-gate
1137c478bdstevel@tonic-gate	one = 1;
1147c478bdstevel@tonic-gate	mone.len = 1;
1157c478bdstevel@tonic-gate	mone.val = &one;
1167c478bdstevel@tonic-gate	c->val = _mp_xalloc(a->len, "m_sub");
1177c478bdstevel@tonic-gate	borrow = 0;
1187c478bdstevel@tonic-gate	for (i = 0; i < b->len; i++) {
1197c478bdstevel@tonic-gate		x = borrow + a->val[i] - b->val[i];
1207c478bdstevel@tonic-gate		if (x & 0100000) {
1217c478bdstevel@tonic-gate			borrow = -1;
1227c478bdstevel@tonic-gate			c->val[i] = (short)(x & 077777);
1237c478bdstevel@tonic-gate		} else {
1247c478bdstevel@tonic-gate			borrow = 0;
1257c478bdstevel@tonic-gate			c->val[i] = (short)x;
1267c478bdstevel@tonic-gate		}
1277c478bdstevel@tonic-gate	}
1287c478bdstevel@tonic-gate	for (; i < a->len; i++) {
1297c478bdstevel@tonic-gate		x = borrow + a->val[i];
1307c478bdstevel@tonic-gate		if (x & 0100000) {
1317c478bdstevel@tonic-gate			c->val[i] = (short)(x & 077777);
1327c478bdstevel@tonic-gate		} else {
1337c478bdstevel@tonic-gate			borrow = 0;
1347c478bdstevel@tonic-gate			c->val[i] = (short)x;
1357c478bdstevel@tonic-gate		}
1367c478bdstevel@tonic-gate	}
1377c478bdstevel@tonic-gate	if (borrow < 0) {
1387c478bdstevel@tonic-gate		for (i = 0; i < a->len; i++) {
1397c478bdstevel@tonic-gate			c->val[i] ^= 077777;
1407c478bdstevel@tonic-gate		}
1417c478bdstevel@tonic-gate		c->len = a->len;
1427c478bdstevel@tonic-gate		mp_madd(c, &mone, c);
1437c478bdstevel@tonic-gate	}
1447c478bdstevel@tonic-gate	for (i = a->len-1; i >= 0; --i) {
1457c478bdstevel@tonic-gate		if (c->val[i] > 0) {
1467c478bdstevel@tonic-gate			if (borrow == 0) {
1477c478bdstevel@tonic-gate				c->len = i + 1;
1487c478bdstevel@tonic-gate			} else {
1497c478bdstevel@tonic-gate				c->len = -i - 1;
1507c478bdstevel@tonic-gate			}
1517c478bdstevel@tonic-gate			return;
1527c478bdstevel@tonic-gate		}
1537c478bdstevel@tonic-gate	}
1547c478bdstevel@tonic-gate	free(c->val);
1557c478bdstevel@tonic-gate}
1567c478bdstevel@tonic-gate
1577c478bdstevel@tonic-gatevoid
1587c478bdstevel@tonic-gatemp_msub(MINT *a, MINT *b, MINT *c)
1597c478bdstevel@tonic-gate{
1607c478bdstevel@tonic-gate	MINT x, y;
1617c478bdstevel@tonic-gate	int sign;
1627c478bdstevel@tonic-gate
1637c478bdstevel@tonic-gate	x.len = y.len = 0;
1647c478bdstevel@tonic-gate	_mp_move(a, &x);
1657c478bdstevel@tonic-gate	_mp_move(b, &y);
1667c478bdstevel@tonic-gate	_mp_xfree(c);
1677c478bdstevel@tonic-gate	sign = 1;
1687c478bdstevel@tonic-gate	if (x.len >= 0) {
1697c478bdstevel@tonic-gate		if (y.len >= 0) {
1707c478bdstevel@tonic-gate			if (x.len >= y.len) {
1717c478bdstevel@tonic-gate				m_sub(&x, &y, c);
1727c478bdstevel@tonic-gate			} else {
1737c478bdstevel@tonic-gate				sign = -1;
1747c478bdstevel@tonic-gate				mp_msub(&y, &x, c);
1757c478bdstevel@tonic-gate			}
1767c478bdstevel@tonic-gate		} else {
1777c478bdstevel@tonic-gate			y.len = -y.len;
1787c478bdstevel@tonic-gate			mp_madd(&x, &y, c);
1797c478bdstevel@tonic-gate		}
1807c478bdstevel@tonic-gate	} else {
1817c478bdstevel@tonic-gate		if (y.len <= 0) {
1827c478bdstevel@tonic-gate			x.len = -x.len;
1837c478bdstevel@tonic-gate			y.len = -y.len;
1847c478bdstevel@tonic-gate			mp_msub(&y, &x, c);
1857c478bdstevel@tonic-gate		} else {
1867c478bdstevel@tonic-gate			x.len = -x.len;
1877c478bdstevel@tonic-gate			mp_madd(&x, &y, c);
1887c478bdstevel@tonic-gate			sign = -1;
1897c478bdstevel@tonic-gate		}
1907c478bdstevel@tonic-gate	}
1917c478bdstevel@tonic-gate	c->len = sign * c->len;
1927c478bdstevel@tonic-gate	_mp_xfree(&x);
1937c478bdstevel@tonic-gate	_mp_xfree(&y);
1947c478bdstevel@tonic-gate}
195