mint.c

网络中交换节点的上数据的交换和下行数据分发的硬件实现

  /* Correct estimate.
   */
  while ((t[1] > 0) || ((t[1] == 0) && t[0] >= c)) {
    if ((t[0] -= c) > (MAX_CMP_WORD - c))
      -- t[1];
    ++ aLow;
  }
  
  *a = TO_HIGH_HALF (aHigh) + aLow;
}
  /* a = b - c * d, where a, b and d are all length-digit number, while c is
     a digit.
   return borrow.
 */
static DWord CMP_SubProduct (DWord *a,DWord *b,DWord c,
							 DWord *d,unsigned int length)
{
  DWord borrow, t[2];
  unsigned int i;

  borrow = 0;
  for (i = 0; i < length; ++ i) 
  {
    DWordMult (t, c, d[i]);

    if ((borrow += t[0]) < t[0]) 
      ++ t[1];
    if ((a[i] = b[i] - borrow) > (MAX_CMP_WORD - borrow)) 
      borrow = t[1] + 1;
    else
      borrow = t[1];
  }
  return (borrow);
}
  /* Compare a and b, where a and b are length-word CMPWord arrays.
   return  1 if a > b, 
          -1 if a < b, 
           0 if a = b.
 */
static int CMP_ArrayCmp (DWord *a,DWord *b,unsigned int length)
{
  int i;

  for (i = (int)length - 1; i >= 0; -- i) {
    if (a[i] > b[i])
      return (1);
    else if (a[i] < b[i])
      return (-1);
  }
  return (0);
} 

