bigil.c

128位大整数运算源代码 源代码包含128位大整数的加减乘除、取模、乘幂、2进制和10进制转换等运算

#include "bigil.h"

void Mov(unsigned short *A, unsigned short *B);
short Add(unsigned short *A, unsigned short *B);
short Sub(unsigned short *A, unsigned short *B);
short Subs(unsigned short *A, unsigned short *B); //A>B?
void Mul(BigLong C,unsigned short *A, unsigned short *B);
void Muls(unsigned short *C,unsigned short *A, unsigned short B);
void Div(unsigned short *A, BigLong C, unsigned short *B);
void Mod(unsigned short *F, BigLong C, unsigned short *B);

//大数比较
short Cmp(unsigned short *A, unsigned short *B)
{
    short i;
	 for(i=7;i>=0;i--)  //if have A and B length can easy.
    {
        if(A[i]>B[i])return 1;
        else if(A[i]<B[i])return -1;
    }
    return 0;
}
//大数赋值
void Mov(unsigned short *A, unsigned short *B)
{
    short i;
	 for(i=0;i<8;i++) A[i]=B[i];
}
//大数相加:可能越界:可以加一个参数add记住最终是否进位。
short Add(unsigned short *A, unsigned short *B)
{
	 short i,add=0;
	 for(i=0;i<8;i++){
		 A[i]+=B[i];
		 if(A[i]<B[i]){
			 A[i]+=add;
			 add=1;
		 }else{
			 A[i]+=add;
			 if(A[i]<add) add=1;
			 else add=0;
		 }
	 }
    return add;
}
//大数相减:可能越界:可以加一个参数add记住最终是否借位。
short Sub(unsigned short *A, unsigned short *B) //A>B?
{
	 short i,sub=0;
	 for(i=0;i<8;i++){
	 //printf("=%u,%u=",A[i],B[i]);
		if(A[i]<B[i]){
		   A[i]-=B[i]+sub;
		   sub=1;
		}else{
			A[i]-=B[i];
		   if(!A[i]&&sub){
			  A[i]=0xffff;
			  sub=1;
		   }else{
			  A[i]-=sub;
			  sub=0;
		   }
		}
	}
	/*short i,add=0,add2;
	 for(i=0;i<8;i++){
	add2=(A[i]<B[i]+add?1:0);
	 A[i]-=B[i]+add;
	add=add2;
	}*/
	 return sub;
}
//多一个长度的大数相减
short Subs(unsigned short *A, unsigned short *B) //A>B?
{
	 short i,sub=0;
	 for(i=0;i<9;i++){
		if(A[i]<B[i]){
		   A[i]-=B[i];
		   A[i]-=sub;
		   sub=1;
		}else{
		   A[i]-=B[i];
		   if(!A[i]&&sub){
			  A[i]=0xffff;
			  sub=1;
		   }else{
			  A[i]-=sub;
			  sub=0;
		   }
		}
	}
	return sub;
}
//大数相乘
void Mul(BigLong C,unsigned short *A, unsigned short *B)
{
	short i,j,k;
   unsigned short add;
   unsigned long m;
	memset((void *)C,0,32);
	for(i=0;i<8;i++){
		for(j=0;j<8;j++){
			m=(unsigned long)A[i]*(unsigned long)B[j];
			C[i+j]+=m&0xffff;
			if(C[i+j]<(m&0xffff)) add=(m>>16)+1;
			else add=m>>16;
			k=i+j+1;
			for(;C[k]+=add,C[k]<add;add=1,k++);
		}
   }
}
//多一个长度的大数相乘
void Muls(unsigned short *C,unsigned short *A, unsigned short B)
{
   short i,k;
   unsigned short add;
   unsigned long m;
	for(i=0;i<9;i++) C[i]=0;
	for(i=0;i<8;i++){
		m=(unsigned long)A[i]*(unsigned long)B;
		C[i]+=m&0xffff;
		if(C[i]<(m&0xffff)) add=(m>>16)+1;
		else add=m>>16;
		k=i+1;
		for(;C[k]+=add,C[k]<add;add=1,k++);
	}
}
//大数相除
void Div(unsigned short *A, BigLong C, unsigned short *B)
{
   short i,h;
   unsigned long m,n;
   unsigned short *D,E[9];
	for(i=0;i<8;i++) A[i]=0;
	D=(unsigned short *)&C[8];
	for(i=7;i>=0;i--){
		for(;h=Cmp(D,B),h>=0;Sub(D,B),A[i+1]++); //limit?A[8]?
		D=(unsigned short *)&C[i]; //D--;
		do{
			m=((unsigned long)C[i+8]<<16)+(unsigned long)C[i+7];
			n=m/((unsigned long)B[7]+1);
			if(n) A[i]+=n; //no carry.
			else{
			   if(m>B[7]) {D[7]=1-Sub(D,B);  A[i]++;}
			   break;
			}
			memset((void *)E,0,18);
			Muls(E,B,(unsigned short)n);
			Subs(D,E);
		}while(1);
	}
	for(;h=Cmp(D,B),h>=0;Sub(D,B),A[0]++); //exit(0);//h==0.
	//for(h=Cmp(D,B);h>=0;Sub(D,B),A[i+1]++);
}
//大数求模
void Mod(unsigned short *F, BigLong C, unsigned short *B)
{
   short i,h;
	unsigned long m,n;
	unsigned short A,*D,E[9];
   //init A=0;
	D = (unsigned short *)&C[8];
	for(i=7;i>=0;i--){
		for(;h=Cmp(D,B),h>=0;Sub(D,B)); //limit?A[8]?
		A=0;
		D=(unsigned short *)&C[i]; //D--;
		do{
			m=((unsigned long)C[i+8]<<16)+(unsigned long)C[i+7];
			n=m/((unsigned long)B[7]+1);  //
			if(n) {A+=n; }//no carry.
			else{
			   if(m>B[7]) {D[7]=1-Sub(D,B);  A++;}
			   break;
			}
			memset((void *)E,0,18);
			Muls(E,B,(unsigned short)n);
			Subs(D,E);
		}while(1);
	}
	for(;h=Cmp(D,B),h>=0;Sub(D,B),A++);
	//for(h=Cmp(D,B);h>=0;Sub(D,B),A[i+1]++);
		memset((void *)F,0,16);
		for(i=0;i<8;i++) F[i]=D[i];
}
//求乘幂的模
void RsaMod(unsigned short *D,unsigned short *A, unsigned short *B, unsigned short *N)
{
	short i,j,k=0;
	char v[33];
	BigLong E;
	memset(v,0,33);
  //for(i=7;i>=0;i--)printf("|%u",A[i]); printf("|=A[i]\n");
  //Put(v,A);   fprintf(ff,"|=A[i]=%s==\n",v);  printf("|=A[i]=%s==\n",v);
  //Put(v,B);   fprintf(ff,"|=B[i]=%s==\n",v);  printf("|=B[i]=%s==\n",v);
  //Put(v,N);   fprintf(ff,"|=N[i]=%s==\n",v);  printf("|=N[i]=%s==\n",v);
	for(i=1;i<8;i++) D[i]=0;  D[0]=1;
	for(i=0;i<16;i++) E[i]=0;
	for(i=7;i>=0;i--){
		for(j=15;j>=0;j--){
		   if(!k) k=(B[i]>>j)&1;
		   if(k){
				Mul(E,D,D);
				Mod(D,E,N);
				if((B[i]>>j)&1){
					Mul(E,A,D);
					Mod(D,E,N);
				}
		   }
	   }
	}
  //Put(v,D);   fprintf(ff,"|=D[i]=%s==\n",v);   printf("|=D[i]=%s==\n",v);
}
//从字符串按16进制格式输入到128位大数
void Get(unsigned short *A, char *str)
{
	 short i,j,len;
	 len=strlen(str);
	 for(i=0;i<8;i++) A[i]=0;
	 for(i=0;i<len/4;i++){
		j=len-i*4;
		A[i]=(Valuei((str[j-4]))<<12)+(Valuei((str[j-3]))<<8)\
			 +(Valuei((str[j-2]))<<4)+Valuei((str[j-1]));
		//printf("|%c%c%c%c=%d=%u\n",str[j-4],str[j-3],str[j-2],str[j-1],len,A[i]);
	 }
	 for(j=0;j<(len&0x03);A[i]<<=4,A[i]+=Valuei(str[j]),j++);
	 //for(j=0;A[i]<<=4,printf("@%d@%d@%u@",j,(len&0x03),A[i]),j<(len&0x03);A[i]+=Valuei(str[j]),j++,printf("@%d@%d@%u@\n",j,(len&0x03),A[i]));
}
//将128位大数按16进制格式输出为字符串
void Put(char *str, unsigned short *A)
{
	 short i,k;
	 memset(str,0,33);
	 for(i=7;A[i]==0&&i>=0;i--);
	 if(A[i]>>12==0){
	   for(k=1;i>=0&&k<3;k++)
		 if((A[i]>>k*4)==0) break;
	   for(;k>0;k--)
		 *str++=Valuea(((A[i]>>((k-1)*4))&0xf));
	   i--;
	 }
	 for(;i>=0;i--){
		 *str++=Valuea((A[i]>>12));
		 *str++=Valuea((A[i]>>8&0xf));
		 *str++=Valuea((A[i]>>4&0xf));
		 *str++=Valuea((A[i]&0xf));
	 }
	 *str='\0';
}
//将256位大数按16进制格式输出为字符串
void Put2(char *str, unsigned short *A)
{
	 short i,k;
	 memset(str,0,65);
	 for(i=15;A[i]==0&&i>=0;i--);
	 for(k=1;i>=0&&k<4;k++)
		 if(A[i]>>k*4==0) break;
	 for(;i>=0&&k>0;k--)
		 *str++=Valuea((A[i]>>k*4));
	 for(;i>=0;i--){
		 *str++=Valuea((A[i]>>12));
		 *str++=Valuea((A[i]>>8&0xf));
		 *str++=Valuea((A[i]>>4&0xf));
		 *str++=Valuea((A[i]&0xf));
	 }
	 *str='\0';
}
//********************************************************************
//将16字节字符串str的信息读入128位大整数A
void Getchar(unsigned short *A,unsigned char *str)
{
	 short i,j,len;
	 len=16;  //strlen(str);
	 for(i=0;i<(len+1)/2;i++) A[i]=0;
	 for(i=0;i<len/2;i++){
		j=len-i*2;
		A[i]=((unsigned short)str[j-2]<<8)+(unsigned short)str[j-1];
	 }
	 if(len&0x01) A[i]=(unsigned short)str[0];
}
//将128位大整数A的信息读入16字节字符串str
void Putchar(unsigned char *str, unsigned short *A)
{
	 short i;
	 memset(str,0,17);
	 for(i=7;A[i]==0&&i>=0;i--);
	 if(i>=0&&A[i]>>8==0){
		 *str++=A[i]&0xff;
		 i--;
	 }
	 for(;i>=0;i--){
		 *str++=A[i]>>8;
		 *str++=A[i]&0xff;
	 }
	 *str=0; //'\0'
}

