/*
     WMODMATH.H
*/
/*
** This file is placed into the public domain by its author,
** Carey Bloodworth (Carey@Bloodworth.org) on July 16, 2001
*/
/*
** This file deals exclusively with manipulating our
** wide ModInts.  It allows ModInts to be any size.
** The routines in here (especially ModMul) are incredibly
** slow.  They just weren't written for efficiency.  They
** were written so I could show examples of using ModInts
** of very wide sizes.
**
** This file is used by WideNTT.c and SS.c (Schonhage-Strassen)
**
** Fake our ModInt's.  This code doesn't know how big
** they are, so we can't have a structure.  So, just
** treat everything as an array.  Makes indexing in
** the calling program a little ugly, though.
*/
#include 
#include 
#include 
#include 

typedef unsigned long long int UINT64;
typedef unsigned long  int UINT32;
typedef unsigned short int UINT16;
typedef UINT16 * ModIntPtr;

extern ModIntPtr Prime;

static ModIntPtr ModMathTemp1=NULL;
static ModIntPtr ModMathTemp2=NULL;
static ModIntPtr ModMathTemp3=NULL;

#define Mod_BITS 16

/* Convert ModBits into ModWords */
/* Round up to full words.  We need 1 extra bit for ModMul */
#define ModBits2ModWords(_qr) (((_qr)+Mod_BITS-1+1)/Mod_BITS)


/* Begin low level data struct manipulations */
ModIntPtr
CB_Malloc(int HowMany,int ModWords)
{ModIntPtr p;

p=(ModIntPtr)malloc(HowMany*ModWords*sizeof(UINT16));
if (p==NULL)
  {
   printf("Unable to ModMalloc for %d of %d ModWords\n",HowMany,ModWords);
   exit(0);
  }
return p;
}

void
CB_Free(void *p)
{
if (p) free(p);
}

void
CB_Dump0(UINT16 *p,size_t Len)
{int x;
for (x=0;x DWords)
  {
   printf("CB_Copy: DWords=%d SWords=%d\n",DWords,SWords);
   exit(0);
  }
 for (x=0;x= 4) P=a[ModWords-4];
if (ModWords >= 3) P=P*65536+a[ModWords-3];
if (ModWords >= 2) P=P*65536+a[ModWords-2];
P=P*65536+a[ModWords-1];
return P;
}
#endif

int
CB_Test(ModIntPtr a,int ModWords)
{
 while (ModWords--)
   if (a[ModWords])
     return 1;
 return 0;
}

int
CB_TestBit(ModIntPtr a,int BitPos,int ModWords)
{int W;
W=BitPos / Mod_BITS;
BitPos %= Mod_BITS;
if (W >= ModWords)
  {printf("CB_TestBit W=%d BitPos=%d ModWords=%d\n",W,BitPos,ModWords);exit(0);}
return a[ModWords-W-1] & (1 << BitPos);
}

void
CB_SetBit(ModIntPtr a,int BitPos,int ModWords)
{int W;
W=BitPos / Mod_BITS;
BitPos %= Mod_BITS;
if (W >= ModWords)
  {printf("CB_SetBit W=%d BitPos=%d ModWords=%d\n",W,BitPos,ModWords);exit(0);}
a[ModWords-W-1] |= (1 << BitPos);
}

int
CB_TestLowBit(ModIntPtr a,int ModWords)
{
if (a[ModWords-1] & 1) return 1;
return 0;
}


int
CB_Cmp(ModIntPtr a, ModIntPtr b,int ModWords)
{int x;

 for (x=0;x b[x]) return 1;
    if (a[x] < b[x]) return -1;
   }
return 0;
}


UINT32
CB_Add(ModIntPtr s, ModIntPtr a, ModIntPtr b,int ModWords)
{UINT32 c = 0;
 int x;

 for (x=ModWords-1;x>=0;x--)
    {
      c    = ((UINT32)b[x]) + ((UINT32)a[x]) + c;
      s[x] = c;
      c  >>= 16;
    }
 return c;
}

void
CB_AddInt(ModIntPtr s,UINT32 v,int ModWords)
{UINT32 c = v;
 int i;

 for (i=ModWords-1;i>=0;i--)
   {
    c    = c + s[i];
    s[i] = c;
    c  >>= 16;
   }
}


UINT32
CB_Sub(ModIntPtr d,ModIntPtr a, ModIntPtr b,int ModWords)
{UINT32 c = 0;
 int x;

 for (x=ModWords-1;x>=0;x--)
   {
    c    = ((UINT32)a[x]) - ((UINT32)b[x]) - c;
    d[x] = c;
    c    = (c >> 16) & 1;
   }
 return c;
}

UINT32
CB_DivInt(ModIntPtr a,UINT32 d,ModIntPtr q,int ModWords)
{int x;
 UINT64 Z=0;

for (x=0;x=0;x--)
  {
   Z=((UINT64)s[x])*i+Z;
   s[x]=Z % 65536;
   Z   =Z / 65536;
  }
return (UINT32)Z;
}

UINT32
CB_ShiftL(ModIntPtr a,int ModWords)
{UINT32 c = 0;
 int i;

 for (i=ModWords-1;i>=0;i--)
   {
     c   |= ( ((UINT32) a[i]) << 1);
     a[i] = c;
     c    = (c >> 16) & 1;
   }
 return c;
}

void
CB_ShiftLx(ModIntPtr a,int Amt,int ModWords)
{
/* If the amount is words, this could be a whole lot faster! */
while (Amt--) CB_ShiftL(a,ModWords);
}

UINT32
CB_ShiftR(ModIntPtr a,int ModWords)
{UINT32 c = 0;
 int i;

 for (i=0;i> 1;
     c    = (c & 1) << 16;
   }
 return c;
}

void
CB_ShiftRx(ModIntPtr a,int Amt,int ModWords)
/* If the amount is words, this could be a whole lot faster! */
{
while (Amt--) CB_ShiftR(a,ModWords);
}

void
CB_Swap(ModIntPtr M1,ModIntPtr M2,int ModWords)
{int x;

 for (x=0;x>=1;}
ModCopy(Prod,b, ModWords);

while (Expon>>=1)
  {
   ModMul(b,b,b, ModWords);
   if (Expon&1) ModMul(Prod,Prod,b, ModWords);
  }
}

void
ModPow(ModIntPtr Prod,ModIntPtr Base,ModIntPtr Expon,int ModWords)
{ModIntPtr b;

b=ModMathTemp3; /* Use temp storage */
ModCopy(b,Base, ModWords);

while (!ModTestLowBit(Expon, ModWords))
  {
   ModMul(b,b,b, ModWords);
   CB_ShiftR(Expon, ModWords);
  }
ModCopy(Prod,b, ModWords);
CB_ShiftR(Expon, ModWords);

while (ModTest(Expon, ModWords))
  {
   ModMul(b,b,b, ModWords);
   if (ModTestLowBit(Expon, ModWords)) ModMul(Prod,Prod,b, ModWords);
   CB_ShiftR(Expon, ModWords);
  }
}

void
InitModMath(int MaxSize)
{
ModMathTemp1=ModMalloc(1,MaxSize);
ModMathTemp2=ModMalloc(1,MaxSize);
ModMathTemp3=ModMalloc(1,MaxSize);
}

void
DeInitModMath(void)
{
ModFree(ModMathTemp1);
ModFree(ModMathTemp2);
ModFree(ModMathTemp3);
}