/* Author: Michael Scott */
/* Date: Dec 2007        */
/* Even Faster Duursma-Lee char 2 Tate pairing based on eta_T pairing */
/* See MIRACL dl2.cpp for more readable C++ version */
/* cl /O2 etat271.c miracl.lib  */
/* 8-bit version */
/* Half sized loop so nearly twice as fast! */

/* MIRACL mirdef.h
 * For Atmel AVR (e.g. ATmega128L) set up mirdef.h as follows 

#define MR_LITTLE_ENDIAN
#define MIRACL 8
#define mr_utype char
#define MR_IBITS 16
#define MR_LBITS 32
#define mr_unsign32 unsigned long
#define mr_dltype int
#define MR_STATIC 34
#define MR_ALWAYS_BINARY
#define MR_NOASM
#define MR_STRIPPED_DOWN
#define MR_GENERIC_MT
#define MAXBASE ((mr_small)1<<(MIRACL-1))
#define MR_BITSINCHAR 8
#define MR_NOKOBLITZ
#define MR_NO_STANDARD_IO 
#define MR_NO_FILE_IO 
#define MR_SIMPLE_BASE 
#define MR_SIMPLE_IO
#define MR_AVR
#define SP271

*/

/* use this mirdef.h to mimic 8-bit implementation on a PC
#define MR_LITTLE_ENDIAN
#define MIRACL 8
#define mr_utype char
#define MR_IBITS 32
#define MR_LBITS 32
#define mr_unsign32 unsigned int
#define mr_dltype short
#define MR_STATIC 34
#define MR_ALWAYS_BINARY
#define MR_NOASM
#define MR_STRIPPED_DOWN
#define MR_GENERIC_MT
#define MAXBASE ((mr_small)1<<(MIRACL-1))
#define MR_BITSINCHAR 8
#define MR_NOKOBLITZ

*/

/* rem build using this batch file for PC
rem Compile MIRACL modules
cl /c /O2 /W3 mrcore.c
cl /c /O2 /W3 mrarth0.c
cl /c /O2 /W3 mrarth1.c
cl /c /O2 /W3 mrio1.c
cl /c /O2 /W3 mrbits.c
cl /c /O2 /W3 mrgf2m.c
cl /c /O2 /W3 mrec2m.c

rem
rem Create library 'miracl.lib'
del miracl.lib

lib /OUT:miracl.lib mrio1.obj
lib /OUT:miracl.lib miracl.lib mrbits.obj 
lib /OUT:miracl.lib miracl.lib mrarth0.obj mrarth1.obj mrcore.obj 
lib /OUT:miracl.lib miracl.lib mrec2m.obj mrgf2m.obj
del mr*.obj

cl /O2 etat271.c miracl.lib

On the ARM use a header like

#define MR_LITTLE_ENDIAN
#define MIRACL 32
#define mr_utype int
#define MR_IBITS 32
#define MR_LBITS 32
#define mr_unsign32 unsigned int
#define mr_dltype long long
#define MR_STATIC 9
#define MR_ALWAYS_BINARY
#define MR_NOASM
#define MR_STRIPPED_DOWN
#define MR_GENERIC_MT
#define MAXBASE ((mr_small)1<<(MIRACL-1))
#define MR_BITSINCHAR 8
#define MR_NOKOBLITZ


/* define one curve or the other.. */

#include <stdio.h>
#include <string.h>
#include "miracl.h"

#define M 271
#define T 207
#define U 175
#define V 111

#define B 0
#define TYPE 1

/* points P and Q from ROM */

/* WORDS = number of words needs to store GF(2^m) = size of bigs */

/* elements of GF(2^m) are stored in bigs */
/* elements of the quartic extension field GF(2^{4m}) are stored as an array of 4 bigs */
/* = {a,b,c,d} = d.X^3+c.X^2+b.X+a */

/* fast inlined addition code */

#if MIRACL==64

#define WORDS 5
#define NPW 16 /* nibbles per word */
#define ROMSZ 20