//将128位大整数B转换成39位10进制A
void convert1(unsigned char *A,unsigned short * B)
{
   short i,j,k,h=3,cr;
   memset(A,0,40);
	for(i=7;B[i]==0&&i>=0;i--);
   for(;i>=0;i--){
		for(j=12;j>=0;j-=4){  //?
			cr=B[i]>>j&0xf;
			for(k=1;k<h;k++){
				A[k]=A[k]*16+cr;  //jian
				if(A[k]>9){
					if(A[k]>99) if(k==(h-2)) h++;
					cr=A[k]/10; // /&%
					A[k]=A[k]%10;
				}else cr=0;
			}
			if(A[h-1]) h++;  //for(h-1), have(h-2)wei.
		}
   }
}
//将39位10进制A转换成128位大整数B
void convert2(unsigned short *B,unsigned char *A)
{
	short i,j,h=1,cr;
	unsigned char *R;
	unsigned short m,n;
	memset(B,0,16);
	memset(R,0,32);
	for(i=39;(A[i]==0)&&i>0;i--);
	for(;i>0;i--){
		cr=A[i];
		for(j=0;j<h;j++){
			R[j]=R[j]*10+cr;  //jian
			if(R[j]>16){
				cr=R[j]>>4&0xf; // /&%
				R[j]=R[j]&0xf;
			}else cr=0;
		}
		if(cr) {R[j]=cr; h++;}
	}
	for(i=0;i<8;i++){
		m=(R[i*4+1]<<4)+R[i*4];
		n=(R[i*4+3]<<4)+R[i*4+2];
		B[i]=(n<<8)+m;
	}
}