Console de poche

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

Instructions

Tu écris le micrologiciel du système de score d'une console portable rétro. Le processeur de la machine est modeste, et l'affichage du tableau des scores se rafraîchit à une cadence fixe. Pour que l'image reste fluide, les routines de score doivent s'exécuter en un nombre prévisible de cycles, quoi que fasse le joueur.

Tu as quatre tâches.

1. Ajoute un bonus sans faire déborder l'affichage

La zone de score de l'écran LCD de la console portable peut afficher six chiffres décimaux. Elle ne peut pas afficher de nombre supérieur à 999999. Lorsqu'un bonus ferait dépasser cette limite au total en cours, le total affiché est maintenu au maximum plutôt que de boucler.

Définis une fonction add_bonus qui, étant donné un total courant et un bonus à ajouter, renvoie le nouveau total plafonné à 999999. Les arguments, dans l'ordre, sont :

1. total : le total de score actuel (toujours compris entre 0 et 999999)
2. bonus : le bonus à ajouter (toujours positif ou nul)

La valeur de retour est total + bonus si cette somme est inférieure ou égale à 999999, et 999999 sinon :

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

Les deux arguments et la valeur de retour sont des entiers signés de 64 bits.

2. Compare deux scores

La console portable conserve un petit classement des meilleurs scores récents du joueur dans son fichier de sauvegarde. Après chaque partie, le nouveau score est inséré dans le classement à la bonne position. La routine de tri demande lequel des deux scores est devant et attend la réponse sous forme d'un petit entier.

Définis une fonction compare_scores qui, étant donné deux scores, renvoie :

• +1 si le premier score est supérieur
• -1 si le premier score est inférieur
• 0 si les deux scores sont égaux

Exemple :

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

Les deux arguments et la valeur de retour sont des entiers signés de 64 bits.

3. Valide un score brut

La console portable peut se connecter à une autre unité via son câble de liaison pour partager des scores après une partie multijoueur. Le câble est parasité électriquement et les octets entrants sont parfois corrompus, ce qui produit des valeurs bien inférieures au minimum autorisé ou bien supérieures au maximum autorisé. Le validateur ramène chaque score entrant dans la plage autorisée avant que le reste du système ne le voie.

Définis une fonction validate_score qui, étant donné un score brut et les limites autorisées, renvoie le score ramené dans [min, max]. Les arguments, dans l'ordre, sont :

1. score : le score brut reçu par le câble de liaison
2. min : le plus petit score autorisé
3. max : le plus grand score autorisé

La valeur de retour est min si score < min, max si score > max, et score sinon. Tu peux supposer que min <= max.

Exemple :

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

Tous les arguments et la valeur de retour sont des entiers signés de 64 bits.

4. Suis les deux meilleurs scores

À la fin de chaque session de jeu, la console portable parcourt le journal des parties récentes dans son fichier de sauvegarde pour trouver les deux meilleurs scores jamais enregistrés. Le journal est un simple tableau d'entiers signés de 64 bits en mémoire. Le parcours traverse le tableau une seule fois et conserve deux maximums courants : le plus élevé vu jusqu'ici, et le deuxième plus élevé.

Note que les deux nombres doivent être au moins égaux à 0. Tout nombre négatif est ignoré.

Une première version de la fonction a été écrite avec des sauts conditionnels en cascade. Pour chaque candidat, le code détermine où il se place (au-dessus du premier, entre le premier et le deuxième, ou nulle part) et décale les maximums courants en conséquence, en écartant tout résultat négatif.

Ça fonctionne. Cependant, comme les valeurs d'entrée sont aléatoires, chaque saut conditionnel entraîne de nombreuses mauvaises prédictions de branchement. C'est pourquoi tu as décidé de réécrire la boucle principale pour qu'elle soit sans branchements.

Voici la fonction avec la partie à branchements commentée :

; 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

Remplace la section commentée par une implémentation sans branchements. Le seul saut autorisé dans le nouveau code est celui qui revient au début de la boucle pour vérifier un nouvel élément du tableau.

La fonction n'a pas de valeur de retour et prend les mêmes arguments que la version à branchements :

1. out : tampon de sortie où la fonction écrira les deux meilleurs scores non négatifs par ordre décroissant, sous forme d'entiers signés de 64 bits
2. array : tableau d'entrée d'entiers signés de 64 bits
3. length : le nombre d'éléments du tableau, sous forme d'un entier non signé de 64 bits