2N/A/* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
2N/A/* All Rights Reserved */
2N/A
2N/A
2N/A/*
2N/A * Copyright (c) 1980 Regents of the University of California.
2N/A * All rights reserved. The Berkeley software License Agreement
2N/A * specifies the terms and conditions for redistribution.
2N/A */
2N/A/* Portions Copyright(c) 1988, Sun Microsystems Inc. */
2N/A/* All Rights Reserved */
2N/A
2N/A/*
2N/A * Copyright (c) 1997, by Sun Microsystems, Inc.
2N/A * All rights reserved.
2N/A */
2N/A
2N/A#ident "%Z%%M% %I% %E% SMI" /* SVr4.0 1.1 */
2N/A
2N/A/* LINTLIBRARY */
2N/A
2N/A#include <mp.h>
2N/A#include <sys/types.h>
2N/A#include "libmp.h"
2N/A
2N/Astatic void m_mult(MINT *, MINT *, MINT *);
2N/A
2N/Avoid
2N/Amp_mult(MINT *a, MINT *b, MINT *c)
2N/A{
2N/A struct mint x, y;
2N/A int sign;
2N/A
2N/A _mp_mcan(a);
2N/A _mp_mcan(b);
2N/A if (a->len == 0 || b->len == 0) {
2N/A _mp_xfree(c);
2N/A return;
2N/A }
2N/A sign = 1;
2N/A x.len = y.len = 0;
2N/A _mp_move(a, &x);
2N/A _mp_move(b, &y);
2N/A if (a->len < 0) {
2N/A x.len = -x.len;
2N/A sign = -sign;
2N/A }
2N/A if (b->len < 0) {
2N/A y.len = -y.len;
2N/A sign = -sign;
2N/A }
2N/A _mp_xfree(c);
2N/A if (x.len < y.len) {
2N/A m_mult(&x, &y, c);
2N/A } else {
2N/A m_mult(&y, &x, c);
2N/A }
2N/A if (sign < 0)
2N/A c->len = -c->len;
2N/A if (c->len == 0)
2N/A _mp_xfree(c);
2N/A _mp_xfree(&x);
2N/A _mp_xfree(&y);
2N/A}
2N/A
2N/A/*
2N/A * Knuth 4.3.1, Algorithm M
2N/A */
2N/Astatic void
2N/Am_mult(MINT *a, MINT *b, MINT *c)
2N/A{
2N/A int i, j;
2N/A int sum;
2N/A short bcache;
2N/A short *aptr;
2N/A short *bptr;
2N/A short *cptr;
2N/A short fifteen = 15;
2N/A int alen;
2N/A int blen;
2N/A
2N/A#define BASEBITS (8 * (unsigned int)sizeof (short) - 1)
2N/A#define BASE (1 << BASEBITS)
2N/A#define LOWBITS (BASE - 1)
2N/A
2N/A alen = a->len;
2N/A blen = b->len;
2N/A
2N/A c->len = alen + blen;
2N/A c->val = _mp_xalloc(c->len, "m_mult");
2N/A
2N/A aptr = a->val;
2N/A bptr = b->val;
2N/A cptr = c->val;
2N/A
2N/A sum = 0;
2N/A bcache = *bptr++;
2N/A for (i = alen; i > 0; i--) {
2N/A sum += *aptr++ * bcache;
2N/A *cptr++ = (short)(sum & LOWBITS);
2N/A if (sum >= 0)
2N/A sum >>= fifteen;
2N/A else
2N/A sum = 0xfffe0000 | (sum >> fifteen);
2N/A }
2N/A *cptr = (short)sum;
2N/A aptr -= alen;
2N/A cptr -= alen;
2N/A cptr++;
2N/A
2N/A for (j = blen - 1; j > 0; j--) {
2N/A sum = 0;
2N/A bcache = *bptr++;
2N/A for (i = alen; i > 0; i--) {
2N/A sum += *aptr++ * bcache + *cptr;
2N/A *cptr++ = (short)(sum & LOWBITS);
2N/A if (sum >= 0)
2N/A sum >>= fifteen;
2N/A else
2N/A sum = 0xfffe0000 | (sum >> fifteen);
2N/A }
2N/A *cptr = (short)sum;
2N/A aptr -= alen;
2N/A cptr -= alen;
2N/A cptr++;
2N/A }
2N/A if (c->val[c->len-1] == 0) {
2N/A c->len--;
2N/A }
2N/A}