mrcore.c

miracl大数库 miracl大数库 miracl大数库

    }
    w->len=(bl|s);
    MR_OUT
}

int size(big x)
{  /*  get size of big number;  convert to *
    *  integer - if possible               */
    int n,m;
    mr_lentype s;
    if (x==NULL) return 0;
    s=(x->len&MR_MSBIT);
    m=(int)(x->len&MR_OBITS);
    if (m==0) return 0;
    if (m==1 && x->w[0]<(mr_small)MR_TOOBIG) n=(int)x->w[0];
    else                                     n=MR_TOOBIG;
    if (s==MR_MSBIT) return (-n);
    return n;
}

int mr_compare(big x,big y)
{  /* compare x and y: =1 if x>y  =-1 if x<y *
    *  =0 if x=y                             */
    int m,n,sig;
    mr_lentype sx,sy;
    if (x==y) return 0;
    sx=(x->len&MR_MSBIT);
    sy=(y->len&MR_MSBIT);
    if (sx==0) sig=PLUS;
    else       sig=MINUS;
    if (sx!=sy) return sig;
    m=(int)(x->len&MR_OBITS);
    n=(int)(y->len&MR_OBITS);
    if (m>n) return sig;
    if (m<n) return -sig;
    while (m>0)
    { /* check digit by digit */
        m--;  
        if (x->w[m]>y->w[m]) return sig;
        if (x->w[m]<y->w[m]) return -sig;
    }
    return 0;
}

#ifdef MR_FLASH

void fpack(_MIPD_ big n,big d,flash x)
{ /* create floating-slash number x=n/d from *
   * big integer numerator and denominator   */
    mr_lentype s;
    int i,ld,ln;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;

    MR_IN(31)

    ld=(int)(d->len&MR_OBITS);
    if (ld==0) mr_berror(_MIPP_ MR_ERR_FLASH_OVERFLOW);
    if (ld==1 && d->w[0]==1) ld=0;
    if (x==d) mr_berror(_MIPP_ MR_ERR_BAD_PARAMETERS);
    if (mr_notint(n) || mr_notint(d)) mr_berror(_MIPP_ MR_ERR_INT_OP);
    s=(n->len&MR_MSBIT);
    ln=(int)(n->len&MR_OBITS);
    if (ln==1 && n->w[0]==1) ln=0;
    if ((ld+ln>mr_mip->nib) && (mr_mip->check || ld+ln>2*mr_mip->nib)) 
        mr_berror(_MIPP_ MR_ERR_FLASH_OVERFLOW);
    if (mr_mip->ERNUM)
    {
       MR_OUT
       return;
    }
    copy(n,x);
    if (n->len==0)
    {
        MR_OUT
        return;
    }
    s^=(d->len&MR_MSBIT);
    if (ld==0)
    {
        if (x->len!=0) x->len|=s;
        MR_OUT
        return;
    }
    for (i=0;i<ld;i++)
        x->w[ln+i]=d->w[i];
    x->len=(s|(ln+((mr_lentype)ld<<MR_BTS)));
    MR_OUT
}

void numer(_MIPD_ flash x,big y)
{ /* extract numerator of x */
    int i,ln,ld;
    mr_lentype s,ly;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;
    if (mr_notint(x))
    {
        s=(x->len&MR_MSBIT);
        ly=(x->len&MR_OBITS);
        ln=(int)(ly&MR_MSK);
        if (ln==0)
        {
            if(s==MR_MSBIT) convert(_MIPP_ (-1),y);
            else            convert(_MIPP_ 1,y);
            return;
        }
        ld=(int)((ly>>MR_BTS)&MR_MSK);
        if (x!=y)
        {
            for (i=0;i<ln;i++) y->w[i]=x->w[i];
            for (i=ln;i<mr_lent(y);i++) y->w[i]=0;
        }
        else for (i=0;i<ld;i++) y->w[ln+i]=0;
        y->len=(ln|s);
    }
    else copy(x,y);
}

