第四章 質數 (1) 兼談動態連結程式庫


心路歷程

寫個程式還有「心路歷程」?真是見鬼了。但是不騙你們,我真的有些想法。起源是最近寫組合語言的人真的越來越少了,連大陸的 Aogo 彙編小站 ( 大陸稱組合語言為彙編語言 ) 的討論區都冷清的可以,更別說台灣了。甚至還有人說,組合語言已死。雖然有點言過其實,但是大家一定也都同意,組合語言能做得到而高階語言做不到的事,幾乎是沒有了。大家也都同意,高階語言能做得到的,組合語言一定能做得到。那現在組合語言還有什麼優勢呢?或許在複雜的計算過程,還有些許的優勢,不過也可能很快就沒了。

最近幾年 ( 民國 106 年,西元 2017 年左右 ),許多國家都想辦法在中小學堙A把程式設計列為學生學習的項目,我國政府也想推行這政策。但是以小木偶這數十年來的觀察,想要學習程式設計,非得要具有清晰的邏輯以及基本的數學為基礎;但這還不是非常重要的,更重要的是要有堅毅的耐心。前面兩個條件,許多智商高的人,輕而易舉就能做到;但是講到耐心,就不是一般人能做到了。尤其是在歷屆政府的政策「鼓舞」下,希望能減低下一代的壓力,於是造成能夠吃苦耐勞、能有恆心有毅力的年輕人已經越來越少。這種氛圍之下,能推廣程式設計,我看是很難。

好了,發牢騷就此打住。小木偶打算在接下來的幾章內,記錄小木偶撰寫將某一正整數分解成質因數乘積的過程。在這過程內,會用到幾個副程式,例如,求小於某正整數的質數、求一正整數的平方根、判斷一正整數是否為質數等。小木偶覺得它們挺管用的,因此把它們製作成動態連結程式庫 ( dynamic-link library )。因此這一章的標題就變成「質數 (1) 兼談動態連結程式庫」,看似兩個無關的主題,卻合在一起了。


原理

Win64 的動態結程式庫

事實上,在 Win64 系統內,想要製作動態連結程式庫,和在 Win32 系統幾乎一樣。動態連結程式庫可以看成是一些副程式的集合或是某些資源的集合。這些副程式或是資源,都是被其他程式所呼叫或使用,所以不需要建立視窗,也不需要訊息迴圈或終結視窗的程式碼。每個動態連結程式庫的格式都固定的,底下就先來看看動態連結程式庫的樣子:

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
       OPTION  CASEMAP:NONE
        OPTION  WIN64:7

;假如需要用到包含檔,那麼可以在此處定義
INCLUDE         WINDOWS.INC
INCLUDELIB      KERNEL32.LIB

;*****************************************************************************************
.DATA?
;此處定義未初始化的變數

;*****************************************************************************************
.CODE
;-----------------------------------------------------------------------------------------
;進入/離開副程式的進入點
DLLEntry        PROC    hInstance,dwReason,dwReserved
                mov     rax,dwReason
.IF rax==DLL_PROCESS_ATTACH
        ;保存hInstance
        ;初始化動態連結程式庫需要的各種資源
   .IF  ;初始化成功
                mov     rax,TRUE
   .ELSE
                mov     rax,FALSE
   .ENDIF
.ELSEIF rax==DLL_THREAD_ATTACH
        ;釋放動態連結程式庫使用的資源
.ELSEIF rax==DLL_THREAD_DETACH
        ;為新的執行緒分配資源
.ELSEIF rax==DLL_PROCESS_DETACH
        ;為執行緒釋放資源
.ENDIF
DLLEntry        ENDP
;進入/離開副程式結束
;-----------------------------------------------------------------------------------------
SubRoutine1     PROC    Param1,Param2   ;此處為第一個副程式的參數
                        ;此處為第一個副程式的程式碼
                ret
SubRoutine1     ENDP
;-----------------------------------------------------------------------------------------
SubRoutine2     PROC    ParamA,ParamB   ;此處為第二個副程式的參數
                        ;此處為第二個副程式的程式碼
                ret
SubRoutine2     ENDP
;*****************************************************************************************
END             DLLEntry

上面的動態連結程式庫模板,是由一個稱為 DLLEntry 副程式及兩個副程式組成,DLLEntry 副程式稱為「進入/離開副程式」,每個動態連結程式庫都會有這個副程式,它的名稱其實可以任意訂定,只要符合組譯器的命名規則即可。雖然「進入/離開副程式」也叫副程式,但是並不像其他副程式一樣是讓其他程式呼叫的,而是作業系統載入或卸載動態連結程式庫時,由作業系統呼叫,讓作業系統有機會做一些事前處理或是離開時作一些清除動作用的。「進入/離開副程式」有固定的格式執行一些動作,假如不需要做這些動作的話,「進入/離開副程式」也可以只是把 1 存入 RAX 堙A然後把 1 當成返回值就跳離。

質數表

