实现一个小型的大数库

litong

这两天在琢磨一个大数库，考虑了几个方面，一是语言，二是大数结构，三是基。
结合LibTomMath和本论坛的一些经验，特别是liangbch兄的一些测试，初步确定
大数结构为:

1. struct MP_INT    usd            dd ?  //实际使用块    alc            dd ?  //已分配块    sgn            dd ?  //符号0,-1    dat            dd ?  //数据块指针ends

复制代码

alc 的值不可能小于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 30bit  28~31
MP_BIT   = 30
打算纯汇编实现，(fasm 汇编语法)，x86结构平台支持，达到一定阶段后，转向X64....
统一stdcall调用方式(x86很缺寄存器^_^)，对于返回的成功或失败由进位标志决定。
STC—Set Carry Flag 失败  (根源于申请内存错)
CLC—Clear Carry Flag 成功.
稳定后，开源，以便大牛优化和更多的算法实现。

局部标签:

1. 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

复制代码

asomiajht

单位数乘法mp_mul_d，用于基的转换(各种基的格式化输入)，初始非优化可能有bug的雏形：

1. align 16;a=a*data   ;data is positiveproc mp_mul_d _a,_data    push    esi    push    ebx    push    edi        mov     esi,[_a]    mov     ecx,[a.usd]    jz      .A02    and     [_data],MP_MASK    cmp     [_data],0    jnz     .A00    stdcall mp_zero,esi    jmp     .A02.A00:     cmp     [a.alc],ecx    ja      .A01    lea     eax,[ecx+1]    stdcall mp_grow,esi,eax    jc      .exit.A01:    xor     ebx,ebx    mov     esi,[a.dat]    xor     edi,edi             ;carry=0   @@:    mov     eax,[esi+ebx*4]    mul     [_data]             ;edx:eax    add     eax,edi    adc     edx,edi    shld    edx,eax,32-MP_BIT       and     eax,MP_MASK    mov     [esi+ebx*4],eax    mov     edi,edx             ;edi=carry    inc     ebx    cmp     ebx,ecx    jb      @B        test    edi,edi    jz      .A02    mov     [esi+ebx*4],edi    mov     esi,[_a]    add     [a.usd],1.A02:    clc.exit:    pop     edi    pop     ebx    pop     esi    retendp

复制代码

ameahopiyoyif

高山仰止
望洋兴叹

evuojad

楼主汇编功夫了得，若完全用汇编实现大数库，工作量非常巨大，且较难维护。
但本人非常支持楼主之创举。

ohicerebag

在做前期工作中，分析LibTomMath的结构意义，usd有些强要示，不妥，修正：

1. struct MP_INT    usd        dd ?    alc        dd ?    sgn        dd ?    dat        dd ?ends

复制代码

1.初始化后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 30bit  28~31
MP_BIT   = 30
相关标签：

1. 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

复制代码

oabipalehov

比如初始化一个mp_int 结构:

1. align 16;===================================================proc mp_init _c    stdcall XMALLOC,MP_PREC*4    jc     .exit        mov     ecx,[_c]    mov     [c.dat],eax    mov     [c.alc],MP_PREC    mov     [c.usd],0    mov     [c.sgn],0    clc;---------------------.exit:    retendp   

复制代码

清除结构：

1. align 16;===================================================proc mp_clear _a    mov     eax,[_a]    cmp     dword [a.dat],0    jz      .exit    push    eax    stdcall XFREE,[a.dat]    pop     eax    xor     ecx,ecx    mov     [a.dat],ecx    mov     [a.alc],ecx    mov     [a.usd],ecx    mov     [a.sgn],ecx.exit:    retendp

复制代码

litong

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,64

1. 00000018     alc0000000c     usdffffffff     sgn001d3a70     dat=================29a69a69     dat[0]00003a69369e90000000000a00a4000000000000249e8a6829a2992700000a68000000290000000000000040

复制代码

xiaobai

基于上面的结构，端午写了个64位的汇编版本，基2^62。api不再有返回错误，(只存在内存申请错，则终止)。内存申请可对齐到指定的字节，默认32字节。
简单做了个64位的static lib 作为与其它语言的调用测试(未严格测试正确性)，dll调用起来也容易与kernel32.dll无异:

1. ;==========================================================================================;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或'\[code]#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[i-1]);    printf("\ndat1=");    if(cT1.sng < 0)        printf("-");    for(i=cT1.usd;i>0;i--)        printf("%016I64X ",cT1.dat[i-1]);    printf("\ndat2=");    if(cT2.sng < 0)        printf("-");    for(i=cT2.usd;i>0;i--)        printf("%016I64X ",cT2.dat[i-1]);        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\


;==========================================================================================[/code]

ozjazit

怎么第一个数字是7fff
输出是13fff

ivamvanibumiq

第一个数字0x7fffffffffffffff是2^4为基(逗号仅仅为了增加某些输入的可读性)。转化为2^62为基输出就是0x13fffffffffffffff(大数运算的内部表示)，最高位在bit63无法表示，进位到下一个limb中，如果是2^64为基，则为0x7fffffffffffffff。