void denom(_MIPD_ flash x,big y)
{ /* extract denominator of x */
    int i,ln,ld;
    mr_lentype ly;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;
    if (!mr_notint(x))
    {
        convert(_MIPP_ 1,y);
        return;
    }
    ly=(x->len&MR_OBITS);
    ln=(int)(ly&MR_MSK);
    ld=(int)((ly>>MR_BTS)&MR_MSK);
    for (i=0;i<ld;i++)
        y->w[i]=x->w[ln+i];
    if (x==y) for (i=0;i<ln;i++) y->w[ld+i]=0;
    else for (i=ld;i<mr_lent(y);i++) y->w[i]=0;
    y->len=ld;
}

#endif

unsigned int igcd(unsigned int x,unsigned int y)
{ /* integer GCD, returns GCD of x and y */
    unsigned int r;
    if (y==0) return x;
    while ((r=x%y)!=0)
        x=y,y=r;
    return y;
}

unsigned long lgcd(unsigned long x,unsigned long y)
{ /* long GCD, returns GCD of x and y */
    unsigned long r;
    if (y==0) return x;
    while ((r=x%y)!=0)
        x=y,y=r;
    return y;
}

unsigned int isqrt(unsigned int num,unsigned int guess)
{ /* square root of an integer */
    unsigned int sqr;
    unsigned int oldguess=guess;
    if (num==0) return 0;
    if (num<4) return 1;
  
    for (;;)
    { /* Newtons iteration */
     /*   sqr=guess+(((num/guess)-guess)/2); */
        sqr=((num/guess)+guess)/2;
        if (sqr==guess || sqr==oldguess) 
        {
            if (sqr*sqr>num) sqr--;
            return sqr;
        }
        oldguess=guess;
        guess=sqr;
    }
}

unsigned long lsqrt(unsigned long num,unsigned long guess)
{ /* square root of a long */
    unsigned long sqr;
    unsigned long oldguess=guess;
    if (num==0) return 0;
    if (num<4) return 1;
  
    for (;;)
    { /* Newtons iteration */
     /*   sqr=guess+(((num/guess)-guess)/2); */
        sqr=((num/guess)+guess)/2;
        if (sqr==guess || sqr==oldguess) 
        {
            if (sqr*sqr>num) sqr--;
            return sqr;
        }
        oldguess=guess;
        guess=sqr;
    }
}

mr_small sgcd(mr_small x,mr_small y)
{ /* integer GCD, returns GCD of x and y */
    mr_small r;
#ifdef MR_FP
    mr_small dres;
#endif
    if (y==(mr_small)0) return x;
    while ((r=MR_REMAIN(x,y))!=(mr_small)0)
        x=y,y=r;
    return y;
}

/* routines to support sliding-windows exponentiation *
 * in various contexts */

int mr_testbit(_MIPD_ big x,int n)
{ /* return value of n-th bit of big */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
#ifdef MR_FP
    mr_small m,a,dres;
    m=mr_shiftbits((mr_small)1,n%mr_mip->lg2b);

    a=x->w[n/mr_mip->lg2b];

    a=MR_DIV(a,m); 

    if ((MR_DIV(a,2.0)*2.0) != a) return 1;
#else
    if ((x->w[n/mr_mip->lg2b] & ((mr_small)1<<(n%mr_mip->lg2b))) >0) return 1;
#endif
    return 0;
}

void mr_addbit(_MIPD_ big x,int n)
{ /* add 2^n to positive x - where you know that bit is zero. Use with care! */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    mr_lentype m=n/mr_mip->lg2b;
    x->w[m]+=mr_shiftbits((mr_small)1,n%mr_mip->lg2b);
    if (x->len<m+1) x->len=m+1;
}

int recode(_MIPD_ big e,int t,int w,int i)
{ /* recode exponent for Comb method */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    int j,r;
    r=0;
    for (j=w-1;j>=0;j--)
    {
        r<<=1;
        r|=mr_testbit(_MIPP_ e,i+j*t);
    }
    return r;
}

