/* ----------------------------------------------------------------------- * * * Copyright 2007 H. Peter Anvin - All Rights Reserved * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation, Inc., * 59 Temple Place Ste 330, Boston MA 02111-1307, USA; version 2.1, * incorporated herein by reference. * * ----------------------------------------------------------------------- */ /* * pbn_mul.c * * Multiply two numbers. This could be made significantly faster for * very large numbers by using Karatsuba or FFT-based multiplication. */ #include "pbnint.h" struct pbn *pbn_mul(struct pbn *s1, struct pbn *s2) { size_t i, j, imax, jmax; struct pbn *d; pbn_limb_t *dp; const pbn_limb_t *s2p; pbn_limb_t x1; pbn_2limb_t t; pbn_limb_t c; if (s1->bits == 0) { pbn_free(s2); return s1; /* s1 == 0 */ } else if (s2->bits == 0) { pbn_free(s1); return s2; /* s2 == 0 */ } imax = (s1->bits+PBN_LIMB_BITS-1) >> PBN_LIMB_SHIFT; jmax = (s2->bits+PBN_LIMB_BITS-1) >> PBN_LIMB_SHIFT; d = pbn_new(imax+jmax); for (i = 0; i < imax; i++) { x1 = s1->num[i]; c = 0; s2p = s2->num; dp = &d->num[i]; for (j = 0; j < jmax; j++) { t = (pbn_2limb_t)x1 * (*s2p++) + *dp + c; *dp++ = (pbn_limb_t)t; c = t >> PBN_LIMB_BITS; } *dp = c; } d->minus = s1->minus ^ s2->minus; pbn_free(s1); pbn_free(s2); return pbn_adjust_bits(d); }