287 lines
8.5 KiB
Plaintext
287 lines
8.5 KiB
Plaintext
/* ARM assembly Raspberry PI */
|
|
/* program testmiller.s */
|
|
|
|
/* for constantes see task include a file in arm assembly */
|
|
/************************************/
|
|
/* Constantes */
|
|
/************************************/
|
|
.include "../constantes.inc"
|
|
|
|
.equ NBDIVISORS, 2000
|
|
|
|
//.include "../../ficmacros32.inc" @ use for developper debugging
|
|
/*******************************************/
|
|
/* Initialized data */
|
|
/*******************************************/
|
|
.data
|
|
szMessStartPgm: .asciz "Program 32 bits start \n"
|
|
szMessEndPgm: .asciz "Program normal end.\n"
|
|
szMessErrorArea: .asciz "\033[31mError : area divisors too small.\n"
|
|
szMessPrime: .asciz " is prime !!!.\n"
|
|
szMessNotPrime: .asciz " is not prime !!!.\n"
|
|
szCarriageReturn: .asciz "\n"
|
|
|
|
.align 4
|
|
iGraine: .int 123456
|
|
/*******************************************/
|
|
/* UnInitialized data */
|
|
/*******************************************/
|
|
.bss
|
|
.align 4
|
|
sZoneConv: .skip 24
|
|
/*******************************************/
|
|
/* code section */
|
|
/*******************************************/
|
|
.text
|
|
.global main
|
|
main: @ program start
|
|
ldr r0,iAdrszMessStartPgm @ display start message
|
|
bl affichageMess
|
|
ldr r4,iStart @ start number
|
|
ldr r5,iLimit @ end number
|
|
tst r4,#1
|
|
addeq r4,#1 @ start with odd number
|
|
1:
|
|
mov r0,r4
|
|
ldr r1,iAdrsZoneConv
|
|
bl conversion10 @ decimal conversion
|
|
ldr r0,iAdrsZoneConv
|
|
bl affichageMess
|
|
mov r0,r4
|
|
bl isPrimeMiller @ test miller rabin
|
|
cmp r0,#0
|
|
beq 2f
|
|
ldr r0,iAdrszMessPrime
|
|
bl affichageMess
|
|
b 3f
|
|
2:
|
|
ldr r0,iAdrszMessNotPrime
|
|
bl affichageMess
|
|
3:
|
|
add r4,r4,#2
|
|
cmp r4,r5
|
|
ble 1b
|
|
|
|
ldr r0,iAdrszMessEndPgm @ display end message
|
|
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
|
|
iAdrszCarriageReturn: .int szCarriageReturn
|
|
iAdrsZoneConv: .int sZoneConv
|
|
iAdrszMessPrime: .int szMessPrime
|
|
iAdrszMessNotPrime: .int szMessNotPrime
|
|
iStart: .int 4294967270
|
|
iLimit: .int 4294967295
|
|
|
|
|
|
/***************************************************/
|
|
/* check if a number is prime test miller rabin */
|
|
/***************************************************/
|
|
/* r0 contains the number */
|
|
/* r0 return 1 if prime 0 else */
|
|
@2147483647
|
|
@4294967297
|
|
@131071
|
|
isPrimeMiller:
|
|
push {r1-r6,lr} @ save registers
|
|
cmp r0,#1 @ control 0 or 1
|
|
movls r0,#0
|
|
bls 100f
|
|
cmp r0,#2 @ control = 2
|
|
moveq r0,#1
|
|
beq 100f
|
|
tst r0,#1
|
|
moveq r0,#0 @ even
|
|
beq 100f
|
|
mov r1,#5 @ loop number
|
|
bl testMiller
|
|
100:
|
|
pop {r1-r6,pc}
|
|
/***************************************************/
|
|
/* test miller rabin algorithme wikipedia */
|
|
/* unsigned */
|
|
/***************************************************/
|
|
/* r0 contains number */
|
|
/* r1 contains parameter */
|
|
/* r0 return 1 if prime 0 if composite */
|
|
testMiller:
|
|
push {r1-r9,lr} @ save registers
|
|
mov r4,r0 @ N
|
|
mov r7,r1 @ loop maxi
|
|
sub r3,r0,#1 @ D
|
|
mov r2,#2
|
|
mov r6,#0 @ S
|
|
1: @ compute D * 2 power S
|
|
lsr r3,#1 @ D= D/2
|
|
add r6,r6,#1 @ increment S
|
|
tst r3,#1 @ D even ?
|
|
beq 1b
|
|
2:
|
|
mov r8,#0 @ loop counter
|
|
sub r5,r0,#3
|
|
3:
|
|
mov r0,r5
|
|
bl genereraleas
|
|
add r0,r0,#2 @ alea (entre 2 et n-1)
|
|
mov r1,r3 @ exposant = D
|
|
mov r2,r4 @ modulo N
|
|
bl moduloPuR32
|
|
cmp r0,#1
|
|
beq 5f
|
|
sub r1,r4,#1 @ n -1
|
|
cmp r0,r1
|
|
beq 5f
|
|
sub r9,r6,#1 @ S - 1
|
|
4:
|
|
mov r2,r0
|
|
umull r0,r1,r2,r0 @ compute square
|
|
mov r2,r4 @ and compute modulo N
|
|
bl division32R2023
|
|
mov r0,r2
|
|
cmp r0,#1
|
|
moveq r0,#0 @ composite
|
|
beq 100f
|
|
sub r1,r4,#1 @ n -1
|
|
cmp r0,r1
|
|
beq 5f
|
|
subs r9,r9,#1
|
|
bge 4b
|
|
mov r0,#0 @ composite
|
|
b 100f
|
|
5:
|
|
add r8,r8,#1
|
|
cmp r8,r7
|
|
blt 3b
|
|
mov r0,#1 @ prime
|
|
100:
|
|
pop {r1-r9,pc}
|
|
/********************************************************/
|
|
/* 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-r6,lr} @ save registers
|
|
cmp r0,#0 @ control <> zero
|
|
beq 100f
|
|
cmp r2,#0 @ control <> zero
|
|
beq 100f
|
|
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 r0,r1 by r2
|
|
bl division32R2023
|
|
mov r6,r2 @ base <- remainder
|
|
2:
|
|
tst r5,#1 @ exposant even or odd
|
|
beq 3f
|
|
umull r0,r1,r6,r3 @ multiplication base
|
|
mov r2,r4 @ and compute modulo N
|
|
bl division32R2023
|
|
mov r3,r2 @ result <- remainder
|
|
3:
|
|
umull r0,r1,r6,r6 @ compute base square
|
|
mov r2,r4 @ and compute modulo N
|
|
bl division32R2023
|
|
mov r6,r2 @ base <- remainder
|
|
|
|
lsr r5,#1 @ left shift 1 bit
|
|
cmp r5,#0 @ end ?
|
|
bne 2b
|
|
mov r0,r3
|
|
100:
|
|
pop {r1-r6,pc}
|
|
|
|
/***************************************************/
|
|
/* division number 64 bits in 2 registers by number 32 bits */
|
|
/* unsigned */
|
|
/***************************************************/
|
|
/* 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 */
|
|
division32R2023:
|
|
push {r3-r6,lr} @ save registers
|
|
mov r4,r2 @ save divisor
|
|
mov r5,#0 @ init upper part divisor
|
|
mov r2,r0 @ save dividende
|
|
mov r3,r1
|
|
mov r0,#0 @ init result
|
|
mov r1,#0
|
|
mov r6,#0 @ init shift counter
|
|
1: @ loop shift divisor
|
|
cmp r5,#0 @ upper divisor <0
|
|
blt 2f
|
|
cmp r5,r3
|
|
cmpeq r4,r2
|
|
bhs 2f @ new divisor > dividende
|
|
lsl r5,#1 @ shift left one bit upper divisor
|
|
lsls r4,#1 @ shift left one bit lower divisor
|
|
orrcs r5,r5,#1 @ move bit 31 lower on upper
|
|
add r6,r6,#1 @ increment shift counter
|
|
b 1b
|
|
2: @ loop 2
|
|
lsl r1,#1 @ shift left one bit upper quotient
|
|
lsls r0,#1 @ shift left one bit lower quotient
|
|
orrcs r1,#1 @ move bit 31 lower on upper
|
|
cmp r5,r3 @ compare divisor and dividende
|
|
cmpeq r4,r2
|
|
bhi 3f
|
|
subs r2,r2,r4 @ < sub divisor from dividende lower
|
|
sbc r3,r3,r5 @ and upper
|
|
orr r0,r0,#1 @ move 1 on quotient
|
|
3:
|
|
lsr r4,r4,#1 @ shift right one bit upper divisor
|
|
lsrs r5,#1 @ and lower
|
|
orrcs r4,#0x80000000 @ move bit 0 upper to 31 bit lower
|
|
subs r6,#1 @ decrement shift counter
|
|
bge 2b @ if > 0 loop 2
|
|
|
|
100:
|
|
pop {r3-r6,pc}
|
|
|
|
|
|
/***************************************************/
|
|
/* Generation random number */
|
|
/***************************************************/
|
|
/* r0 contains limit */
|
|
genereraleas:
|
|
push {r1-r4,lr} @ save registers
|
|
ldr r4,iAdriGraine
|
|
ldr r2,[r4]
|
|
ldr r3,iNbDep1
|
|
mul r2,r3,r2
|
|
ldr r3,iNbDep1
|
|
add r2,r2,r3
|
|
str r2,[r4] @ save seed for next call
|
|
cmp r0,#0
|
|
beq 100f
|
|
mov r1,r0 @ divisor
|
|
mov r0,r2 @ dividende
|
|
bl division
|
|
mov r0,r3 @ résult = remainder
|
|
|
|
100: @ end function
|
|
pop {r1-r4,pc} @ restaur registers
|
|
iAdriGraine: .int iGraine
|
|
iNbDep1: .int 0x343FD
|
|
iNbDep2: .int 0x269EC3
|
|
/***************************************************/
|
|
/* ROUTINES INCLUDE */
|
|
/***************************************************/
|
|
.include "../affichage.inc"
|