/* quotient and remainder cannot be one of dividend and divisor */
//weiecho
int MI_Divide (MInt *dividend,MInt *divisor,
			   MInt *quotient,MInt *remainder)
{
  DWord ai, t, *aa, *cc, *dd;
  DWord a;
  int i, status;
  unsigned int ccWords, ddWords, shift;
  
  MI_RecomputeLength (dividend->length,dividend);
  MI_RecomputeLength (divisor->length,divisor);

  do 
  {
    if (MI_Compare (dividend, divisor) < 0) 
    {
      MI_WordToMInt (0, quotient);
      status = MI_Move (dividend, remainder);
      break;
    }

    MI_Move(dividend, remainder);

    /* Normalize operands. */                    
    a=divisor->value[divisor->length-1];
    for(i=0;(i<CMP_WORD_SIZE)&&(a!=0);++i,a>>=1);
    /*i = CMP_WordBits (divisor->value[divisor->length - 1]);*/

    shift = CMP_WORD_SIZE - i;
    ccWords = remainder->length;
    cc = remainder->value;
    if ((cc[ccWords] = 
    	CMP_ArrayLeftShift (cc, shift, ccWords)) != 0) 
      cc[++ ccWords] = 0;

    ddWords = divisor->length;
    dd = divisor->value;
    CMP_ArrayLeftShift (dd, shift, ddWords);
/*===========================*/
    t = dd[ddWords - 1];
    aa = quotient->value;
  
    for (i = ccWords - ddWords; i >= 0; -- i) 
    {
      /* Underestimate quotient digit and subtract.   */
      if (t == MAX_CMP_WORD)
        ai = cc[i + ddWords];
      else
        CMP_WordDiv (&ai, &cc[i + ddWords - 1], t + 1);
      cc[i + ddWords] -= CMP_SubProduct (&cc[i], &cc[i], ai, dd, ddWords);

      /* Correct estimate.       */
      while (cc[i + ddWords] || (CMP_ArrayCmp (&cc[i], dd, ddWords) >= 0)) {
        ++ ai;
        cc[i + ddWords] -= CMP_ArraySub (&cc[i], &cc[i], dd, ddWords);
      }
      aa[i] = ai;
    }

    CMP_ArrayRightShift (dd, shift, ddWords);
    CMP_ArrayRightShift (cc, shift, ddWords);
    MI_RecomputeLength (ddWords, remainder);
    MI_RecomputeLength (ccWords - ddWords + 1, quotient);
  } while (0);
              
  return 0;
}
int MI_ModularReduce (MInt *operand,MInt *modulus,MInt *reducedValue)
{
  DWord ai, t, *cc, *dd;
  dword a;
  int i, status;
  unsigned int ccWords, ddWords, shift;
  MI_RecomputeLength (operand->length,operand);
  MI_RecomputeLength (modulus->length,modulus);

  do {

    if (MI_Compare (operand, modulus) < 0) {
      status = MI_Move (operand, reducedValue);
      break;
    }

    if ((status = MI_Move (operand, reducedValue)) != 0)
      break;

    // Normalize operands.     
    a=modulus->value[modulus->length-1];
    for(i=0;(i<CMP_WORD_SIZE)&&(a!=0);++i,a>>=1);
    
    shift = CMP_WORD_SIZE - i;

    ccWords = reducedValue->length;
    cc = reducedValue->value;
    if ((cc[ccWords] = CMP_ArrayLeftShift (cc, shift, ccWords)) != 0) 
      cc[++ ccWords] = 0;

    ddWords = modulus->length;
    dd = modulus->value;
    CMP_ArrayLeftShift (dd, shift, ddWords);
    t = dd[ddWords - 1];

    for (i = ccWords - ddWords; i >= 0; -- i) {
      // Underestimate quotient digit and subtract.
     if (t == MAX_CMP_WORD)
        ai = cc[i + ddWords];
      else
        CMP_WordDiv (&ai, &cc[i + ddWords - 1], t + 1);
      cc[i + ddWords] -= CMP_SubProduct (&cc[i], &cc[i], ai, dd, ddWords);

      // Correct estimate.
      while (cc[i + ddWords] || (CMP_ArrayCmp (&cc[i], dd, ddWords) >= 0)) {
        cc[i + ddWords] -= CMP_ArraySub (&cc[i], &cc[i], dd, ddWords);
      }
    }

    CMP_ArrayRightShift (dd, shift, ddWords);
    CMP_ArrayRightShift (cc, shift, ddWords);
    MI_RecomputeLength (ddWords, reducedValue);
  } while (0); 
    
  return 0;
}
//===================================
int MI_ShiftRightByDWords (int shiftWordCount,MInt * theInt)
{
	int i;
    for (i = 0; i < theInt->length - shiftWordCount; ++ i)
      theInt->value [i] = theInt->value [i + shiftWordCount];
    if (i <= 0)
	{
      theInt->length = 1;
      theInt->value[0] = 0;
    }
    else
      theInt->length -= shiftWordCount;
	return (0);

}
MI_ShiftLeftByBits(int shiftBitCount, MInt *theInt)
{
	unsigned int temp,shiftInc=0;
	int i;
	for(i=0;i<theInt->length;i++)
	{
		temp=theInt->value[i];
		theInt->value[i]=(temp<<shiftBitCount)|shiftInc;
		shiftInc=temp>>(MI_WORD_SIZE-shiftBitCount);
	}
	if(shiftInc)theInt->value[(theInt->length)++]=shiftInc;
	return 0;	
}
int MI_ShiftRightByBits (int shiftBitCount, MInt *theInt)
{
	DWord r, wordLeft;
	int bitsLeft, i, offset, shiftBits;
  
	offset = shiftBitCount / MI_WORD_SIZE;
	shiftBits = shiftBitCount % MI_WORD_SIZE;
	if (shiftBits == 0) 
		return (MI_ShiftRightByDWords (offset, theInt));
  
	bitsLeft = MI_WORD_SIZE - shiftBits;
	if (offset < theInt->length ) 
	{	
		wordLeft = shiftBits ? theInt->value[offset] >> shiftBits : 0;
		for (i = 1; i < theInt->length - offset; ++ i) 
		{
			r = theInt->value[i + offset];
			theInt->value[i - 1] = (r << bitsLeft) | wordLeft;
			wordLeft = shiftBits ? r >> shiftBits : 0;
		}
		theInt->value[theInt->length - offset - 1] = wordLeft;

		MI_RecomputeLength (theInt->length - offset, theInt);
	}
	else
	{
		theInt->length = 1;
		theInt->value[0] = 0;
	}  
	return (0);
}

// Assume that bitIndex begins from 0
int MI_GetBit (int bitIndex,MInt *theInt,int *theBit)
{
  int wordIndex;

  wordIndex = bitIndex / MI_WORD_SIZE;
  do {
    if (wordIndex >= (theInt->length)) 
	{
      *theBit = 0;
      break;
    }
    bitIndex %= MI_WORD_SIZE;
    *theBit = (theInt->value[wordIndex] >> bitIndex) & 1;
  } while (0);
  return (0);
}

