🎇 🐫 🏄 सरल x86 कोडांतरक कार्यक्रम: एराटोस्थनीज की छलनी 🏗️ 👩‍💻 🤽

उद्घाटन टिप्पणी

मेरे पेशे में, मैं निम्न-स्तरीय प्रोग्रामिंग का सामना नहीं करता: मैं स्क्रिप्टिंग भाषाओं में प्रोग्रामिंग में लगा हुआ हूं। लेकिन चूँकि आत्मा को विविधता की आवश्यकता होती है, ज्ञान के क्षितिज को व्यापक बनाना या बस यह समझना कि मशीन निम्न स्तर पर कैसे काम करती है, मैं उन भाषाओं के अलावा अन्य भाषाओं में प्रोग्रामिंग करता हूँ जिनके साथ मैं पैसा कमाता हूँ - यह मेरा शौक है।

और अब, मैं x86 परिवार प्रोसेसर के लिए एक सरल विधानसभा भाषा कार्यक्रम बनाने के अनुभव को साझा करना चाहूंगा, जिसके विश्लेषण से आप अपनी यात्रा को अमूर्त स्तरों के तराई क्षेत्रों की विजय में शुरू कर सकते हैं।

इसे लिखने से पहले, मैंने भविष्य के कार्यक्रम के लिए ऐसी आवश्यकताओं को तैयार किया:

मेरा कार्यक्रम एक डॉस कार्यक्रम नहीं होना चाहिए। बहुत से उदाहरण एक साधारण एपीआई के संबंध में इसके लिए उन्मुख हैं। मेरा कार्यक्रम आधुनिक ओएस पर चलना चाहिए ।
कार्यक्रम को एक गुच्छा का उपयोग करना चाहिए - इसके निपटान में गतिशील रूप से आवंटित स्मृति प्राप्त करें।
बहुत अधिक जटिल न होने के लिए, कार्यक्रम को बिना हाइफ़न के उपयोग के बिना अहस्ताक्षरित पूर्णांक के साथ काम करना चाहिए।

अपने कार्यक्रम के लिए, मैंने एरासोस्थनीज़ की छलनी का उपयोग करके अपराधों की खोज करना चुना। मैंने nasm को असेंबलर के रूप में चुना।

मैंने इसके निष्पादन की गति की तुलना में शैली और समझ पर अधिक जोर देने के साथ कोड लिखा। उदाहरण के लिए, मैंने xor eax, eax का उपयोग करके रजिस्टर को रीसेट नहीं किया, लेकिन अधिक उपयुक्त निर्देश शब्दार्थ के कारण mov eax, 0 का उपयोग किया। मैंने फैसला किया कि चूंकि कार्यक्रम विशेष रूप से शैक्षिक लक्ष्यों का पीछा करता है, आप कोडांतरक में कोड शैली की खोज में अविश्वास और संलग्न कर सकते हैं।

तो, आइए देखें कि क्या हुआ।

कहाँ से शुरू करें?

शायद सबसे कठिन बात जो आपको उच्च स्तरीय भाषाओं से असेंबलर में ले जाने के दौरान होती है, स्मृति का संगठन है। सौभाग्य से, हैबे पर इस विषय पर पहले से ही एक अच्छा लेख था।

सवाल यह भी उठता है कि कार्यक्रम की आंतरिक दुनिया और बाहरी वातावरण के बीच डेटा का आदान-प्रदान कैसे इतने निचले स्तर पर होता है। यहां ऑपरेटिंग सिस्टम का एपीआई दृश्य में प्रवेश करता है। डॉस में, जैसा कि पहले ही उल्लेख किया गया है, इंटरफ़ेस काफी सरल था। उदाहरण के लिए, कार्यक्रम "हैलो, दुनिया" इस तरह दिखता था:

 SECTION .text org 0x100 mov ah, 0x9 mov dx, hello int 0x21 mov ax, 0x4c00 int 0x21 SECTION .data hello: db "Hello, world!", 0xD, 0xA, '$'

