apwrx.c

brew代码里面的一个文件

/****************************************************************************************
*
*   Title:    APWRXARM.C
*
*   Author:   R. F. Quick, Jr.
*   Created:  April 21, 1998
*   Modified: January 13, 1999
*
*   Language: Microsoft Visual C++ 5.0; ARM ?
*
*   Description:
*
*     Provides the n-bit a**x mod p function required for Diffie-Hellman
*     key exchange.
*
*     Note: this procedure returns 1 for 0**0.
*     Note: this procedure requires that p be an odd number (lsb must be 1)
*
*     This version implements Montgomery reduction and 4-bit
*     sliding-window exponent.  Also has special squaring routine.
*
*     This version uses 32-bit arithmetic, C only.
*
*   Template:
*
*     int apwrxN(int n, unsigned WORD *a, unsigned WORD *x, unsigned WORD *ax,
*       unsigned WORD *p);
*
*   Calling parameters:
*
*     n Number of bits in a, x and p.
*
*     a Input: N-bit value of a.  Stored as unsigned WORD array, with the 
*       least significant word in a[0].  Not changed during execution.
*       
*     x Input: N-bit value of x.  Stored as unsigned WORD array, with the 
*       least significant word in a[0].  Not changed during execution.
*       
*     ax  Output: N-bit value of a**x mod p.  Stored as unsigned WORD array, 
*       with the least significant word in a[0].
*
*     p Input: N-bit value of p.  Stored as unsigned WORD array, with the 
*       least significant word in a[0].  Not changed during execution.
*       
*   Return value:
*   
*     0 if no error, -1 if error.  The  error return occurs if p is all zero
*     or is an even number.
*         
*   (c) 1998, 1999 QUALCOMM Incorporated
*
Copyright (c) 1998 by QUALCOMM, Incorporated.  All Rights Reserved.
*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*/

/* <EJECT> */
/*===========================================================================

                        EDIT HISTORY FOR MODULE

This section contains comments describing changes made to the module.
Notice that changes are listed in reverse chronological order.

$PVCSPath: L:/src/asw/MSM5100/CP_REL_A/vcs/apwrx.c_v   1.0.2.0   30 Nov 2001 16:43:58   fchan  $
$Header: //depot/asic/msmshared/1x/cp/MSMSHARED_CP_CDMA.02.00.64B/apwrx.c#1 $ $DateTime: 2004/08/24 16:28:29 $ $Author: louiel $

when       who     what, where, why
--------   ---     ----------------------------------------------------------
11/20/02   va      Fixed compiler warning.
09/30/99   ks      Removed compiler warnings by added casts.
01/25/99   ck      Added code to acknowledge the STOP and OFFLINE signals if
                   they are recd in the middle of exponentiation.
01/20/99   ck      Checked in the Module with changes to generate a random
                   number, report to dog and to abort the processing

===========================================================================*/

/* <EJECT> */
/*===========================================================================

                     INCLUDE FILES FOR MODULE

===========================================================================*/
#include "comdef.h"
#include "target.h"

#if(defined (FEATURE_DH) && defined(FEATURE_DH_EXP))

#include "memory.h"
#include "apwrx.h"
#include "dog.h"
#include "msg.h"
#include "dh.h"
#include "task.h"
#include "mc.h"

/* WindowSize must be a power of 2 from 1 to 3
   (i.e. WindowSize can be 2, 4 or 8 bits) */

#define WindowSize 4
#define WindowStorage ((1 << WindowSize) - 1)
#define WindowMask ((1 << WindowSize) - 1)

static 
void WORD_mul(unsigned WORD xy[2],  /* product */
         unsigned WORD x[2],  /* first multiplier */      
         unsigned WORD y)   /* second multiplier */
{
  unsigned WORD t,u;

  /* create x0y0 and x1y1 terms and store */
  xy[0] = (x[0] & LOW)*(y & LOW);
  xy[1] = (x[0] >> (BITCT/2))*(y >> (BITCT/2));

  /* create cross terms in t and u */
  t = (x[0] & LOW)*(y >> (BITCT/2));
  u = (x[0] >> (BITCT/2))*(y & LOW);

  /* add cross terms with carry to xy[1] */
  t += u;
  if (t < u)
    xy[1] += 1 << (BITCT/2);

  /* add ls part of cross term to xy[0] with carry to xy[1] */
  u = xy[0] + (t << (BITCT/2));
  xy[1] += (u < xy[0]);
  xy[0] = u;

  /* add ms part of cross term to xy[1] */
  xy[1] += t >> (BITCT/2);
}

/* multiply multiple-precision numbers
   the extra word in xy ensures that the addition loop terminates
   with no carry, eliminating the need for checking the index */

