/*
     CRT.H
*/
/*
** This file is placed into the public domain by its author,
** Carey Bloodworth (Carey@Bloodworth.org) on July 16, 2001
**
** This file is part of mpntt31.c, a simple multi-prime NTT
*/


/*
** For portability reasons, I'm using 16 bit short integers.
** Obviously, for performance, you'd use a full word and some assembly.
** This means the CRT_LEN is twice the number of primes.  Assuming, of
** course, that ModInt is a 32 bit int.
*/
#define CRT_LEN (NPrimes*2)
typedef unsigned short int CRTNum;

void
ClearCRT(CRTNum *Num)
{int x;
for (x=0;x Limit[x]) {break;}

B=0;
for (x=CRT_LEN-1;x>=0;x--)
  {
   D=((UINT32)Num[x])-((UINT32)Limit[x])-B;
   B=0;
   if (D < 0) {D+=0x10000;B=1;}
   Num[x]=D;
  }
}

void
MulCRT(CRTNum *Num, ModInt Val,int Len)
/* Multiply the CRT by a ModInt */
{double P,T;

P=0;
while (Len--)
  {
   P=((double)Num[Len])*Val+P;
   T=floor(P/65536.0);
   Num[Len]=P-T*65536.0;
   P=T;
  }
}

static void
Add2CRT(CRTNum *Num1, CRTNum *Num2)
{UINT32 S,C;
 int x;

C=0;
for (x=CRT_LEN-1;x>=0;x--)
  {
   S=((UINT32)Num1[x])+((UINT32)Num2[x])+C;
   C=0;
   if (S >= 65536) {S-= 65536;C=1;}
   Num1[x]=S;
  }
}

UINT32
StripCRT(CRTNum *Num)
{double D1;int x;
 double DBase=BASE; /* global constant needed as a double */
D1=0.0;
for (x=0;x