要把所有質數列出來成一張表,這是不可能的。早在西元前三百多年,古希臘數學家歐幾里德就已經證明了「有無限多個質數」( 見昌爸工作坊 )。既然建立無法有無限多個的質數表格,只能退而求其次,只要能建立小於某個正整數的質數即可。而 64 位元的 CPU,所能表示的正整數最大為 264-1,所以小木偶就想寫出一副程式,能列出小於 264-1 的所有質數。( 各位看倌,乍看之下,會以為這個數不大,但實際算過後得知,264-1=18446744073709551615≒1.8447×1019,其實是很大的數,共有 20 位數。)

在網路上查詢可以知道,有許多方法能計算質數表,小木偶使用 Eratosthenes 篩選法。這個方法的原理很簡單,底下簡述這種方法。假設想要列出小於 N 的質數,可以先由 2 開始把小於 N 的正整數一一列出,然後把 2 的倍數刪去。之後再由 2 開始找到第一個沒被刪去的數,3,即為質數,再把 3 的倍數刪去。刪去之後再由 3 開始,找到第一個沒被刪去的數,5,這就是下一個質數,再刪去 5 的倍數。然後由 5 開始,找到下一個沒被刪去的數,7,7 就是下個質數……如此循環不已,直到 N 為止。結果如下圖:

Eratosthenes 篩選法

如果用 Eratosthenes 篩選法當成演算法,寫成電腦程式來列出質數的步驟,大致就是:①先配置 N 個元素的陣列。②設一個兩層的迴圈,第一層迴圈由 2 開始,到 N 結束,每一次都先檢查此數是否已被刪除,如果刪除,就不進入第二層迴圈,直接跳到第一層迴圈的下一個數繼續。如果沒被刪除,表示此數為質數,然後進入第二層迴圈。③第二層迴圈由該數開始,直到 N 結束,主要目的是檢查輪到的數是否為該數的倍數,如果是則刪除。④結束。

Eratosthenes 篩選法的原理雖然簡單,但是如果 N 很大時,缺點就會顯現出來,那就是:

  1. 要花費大量記憶體。如果你要求 1000 以內的質數,需要先配置 1KB 的記憶體,大概不致有什麼問題;但是如果是要求一億以內的質數,就得需要 100MB 的記憶體。
  2. 速度太慢。以一億為例,刪去 2 的倍數時,要重複迴圈五千萬次,刪去 3 的倍數時要重複三千三百萬次…,其實是很沒有效率的。

因此有以下的改進方法。

改進建立質數表的方法

底下說明建立質數表時,如何增進速度。因為底下的說明,太過於瑣碎,需配合原始碼,相互閱讀,大約才能了解。

①以一個位元代表一個奇數

用組合語言,就能彌補第一個缺點,因為組合語言很擅長處理位元,因此小木偶改用以一位元代替一個數,而不是用一個位元組表示一個數。另外,偶數中就只有 2 是質數,故乾脆額外處理 2,然後把偶數全部刪去,這樣的話一個位元組就能代表 16 個數了。也就是說,第零個位元組的第零位元代表 3、第一位元代表 5、第二位元代表 7、第三位元代表 9…,見下圖最底下一行的白色字。因此如果是第 P 個位元組的第 Q 個位元,所代表的數可以輕易算出是「16P+2Q+3」,當然 P、Q 均從 0 開始,Q 必須是 0 到 7 的整數。例如,第 3 個位元組的第 4 個位元,代表 59。反過來,如果要求某個奇數,X,在第幾個位元組 ( 以 P 表示 ) 堶悸熔譬X個位元 ( 以 Q 表示 ),可以經由下面步驟算出:

  P=( X-3 )÷16 的商數
  Q=( X-3 )÷16 的餘數,再除以 2

配置記憶體時,一般是呼叫 GlobalAlloc,可以用 GPTR 參數使所配置的記憶體內容均設為 0。因此小木偶設定:若某個位元為 0,表示此位元所代表的數為質數;若某個位元為 1,表示此位元所代表的數不是質數。一開始,先假定所有的數均為質數,故每個位元都為 0,但如果某數是 2 的倍數,或其他數的倍數,表示此數可以被該數整除,就不是質數,應將此位元設為 1。例如 15 可被 3 整除,不是質數,該位元應設為一。不過 2 已經刪除,所以從 3 開始。參考下圖,您應該可以發現,距離 3 往右三個位元處的 9 是 3 的倍數,此位元應該設為一;再往右三個位元的 15 也是 3 的倍數,此位元也應設為一……。如果事先把這些位元設為一,表示刪除的話,將來就可以減少許多計算。

既然如此,何不一開始就乾脆連 5 和 7 的倍數,也先刪除。也就是說,在配置記憶體之後,就先把 3、5、7 的倍數所代表的位元設為 1,這樣就可以減少更多計算。參考下圖,您會可以發現,刪除 5 的倍數時,是五個一數,該位元就是代表 5 的倍數;刪除 7 的倍數時,是七個一數,該位元就是代表 7 的倍數。當然,在刪除 5 倍數時,有些可能在刪除 3 的倍數時,就已經刪去了,例如 15;同樣的事,也發生在刪除 7 的倍數時。綜合上述結果,第零∼四個位元組的數值分別是 48H、9AH、0A5H、0CDH、0B2h,如下圖所示。