static const mr_small rom[]={
0x591B401498D66271,0xA16F0C4E5357F2F6,0xD76AEF912696E510,0x75C041258C778D1D,0x10B1,
0x80DC7F385B9C26BF,0x2B65C2A7BAF3B9FD,0x6A84C19620F8D8B9,0x6D0DB856E16E7097,0x7C02,
0x4EDF428FD0EE2151,0x8A4509E6D6013138,0xBB5FBE66F7C468E7,0xA2740AF91652325E,0x2C67,
0x329B869A3E833026,0xB3716EC7D5F80608,0x3EE35C892B03AE59,0x5AF93E7449ABB134,0x48FB
};

void fincr2(big a,big c)
{ 
    mr_small *aa,*cc;
    aa=a->w; cc=c->w;

    cc[0]^=aa[0];
    cc[1]^=aa[1];
    cc[2]^=aa[2];
    cc[3]^=aa[3];
    cc[4]^=aa[4];

    c->len=WORDS;
    if (cc[4]==0) mr_lzero(c);
}

void fadd2(big a,big b,big c)
{ 
    mr_small *aa,*bb,*cc;
    aa=a->w; bb=b->w; cc=c->w;

    cc[0]=aa[0]^bb[0];
    cc[1]=aa[1]^bb[1];
    cc[2]=aa[2]^bb[2];
    cc[3]=aa[3]^bb[3];
    cc[4]=aa[4]^bb[4];

    c->len=WORDS;
    if (cc[4]==0) mr_lzero(c);
}

/* fast inlined copy code - replaces copy(.) */

void fcopy2(big a,big b)
{
    mr_small *aa,*bb;
    aa=a->w; bb=b->w;

    bb[0]=aa[0];
    bb[1]=aa[1];
    bb[2]=aa[2];
    bb[3]=aa[3];
    bb[4]=aa[4];
 
    b->len=a->len;
}


#endif

#if MIRACL==32

#define WORDS 9
#define NPW 8 /* nibbles per word */
#define ROMSZ 36

static const mr_small rom[]={
0x98D66271,0x591B4014,0x5357F2F6,0xA16F0C4E,0x2696E510,0xD76AEF91,0x8C778D1D,0x75C04125,0x10B1,
0x5B9C26BF,0x80DC7F38,0xBAF3B9FD,0x2B65C2A7,0x20F8D8B9,0x6A84C196,0xE16E7097,0x6D0DB856,0x7C02,
0xD0EE2151,0x4EDF428F,0xD6013138,0x8A4509E6,0xF7C468E7,0xBB5FBE66,0x1652325E,0xA2740AF9,0x2C67,
0x3E833026,0x329B869A,0xD5F80608,0xB3716EC7,0x2B03AE59,0x3EE35C89,0x49ABB134,0x5AF93E74,0x48FB
};

void fincr2(big a,big c)
{ 
    mr_small *aa,*cc;
    aa=a->w; cc=c->w;

    cc[0]^=aa[0];
    cc[1]^=aa[1];
    cc[2]^=aa[2];
    cc[3]^=aa[3];
    cc[4]^=aa[4];
    cc[5]^=aa[5];
    cc[6]^=aa[6];
    cc[7]^=aa[7];
    cc[8]^=aa[8];
  

    c->len=WORDS;
    if (cc[8]==0) mr_lzero(c);
}

void fadd2(big a,big b,big c)
{ 
    mr_small *aa,*bb,*cc;
    aa=a->w; bb=b->w; cc=c->w;

    cc[0]=aa[0]^bb[0];
    cc[1]=aa[1]^bb[1];
    cc[2]=aa[2]^bb[2];
    cc[3]=aa[3]^bb[3];
    cc[4]=aa[4]^bb[4];
    cc[5]=aa[5]^bb[5];
    cc[6]=aa[6]^bb[6];
    cc[7]=aa[7]^bb[7];
    cc[8]=aa[8]^bb[8];

    c->len=WORDS;
    if (cc[8]==0) mr_lzero(c);
}

/* fast inlined copy code - replaces copy(.) */

