Miracle密码算法开源库(十一)分析 :mrflsh2.c

2021SC@SDUSC 山东大学软件学院软件工程应用与实践

 

1、mrflsh2.c结构

mrflsh2.c的总体结构如下,,主要实现了expon()、 fexp()、flog()、fpowf()几个在miracl开源库中比较重要的函数,这一次的博客就是读一下这函数的功能。

 2、源代码 

static int expon(_MIPD_ big w,int n)
{  /* generator for C.F. of e */ 
    if (n==0) return 2;
    if (n%3==2) return 2*(n/3)+2;
    else return 1;
}

expon()方法的主要作用就是根据n的输入值获得不同的输出值。如果n等于0的话返回2,n除以3的余数为2的话返回2*(n/3)+2,否则返回1.

void fexp(_MIPD_ flash x,flash y)
{ /* calculates y=exp(x) */
    int i,n,nsq,m,sqrn,op[5];
    BOOL minus,rem;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;
    if (size(x)==0)
    {
        convert(_MIPP_ 1,y);
        return;
    }
    copy(x,y);

    MR_IN(54)

    minus=FALSE;
    if (size(y)<0)
    {
        minus=TRUE;
        negify(y,y);
    }
    ftrunc(_MIPP_ y,y,mr_mip->w9);
    n=size(y);
    if (n==MR_TOOBIG)
    {
        mr_berror(_MIPP_ MR_ERR_FLASH_OVERFLOW);
        MR_OUT
        return;
    }
    if (n==0) convert(_MIPP_ 1,y);
    else
    {
        build(_MIPP_ y,expon);
        if (minus)
        { /* underflow to zero - bit of a bodge */
            rem=mr_mip->ERCON;
            mr_mip->ERCON=TRUE;
            fpower(_MIPP_ y,n,y);
            mr_mip->ERCON=rem;
            if (mr_mip->ERNUM)
            {
                mr_mip->ERNUM=0;
                zero(y);
                MR_OUT
                return;
            }
        }
        else fpower(_MIPP_ y,n,y);
    }
    if (size(mr_mip->w9)==0)
    {
        if (minus) frecip(_MIPP_ y,y);
        MR_OUT
        return;
    }
    sqrn=isqrt(mr_mip->lg2b*mr_mip->workprec,mr_mip->lg2b);
    nsq=0;
    copy(mr_mip->w9,mr_mip->w8);
    frecip(_MIPP_ mr_mip->w9,mr_mip->w9);
    ftrunc(_MIPP_ mr_mip->w9,mr_mip->w9,mr_mip->w9);
    m=logb2(_MIPP_ mr_mip->w9);
    if (m<sqrn)
    { /* scale fraction down */
        nsq=sqrn-m;
        expb2(_MIPP_ nsq,mr_mip->w9);
        fdiv(_MIPP_ mr_mip->w8,mr_mip->w9,mr_mip->w8);
    }
    zero(mr_mip->w10);
    op[0]=0x4B;  /* set up for x/(C+y) */
    op[1]=1;
    op[2]=0;
    for (m=sqrn;m>0;m--)
    { /* Unwind C.F. expansion for exp(x)-1 */
        if (m%2==0) op[4]=2,op[3]=1;
        else        op[4]=m,op[3]=(-1);
        flop(_MIPP_ mr_mip->w8,mr_mip->w10,op,mr_mip->w10);
    }
    op[0]=0x2C;  /* set up for (x+2).y */
    op[1]=op[3]=1;
    op[2]=2;
    op[4]=0;
    for (i=0;i<nsq;i++)
    { /* now square it back up again */
        flop(_MIPP_ mr_mip->w10,mr_mip->w10,op,mr_mip->w10);
    }
    op[2]=1;
    flop(_MIPP_ mr_mip->w10,y,op,y);
    if (minus) frecip(_MIPP_ y,y);
    MR_OUT
}

fexp()方法的主要作用就是获得以输入数据flash数据类型x为幂,以e为底数的指数并且赋值给输入数据y。首先调用size方法将x转化为int数据类型,观察x是否为0,是的话调用convert方法把y赋值为1的flash数据类型,否则的话调用copy方法那x赋值给y。然后调用size方法看int数据类型的y是否小于0,是的话调用方法获得y的相反数,调用ftrunc方法把y切分为flsah类型的mr_mip->w9和big数据类型的y,调用size方法将y转化为int数据类型赋值给n。如果没有发生一个下溢到零位的错误的话,就等于fpower方法直接获得y的n次方赋值给y。之后该函数内部使用了多种其他函数来计算e的x次方,该方法的时间复杂度为O(n2.5),可以说再相对较少的运行时间内就可以得出答案。

