(05-06-2020 05:08 AM)Nad Wrote: [ -> ]Even rewriting my string to mpz conversion routine is presenting somewhat of a challenge
The following C/assembly code converts the string commandLineString to an mpz and stores the result in mpz1, and gives the length of mpz1 in limbs:
Code:
#define MAXLIMBS 1000 //adjust depending on amount of RAM available
typedef uint32_t mpz[MAXLIMBS];
uint32_t mpz_10[] = {10};
mpz mpz1;
mpz mpz2;
mpz w;
uint32_t i;
uint32_t j;
uint32_t limbs;
i = 0;
limbs = 1;
while (commandLineString[i]) {
limbs = multiply_mpz(limbs, mpz1, 1, mpz_10);
for (j=0;j<limbs;j++) mpz1[j]=w[j];
init_w(); //set w = 0
limbs = mpzx10PlusDigit(limbs,commandLineString[i]-48);
i++;
}
The function multiply_mpz uses the "classic" multiplication algorithm:
Code:
uint32_t multiply_mpz(uint32_t m, uint32_t * u, uint32_t n,uint32_t * v) {
uint32_t i;
uint32_t j;
uint32_t carry;
uint64_t t;
for (j=0;j<n;j++) {
if (v[j]==0) continue;
carry = 0;
for (i=0;i<m;i++) {
t = limbProduct(u[i],v[j],carry,w[i+j]);
w[i+j] = t;
carry = t >> 32;
}
w[m+j]=carry;
}
if (w[m+n-1]==0) limbs = m+n-1;
else limbs = m+n;
return limbs;
}
The assembly routine limbProduct returns a 64-bit result:
Code:
AREA limbProduct_area,CODE,READONLY
EXPORT limbProduct
ENTRY
limbProduct UMULL R0,R1,R0,R1
ADDS R0,R0,R2
ADC R1,R1,#0
ADDS R0,R0,R3
ADC R1,R1,#0
BX lr
END
For Cortex M4/M7 processors the multiply and accumulate instruction UMAAL can be used in limbProduct, making the algorithm faster.
After mpz1 has been multiplied by 10 the assembly routine mpzx10PlusDigit adds to it the next digit in commandLineString:
Code:
;add mpz1 to commandLineString[i]-0x30 and store in mpz1
;input: R0 = number of limbs, R1 = commandLineString[i]-0x30
;output: R0 = number of limbs
AREA mpzx10PlusDigit_area,CODE,READONLY
EXPORT mpzx10PlusDigit
IMPORT mpz1
ENTRY
mpzx10PlusDigit
PUSH {R4,R5}
MOV R4,R0
LDR R5,=0xFFFFFFFF
LDR R2,=mpz1
SUBS R0,R0,#1
BEQ section_2
LDR R3,[R2]
ADDS R3,R3,R1
STR R3,[R2],#4
SUB R0,R0,#1
TST R0,R5
BEQ section_1
loop LDR R3,[R2]
ADCS R3,R3,#0
STR R3,[R2],#4
SUB R0,R0,#1
TST R0,R5
BNE loop
;;;;;;;;;;;;;;;;;add MS limb of mpz_1 and commandLineString[i]-0x30 and add new limb if necessary
section_1 LDR R3,[R2]
ADCS R3,R3,#0
STR R3,[R2],#4
BCC exit
LDR R3,[R2]
MOV R3,#1
STR R3,[R2]
ADD R4,R4,#1
B exit
;;;;;;;;;;;;;;;;;add limb of mpz_1 and commandLineString[i]-0x30 and add new limb if necessary
section_2 LDR R3,[R2]
ADDS R3,R3,R1
STR R3,[R2],#4
BCC exit
LDR R3,[R2]
MOV R3,#1
STR R3,[R2]
ADD R4,R4,#1
exit MOV R0,R4
POP {R4,R5}
BX lr
END