Windows में, Win32 API का उपयोग इन उद्देश्यों के लिए किया जाता है, क्रमशः, प्रोग्राम को संबंधित पुस्तकालयों के तरीकों का उपयोग करना चाहिए:

 %include "win32n.inc" extern MessageBoxA import MessageBoxA user32.dll extern ExitProcess import ExitProcess kernel32.dll SECTION code use32 class=code ..start: push UINT MB_OK push LPCTSTR window_title push LPCTSTR banner push HWND NULL call [MessageBoxA] push UINT NULL call [ExitProcess] SECTION data use32 class=data banner: db "Hello, world!", 0xD, 0xA, 0 window_title: db "Hello", 0

यहां हम win32n.inc फ़ाइल का उपयोग करते हैं, जहां मैक्रोज़ परिभाषित हैं कि Win32 API के साथ काम करने के लिए कोड को कम करें।

मैंने सीधे ओएस एपीआई का उपयोग नहीं करने का फैसला किया और सी लाइब्रेरी से कार्यों का उपयोग करने का तरीका चुना। यह लिनक्स में कार्यक्रम को संकलित करने की संभावना को भी खोलता है (और, सबसे अधिक संभावना, अन्य ओएस में) - इस कार्यक्रम के लिए एक बड़ी और आवश्यक उपलब्धि नहीं है, लेकिन एक सुखद उपलब्धि है।

सबरूटीन कॉल

सबप्रोग्राम को कॉल करने की आवश्यकता अध्ययन के लिए कई विषयों पर जोर देती है: सबप्रोग्राम्स का आयोजन, तर्क पारित करना, स्टैक फ्रेम बनाना, स्थानीय चर के साथ काम करना।

उपप्रोग्राम वह लेबल होता है जिसके द्वारा कोड स्थित होता है। सबरूटीन ret स्टेटमेंट के साथ समाप्त होता है। उदाहरण के लिए, डॉस में इस तरह की एक सबरुटी कंसोल में "हेलो, वर्ल्ड" स्ट्रिंग प्रदर्शित करती है:

 print_hello: mov ah, 0x9 mov dx, hello int 0x21 ret

इसे कॉल करने के लिए, आपको call स्टेटमेंट का उपयोग करना होगा:

 call print_hello

खुद के लिए, मैंने रजिस्टरों के माध्यम से उपप्रोग्राम में तर्क पारित करने का फैसला किया और उन टिप्पणियों में संकेत दिया जिनमें रजिस्टर होना चाहिए, लेकिन उच्च स्तर की भाषाओं में, स्टैक के माध्यम से तर्क पारित किए जाते हैं। उदाहरण के लिए, यह कैसे सी लाइब्रेरी से printf फ़ंक्शन कहलाता है:

 push hello call _printf add esp, 4

तर्क दाएं से बाएं पास किए जाते हैं, कॉल करने वाले के साथ स्टैक झूठ को साफ करने की जिम्मेदारी।

सबरूटीन में प्रवेश करते समय, आपको एक नया स्टैक फ्रेम बनाने की आवश्यकता होती है । यह निम्नानुसार किया जाता है:

 print_hello: push ebp ;       mov ebp, esp ;

तदनुसार, बाहर निकलने से पहले, आपको स्टैक की पिछली स्थिति को पुनर्स्थापित करने की आवश्यकता है:

  mov esp, ebp pop ebp ret

स्थानीय चर के लिए , एक स्टैक का भी उपयोग किया जाता है, जिस पर एक नया फ्रेम बनाने के बाद, बाइट्स की आवश्यक संख्या आवंटित की जाती है:

 print_hello: push ebp mov ebp, esp sub esp, 8 ;     8 ,

X86 आर्किटेक्चर भी विशेष निर्देश प्रदान करता है जिसकी मदद से ये क्रियाएं अधिक आसानी से लागू की जा सकती हैं:

 print_hello: enter 8, 0 ;  ,  8     leave ;  ret

enter बयान का दूसरा पैरामीटर सबरूटीन का घोंसले का स्तर है। यह उच्च-स्तरीय भाषाओं के साथ जोड़ने के लिए आवश्यक है जो दिनचर्या को व्यवस्थित करने के लिए इस तरह की तकनीक का समर्थन करते हैं। हमारे मामले में, यह मान शून्य छोड़ा जा सकता है।

कार्यक्रम ही

प्रोजेक्ट में निम्न फ़ाइलें हैं:

main.asm - मुख्य फ़ाइल,
functions.asm चमगादड़ - दिनचर्या,
string_constants.asm - स्ट्रिंग स्थिरांक की परिभाषा,
Makefile - स्क्रिप्ट का निर्माण

मुख्य फ़ाइल के लिए कोड पर विचार करें:

main.asm

 %define SUCCESS 0 %define MIN_MAX_NUMBER 3 %define MAX_MAX_NUMBER 4294967294 global _main extern _printf extern _scanf extern _malloc extern _free SECTION .text _main: enter 0, 0 ;   call input_max_number cmp edx, SUCCESS jne .custom_exit mov [max_number], eax ;     mov eax, [max_number] call allocate_flags_memory cmp edx, SUCCESS jne .custom_exit mov [primes_pointer], eax ;   mov eax, [primes_pointer] mov ebx, [max_number] call find_primes_with_eratosthenes_sieve ;  mov eax, [primes_pointer] mov ebx, [max_number] call print_primes ;     mov eax, [primes_pointer] call free_flags_memory ; .success: push str_exit_success call _printf jmp .return .custom_exit: push edx call _printf .return: mov eax, SUCCESS leave ret %include "functions.asm" SECTION .data max_number: dd 0 primes_pointer: dd 0 %include "string_constants.asm"

यह देखा जा सकता है कि कार्यक्रम को 5 ब्लॉकों में विभाजित किया गया है, जिसे उपप्रोग्राम के रूप में डिज़ाइन किया गया है:

input_max_number - कंसोल का उपयोग करके यह उपयोगकर्ता से अधिकतम संख्या के लिए पूछता है जिससे सरल खोजे जाते हैं; त्रुटियों से बचने के लिए, मूल्य स्थिरांक MIN_MAX_NUMBER और MAX_MAX_NUMBER द्वारा सीमित है
allocate_flags_memory - ओएस को ढेर पर संख्या के निशान (सरल / यौगिक) के लिए मेमोरी आवंटित करने के लिए कहें; यदि सफल होता है, तो eax रजिस्टर के माध्यम से आवंटित मेमोरी को एक पॉइंटर लौटाता है
find_primes_with_eratosthenes_sieve - find_primes_with_eratosthenes_sieve की क्लासिक छलनी का उपयोग करके संयुक्त संख्याओं को निकाल दिया;
print_primes - कंसोल को primes की एक सूची प्रिंट करें;
free_flags_memory - झंडे के लिए आवंटित मुफ्त मेमोरी

फ़ंक्शंस के लिए, निम्नलिखित नियम पर सहमति दी गई थी: मान को edx माध्यम से लौटाया गया है, edx में स्थिति है। सफल होने पर, इसमें SUCCESS मान होता है, जो कि, 0 , विफलता के मामले में, त्रुटि संदेश के साथ लाइन का पता है जो उपयोगकर्ता को प्रदर्शित किया जाएगा।

string_constants.asm फ़ाइल में स्ट्रिंग चर की परिभाषा शामिल है, जिनके मान, फ़ाइल संकेत के नाम के रूप में, परिवर्तित होने का इरादा नहीं है। यह केवल इन चरों के लिए था कि एक अपवाद "वैश्विक चर का उपयोग न करें" नियम के लिए किया गया था। I / O फ़ंक्शंस में स्ट्रिंग स्थिरांक वितरित करने के लिए मुझे कभी भी अधिक सुविधाजनक तरीका नहीं मिला - मैंने फ़ंक्शन कॉल के तुरंत पहले स्टैक पर लिखने के बारे में भी सोचा था, लेकिन फैसला किया कि यह विचार वैश्विक चर के साथ विचार की तुलना में बहुत खराब है।

string_constants.asm

 ; -,  str_max_number_label: db "Max number (>=3): ", 0 str_max_number_input_format: db "%u", 0 str_max_number_output_format: db "Using max number %u", 0xD, 0xA, 0 str_print_primes_label: db "Primes:", 0xD, 0xA, 0 str_prime: db "%u", 0x9, 0 str_cr_lf: db 0xD, 0xA, 0 ;  str_exit_success: db "Success!", 0xD, 0xA, 0 str_error_max_num_too_little: db "Max number is too little!", 0xD, 0xA, 0 str_error_max_num_too_big: db "Max number is too big!", 0xD, 0xA, 0 str_error_malloc_failed: db "Can't allocate memory!", 0xD, 0xA, 0

निम्न परिदृश्य का उपयोग असेंबली के लिए किया जाता है:

makefile

 ifdef SystemRoot format = win32 rm = del ext = .exe else format = elf rm = rm -f ext = endif all: primes.o gcc primes.o -o primes$(ext) $(rm) primes.o primes.o: nasm -f $(format) main.asm -o primes.o

उपप्रोग्राम (कार्य)

input_max_number

सबरूटीन कोड

 ;    ; : EAX -   input_max_number: ; -, ;4     enter 4, 1 ;  push str_max_number_label ;. string_constants.asm call _printf add esp, 4 ; scanf mov eax, ebp sub eax, 4 push eax push str_max_number_input_format ;. string_constants.asm call _scanf add esp, 8 mov eax, [ebp-4] ; cmp eax, MIN_MAX_NUMBER jb .number_too_little cmp eax, MAX_MAX_NUMBER ja .number_too_big jmp .success ; .number_too_little: mov edx, str_error_max_num_too_little ;. string_constants.asm jmp .return .number_too_big: mov edx, str_error_max_num_too_big ;. string_constants.asm jmp .return .success: push eax push str_max_number_output_format ;. string_constants.asm call _printf add esp, 4 pop eax mov edx, SUCCESS .return: leave ret

उपप्रोग्राम को प्रोग्राम में पेश करने के लिए डिज़ाइन किया गया है जिसमें अधिकतम संख्या को खोजा जाएगा। यहां मुख्य बिंदु सी लाइब्रेरी से scanf फ़ंक्शन के लिए कॉल है:

  mov eax, ebp sub eax, 4 push eax push str_max_number_input_format ;. string_constants.asm call _scanf add esp, 8 mov eax, [ebp-4]

इस प्रकार, मेमोरी एड्रेस को पहले बेस में स्टैक बेस पॉइंटर के नीचे 4 बाइट्स लिखा गया है। यह उपप्रोग्राम की स्थानीय आवश्यकताओं के लिए आवंटित की गई मेमोरी है। इस मेमोरी के पॉइंटर को scanf फंक्शन में पास किया जाता है क्योंकि कीबोर्ड से दर्ज किए गए डेटा को लिखने के लिए लक्ष्य।

फ़ंक्शन को कॉल करने के बाद, दर्ज किया गया मान मेमोरी से eax तक चलता है।

आवंटित करें_फ्लैग_मेमोरी और फ्री_फ्लैग_मैमोरी

रूटीन कोड

 ;      ; : EAX -   ; : EAX -    allocate_flags_memory: enter 8, 1 ; EAX+1  inc eax mov [ebp-4], eax push eax call _malloc add esp, 4 ; cmp eax, 0 je .fail mov [ebp-8], eax ; mov byte [eax], 0 cld mov edi, eax inc edi mov edx, [ebp-4] add edx, eax mov al, 1 .write_true: stosb cmp edi, edx jb .write_true ; mov eax, [ebp-8] jmp .success .fail: mov edx, str_error_malloc_failed ;. string_constants.asm jmp .return .success: mov edx, SUCCESS .return: leave ret ;      ; : EAX -    free_flags_memory: enter 0, 1 push eax call _free add esp, 4 leave ret

इन रूटीनों में प्रमुख स्थान मॉलोक के लिए कॉल और सी लाइब्रेरी से free कार्य हैं।

malloc सफलता के मामले में, eax रजिस्टर के माध्यम से आवंटित मेमोरी का पता देता है, विफलता के मामले में, इस रजिस्टर में 0 होता है। यह अधिकतम संख्या के संबंध में कार्यक्रम की अड़चन है। 32 बिट्स 4,294,967,295 तक के अपराधों की खोज करने के लिए पर्याप्त हैं, लेकिन आप एक बार में अधिक मेमोरी आवंटित नहीं कर पाएंगे।

find_primes_with_eratosthenes_sieve