static
void mulN(int N,        /* number of unsigned WORDs in x and y */
      unsigned WORD *x,   /* first multiplier */
      unsigned WORD *y,   /* second multiplier */
      unsigned WORD *xy)    /* product (2N+1 in size) */
{
  int i,j,k;
  unsigned WORD t[2], tx[2];

  memset(xy, 0, 2*N*sizeof(unsigned WORD));

  tx[1] = 0;

  for (i = 0; i < N; i++)
  {
    for (j = 0; j < N; j++)
    {
      tx[0] = x[i];
      WORD_mul(t,tx,y[j]);

      for (k = i+j; k < 2*N; k++)
      {
        xy[k] += t[0];
        t[0] = t[1] + (xy[k] < t[0]);
        if (t[0] == 0)
          break;
        t[1] = 0;
      }
    }
  }
}

/* square a multiple-precision number */

static
void squareN(int N,
       unsigned WORD *x,
       unsigned WORD *x2)
{
  int i,j,k;
  unsigned WORD c, d, t[2], tx[2];

  tx[1] = 0;

  for (i = 0; i < N; i++)
  {
    /* put in diagonal terms (sets x2, hence no need to initialize) */

    tx[0] = x[i];
    WORD_mul(&x2[2*i],tx,x[i]);
  }

  for (i = 0; i < N-1; i++)
  {
    /* add in twice the off-diagonal terms */

    for (j = i+1; j < N; j++)
    {
      tx[0] = x[i];
      WORD_mul(t,tx,x[j]);

      /* double t */

      d = t[0] << 1;
      c = (d < t[0]);
      t[0] = d;

      d = (t[1] << 1) + c;
      c = (d < t[1]);
      t[1] = d;
      d = c; /* save carry off end */

      for (k = i+j; k < 2*N; k++)
      {
        /* add lsw with carry to c */

        x2[k] += t[0];
        c = (x2[k] < t[0]);

        /* add c to msw with carry to d */

        t[1] += c;
        d += (t[1] < c);

        if ((t[1]|d) == 0)
          break;

        t[0] = t[1];
        t[1] = d;
        d = 0;
      }
    }
  }
}

/* find the integer quotient from dividing an unsigned WORD into a double unsigned WORD */

static
unsigned WORD divd1(unsigned WORD d[2], unsigned WORD v)
{
  int i, c;
  unsigned WORD q;

  if (v == 0) // actual first word should have been 10...0, just divide by 2**BITCT
  {
    if (d[1])
      return d[1];
    else  // special case where divisor is 0xf...f and d[] is also 0xf...f
      return 1;
  }

  if (d[1] == 0) // ms word is zero
    return d[0]/v;

  q = 0;
  c = 0;
  for (i = 0; i < BITCT; i++)
  {
    q <<= 1;

    if (d[1] & MSB)
      c = 1;
    d[1] <<= 1;
    if (d[0] & MSB)
      d[1]++;
    d[0] <<= 1;

    if (c || (v <= d[1]))
    {
      q++;
      d[1] -= v;
      c = 0;
    }
  }
  return q;
}

/* take xy % p.  p_mspos is the position of the most-significant nonzero word in p */

int modpN(int N,      /* number of unsigned WORDs in p */
      unsigned WORD *xy, /* product to be reduced (2N in size) */
      unsigned WORD *p, /* modulus */
      int xy_order    /* number of unsigned WORDs in xy */
     )
{
  int i,j,k,p_mspos;
  unsigned WORD q,t[2],tx[2],d;

  /* start with shifted p aligned with msw of xy, and step to the right,
     subtracting multiples of shifted p until xy is less than shifted p */

  /* find ms word of p */

  for (p_mspos = N-1; p_mspos >= 0; p_mspos--)
    if (p[p_mspos] != 0)
      break;

  if (p_mspos < 0)
  /* p is zero; divide would hang */
  {
    return(-1);
  }

  /* set d to msw of divisor (doesn't change during this function) */
  
  d = p[p_mspos];
  tx[1] = 0;

  for (i = xy_order-1; i >= p_mspos; i--)
  {
    if (i < xy_order-1)
      t[1] = xy[i+1];
    else
      t[1] = 0;
    t[0] = xy[i];
    while (t[1] || (t[0] >= d))
    /* loop until xy is less than shifted p */
    {
      /* Get q = approximate quotient for this step.  Compute it using
         d+1 instead of d to allow for rounding error (thereby ensuring no
         overflow during the multiplication of p by q).
         
         q can be anywhere from half the actual quotient to
         the actual quotient, depending on how much larger d+1 is compared
         to d. (With left-justified p, the range is much
         tighter, speeding up the division.) */

      if (t[1] || (t[0] > d))
        q = divd1(t, (unsigned WORD)(d+1));
      else if (t[0] < d)
        q = 0;
      else
      /* see if xy is really >= shifted p */
      {
        q = 1;
        for (j = i-1; j >= i - p_mspos; j--)
        {
          if (xy[j] > p[p_mspos+j-i])
          /* it's bigger, go do the subtraction */
            break;
          else if (xy[j] < p[p_mspos+j-i])
          /* it's smaller, stop */
          {
            q = 0;
            break;
          }
          /* continue only if the words are equal */
        }
      }

      if (q == 0)
      /* xy is less than shifted p, break out of while loop */
        break;