如果想要在計算前,事先刪除 3、5、7 的倍數,再加上每 8 個數組成一個位元組,至少需要 3×5×7×8 個位元,恰好是 105 個位元組。意思是,每 105 個位元組會重複出現。因此可以先定義這 105 個位元組的資料,然後在配置記憶體之後,把這 105 個位元組的資料,以組合語言 REP MOVSB 指令,重複的填入配置完成的記憶體內,就立刻刪除了 2、3、5、7 的倍數。但是,要注意的是,第零個位元組並不會重複,因為代表 3、5、7 的位元沒被刪除,此三位元為 0,是質數。而其後的 3 個位元組,會在 105 個位元組之後重複出現。小木偶以筆算花了一些時間得到結果,後來想想筆算很可能算錯,後來還是寫了個程式做這件事。最後這 105 個位元組是可查閱

②刪去質數的倍數時,從該質數的平方開始刪除

除了上面的方法之外,還有幾個方法可以減少計算次數。首先,找到某個質數後,要刪去該質數的倍數時,可以從該質數的平方開始刪除,因為前面的倍數都已經刪去。例如要刪去 11 的倍數時,3×11、5×11、9×11 必定都已經在刪除 3、5 的倍數時刪去了,所以從 11×11 開始刪除即可。那麼,要怎麼找到質數的平方呢?如果您仔細觀察上圖,會發現:

32 所代表的位元,距離 3 有  3 個位元遠。 3 可以寫成 1×3
52 所代表的位元,距離 5 有 10 個位元遠。10 可以寫成 2×5
72 所代表的位元,距離 7 有 21 個位元遠。21 可以寫成 3×7
92 所代表的位元,距離 9 有 36 個位元遠。36 可以寫成 4×9

從前面幾個質數的平方,就能看出來一些規律。質數的平方距離該質數,有 ( n×質數 ) 個位元那麼遠,n 是從一開始的正整數,它代表由三開始的第幾個奇數。或者換一方式思考,我們可以把所配置的記憶體,看成由 0 開始到 100 或 1000 或 10000 個位元所組成的,並想成使位元組的界限消失,亦即不使八個位元變成一個位元組。第零個位元就代表 3,第一個位元就代表 5……第八個位元代表 19,第九個位元代表 21……那麼,n 就是所配置的記憶體中的第幾個位元再加一。R11 暫存器,就代表這個數值,在原始碼的第 153 行就定義了 R11 從 4 開始,而第 154∼160 行,就是計算出從某個質數開始,到質數的平方有多少個位元。

③以加法代替乘法,刪除質數的倍數

每個質數的倍數距離下一個倍數,有多少位元?您也可以從上圖觀察。:

3 距離  9 有 3 個位元,15 距離  9 有 3 個位元,21 距離 15 有 3 個位元……
5 距離 15 有 5 個位元,15 距離 25 有 5 個位元,25 距離 35 有 5 個位元……
7 距離 21 有 7 個位元,21 距離 35 有 7 個位元,35 距離 49 有 7 個位元……

換句話說,質數的倍數距離下一個倍數的位元數,距離和質數大小一樣。意思是,我們可以以加法累進刪除質數的倍數,而不用乘法,因為乘法速率較加法慢。在原始碼的第 167 行就已計算完成,每個倍數距離下一個倍數的位元數,記錄在 R8:R9 堙C因為記憶體中,仍以位元組內的第幾個位元表示,所以程式 R8:R9 的意思,質數的倍數距離下一個倍數有 R8 個位元組再加上 R9 位元這麼遠。

④篩選到根號 N 就可以了

還有一個可以加快 Eratosthenes 篩選法的方法。如果想要把小於 N 的質數列出來,以 Eratosthenes 篩選法篩選,只要篩選到根號N就可以了。例如要列出 100 以下的質數,只要篩選掉 10 以下的質數倍數就可以了。在刪除 2 的倍數時,必定會刪除 2×11、2×13、2×17…;在刪除 3 的倍數時,也會刪除 3×11、3×13、3×17…;而且兩個都大於 10 的數相乘所得的乘積一定超過 100,例如 11×11=121。綜觀上面的理由,就可得知,只需刪除到根號N就可以了。

一數的平方根可以用 FPU 指令,FSQRT 計算,但是這個指令只能計算小於 9223372036854775807 ( =263-1 ) 的平方根,超過這個數,只好用牛頓法求到整數位。有關牛頓法求一數之平方根,可以參考大陸博客園的「一個 Sqrt 函數引發的血案」文章。小木偶已經撰寫好一個副程式,square_root,可供呼叫。以 square_root 計算使用者所輸入數值的平方根,並將其轉變成 SqrtByte 及 SqrtBit。這兩個變數,分別代表所輸入數值的平方根,在所配置記憶體的第 SqrtByte 位元組的第 SqrtBit 位元 ( 見程式碼第 107∼119 行 )。在程式碼的第 153 行,設定 R11 為四,就是開始刪除 11 的倍數,11 的倍數刪完,就輪到 13 的倍數,13 的倍數刪完,就輪到 17 的倍數……直到第 188∼191 行,就是檢查是否已經刪除到根號N了。

