421 lines
13 KiB
Text
421 lines
13 KiB
Text
|
/* ARM assembly Raspberry PI or android 32 bits */
|
|||
|
|
/* program tonshan.s */
|
|||
|
|
|
|||
|
|
/* REMARK 1 : this program use routines in a include file
|
|||
|
|
see task Include a file language arm assembly
|
|||
|
|
for the routine affichageMess conversion10
|
|||
|
|
see at end of this program the instruction include */
|
|||
|
|
/* for constantes see task include a file in arm assembly */
|
|||
|
|
/************************************/
|
|||
|
|
/* Constantes */
|
|||
|
|
/************************************/
|
|||
|
|
.include "../constantes.inc"
|
|||
|
|
|
|||
|
|
/*******************************************/
|
|||
|
|
/* Initialized data */
|
|||
|
|
/*******************************************/
|
|||
|
|
.data
|
|||
|
|
szMessStartPgm: .asciz "Program 32 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"
|
|||
|
|
|
|||
|
|
iNumberN: .int 1030
|
|||
|
|
iNumberP: .int 10009
|
|||
|
|
|
|||
|
|
iNumberN1: .int 1032
|
|||
|
|
iNumberP1: .int 10009
|
|||
|
|
|
|||
|
|
iNumberN2: .int 44402
|
|||
|
|
iNumberP2: .int 100049
|
|||
|
|
|
|||
|
|
/*******************************************/
|
|||
|
|
/* UnInitialized data */
|
|||
|
|
/*******************************************/
|
|||
|
|
.bss
|
|||
|
|
.align 4
|
|||
|
|
sZoneConv: .skip 24
|
|||
|
|
/*******************************************/
|
|||
|
|
/* code section */
|
|||
|
|
/*******************************************/
|
|||
|
|
.text
|
|||
|
|
.global main
|
|||
|
|
main: // program start
|
|||
|
|
ldr r0,iAdrszMessStartPgm // display start message
|
|||
|
|
bl affichageMess
|
|||
|
|
|
|||
|
|
mov r0,#10
|
|||
|
|
mov r1,#13
|
|||
|
|
bl displayEntry // display entry number
|
|||
|
|
bl computeTonSha // compute roots
|
|||
|
|
bl displayResult // display roots
|
|||
|
|
|
|||
|
|
mov r0,#56
|
|||
|
|
mov r1,#101
|
|||
|
|
bl displayEntry
|
|||
|
|
bl computeTonSha
|
|||
|
|
bl displayResult
|
|||
|
|
|
|||
|
|
|
|||
|
|
ldr r4,iAdriNumberN
|
|||
|
|
ldr r0,[r4]
|
|||
|
|
ldr r4,iAdriNumberP
|
|||
|
|
ldr r1,[r4]
|
|||
|
|
bl displayEntry
|
|||
|
|
bl computeTonSha
|
|||
|
|
bl displayResult
|
|||
|
|
|
|||
|
|
ldr r4,iAdriNumberN1
|
|||
|
|
ldr r0,[r4]
|
|||
|
|
ldr r4,iAdriNumberP1
|
|||
|
|
ldr r1,[r4]
|
|||
|
|
bl displayEntry
|
|||
|
|
bl computeTonSha
|
|||
|
|
bcs 1f
|
|||
|
|
bl displayResult
|
|||
|
|
1:
|
|||
|
|
ldr r4,iAdriNumberN2
|
|||
|
|
ldr r0,[r4]
|
|||
|
|
ldr r4,iAdriNumberP2
|
|||
|
|
ldr r1,[r4]
|
|||
|
|
bl displayEntry
|
|||
|
|
bl computeTonSha
|
|||
|
|
bl displayResult
|
|||
|
|
|
|||
|
|
ldr r0,iAdrszMessEndPgm // display end message
|
|||
|
|
bl affichageMess
|
|||
|
|
b 100f
|
|||
|
|
99: // display error message
|
|||
|
|
ldr r0,iAdrszMessError
|
|||
|
|
bl affichageMess
|
|||
|
|
100: // standard end of the program
|
|||
|
|
mov r0, #0 // return code
|
|||
|
|
mov r7, #EXIT // request to exit program
|
|||
|
|
svc 0 // perform system call
|
|||
|
|
iAdrszMessStartPgm: .int szMessStartPgm
|
|||
|
|
iAdrszMessEndPgm: .int szMessEndPgm
|
|||
|
|
iAdrszMessError: .int szMessError
|
|||
|
|
iAdrszMessNoSolution: .int szMessNoSolution
|
|||
|
|
iAdrszCarriageReturn: .int szCarriageReturn
|
|||
|
|
iAdriNumberN: .int iNumberN
|
|||
|
|
iAdriNumberP: .int iNumberP
|
|||
|
|
iAdriNumberN1: .int iNumberN1
|
|||
|
|
iAdriNumberP1: .int iNumberP1
|
|||
|
|
iAdriNumberN2: .int iNumberN2
|
|||
|
|
iAdriNumberP2: .int iNumberP2
|
|||
|
|
|
|||
|
|
iAdrszMessResult: .int szMessResult
|
|||
|
|
iAdrsZoneConv: .int sZoneConv
|
|||
|
|
|
|||
|
|
/******************************************************************/
|
|||
|
|
/* algorithm Tonelli–Shanks */
|
|||
|
|
/******************************************************************/
|
|||
|
|
/* r0 contains number */
|
|||
|
|
/* r1 contains modulus */
|
|||
|
|
/* r0 return root 1 */
|
|||
|
|
/* r1 return root 2 */
|
|||
|
|
computeTonSha:
|
|||
|
|
push {r2-r12,lr}
|
|||
|
|
|
|||
|
|
mov r9,r0 // save number
|
|||
|
|
mov r10,r1 // save modulo p
|
|||
|
|
mov r2,r10
|
|||
|
|
sub r1,r2,#1
|
|||
|
|
lsr r1,r1,#1
|
|||
|
|
bl moduloPuR32
|
|||
|
|
cmp r0,#1
|
|||
|
|
bne 20f
|
|||
|
|
sub r5,r10,#1
|
|||
|
|
mov r6,#1 // s
|
|||
|
|
1:
|
|||
|
|
lsr r5,r5,#1 // div by 2
|
|||
|
|
tst r5,#1 // even ?
|
|||
|
|
addeq r6,#1
|
|||
|
|
beq 1b // and loop
|
|||
|
|
// r5 = q
|
|||
|
|
cmp r6,#1 // s = 1 ?
|
|||
|
|
bne 3f
|
|||
|
|
add r1,r10,#1 // compute root 1
|
|||
|
|
lsr r1,r1,#2 // p + 1 / 4
|
|||
|
|
mov r0,r9 // n
|
|||
|
|
mov r2,r10 // p
|
|||
|
|
bl moduloPuR32
|
|||
|
|
neg r1,r0 // compute root 2 = - root 1
|
|||
|
|
b 100f // and end
|
|||
|
|
3:
|
|||
|
|
mov r7,#3 // z
|
|||
|
|
4:
|
|||
|
|
mov r0,r7
|
|||
|
|
mov r2,r10 // p
|
|||
|
|
sub r1,r2,#1
|
|||
|
|
lsr r1,r1,#1 // power = p - 1 / 2
|
|||
|
|
bl moduloPuR32
|
|||
|
|
cmp r0,#1
|
|||
|
|
addeq r7,#2
|
|||
|
|
beq 4b
|
|||
|
|
cmp r0,#0
|
|||
|
|
addeq r7,#2
|
|||
|
|
beq 4b
|
|||
|
|
mov r0,r7 // z
|
|||
|
|
mov r1,r5 // q
|
|||
|
|
mov r2,r10 // p
|
|||
|
|
bl moduloPuR32
|
|||
|
|
mov r12,r0 // c = z pow q mod p
|
|||
|
|
|
|||
|
|
add r1,r5,#1 // = q +1
|
|||
|
|
lsr r1,r1,#1 // div 2
|
|||
|
|
mov r0,r9 // n
|
|||
|
|
mov r2,r10 // p
|
|||
|
|
bl moduloPuR32
|
|||
|
|
mov r4,r0 // r = n puis (q+1)/2 mod p
|
|||
|
|
|
|||
|
|
mov r0,r9 // n
|
|||
|
|
mov r1,r5 // = q
|
|||
|
|
mov r2,r10 // p
|
|||
|
|
bl moduloPuR32
|
|||
|
|
mov r5,r0 // reuse r5 = t = n pow q mod p
|
|||
|
|
|
|||
|
|
8: // begin loop
|
|||
|
|
cmp r5,#1
|
|||
|
|
beq 10f
|
|||
|
|
mov r0,r5 // t
|
|||
|
|
mov r1,r6 // m
|
|||
|
|
mov r2,r10 // p
|
|||
|
|
bl searchI // search i for t puis 2 puis i = 1 mod p
|
|||
|
|
cmp r0,#-1 // not find -> no solution
|
|||
|
|
beq 20f
|
|||
|
|
mov r9,r0 // i
|
|||
|
|
sub r8,r6,r0 // compute b
|
|||
|
|
sub r8,r8,#1 // m - i - 1
|
|||
|
|
mov r1,#1
|
|||
|
|
lsl r1,r1,r8
|
|||
|
|
mov r0,r12
|
|||
|
|
mov r2,r10 // p
|
|||
|
|
bl moduloPuR32
|
|||
|
|
mov r7,r0 // b = c puis 2 puis 2 puis m-i-1 à verifier
|
|||
|
|
|
|||
|
|
umull r0,r1,r7,r4 // r = r * b mod p
|
|||
|
|
mov r2,r10
|
|||
|
|
bl division32R
|
|||
|
|
mov r4,r2 // r mod p
|
|||
|
|
umull r0,r1,r7,r7
|
|||
|
|
mov r2,r10
|
|||
|
|
bl division32R
|
|||
|
|
mov r12,r2 // c mod p
|
|||
|
|
|
|||
|
|
umull r0,r1,r5,r12
|
|||
|
|
mov r2,r10
|
|||
|
|
bl division32R
|
|||
|
|
mov r5,r2 // t mod p
|
|||
|
|
|
|||
|
|
mov r6,r9 // m = i
|
|||
|
|
b 8b
|
|||
|
|
9:
|
|||
|
|
|
|||
|
|
10:
|
|||
|
|
mov r0,r4 // r0 return root 1
|
|||
|
|
sub r1,r10,r0 // r1 return root 2
|
|||
|
|
cmn r0,#0 // carry à zero roots ok
|
|||
|
|
b 100f
|
|||
|
|
20:
|
|||
|
|
ldr r0,iAdrszMessNoSolution
|
|||
|
|
bl affichageMess
|
|||
|
|
|
|||
|
|
mov r0,#0
|
|||
|
|
mov r1,#0
|
|||
|
|
cmp r0,#0 // carry to 1 No solution
|
|||
|
|
100:
|
|||
|
|
pop {r2-r12,lr} // restaur registers
|
|||
|
|
bx lr // return
|
|||
|
|
/******************************************************************/
|
|||
|
|
/* search i */
|
|||
|
|
/******************************************************************/
|
|||
|
|
// r0 contains t
|
|||
|
|
// r1 contains maxi
|
|||
|
|
// r2 contains modulo
|
|||
|
|
// r0 return i
|
|||
|
|
searchI:
|
|||
|
|
push {r1-r6,lr}
|
|||
|
|
|
|||
|
|
mov r4,r0 // t
|
|||
|
|
mov r6,r1 // m
|
|||
|
|
mov r3,#1 // i
|
|||
|
|
1:
|
|||
|
|
mov r5,#1
|
|||
|
|
lsl r5,r5,r3 // compute 2 power i
|
|||
|
|
|
|||
|
|
mov r0,r4
|
|||
|
|
mov r1,r5
|
|||
|
|
bl moduloPuR32 // compute t pow 2 pow i mod p
|
|||
|
|
cmp r0,#1 // = 1 ?
|
|||
|
|
beq 3f // yes it is ok
|
|||
|
|
add r3,r3,#1 // next i
|
|||
|
|
cmp r3,r6
|
|||
|
|
blt 1b // loop
|
|||
|
|
mov r0,#-1 // not find
|
|||
|
|
b 100f
|
|||
|
|
3:
|
|||
|
|
mov r0,r3 // return i
|
|||
|
|
100:
|
|||
|
|
pop {r1-r6,lr} // restaur registers
|
|||
|
|
bx lr // return
|
|||
|
|
/******************************************************************/
|
|||
|
|
/* display numbers */
|
|||
|
|
/******************************************************************/
|
|||
|
|
/* r0 contains number */
|
|||
|
|
/* r1 contains modulo */
|
|||
|
|
displayEntry:
|
|||
|
|
push {r0-r3,lr}
|
|||
|
|
mov r2,r1 // root 2
|
|||
|
|
ldr r1,iAdrsZoneConv // convert root 1 in r0
|
|||
|
|
bl conversion10S // convert ascii string
|
|||
|
|
ldr r0,iAdrszMessEntry
|
|||
|
|
ldr r1,iAdrsZoneConv
|
|||
|
|
bl strInsertAtCharInc // and put in message
|
|||
|
|
mov r3,r0
|
|||
|
|
mov r0,r2 // racine 2
|
|||
|
|
ldr r1,iAdrsZoneConv
|
|||
|
|
bl conversion10S // convert ascii string
|
|||
|
|
mov r0,r3
|
|||
|
|
ldr r1,iAdrsZoneConv
|
|||
|
|
bl strInsertAtCharInc // and put in message
|
|||
|
|
bl affichageMess
|
|||
|
|
100:
|
|||
|
|
pop {r0-r3,lr} // restaur registers
|
|||
|
|
bx lr // return
|
|||
|
|
iAdrszMessEntry: .int szMessEntry
|
|||
|
|
/******************************************************************/
|
|||
|
|
/* display roots */
|
|||
|
|
/******************************************************************/
|
|||
|
|
/* r0 contains root 1 */
|
|||
|
|
/* r1 contains root 2 */
|
|||
|
|
displayResult:
|
|||
|
|
push {r1-r3,lr}
|
|||
|
|
mov r2,r1 // root 2
|
|||
|
|
ldr r1,iAdrsZoneConv // convert root 1 in r0
|
|||
|
|
bl conversion10S // convert ascii string
|
|||
|
|
ldr r0,iAdrszMessResult
|
|||
|
|
ldr r1,iAdrsZoneConv
|
|||
|
|
bl strInsertAtCharInc // and put in message
|
|||
|
|
mov r3,r0
|
|||
|
|
mov r0,r2 // racine 2
|
|||
|
|
ldr r1,iAdrsZoneConv
|
|||
|
|
bl conversion10S // convert ascii string
|
|||
|
|
mov r0,r3
|
|||
|
|
ldr r1,iAdrsZoneConv
|
|||
|
|
bl strInsertAtCharInc // and put in message
|
|||
|
|
bl affichageMess
|
|||
|
|
100:
|
|||
|
|
|
|||
|
|
pop {r1-r3,lr} // restaur registers
|
|||
|
|
bx lr // return
|
|||
|
|
/********************************************************/
|
|||
|
|
/* Calcul modulo de b puissance e modulo m */
|
|||
|
|
/* Exemple 4 puissance 13 modulo 497 = 445 */
|
|||
|
|
/* */
|
|||
|
|
/********************************************************/
|
|||
|
|
/* r0 nombre */
|
|||
|
|
/* r1 exposant */
|
|||
|
|
/* r2 modulo */
|
|||
|
|
/* r0 return result */
|
|||
|
|
moduloPuR32:
|
|||
|
|
push {r1-r7,lr} @ save registers
|
|||
|
|
cmp r0,#0 @ verif <> zero
|
|||
|
|
beq 90f
|
|||
|
|
cmp r1,#0 @ verif <> zero
|
|||
|
|
moveq r0,#0
|
|||
|
|
beq 90f
|
|||
|
|
cmp r2,#0 @ verif <> zero
|
|||
|
|
moveq r0,#0
|
|||
|
|
beq 90f @
|
|||
|
|
1:
|
|||
|
|
mov r4,r2 @ save modulo
|
|||
|
|
mov r5,r1 @ save exposant
|
|||
|
|
mov r6,r0 @ save base
|
|||
|
|
mov r3,#1 @ start result
|
|||
|
|
|
|||
|
|
mov r1,#0 @ division de r0,r1 par r2
|
|||
|
|
bl division32R
|
|||
|
|
mov r6,r2 @ base <- remainder
|
|||
|
|
2:
|
|||
|
|
tst r5,#1 @ exposant even or odd
|
|||
|
|
beq 3f
|
|||
|
|
umull r0,r1,r6,r3
|
|||
|
|
mov r2,r4
|
|||
|
|
bl division32R
|
|||
|
|
mov r3,r2 @ result <- remainder
|
|||
|
|
3:
|
|||
|
|
umull r0,r1,r6,r6
|
|||
|
|
mov r2,r4
|
|||
|
|
bl division32R
|
|||
|
|
mov r6,r2 @ base <- remainder
|
|||
|
|
|
|||
|
|
lsr r5,#1 @ left shift 1 bit
|
|||
|
|
cmp r5,#0 @ end ?
|
|||
|
|
bne 2b
|
|||
|
|
mov r0,r3
|
|||
|
|
90:
|
|||
|
|
cmn r0,#0 @ no error
|
|||
|
|
100: @ fin standard de la fonction
|
|||
|
|
pop {r1-r7,lr} @ restaur des registres
|
|||
|
|
bx lr @ retour de la fonction en utilisant lr
|
|||
|
|
|
|||
|
|
/***************************************************/
|
|||
|
|
/* division number 64 bits in 2 registers by number 32 bits */
|
|||
|
|
/***************************************************/
|
|||
|
|
/* r0 contains lower part dividende */
|
|||
|
|
/* r1 contains upper part dividende */
|
|||
|
|
/* r2 contains divisor */
|
|||
|
|
/* r0 return lower part quotient */
|
|||
|
|
/* r1 return upper part quotient */
|
|||
|
|
/* r2 return remainder */
|
|||
|
|
division32R:
|
|||
|
|
push {r3-r9,lr} @ save registers
|
|||
|
|
mov r6,#0 @ init upper upper part remainder !!
|
|||
|
|
mov r7,r1 @ init upper part remainder with upper part dividende
|
|||
|
|
mov r8,r0 @ init lower part remainder with lower part dividende
|
|||
|
|
mov r9,#0 @ upper part quotient
|
|||
|
|
mov r4,#0 @ lower part quotient
|
|||
|
|
mov r5,#32 @ bits number
|
|||
|
|
1: @ begin loop
|
|||
|
|
lsl r6,#1 @ shift upper upper part remainder
|
|||
|
|
lsls r7,#1 @ shift upper part remainder
|
|||
|
|
orrcs r6,#1
|
|||
|
|
lsls r8,#1 @ shift lower part remainder
|
|||
|
|
orrcs r7,#1
|
|||
|
|
lsls r4,#1 @ shift lower part quotient
|
|||
|
|
lsl r9,#1 @ shift upper part quotient
|
|||
|
|
orrcs r9,#1
|
|||
|
|
@ divisor sustract upper part remainder
|
|||
|
|
subs r7,r2
|
|||
|
|
sbcs r6,#0 @ and substract carry
|
|||
|
|
bmi 2f @ négative ?
|
|||
|
|
|
|||
|
|
@ positive or equal
|
|||
|
|
orr r4,#1 @ 1 -> right bit quotient
|
|||
|
|
b 3f
|
|||
|
|
2: @ negative
|
|||
|
|
orr r4,#0 @ 0 -> right bit quotient
|
|||
|
|
adds r7,r2 @ and restaur remainder
|
|||
|
|
adc r6,#0
|
|||
|
|
3:
|
|||
|
|
subs r5,#1 @ decrement bit size
|
|||
|
|
bgt 1b @ end ?
|
|||
|
|
mov r0,r4 @ lower part quotient
|
|||
|
|
mov r1,r9 @ upper part quotient
|
|||
|
|
mov r2,r7 @ remainder
|
|||
|
|
100: @ function end
|
|||
|
|
pop {r3-r9,lr} @ restaur registers
|
|||
|
|
bx lr
|
|||
|
|
/***************************************************/
|
|||
|
|
/* ROUTINES INCLUDE */
|
|||
|
|
/***************************************************/
|
|||
|
|
.include "../affichage.inc"
|