vlongvalue.cpp

椭圆曲线密码C实现的

#include "stdafx.h"
#include "vlongvalue.h"
/////////////////////////////////////////////////////////////////////////

unsigned flex_unit::get( unsigned i ) const
{
  if ( i >= n ) return 0;
  return a[i];
}

void flex_unit::clear()
{
   n = 0;
}

flex_unit::flex_unit()
{
  z = 0;
  a = 0;
  n = 0;
}

flex_unit::~flex_unit()
{
  unsigned i=z;
  while (i) { 
	  i-=1; a[i] = 0; 
  } // burn
  delete [] a;
}

void flex_unit::reserve( unsigned x )
{
  if (x > z)
  {
    unsigned * na = new unsigned[x];
    for (unsigned i=0;i<n;i+=1) na[i] = a[i];
    delete [] a;
    a = na;
    z = x;
  }
}

void flex_unit::set( unsigned i, unsigned x )
{
	if ( i < n )
	{
		a[i] = x;
		if (x==0) 
		{
			while (n && a[n-1]==0) 
				n-=1; // normalise
		}
	}else{
		if ( x ){
			reserve(i+1);
			for (unsigned j=n;j<i;j+=1) 
				a[j] = 0;
			a[i] = x;
			n = i+1;
		}
	}
}

void flex_unit::fast_mul( flex_unit &x, flex_unit &y, unsigned keep )
{
  // *this = (x*y) % (2**keep)
  unsigned i,limit = (keep+BPU-1)/BPU; // size of result in words
  reserve(limit); 
  for (i=0; i<limit; i+=1)
  {
	  a[i] = 0;
  }
  unsigned min = x.n; 
  if (min>limit) 
	  min = limit;
  for (i=0; i<min; i+=1)
  {
	  unsigned m = x.a[i];
	  unsigned c = 0; // carry
	  unsigned min = i+y.n; 
	  if (min>limit) 
		  min = limit;
	  for ( unsigned j=i; j<min; j+=1 )
	  {
		  // This is the critical loop
		  // Machine dependent code could help here
		  // c:a[j] = a[j] + c + m*y.a[j-i];
		  unsigned w, v = a[j], p = y.a[j-i];
		  v += c; c = ( v < c );
		  int x1 = lo(p);
		  int x2 = lo(m);
		  int x3 = hi(p);
		  int x4 = hi(m);
		  w = lo(p)*lo(m); 
		  v += w; 
		  c += ( v < w );
		  w = lo(p)*hi(m); 
		  c += hi(w); 
		  w = lh(w); 
		  v += w; 
		  c += ( v < w );
		  w = hi(p)*lo(m); 
		  c += hi(w); 
		  w = lh(w); 
		  v += w; 
		  c += ( v < w );
		  c += hi(p) * hi(m);
		  a[j] = v;
	  }
	  
	  while ( c && j<limit )
	  {
		  a[j] += c;
		  c = a[j] < c;
		  j += 1;
	  }
  }

  // eliminate unwanted bits
  keep %= BPU; if (keep) a[limit-1] &= (1<<keep)-1;

   // calculate n
  while (limit && a[limit-1]==0) limit-=1;
  n = limit;
}

////////////////////////////////////////////////////////////////////////////////
vlong_value::operator unsigned()
{
  return get(0);
}

int vlong_value::is_zero() const
{
  return n==0;
}

int vlong_value::test( unsigned i ) const
{
	return ( get(i/BPU) & (1<<(i%BPU)) ) != 0; 
}

unsigned vlong_value::bits() const
{
  unsigned x = n*BPU;
  while (x && test(x-1)==0) x -= 1;
  return x;
}

int vlong_value::cf( vlong_value& x ) const
{
  if ( n > x.n ) return +1;
  if ( n < x.n ) return -1;
  unsigned i = n;
  while (i)
  {
    i -= 1;
    if ( get(i) > x.get(i) ) return +1;
    if ( get(i) < x.get(i) ) return -1;
  }
  return 0;
}

void vlong_value::shl()
{
  unsigned carry = 0;
  unsigned N = n; // necessary, since n can change
  for (unsigned i=0;i<=N;i+=1)
  {
    unsigned u = get(i);
    set(i,(u<<1)+carry);
    carry = u>>(BPU-1);
  }
}

void vlong_value::shr()
{
  unsigned carry = 0;
  unsigned i=n;
  while (i)
  {
    i -= 1;
    unsigned u = get(i);
    set(i,(u>>1)+carry);
    carry = u<<(BPU-1);
  }
}

void vlong_value::shr( unsigned x )
{
  unsigned delta = x/BPU; x %= BPU;
  for (unsigned i=0;i<n;i+=1)
  {
    unsigned u = get(i+delta);
    if (x)
    {
      u >>= x;
      u += get(i+delta+1) << (BPU-x);
    }
    set(i,u);
  }
}

void vlong_value::add( vlong_value & x )
{
  unsigned carry = 0;
  unsigned max = n; if (max<x.n) max = x.n;
  reserve(max);
  for (unsigned i=0;i<max+1;i+=1)
  {
    unsigned u = get(i);
    u = u + carry; carry = ( u < carry );
    unsigned ux = x.get(i);
    u = u + ux; carry += ( u < ux );
    set(i,u);
  }
}

void vlong_value::subtract( vlong_value & x )
{
  unsigned carry = 0;
  unsigned N = n;
  for (unsigned i=0;i<N;i+=1)
  {
    unsigned ux = x.get(i);
    ux += carry;
    if ( ux >= carry )
    {
      unsigned u = get(i);
      unsigned nu = u - ux;
      carry = nu > u;
      set(i,nu);
    }
  }
}

void vlong_value::init( unsigned x )
{
  clear();
  set(0,x);
}

void vlong_value::copy( vlong_value& x )
{
  clear();
  unsigned i=x.n;
  while (i) { i -= 1; set( i, x.get(i) ); }
}

vlong_value::vlong_value()
{
  share = 0;
}

void vlong_value::mul( vlong_value& x, vlong_value& y )
{
  fast_mul( x, y, x.bits()+y.bits() );
}

void vlong_value::divide( vlong_value& x, vlong_value& y, vlong_value& rem )
{
  init(0);
  rem.copy(x);
  vlong_value m,s;
  m.copy(y);
  s.init(1);

  while ( rem.cf(m) > 0 )
  {
    m.shl();
    s.shl();
  }

  while ( rem.cf(y) >= 0 )
  {
    while ( rem.cf(m) < 0 )
    {
      m.shr();
      s.shr();
    }
    rem.subtract( m );
    add( s );
  }

}