实现一个小型的大数库
这两天在琢磨一个大数库，考虑了几个方面，一是语言，二是大数结构，三是基。结合LibTomMath和本论坛的一些经验，特别是liangbch兄的一些测试，初步确定
大数结构为:struct MP_INT
usd dd ?//实际使用块
alc dd ?//已分配块
sgn dd ?//符号0,-1
dat dd ?//数据块指针
endsalc 的值不可能小于1，dat总是指向一个预先分配有空间的数组。//初始值设为MP_PREC
usd 的值不可能超过alc，并且必须大于等于0，其值暗示了数组dat中第(usd-1)不为0。数组dat中第usd个及
以上位置必须为0。
如果usd为0。那么sgn的值必须是0，这代表mp_int的值为0。
sgn 表示0或正数时其值为0，负数时其值为-1.
以2为基底，位在31~28 ，内测定义30位。
MP_MASK= 3FFFFFFFh;base 30bit28~31
MP_BIT = 30
打算纯汇编实现，(fasm 汇编语法)，x86结构平台支持，达到一定阶段后，转向X64....
统一stdcall调用方式(x86很缺寄存器^_^)，对于返回的成功或失败由进位标志决定。
STC—Set Carry Flag 失败(根源于申请内存错)
CLC—Clear Carry Flag 成功.
稳定后，开源，以便大牛优化和更多的算法实现。
局部标签:virtual at esi
a:
.usd dd ?
.alc dd ?
.sgn dd ?
.dat dd ?
end virtual
virtual at edi
b:
.usd dd ?
.alc dd ?
.sgn dd ?
.dat dd ?
end virtual
virtual at ebx
c:
.usd dd ?
.alc dd ?
.sgn dd ?
.dat dd ?
end virtual 单位数乘法mp_mul_d，用于基的转换(各种基的格式化输入)，初始非优化可能有bug的雏形：align 16
;a=a*data ;data is positive
proc mp_mul_d _a,_data
push esi
push ebx
push edi
mov esi,
mov ecx,
jz .A02
and ,MP_MASK
cmp ,0
jnz .A00
stdcall mp_zero,esi
jmp .A02
.A00:
cmp ,ecx
ja .A01
lea eax,
stdcall mp_grow,esi,eax
jc .exit
.A01:
xor ebx,ebx
mov esi,
xor edi,edi ;carry=0
@@:
mov eax,
mul ;edx:eax
add eax,edi
adc edx,edi
shld edx,eax,32-MP_BIT
and eax,MP_MASK
mov ,eax
mov edi,edx ;edi=carry
inc ebx
cmp ebx,ecx
jb @B
test edi,edi
jz .A02
mov ,edi
mov esi,
add ,1
.A02:
clc
.exit:
pop edi
pop ebx
pop esi
ret
endp
高山仰止
望洋兴叹 楼主汇编功夫了得，若完全用汇编实现大数库，工作量非常巨大，且较难维护。
但本人非常支持楼主之创举。 在做前期工作中，分析LibTomMath的结构意义，usd有些强要示，不妥，修正：struct MP_INT
usd dd ?
alc dd ?
sgn dd ?
dat dd ?
ends1.初始化后alc 的值不可能小于1，dat总是指向一个预先分配有空间的数组。初始值设为MP_PREC。
2.usd 的值不可能超过alc，并且必须大于等于0，其值暗示了数组dat中第(usd-1)不为0。
如果usd为0,这代表mp_int的值为0,此时sgn的值必须是0，数组dat中第usd个及以上位置不保证为0。
3.sgn 表示0或正数时其值为0，负数时其值为-1.
MP_PREC= 8 ;byte 8 16 32 64 128 256 ...
MP_MASK= 3FFFFFFFh;base 30bit28~31
MP_BIT = 30
相关标签：virtual at esi
s:
.usd dd ?
.alc dd ?
.sgn dd ?
.dat dd ?
end virtual
virtual at edi
e:
.usd dd ?
.alc dd ?
.sgn dd ?
.dat dd ?
end virtual
virtual at eax
a:
.usd dd ?
.alc dd ?
.sgn dd ?
.dat dd ?
end virtual
virtual at ebx
b:
.usd dd ?
.alc dd ?
.sgn dd ?
.dat dd ?
end virtual
virtual at ecx
c:
.usd dd ?
.alc dd ?
.sgn dd ?
.dat dd ?
end virtual
virtual at edx
d:
.usd dd ?
.alc dd ?
.sgn dd ?
.dat dd ?
end virtual 比如初始化一个mp_int 结构:align 16
;===================================================
proc mp_init _c
stdcall XMALLOC,MP_PREC*4
jc .exit
mov ecx,
mov ,eax
mov ,MP_PREC
mov ,0
mov ,0
clc
;---------------------
.exit:
ret
endp 清除结构：align 16
;===================================================
proc mp_clear _a
mov eax,
cmp dword ,0
jz .exit
push eax
stdcall XFREE,
pop eax
xor ecx,ecx
mov ,ecx
mov ,ecx
mov ,ecx
mov ,ecx
.exit:
ret
endp 2楼mp_mul_d bug
adc edx,edi 更正为adc edx,0
2~64进制的串读取:
==========================================================================
;fmp_read_radix(_a,_str,_radix)
;_radix -64 -2 ~2 64 取绝对值
若基不大于36时，字母大小写忽略;
串支持5个分隔符:空格，逗号，制表，回车，换行符;
串终止符二选一：零或字符'\$';
支持负号'-';
;_map="0123456789ABCDEFGHIJKLMNOPQRSTUVWSYZabcdefghijklmnopqrstuvwxyz+/",20h,',',09h,0ah,0dh
;最多10+26+26+2=64个有效字符+分隔号5个=69
;预扫描终止符:0或'\$'
;输入串，以0结束或以\$结束:
;str[]="-12abc03";
;str[]="1,2ab,c03";
;str[]=" - 1, 2ab,c03\$afdf"; 预扫描字符' - 1, 2ab,c03\$'
;=========================================================================
为验证正确性，与tommath.lib得到的结果一致(base 30bit).
mp_read_radix(&a,"-10000000000f000fefefadadefe000000f0000000Asdf00003fffffff",64);
tommath不支持分隔符。
fmp_read_radix测试串szTest
szTest db ' - 10000000, 000f000fefefadadefe000000f0000000 Asdf00,003 fffffff\$', 09h
//stdcall fmp_read_radix,mp_t,szTest,6400000018 alc
0000000c usd
ffffffff sgn
001d3a70 dat
=================
29a69a69 dat
00003a69
369e9000
0000000a
00a40000
00000000
249e8a68
29a29927
00000a68
00000029
00000000
00000040 基于上面的结构，端午写了个64位的汇编版本，基2^62。api不再有返回错误，(只存在内存申请错，则终止)。内存申请可对齐到指定的字节，默认32字节。
简单做了个64位的static lib 作为与其它语言的调用测试(未严格测试正确性)，dll调用起来也容易与kernel32.dll无异:;==========================================================================================
;mpz_read_radix(a,str,radix)
;radix -64 -2~2 64
;map="0123456789ABCDEFGHIJKLMNOPQRSTUVWSYZabcdefghijklmnopqrstuvwxyz+/",20h,',',09h,0ah,0dh
;最多10+26+26+2=64个有效字符+分隔号5个=69
;预扫描终止符:0或'\#include <stdio.h>
typedef _int64 INT64;
typedef unsigned _int64 UINT64;
typedef unsigned char UCHAR;
typedef struct
{
UINT64 usd;
UINT64 alc;
INT64 sng;
UINT64 *dat;
}MP_INT;
void mpz_init(MP_INT *);
void mpz_read_radix(MP_INT *,UCHAR *str,UINT64 radix);
void mpz_clear(MP_INT *);
void main()
{
UCHAR *str0="7,ff ff,ffff,ffff,fff\$";
UCHAR *str1="1,2ab,c03";
UCHAR *str2=" - 10000000, 000f000fefefadadefe000000f0000000 Asdf00,003 fffffff";
MP_INT cT0,cT1,cT2;
UINT64 i=0;
mpz_init(&cT0);
mpz_init(&cT1);
mpz_init(&cT2);
mpz_read_radix(&cT0,str0,16);
mpz_read_radix(&cT1,str1,16);
mpz_read_radix(&cT2,str2,64);
printf("\ndat0=");
for(i=cT0.usd;i>0;i--)
printf("%016I64X ",cT0.dat);
printf("\ndat1=");
if(cT1.sng < 0)
printf("-");
for(i=cT1.usd;i>0;i--)
printf("%016I64X ",cT1.dat);
printf("\ndat2=");
if(cT2.sng < 0)
printf("-");
for(i=cT2.usd;i>0;i--)
printf("%016I64X ",cT2.dat);
mpz_clear(&cT0);
mpz_clear(&cT1);
mpz_clear(&cT2);
system("pause");
}
;输入串，以0结束或以\$结束:
;str[]="-12abc03";
;str[]="1,2ab,c03";
;str[]=" - 1, 2ab,c03\$afdf"; 预扫描有效字符' - 1, 2ab,c03\[ DISCUZ_CODE_1 ]
;==========================================================================================[ DISCUZ_CODE_1 ]
G-Spider 发表于 2013-6-13 23:32
基于上面的结构，端午写了个64位的汇编版本，基2^62。api不再有返回错误，(只存在内存申请错，则终止)。内 ...
怎么第一个数字是7fff
输出是13fff gogdizzy 发表于 2013-7-2 18:44
怎么第一个数字是7fff
输出是13fff
第一个数字0x7fffffffffffffff是2^4为基(逗号仅仅为了增加某些输入的可读性)。转化为2^62为基输出就是0x13fffffffffffffff(大数运算的内部表示)，最高位在bit63无法表示，进位到下一个limb中，如果是2^64为基，则为0x7fffffffffffffff。
页:
[1]