实现一个小型的大数库
这两天在琢磨一个大数库，考虑了几个方面，一是语言，二是大数结构，三是基。结合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 virtualvirtual at edi b: .usd dd ? .alc dd ? .sgn dd ? .dat dd ?end virtualvirtual at ebx c: .usd dd ? .alc dd ? .sgn dd ? .dat dd ?end virtual 单位数乘法mp_mul_d，用于基的转换(各种基的格式化输入)，初始非优化可能有bug的雏形：align 16;a=a*data ;data is positiveproc 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 retendp 高山仰止
望洋兴叹 楼主汇编功夫了得，若完全用汇编实现大数库，工作量非常巨大，且较难维护。
但本人非常支持楼主之创举。 在做前期工作中，分析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 virtualvirtual at edi e: .usd dd ? .alc dd ? .sgn dd ? .dat dd ?end virtualvirtual at eax a: .usd dd ? .alc dd ? .sgn dd ? .dat dd ?end virtualvirtual at ebx b: .usd dd ? .alc dd ? .sgn dd ? .dat dd ?end virtualvirtual at ecx c: .usd dd ? .alc dd ? .sgn dd ? .dat dd ?end virtualvirtual 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: retendp 清除结构：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: retendp 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 alc0000000c usdffffffff sgn001d3a70 dat=================29a69a69 dat00003a69369e90000000000a00a4000000000000249e8a6829a2992700000a68000000290000000000000040 基于上面的结构，端午写了个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");}https://bbs.emath.ac.cn/data/attachment/forum/month_1306/1306132332d580fa4869cd5718.png
;输入串，以0结束或以\$结束:
;str[]="-12abc03";
;str[]="1,2ab,c03";
;str[]=" - 1, 2ab,c03\$afdf"; 预扫描有效字符' - 1, 2ab,c03\
;========================================================================================== 怎么第一个数字是7fff
输出是13fff 第一个数字0x7fffffffffffffff是2^4为基(逗号仅仅为了增加某些输入的可读性)。转化为2^62为基输出就是0x13fffffffffffffff(大数运算的内部表示)，最高位在bit63无法表示，进位到下一个limb中，如果是2^64为基，则为0x7fffffffffffffff。
页:
[1]