7.2 דפוסים באסמבלי פתרון

פתרון - דפוסים באסמבלי

פתרון תרגיל 1 - זיהוי מבנה C מאסמבלי

קטע א:

        cmp     edi, 0
        jge     .L1
        neg     edi
.L1:
        mov     eax, edi
        ret

זהו if בלי else. ניתוח:
- cmp edi, 0; jge .L1 - אם edi >= 0, דלג (כלומר ה-if הוא if (x < 0))
- neg edi - הופך את הסימן (x = -x)
- מחזיר את edi

שחזור:

int abs_value(int x) {
    if (x < 0) {
        x = -x;
    }
    return x;
}

זו פונקציית ערך מוחלט.

---

קטע ב:

        xor     eax, eax
        xor     ecx, ecx
.L1:
        add     eax, ecx
        inc     ecx
        cmp     ecx, esi
        jl      .L1
        ret

זוהי לולאת for (מאופטמת, בלי קפיצה ראשונית לתנאי). ניתוח:
- xor eax, eax - sum = 0
- xor ecx, ecx - i = 0
- גוף הלולאה: sum += i, i++
- תנאי: i < esi (הארגומנט השני, n)

שחזור:

int sum_range(int unused, int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += i;
    }
    return sum;
}

סכום כל המספרים מ-0 עד n-1.

---

קטע ג:

        mov     eax, edi
.L1:
        test    eax, eax
        je      .L2
        mov     edx, eax
        shr     edx, 1
        add     eax, edx
        add     eax, 1
        jmp     .L1
.L2:
        ret

זוהי לולאת while. ניתוח:
- eax מתחיל עם הארגומנט (edi)
- התנאי: while (eax != 0)
- בגוף: edx = eax / 2 (shr 1 = חילוק ב-2 unsigned), eax = eax + eax/2 + 1

שחזור:

int func(int x) {
    while (x != 0) {
        x = x + x / 2 + 1;
    }
    return x;
}

שימו לב: פונקציה זו בעצם לא תסתיים עבור רוב הקלטים החיוביים (x ימשיך לגדול עד overflow). היא עשויה לסיים כש-x מגיע ל-0 דרך overflow.

---

קטע ד:

        cmp     edi, 3
        ja      .default
        lea     rax, [rip + .jump_table]
        movsxd  rdx, dword [rax + rdi*4]
        add     rax, rdx
        jmp     rax

זהו switch/case עם טבלת קפיצות. ניתוח:
- cmp edi, 3; ja .default - אם edi > 3 (unsigned) - קפוץ ל-default
- הcase-ים הם 0, 1, 2, 3 (ערכים רצופים)
- הטבלה מכילה offset-ים יחסיים לכתובת הטבלה עצמה
- rdi*4 - כל כניסה בטבלה היא 4 בתים (dword)

שחזור (מבנה כללי):

switch (x) {
    case 0: /* ... */ break;
    case 1: /* ... */ break;
    case 2: /* ... */ break;
    case 3: /* ... */ break;
    default: /* ... */ break;
}

---

פתרון תרגיל 2 - חיזוי התנהגות

קטע א (edi = 5):

func:
        mov     eax, 1         ; eax = 1
        cmp     edi, 1         ; 5 > 1 -> לא קופץ
        jle     .end
.loop:
        imul    eax, edi       ; eax = eax * edi
        dec     edi            ; edi--
        cmp     edi, 1         ; edi > 1?
        jg      .loop
.end:
        ret

מעקב ידני:
| איטרציה | eax | edi |
|---------|------|-----|
| התחלה | 1 | 5 |
| 1 | 15 = 5 | 4 |
| 2 | 54 = 20 | 3 |
| 3 | 203 = 60 | 2 |
| 4 | 602 = 120 | 1 |

edi = 1, התנאי edi > 1 לא מתקיים, הלולאה נגמרת.

ערך ההחזרה: 120 (זו עצרת - 5!)

---

קטע ב (edi = 6):

func:
        xor     eax, eax       ; eax = 0
        test    edi, 1         ; 6 & 1 = 0 -> ZF=1 (6 זוגי)
        jnz     .odd           ; לא קופץ (ZF=1)
        mov     eax, 1         ; eax = 1
.odd:
        ret

edi = 6 בבינארי הוא 110. test edi, 1 בודק את הביט התחתון (0 = זוגי, 1 = אי-זוגי).
6 הוא זוגי, לכן הביט התחתון הוא 0, ולכן ZF=1, ולכן jnz לא קופץ.

ערך ההחזרה: 1 (הפונקציה מחזירה 1 אם המספר זוגי, 0 אם אי-זוגי)

---

קטע ג (edi = 10, esi = 3):

func:
        mov     eax, edi       ; eax = 10
        xor     edx, edx       ; edx = 0 (החלק העליון של המחולק)
        div     esi            ; eax = 10/3 = 3, edx = 10%3 = 1
        mov     eax, edx       ; eax = edx = 1
        ret

הפקודה div esi מחלקת את edx:eax ב-esi. התוצאה: eax = מנה (3), edx = שארית (1).
הפונקציה מחזירה את השארית.

ערך ההחזרה: 1 (זו פונקציית מודולו: 10 % 3 = 1)

---

פתרון תרגיל 3 - התאמת קוד C לדיסאסמבלי

פונקציה D מתאימה לקטע 1:

        mov     eax, edi           ; eax = a
        sub     eax, esi           ; eax = a - b
        mov     ecx, esi
        sub     ecx, edi           ; ecx = b - a
        cmp     edi, esi           ; a > b?
        cmovle  eax, ecx           ; אם a <= b, eax = b - a
        ret

ההוראה cmovle (conditional move if less or equal) מחליפה את eax רק אם a <= b. זו אופטימיזציה - הקומפיילר חישב את שתי התוצאות (a-b ו-b-a) ובוחר ביניהן בלי קפיצה. זה המימוש של func_d שמחזירה |a-b|.

---

פונקציה B מתאימה לקטע 2:

        xor     eax, eax           ; count = 0
        test    edi, edi
        je      .end               ; if (x == 0) return 0
.loop:
        mov     ecx, edi
        and     ecx, 1             ; ecx = x & 1 (הביט התחתון)
        add     eax, ecx           ; count += (x & 1)
        shr     edi, 1             ; x >>= 1
        test    edi, edi
        jne     .loop              ; while (x != 0)
.end:
        ret

לולאת while שסופרת ביטים דלוקים (1) במספר. x & 1 בודק את הביט התחתון, x >>= 1 מזיז ימינה. זו func_b - popcount.

---

פונקציה A מתאימה לקטע 3:

        mov     eax, [rdi]         ; max = arr[0]
        mov     ecx, 1             ; i = 1
.loop:
        cmp     ecx, esi           ; i >= n?
        jge     .end
        mov     edx, [rdi + rcx*4] ; edx = arr[i]
        cmp     edx, eax           ; arr[i] > max?
        cmovg   eax, edx           ; אם כן, max = arr[i]
        inc     ecx                ; i++
        jmp     .loop
.end:
        ret

הגישה [rdi + rcx*4] (scale=4) מעידה על מערך int. הפונקציה מחפשת ערך מקסימלי - func_a.

---

פונקציה C מתאימה לקטע 4:

        xor     ecx, ecx           ; i = 0
.loop:
        cmp     ecx, esi           ; i >= n?
        jge     .end
        shl     dword [rdi + rcx*4], 1  ; arr[i] *= 2 (הזזה שמאלה = כפל ב-2)
        inc     ecx                ; i++
        jmp     .loop
.end:
        ret

לולאה על מערך int (scale=4) שמכפילה כל איבר ב-2. שימו לב לאופטימיזציה: shl ..., 1 במקום imul ..., 2. זו func_c.

---

פתרון תרגיל 4 - זיהוי אופטימיזציות

קטע א:

        lea     eax, [rdi + rdi*4]     ; eax = rdi + rdi*4 = rdi * 5
        ret

אופטימיזציה: כפל ב-5 באמצעות lea במקום imul edi, 5.
קוד C:

int multiply_by_5(int x) {
    return x * 5;
}

---