void fcopy2(big a,big b)
{
    mr_small *aa,*bb;
    aa=a->w; bb=b->w;

    bb[0]=aa[0];
    bb[1]=aa[1];
    bb[2]=aa[2];
    bb[3]=aa[3];
    bb[4]=aa[4];
    bb[5]=aa[5];
    bb[6]=aa[6];
    bb[7]=aa[7];
    bb[8]=aa[8];
 
    b->len=a->len;
}

#endif

#if MIRACL==8

#define WORDS 34
#define NPW 2
#define ROMSZ 136

/* For Pentanomial x^271+x^207+x^175+x^111+1 */

#ifdef MR_AVR
__attribute__((__progmem__))
#endif 
static const mr_small rom[]={
0x71,0x62,0xD6,0x98,0x14,0x40,0x1B,0x59,0xF6,0xF2,0x57,0x53,0x4E,0xC,0x6F,0xA1,0x10,0xE5,0x96,0x26,0x91,0xEF,0x6A,0xD7,0x1D,0x8D,0x77,0x8C,0x25,0x41,0xC0,0x75,0xB1,0x10,
0xBF,0x26,0x9C,0x5B,0x38,0x7F,0xDC,0x80,0xFD,0xB9,0xF3,0xBA,0xA7,0xC2,0x65,0x2B,0xB9,0xD8,0xF8,0x20,0x96,0xC1,0x84,0x6A,0x97,0x70,0x6E,0xE1,0x56,0xB8,0xD,0x6D,0x2,0x7C,
0x51,0x21,0xEE,0xD0,0x8F,0x42,0xDF,0x4E,0x38,0x31,0x1,0xD6,0xE6,0x9,0x45,0x8A,0xE7,0x68,0xC4,0xF7,0x66,0xBE,0x5F,0xBB,0x5E,0x32,0x52,0x16,0xF9,0xA,0x74,0xA2,0x67,0x2C,
0x26,0x30,0x83,0x3E,0x9A,0x86,0x9B,0x32,0x8,0x6,0xF8,0xD5,0xC7,0x6E,0x71,0xB3,0x59,0xAE,0x3,0x2B,0x89,0x5C,0xE3,0x3E,0x34,0xB1,0xAB,0x49,0x74,0x3E,0xF9,0x5A,0xFB,0x48
};

void fincr2(big a,big c)
{ 
    mr_small *aa,*cc;
    aa=a->w; cc=c->w;

    cc[0]^=aa[0];
    cc[1]^=aa[1];
    cc[2]^=aa[2];
    cc[3]^=aa[3];
    cc[4]^=aa[4];
    cc[5]^=aa[5];
    cc[6]^=aa[6];
    cc[7]^=aa[7];
    cc[8]^=aa[8];
    cc[9]^=aa[9];
    cc[10]^=aa[10];
    cc[11]^=aa[11];
    cc[12]^=aa[12];
    cc[13]^=aa[13];
    cc[14]^=aa[14];
    cc[15]^=aa[15];
    cc[16]^=aa[16];
    cc[17]^=aa[17];
    cc[18]^=aa[18];
    cc[19]^=aa[19];
    cc[20]^=aa[20];
    cc[21]^=aa[21];
    cc[22]^=aa[22];
    cc[23]^=aa[23];
    cc[24]^=aa[24];
    cc[25]^=aa[25];
    cc[26]^=aa[26];
    cc[27]^=aa[27];
    cc[28]^=aa[28];
    cc[29]^=aa[29];
    cc[30]^=aa[30];
    cc[31]^=aa[31];
    cc[32]^=aa[32];
    cc[33]^=aa[33];

    c->len=WORDS;
    if (cc[33]==0) mr_lzero(c);
}

