1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
/*
* prime.S - check if a number is prime
* x86 assembler demonstration program
* use with GNU AS
*
* written by Jan Engelhardt, 2003-2006
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the WTF Public License version 2 or
* (at your option) any later version.
*/
.intel_syntax noprefix;
.section .rodata;
.L_LC0:
.string "%u is a prime\n";
.L_LC1:
.string "%u is not a prime (split by %u)\n";
.text;
.global main;
.type main, @function;
main:
push ebp;
mov ebp, esp;
push dword ptr [ebp+12];
push dword ptr [ebp+8];
call GetPrime;
add esp, 8;
mov edi, eax;
mov esi, eax;
call IsPrime;
test eax, eax;
push eax;
jne .L_main_noprime;
.L_main_isprime:
push edi;
push offset flat:.L_LC0;
call printf;
add esp, 8;
jmp .L_main_end;
.L_main_noprime:
push eax;
push edi;
push offset flat:.L_LC1;
call printf;
add esp, 12;
.L_main_end:
pop eax;
leave;
ret;
.globl GetPrime;
.type GetPrime, @function;
GetPrime:
push ebp;
mov ebp, esp;
cmp dword ptr [ebp+8], 2;
jae .L_GetArgs_run;
mov eax, 13;
jmp .L_GetArgs_end;
.L_GetArgs_run:
mov ebx, dword ptr [ebp+12];
push 0;
push 0;
push dword ptr [ebx+4];
call strtoul;
add esp, 12;
.L_GetArgs_end:
leave;
ret;
/*
* In an attempt to improve IsPrime2 further, this function only runs up to
* sqrt(N) rather than N/2. This is possible since if you split the number in
* two integral factors, the maximum value of either (see them independently)
* can be sqrt(N):
*
* Imagine we take 100 as the number to check:
* 100 = x * y |T y strives to 0, while y >= x
* => 100 = x ** 2 |sqrt()
* <=> x = 10
*
* Checking a prime near 2^31 thus only takes about 3 secs instead on a modest
* CPU. (15+ secs for IsPrime2 on *that* modest CPU.)
*/
.globl IsPrime;
.type IsPrime, @function
IsPrime:
push ebp;
mov ebp, esp;
sub esp, 8;
/* Early case exclusion */
cmp esi, 3;
jbe .L_IsPrime_IsPrime;
mov ecx, 2;
test si, 1;
je .L_IsPrime_NoPrime;
cmp esi, 7;
jbe .L_IsPrime_IsPrime;
/* Set up FPU to round up */
fstcw word ptr [ebp-8];
mov ax, word ptr [ebp-8];
and ax, 0xF0FF;
or ax, 0x0B00;
mov word ptr [ebp-8], ax;
fldcw /* word ptr */ [ebp-8];
/* Maximum count is ceil(sqrt(esi)) */
mov dword ptr [ebp-4], esi;
fild dword ptr [ebp-4];
fsqrt;
fistp dword ptr [ebp-4];
mov ebx, dword ptr [ebp-4];
/* Iterative loop */
cmp ebx, 3;
jb .L_IsPrime_IsPrime;
mov ecx, 3;
.L_IsPrime_loop:
mov eax, esi;
xor edx, edx;
div ecx;
test edx, edx;
je .L_IsPrime_NoPrime;
add ecx, 2;
cmp ecx, ebx;
jbe .L_IsPrime_loop;
.L_IsPrime_IsPrime:
add esp, 8;
mov eax, 0;
leave;
ret;
.L_IsPrime_NoPrime:
add esp, 8;
mov eax, ecx;
leave;
ret;
|