判斷一正整數是否為質數

既已計算出質數列表,要判斷某個正整數是否為質數,就不是件難事了。只要以該正整數當做被除數,把小於該正整數的質數當做除數,做除法運算,如能整除,那麼該正整數就不是質數;如果所有小於該正整數的質數,都不能整除該正整數,那麼這個正整數就是質數。不過為了加速,可以不需要把所有質數列出來,才做除法運算。小木偶的做法是,只要一找到質數,就立刻相除。這樣就會使速率變快很多。因為只需判斷是否為質數即可,另外也可指出是哪一個質數能整除該正整數。


原始碼

講了這麼多,這一章要製作三個副程式:square_root、find_prime、is_prime,其功用分別是求出某數的平方根、求出小於或等於某正整數的所有質數、判斷某正整數是否為質數。小木偶想,或許可以把這三個副程式,包裝成一個動態連結程式庫 ( DLL ),名稱為「PRIMEDLL.ASM」。而第一個副程式,square_root,較為簡單所以不特別說明。

小於或等於某正整數的質數列表:find_prime

副程式,find_prime,是用來列出所有小於某個正整數的質數,其原型為:

find_prime  PROTO   num:QWORD,pMemPrm:LPSTR

它有兩個參數,num、pMemPrm。第一個參數,num,為正整數,傳給 find_prime 副程式,使之計算小於或等於 num 的質數。而其結果存於第二個參數,pMemPrm,所指的記憶體區塊堙C這塊記憶體,必須由主程式配置好,並將其位址,pMemPrm,傳給 find_prime。pMemPrm 所指的記憶體區塊長度與 num 之值有關,為個位元組,並且一開始,每個位元組都應該是 0,因此如果是呼叫 GlobalAlloc 來建立 pMemPrm 記憶體區塊,應使用 GPTR 參數。

判斷某正整數是否為質數:is_prime

副程式,is_prime,的原型是

is_prime    PROTO   num:QWORD

她只有一個參數,num,num 為正整數。is_prime 會計算 num 是否為質數,返回時,若 RAX=0,表示 num 為 0 或 1;若 RAX=1,表示 num 為質數;若 RAX 為其他數,表示 num 不是質數,而 RAX 為其最小之質因數。

原始碼

底下是 PRIMEDLL.ASM 的原始碼:

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
;此程式只包含三個副程式,為64位元版本
;1.square_root求某數平方根
;2.find_prime:於記憶體中,列出小於或等於某正整數的質數。
;3.is_prime:判斷某正整數是否為質數
        OPTION  CASEMAP:NONE
        OPTION  WIN64:7

INCLUDELIB      KERNEL32.LIB
GlobalAlloc     PROTO   :QWORD,:QWORD
GlobalFree      PROTO   :QWORD
;*****************************************************************************************
.CODE
;-----------------------------------------------------------------------------------------
DLLEntry        PROC    hInstance,dwReason,dwReserved
                mov     rax,1
                ret
DLLEntry        ENDP
;-----------------------------------------------------------------------------------------
;求num的平方根,把平方根的整數部份存於RAX後返回。若num≦7fffffffffffffffh,用NDP(FPU)運
;算;若超過,NDP無法處理改用牛頓法計算(程式碼位於big_number到sqrt_root_ok之間)
;呼叫前後不變的暫存器:R9∼R15、RBX、RSI、RDI
;輸入:num-求num之平方根,num為無號數
;輸出:RAX=根號num之整數部分
square_root     PROC    num:QWORD
                mov     rdx,7fffffffffffffffh
                cmp     rcx,rdx
                ja      big_number
                finit
                fild    num
                fsqrt
                fistp   num
                mov     rax,num
                jmp     sqrt_root_ok
big_number:     mov     r8,3719550786  ;xn=3719550786
next_time:      sub     rdx,rdx
                mov     rax,num
                div     r8
                add     rax,r8
                shr     rax,1
                cmp     rax,r8
                je      sqrt_root_ok
                mov     r8,rax
                jmp     next_time
sqrt_root_ok:   ret
square_root     ENDP
;-----------------------------------------------------------------------------------------
;find_prime副程式用來搜尋小於或等於正整數num的所有質數,返回時把結果記錄在pMemPrm所指的位
;址。pMemPrm所指記憶體區塊,由父程式配置,長度為(num/16+20h)位元組。(因為偶數不須佔用位元
;,且每個數佔用一位元,故8個奇數佔用一個元組,故除以16)。
;呼叫前後,不變的暫存器:R12∼R15、RBX、RSI、RDI
;輸入:num-一正整數,find_prime會計算小於此正整數的所有質數
;   pMemPrm-記憶體區塊位址,其內容應全為0,find_prime計算後,若某一位元為0,表示該位元
;        所代表的數為質數;若某位元為1,該位元所代表的數不是質數。第P位元組的第Q個
;        位元,所代表的數=16P+2Q+3,P由0開始,0≦Q≦7。
;輸出:RAX-小於或等於正整數num的質數個數
find_prime      PROC    USES rsi rdi num:QWORD,pMemPrm:QWORD
                LOCAL   MaxByte:QWORD,MaxBit:QWORD      ;最大位元數
                LOCAL   SqrtByte:QWORD,SqrtBit:QWORD    ;num的平方根在第幾個位元組內的第幾
;使用技巧:                                             ;個位元
;1.pMemPrm所指的記憶體區塊內的每個位元代表一個奇數,亦即已刪除2的倍數
;2.在標號again:處及其後數行,載入一個105位元組的字串,就能刪除3、5、7的倍數
;3.由pMemPrm所指之記憶體區塊開始,看哪個位元為0,即為質數;1為合數
;4.第零個位元組的第零、一、二位元分別代表3、5、7,第三個位元是9,在此副程式的前幾行程式碼就
; 已被刪除,故從第四個位元開始,此位元代表11,開始刪除11的倍數。
;5.但是刪除時,3*11、5*11、7*11、9*11都已經刪除過了,換句話說只要從11*11始就可以了。質言之
;  ,每次找到質數p,要刪除p的倍數時,只需從p的平方開始刪去即可,直至num為止
;6.質數11的倍數刪除後,再搜尋下一個是0的位元,該位元所代表的數為質數,再從該質數的平方刪去
; 該質數的倍數
;7.重複步驟6,一直到num的平方根為止,即可找到小於num的質數
                mov     rdi,rdx
                mov     al,48h
                stosb
        .IF rcx<=1
                xor     rax,rax ;使用者輸入0、1
        .ELSEIF rcx==2
                mov     rax,1   ;使用者輸入2
        .ELSEIF rcx<=4
                mov     rax,2   ;使用者輸入3、4
        .ELSEIF rcx<=6
                mov     rax,3   ;使用者輸入5、6
        .ELSEIF rcx<=10
                mov     rax,4   ;使用者輸入7、8、9、10
        .ELSE
                jmp     over_10
        .ENDIF
                jmp     exit_fp
;刪除3、5、7的倍數,所需的資料。共105個位元組。從第一個位元組開始,第0個位元組是48h,沒列入
multiple_of_357 DB      09ah,0a5h,0cdh,0b2h,076h,049h,0b7h,0a6h,0d9h,0d2h,02ch,079h,09eh
                DB      034h,04bh,09bh,065h,0edh,092h,06eh,04dh,0b3h,0a5h,059h,0f2h,03ch
                DB      069h,096h,036h,0cbh,0dah,025h,0ddh,09ah,066h,04bh,0b3h,0e4h,079h
                DB      0d2h,02ch,06dh,096h,0b5h,04bh,0bah,035h,0cdh,096h,066h,0c9h,0f3h
                DB      0a4h,059h,0dah,02ch,06bh,097h,074h,06bh,09ah,02dh,0cdh,092h,0e7h
                DB      049h,0b3h,0b4h,059h,0d6h,02eh,0e9h,0d6h,034h,05bh,09ah,025h,0cfh
                DB      093h,066h,069h,0b3h,0ach,05dh,0d2h,0adh,069h,0b6h,034h,04bh,09eh
                DB      027h,0cdh,0d2h,066h,059h,0bbh,0a4h,05bh,0d3h,06ch,069h,096h,03ch
                DB      04fh
;下表是用來計算某個位元組內,共有幾個位元是零,例如第0筆資料是8,即數值是0的位元組有8個0
;;第一筆資料是7,即數值是1的位元組有7個0;第二筆資料是7,即數值是2的位元組有7個0
tbl_of_no_of_0  DB      8,7,7,6,7,6,6,5,7,6,6,5,6,5,5,4,7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3
                DB      7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2
                DB      7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2
                DB      6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1
                DB      7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2
                DB      6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1
                DB      6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1
                DB      5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1,4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0
over_10:        INVOKE  square_root,rcx
    ;根號num在pMemPrm所指記憶體的第SqrtByte個位元組的第SqrtBit個位元,以
    ;SqrtByte:SqrtBit記錄之
                test    rax,1   ;RAX=num的平方根
                jnz     odd_0
                dec     rax     ;若為num之平方根為偶數,減一使成奇數
odd_0:          sub     rdx,rdx ;SqrtByte=(RAX-3)/16之商
                sub     rax,3   ;SqrtBit=(RAX-3)/16之餘數再除以2
                mov     r8,16
                div     r8
                mov     SqrtByte,rax
                shr     rdx,1
                mov     SqrtBit,rdx
    ;算出pMemPrm所指的記憶體區塊,最多到MaxByte個位元組內的第MaxBit個位元
                mov     rax,rcx
                test    rcx,1
                jnz     odd_1
                dec     rax     ;使用者輸入偶數,因此最後的偶數不用計算
odd_1:          shr     rax,1   ;除去偶數
                xor     rdx,rdx
                mov     r8,8
                div     r8
                mov     MaxByte,rax
                mov     MaxBit,rdx      ;最後一個位元是第MaxByte位元組的第MaxBit位元
    ;刪除3、5、7的倍數,方法是把multiple_of_357字串共105個位元組,填入pMemPrm所指的記憶體
                xor     rdx,rdx
                mov     r11,105
                div     r11
                mov     r9,rax
                or      rax,rax
                jz      remain
again:          mov     rcx,r11
                lea     rsi,multiple_of_357
                rep     movsb
                dec     r9
                jnz     again
remain:         mov     rcx,rdx
                lea     rsi,multiple_of_357
                rep     movsb
        ;在hMemPrm記憶體區塊堙A每個位元代表一個奇數,從第0個位元組的第2個位元開始搜尋,
        ;第一個找到的位元為0的表示此為質數,將其倍數刪去,然後再找到下一個位元為零的,就
        ;是質數…依此程序,直到最後一個位元
                mov     rdi,pMemPrm
                mov     rsi,MaxByte
        ;把pMemPrm記憶體區塊的位元組、位元界限消失,看成連續位元,R11=第幾個位元,從0開
        ;始到(num-1)
                mov     r11,4   ;R11=4,表示數值11,數值=2*R11+3
find_a_prime:   mov     rax,r11
                mov     r8,r11
                shl     rax,1
                inc     r8
                add     rax,3
                mov     r9,rax  ;RAX=R9=找到的質數
                mul     r8  ;RAX=質數的平方所代表的位元距離該質數有多少個位元=(R11+1)*RAX
                add     rax,r11
                mov     r8,r9
                mov     rcx,rax
                and     rcx,7   ;從質數的平方開始,刪去質數的倍數。
                and     r9,7    ;質數的平方在第RAX:RCX處,每次增加R8:R9
                shr     rax,3
                shr     r8,3
next_multiple:  cmp     rax,rsi         ;刪去之前,先檢查RAX:RCX是否超過MaxByte:MaxBit
                jb      set_bit_on      ;若沒有超過,跳到set_bit_on
                ja      next_number
                cmp     rcx,MaxBit
                ja      next_number
set_bit_on:     mov     r10b,1
                shl     r10b,cl
                or      [rdi+rax],r10b
                add     rcx,r9
                add     rax,r8
                cmp     rcx,7
                jbe     next_multiple
                inc     rax
                sub     rcx,8
                jmp     next_multiple  
next_number:    inc     r11     ;已經刪除該質數的倍數,檢查下一個位元所代表的數是否為質數
                mov     r10,r11 ;下一個數就是使R11增加一,也就是在pMemPrm所指的記憶體區塊
                mov     rcx,r11 ;的第R11位元須把這個記憶體區塊視為連續的位元組成,使位元
                shr     r10,3   ;組的界限消失,而第R11個位元是在第R10個位元組堛熔麗CX位元
                and     rcx,7
                cmp     r10,SqrtByte    ;在檢查下一位元前,先檢查是否超過SqrtByte:SqrtBit
                jbe     lt_max          ;如果超過,表示已經刪除了所有小於根號num所有質數之
                cmp     rcx,SqrtBit     ;倍數,跳至get_no_of_prm處
                jae     get_no_of_prm
lt_max:         mov     al,1
                shl     al,cl
                test    [rdi+r10],al    ;檢查下個位元,如果為0,表示下一位元所代表的數為質
                jnz     next_number     ;數,跳躍至find_a_prime處;否則表示不是質數,就
                jmp     find_a_prime    ;跳到next_number
    ;已經檢查到num平方根,表示在pMemPrm所指的記憶體區塊,長MaxByte個位元組內的位元為0者為
    ;質數。底下是計算小於或等於num的質數共有多少個
get_no_of_prm:  mov     r10,OFFSET tbl_of_no_of_0
                mov     r8,0
                mov     rax,1           ;第一個質數不在pMemPrm所指的記憶體內,故由1開始
        ;計算在pMemPrm所指記憶體內的每一個位元組共有幾個位元為0,並且將其總加起來
next_8_bits:    cmp     r8,MaxByte
                jae     less_1_byte
                movzx   r9,BYTE PTR [rdi+r8]
                movzx   rsi,BYTE PTR [r10+r9]
                add     rax,rsi
                inc     r8
                jmp     next_8_bits
        ;計算完整的位元組後還剩幾個位元,計算位元為0的個數
less_1_byte:    mov     dl,[rdi+r8]
                mov     rcx,MaxBit
                jrcxz   exit_fp
@@:             shr     dl,1
                jc      nxt_bit
                inc     rax