int mr_window(_MIPD_ big x,int i,int *nbs,int * nzs,int window_size)
{ /* returns sliding window value, max. of 5 bits,         *
   * (Note from version 5.23 this can be changed by        *
   * setting parameter window_size. This can be            *
   * a useful space-saver) starting at i-th bit of big x.  *
   * nbs is number of bits processed, nzs is the number of *
   * additional trailing zeros detected. Returns valid bit *
   * pattern 1x..x1 with no two adjacent 0's. So 10101     *
   * will return 21 with nbs=5, nzs=0. 11001 will return 3,*
   * with nbs=2, nzs=2, having stopped after the first 11..*/
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    int j,r,w;
    w=window_size;

/* check for leading 0 bit */

    *nbs=1;
    *nzs=0;
    if (!mr_testbit(_MIPP_ x,i)) return 0;

/* adjust window size if not enough bits left */
   
    if (i-w+1<0) w=i+1;

    r=1;
    for (j=i-1;j>i-w;j--)
    { /* accumulate bits. Abort if two 0's in a row */
        (*nbs)++;
        r*=2;
        if (mr_testbit(_MIPP_ x,j)) r+=1;
        if (r%4==0)
        { /* oops - too many zeros - shorten window */
            r/=4;
            *nbs-=2;
            *nzs=2;
            break;
        }
    }
    if (r%2==0)
    { /* remove trailing 0 */
        r/=2;
        *nzs=1;
        (*nbs)--;
    }
    return r;
}

int mr_window2(_MIPD_ big x,big y,int i,int *nbs,int *nzs)
{ /* two bit window for double exponentiation */
    int r,w;
    BOOL a,b,c,d;
    w=2;
    *nbs=1;
    *nzs=0;

/* check for two leading 0's */
    a=mr_testbit(_MIPP_ x,i); b=mr_testbit(_MIPP_ y,i);

    if (!a && !b) return 0;
    if (i<1) w=1;

    if (a)
    {
        if (b) r=3;
        else   r=2;
    }
    else r=1;
    if (w==1) return r;

    c=mr_testbit(_MIPP_ x,i-1); d=mr_testbit(_MIPP_ y,i-1);

    if (!c && !d) 
    {
        *nzs=1;
        return r;
    }

    *nbs=2;
    r*=4;
    if (c)
    {
        if (d) r+=3;
        else   r+=2;
    }
    else r+=1;
    return r;
}

int mr_naf_window(_MIPD_ big x,big x3,int i,int *nbs,int *nzs,int store)
{ /* returns sliding window value, using fractional windows   *
   * where "store" precomputed values are precalulated and    *
   * stored. Scanning starts at the i-th bit of  x. nbs is    *
   * the number of bits processed. nzs is number of           *
   * additional trailing zeros detected. x and x3 (which is   *
   * 3*x) are combined to produce the NAF (non-adjacent       *
   * form). So if x=11011(27) and x3 is 1010001, the LSB is   *
   * ignored and the value 100T0T (32-4-1=27) processed,      *
   * where T is -1. Note x.P = (3x-x)/2.P. This value will    *
   * return +7, with nbs=4 and nzs=1, having stopped after    *
   * the first 4 bits. If it goes too far, it must backtrack  *
   * Note in an NAF non-zero elements are never side by side, *
   * so 10T10T won't happen. NOTE: return value n zero or     * 
   * odd, -21 <= n <= +21     */

    int nb,j,r,biggest;

 /* get first bit */
    nb=mr_testbit(_MIPP_ x3,i)-mr_testbit(_MIPP_ x,i);

    *nbs=1;
    *nzs=0;
    if (nb==0) return 0;
    if (i==0) return nb;

    biggest=2*store-1;

    if (nb>0) r=1;
    else      r=(-1);

    for (j=i-1;j>0;j--)
    {
        (*nbs)++;
        r*=2;
        nb=mr_testbit(_MIPP_ x3,j)-mr_testbit(_MIPP_ x,j);
        if (nb>0) r+=1;
        if (nb<0) r-=1;
        if (abs(r)>biggest) break;
    }

    if (r%2!=0 && j!=0)
    { /* backtrack */
        if (nb>0) r=(r-1)/2;
        if (nb<0) r=(r+1)/2;
        (*nbs)--;
    }
    
    while (r%2==0)
    { /* remove trailing zeros */
        r/=2;
        (*nzs)++;
        (*nbs)--;
    }     
    return r;
}

