From 14c7f45cdae826f88dc539c8c38dd95caf305731 Mon Sep 17 00:00:00 2001 From: Maurus Cuelenaere Date: Fri, 11 Jul 2008 15:50:46 +0000 Subject: Add zook's ZenUtils to SVN git-svn-id: svn://svn.rockbox.org/rockbox/trunk@18010 a1c6a512-1295-4272-9138-f99709370657 --- .../libraries/beecrypt-4.1.2/beecrypt/mp.c | 1537 ++++++++++++++++++++ 1 file changed, 1537 insertions(+) create mode 100755 utils/zenutils/libraries/beecrypt-4.1.2/beecrypt/mp.c (limited to 'utils/zenutils/libraries/beecrypt-4.1.2/beecrypt/mp.c') diff --git a/utils/zenutils/libraries/beecrypt-4.1.2/beecrypt/mp.c b/utils/zenutils/libraries/beecrypt-4.1.2/beecrypt/mp.c new file mode 100755 index 0000000000..82d272c17a --- /dev/null +++ b/utils/zenutils/libraries/beecrypt-4.1.2/beecrypt/mp.c @@ -0,0 +1,1537 @@ +/* + * Copyright (c) 2002, 2003 Bob Deblier + * + * This library 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; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + */ + +/*!\file mp.c + * \brief Multi-precision integer routines. + * \author Bob Deblier + * \ingroup MP_m + */ + +#define BEECRYPT_DLL_EXPORT + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include "beecrypt/mp.h" +#include "beecrypt/mpopt.h" + +#ifndef ASM_MPZERO +void mpzero(size_t size, mpw* data) +{ + while (size--) + *(data++) = 0; +} +#endif + +#ifndef ASM_MPFILL +void mpfill(size_t size, mpw* data, mpw fill) +{ + while (size--) + *(data++) = fill; +} +#endif + +#ifndef ASM_MPODD +int mpodd(size_t size, const mpw* data) +{ + return (int)(data[size-1] & 0x1); +} +#endif + +#ifndef ASM_MPEVEN +int mpeven(size_t size, const mpw* data) +{ + return !(int)(data[size-1] & 0x1); +} +#endif + +#ifndef ASM_MPZ +int mpz(size_t size, const mpw* data) +{ + while (size--) + if (*(data++)) + return 0; + return 1; +} +#endif + +#ifndef ASM_MPNZ +int mpnz(size_t size, const mpw* data) +{ + while (size--) + if (*(data++)) + return 1; + return 0; +} +#endif + +#ifndef ASM_MPEQ +int mpeq(size_t size, const mpw* xdata, const mpw* ydata) +{ + while (size--) + { + if (*xdata == *ydata) + { + xdata++; + ydata++; + } + else + return 0; + } + return 1; +} +#endif + +#ifndef ASM_MPEQX +int mpeqx(size_t xsize, const mpw* xdata, size_t ysize, const mpw* ydata) +{ + if (xsize > ysize) + { + register size_t diff = xsize - ysize; + return mpeq(ysize, xdata+diff, ydata) && mpz(diff, xdata); + } + else if (xsize < ysize) + { + register size_t diff = ysize - xsize; + return mpeq(xsize, ydata+diff, xdata) && mpz(diff, ydata); + } + else + return mpeq(xsize, xdata, ydata); +} +#endif + +#ifndef ASM_MPNE +int mpne(size_t size, const mpw* xdata, const mpw* ydata) +{ + while (size--) + { + if (*xdata == *ydata) + { + xdata++; + ydata++; + } + else + return 1; + } + return 0; +} +#endif + +#ifndef ASM_MPNEX +int mpnex(size_t xsize, const mpw* xdata, size_t ysize, const mpw* ydata) +{ + if (xsize > ysize) + { + register size_t diff = xsize - ysize; + return mpnz(diff, xdata) || mpne(ysize, xdata+diff, ydata); + } + else if (xsize < ysize) + { + register size_t diff = ysize - xsize; + return mpnz(diff, ydata) || mpne(xsize, ydata+diff, xdata); + } + else + return mpne(xsize, xdata, ydata); +} +#endif + +#ifndef ASM_MPGT +int mpgt(size_t size, const mpw* xdata, const mpw* ydata) +{ + while (size--) + { + if (*xdata < *ydata) + return 0; + if (*xdata > *ydata) + return 1; + xdata++; ydata++; + } + return 0; +} +#endif + +#ifndef ASM_MPGTX +int mpgtx(size_t xsize, const mpw* xdata, size_t ysize, const mpw* ydata) +{ + if (xsize > ysize) + { + register size_t diff = xsize - ysize; + return mpnz(diff, xdata) || mpgt(ysize, xdata + diff, ydata); + } + else if (xsize < ysize) + { + register size_t diff = ysize - xsize; + return mpz(diff, ydata) && mpgt(xsize, xdata, ydata + diff); + } + else + return mpgt(xsize, xdata, ydata); +} +#endif + +#ifndef ASM_MPLT +int mplt(size_t size, const mpw* xdata, const mpw* ydata) +{ + while (size--) + { + if (*xdata > *ydata) + return 0; + if (*xdata < *ydata) + return 1; + xdata++; ydata++; + } + return 0; +} +#endif + +#ifndef ASM_MPLTX +int mpltx(size_t xsize, const mpw* xdata, size_t ysize, const mpw* ydata) +{ + if (xsize > ysize) + { + register size_t diff = xsize - ysize; + return mpz(diff, xdata) && mplt(ysize, xdata+diff, ydata); + } + else if (xsize < ysize) + { + register size_t diff = ysize - xsize; + return mpnz(diff, ydata) || mplt(xsize, xdata, ydata+diff); + } + else + return mplt(xsize, xdata, ydata); +} +#endif + +#ifndef ASM_MPGE +int mpge(size_t size, const mpw* xdata, const mpw* ydata) +{ + while (size--) + { + if (*xdata < *ydata) + return 0; + if (*xdata > *ydata) + return 1; + xdata++; ydata++; + } + return 1; +} +#endif + +#ifndef ASM_MPGEX +int mpgex(size_t xsize, const mpw* xdata, size_t ysize, const mpw* ydata) +{ + if (xsize > ysize) + { + register size_t diff = xsize - ysize; + return mpnz(diff, xdata) || mpge(ysize, xdata+diff, ydata); + } + else if (xsize < ysize) + { + register size_t diff = ysize - xsize; + return mpz(diff, ydata) && mpge(xsize, xdata, ydata+diff); + } + else + return mpge(xsize, xdata, ydata); +} +#endif + +#ifndef ASM_MPLE +int mple(size_t size, const mpw* xdata, const mpw* ydata) +{ + while (size--) + { + if (*xdata < *ydata) + return 1; + if (*xdata > *ydata) + return 0; + xdata++; ydata++; + } + return 1; +} +#endif + +#ifndef ASM_MPLEX +int mplex(size_t xsize, const mpw* xdata, size_t ysize, const mpw* ydata) +{ + if (xsize > ysize) + { + register size_t diff = xsize - ysize; + return mpz(diff, xdata) && mple(ysize, xdata+ diff, ydata); + } + else if (xsize < ysize) + { + register size_t diff = ysize - xsize; + return mpnz(diff, ydata) || mple(xsize, xdata, ydata+diff); + } + else + return mple(xsize, xdata, ydata); +} +#endif + +#ifndef ASM_MPISONE +int mpisone(size_t size, const mpw* data) +{ + data += size; + if (*(--data) == 1) + { + while (--size) + if (*(--data)) + return 0; + return 1; + } + return 0; +} +#endif + +#ifndef ASM_MPISTWO +int mpistwo(size_t size, const mpw* data) +{ + data += size; + if (*(--data) == 2) + { + while (--size) + if (*(--data)) + return 0; + return 1; + } + return 0; +} +#endif + +#ifndef ASM_MPEQMONE +int mpeqmone(size_t size, const mpw* xdata, const mpw* ydata) +{ + xdata += size; + ydata += size; + + if (*(--xdata)+1 == *(--ydata)) + { + while (--size) + if (*(--xdata) != *(--ydata)) + return 0; + return 1; + } + return 0; +} +#endif + +#ifndef ASM_MPLEONE +int mpleone(size_t size, const mpw* data) +{ + data += size; + if (*(--data) > 1) + return 0; + else + { + while (--size) + if (*(--data)) + return 0; + return 1; + } +} +#endif + +#ifndef ASM_MPMSBSET +int mpmsbset(size_t size, const mpw* data) +{ + return (int)((*data) >> (MP_WBITS-1)); +} +#endif + +#ifndef ASM_MPLSBSET +int mplsbset(size_t size, const mpw* data) +{ + return (int)(data[size-1] & 0x1); +} +#endif + +#ifndef ASM_MPSETMSB +void mpsetmsb(size_t size, mpw* data) +{ + *data |= MP_MSBMASK; +} +#endif + +#ifndef ASM_MPSETLSB +void mpsetlsb(size_t size, mpw* data) +{ + data[size-1] |= MP_LSBMASK; +} +#endif + +#ifndef ASM_MPCLRMSB +void mpclrmsb(size_t size, mpw* data) +{ + *data &= ~ MP_MSBMASK; +} +#endif + +#ifndef ASM_MPCLRLSB +void mpclrlsb(size_t size, mpw* data) +{ + data[size-1] &= ~ MP_LSBMASK; +} +#endif + +#ifndef ASM_MPAND +void mpand(size_t size, mpw* xdata, const mpw* ydata) +{ + while (size--) + xdata[size] &= ydata[size]; +} +#endif + +#ifndef ASM_MPOR +void mpor(size_t size, mpw* xdata, const mpw* ydata) +{ + while (size--) + xdata[size] |= ydata[size]; +} +#endif + +#ifndef ASM_MPXOR +void mpxor(size_t size, mpw* xdata, const mpw* ydata) +{ + while (size--) + xdata[size] ^= ydata[size]; +} +#endif + +#ifndef ASM_MPNOT +void mpnot(size_t size, mpw* data) +{ + while (size--) + data[size] = ~data[size]; +} +#endif + +#ifndef ASM_MPSETW +void mpsetw(size_t size, mpw* xdata, mpw y) +{ + while (--size) + *(xdata++) = 0; + *(xdata++) = y; +} +#endif + +#ifndef ASM_MPSETX +void mpsetx(size_t xsize, mpw* xdata, size_t ysize, const mpw* ydata) +{ + while (xsize > ysize) + { + xsize--; + *(xdata++) = 0; + } + while (ysize > xsize) + { + ysize--; + ydata++; + } + while (xsize--) + *(xdata++) = *(ydata++); +} +#endif + +#ifndef ASM_MPADDW +int mpaddw(size_t size, mpw* xdata, mpw y) +{ + register mpw load, temp; + register int carry = 0; + + xdata += size-1; + + load = *xdata; + temp = load + y; + *(xdata--) = temp; + carry = (load > temp); + + while (--size && carry) + { + load = *xdata; + temp = load + 1; + *(xdata--) = temp; + carry = (load > temp); + } + return carry; +} +#endif + +#ifndef ASM_MPADD +int mpadd(size_t size, mpw* xdata, const mpw* ydata) +{ + register mpw load, temp; + register int carry = 0; + + xdata += size-1; + ydata += size-1; + + while (size--) + { + temp = *(ydata--); + load = *xdata; + temp = carry ? (load + temp + 1) : (load + temp); + *(xdata--) = temp; + carry = carry ? (load >= temp) : (load > temp); + } + return carry; +} +#endif + +#ifndef ASM_MPADDX +int mpaddx(size_t xsize, mpw* xdata, size_t ysize, const mpw* ydata) +{ + if (xsize > ysize) + { + register size_t diff = xsize - ysize; + return mpaddw(diff, xdata, (mpw) mpadd(ysize, xdata+diff, ydata)); + } + else + { + register size_t diff = ysize - xsize; + return mpadd(xsize, xdata, ydata+diff); + } +} +#endif + +#ifndef ASM_MPSUBW +int mpsubw(size_t size, mpw* xdata, mpw y) +{ + register mpw load, temp; + register int carry = 0; + + xdata += size-1; + + load = *xdata; + temp = load - y; + *(xdata--) = temp; + carry = (load < temp); + + while (--size && carry) + { + load = *xdata; + temp = load - 1; + *(xdata--) = temp; + carry = (load < temp); + } + return carry; +} +#endif + +#ifndef ASM_MPSUB +int mpsub(size_t size, mpw* xdata, const mpw* ydata) +{ + register mpw load, temp; + register int carry = 0; + + xdata += size-1; + ydata += size-1; + + while (size--) + { + temp = *(ydata--); + load = *xdata; + temp = carry ? (load - temp - 1) : (load - temp); + *(xdata--) = temp; + carry = carry ? (load <= temp) : (load < temp); + } + return carry; +} +#endif + +#ifndef ASM_MPSUBX +int mpsubx(size_t xsize, mpw* xdata, size_t ysize, const mpw* ydata) +{ + if (xsize > ysize) + { + register size_t diff = xsize - ysize; + return mpsubw(diff, xdata, (mpw) mpsub(ysize, xdata+diff, ydata)); + } + else + { + register size_t diff = ysize - xsize; + return mpsub(xsize, xdata, ydata+diff); + } +} +#endif + +#ifndef ASM_MPNEG +void mpneg(size_t size, mpw* data) +{ + mpnot(size, data); + mpaddw(size, data, 1); +} +#endif + +#ifndef ASM_MPSETMUL +mpw mpsetmul(size_t size, mpw* result, const mpw* data, mpw y) +{ + #if HAVE_MPDW + register mpdw temp; + register mpw carry = 0; + + data += size; + result += size; + + while (size--) + { + temp = *(--data); + temp *= y; + temp += carry; + *(--result) = (mpw) temp; + carry = (mpw)(temp >> MP_WBITS); + } + #else + register mpw temp, load, carry = 0; + register mphw ylo, yhi; + + ylo = (mphw) y; + yhi = (mphw) (y >> MP_HWBITS); + + data += size; + result += size; + + while (size--) + { + register mphw xlo, xhi; + register mpw rlo, rhi; + + xlo = (mphw) (temp = *(--data)); + xhi = (mphw) (temp >> MP_HWBITS); + + rlo = (mpw) xlo * ylo; + rhi = (mpw) xhi * yhi; + load = rlo; + temp = (mpw) xhi * ylo; + rlo += (temp << MP_HWBITS); + rhi += (temp >> MP_HWBITS) + (load > rlo); + load = rlo; + temp = (mpw) xlo * yhi; + rlo += (temp << MP_HWBITS); + rhi += (temp >> MP_HWBITS) + (load > rlo); + load = rlo; + temp = rlo + carry; + carry = rhi + (load > temp); + *(--result) = temp; + } + #endif + return carry; +} +#endif + +#ifndef ASM_MPADDMUL +mpw mpaddmul(size_t size, mpw* result, const mpw* data, mpw y) +{ + #if HAVE_MPDW + register mpdw temp; + register mpw carry = 0; + + data += size; + result += size; + + while (size--) + { + temp = *(--data); + temp *= y; + temp += carry; + temp += *(--result); + *result = (mpw) temp; + carry = (mpw)(temp >> MP_WBITS); + } + #else + register mpw temp, load, carry = 0; + register mphw ylo, yhi; + + ylo = (mphw) y; + yhi = (mphw) (y >> MP_HWBITS); + + data += size; + result += size; + + while (size--) + { + register mphw xlo, xhi; + register mpw rlo, rhi; + + xlo = (mphw) (temp = *(--data)); + xhi = (mphw) (temp >> MP_HWBITS); + + rlo = (mpw) xlo * ylo; + rhi = (mpw) xhi * yhi; + load = rlo; + temp = (mpw) xhi * ylo; + rlo += (temp << MP_HWBITS); + rhi += (temp >> MP_HWBITS) + (load > rlo); + load = rlo; + temp = (mpw) xlo * yhi; + rlo += (temp << MP_HWBITS); + rhi += (temp >> MP_HWBITS) + (load > rlo); + load = rlo; + rlo += carry; + temp = (load > rlo); + load = rhi; + rhi += temp; + carry = (load > rhi); + load = rlo; + rlo += *(--result); + *result = rlo; + carry += rhi + (load > rlo); + } + #endif + return carry; +} +#endif + +#ifndef ASM_MPMUL +void mpmul(mpw* result, size_t xsize, const mpw* xdata, size_t ysize, const mpw* ydata) +{ + /* preferred passing of parameters is x the larger of the two numbers */ + if (xsize >= ysize) + { + register mpw rc; + + result += ysize; + ydata += ysize; + + rc = mpsetmul(xsize, result, xdata, *(--ydata)); + *(--result) = rc; + + while (--ysize) + { + rc = mpaddmul(xsize, result, xdata, *(--ydata)); + *(--result) = rc; + } + } + else + { + register mpw rc; + + result += xsize; + xdata += xsize; + + rc = mpsetmul(ysize, result, ydata, *(--xdata)); + *(--result) = rc; + + while (--xsize) + { + rc = mpaddmul(ysize, result, ydata, *(--xdata)); + *(--result) = rc; + } + } +} +#endif + +#ifndef ASM_MPADDSQRTRC +void mpaddsqrtrc(size_t size, mpw* result, const mpw* data) +{ + #if HAVE_MPDW + register mpdw temp; + register mpw load, carry = 0; + + result += (size << 1); + + while (size--) + { + temp = load = data[size]; + temp *= load; + temp += carry; + temp += *(--result); + *result = (mpw) temp; + temp >>= MP_WBITS; + temp += *(--result); + *result = (mpw) temp; + carry = (mpw)(temp >> MP_WBITS); + } + #else + register mpw temp, load, carry = 0; + + result += (size << 1); + + while (size--) + { + register mphw xlo, xhi; + register mpw rlo, rhi; + + xlo = (mphw) (temp = data[size]); + xhi = (mphw) (temp >> MP_HWBITS); + + rlo = (mpw) xlo * xlo; + rhi = (mpw) xhi * xhi; + temp = (mpw) xhi * xlo; + load = rlo; + rlo += (temp << MP_HWBITS); + rhi += (temp >> MP_HWBITS) + (load > rlo); + load = rlo; + rlo += (temp << MP_HWBITS); + rhi += (temp >> MP_HWBITS) + (load > rlo); + load = rlo; + rlo += carry; + rhi += (load > rlo); + load = rlo; + rlo += *(--result); + *result = rlo; + temp = (load > rlo); + load = rhi; + rhi += temp; + carry = (load > rhi); + load = rhi; + rhi += *(--result); + *result = rhi; + carry += (load > rhi); + } + #endif +} +#endif + +#ifndef ASM_MPSQR +void mpsqr(mpw* result, size_t size, const mpw* data) +{ + register mpw rc; + register size_t n = size-1; + + result += size; + result[n] = 0; + + if (n) + { + rc = mpsetmul(n, result, data, data[n]); + *(--result) = rc; + while (--n) + { + rc = mpaddmul(n, result, data, data[n]); + *(--result) = rc; + } + } + + *(--result) = 0; + + mpmultwo(size << 1, result); + + mpaddsqrtrc(size, result, data); +} +#endif + +#ifndef ASM_MPSIZE +size_t mpsize(size_t size, const mpw* data) +{ + while (size) + { + if (*data) + return size; + data++; + size--; + } + return 0; +} +#endif + +#ifndef ASM_MPBITS +size_t mpbits(size_t size, const mpw* data) +{ + return MP_WORDS_TO_BITS(size) - mpmszcnt(size, data); +} +#endif + +#ifndef ASM_MPNORM +size_t mpnorm(size_t size, mpw* data) +{ + register size_t shift = mpmszcnt(size, data); + mplshift(size, data, shift); + return shift; +} +#endif + +#ifndef ASM_MPDIVTWO +void mpdivtwo(size_t size, mpw* data) +{ + register mpw temp, carry = 0; + + while (size--) + { + temp = *data; + *(data++) = (temp >> 1) | carry; + carry = (temp << (MP_WBITS-1)); + } +} +#endif + +#ifndef ASM_MPSDIVTWO +void mpsdivtwo(size_t size, mpw* data) +{ + int carry = mpmsbset(size, data); + mpdivtwo(size, data); + if (carry) + mpsetmsb(size, data); +} +#endif + +#ifndef ASM_MPMULTWO +int mpmultwo(size_t size, mpw* data) +{ + register mpw temp, carry = 0; + + data += size; + while (size--) + { + temp = *(--data); + *data = (temp << 1) | carry; + carry = (temp >> (MP_WBITS-1)); + } + return (int) carry; +} +#endif + +#ifndef ASM_MPMSZCNT +size_t mpmszcnt(size_t size, const mpw* data) +{ + register size_t zbits = 0; + register size_t i = 0; + + while (i < size) + { + register mpw temp = data[i++]; + if (temp) + { + while (!(temp & MP_MSBMASK)) + { + zbits++; + temp <<= 1; + } + break; + } + else + zbits += MP_WBITS; + } + return zbits; +} +#endif + +#ifndef ASM_MPLSZCNT +size_t mplszcnt(size_t size, const mpw* data) +{ + register size_t zbits = 0; + + while (size--) + { + register mpw temp = data[size]; + if (temp) + { + while (!(temp & MP_LSBMASK)) + { + zbits++; + temp >>= 1; + } + break; + } + else + zbits += MP_WBITS; + } + return zbits; +} +#endif + +#ifndef ASM_MPLSHIFT +void mplshift(size_t size, mpw* data, size_t count) +{ + register size_t words = MP_BITS_TO_WORDS(count); + + if (words < size) + { + register short lbits = (short) (count & (MP_WBITS-1)); + + /* first do the shifting, then do the moving */ + if (lbits) + { + register mpw temp, carry = 0; + register short rbits = MP_WBITS - lbits; + register size_t i = size; + + while (i > words) + { + temp = data[--i]; + data[i] = (temp << lbits) | carry; + carry = (temp >> rbits); + } + } + if (words) + { + mpmove(size-words, data, data+words); + mpzero(words, data+size-words); + } + } + else + mpzero(size, data); +} +#endif + +#ifndef ASM_MPRSHIFT +void mprshift(size_t size, mpw* data, size_t count) +{ + register size_t words = MP_BITS_TO_WORDS(count); + + if (words < size) + { + register short rbits = (short) (count & (MP_WBITS-1)); + + /* first do the shifting, then do the moving */ + if (rbits) + { + register mpw temp, carry = 0; + register short lbits = MP_WBITS - rbits; + register size_t i = 0; + + while (i < size-words) + { + temp = data[i]; + data[i++] = (temp >> rbits) | carry; + carry = (temp << lbits); + } + } + if (words) + { + mpmove(size-words, data+words, data); + mpzero(words, data); + } + } + else + mpzero(size, data); +} +#endif + +#ifndef ASM_MPRSHIFTLSZ +size_t mprshiftlsz(size_t size, mpw* data) +{ + register mpw* slide = data+size-1; + register size_t zwords = 0; /* counter for 'all zero bit' words */ + register short lbits, rbits = 0; /* counter for 'least significant zero' bits */ + register mpw temp, carry = 0; + + data = slide; + + /* count 'all zero' words and move src pointer */ + while (size--) + { + /* test if we have a non-zero word */ + if ((carry = *(slide--))) + { + /* count 'least signification zero bits and set zbits counter */ + while (!(carry & MP_LSBMASK)) + { + carry >>= 1; + rbits++; + } + break; + } + zwords++; + } + + if ((rbits == 0) && (zwords == 0)) + return 0; + + /* prepare right-shifting of data */ + lbits = MP_WBITS - rbits; + + /* shift data */ + while (size--) + { + temp = *(slide--); + *(data--) = (temp << lbits) | carry; + carry = (temp >> rbits); + } + + /* store the final carry */ + *(data--) = carry; + + /* store the return value in size */ + size = MP_WORDS_TO_BITS(zwords) + rbits; + + /* zero the (zwords) most significant words */ + while (zwords--) + *(data--) = 0; + + return size; +} +#endif + +/* try an alternate version here, with descending sizes */ +/* also integrate lszcnt and rshift properly into one function */ +#ifndef ASM_MPGCD_W +/* + * mpgcd_w + * need workspace of (size) words + */ +void mpgcd_w(size_t size, const mpw* xdata, const mpw* ydata, mpw* result, mpw* wksp) +{ + register size_t shift, temp; + + if (mpge(size, xdata, ydata)) + { + mpcopy(size, wksp, xdata); + mpcopy(size, result, ydata); + } + else + { + mpcopy(size, wksp, ydata); + mpcopy(size, result, xdata); + } + + /* get the smallest returned values, and set shift to that */ + + shift = mprshiftlsz(size, wksp); + temp = mprshiftlsz(size, result); + + if (shift > temp) + shift = temp; + + while (mpnz(size, wksp)) + { + mprshiftlsz(size, wksp); + mprshiftlsz(size, result); + + if (mpge(size, wksp, result)) + mpsub(size, wksp, result); + else + mpsub(size, result, wksp); + + /* slide past zero words in both operands by increasing pointers and decreasing size */ + if ((*wksp == 0) && (*result == 0)) + { + size--; + wksp++; + result++; + } + } + + /* figure out if we need to slide the result pointer back */ + if ((temp = MP_BITS_TO_WORDS(shift))) + { + size += temp; + result -= temp; + } + + mplshift(size, result, shift); +} +#endif + +#ifndef ASM_MPEXTGCD_W +/* needs workspace of (6*size+6) words */ +/* used to compute the modular inverse */ +int mpextgcd_w(size_t size, const mpw* xdata, const mpw* ydata, mpw* result, mpw* wksp) +{ + /* + * For computing a modular inverse, pass the modulus as xdata and the number + * to be inverted as ydata. + * + * Fact: if a element of Zn, then a is invertible if and only if gcd(a,n) = 1 + * Hence: if n is even, then a must be odd, otherwise the gcd(a,n) >= 2 + * + * The calling routine must guarantee this condition. + */ + + register size_t sizep = size+1; + register int full; + + mpw* udata = wksp; + mpw* vdata = udata+sizep; + mpw* adata = vdata+sizep; + mpw* bdata = adata+sizep; + mpw* cdata = bdata+sizep; + mpw* ddata = cdata+sizep; + + mpsetx(sizep, udata, size, xdata); + mpsetx(sizep, vdata, size, ydata); + mpzero(sizep, bdata); + mpsetw(sizep, ddata, 1); + + if ((full = mpeven(sizep, udata))) + { + mpsetw(sizep, adata, 1); + mpzero(sizep, cdata); + } + + while (1) + { + while (mpeven(sizep, udata)) + { + mpdivtwo(sizep, udata); + + if (mpodd(sizep, bdata) || (full && mpodd(sizep, adata))) + { + if (full) mpaddx(sizep, adata, size, ydata); + mpsubx(sizep, bdata, size, xdata); + } + + if (full) mpsdivtwo(sizep, adata); + mpsdivtwo(sizep, bdata); + } + while (mpeven(sizep, vdata)) + { + mpdivtwo(sizep, vdata); + + if (mpodd(sizep, ddata) || (full && mpodd(sizep, cdata))) + { + if (full) mpaddx(sizep, cdata, size, ydata); + mpsubx(sizep, ddata, size, xdata); + } + + if (full) mpsdivtwo(sizep, cdata); + mpsdivtwo(sizep, ddata); + } + if (mpge(sizep, udata, vdata)) + { + mpsub(sizep, udata, vdata); + if (full) mpsub(sizep, adata, cdata); + mpsub(sizep, bdata, ddata); + } + else + { + mpsub(sizep, vdata, udata); + if (full) mpsub(sizep, cdata, adata); + mpsub(sizep, ddata, bdata); + } + if (mpz(sizep, udata)) + { + if (mpisone(sizep, vdata)) + { + if (result) + { + if (*ddata & MP_MSBMASK) + { + /* keep adding the modulus until we get a carry */ + while (!mpaddx(sizep, ddata, size, xdata)); + } + else + { + /* in some computations, d ends up > x, hence: + * keep subtracting n from d until d < x + */ + while (mpgtx(sizep, ddata, size, xdata)) + mpsubx(sizep, ddata, size, xdata); + } + mpsetx(size, result, sizep, ddata); + } + return 1; + } + return 0; + } + } +} +#endif + +#ifndef ASM_MPPNDIV +mpw mppndiv(mpw xhi, mpw xlo, mpw y) +{ + register mpw result = 0; + register short count = MP_WBITS; + register int carry = 0; + + while (count--) + { + if (carry | (xhi >= y)) + { + xhi -= y; + result++; + } + carry = (xhi >> (MP_WBITS-1)); + xhi <<= 1; + xhi |= (xlo >> (MP_WBITS-1)); + xlo <<= 1; + result <<= 1; + } + if (carry | (xhi >= y)) + { + xhi -= y; + result++; + } + return result; +} +#endif + +#ifndef ASM_MPMOD +void mpmod(mpw* result, size_t xsize, const mpw* xdata, size_t ysize, const mpw* ydata, mpw* workspace) +{ + /* result size xsize, workspace size 2*ysize+1 */ + mpw q, msw; + mpw* rdata = result; + mpw* ynorm = workspace+ysize+1; + size_t shift, qsize = xsize-ysize; + + mpcopy(ysize, ynorm, ydata); + shift = mpnorm(ysize, ynorm); + msw = *ynorm; + mpcopy(xsize, rdata, xdata); + if (mpge(ysize, rdata, ynorm)) + mpsub(ysize, rdata, ynorm); + + while (qsize--) + { + q = mppndiv(rdata[0], rdata[1], msw); + + *workspace = mpsetmul(ysize, workspace+1, ynorm, q); + + while (mplt(ysize+1, rdata, workspace)) + { + mpsubx(ysize+1, workspace, ysize, ynorm); + q--; + } + mpsub(ysize+1, rdata, workspace); + rdata++; + } + /* de-normalization steps */ + while (shift--) + { + mpdivtwo(ysize, ynorm); + if (mpge(ysize, rdata, ynorm)) + mpsub(ysize, rdata, ynorm); + } +} +#endif + +#ifndef ASM_MPNDIVMOD +void mpndivmod(mpw* result, size_t xsize, const mpw* xdata, size_t ysize, const mpw* ydata, register mpw* workspace) +{ + /* result must be xsize+1 in length */ + /* workspace must be ysize+1 in length */ + /* expect ydata to be normalized */ + mpw q; + mpw msw = *ydata; + size_t qsize = xsize-ysize; + + *result = (mpge(ysize, xdata, ydata) ? 1 : 0); + mpcopy(xsize, result+1, xdata); + + if (*result) + (void) mpsub(ysize, result+1, ydata); + + result++; + + while (qsize--) + { + q = mppndiv(result[0], result[1], msw); + + *workspace = mpsetmul(ysize, workspace+1, ydata, q); + + while (mplt(ysize+1, result, workspace)) + { + mpsubx(ysize+1, workspace, ysize, ydata); + q--; + } + mpsub(ysize+1, result, workspace); + *(result++) = q; + } +} +#endif + +void mpprint(size_t size, const mpw* data) +{ + mpfprint(stdout, size, data); +} + +void mpprintln(size_t size, const mpw* data) +{ + mpfprintln(stdout, size, data); +} + +void mpfprint(FILE* f, size_t size, const mpw* data) +{ + if (data == (mpw*) 0) + return; + + if (f == (FILE*) 0) + return; + + while (size--) + { + #if (MP_WBITS == 32) + fprintf(f, "%08x", (unsigned) *(data++)); + #elif (MP_WBITS == 64) + # if WIN32 + fprintf(f, "%016I64x", *(data++)); + # elif SIZEOF_UNSIGNED_LONG == 8 + fprintf(f, "%016lx", *(data++)); + # else + fprintf(f, "%016llx", *(data++)); + # endif + #else + # error + #endif + } + fflush(f); +} + +void mpfprintln(FILE* f, size_t size, const mpw* data) +{ + if (data == (mpw*) 0) + return; + + if (f == (FILE*) 0) + return; + + while (size--) + { + #if (MP_WBITS == 32) + fprintf(f, "%08x", *(data++)); + #elif (MP_WBITS == 64) + # if WIN32 + fprintf(f, "%016I64x", *(data++)); + # elif SIZEOF_UNSIGNED_LONG == 8 + fprintf(f, "%016lx", *(data++)); + # else + fprintf(f, "%016llx", *(data++)); + # endif + #else + # error + #endif + } + fprintf(f, "\n"); + fflush(f); +} + +int i2osp(byte *osdata, size_t ossize, const mpw* idata, size_t isize) +{ + #if WORDS_BIGENDIAN + size_t max_bytes = MP_WORDS_TO_BYTES(isize); + #endif + size_t significant_bytes = (mpbits(isize, idata) + 7) >> 3; + + /* verify that ossize is large enough to contain the significant bytes */ + if (ossize >= significant_bytes) + { + /* looking good; check if we have more space than significant bytes */ + if (ossize > significant_bytes) + { /* fill most significant bytes with zero */ + memset(osdata, 0, ossize - significant_bytes); + osdata += ossize - significant_bytes; + } + if (significant_bytes) + { /* fill remaining bytes with endian-adjusted data */ + #if !WORDS_BIGENDIAN + mpw w = idata[--isize]; + byte shift = 0; + + /* fill right-to-left; much easier than left-to-right */ + do + { + osdata[--significant_bytes] = (byte)(w >> shift); + shift += 8; + if (shift == MP_WBITS) + { + shift = 0; + w = idata[--isize]; + } + } while (significant_bytes); + #else + /* just copy data past zero bytes */ + memcpy(osdata, ((byte*) idata) + (max_bytes - significant_bytes), significant_bytes); + #endif + } + return 0; + } + return -1; +} + +int os2ip(mpw* idata, size_t isize, const byte* osdata, size_t ossize) +{ + size_t required; + + /* skip non-significant leading zero bytes */ + while (!(*osdata) && ossize) + { + osdata++; + ossize--; + } + + required = MP_BYTES_TO_WORDS(ossize + MP_WBYTES - 1); + + if (isize >= required) + { + /* yes, we have enough space and can proceed */ + mpw w = 0; + /* adjust counter so that the loop will start by skipping the proper + * amount of leading bytes in the first significant word + */ + byte b = (ossize % MP_WBYTES); + + if (isize > required) + { /* fill initials words with zero */ + mpzero(isize-required, idata); + idata += isize-required; + } + + if (b == 0) + b = MP_WBYTES; + + while (ossize--) + { + w <<= 8; + w |= *(osdata++); + b--; + + if (b == 0) + { + *(idata++) = w; + w = 0; + b = MP_WBYTES; + } + } + + return 0; + } + return -1; +} + +int hs2ip(mpw* idata, size_t isize, const char* hsdata, size_t hssize) +{ + size_t required = MP_NIBBLES_TO_WORDS(hssize + MP_WNIBBLES - 1); + + if (isize >= required) + { + register size_t i; + + + if (isize > required) + { /* fill initial words with zero */ + for (i = required; i < isize; i++) + *(idata++) = 0; + } + while (hssize) + { + register mpw w = 0; + register size_t chunk = hssize & (MP_WNIBBLES - 1); + register char ch; + + if (chunk == 0) chunk = MP_WNIBBLES; + + for (i = 0; i < chunk; i++) + { + ch = *(hsdata++); + w <<= 4; + if (ch >= '0' && ch <= '9') + w += (ch - '0'); + else if (ch >= 'A' && ch <= 'F') + w += (ch - 'A') + 10; + else if (ch >= 'a' && ch <= 'f') + w += (ch - 'a') + 10; + } + *(idata++) = w; + hssize -= chunk; + } + return 0; + } + return -1; +} -- cgit v1.2.3