mint.c

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

// MInt.cpp: implementation of the MInt class.

#include "MInt.h"

#define HalfWord unsigned short
#define HALF_WORD_BITS   16
#define BITS_PER_BYTE    8
#define CMP_WORD_SIZE        (sizeof (DWord)*BITS_PER_BYTE)

#define MAX_CMP_WORD         (DWord)0xffffffff
#define MAX_CMP_HALF_WORD    0xffff

#define LOW_HALF(x) ((x) & MAX_CMP_HALF_WORD)
#define HIGH_HALF(x) (((x) >> HALF_WORD_BITS) & MAX_CMP_HALF_WORD)
#define TO_HIGH_HALF(x) (((DWord)(x)) << HALF_WORD_BITS)

int MI_Move (MInt *source,MInt *destination)
{
	int i;
	destination->length = source->length;
	for(i=0;i<source->length;i++)
		destination->value[i]=source->value[i];
	return 0;
}
//return 1 iff first>second;
//return o iff first=second;

//weiecho
int MI_Compare (MInt *firstMInt,MInt *secondMInt)
{
  int i;
  
  if (firstMInt->length > secondMInt->length)
  {
	  if((firstMInt->length==1)&&(firstMInt->value[0]==0))
		  return 0;
	  else
		  return (1);
  }
  else if (firstMInt->length < secondMInt->length)
  {
	  if((secondMInt->length==1)&&(secondMInt->value[0]==0))
		  return 0;
	  else
		  return (-1);
  }
  else {
    for (i = firstMInt->length - 1; i >= 0; -- i)
      if (firstMInt->value[i] > secondMInt->value[i])
        return (1);
      else if (firstMInt->value[i] < secondMInt->value[i])
        return (-1);
  }
  return (0);
}
int MI_Add (MInt *addend1,MInt *addend2,MInt *sum)
{
  DWord *a, carry, *longValue, *shortValue, word;
  int i, max, min;
  
  if (addend1->length > addend2->length) 
  {
    max = addend1->length;
    min = addend2->length;
    longValue = addend1->value;
    shortValue = addend2->value;
  }
  else {
    min = addend1->length;
    max = addend2->length;
    longValue = addend2->value;
    shortValue = addend1->value;
  }
  do {
    carry = 0;
    a = sum->value;
    for (i = 0; i < min; ++ i) 
	{
      if ((word = longValue[i] + carry) < carry) {
        carry = 1;
        word = shortValue[i];
      }
      else if ((word += shortValue[i]) < shortValue[i])
        carry = 1;
      else 
        carry = 0;
      a[i] = word;
    }
    for (i = min; i < max; ++ i)
      if ((a[i] = carry + longValue[i]) < carry)
        carry = 1;
      else
	  {
        carry = 0;
        ++ i;

        memcpy (&a[i], &longValue[i], 
          sizeof (DWord) * (max - i));
        break;
      }
    
    if (carry == 1) {
      a[max] = 1;
      sum->length = max + 1;
    }
    else
      sum->length = max;
  } while (0);  
  
  return 0;
}

