CodeWars - ภาษาแอสเซมบลี - ตรวจสอบรายการค่า

Sep 29 2020

ฉันกำลังประสบปัญหาภาษาแอสเซมบลีใน CodeWars ซึ่งเป็นเว็บไซต์ที่มีปัญหาในการฝึกฝน

ปัญหา

https://www.codewars.com/kata/545991b4cbae2a5fda000158/train/nasm

สร้างเมธอดที่ยอมรับรายการและรายการและส่งคืนค่าจริงหากรายการนั้นเป็นของรายการมิฉะนั้นเป็นเท็จ

โซลูชันในค

เพื่อให้คุณทราบว่ารหัสประกอบจะทำอย่างไร

#include <stdbool.h>
#include <stddef.h>

bool include(const int* arr, size_t size, int item)
{
    int i = 0;
    loop:
    if ( i < size ) {
        if ( arr[i] == item ) {
            return true;
        }
        i++;
        goto loop;
    } 
    return false;
}

โซลูชันใน NASM Assembly (Linux x64)

CodeWars ให้ 7 บรรทัดที่ด้านบน

SECTION .text
global include
include:

    ; bool include(const int* arr, size_t size, int item)
    ; sizeof(int) = 4 bytes (32bit)
    ; sizeof(size_t) = 8 bytes (64bit)
    
    ;rdi = &arr    pointer, 8 bytes
    ;   arr[i]          signed int, 4 bytes (dd)
    ;rsi = size    size_t, unsigned int, 8 bytes
    ;edx = item    signed int, 4 bytes
    
    ; Avoid using registers that we need to preserve (RBX, RBP, R12-R15). Else we'd have to push and pop them onto the stack.

    mov rcx, 0      ; unsigned int i = 0;
loop1:
    cmp rcx, rsi    ; if ( i < size ) {
    jae skip_loop
    
    mov r8d, [rdi + 4 * rcx]        ; make a temp variable so we can see this in step debugging
    cmp edx, r8d    ; if ( arr[i] == item ) {
    jne skip_if
    mov rax, 1      ; return true;
    ret
    
skip_if:
    inc rcx         ; i++;
    jmp loop1
    
skip_loop:
    mov rax, 0      ; return false;
    ret

คำถาม

ฉันเป็นคนใหม่ในการประกอบ ข้อเสนอแนะใด ๆ เกี่ยวกับรูปแบบและแนวทางปฏิบัติที่ดีที่สุดจะได้รับการชื่นชม ตัวอย่างเช่น

มีรูปแบบมาตรฐานที่จะใช้เมื่อเขียนลูปหรือไม่?
มีรูปแบบมาตรฐานที่จะใช้เมื่อเขียน if / elseif / else หรือไม่?
มีตัวเลือกคำและการจัดรูปแบบที่ดีกว่าสำหรับป้ายกำกับหรือไม่?

คำตอบ

7 JoseFernandoLopezFernandez Sep 30 2020 at 23:45

ก่อนอื่นอุปกรณ์ประกอบฉากสำหรับความคิดเห็นมากมายโดยเฉพาะอย่างยิ่งวิธีที่คุณรวมการเป็นตัวแทนใน C การแทนค่า C นั้นมีการเปรียบเทียบแบบเซ็นกับแบบไม่ได้ลงนามซึ่งอาจทำให้เกิดข้อผิดพลาดแปลก ๆเมื่อใดและที่ใดที่คุณไม่คาดคิด แต่ฉันจะไป เพื่อยึดติดกับรหัสการประกอบในการตรวจสอบนี้ ผมแค่อยากจะแนะนำประกาศเคาน์เตอร์ห่วงiเป็นsize_tเพราะนั่นคือสิ่งที่ประเภทของสภาพหยุดคือ

ฉันประกอบฟังก์ชัน C ของคุณโดยใช้ gcc เวอร์ชัน 10.2.0 ด้วย-O3 -march=nativeดังนั้นฉันจะรวมเอาท์พุทไว้ที่นี่เพื่อที่ฉันจะได้อธิบายทีละขั้นตอนโดยเปรียบเทียบการใช้งานทั้งสอง นี่เป็นความคิดที่ดีจริงๆเพราะการทำงานย้อนหลังผ่านสิ่งที่คอมไพเลอร์ C ช่วยให้คุณเห็นภาษาแอสเซมบลีที่แท้จริงไม่ใช่แค่การฝึกฝนตัวอย่างที่คุณเขียน Compiler Explorerเป็นเครื่องมือที่ยอดเยี่ยมสำหรับสิ่งนี้

อย่างไรก็ตามนี่คือไฟล์อินพุตของฉัน

#include <stdbool.h>
#include <stddef.h>

bool include(const int* arr, size_t size, int item) {
    for (size_t i = 0; i < size; ++i) {
        if (arr[i] == item) {
            return true;
        }
    }

    return false;
}

ในการประกอบฉันใช้คำสั่งต่อไปนี้ สังเกต-masm=intelอาร์กิวเมนต์; ไวยากรณ์ของแอสเซมบลีเริ่มต้นAT&Tสำหรับเครื่องมือ GNU

gcc -S -O3 -march=native -masm=intel -o output.asm input.c

คุณสามารถกรองข้อมูลเมตาเสริมและป้ายกำกับที่มีโดยใช้คำสั่งต่อไปนี้

cat output.asm | sed -E '/^\s+\./d;/^\.L[A-Z]/d'

และนี่คือผลลัพธ์ของฉัน

include:
        test    rsi, rsi
        je      .L4
        xor     eax, eax
        jmp     .L3
.L8:
        inc     rax
        cmp     rsi, rax
        je      .L4
.L3:
        cmp     DWORD PTR [rdi+rax*4], edx
        jne     .L8
        mov     eax, 1
        ret
.L4:
        xor     eax, eax
        ret

สังเกตว่าบรรทัดแรกแตกต่างกันอยู่แล้ว ในรุ่นของคุณเริ่มต้นโดยการตั้งค่าrcxลงทะเบียนเพื่อ0ใช้การเรียนการสอนในขณะที่การส่งออกคอมไพเลอร์mov test rsi, rsiทำไม?

ตามที่คุณระบุไว้การประชุมการเรียกโปรแกรมแอสเซมบลีของ Intel x86-64 Linux กำหนดว่าrsiรีจิสเตอร์มีอาร์กิวเมนต์ที่สองสำหรับฟังก์ชันของคุณในกรณีนี้คือขนาดของอาร์เรย์ จากเอกสาร Intel x86-64 (หน้า 1866) testคำสั่งจะทำการทดสอบเชิงตรรกะ AND กับอาร์กิวเมนต์ หากผลเป็นศูนย์จะตั้งธงเป็นศูนย์เท่ากับZF 1ดังนั้นคำสั่งต่อไปนี้จึงสมเหตุสมผลเนื่องจากคำสั่ง "กระโดดใกล้ถ้าเท่ากัน" ( je) จะดำเนินการเมื่อตั้งค่าแฟล็กศูนย์ ( ZF=1)

กล่าวอีกนัยหนึ่งรูทีนย่อยเริ่มต้นด้วยการตรวจสอบว่าอาร์เรย์อินพุตมีรายการใด ๆ จริงหรือไม่ก่อนที่จะทำอะไรกับมัน โปรดทราบว่าคุณไม่ได้ตรวจสอบกรณีขอบนี้ในรหัสเดิมของคุณ (และคุณไม่ได้ตรวจสอบตัวชี้อาร์เรย์NULL) และเป็นตัวอย่างที่ดีของคอมไพเลอร์ที่ยอดเยี่ยม Matt Godbolt (คนที่สร้าง Compiler Explorer) มีคำพูดที่ยอดเยี่ยมเกี่ยวกับเรื่องประเภทนี้ซึ่งผมขอแนะนำให้คุณลองดูว่าคุณชอบสิ่งนี้หรือไม่

ยังไงก็ตามถ้าคุณดูที่ฉลากคุณจะสังเกตเห็นว่ามันเป็นความหมายเทียบเท่ากับของคุณ.L4 skip_loopอย่างไรก็ตามคุณตั้งค่าraxregister (เช่นค่าส่งคืนของฟังก์ชัน) ให้เท่ากับศูนย์โดยmovใส่0เข้าไปในขณะที่คอมไพเลอร์ใช้เอกสิทธิ์เฉพาะหรือxorคำสั่งeaxด้วยตัวมันเองซึ่งเห็นได้ชัดว่าจะเป็นศูนย์เสมอ คุณไม่ได้ผิดทางความหมายสำหรับการทำเช่นนี้ แต่คุณสามารถอ่านโพสต์ SO นี้ซึ่งอธิบายรายละเอียดที่สำคัญว่าทำไมคุณจึงควรเลือกใช้xor eax, eaxวิธีนี้ รุ่นสั้นก็คือว่ามันมีประสิทธิภาพมากขึ้นและอีกรุ่นคือว่ามันมากมีประสิทธิภาพมากขึ้น แต่มีผลประโยชน์อื่น ๆ เช่นการใช้พลังงาน โพสต์นั้นมีรายละเอียดมากขึ้นและเป็นการอ่านที่ยอดเยี่ยม

ห่วงของคุณเองก็ดูโอเคสำหรับฉัน คอมไพเลอร์ใช้raxรีจิสเตอร์สำหรับตัวนับลูปซึ่งทั้งคุณและคอมไพเลอร์จะใช้เพื่อรับค่าอาร์เรย์ที่ดัชนีที่เหมาะสม ข้อแตกต่างที่แท้จริงเพียงอย่างเดียวระหว่างสองเวอร์ชันคือคอมไพเลอร์ใช้jmpคำสั่งการกระโดดที่ไม่มีเงื่อนไขเพื่อข้ามส่วนแรกของลูปหลักซึ่งมีการเพิ่มตัวนับลูปในขณะที่โค้ดของคุณมีค่าสุดท้าย

ฉันไม่คิดว่าความแตกต่างนี้มีผลกระทบอย่างแท้จริงเนื่องจากการใช้งานทั้งสองมีการกระโดดแบบมีเงื่อนไขสองครั้งซึ่งส่งผลกระทบอย่างมากต่อประสิทธิภาพเนื่องจากการเรียกใช้คำสั่งที่ไม่มีเงื่อนไขและเกี่ยวข้องกับคุณสมบัติตัวประมวลผลขั้นสูงเพิ่มเติมเช่นการทำนายสาขาซึ่งจะแนะนำปัญหาผ่านการเพิ่มประสิทธิภาพที่เรียกว่าการเก็งกำไร การกระทำ (เรื่องสั้นขนาดยาวการเพิ่มประสิทธิภาพมีความซับซ้อนคุณจะไม่รู้จริง ๆ จนกว่าคุณจะกำหนดโปรไฟล์และคุณอาจไม่ควรสนใจเกี่ยวกับการเพิ่มประสิทธิภาพจนกว่าคุณจะมีสิ่งที่ทำงานได้เพื่อเพิ่มประสิทธิภาพแต่คุณ "อาจจะ" ดี)

สิ่งที่ฉันพบว่าน่าสนใจจริงๆ (แม้ว่าจะไม่ส่งผลกระทบโดยเฉพาะอย่างยิ่งหรือทำให้มุมมองโลกแตก) เชื่อหรือไม่ว่าการสร้างตัวแปรชั่วคราวนั้นแล้วการเปรียบเทียบจะใช้ไบต์จำนวนเท่ากันในการเข้ารหัสเมื่อเปรียบเทียบโดยตรงกับเอาต์พุตคอมไพเลอร์ในเวอร์ชันของฉัน

นี่คือตัวอย่างจากobjdumpผลลัพธ์สำหรับเวอร์ชันของคุณ (ในการสร้างสิ่งนี้บนเครื่องโลคัลของคุณคำสั่งที่ฉันใช้หลังจากประกอบกับ nasm คือobjdump -Mx86-64,intel -D -S -s input.o)

0000000000000005 <loop1>:
loop1:
    cmp rcx, rsi    ; if ( i < size ) {
   5:   48 39 f1                cmp    rcx,rsi
    jae skip_loop
   8:   73 14                   jae    1e <skip_loop>
    
    mov r8d, [rdi + 4 * rcx]        ; make a temp variable so we can see this in step debugging
   a:   44 8b 04 8f             mov    r8d,DWORD PTR [rdi+rcx*4]
    cmp edx, r8d    ; if ( arr[i] == item ) {
   e:   44 39 c2                cmp    edx,r8d
    jne skip_if
  11:   75 06                   jne    19 <skip_if>
    mov rax, 1      ; return true;
  13:   b8 01 00 00 00          mov    eax,0x1
    ret
  18:   c3                      ret

ต่อไปนี้คือตัวอย่างข้อมูลจากเอาต์พุตสำหรับเวอร์ชันของคอมไพเลอร์ที่มีการดำเนินการเปรียบเทียบ

0000000000000011 <include.L3>:
.L3:
    cmp     [dword rdi+rax*4], edx
  11:   39 94 87 00 00 00 00    cmp    DWORD PTR [rdi+rax*4+0x0],edx
    jne     .L8
  18:   75 ef                   jne    9 <include.L8>
    mov     eax, 1
  1a:   b8 01 00 00 00          mov    eax,0x1
    ret
  1f:   c3                      ret

สังเกตว่าในเวอร์ชันของคุณการกำหนดให้กับตัวแปรชั่วคราวใช้เวลาสี่ไบต์ คุณระบุr8dรีจิสเตอร์เป็นรีจิสเตอร์ปลายทางดังนั้นนี่จึงไม่ใช่สิ่งที่แปลกใหม่ แต่คำสั่งเปรียบเทียบต่อไปนี้ต้องการเข้ารหัสเพียงสามไบต์:

44 8b 04 8f             mov    r8d,DWORD PTR [rdi+rcx*4]
44 39 c2                cmp    edx,r8d

เวอร์ชันของคอมไพเลอร์ข้ามการกำหนดตัวแปรระดับกลาง แต่คำสั่งที่เป็นผลลัพธ์ต้องการเจ็ดไบต์ในการเข้ารหัส

39 94 87 00 00 00 00    cmp    DWORD PTR [rdi+rax*4+0x0],edx

เพื่ออธิบายว่าทำไมผู้ zeroes พิเศษที่ว่าท้ายที่สุดผมจะยืมอีกครั้งจากการโพสต์ที่ยิ่งใหญ่นี้ที่คุณควรอ่านแน่นอน

ขนาดรหัสเครื่องที่เล็กลง [... ] เป็นข้อได้เปรียบเสมอ: ความหนาแน่นของโค้ดที่สูงขึ้นทำให้พลาดแคชคำสั่งน้อยลงและดึงคำสั่งได้ดีขึ้นและอาจถอดรหัสแบนด์วิดท์ได้

ในการขับรถกลับบ้านจุดนี้ให้เราอ่านเอกสารคำแนะนำการกระโดดตามเงื่อนไข (หน้า 1109 ในคู่มือรวม [เล่ม 1-4]):

การกระโดดตามเงื่อนไขทั้งหมดจะถูกแปลงเป็นการดึงรหัสของบรรทัดแคชหนึ่งหรือสองบรรทัดโดยไม่คำนึงถึงที่อยู่กระโดดหรือความสามารถในการแคช

ตอนนี้ฉันปล่อยลิงก์นี้ไปยังหมายเลขเวลาในการตอบสนองโปรแกรมเมอร์ทุกคนควรทราบเพื่อการจรรโลงใจของคุณแม้ว่าจะควรสังเกตว่าเอกสารนี้มาจากปี 2012 ก็ตามนี่คือเวอร์ชันอัปเดตที่ยอดเยี่ยมซึ่งคุณสามารถดูตัวเลขเวลาแฝงตามปี (รวมถึงปี 2020) แต่ฉัน ที่จริงเพิ่งค้นพบสิ่งนี้ด้วยตัวเองดังนั้นฉันยอมรับว่าฉันยังไม่ได้ตรวจสอบแหล่งที่มาเพื่อความถูกต้อง ฉันกำลังรวมไว้เพื่อความสมบูรณ์อย่างไรก็ตาม

เท่าที่ป้ายชื่อตัวเองมีความกังวลตั้งแต่loop1, skip_ifและskip_loopทุกคนมีเหตุผลที่เกี่ยวข้องกับการincludeย่อยผมจะแนะนำให้ใช้ฉลากท้องถิ่นให้มากขึ้นอย่างสังหรณ์ใจในการจัดระเบียบรหัสการชุมนุมของคุณ ป้ายกำกับท้องถิ่นมีประโยชน์อย่างยิ่งเนื่องจากชื่อรูทีนย่อยทำหน้าที่เป็นเนมสเปซประเภทหนึ่งซึ่งช่วยให้คุณสามารถนำชื่อเลเบลโลคัลที่กำหนดไว้ในนั้นมาใช้ซ้ำได้ คุณสามารถดูincludeเวอร์ชันด้านบนที่ประกอบโดย gcc โดยใช้ป้ายกำกับท้องถิ่น

คำแนะนำเดียวที่ฉันจะทำเกี่ยวกับลูปคือระวังการใช้การกระโดดตามเงื่อนไขที่เหมาะสมกับสถานการณ์ของคุณ จากเอกสารประกอบ:

คำว่า "น้อยกว่า" และ "มากกว่า" ใช้สำหรับการเปรียบเทียบจำนวนเต็มที่ลงนามและคำว่า "ด้านบน" และ "ด้านล่าง" ใช้สำหรับจำนวนเต็มที่ไม่ได้ลงชื่อ

นี่ไม่ใช่การอวดดีเช่นกัน ยกตัวอย่างเช่นคำสั่ง "กระโดดถ้าสูงกว่าหรือเท่ากัน" jaeในโค้ดของคุณ เป็นไปตามcmpคำสั่งซึ่งจะลบตัวถูกดำเนินการที่สองออกจากตัวดำเนินการตัวแรกและแก้ไขEFLAGSรีจิสเตอร์ให้สอดคล้องกัน โดยเฉพาะอย่างยิ่งsubคำสั่งระดับกลางจะดำเนินการทั้งการลบที่ลงชื่อและไม่ได้ลงนามการตั้งค่าแฟล็กโอเวอร์โฟลว์และการดำเนินการตามลำดับ อย่างไรก็ตามด้วยการใช้jaeคำสั่งคุณจะตรวจสอบแฟล็กพกพาโดยปริยายเท่านั้นดังนั้นหวังว่าเงื่อนไขตัวนับลูปและตัวหยุดของคุณจะเป็นประเภทเดียวกัน

มาตรฐาน C กำหนดวิธีการนี้ซึ่งจะช่วยลดข้อบกพร่องโดยการแปลงทั้งอย่างถูกต้องและปลอดภัยที่สุดและโดยการให้คำเตือนที่เป็นประโยชน์และแม้แต่ข้อความแสดงข้อผิดพลาด (ขึ้นอยู่กับการตั้งค่าความเข้มงวดในการคอมไพล์) แน่นอนว่าหากคุณกำลังจะเขียนภาษาแอสเซมบลีโดยตรงสิ่งนี้ไม่ได้ช่วยคุณได้แน่นอน

สำหรับการอ้างอิงEFLAGSโค้ดเงื่อนไขสามารถพบได้ในเล่ม 1 ภาคผนวก B ของคู่มือสำหรับนักพัฒนาซอฟต์แวร์สถาปัตยกรรมIntel® 64 และ IA-32และตารางอ้างอิงการกระโดดตามเงื่อนไขเริ่มต้นในหน้า 1106 ของเล่ม 2