Books about CAS

[F-73P]

(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