4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync/* $NetBSD: sum.c,v 1.1.1.1.14.1 2008/04/08 21:10:55 jdc Exp $ */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync/****************************************************************
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncThe author of this software is David M. Gay.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncCopyright (C) 1998 by Lucent Technologies
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncAll Rights Reserved
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncPermission to use, copy, modify, and distribute this software and
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncits documentation for any purpose and without fee is hereby
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncgranted, provided that the above copyright notice appear in all
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsynccopies and that both that the copyright notice and this
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncpermission notice and warranty disclaimer appear in supporting
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncdocumentation, and that the name of Lucent or any of its entities
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncnot be used in advertising or publicity pertaining to
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncdistribution of the software without specific, written prior
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncpermission.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncLUCENT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncINCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncIN NO EVENT SHALL LUCENT OR ANY OF ITS ENTITIES BE LIABLE FOR ANY
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncSPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncWHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncIN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncTHIS SOFTWARE.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync****************************************************************/
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync/* Please send bug reports to David M. Gay (dmg at acm dot org,
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * with " at " changed at "@" and " dot " changed to "."). */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#include <LibConfig.h>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#include "gdtoaimp.h"
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Bigint *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef KR_headers
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncsum(a, b) Bigint *a; Bigint *b;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncsum(Bigint *a, Bigint *b)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Bigint *c;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ULong carry, *xc, *xa, *xb, *xe, y;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef Pack_32
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ULong z;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if (a->wds < b->wds) {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync c = b; b = a; a = c;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync c = Balloc(a->k);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if (c == NULL)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return NULL;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync c->wds = a->wds;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync carry = 0;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync xa = a->x;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync xb = b->x;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync xc = c->x;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync xe = xc + b->wds;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef Pack_32
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync do {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync y = (*xa & 0xffff) + (*xb & 0xffff) + carry;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync carry = (y & 0x10000) >> 16;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync z = (*xa++ >> 16) + (*xb++ >> 16) + carry;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync carry = (z & 0x10000) >> 16;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Storeinc(xc, z, y);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync while(xc < xe);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync xe += a->wds - b->wds;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync while(xc < xe) {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync y = (*xa & 0xffff) + carry;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync carry = (y & 0x10000) >> 16;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync z = (*xa++ >> 16) + carry;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync carry = (z & 0x10000) >> 16;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Storeinc(xc, z, y);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync do {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync y = *xa++ + *xb++ + carry;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync carry = (y & 0x10000) >> 16;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *xc++ = y & 0xffff;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync while(xc < xe);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync xe += a->wds - b->wds;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync while(xc < xe) {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync y = *xa++ + carry;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync carry = (y & 0x10000) >> 16;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *xc++ = y & 0xffff;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if (carry) {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if (c->wds == c->maxwds) {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync b = Balloc(c->k + 1);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if (b == NULL)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return NULL;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Bcopy(b, c);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Bfree(c);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync c = b;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync c->x[c->wds++] = 1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return c;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }