今日は、線形探索（番兵法）。簡単そうだから。
#include <stdio.h> #include <stdlib.h> int search(int list[], int length, int target) { // 番兵（sentinel） list[length] = target; int i = 0; for (; i < length + 1; i++) { if (list[i] == target) break; } if (i != length + 1) { return i; // 見つかった } else { return -1; // 見つからなかった } } int main(void) { // target を探索 int target = 30; // 探索対象のリスト int length = 8; int *list; list = calloc(length + 1, sizeof(int)); if (list == NULL) return -1; list[0] = 23; list[1] = 43; list[2] = 11; list[3] = 64; list[4] = 91; list[5] = 75; list[6] = 30; list[7] = 58; // 線形探索 int index = search(list, length, target); free(list); // 結果の表示 if (index < length) { printf("%d 番目に見つかりました。\r\n", index + 1); return 0; } else if (index == length) { printf("見つかりませんでした。\r\n"); return 0; } else { printf("エラーが発生しました [index = %d]\r\n", index); return -1; } }
今日は、main 関数も読む。デバッグ用のコードを、ごりごり読む。
_main: 00D717A0 push ebp ; EBP を退避 00D717A1 mov ebp,esp ; ESP を退避（EBP ← ESP） 00D717A3 sub esp,0F0h ; ESP ← ESP−0xF0 00D717A9 push ebx ; EBX を退避 00D717AA push esi ; ESI を退避 00D717AB push edi ; EDI を退避 00D717AC lea edi,[ebp+FFFFFF10h] ; EDI ← EDI＋0xF0 00D717B2 mov ecx,3Ch ; ECX ← 0x3C 00D717B7 mov eax,0CCCCCCCCh ; EAX ← 0xCCCCCCCC 00D717BC rep stos dword ptr es:[edi] ; EDI 番地 ← EAX（EDI が 4 減る） ; これを、ECX（0x3C）回繰り返す 00D717BE mov dword ptr [ebp-8],1Eh ; EBP−0x08 番地（target） ← 30 00D717C5 mov dword ptr [ebp-14h],8 ; EBP−0x14 番地（length） ← 8 00D717CC mov esi,esp ; ESI ← ESP 00D717CE push 4 ; 第 2 引数 sizeof(int) 00D717D0 mov eax,dword ptr [ebp-14h] ; EAX ← length 00D717D3 add eax,1 ; EAX ← length＋1 00D717D6 push eax ; 第 1 引数 length＋1 00D717D7 call dword ptr ds:[00D7B16Ch] ; [__imp__calloc] 00D717DD add esp,8 ; ESP を 2 段下へ（引数 2 つ分） 00D717E0 cmp esi,esp ; ESP がずれていないことを確認 00D717E2 call 00D71122 ; __RTC_CheckEsp 00D717E7 mov dword ptr [ebp-20h],eax ; EBP−0x20 番地（list）← EAX 00D717EA cmp dword ptr [ebp-20h],0 ; list と 0 を比較 00D717EE jne 00D717F8 ; 以降の処理へ進む 00D717F0 or eax,0FFFFFFFFh ; EAX ← −1 00D717F3 jmp 00D71905 ; 終了へ進む 00D717F8 mov eax,4 ; EAX ← 4 00D717FD imul ecx,eax,0 ; ECX ← EAX × 0 00D71800 mov edx,dword ptr [ebp-20h] ; EDX ← EBP−0x20（list）番地の値 00D71803 mov dword ptr [edx+ecx],17h ; EDX＋ECX 番地（list[0]） ← 23 00D7180A mov eax,4 ; EAX ← 4 00D7180F shl eax,0 ; EAX ← EAX × 1（0 ビット左にずらす） 00D71812 mov ecx,dword ptr [ebp-20h] ; ECX ← EBP−0x20（list）番地の値 00D71815 mov dword ptr [ecx+eax],2Bh ; ECX＋EAX 番地（list[1]） ← 43 ........ ... ....................... ; 途中略 00D71875 mov eax,4 ; EAX ← 4 00D7187A imul ecx,eax,7 ; ECX ← EAX × 7 00D7187D mov edx,dword ptr [ebp-20h] ; EDX ← EBP−0x20（list）番地の値 00D71880 mov dword ptr [edx+ecx],3Ah ; EDX＋ECX 番地（list[7]） ← 58 00D71887 mov eax,dword ptr [ebp-8] ; EAX ← target 00D7188A push eax ; 第 3 引数 00D7188B mov ecx,dword ptr [ebp-14h] ; ECX ← length 00D7188E push ecx ; 第 2 引数 00D7188F mov edx,dword ptr [ebp-20h] ; EDX ← list 00D71892 push edx ; 第 1 引数 00D71893 call 00D71041 ; _search 00D71898 add esp,0Ch ; ESP を 3 段（引数 3 つ分）下へ 00D7189B mov dword ptr [ebp-2Ch],eax ; index 番地 ← EAX 00D7189E mov esi,esp ; ESI ← ESP 00D718A0 mov eax,dword ptr [ebp-20h] ; EAX ← list 00D718A3 push eax ; 引数 00D718A4 call dword ptr ds:[00D7B168h] ; [__imp__free] 00D718AA add esp,4 ; ESP を 1 段下へ 00D718AD cmp esi,esp ; ESI と ESP を比較 00D718AF call 00D71122 ; __RTC_CheckEsp 00D718B4 mov eax,dword ptr [ebp-2Ch] ; EAX ← EBP−2C（index）番地の値 00D718B7 cmp eax,dword ptr [ebp-14h] ; EAX（index）と length を比較 00D718BA jge 00D718D6 ; Jump if Greater or Equal 00D718BC mov eax,dword ptr [ebp-2Ch] ; EAX ← EBP−2C（index）番地の値 00D718BF add eax,1 ; EAX ← EAX＋1 00D718C2 push eax ; 引数 index＋1 00D718C3 push 0D77C08h ; 引数 "%d 番目に見つかりました。\r\n" 00D718C8 call 00D7132F ; _printf 00D718CD add esp,8 ; ESP を 2 段下へ（引数 2 つ分） 00D718D0 xor eax,eax ; EAX ← 1（戻り値） 00D718D2 jmp 00D71905 ; 終了へ進む 00D718D4 jmp 00D71905 ; （なぜ jmp が 2 回ある？） 00D718D6 mov eax,dword ptr [ebp-2Ch] ; EAX ← EBP−2C（index）番地の値 00D718D9 cmp eax,dword ptr [ebp-14h] ; EAX（index）と length を比較 00D718DC jne 00D718F1 ; 00D718DE push 0D77B30h ; 引数 "見つかりませんでした。\r\n" 00D718E3 call 00D7132F ; _printf 00D718E8 add esp,4 ; ESP を 1 段下へ（引数 1 つ分） 00D718EB xor eax,eax ; EAX ← 1（戻り値） 00D718ED jmp 00D71905 ; 終了へ進む 00D718EF jmp 00D71905 ; （なぜ jmp が 2 回ある？） 00D718F1 mov eax,dword ptr [ebp-2Ch] ; EAX ← EBP−2C（index）番地の値 00D718F4 push eax ; 引数 index 00D718F5 push 0D77D08h ; 引数 "エラーが発生しました [index = %d]\r\n" 00D718FA call 00D7132F ; _printf 00D718FF add esp,8 ; ESP を 2 段下へ（引数 2 つ分） 00D71902 or eax,0FFFFFFFFh ; EAX ← −1（戻り値） 00D71905 pop edi ; EDI を戻す 00D71906 pop esi ; ESI を戻る 00D71907 pop ebx ; EBX を戻す 00D71908 add esp,0F0h ; ESP ← ESP＋0xF0 00D7190E cmp ebp,esp ; EBP と ESP を比較する 00D71910 call 00D71122 ; __RTC_CheckEsp 00D71915 mov esp,ebp ; ESP ← EBP 00D71917 pop ebp ; EBP を戻す 00D71918 ret ; EAX の値（リターンコード）で終了
もちろん search 関数も読む。もりもり読む。
_search: ; 前処理 00D71A10 push ebp ; EBP を退避 00D71A11 mov ebp,esp ; ESP を退避（EBP ← ESP） 00D71A13 sub esp,0CCh ; ESP ← ESP−0xCC 00D71A19 push ebx ; EBX を退避 00D71A1A push esi ; ESI を退避 00D71A1B push edi ; EDI を退避 00D71A1C lea edi,[ebp+FFFFFF34h] ; EDI ← EBP＋0xCC 00D71A22 mov ecx,33h ; ECX ← 0x33 00D71A27 mov eax,0CCCCCCCCh ; EAX ← 0xCCCCCCCC 00D71A2C rep stos dword ptr es:[edi] ; EDI 番地 ← EAX（EDI が 4 減る） ; これを、ECX（0x33）回繰り返す ; 初期値の設定 00D71A2E mov eax,dword ptr [ebp+0Ch] ; EAX ← EBP＋0x0C（length）番地の値 00D71A31 mov ecx,dword ptr [ebp+8] ; ECX ← EBP＋0x08（list）番地の値 00D71A34 mov edx,dword ptr [ebp+10h] ; EDX ← EBP＋0x10（target）番地の値 00D71A37 mov dword ptr [ecx+eax*4],edx; ECX＋EAX×4 番地 ← EDX 00D71A3A mov dword ptr [ebp-8],0 ; EBX−8（i）← 0 00D71A41 jmp 00D71A4C ; list と target のマッチングへ進む ; ループの処理（i のインクリメント） 00D71A43 mov eax,dword ptr [ebp-8] ; EAX ← i 00D71A46 add eax,1 ; i++ 00D71A49 mov dword ptr [ebp-8],eax ; EBP−8（i）番地 ← EAX（i++） ; ループの処理（list と target のマッチング） 00D71A4C mov eax,dword ptr [ebp+0Ch] ; EAX ← EBP＋0x0C（length）番地の値 00D71A4F add eax,1 ; length＋1 00D71A52 cmp dword ptr [ebp-8],eax ; EBP−8（i）の値と EAX を比較 00D71A55 jge 00D71A69 ; 見つかったかどうかの判定に進む 00D71A57 mov eax,dword ptr [ebp-8] ; EAX ← EBP−8（i）番地の値 00D71A5A mov ecx,dword ptr [ebp+8] ; ECX ← EBP＋0x08（list）番地の値 00D71A5D mov edx,dword ptr [ecx+eax*4]; EDX ← list 番地から i 段下 00D71A60 cmp edx,dword ptr [ebp+10h] ; EDX と target を比較 00D71A63 jne 00D71A67 ; 2 行下へ進む 00D71A65 jmp 00D71A69 ; 見つかったかどうかの判定に進む 00D71A67 jmp 00D71A43 ; i のインクリメントへ進む ; ループの処理（見つかったかどうかの判定） 00D71A69 mov eax,dword ptr [ebp+0Ch] ; EAX ← EBP＋0x0C（length）番地の値 00D71A6C add eax,1 ; length＋1 00D71A6F cmp dword ptr [ebp-8],eax ; i の値と length＋1 の値を比較 00D71A72 je 00D71A7B ; 4 行下へ進む 00D71A74 mov eax,dword ptr [ebp-8] ; EAX ← i 00D71A77 jmp 00D71A7E ; 後処理へ進む 00D71A79 jmp 00D71A7E ;（なぜ jmp が 2 回ある？） 00D71A7B or eax,0FFFFFFFFh ; EAX ← −1 ; 後処理 00D71A7E pop edi ; EDI を戻す 00D71A7F pop esi ; ESI を戻す 00D71A80 pop ebx ; EBX を戻す 00D71A81 mov esp,ebp ; ESP を戻す（ESB ← EBP） 00D71A83 pop ebp ; EBP を戻す 00D71A84 ret ; EAX の値（リターンコード）で終了
急いでいるので、コメント控えめで。
