TEST DE LUCAS LEHMER

; test de Lucas Lehmer
; recherche des nombres premiers de la forme 2^n-1
; compilation avec masm32 (console)

   .486                                    ; create 32 bit code
   .model flat, stdcall                    ; 32 bit memory model
   option casemap :none                    ; case sensitive
 
    include \masm32\include\windows.inc     ; always first

    include \masm32\include\gdi32.inc
    include \masm32\include\user32.inc
    include \masm32\include\kernel32.inc

    includelib \masm32\lib\gdi32.lib
    includelib \masm32\lib\user32.lib
    includelib \masm32\lib\kernel32.lib


    StdOut PROTO :DWORD
    TestPremier PROTO :DWORD
    TestLucas   PROTO :DWORD
    .data
    outHandle dd 0
    p0 dd 3
    A dd 0
    B dd 0
    max dd 2000   ;valeur maximale a tester
    strFormat     db "%7d ",0
    strTempsCalcul db 13,10,"Temps de calcul %d ms",13,10,0
    strInit db "2^n-1 est premier pour n=",13,10,0
    strMemErr db "pas assez de memoire",0
    
    strSortie db 32 dup (0)
   .code    

start:
     invoke GetStdHandle,STD_OUTPUT_HANDLE
     mov outHandle,eax
      
     invoke GetTickCount
     push eax
   
     mov ebx,max
     add ebx,31
     shr ebx,3
     and ebx,-4
     push ebx
     invoke GlobalAlloc,GMEM_FIXED,ebx
     pop ebx
     or eax,eax
     jz err
     mov A,eax
     shl ebx,1
     invoke GlobalAlloc,GMEM_FIXED,ebx
     or eax,eax
     jz err
     mov B,eax
     invoke StdOut,offset strInit
suivant:
     invoke TestPremier,p0
     or eax,eax
     jz main1
     push esi
     push edi
     invoke TestLucas,p0
     pop edi
     pop esi
     or eax,eax
     jz main1
     invoke wsprintf,offset strSortie,offset strFormat,p0
     invoke StdOut,offset strSortie   
main1:
     add p0,2
     mov eax,max
     cmp p0,eax
     jb suivant

; on a fini
     invoke GetTickCount
     pop ebx
     sub eax,ebx
     invoke wsprintf,offset strSortie,offset strTempsCalcul,eax
     invoke StdOut,offset strSortie 
     invoke ExitProcess,0
     
     
err: invoke StdOut,offset strMemErr
     invoke ExitProcess,0
     
     
StdOut proc chaine: DWORD
      sub esp,4
      mov ecx,chaine
      xor ebx,ebx
SO1:      
      mov al,[ebx+ecx]
      inc ebx
      or al,al
      jnz SO1
      dec ebx
      lea ecx,[ebp-4]
      invoke WriteConsole,outHandle,chaine,ebx,ecx,0
      ret
StdOut endp

TestPremier proc p: DWORD 

     cmp p,4
     jb TP2
     mov ebx,1
TP1: add ebx,2
     xor edx,edx
     mov eax,p
     div ebx
     or edx,edx
     jz compose
     cmp ebx,eax
     jb TP1
TP2: mov eax,1
     ret

compose: 
     xor eax,eax
     ret
TestPremier endp
     



TestLucas proc p: DWORD
     p3 equ [ebp-4] ;Taille de A en octets
     p2 equ [ebp-8]
     p1 equ [ebp-12]
     n  equ [ebp-16]

     cld
     sub esp,16
     mov eax,p
     sub eax,2
     mov n,eax

     pushad
     mov eax,p
     add eax,31
     shr eax,3
     and eax,-4
     mov p3,eax
     mov ecx,p
     and ecx,31
     mov p1,ecx
     mov eax,1
     shl eax,cl
     mov p2,eax
; A=4
     mov edi,A
     mov eax,4
     stosd
     mov ecx,p3
     shr ecx,2
     dec ecx
     jz pas
     xor eax,eax
     rep stosd
 pas:
; B = A*A
     mov ecx,p3
     shr ecx,1
     xor eax,eax
     mov edi,B
     rep stosd

     mov edi,A
     mov ecx,edi
     add ecx,p3

l1:  mov esi,edi
     add esi,4
     cmp esi,ecx
     jnb l2b
     mov ebx,esi
     sub ebx,A
     shl ebx,1
     sub ebx,4
     add ebx,B

l0:  lodsd
     mul dword ptr [edi]
     add [ebx],eax
     adc [ebx+4],edx
     jnb l2
     push ebx
l3:  add ebx,4
     inc dword ptr [ebx+4]
     jz l3
     pop ebx
l2:  add ebx,4
     cmp esi,ecx
     jb l0
     add edi,4
     jmp l1

l2b: push ecx
     mov esi,B
     mov ecx,p3
     shr ecx,1
     mov edi,esi
l2c: lodsd
     rcl eax,1
     stosd
     loop l2c
     pop ecx

     mov esi,A
     mov edi,B
     xor ebx,ebx
l2d: lodsd
     mul eax
     shr ebx,1
     adc [edi],eax
     adc [edi+4],edx
     rcl ebx,1
     add edi,8
     cmp esi,ecx
     jb l2d

; B = B - 2
     mov ebx,2
     mov edi,B
     cmp [edi],ebx
     jnb l4b
     xor eax,eax
     mov ecx,p3
     shl ecx,1
     sub ecx,4

     add edi,4
     repe scasb
     jnz l4
l5:  mov eax,p2
     mov edi,B
     add edi,p3
     add [edi-4],eax
     inc ebx
l4:  mov edi,B

l4b: sub [edi],ebx
     jnb l7
l6:  add edi,4
     dec dword ptr [edi]
     cmp dword ptr [edi],-1
     jz l6
;A = B mod 2^p -1

l7:
     mov ecx,p1
     mov esi,B
     add esi,p3
     sub esi,4
     mov edi,A
     lodsd
     mov edx,edi
     add edx,p3
l10:
     mov ebx,eax
     lodsd
     shrd ebx,eax,cl
     mov [edi],ebx
     add edi,4
     cmp edi,edx
     jb l10
     mov ecx,p2
     dec ecx
     sub esi,p3
     and [esi-4],ecx
     mov esi,B
     mov edi,A
     mov ecx,p3
     shr ecx,2
     clc
 l11:
     lodsd
     adc eax,[edi]
     stosd
     loop l11
     sub eax,p2
     jb l12
     mov [edi-4],eax
     mov esi,A
     sub esi,4
l13: add esi,4
     inc dword ptr [esi]
     jz l13

l12:
     dec dword ptr n
     jnz pas

;test si le reste est nul
     mov edi,A
     mov ecx,p3
     shr ecx,2
     dec ecx
     jz l21
     mov eax,-1
     repe scasd
     jnz l20
l21:
     mov eax,p2
     dec eax
     scasd
     jz premier

l20:
     mov ecx,p3
     mov edi,A
     xor eax,eax
     repe scasb
     jz premier

     popad
     mov eax,0
     ret

premier:
     popad
     mov eax,1
     ret

TestLucas endp


 
end start