442 lines
14 KiB
Text
442 lines
14 KiB
Text
|
/* ARM assembly AARCH64 Raspberry PI 3B or android 64 bits */
|
|||
|
|
/* program tonshan64.s */
|
|||
|
|
|
|||
|
|
/*******************************************/
|
|||
|
|
/* Constantes file */
|
|||
|
|
/*******************************************/
|
|||
|
|
/* for this file see task include a file in language AArch64 assembly*/
|
|||
|
|
.include "../includeConstantesARM64.inc"
|
|||
|
|
|
|||
|
|
/*******************************************/
|
|||
|
|
/* Initialized data */
|
|||
|
|
/*******************************************/
|
|||
|
|
.data
|
|||
|
|
szMessStartPgm: .asciz "Program 64 bits start \n"
|
|||
|
|
szMessEndPgm: .asciz "Program normal end.\n"
|
|||
|
|
szMessError: .asciz "\033[31mError !!!\n"
|
|||
|
|
szMessErrGen: .asciz "Error end program.\n"
|
|||
|
|
szMessOverflow: .asciz "Overflow function modulo.\n"
|
|||
|
|
szMessNoSolution: .asciz "No solution.\n"
|
|||
|
|
szCarriageReturn: .asciz "\n"
|
|||
|
|
|
|||
|
|
/* datas message display */
|
|||
|
|
szMessEntry: .asciz "Number : @ modulo : @ ==> "
|
|||
|
|
szMessResult: .asciz "Racine 1 : @ Racine 2 : @ \n"
|
|||
|
|
|
|||
|
|
|
|||
|
|
qNumberN: .quad 44402
|
|||
|
|
qNumberP: .quad 100049
|
|||
|
|
/*******************************************/
|
|||
|
|
/* UnInitialized data */
|
|||
|
|
/*******************************************/
|
|||
|
|
.bss
|
|||
|
|
.align 4
|
|||
|
|
sZoneConv: .skip 24
|
|||
|
|
/*******************************************/
|
|||
|
|
/* code section */
|
|||
|
|
/*******************************************/
|
|||
|
|
.text
|
|||
|
|
.global main
|
|||
|
|
main: // program start
|
|||
|
|
ldr x0,qAdrszMessStartPgm // display start message
|
|||
|
|
bl affichageMess
|
|||
|
|
|
|||
|
|
mov x0,10
|
|||
|
|
mov x1,13
|
|||
|
|
bl displayEntry
|
|||
|
|
bl computeTonSha
|
|||
|
|
bl displayResult
|
|||
|
|
|
|||
|
|
mov x0,56
|
|||
|
|
mov x1,101
|
|||
|
|
bl displayEntry
|
|||
|
|
bl computeTonSha
|
|||
|
|
bl displayResult
|
|||
|
|
|
|||
|
|
mov x0,1030
|
|||
|
|
mov x1,10009
|
|||
|
|
bl displayEntry
|
|||
|
|
bl computeTonSha
|
|||
|
|
bl displayResult
|
|||
|
|
|
|||
|
|
mov x0,1032
|
|||
|
|
mov x1,10009
|
|||
|
|
bl displayEntry
|
|||
|
|
bl computeTonSha
|
|||
|
|
bcs 1f
|
|||
|
|
bl displayResult
|
|||
|
|
1:
|
|||
|
|
ldr x4,qAdrqNumberN
|
|||
|
|
ldr x0,[x4]
|
|||
|
|
ldr x4,qAdrqNumberP
|
|||
|
|
ldr x1,[x4]
|
|||
|
|
bl displayEntry
|
|||
|
|
bl computeTonSha
|
|||
|
|
bl displayResult
|
|||
|
|
|
|||
|
|
ldr x0,qAdrszMessEndPgm // display end message
|
|||
|
|
bl affichageMess
|
|||
|
|
b 100f
|
|||
|
|
99: // display error message
|
|||
|
|
ldr x0,qAdrszMessError
|
|||
|
|
bl affichageMess
|
|||
|
|
100: // standard end of the program
|
|||
|
|
mov x0, #0 // return code
|
|||
|
|
mov x8, #EXIT // request to exit program
|
|||
|
|
svc 0 // perform system call
|
|||
|
|
qAdrszMessStartPgm: .quad szMessStartPgm
|
|||
|
|
qAdrszMessEndPgm: .quad szMessEndPgm
|
|||
|
|
qAdrszMessError: .quad szMessError
|
|||
|
|
qAdrszMessNoSolution: .quad szMessNoSolution
|
|||
|
|
qAdrszCarriageReturn: .quad szCarriageReturn
|
|||
|
|
qAdrqNumberN: .quad qNumberN
|
|||
|
|
qAdrqNumberP: .quad qNumberP
|
|||
|
|
|
|||
|
|
qAdrszMessResult: .quad szMessResult
|
|||
|
|
qAdrsZoneConv: .quad sZoneConv
|
|||
|
|
|
|||
|
|
/******************************************************************/
|
|||
|
|
/* algorithm Tonelli–Shanks */
|
|||
|
|
/******************************************************************/
|
|||
|
|
/* x0 contains number */
|
|||
|
|
/* x1 contains modulus */
|
|||
|
|
/* x0 return root 1 */
|
|||
|
|
/* x1 return root 2 */
|
|||
|
|
computeTonSha:
|
|||
|
|
stp x10,lr,[sp,-16]! // save registres
|
|||
|
|
stp x2,x3,[sp,-16]! // save registres
|
|||
|
|
stp x4,x5,[sp,-16]! // save registres
|
|||
|
|
stp x6,x7,[sp,-16]! // save registres
|
|||
|
|
stp x8,x9,[sp,-16]! // save registres
|
|||
|
|
stp x11,x12,[sp,-16]! // save registres
|
|||
|
|
mov x9,x0 // save number
|
|||
|
|
mov x10,x1 // save modulo p
|
|||
|
|
mov x2,x10
|
|||
|
|
sub x1,x2,1
|
|||
|
|
lsr x1,x1,1
|
|||
|
|
bl moduloPuR64
|
|||
|
|
bcs 100f // error ?
|
|||
|
|
cmp x0,#1
|
|||
|
|
bne 20f
|
|||
|
|
sub x5,x10,1
|
|||
|
|
mov x6,#1 // s
|
|||
|
|
1:
|
|||
|
|
lsr x5,x5,#1 // div by 2
|
|||
|
|
tst x5,1 // even ?
|
|||
|
|
cinc x6,x6,eq // yes count
|
|||
|
|
beq 1b // and loop
|
|||
|
|
// x5 = q
|
|||
|
|
cmp x6,#1 // s = 1 ?
|
|||
|
|
bne 3f
|
|||
|
|
add x1,x10,1 // compute root 1
|
|||
|
|
lsr x1,x1,#2 // p + 1 / 4
|
|||
|
|
mov x0,x9 // n
|
|||
|
|
mov x2,x10 // p
|
|||
|
|
bl moduloPuR64
|
|||
|
|
bcs 100f // error ?
|
|||
|
|
neg x1,x0 // compute root 2 = - root 1
|
|||
|
|
b 100f // and end
|
|||
|
|
3:
|
|||
|
|
mov x7,#3 // z
|
|||
|
|
4:
|
|||
|
|
mov x0,x7
|
|||
|
|
mov x2,x10 // p
|
|||
|
|
sub x1,x2,1
|
|||
|
|
lsr x1,x1,1 // power = p - 1 / 2
|
|||
|
|
bl moduloPuR64
|
|||
|
|
bcs 100f // error ?
|
|||
|
|
cmp x0,#1
|
|||
|
|
cinc x7,x7,eq // si égal à 1
|
|||
|
|
cinc x7,x7,eq
|
|||
|
|
beq 4b
|
|||
|
|
cmp x0,0
|
|||
|
|
cinc x7,x7,eq // si egal à 0
|
|||
|
|
cinc x7,x7,eq
|
|||
|
|
beq 4b
|
|||
|
|
mov x0,x7 // z
|
|||
|
|
mov x1,x5 // q
|
|||
|
|
mov x2,x10 // p
|
|||
|
|
bl moduloPuR64
|
|||
|
|
bcs 100f // error ?
|
|||
|
|
mov x12,x0 // c = z pow q mod p
|
|||
|
|
|
|||
|
|
add x1,x5,1 // = q +1
|
|||
|
|
lsr x1,x1,1 // div 2
|
|||
|
|
mov x0,x9 // n
|
|||
|
|
mov x2,x10 // p
|
|||
|
|
bl moduloPuR64
|
|||
|
|
mov x4,x0 // r = n puis (q+1)/2 mod p
|
|||
|
|
|
|||
|
|
mov x0,x9 // n
|
|||
|
|
mov x1,x5 // = q
|
|||
|
|
mov x2,x10 // p
|
|||
|
|
bl moduloPuR64
|
|||
|
|
bcs 100f // error ?
|
|||
|
|
mov x5,x0 // reuse r5 = t = n pow q mod p
|
|||
|
|
|
|||
|
|
8: // begin loop
|
|||
|
|
cmp x5,1
|
|||
|
|
beq 10f
|
|||
|
|
mov x0,x5 // t
|
|||
|
|
mov x1,x6 // m
|
|||
|
|
mov x2,x10 // p
|
|||
|
|
bl searchI // search i for t puis 2 puis i = 1 mod p
|
|||
|
|
cmp x0,-1 // not find -> no solution
|
|||
|
|
beq 20f
|
|||
|
|
mov x9,x0 // i
|
|||
|
|
sub x8,x6,x0 // compute b
|
|||
|
|
sub x8,x8,1 // m - i - 1
|
|||
|
|
mov x1,1
|
|||
|
|
lsl x1,x1,x8
|
|||
|
|
mov x0,x12
|
|||
|
|
mov x2,x10 // p
|
|||
|
|
bl moduloPuR64
|
|||
|
|
bcs 100f // error ?
|
|||
|
|
mov x7,x0 // b = c puis 2 puis 2 puis m-i-1 à verifier
|
|||
|
|
|
|||
|
|
mul x0,x7,x4 // r = r * b mod p
|
|||
|
|
umulh x1,x7,x4
|
|||
|
|
mov x2,x10
|
|||
|
|
bl divisionReg128U
|
|||
|
|
mov x4,x3 // r mod p
|
|||
|
|
mul x0,x7,x7
|
|||
|
|
umulh x1,x7,x7
|
|||
|
|
mov x2,x10
|
|||
|
|
bl divisionReg128U
|
|||
|
|
mov x12,x3 // c mod p
|
|||
|
|
|
|||
|
|
mul x0,x5,x12
|
|||
|
|
umulh x1,x5,x12
|
|||
|
|
mov x2,x10
|
|||
|
|
bl divisionReg128U
|
|||
|
|
mov x5,x3 // t mod p
|
|||
|
|
|
|||
|
|
mov x6,x9 // m = i
|
|||
|
|
b 8b
|
|||
|
|
9:
|
|||
|
|
|
|||
|
|
10:
|
|||
|
|
mov x0,x4 // x0 return root 1
|
|||
|
|
sub x1,x10,x0 // x1 return root 2
|
|||
|
|
cmn x0,0 // carry à zero roots ok
|
|||
|
|
b 100f
|
|||
|
|
20:
|
|||
|
|
ldr x0,qAdrszMessNoSolution
|
|||
|
|
bl affichageMess
|
|||
|
|
|
|||
|
|
mov x0,0
|
|||
|
|
mov x1,0
|
|||
|
|
cmp x0,0 // carry to 1 No solution
|
|||
|
|
100:
|
|||
|
|
ldp x11,x12,[sp],16
|
|||
|
|
ldp x8,x9,[sp],16
|
|||
|
|
ldp x6,x7,[sp],16
|
|||
|
|
ldp x4,x5,[sp],16
|
|||
|
|
ldp x2,x3,[sp],16
|
|||
|
|
ldp x10,lr,[sp],16 // restaur des 2 registres
|
|||
|
|
ret // retour adresse lr x30
|
|||
|
|
|
|||
|
|
/******************************************************************/
|
|||
|
|
/* search i */
|
|||
|
|
/******************************************************************/
|
|||
|
|
// x0 contains t
|
|||
|
|
// x1 contains maxi
|
|||
|
|
// x2 contains modulo
|
|||
|
|
searchI:
|
|||
|
|
stp x1,lr,[sp,-16]! // save registres
|
|||
|
|
stp x2,x3,[sp,-16]! // save registres
|
|||
|
|
stp x4,x5,[sp,-16]! // save registres
|
|||
|
|
stp x6,x7,[sp,-16]! // save registres
|
|||
|
|
mov x4,x0 // t
|
|||
|
|
mov x6,x1 // m
|
|||
|
|
mov x3,1 // i
|
|||
|
|
1:
|
|||
|
|
mov x5,1
|
|||
|
|
lsl x5,x5,x3 // compute 2 power i
|
|||
|
|
|
|||
|
|
mov x0,x4
|
|||
|
|
mov x1,x5
|
|||
|
|
bl moduloPuR64 // compute t pow 2 pow i mod p
|
|||
|
|
cmp x0,1 // = 1 ?
|
|||
|
|
beq 3f // yes it is ok
|
|||
|
|
add x3,x3,1 // next i
|
|||
|
|
cmp x3,x6
|
|||
|
|
blt 1b // loop
|
|||
|
|
mov x0,-1 // not find
|
|||
|
|
b 100f
|
|||
|
|
3:
|
|||
|
|
mov x0,x3 // return i
|
|||
|
|
100:
|
|||
|
|
ldp x6,x7,[sp],16
|
|||
|
|
ldp x4,x5,[sp],16
|
|||
|
|
ldp x2,x3,[sp],16
|
|||
|
|
ldp x1,lr,[sp],16 // restaur des 2 registres
|
|||
|
|
ret // retour adresse lr x30
|
|||
|
|
/******************************************************************/
|
|||
|
|
/* display numbers */
|
|||
|
|
/******************************************************************/
|
|||
|
|
/* x0 contains number */
|
|||
|
|
/* x1 contains modulo */
|
|||
|
|
displayEntry:
|
|||
|
|
stp x0,lr,[sp,-16]! // save registres
|
|||
|
|
stp x1,x2,[sp,-16]! // save registres
|
|||
|
|
mov x2,x1 // root 2
|
|||
|
|
ldr x1,qAdrsZoneConv // convert root 1 in r0
|
|||
|
|
bl conversion10S // convert ascii string
|
|||
|
|
ldr x0,qAdrszMessEntry
|
|||
|
|
ldr x1,qAdrsZoneConv
|
|||
|
|
bl strInsertAtCharInc // and put in message
|
|||
|
|
mov x3,x0
|
|||
|
|
mov x0,x2 // racine 2
|
|||
|
|
ldr x1,qAdrsZoneConv
|
|||
|
|
bl conversion10S // convert ascii string
|
|||
|
|
mov x0,x3
|
|||
|
|
ldr x1,qAdrsZoneConv
|
|||
|
|
bl strInsertAtCharInc // and put in message
|
|||
|
|
bl affichageMess
|
|||
|
|
100:
|
|||
|
|
ldp x1,x2,[sp],16
|
|||
|
|
ldp x0,lr,[sp],16 // restaur des 2 registres
|
|||
|
|
ret // retour adresse lr x30
|
|||
|
|
qAdrszMessEntry: .quad szMessEntry
|
|||
|
|
/******************************************************************/
|
|||
|
|
/* display roots */
|
|||
|
|
/******************************************************************/
|
|||
|
|
/* x0 contains root 1 */
|
|||
|
|
/* x1 contains root 2 */
|
|||
|
|
displayResult:
|
|||
|
|
stp x1,lr,[sp,-16]! // save registres
|
|||
|
|
stp x2,x3,[sp,-16]! // save registres
|
|||
|
|
mov x2,x1 // root 2
|
|||
|
|
ldr x1,qAdrsZoneConv // convert root 1 in r0
|
|||
|
|
bl conversion10S // convert ascii string
|
|||
|
|
ldr x0,qAdrszMessResult
|
|||
|
|
ldr x1,qAdrsZoneConv
|
|||
|
|
bl strInsertAtCharInc // and put in message
|
|||
|
|
mov x3,x0
|
|||
|
|
mov x0,x2 // racine 2
|
|||
|
|
ldr x1,qAdrsZoneConv
|
|||
|
|
bl conversion10S // convert ascii string
|
|||
|
|
mov x0,x3
|
|||
|
|
ldr x1,qAdrsZoneConv
|
|||
|
|
bl strInsertAtCharInc // and put in message
|
|||
|
|
bl affichageMess
|
|||
|
|
100:
|
|||
|
|
ldp x2,x3,[sp],16
|
|||
|
|
ldp x1,lr,[sp],16 // restaur des 2 registres
|
|||
|
|
ret // retour adresse lr x30
|
|||
|
|
/**************************************************************/
|
|||
|
|
/********************************************************/
|
|||
|
|
/* Calcul modulo de b puissance e modulo m */
|
|||
|
|
/* Exemple 4 puissance 13 modulo 497 = 445 */
|
|||
|
|
/********************************************************/
|
|||
|
|
/* x0 nombre */
|
|||
|
|
/* x1 exposant */
|
|||
|
|
/* x2 modulo */
|
|||
|
|
moduloPuR64:
|
|||
|
|
stp x1,lr,[sp,-16]! // save registres
|
|||
|
|
stp x3,x4,[sp,-16]! // save registres
|
|||
|
|
stp x5,x6,[sp,-16]! // save registres
|
|||
|
|
stp x7,x8,[sp,-16]! // save registres
|
|||
|
|
stp x9,x10,[sp,-16]! // save registres
|
|||
|
|
cbz x0,100f
|
|||
|
|
cbz x1,100f
|
|||
|
|
mov x8,x0
|
|||
|
|
mov x7,x1
|
|||
|
|
mov x6,1 // resultat
|
|||
|
|
udiv x4,x8,x2
|
|||
|
|
msub x9,x4,x2,x8 // contient le reste
|
|||
|
|
1:
|
|||
|
|
tst x7,1
|
|||
|
|
beq 2f
|
|||
|
|
mul x4,x9,x6
|
|||
|
|
umulh x5,x9,x6
|
|||
|
|
mov x6,x4
|
|||
|
|
mov x0,x6
|
|||
|
|
mov x1,x5
|
|||
|
|
bl divisionReg128U
|
|||
|
|
cbnz x1,99f // overflow
|
|||
|
|
mov x6,x3
|
|||
|
|
2:
|
|||
|
|
mul x8,x9,x9
|
|||
|
|
umulh x5,x9,x9
|
|||
|
|
mov x0,x8
|
|||
|
|
mov x1,x5
|
|||
|
|
bl divisionReg128U
|
|||
|
|
cbnz x1,99f // overflow
|
|||
|
|
mov x9,x3
|
|||
|
|
lsr x7,x7,1
|
|||
|
|
cbnz x7,1b
|
|||
|
|
cmn x0,0 // carry à zero pas d'erreur
|
|||
|
|
mov x0,x6 // result
|
|||
|
|
b 100f
|
|||
|
|
99:
|
|||
|
|
ldr x0,qAdrszMessOverflow
|
|||
|
|
bl affichageMess
|
|||
|
|
cmp x0,0 // carry à un car erreur
|
|||
|
|
mov x0,-1 // code erreur
|
|||
|
|
|
|||
|
|
100:
|
|||
|
|
ldp x9,x10,[sp],16 // restaur des 2 registres
|
|||
|
|
ldp x7,x8,[sp],16 // restaur des 2 registres
|
|||
|
|
ldp x5,x6,[sp],16 // restaur des 2 registres
|
|||
|
|
ldp x3,x4,[sp],16 // restaur des 2 registres
|
|||
|
|
ldp x1,lr,[sp],16 // restaur des 2 registres
|
|||
|
|
ret // retour adresse lr x30
|
|||
|
|
qAdrszMessOverflow: .quad szMessOverflow
|
|||
|
|
/***************************************************/
|
|||
|
|
/* division d un nombre de 128 bits par un nombre de 64 bits */
|
|||
|
|
/***************************************************/
|
|||
|
|
/* x0 contient partie basse dividende */
|
|||
|
|
/* x1 contient partie haute dividente */
|
|||
|
|
/* x2 contient le diviseur */
|
|||
|
|
/* x0 retourne partie basse quotient */
|
|||
|
|
/* x1 retourne partie haute quotient */
|
|||
|
|
/* x3 retourne le reste */
|
|||
|
|
divisionReg128U:
|
|||
|
|
stp x6,lr,[sp,-16]! // save registres
|
|||
|
|
stp x4,x5,[sp,-16]! // save registres
|
|||
|
|
mov x5,#0 // raz du reste R
|
|||
|
|
mov x3,#128 // compteur de boucle
|
|||
|
|
mov x4,#0 // dernier bit
|
|||
|
|
1:
|
|||
|
|
lsl x5,x5,#1 // on decale le reste de 1
|
|||
|
|
tst x1,1<<63 // test du bit le plus à gauche
|
|||
|
|
lsl x1,x1,#1 // on decale la partie haute du quotient de 1
|
|||
|
|
beq 2f
|
|||
|
|
orr x5,x5,#1 // et on le pousse dans le reste R
|
|||
|
|
2:
|
|||
|
|
tst x0,1<<63
|
|||
|
|
lsl x0,x0,#1 // puis on decale la partie basse
|
|||
|
|
beq 3f
|
|||
|
|
orr x1,x1,#1 // et on pousse le bit de gauche dans la partie haute
|
|||
|
|
3:
|
|||
|
|
orr x0,x0,x4 // position du dernier bit du quotient
|
|||
|
|
mov x4,#0 // raz du bit
|
|||
|
|
cmp x5,x2
|
|||
|
|
blt 4f
|
|||
|
|
sub x5,x5,x2 // on enleve le diviseur du reste
|
|||
|
|
mov x4,#1 // dernier bit à 1
|
|||
|
|
4:
|
|||
|
|
// et boucle
|
|||
|
|
subs x3,x3,#1
|
|||
|
|
bgt 1b
|
|||
|
|
lsl x1,x1,#1 // on decale le quotient de 1
|
|||
|
|
tst x0,1<<63
|
|||
|
|
lsl x0,x0,#1 // puis on decale la partie basse
|
|||
|
|
beq 5f
|
|||
|
|
orr x1,x1,#1
|
|||
|
|
5:
|
|||
|
|
orr x0,x0,x4 // position du dernier bit du quotient
|
|||
|
|
mov x3,x5
|
|||
|
|
100:
|
|||
|
|
ldp x4,x5,[sp],16 // restaur des 2 registres
|
|||
|
|
ldp x6,lr,[sp],16 // restaur des 2 registres
|
|||
|
|
ret // retour adresse lr x30
|
|||
|
|
|
|||
|
|
/********************************************************/
|
|||
|
|
/* File Include fonctions */
|
|||
|
|
/********************************************************/
|
|||
|
|
/* for this file see task include a file in language AArch64 assembly */
|
|||
|
|
.include "../includeARM64.inc"
|