קטע ב:

        mov     eax, edi
        shr     eax, 3                 ; eax = edi / 8 (unsigned)
        ret

אופטימיזציה: חילוק ב-8 באמצעות shr (הזזה ימינה ב-3 ביטים = חילוק ב-2^3 = 8).
קוד C:

unsigned int divide_by_8(unsigned int x) {
    return x / 8;
}

שימו לב: shr (unsigned shift right) ולא sar, מה שמעיד שהמשתנה הוא unsigned.

---

קטע ג:

        xor     eax, eax               ; eax = 0
        test    edi, edi
        setne   al                     ; al = 1 אם edi != 0
        ret

אופטימיזציה: המרה לבוליאני באמצעות setne במקום if/else.
קוד C:

int is_nonzero(int x) {
    return x != 0;
}

או שקול:

int to_bool(int x) {
    return !!x;
}

---

קטע ד:

        lea     eax, [rdi + rdi*2]     ; eax = rdi * 3
        shl     eax, 2                 ; eax = eax * 4 = rdi * 12
        ret

אופטימיזציה: כפל ב-12 = כפל ב-3 (lea) ואז כפל ב-4 (shl). הקומפיילר פירק 12 = 3 * 4 ומשתמש בשתי פעולות מהירות במקום imul.
קוד C:

int multiply_by_12(int x) {
    return x * 12;
}

---

קטע ה:

        mov     eax, edi
        sar     eax, 31                ; eax = 0 (חיובי) או -1 (שלילי)
        shr     eax, 30                ; eax = 0 (חיובי) או 3 (שלילי)
        add     eax, edi               ; תיקון עיגול
        sar     eax, 2                 ; חילוק ב-4
        ret

אופטימיזציה: חילוק signed ב-4 עם תיקון עיגול. sar (arithmetic shift right) שומר על הסימן, אבל חילוק signed של מספרים שליליים דורש תיקון (כי C מעגל לכיוון אפס, לא לכיוון מינוס אינסוף).

הסבר מפורט:
- sar eax, 31 - מפיק 0 לחיוביים, -1 (0xFFFFFFFF) לשליליים
- shr eax, 30 - מפיק 0 לחיוביים, 3 לשליליים (0xFFFFFFFF >> 30 = 3)
- add eax, edi - עבור שליליים, מוסיף 3 כדי לתקן עיגול
- sar eax, 2 - חילוק ב-4

קוד C:

int divide_by_4(int x) {
    return x / 4;
}

---

פתרון תרגיל 5 - שחזור פונקציה מלאה

mystery:
        push    rbp
        mov     rbp, rsp
        push    rbx
        mov     rbx, rdi               ; rbx = ארגומנט ראשון (מצביע)
        xor     eax, eax               ; eax = 0
        test    rbx, rbx               ; מצביע == NULL?
        je      .end                   ; אם כן - החזר 0
        xor     eax, eax               ; eax = 0 (מונה)
.loop:
        cmp     byte [rbx + rax], 0    ; הבית במיקום rax == 0?
        je      .end                   ; אם כן - סיום
        inc     rax                    ; rax++
        jmp     .loop
.end:
        pop     rbx
        pop     rbp
        ret

ניתוח:
1. הפונקציה מקבלת מצביע ב-rdi (שנשמר ב-rbx)
2. בודקת אם המצביע הוא NULL - אם כן, מחזירה 0
3. מאתחלת מונה (rax) ל-0
4. בלולאה: בודקת אם byte [rbx + rax] שווה 0 (null terminator)
5. אם לא - מגדילה את המונה ב-1 וממשיכה
6. מחזירה את המונה ב-rax

cmp byte [rbx + rax], 0 בודק בית אחד (char) בכתובת rbx+rax. הלולאה סופרת כמה בתים יש עד שמגיעים ל-null byte (\0).

שחזור:

size_t mystery(const char *str) {
    if (str == NULL)
        return 0;

    size_t len = 0;
    while (str[len] != '\0') {
        len++;
    }
    return len;
}

זוהי מימוש של strlen - ספירת אורך מחרוזת. הפונקציה עוברת על המחרוזת תו-תו עד שמוצאת את ה-null terminator ומחזירה את מספר התווים.