bigpdiv.c revision 65c4736d9c0ebc6d9b1d991593b55566909da9cd
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt/* Copyright (C) RSA Data Security, Inc. created 1986, 1996. This is an
699f790c49d03a9ef3c3234a72d272bb469203e8Evan Hunt unpublished work protected as such under copyright law. This work
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt contains proprietary, confidential, and trade secret information of
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark Andrews RSA Data Security, Inc. Use, disclosure or reproduction without the
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark Andrews express written authorization of RSA Data Security, Inc. is
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark Andrews prohibited.
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt */
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt#include "global.h"
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt#include "bigmath.h"
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt/* BigPdiv POSITIVE DIVIDE
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt uu=vv * qi+ri
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt uu in reg of ll cells
699f790c49d03a9ef3c3234a72d272bb469203e8Evan Hunt vv in reg of kk cells
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt qi assumed to be ll cells
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt ri assumed to be kk cells
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt restriction uu>=0, vv>0
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt input uu in reg of ll cells
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt input vv in reg of kk cells
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt output qi assumed to be ll cells
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt output ri assumed to be kk cells
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt restriction uu>=0, vv>0
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt uu=vv * qi+ri
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt */
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt#define UJN (u[(j+n)/2] & mk[(j+n)%2])
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt#define VN (v[n/2] & mk[n%2])
dbb012765c735ee0d82dedb116cdc7cf18957814Evan Hunt#define UT (u[t/2] & mk[t%2])
dbb012765c735ee0d82dedb116cdc7cf18957814Evan Huntvoid BigPdiv (qi, ri, uu, vv, ll, kk)
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan HuntUINT2 *qi, *ri, *uu, *vv;
dbb012765c735ee0d82dedb116cdc7cf18957814Evan Huntunsigned int ll, kk;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt{
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt UINT2 u[2 * MAX_RSA_PRIME_WORDS + 2], us[2 * MAX_RSA_PRIME_WORDS + 2],
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt v[2 * MAX_RSA_PRIME_WORDS + 2], vs[2 * MAX_RSA_PRIME_WORDS + 2],
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt q[2 * MAX_RSA_PRIME_WORDS + 2], r[2 * MAX_RSA_PRIME_WORDS + 2],
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt t1[2 * MAX_RSA_PRIME_WORDS + 2], t2[2 * MAX_RSA_PRIME_WORDS + 2],
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt t3[2 * MAX_RSA_PRIME_WORDS + 2], mk[2];
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt int j, l, n, m, t, x;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt unsigned int a, b, c, d, e, vh, qq;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt if (ll >= kk)
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt l = ll + 2;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt else
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt l = kk + 2;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt mk[0] = 0x00FF;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt mk[1] = 0xFF00;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt b = 0x0100;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigConst (u, 0, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigConst (v, 0, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigCopy (u, uu, ll);
e20788e1216ed720aefa84f3295f7899d9f28c22Mark Andrews BigCopy (us, u, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigCopy (v, vv, kk);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigCopy (vs, v, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt /* zero q */
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigConst (q, 0, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt /* Calculate len of v=n.
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt */
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt for (n = (2 * l) - 1; n >= 0; n--) {
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt if (VN == 0)
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt continue;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt break;
80169c379dd4e0a6e164b7cac4bf5fa013c91138Mark Andrews }
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt /* Normalize.
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt */
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt a = VN;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt if (n % 2 == 1)
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt a = a >> 8;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt d = b / (a+1);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigConst (t1, d, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigPmpyl (t2, t1, v, l);
acbb301e648b82fcc38b876a44403cf0fe539cc9Evan Hunt BigCopy (v, t2, l);
acbb301e648b82fcc38b876a44403cf0fe539cc9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt /* vh=high order digit of normalized v */
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt vh = VN;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt if (n % 2 == 1)
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt vh = vh >> 8;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigPmpyl (t2, t1, u, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigCopy (u, t2, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt /* Calculate len of u=t.
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt */
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt for (t = (2 * l)-1; t >= 0; t--) {
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt if (UT == 0)
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt continue;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt break;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt }
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt /* calc t = n + m */
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt m = t - n;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt /* Divide u by v.
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt */
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt for (j = m + 1 + n; j > n; j--) {
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt if (j % 2 == 1)
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt c = u[j / 2];
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt else {
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt a = u[j/2];
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt a = a << 8;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt e = u[(j - 1) / 2];
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt e = e >> 8;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt c = a + e;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt }
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt a = c >> 8;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt if (vh == a)
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt qq = b - 1;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt else
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt qq = c / vh;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigConst (t1, qq, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigPmpyl (t2, v, t1, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt Big2Exp (t3, (j - 1 - n) * 8, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigPmpyl (t1, t3, t2, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigSub (t2, u, t1, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt /* Adjust q.
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt */
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt for (x = 0; ; qq --, x ++) {
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt if (BigSign (t2, l) != -1)
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt break;
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigPmpyl (t1, t3, v, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigAdd (t2, t2, t1, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt }
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigCopy (u, t2, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigConst (t3, qq, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt Big2Exp (t2, 8, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigPmpyl (t1, q, t2, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigAdd (q, t3, t1, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt }
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt /* Check result.
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt */
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigPmpyl (t1, vs, q, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt /* t2 has remainder */
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigSub (t2, us, t1, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigSub (t3, vs, t2, l);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt /* transfer results to input registers */
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigCopy (qi, q, ll);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt BigCopy (ri, t2, kk);
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt T_memset ((POINTER)u, 0, sizeof (u));
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt T_memset ((POINTER)us, 0, sizeof (us));
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt T_memset ((POINTER)v, 0, sizeof (v));
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt T_memset ((POINTER)vs, 0, sizeof (vs));
dbb012765c735ee0d82dedb116cdc7cf18957814Evan Hunt T_memset ((POINTER)q, 0, sizeof (q));
dbb012765c735ee0d82dedb116cdc7cf18957814Evan Hunt T_memset ((POINTER)r, 0, sizeof (r));
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt T_memset ((POINTER)t1, 0, sizeof (t1));
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt T_memset ((POINTER)t2, 0, sizeof (t2));
ba751492fcc4f161a18b983d4f018a1a52938cb9Evan Hunt T_memset ((POINTER)t3, 0, sizeof (t3));
f5c17a057fc5974bb51d7bc8c5827a7fd6dc9aeeEvan Hunt}
f5c17a057fc5974bb51d7bc8c5827a7fd6dc9aeeEvan Hunt