void fadd2(big a,big b,big c)
{ 
    mr_small *aa,*bb,*cc;
    aa=a->w; bb=b->w; cc=c->w;

    cc[0]=aa[0]^bb[0];
    cc[1]=aa[1]^bb[1];
    cc[2]=aa[2]^bb[2];
    cc[3]=aa[3]^bb[3];
    cc[4]=aa[4]^bb[4];
    cc[5]=aa[5]^bb[5];
    cc[6]=aa[6]^bb[6];
    cc[7]=aa[7]^bb[7];
    cc[8]=aa[8]^bb[8];
    cc[9]=aa[9]^bb[9];
    cc[10]=aa[10]^bb[10];
    cc[11]=aa[11]^bb[11];
    cc[12]=aa[12]^bb[12];
    cc[13]=aa[13]^bb[13];
    cc[14]=aa[14]^bb[14];
    cc[15]=aa[15]^bb[15];
    cc[16]=aa[16]^bb[16];
    cc[17]=aa[17]^bb[17];
    cc[18]=aa[18]^bb[18];
    cc[19]=aa[19]^bb[19];
    cc[20]=aa[20]^bb[20];
    cc[21]=aa[21]^bb[21];
    cc[22]=aa[22]^bb[22];
    cc[23]=aa[23]^bb[23];
    cc[24]=aa[24]^bb[24];
    cc[25]=aa[25]^bb[25];
    cc[26]=aa[26]^bb[26];
    cc[27]=aa[27]^bb[27];
    cc[28]=aa[28]^bb[28];
    cc[29]=aa[29]^bb[29];
    cc[30]=aa[30]^bb[30];
    cc[31]=aa[31]^bb[31];
    cc[32]=aa[32]^bb[32];
    cc[33]=aa[33]^bb[33];

    c->len=WORDS;
    if (cc[33]==0) mr_lzero(c);
}

/* fast inlined copy code - replaces copy(.) */

void fcopy2(big a,big b)
{
    mr_small *aa,*bb;
    aa=a->w; bb=b->w;

    bb[0]=aa[0];
    bb[1]=aa[1];
    bb[2]=aa[2];
    bb[3]=aa[3];
    bb[4]=aa[4];
    bb[5]=aa[5];
    bb[6]=aa[6];
    bb[7]=aa[7];
    bb[8]=aa[8];
    bb[9]=aa[9];
    bb[10]=aa[10];
    bb[11]=aa[11];
    bb[12]=aa[12];
    bb[13]=aa[13];
    bb[14]=aa[14];
    bb[15]=aa[15];
    bb[16]=aa[16];
    bb[17]=aa[17];
    bb[18]=aa[18];
    bb[19]=aa[19];
    bb[20]=aa[20];
    bb[21]=aa[21];
    bb[22]=aa[22];
    bb[23]=aa[23];
    bb[24]=aa[24];
    bb[25]=aa[25];
    bb[26]=aa[26];
    bb[27]=aa[27];
    bb[28]=aa[28];
    bb[29]=aa[29];
    bb[30]=aa[30];
    bb[31]=aa[31];
    bb[32]=aa[32];
    bb[33]=aa[33];

    b->len=a->len;
}

#endif

/* Use internal workspace variables w1-w13 - must be careful doing this! - see comment below */

void mul(_MIPD_ big *a,big *b,big *r)
{
    /* Special multiplier for GF(2^{4m}) values of the form (x,y,y+1,0) */

    fcopy2(a[1],mr_mip->w2);
    fcopy2(b[1],mr_mip->w3);
    fadd2(a[1],a[0],mr_mip->w8);    /* e=w+p */
    fadd2(b[1],b[0],mr_mip->w9);    /* s=t+q */

    /* only 3 modmults.. */

    modmult2(_MIPP_ mr_mip->w9,mr_mip->w8,mr_mip->w9);      /* z=(w+p)*(t+q) */
    modmult2(_MIPP_ mr_mip->w3,mr_mip->w2,mr_mip->w4);      /* tw=t*w */
    modmult2(_MIPP_ a[0],b[0],mr_mip->w8);            /* pq=p*q */
    fincr2(mr_mip->w4,mr_mip->w9);                    /* z+=tw  */     
    fincr2(mr_mip->w8,mr_mip->w9);                    /* z+=pq  */
    fincr2(mr_mip->w3,mr_mip->w2);                    /* w+=t   */
    fadd2(mr_mip->w2,mr_mip->w4,mr_mip->w3);          /* t=w+tw */
    incr2(mr_mip->w3,1,mr_mip->w3);                   /* t=w+tw+1  */

    fadd2(mr_mip->w9,a[0],mr_mip->w12);            /* x=z+p     */
    fincr2(b[0],mr_mip->w12);                      /* x=z+p+q   */

    fadd2(mr_mip->w8,mr_mip->w3,r[0]);                /* r[0]=pq+t */
    fadd2(mr_mip->w9,mr_mip->w3,r[1]);                /* r[1]=z+t  */
    fadd2(mr_mip->w12,mr_mip->w4,r[2]);               /* r[2]=z+p+q+tw */
    fcopy2(mr_mip->w2,r[3]);                       /* r[3]=w    */
}