int MI_AddDWord (DWord increment,MInt *base)
{
  DWord carry;
  int i, status;
  
  status = 0;
  if ((base->value[0] += increment) < increment) {
    carry = 1;
    for (i = 1; i < base->length; ++ i)
      if ((base->value[i] += 1) != 0) {
        carry = 0;
        break;
      }
    if (carry == 1) {
      do {
        base->value[base->length] = 1;
        ++ base->length;
      } while (0);
    }
  }
  return (status);
}
int MI_Subtract (MInt *minuend,MInt *subtrahend,MInt *difference)
{
  MInt  *b, *c;
  DWord ai, borrow;
  int i, status=0;

  do
  {
    if ((i = MI_Compare (minuend, subtrahend)) > 0) 
	{
      b = minuend;
      c = subtrahend;
    }
    else if (i == 0) {
      difference->length = 1;
      difference->value[0] = 0;
      break;
    }
    else {
      b = subtrahend;
      c = minuend;
      status = MI_NEGATIVE;
    }
    borrow = 0;
    for (i = 0; i < c->length ; ++ i) 
	{
      if ((borrow += c->value[i]) < c->value[i]) 
	  {
        difference->value[i] = b->value[i];
        borrow = 1;
      }
      else 
	  {
        if ((ai = b->value[i] - borrow) > (MAX_CMP_WORD - borrow))
          borrow = 1;
        else 
          borrow = 0;
        difference->value[i] = ai;
      }
    }

    for (i = c->length;i < b->length; ++ i) {
      if ((ai = b->value[i] - borrow) > MAX_CMP_WORD - borrow)
        borrow = 1;
      else
        borrow = 0;
      difference->value[i] = ai;
    }
    MI_RecomputeLength (b->length , difference);
  } while (0);

  return (status);  
}
int MI_SubtractDWord (DWord decrement,MInt *base)
{
  int borrow, i, status;

  status = 0;
  if ((base->value[0] -= decrement) > (MAX_CMP_WORD - decrement)) {
    borrow = 1;
    for (i = 1; i < base->length ; ++ i)
      if ((-- base->value[i]) != MAX_CMP_WORD) 
	  {
        borrow = 0;
        break;
      }
    if (borrow == 1) 
	{
      // this means base is only one word long 
      base->value[0] = ~ base->value[0];
      ++ base->value[0];
      status = MI_NEGATIVE;
    }
    MI_RecomputeLength (base->length , base);
  }
  return (status);
}
//==========


static void DWordMult (DWord a[2], const DWord b,const DWord c)
{
  register DWord t, u;
  HalfWord bHigh, bLow, cHigh, cLow;

  bHigh = (HalfWord)HIGH_HALF (b);
  bLow = (HalfWord)LOW_HALF (b);
  cHigh = (HalfWord)HIGH_HALF (c);
  cLow = (HalfWord)LOW_HALF (c);

  a[0] = (DWord)bLow * (DWord)cLow;
  t = (DWord)bLow * (DWord)cHigh;
  u = (DWord)bHigh * (DWord)cLow;
  a[1] = (DWord)bHigh * (DWord)cHigh;
  
  if ((t += u) < u)
    a[1] += TO_HIGH_HALF (1);
  u = TO_HIGH_HALF (t);

  if ((a[0] += u) < u)
    ++ a[1];
  a[1] += HIGH_HALF (t);
}

/* a = b + c * d, where a, b and d are all length-digit number, while c is
     a CMPWord.
   return carry.
 */