void flog(_MIPD_ flash x,flash y)
{ /* calculate y=log(x) to base e */
    BOOL hack;
    int op[5];
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    copy(x,y);
    if (mr_mip->ERNUM) return;
    if (size(y)==1)
    {
        zero(y);
        return;
    }

    MR_IN(55)

    if (size(y)<=0)
    {
        mr_berror(_MIPP_ MR_ERR_NEG_LOG);
        MR_OUT
        return;
    }
    hack=FALSE;
    if (mr_lent(y)<=2)
    { /* for 'simple' values of y */
        hack=TRUE;
        build(_MIPP_ mr_mip->w11,expon);
        fdiv(_MIPP_ y,mr_mip->w11,y);
    }
    op[0]=0x68;
    op[1]=op[3]=1;
    op[2]=(-1);
    op[4]=0;
    mr_mip->workprec=mr_mip->stprec;
    dconv(_MIPP_ log(fdsize(_MIPP_ y)),mr_mip->w11);
    while (mr_mip->workprec!=mr_mip->nib)
    { /* Newtons iteration w11=w11+(y-exp(w11))/exp(w11) */
        if (mr_mip->workprec<mr_mip->nib) mr_mip->workprec*=2;
        if (mr_mip->workprec>=mr_mip->nib) mr_mip->workprec=mr_mip->nib;
        else if (mr_mip->workprec*2>mr_mip->nib) mr_mip->workprec=(mr_mip->nib+1)/2;
        fexp(_MIPP_ mr_mip->w11,mr_mip->w12);
        flop(_MIPP_ y,mr_mip->w12,op,mr_mip->w12);
        fadd(_MIPP_ mr_mip->w12,mr_mip->w11,mr_mip->w11);
    }
    copy(mr_mip->w11,y);
    if (hack) fincr(_MIPP_ y,1,1,y);
    MR_OUT
}

flog()方法的主要作用就是获得以输入数据flash数据类型x为真数,以e为底数的对数并且赋值给输入数据y。首先调用mr_lent方法获得y的len属性,如果小于2的话,把hack赋值为true,调用build方法创建mr_mip->w11,调用fdiv方法获得y/mr_mip->w11并且赋值给y。然后给数组op赋予不同的初值。再把mr_mip->stprec赋值给mr_mip->workprec,调用fdsize方法把ycongflash形式转化为double形式,再调用log方法获得以y为真数,以e为底数的对数,然后调用dconv方法ba上述结果转化为flash形式再赋值给mr_mip->w11。接下来循环使用牛顿法计算w11+(y-exp(w11))/exp(w11)的近似值并且赋值给w11,最后调用copy方法把w11赋值给y,如果hack调用true的话,调用fincr方法使得y+1/1并且赋值给y。

void fpowf(_MIPD_ flash x,flash y,flash z)
{ /* raise flash number to flash power *
   *     z=x^y  -> z=exp(y.log(x))     */
    int n;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;

    MR_IN(56)

    n=size(y);
    if (mr_abs(n)<MR_TOOBIG)
    { /* y is small int */
        fpower(_MIPP_ x,n,z);
        MR_OUT
        return;
    }
    frecip(_MIPP_ y,mr_mip->w13);
    n=size(mr_mip->w13);
    if (mr_abs(n)<MR_TOOBIG)
    { /* 1/y is small int */
        froot(_MIPP_ x,n,z);
        MR_OUT
        return;
    }
    copy(x,z);
    flog(_MIPP_ z,z);
    fdiv(_MIPP_ z,mr_mip->w13,z);
    fexp(_MIPP_ z,z);
    MR_OUT
}

fpowf()方法的主要作用就是获得以输入数据x为底数,以y为幂的指数,并且把结果赋值给z。首先调用size方法把y转化为int类型赋值给n,然后调用mr_abs方法获得n的绝对值,如果n足够小的话,调用fpower方法直接获得x的n次方赋值给z并且退出。然后调用 frecip方法获得1/y并且赋值给mr_mip->w13,再调用size方法把mr_mip->w13转化为int类型赋值给n,如果n足够小的话,调用fpower方法直接获得x的n次方赋值给z并且退出。y或者1/y都不够小的话调用copy方法把x赋值给z,调用flog方法获得z的自然对数并且赋值给z,调用fdiv方法获得 z/mr_mip->w13并且赋值给z,再调用 fexp方法获得e的z次方并且赋值给z。


版权声明:本文为hhf1732641824原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。