/* squaring GF(2^{4m}) values */

void square4(_MIPD_ big *a,big *c)
{
    if (a!=c)
    {
        fcopy2(a[0],c[0]);
        fcopy2(a[1],c[1]);
        fcopy2(a[2],c[2]);
        fcopy2(a[3],c[3]);
    }

    modsquare2(_MIPP_ c[3],c[3]);
    fcopy2(c[2],mr_mip->w1);
    modsquare2(_MIPP_ mr_mip->w1,mr_mip->w1);
    fcopy2(c[1],c[2]);
    modsquare2(_MIPP_ c[2],c[2]);
    modsquare2(_MIPP_ c[0],c[0]);
    fincr2(c[3],c[2]);
    fincr2(mr_mip->w1,c[0]);
    fcopy2(mr_mip->w1,c[1]);

    return;
}

/* multiplying general GF(2^{4m}) values */
/* Uses karatsuba - 9 modmults - very time critical */
/* Use internal workspace variables w1-w13 - must be careful doing this! */
/* The thing is to ensure that none of the invoked miracl internal routines are using the same variables */
/* So first check the miracl source code.... I did... Its OK ... */

void mult4(_MIPD_ big *a,big *b,big *c)
{
    fadd2(a[1],a[3],mr_mip->w3);
    fadd2(a[0],a[2],mr_mip->w4);
    fadd2(b[1],b[3],mr_mip->w8);
    fadd2(b[0],b[2],mr_mip->w9);

    modmult2(_MIPP_ mr_mip->w8,mr_mip->w3,mr_mip->w10);
    modmult2(_MIPP_ mr_mip->w9,mr_mip->w4,mr_mip->w11);
    modmult2(_MIPP_ a[1],b[1],mr_mip->w2);
    modmult2(_MIPP_ a[2],b[2],mr_mip->w1);

    fadd2(mr_mip->w2,mr_mip->w1,mr_mip->w13);

    fadd2(a[1],a[0],c[1]);
    fadd2(b[0],b[1],mr_mip->w12);
    modmult2(_MIPP_ c[1],mr_mip->w12,c[1]);
    modmult2(_MIPP_ a[0],b[0],c[0]);
    fincr2(c[0],c[1]);
    fincr2(mr_mip->w2,c[1]);

    fcopy2(a[2],c[2]);
    fadd2(a[2],a[3],mr_mip->w12);
    fadd2(b[2],b[3],mr_mip->w2);
    modmult2(_MIPP_ mr_mip->w12,mr_mip->w2,mr_mip->w12);

    fincr2(mr_mip->w12,mr_mip->w1);
    modmult2(_MIPP_ a[3],b[3],mr_mip->w2);
    fincr2(mr_mip->w2,mr_mip->w1);

    fadd2(mr_mip->w9,mr_mip->w8,mr_mip->w12);
    fcopy2(mr_mip->w12,c[3]);
    fadd2(mr_mip->w4,mr_mip->w3,mr_mip->w12);
    modmult2(_MIPP_ c[3],mr_mip->w12,c[3]);

    fincr2(mr_mip->w2,mr_mip->w1);

    fincr2(mr_mip->w10,c[3]);
    fincr2(mr_mip->w11,c[3]);
    fincr2(mr_mip->w1,c[3]);
    fincr2(c[1],c[3]);