static int DW_AddProduct (DWord *a, DWord *b, DWord c, DWord *d, unsigned int length)
{
  DWord carry, t[2];
  unsigned int i;

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

int MI_Multiply(MInt *multiplicand,MInt *multiplier,MInt *product)
{
	DWord a[MINTLENGTH], *b, *c;
	int cLen, i, productLen;
  
    productLen = multiplicand->length + multiplier->length;
    
    b = multiplicand->value;
    c = multiplier->value;
    cLen = multiplier->length;
    for(i=0;i<productLen;i++)	a[i]=0;;
    
    for (i = 0; i < multiplicand->length; ++ i)
      a[cLen + i] += DW_AddProduct (&a[i], &a[i], b[i], c, cLen);
	for(i=0;i<productLen;i++)
		product->value[i]=a[i];
	MI_RecomputeLength (productLen, product);
  
	return (0);
}

//=================//        divide         //
/* a = b - c.
   a, b, c are all 'length-word' CMPWord arrays.
   return borrow.
 */
static DWord CMP_ArraySub (DWord *a,DWord *b,DWord *c,
						   unsigned int length)
{
  DWord ai, borrow;
  unsigned int i;

  borrow = 0;
  for (i = 0; i < length; ++ i) {
    if ((borrow += c[i]) < c[i]) {
      a[i] = b[i];
      borrow = 1;
    }
    else {
      if ((ai = b[i] - borrow) > (MAX_CMP_WORD - borrow))
        borrow = 1;
      else 
        borrow = 0;
      a[i] = ai;
    }
  }
  return (borrow);
}

/* a = a << bits, 
   where bits < CMP_WORD_SIZE, size of a array is "length"
   return the CMPWord shifted out.
   only used in CMP_Divide
 */
static DWord CMP_ArrayLeftShift (DWord *a,unsigned int bits,
								   unsigned int length)
{
  DWord r, shiftOut;
  unsigned int i, bitsLeft;
  
  if (bits == 0) {
    return (0);
  }
  
  bitsLeft = CMP_WORD_SIZE - bits;
  shiftOut = 0;
  for (i = 0; i < length; ++i) {
    r = a[i];
    a[i] = (r << bits) | shiftOut;
    shiftOut = r >> bitsLeft;
  }
  return (shiftOut);
}
/* a = a >> bits, 
   where bits < CMP_WORD_SIZE, size of a array is "length"
   return the CMPWord shifted out.
   only used in CMP_Divide
 */
static DWord CMP_ArrayRightShift (DWord *a,unsigned int bits,
									unsigned int length)
{
  DWord r, shiftOut;
  int i, bitsLeft;

  if (bits == 0) {
    return (0);
  }

  bitsLeft = CMP_WORD_SIZE - bits;
  shiftOut = 0;
  for (i = length - 1; i >= 0; --i) {
    r = a[i];
    a[i] = (r >> bits) | shiftOut;
    shiftOut = r << bitsLeft;
  }
  return (shiftOut);
}
 /* Sets a = b / c, where a and c are digits.
   Lengths: b[2].
   Assumes b[1] < c and HIGH_HALF (c) > 0. For efficiency, c should be
   normalized.
 */
static void CMP_WordDiv (DWord *a,DWord b[2],DWord c)
{
  DWord t[2], u, v;
  HalfWord aHigh, aLow, cHigh, cLow;

  cHigh = (HalfWord)( (c >>16) & 0xffff);
  cLow = (HalfWord)( (c&0xffff));

  t[0] = b[0];
  t[1] = b[1];

  /* Underestimate high half of quotient and subtract.   */
  if (cHigh == MAX_CMP_HALF_WORD)
    aHigh = (HalfWord)HIGH_HALF (t[1]);
  else
    aHigh = (HalfWord)(t[1] / (cHigh + 1));
  u = (DWord)aHigh * (DWord)cLow;
  v = (DWord)aHigh * (DWord)cHigh;
  if ((t[0] -= TO_HIGH_HALF (u)) > (MAX_CMP_WORD - TO_HIGH_HALF (u)))
    -- t[1];
  t[1] -= HIGH_HALF (u);
  t[1] -= v;

  /* Correct estimate.
   */
  while ((t[1] > cHigh) ||
         ((t[1] == cHigh) && (t[0] >= TO_HIGH_HALF (cLow)))) {
    if ((t[0] -= TO_HIGH_HALF (cLow)) > MAX_CMP_WORD - TO_HIGH_HALF (cLow))
      -- t[1];
    t[1] -= cHigh;
    ++ aHigh;
  }

  /* Underestimate low half of quotient and subtract.
   */
  if (cHigh == MAX_CMP_HALF_WORD)
    aLow = (HalfWord)LOW_HALF (t[1]);
  else
    aLow = 
      (HalfWord)((TO_HIGH_HALF (t[1]) + HIGH_HALF (t[0])) / (cHigh + 1));
  u = (DWord)aLow * (DWord)cLow;
  v = (DWord)aLow * (DWord)cHigh;
  if ((t[0] -= u) > (MAX_CMP_WORD - u))
    -- t[1];
  if ((t[0] -= TO_HIGH_HALF (v)) > (MAX_CMP_WORD - TO_HIGH_HALF (v)))
    -- t[1];
  t[1] -= HIGH_HALF (v);