Кишенькова консоль

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

Вказівки

Ми пишемо прошивку для системи підрахунку очок у ретро кишеньковій консолі. Процесор машини доволі скромний, а табло з результатами оновлюється з фіксованою частотою. Щоб зображення залишалося плавним, рутини підрахунку очок мають виконуватися за передбачувану кількість тактів, незалежно від того, що робить гравець.

На нас чекають чотири завдання.

1. Додати бонус, не переповнивши дисплей

Ділянка результатів на РК-дисплеї консолі вміщує шість десяткових цифр. Вона не може показати жодного числа, більшого за 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-бітні знакові цілі числа.

2. Порівняти два результати

Консоль зберігає невелику таблицю лідерів із найкращими недавніми результатами гравця у своєму файлі збереження. Після кожної гри новий результат вставляється в таблицю лідерів на потрібну позицію. Рутина сортування запитує, котрий із двох результатів випереджає, і приймає відповідь у вигляді невеликого цілого числа.

Визначте функцію compare_scores, яка, отримавши два результати, повертає:

• +1, якщо перший результат вищий
• -1, якщо перший результат нижчий
• 0, якщо обидва результати рівні

Приклад:

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

І аргументи, і повернене значення - 64-бітні знакові цілі числа.

3. Перевірити необроблений результат

Консоль може зʼєднатися з іншим пристроєм через кабель звʼязку, щоб обмінятися результатами після матчу на кількох гравців. Кабель електрично шумний, і вхідні байти час від часу псуються, даючи значення далеко нижчі за допустимий мінімум або далеко вищі за допустимий максимум. Валідатор обмежує кожен вхідний результат допустимим діапазоном, перш ніж його побачить решта системи.

Визначте функцію 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-бітні знакові цілі числа.

4. Відстежити два найвищі результати

Наприкінці кожного ігрового сеансу консоль сканує журнал недавніх ігор у своєму файлі збереження, щоб знайти два найвищі результати за весь час. Журнал - це звичайний масив 64-бітних знакових цілих чисел у памʼяті. Сканування проходить масивом один раз і тримає два поточні максимуми: найвищий, побачений досі, і другий за висотою.

Звернімо увагу, що обидва числа мають бути не меншими за 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: буфер вихідних даних, куди функція запише два найвищі невідʼємні результати в порядку спадання, як 64-бітні знакові цілі числа
2. array: вхідний масив 64-бітних знакових цілих чисел
3. length: кількість елементів у масиві, як 64-бітне беззнакове ціле число