//weiecho
int MI_RecomputeLength (int targetLength,MInt *theInt)
{
	int i;

	for (i = targetLength - 1; i >= 0; -- i)
		if (theInt->value[i] != 0)
			break;
	theInt->length = i + 1;
	return (0);
}
///////////////////////////////////////////////

// Computes theInt = theInt + k (mod prime)
int FP_AddDWord (DWord k, MInt *prime,MInt *theInt)
{
	MInt t;
    MI_AddDWord (k, theInt);
    if (MI_Compare (theInt, prime) >= 0)
	{
      MI_ModularReduce (theInt, prime, &t);
      MI_Move (&t, theInt);
    }
	return 0;
}

int FP_Add (MInt *addend1,MInt *addend2, 
				MInt *modulus,MInt *sum)
{
	MInt t;
    MI_Add (addend1, addend2, &t);
    if (MI_Compare (&t, modulus) >= 0)
		MI_Subtract (&t, modulus, sum);
    else 
		MI_Move (&t, sum);
	return 0;
}

int FP_Substract (MInt *minuend,MInt *subtrahend,
					 MInt *modulus,MInt *difference)
{
	MInt  t;
	int status;

    status = MI_Subtract (minuend, subtrahend, &t);
    if(status==0)
	    MI_Move (&t, difference);
	else
        MI_Subtract (modulus, &t, difference);
    return 0;
  
}
//weiecho
int FP_Invert (MInt *operand,MInt *modulus,MInt *inverse)
{
	MInt q, t1, t3, u1, u3, v1, v3, w;
	int u1Sign;
    MI_WordToMInt (1, &u1);
    MI_WordToMInt (0, &v1);
    MI_Move (operand, &u3);
    MI_Move (modulus, &v3);

    u1Sign = 1;
	while (v3.length != 0 ) 
	{
		MI_Divide (&u3, &v3, &q, &t3);
		MI_Multiply (&q, &v1, &w);
		MI_Add (&u1, &w, &t1);
		MI_Move (&v1, &u1);
		MI_Move (&t1, &v1);
		MI_Move (&v3, &u3);
		MI_Move (&t3, &v3);
		u1Sign = -u1Sign;
    }

    if (u1Sign < 0) 
		MI_Subtract (modulus, &u1, inverse);
    else 
		MI_Move (&u1, inverse);
    
	return 0;
}


int FP_Mul(MInt *a,MInt *b,MInt *p,MInt *product)
{
	MI_Multiply (a, b, product);
	MI_ModularReduce (product, p, product);
	return 0;
}
//===============================
//*********************************************
//==============================================
static int DW_AddProduct2(DWord *a,const DWord c,const DWord *d,
						  const DWord c1,const DWord *d1, unsigned int length)
{
  register DWord carry;
  dword t[2];
  unsigned int i;

  carry = 0;
  for (i = 0; i < length; ++ i) 
  {
    DWordMult (t, c, d[i]);
    if ((a[i] = a[i] + carry) < carry)	carry = 1;
	else	carry = 0;
    if ((a[i] += t[0]) < t[0])
      ++ carry;
    carry += t[1];
  }
  a[i]+=carry;

  carry = 0;
  for (i = 0; i < length; ++ i) 
  {
    DWordMult (t, c1, d1[i]);
    if ((a[i] = a[i] + carry) < carry)	carry = 1;
	else	carry = 0;
    if ((a[i] += t[0]) < t[0])
      ++ carry;
    carry += t[1];
  }
  if ((a[i] = a[i] + carry) < carry)
	  carry = 1;
  else	carry = 0;
  
  return (carry);
}

int Generate_A_N0(MInt *N,MInt *A,dword *N0)
{

  	
	int i,length;
	MInt R,one, t;
	//init
	R.length=2;	R.value[0]=0;	R.value[1]=1;  //r0=2^32
	one.length=1; one.value[0]=N->value[0];//one=m0
	FP_Invert(&one,&R,&t);
	MI_Subtract(&R,&t,&one);
	*N0=one.value[0];

	length=N->length;
	R.length=length+1;
	for(i=0;i<length;i++)
		R.value[i]=0;
	R.value[length]=1;
	MI_ModularReduce(&R,N,&t);
	FP_Mul(&t,&t,N,A);

  
 	return 0;
}