Κονσόλα τσέπης

abs_branch:
    mov rax, rdi
    cmp rax, 0
    jge .done
    neg rax
.done:
    ret

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi
    cmp rdi, 0
    cmovge rax, rdi    ; the value in `rdi` is moved to `rax` if rdi >= 0
                       ; otherwise, it stays the same, i.e., -rdi
    ; now rax = abs(rdi)
    ret

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi. `neg` sets SF = 1 if the result is negative
    cmovs rax, rdi     ; if SF == 1 (i.e., rax < 0), replace rax with rdi
                       ; otherwise rax stays = -rdi, which is non-negative
    ; now rax = abs(rdi)
    ret

cmp rdi, rsi
setg al             ; al = 1 if rdi > rsi (signed), 0 otherwise
movzx eax, al       ; eax (and rax) = 1 or 0, with the upper bits cleared

Οδηγίες

Γράφεις firmware για το σύστημα βαθμολογίας μιας retro φορητής κονσόλας. Η CPU του μηχανήματος είναι μέτρια, και η οθόνη βαθμολογίας ανανεώνεται με σταθερό ρυθμό. Για να μένει ομαλή η εικόνα, οι ρουτίνες βαθμολογίας πρέπει να εκτελούνται σε προβλέψιμο αριθμό κύκλων ανεξάρτητα από το τι κάνει ο παίκτης.

Έχεις τέσσερις εργασίες.

1. Πρόσθεσε μπόνους χωρίς υπερχείλιση της οθόνης

Η περιοχή βαθμολογίας της οθόνης LCD της κονσόλας χωράει έξι δεκαδικά ψηφία. Δεν μπορεί να εμφανίσει κανέναν αριθμό πάνω από 999999. Όταν ένα μπόνους θα έσπρωχνε το τρέχον σύνολο πάνω από αυτό το όριο, το σύνολο που εμφανίζεται κρατιέται στο μέγιστο αντί να αναδιπλωθεί.

Όρισε μια συνάρτηση add_bonus που, δεδομένου ενός τρέχοντος συνόλου και ενός μπόνους προς πρόσθεση, επιστρέφει το νέο σύνολο περιορισμένο στο 999999. Τα ορίσματα, με τη σειρά, είναι:

1. total: το τρέχον σύνολο βαθμολογίας (πάντα μεταξύ 0 και 999999)
2. bonus: το μπόνους προς πρόσθεση (πάντα μη αρνητικό)

Η τιμή επιστροφής είναι total + bonus αν αυτό το άθροισμα είναι μικρότερο ή ίσο με 999999, και 999999 διαφορετικά:

add_bonus(500, 100);
// => 600
add_bonus(999990, 50);
// => 999999
add_bonus(999999, 0);
// => 999999

Τόσο τα ορίσματα όσο και η τιμή επιστροφής είναι προσημασμένοι ακέραιοι 64-bit.

2. Σύγκρινε δύο βαθμολογίες

Η κονσόλα κρατάει έναν μικρό πίνακα κατάταξης με τις καλύτερες πρόσφατες βαθμολογίες του παίκτη στο αρχείο αποθήκευσής της. Μετά από κάθε παιχνίδι, η νέα βαθμολογία εισάγεται στον πίνακα κατάταξης στη σωστή θέση. Η ρουτίνα ταξινόμησης ρωτάει ποια από τις δύο βαθμολογίες είναι μπροστά και περιμένει την απάντηση ως μικρό ακέραιο.

Όρισε μια συνάρτηση compare_scores που, δεδομένων δύο βαθμολογιών, επιστρέφει:

• +1 αν η πρώτη βαθμολογία είναι υψηλότερη
• -1 αν η πρώτη βαθμολογία είναι χαμηλότερη
• 0 αν οι δύο βαθμολογίες είναι ίσες

Παράδειγμα:

compare_scores(500, 300);
// => 1
compare_scores(300, 500);
// => -1
compare_scores(500, 500);
// => 0

Τόσο τα ορίσματα όσο και η τιμή επιστροφής είναι προσημασμένοι ακέραιοι 64-bit.

3. Επικύρωσε μια ακατέργαστη βαθμολογία

Η κονσόλα μπορεί να συνδεθεί με μια άλλη μονάδα μέσω του καλωδίου σύνδεσής της για να μοιραστεί βαθμολογίες μετά από έναν αγώνα multiplayer. Το καλώδιο έχει ηλεκτρικό θόρυβο και τα εισερχόμενα byte μερικές φορές αλλοιώνονται, παράγοντας τιμές πολύ κάτω από το επιτρεπτό ελάχιστο ή πολύ πάνω από το επιτρεπτό μέγιστο. Ο επικυρωτής περιορίζει κάθε εισερχόμενη βαθμολογία στο επιτρεπτό εύρος πριν τη δει το υπόλοιπο σύστημα.