/* Some general purpose elliptic curve stuff */

BOOL point_at_infinity(epoint *p)
{
    if (p==NULL) return FALSE;
    if (p->marker==MR_EPOINT_INFINITY) return TRUE;
    return FALSE;
}

#ifndef MR_STATIC

epoint* epoint_init(_MIPDO_ )
{ /* initialise epoint to general point at infinity. */
    epoint *p;
    char *ptr;

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return NULL;

    MR_IN(96)

/* Create space for whole structure in one heap access */ 

    p=(epoint *)mr_alloc(_MIPP_ mr_esize(mr_mip->nib-1),1);

    ptr=(char *)p+sizeof(epoint);
    p->X=mirvar_mem(_MIPP_ ptr,0);
    p->Y=mirvar_mem(_MIPP_ ptr,1);
#ifndef MR_AFFINE_ONLY
    p->Z=mirvar_mem(_MIPP_ ptr,2);
#endif
    p->marker=MR_EPOINT_INFINITY;

    MR_OUT

    return p;
}

#endif

epoint* epoint_init_mem_variable(_MIPD_ char *mem,int index,int sz)
{
    epoint *p;
    char *ptr;
    int offset,r;

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    offset=0;
    r=(unsigned long)mem%MR_SL;
    if (r>0) offset=MR_SL-r;

#ifndef MR_AFFINE_ONLY
    if (mr_mip->coord==MR_AFFINE)
        p=(epoint *)&mem[offset+index*mr_esize_a(sz)];
    else
#endif
    p=(epoint *)&mem[offset+index*mr_esize(sz)];

    ptr=(char *)p+sizeof(epoint);
    p->X=mirvar_mem_variable(ptr,0,sz);
    p->Y=mirvar_mem_variable(ptr,1,sz);
#ifndef MR_AFFINE_ONLY
    if (mr_mip->coord!=MR_AFFINE) p->Z=mirvar_mem_variable(ptr,2,sz);
#endif
    p->marker=MR_EPOINT_INFINITY;
    return p;
}

epoint* epoint_init_mem(_MIPD_ char *mem,int index)
{ 
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return NULL;

    return epoint_init_mem_variable(_MIPP_ mem,index,mr_mip->nib-1);
}

#ifndef MR_STATIC

/* allocate space for a number of epoints from the heap */

void *ecp_memalloc(_MIPD_ int num)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

#ifndef MR_AFFINE_ONLY
    if (mr_mip->coord==MR_AFFINE)
        return mr_alloc(_MIPP_  mr_ecp_reserve_a(num,mr_mip->nib-1),1);
    else
#endif
        return mr_alloc(_MIPP_  mr_ecp_reserve(num,mr_mip->nib-1),1);
}

#endif

void ecp_memkill(_MIPD_ char *mem,int num)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    if (mem==NULL) return;

#ifndef MR_AFFINE_ONLY
    if (mr_mip->coord==MR_AFFINE)
        memset(mem,0,mr_ecp_reserve_a(num,mr_mip->nib-1));
    else
#endif
        memset(mem,0,mr_ecp_reserve(num,mr_mip->nib-1));


#ifndef MR_STATIC
    mr_free(mem);
#endif
}

#ifndef MR_STATIC

void epoint_free(epoint *p)
{ /* clean up point */
 
    if (p==NULL) return;
    zero(p->X);
    zero(p->Y);
#ifndef MR_AFFINE_ONLY
    if (p->marker==MR_EPOINT_GENERAL) zero(p->Z);
#endif
    mr_free(p);
}        

#endif