nxt_bit:        loop    @b
exit_fp:        ret
find_prime      ENDP
;-----------------------------------------------------------------------------------------
;判斷num是否為質數
;呼叫前後不變的暫存器:R12∼R15、RBX、RSI、RDI
;輸入:num-判斷num是否為質數,num必須小於18446744073709551616(=2^64)
;返回值:RAX=0,表示num為0或1
;    RAX=1,表示num為質數
;    RAX=其他數,表示num不是質數,且RAX為其最小之質因數
is_prime        PROC    USES r12 r13 rsi rdi num:QWORD
                LOCAL   sqrt_n:QWORD    ;√n
                LOCAL   hMem:QWORD
                or      rcx,rcx
                je      num_is_1_or_0
                cmp     rcx,1
                jne     chk_2_3_5
num_is_1_or_0:  xor     rax,rax
                jmp     quit
three_five      DB      9ah,25h,0cdh,92h,66h,49h,0b3h,0a4h,59h,0d2h,2ch,69h,96h,34h,04bh
;檢查RCX是否為2、3、5,如果是的話,返回時,RAX=1
chk_2_3_5:      cmp     rcx,2
                je      num_is_235
                cmp     rcx,3
                je      num_is_235
                cmp     rcx,5
                jne     chk_even
num_is_235:     mov     rax,1
                jmp     quit
;檢查RCX是否為偶數,如果是的話,返回時,RAX=2
chk_even:       test    rcx,1
                jnz     odd_number0
                mov     rax,2
                jmp     quit
        ;檢查num是否為3或5的倍數
odd_number0:    mov     rax,num
                mov     rcx,3
                xor     rdx,rdx
                div     rcx
                or      rdx,rdx
                jnz     chk_5
                mov     rax,rcx
                jmp     quit
chk_5:          mov     rax,num
                mov     rcx,5
                xor     rdx,rdx
                div     rcx
                mov     rax,rcx
                or      rdx,rdx
                jz      quit
                INVOKE  square_root,num
                test    rax,1
                jnz     odd_number1
                inc     rax
odd_number1:    mov     sqrt_n,rax
                mov     rdx,rax
        ;底下要配置記憶體,每個奇數佔用一位元,偶數不必佔用空間,因此每個位元組可容納8個奇
        ;數,而奇、偶數相隔,所以要計算到數值大小為RDX,只要配置RDX/16個位元組,為求保險,
        ;再多20h個位元組
                shr     rdx,4
                add     rdx,20h
                and     rdx,0fffffffffffffff0h
                INVOKE  GlobalAlloc,40h,rdx     ;GPTR=40h
                mov     hMem,rax
        ;計算最後一個位元在hMem後的第R10(從第0個位元組開始)個位元組裡面的第R11個位元
                mov     r10,sqrt_n
                test    r10,1
                jnz     odd_number2
                dec     r10
odd_number2:    mov     r11,r10
                shr     r10,4
                sub     r11,3
                mov     rdi,rax
                and     r11,0fh
                shr     r11,1
        ;第一個位元組的第0、1、2、3、4、5、6、7分別代表3、5、7、9、11、13、15、17,計算完
        ;成後,若某位元為1,表示合數;若某位元為0,表示質數。因此計算完成後,第一個位元組
        ;是的第0位元到第7位元分別是0、0、0、1、0、0、1、0,亦即48h。
                mov     al,48h
                stosb
                mov     rdx,r10
        ;把3、5的倍數所代表的位元設為1
next_15bytes:   mov     rcx,15
                lea     rsi,three_five
                rep     movsb
                sub     rdx,15
                jg      next_15bytes
        ;檢查hMem堛漕C一位元,若為1,表示非質數,再檢查下一位元;若為0,表示質數,先檢查
        ;n是否能被該質數整除,如果能的話,則使RAX=該質數,並跳出此副程式,如果不能整除,
        ;則使該質數的所有倍數所代表的位元變為1,再檢查下一位元
                mov     rsi,hMem
                mov     r8,0    ;以R8:RCX指向hMem堛漕C個位元
                mov     rcx,2   ;從質數7開始檢查,R8:RCX=0:2,表示7
next_bit:       cmp     r8,r10  ;先檢查是否超過sqrt_n,R10:R11=sqrt_n在第R10個位元組堛
                jb      not_max ;第R11個位元
                ja      n_is_prime
                cmp     rcx,r11
                ja      n_is_prime
not_max:        mov     al,1
                shl     al,cl
                test    [r8+rsi],al
                jz      a_prime
                inc     rcx     ;此位元代表的數並非質數,跳到下一數
                cmp     rcx,8   ;檢查是否已經到下一個位元組
                jne     next_bit
                xor     rcx,rcx
                inc     r8
                jmp     next_bit
        ;R8:RCX所代表的數為新找著的質數,先試驗是否能整除num,然後再刪除該質數的倍數
a_prime:        mov     r9,r8
                shl     r9,4
                mov     rdx,rcx
                add     r9,3
                shl     rdx,1
                add     r9,rdx  ;R9=16R8+2RCX+3=質數
                mov     rax,num
                xor     rdx,rdx
                div     r9
                or      rdx,rdx
                jnz     indivisibility  ;indivisibility是除不盡的意思
                push    r9              ;num能被找到的質數,R9整除
                INVOKE  GlobalFree,hMem
                pop     rax
                jmp     quit
        ;num不能被找著的質數整除,要從該質數的平方處開始,刪除該質數的倍數。