Όρισε μια συνάρτηση validate_score που, δεδομένης μιας ακατέργαστης βαθμολογίας και των επιτρεπτών ορίων, επιστρέφει τη βαθμολογία περιορισμένη στο [min, max]. Τα ορίσματα, με τη σειρά, είναι:

1. score: η ακατέργαστη βαθμολογία που ελήφθη μέσω του καλωδίου σύνδεσης
2. min: η μικρότερη επιτρεπτή βαθμολογία
3. max: η μεγαλύτερη επιτρεπτή βαθμολογία

Η τιμή επιστροφής είναι min αν score < min, max αν score > max, και score διαφορετικά. Μπορείς να υποθέσεις ότι min <= max.

Παράδειγμα:

validate_score(450, 0, 500);
// => 450
validate_score(-50, 0, 1530);
// => 0
validate_score(1234567, 0, 2999);
// => 2999

Όλα τα ορίσματα και η τιμή επιστροφής είναι προσημασμένοι ακέραιοι 64-bit.

4. Παρακολούθησε τις δύο υψηλότερες βαθμολογίες

Στο τέλος κάθε συνεδρίας παιχνιδιού, η κονσόλα σαρώνει το αρχείο καταγραφής των πρόσφατων παιχνιδιών στο αρχείο αποθήκευσής της για να βρει τις δύο υψηλότερες βαθμολογίες που έχουν καταγραφεί ποτέ. Το αρχείο καταγραφής είναι ένας απλός πίνακας προσημασμένων ακεραίων 64-bit στη μνήμη. Η σάρωση διατρέχει τον πίνακα μία φορά και κρατάει δύο τρέχοντα μέγιστα: το υψηλότερο που έχει δει μέχρι στιγμής, και το δεύτερο υψηλότερο.

Σημείωσε ότι και οι δύο αριθμοί πρέπει να είναι τουλάχιστον 0. Κάθε αρνητικός αριθμός αγνοείται.

Μια πρώτη εκδοχή της συνάρτησης γράφτηκε με διαδοχικά υπό συνθήκη άλματα. Για κάθε υποψήφιο, ο κώδικας ρωτάει πού ταιριάζει (πάνω από το πρώτο, ανάμεσα στο πρώτο και το δεύτερο, ή πουθενά) και μετατοπίζει ανάλογα τα τρέχοντα μέγιστα, απορρίπτοντας κάθε αρνητικό αποτέλεσμα.

Αυτό δουλεύει. Ωστόσο, επειδή οι τιμές εισόδου είναι τυχαίες, κάθε άλμα υπό συνθήκη οδηγεί σε πολλές λανθασμένες προβλέψεις διακλάδωσης. Γι' αυτό αποφάσισες να ξαναγράψεις τον κύριο βρόχο χωρίς διακλαδώσεις.

Παρακάτω είναι η συνάρτηση με το τμήμα με τις διακλαδώσεις σχολιασμένο:

; rdi = output buffer for two elements, rsi = input array address, rdx = number of elements in array
top_two:
    xor r8d, r8d                   ; first  = 0
    xor r9d, r9d                   ; second = 0
    xor ecx, ecx                   ; index = 0
    test rdx, rdx
    jz .done

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                       BRANCHY CODE TO REFACTOR
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;.loop:
;    mov rax, qword [rsi + 8*rcx]   ; candidate
;    inc rcx
;    cmp rax, r8
;    jle .check_second              ; candidate <= first, try second
;    mov r9, r8                     ; second = first
;    mov r8, rax                    ; first  = candidate
;    cmp rcx, rdx
;    jb .loop                       ; go to next iteration
;    jmp .done                      ; otherwise, we are done
;.check_second:
;    cmp rax, r9
;    jle .loop                      ; candidate <= second, go to next iteration
;    mov r9, rax                    ; second = candidate
;    cmp rcx, rdx
;    jb .loop                       ; go to next iteration
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

.done:
    mov qword [rdi], r8            ; save first
    mov qword [rdi + 8], r9        ; save second
    ret

Αντικατέστησε το σχολιασμένο τμήμα με υλοποίηση χωρίς διακλαδώσεις. Το μόνο άλμα που επιτρέπεται στον νέο κώδικα είναι αυτό που πηγαίνει πίσω στην αρχή του βρόχου για να ελέγξει ένα νέο στοιχείο του πίνακα.

Η συνάρτηση δεν έχει τιμή επιστροφής και δέχεται τα ίδια ορίσματα με την εκδοχή με τις διακλαδώσεις:

1. out: buffer εξόδου όπου η συνάρτηση θα γράψει τις δύο κορυφαίες μη αρνητικές βαθμολογίες σε φθίνουσα σειρά, ως προσημασμένους ακεραίους 64-bit
2. array: πίνακας εισόδου με προσημασμένους ακεραίους 64-bit
3. length: ο αριθμός των στοιχείων του πίνακα, ως ανυπόγραφος ακέραιος 64-bit