सबरूटीन कोड

 ;       ;: EAX -    , EBX -   find_primes_with_eratosthenes_sieve: enter 8, 1 mov [ebp-4], eax add eax, ebx inc eax mov [ebp-8], eax ;   cld mov edx, 2 ;p = 2 mov ecx, 2 ;  = 2 .strike_out_cycle: ;x = c*p mov eax, edx push edx mul ecx pop edx cmp eax, ebx jbe .strike_out_number jmp .increase_p .strike_out_number: mov edi, [ebp-4] add edi, eax mov byte [edi], 0 inc ecx ;c = c + 1 jmp .strike_out_cycle .increase_p: mov esi, [ebp-4] add esi, edx inc esi mov ecx, edx inc ecx .check_current_number: mov eax, ecx mul eax cmp eax, ebx ja .return lodsb inc ecx cmp al, 0 jne .new_p_found jmp .check_current_number .new_p_found: mov edx, ecx dec edx mov ecx, 2 jmp .strike_out_cycle .return: leave ret

सबरूटीन एक्सएमएल असेंबली भाषा में समग्र संख्या, एराटोस्थनीज की छलनी के लिए शास्त्रीय एल्गोरिदम को लागू करता है। यह सुखद है क्योंकि यह बाहरी फ़ंक्शन कॉल का उपयोग नहीं करता है और त्रुटि से निपटने की आवश्यकता नहीं है :)

print_primes

सबरूटीन कोड

 ;    ; : EAX -    , EBX -   print_primes: enter 12, 1 mov [ebp-4], eax mov [ebp-8], ebx push str_print_primes_label call _printf add esp, 4 cld mov esi, [ebp-4] mov edx, esi add edx, [ebp-8] inc edx mov [ebp-12], edx mov ecx, 0 .print_cycle: lodsb cmp al, 0 jne .print jmp .check_finish .print: push esi push ecx push str_prime ;. string_constants.asm call _printf add esp, 4 pop ecx pop esi mov edx, [ebp-12] .check_finish: inc ecx cmp esi, edx jb .print_cycle push str_cr_lf call _printf add esp, 4 leave ret

रुटीन प्राइम नंबर को कंसोल पर प्रिंट करता है। यहाँ मुख्य बिंदु C लाइब्रेरी से printf फ़ंक्शन को कॉल कर रहा है।

निष्कर्ष

खैर, कार्यक्रम सभी उल्लिखित आवश्यकताओं को पूरा करता है और समझने में आसान लगता है। मैं आशा करना चाहता हूं कि किसी के विश्लेषण से प्रोग्रामिंग को निम्न स्तर पर समझने में मदद मिलेगी और वह उतना ही आनंद लेगा जितना मैंने किया था।

मैं कार्यक्रम का पूर्ण स्रोत कोड भी देता हूं।

मैं एक दिलचस्प तथ्य भी दे सकता हूं। चूंकि हमें बचपन से सिखाया गया था कि कोडांतरक प्रोग्राम तेजी से चलते हैं, इसलिए मैंने इस प्रोग्राम की गति की तुलना C ++ प्रोग्राम की गति के साथ करने का फैसला किया, जो मैंने एक बार लिखा था और एटकिन रीशेट का उपयोग करके प्रिम्स की तलाश कर रहा था। विजुअल स्टूडियो में /O2 साथ संकलित एक C ++ प्रोग्राम ने मेरी मशीन पर लगभग 25 सेकंड ^में नंबर 2 ³⁰ तक खोजा। असेंबलर में कार्यक्रम 15 सेकंड की चलनी के साथ Eratosthenes दिखाया।

यह, ज़ाहिर है, एक वैज्ञानिक तथ्य से अधिक एक चाल है, क्योंकि कोई गंभीर परीक्षण नहीं था, कारणों का कोई स्पष्टीकरण नहीं था, लेकिन एक दिलचस्प तथ्य के रूप में, यह मुझे लेख को पूरा करने के लिए लगता है।

सरल x86 कोडांतरक कार्यक्रम: एराटोस्थनीज की छलनी

उद्घाटन टिप्पणी

कहाँ से शुरू करें?

सबरूटीन कॉल

कार्यक्रम ही

उपप्रोग्राम (कार्य)

input_max_number

आवंटित करें_फ्लैग_मेमोरी और फ्री_फ्लैग_मैमोरी

find_primes_with_eratosthenes_sieve

print_primes

निष्कर्ष

उपयोगी लिंक

More articles: