2021SC@SDUSC 山东大学软件学院软件工程应用与实践
1、mrbits.c结构mrbits.c的总体结构如下，，主要实现了logb2()、expb2()、bigbits()、sftbit()几个在miracl开源库中比较重要的函数，这一次的博客就是读一下这函数的功能。
2、源代码int logb2(_MIPD_ big x)
{
int xl,lg2;
mr_small top;
#ifdef MR_OS_THREADS
miracl *mr_mip=get_mip();
#endif
if (mr_mip->ERNUM || size(x)==0) return 0;
MR_IN(49)
#ifndef MR_ALWAYS_BINARY
if (mr_mip->base==mr_mip->base2)
{
#endif
xl=(int)(x->len&MR_OBITS);
lg2=mr_mip->lg2b*(xl-1);
top=x->w[xl-1];
while (top>=1)
{
lg2++;
top/=2;
}
#ifndef MR_ALWAYS_BINARY
}
else
{
copy(x,mr_mip->w0);
insign(PLUS,mr_mip->w0);
lg2=0;
while (mr_mip->w0->len>1)
{
#ifdef MR_FP_ROUNDING
mr_sdiv(_MIPP_ mr_mip->w0,mr_mip->base2,mr_invert(mr_mip->base2),mr_mip->w0);
#else
mr_sdiv(_MIPP_ mr_mip->w0,mr_mip->base2,mr_mip->w0);
#endif
lg2+=mr_mip->lg2b;
}
while (mr_mip->w0->w[0]>=1)
{
lg2++;
mr_mip->w0->w[0]/=2;
}
}
#endif
MR_OUT
return lg2;
}
logb2()方法的主要作用就是求一个大数字以2为底的对数或其近似解。当mr_mip->base等于mr_mip->base2也就是说这个大数字可以被2整除的时候，该函数会先获取这个大数字的长度xl，lg2就等于mr_mip->lg2b*(xl-1)，top为x->w[xl-1]，接着再循环中lg2每自加1，top就除以2，最后返回lg2。在另一种情况下只能近似求解，先调用copy方法把x复制给mr_mip->w0，再把mr_mip->w0转化为绝对值，再把lg2赋值为0，之后在w0的len属性大于1的限制条件下循环，每调用一次mr_sdiv方法让mr_mip->w0->len除以mr_mip->base2，lg2都加一次mr_mip->lg2b。然后在w0的w[0]属性大于等于1的限制条件下循环，lg2每自加2，w[0]都除以2。最后返回lg2。
void sftbit(_MIPD_ big x,int n,big z)
{
int m;
mr_small sm;
#ifdef MR_OS_THREADS
miracl *mr_mip=get_mip();
#endif
if (mr_mip->ERNUM) return;
copy(x,z);
if (n==0) return;
MR_IN(47)
m=mr_abs(n);
sm=mr_shiftbits((mr_small)1,m%mr_mip->lg2b);
if (n>0)
{
#ifndef MR_ALWAYS_BINARY
if (mr_mip->base==mr_mip->base2)
{
#endif
mr_shift(_MIPP_ z,n/mr_mip->lg2b,z);
mr_pmul(_MIPP_ z,sm,z);
#ifndef MR_ALWAYS_BINARY
}
else
{
expb2(_MIPP_ m,mr_mip->w1);
multiply(_MIPP_ z,mr_mip->w1,z);
}
#endif
}
else
{
#ifndef MR_ALWAYS_BINARY
if (mr_mip->base==mr_mip->base2)
{
#endif
mr_shift(_MIPP_ z,n/mr_mip->lg2b,z);
#ifdef MR_FP_ROUNDING
mr_sdiv(_MIPP_ z,sm,mr_invert(sm),z);
#else
mr_sdiv(_MIPP_ z,sm,z);
#endif
#ifndef MR_ALWAYS_BINARY
}
else
{
expb2(_MIPP_ m,mr_mip->w1);
divide(_MIPP_ z,mr_mip->w1,z);
}
#endif
}
MR_OUT
}
sftbit()方法的主要作用就是把一个大数字x移动n位（n有正负，代表左右）获得大数字z。首先调用copy方法把x复制给在，再获得整数n的绝对值m，然后获得sm：把1左移m%mr_mip->lg2b的位数（也就是2的m%mr_mip->lg2b次方）。当n大于0且x可被2整除的情况下，先调用mr_shift方法把z乘以2的n/mr_mip->lg2b次方，再调用mr_pmul方法让z乘以sm。如果x不能被2整除，先调用expb2方法获得2的m次方赋值给mr_mip->w1，再调用 multiply方法将z乘以 mr_mip->w1。当n小于0且x可被2整除的情况下，先调用mr_shift方法把z乘以2的n/mr_mip->lg2b次方，再调用mr_sdivl方法让z除以sm。如果x不能被2整除，先调用expb2方法获得2的m次方赋值给mr_mip->w1，再调用divide方法将z除以 mr_mip->w1。
void expb2(_MIPD_ int n,big x)
{
int r,p;
#ifndef MR_ALWAYS_BINARY
int i;
#endif
#ifdef MR_OS_THREADS
miracl *mr_mip=get_mip();
#endif
if (mr_mip->ERNUM) return;
convert(_MIPP_ 1,x);
if (n==0) return;
MR_IN(149)
if (n<0)
{
mr_berror(_MIPP_ MR_ERR_NEG_POWER);
MR_OUT
return;
}
r=n/mr_mip->lg2b;
p=n%mr_mip->lg2b;
#ifndef MR_ALWAYS_BINARY
if (mr_mip->base==mr_mip->base2)
{
#endif
mr_shift(_MIPP_ x,r,x);
x->w[x->len-1]=mr_shiftbits(x->w[x->len-1],p);
#ifndef MR_ALWAYS_BINARY
}
else
{
for (i=1;i<=r;i++)
mr_pmul(_MIPP_ x,mr_mip->base2,x);
mr_pmul(_MIPP_ x,mr_shiftbits((mr_small)1,p),x);
}
#endif
MR_OUT
}
expb2()方法的主要作用就是获得2的n次方并且转化为大数字赋值给x。首先调用convert方法把x转换为1的大数字形式，再看n是否小于0。是的话异常报错退出。否则的话获得n除以lg2b的商r和余数p。如果mr_mip->base等于mr_mip->base2的话，先将x乘以2的r次方，再把w[x->len-1]左移p位。不等于的话在i小于等于r的限制条件下循环调用mr_pmul把x乘以mr_mip->base2，最后把x乘以2的p次方。
void bigbits(_MIPD_ int n,big x)
{
mr_small r;
mr_lentype wlen;
#ifdef MR_FP
mr_small dres;
#endif
#ifdef MR_OS_THREADS
miracl *mr_mip=get_mip();
#endif
zero(x);
if (mr_mip->ERNUM || n<=0) return;
MR_IN(150)
expb2(_MIPP_ n,mr_mip->w1);
wlen=mr_mip->w1->len;
do
{
r=brand(_MIPPO_ );
if (mr_mip->base==0) x->w[x->len++]=r;
else x->w[x->len++]=MR_REMAIN(r,mr_mip->base);
} while (x->lenbase==mr_mip->base2)
{
#endif
x->w[wlen-1]=MR_REMAIN(x->w[wlen-1],mr_mip->w1->w[wlen-1]);
mr_lzero(x);
#ifndef MR_ALWAYS_BINARY
}
else
{
divide(_MIPP_ x,mr_mip->w1,mr_mip->w1);
}
#endif
MR_OUT
}
bigbits()方法的主要作用就是生成一个小于2^n 的随机大数字。首先等于zero将x清零，再调用expb2方法获得2的n次方wl，然后获取w1的len属性wlen。之后在x的len属性小于wlen的限制条件下循环调用brand方法获取一个随机整数人，使得w[x->len++]等于r或者r除以mr_mip->base的余数。最后看x是否可以被2整除，是的话x->w[wlen-1]就等于x->w[wlen-1]除以mr_mip->w1->w[wlen-1]的余数，在调用mr_lzero方法清除x的前置零；不是的话调用divide方法将x除以,mr_mip->w1。最后的x就是生成的随机数。