indivisibility: mov     rax,r9
                dec     rax
                xor     rdx,rdx
                shr     rax,1
                mul     r9      ;該質數的平方,距離該質數(R8:RCX所指的位元)有RAX個位元
                mov     rdx,rax ;RAX=質數×(質數-1)/2
                and     rax,7
                shr     rdx,3
                add     rax,rcx
                add     rdx,r8
                push    rcx     ;RCX為指向hMem堛漕C個位元,在前面以R8:RCX表示,因此
                cmp     rax,7   ;必須保存起來
                jbe     start_to_del
                sub     rax,8
                inc     rdx
start_to_del:   mov     r13,r9  ;計算R12:R13,R12:R13是每次增加的質數所代表的位元組數
                mov     r12,r9  ;及位元數
                mov     rcx,rax
                shr     r12,3
                and     r13,7   ;從RDX:RCX開始,每次增加R12:R13,直到R10:R11
chk_over:       cmp     rdx,r10 ;檢查是否超過R10:R11
                jb      chk_not_over
                ja      set_1_over
                cmp     rcx,r11
                ja      set_1_over
chk_not_over:   mov     al,1    ;如果沒有超過R10:R11,把每個質數的倍數所代表的位元設為1
                shl     al,cl
                or      [rsi+rdx],al
                add     rcx,r13
                add     rdx,r12
                cmp     rcx,8
                jb      chk_over
                inc     rdx
                sub     rcx,8
                jmp     chk_over
set_1_over:     pop     rcx     ;已把所有質數倍數所代表的位元設為1,要搜尋下一個質數
                inc     rcx
                cmp     rcx,8
                jb      next_bit
                sub     rcx,8
                inc     r8
                jmp     next_bit
n_is_prime:     INVOKE  GlobalFree,hMem
                mov     rax,1
quit:           ret
is_prime        ENDP
;*****************************************************************************************
END             DLLEntry

PRIMEDLL.DEF 的內容是:

1
2
3
4
EXPORTS
        square_root
        find_prime
        is_prime

組譯與連結

在「命令提示字元」堙A依下面方法組譯及連結:

E:\HomePage\SOURCE\Win64\PRIME>uasm64 -win64 PRIMEDLL.ASM [Enter]
UASM v2.46, Jan  8 2018, Masm-compatible assembler.
Portions Copyright (c) 1992-2002 Sybase, Inc. All Rights Reserved.
Source code is available under the Sybase Open Watcom Public License.

PRIMEDLL.ASM: 386 lines, 3 passes, 26 ms, 0 warnings, 0 errors

E:\HomePage\SOURCE\Win64\PRIME>link /DLL /DEF:PRIMEDLL.DEF PRIMEDLL.OBJ [Enter]
Microsoft (R) Incremental Linker Version 9.00.21022.08
Copyright (C) Microsoft Corporation.  All rights reserved.

/SUBSYSTEM:WINDOWS /DEBUG
   Creating library PRIMEDLL.lib and object PRIMEDLL.exp

E:\HomePage\SOURCE\Win64\PRIME>

補充解說

在 find_prime 堙A計算質數個數

在 PRIMEDLL.ASM 的第 199∼217 行。而在 tbl_of_no_of_0 處,定義了 256 各位元組所組成的陣列,如下面:

tbl_of_no_of_0  DB      8,7,7,6,7,6,6,5,7,6,6,5,6,5,5,4,7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3
                DB      7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2
                ……

從 0 到 255 每個數都可以以 8 個位元表示,您也能說 8 個位元可以表示 0∼255 共 256 個整數。而這 8 個位元有幾個位元是 0?有幾個位元是 1?可以參照上面的 tbl_of_no_of_0 陣列。例如第 0 個位元組代表 0,有 8 個位元是 0;第一個位元組代表數值 1,有 7 個位元是 0;第二個位元組代表數值 2,有 7 個位元是 0…。所以在第 199∼217 行就是以查表的方式,去計算每 16 個奇數堙A共有幾個位元是 0,就代表有幾個質數,然後全部累加起來,最後記錄在 RAX 堙C

因為第一個質數是 2,不在 hMemPrm 所指的記憶體區塊中,因此 RAX 由 1 開始。如果 num<10 的話,已在第 73∼81 行處理了,所以可大膽的設定 RAX 由 1 開始。

副程式內用到的資料

有些資料,只有在副程式媟|用到,其他地方用不著。例如 tbl_of_no_of_0 陣列、multiple_of_357 陣列,都只在 find_prime 堥洏峞A其他地方都不會用到這兩陣列的資料。像這時候,如果要把副程式封裝起來,就可以像上面的寫法,在無條件跳躍指令之後,定義這些資料,不過這些資料,只能讀取,不能修改,畢竟這是安插在程式碼區段中的資料。


回上一章回到首頁到下一章