Donkey Kong Country 2 et l’open bus

• Certaines sections de tonneaux rotatifs de Donkey Kong Country 2 présentent, dans l’ancien émulateur SNES ZSNES, un bug où le tonneau continue de tourner même après avoir relâché les touches directionnelles ; la cause est l’absence d’implémentation du comportement open bus
• Sur une vraie SNES, lorsqu’on lit une adresse non mappée, on relit la dernière valeur présente sur le bus de données, et DKC2 s’appuie sur cette particularité lors de la lecture de $2000/$2001 dans la bank $B3
• La routine en cause effectue un XOR entre l’ancienne direction du tonneau et la nouvelle, puis exécute and $2000 ; sur le matériel réel, cette lecture open bus 16 bits renvoie 0x2020, ce qui permet de déterminer le franchissement d’une limite de direction
• Si une lecture open bus renvoie 0, comme dans ZSNES, le résultat du AND est toujours 0, la branche de fin de rotation n’est jamais exécutée, et le tonneau continue de tourner jusqu’à ce qu’on appuie dans la direction opposée
• Il est très probable que l’instruction aurait dû être and #$2000 ; dans une révision de la ROM, remplacer l’opcode à $33EDAC de 0x2D par 0x29 permet un fonctionnement normal même sans open bus

---

Le phénomène des tonneaux rotatifs qui ne s’arrêtent pas dans ZSNES

• Donkey Kong Country 2 contient un vieux bug où les tonneaux rotatifs de certains niveaux ne fonctionnent pas correctement dans ZSNES
• En fonctionnement normal, le joueur ne peut contrôler la rotation que lorsqu’il maintient une direction gauche ou droite à l’intérieur du tonneau
• Dans ZSNES, après avoir appuyé une fois à gauche ou à droite, le tonneau continue de tourner dans cette direction ; si l’on appuie dans l’autre sens, il continue alors de tourner dans le sens opposé
• Dans les passages plus avancés, les tonneaux sont placés au-dessus de pics ou de dangers, si bien que ce bug augmente fortement la difficulté du niveau par rapport à l’intention des développeurs
• Le même problème semble avoir été découvert par Anomie il y a environ 20 ans et corrigé dans Snes9x ; à l’époque, la correction ne consistait pas à émuler complètement l’open bus, mais à coder en dur les valeurs d’adresses précises dont dépend le jeu
• Dans ZSNES, ce bug n’a finalement jamais été corrigé, et la dernière version du projet date de 2007

L’open bus de la SNES et l’adressage du 65816

• Sur SNES, lire une adresse mémoire invalide ne fait généralement pas planter le programme
• Lorsqu’une adresse non mappée est lue, le CPU relit la dernière valeur qui se trouvait sur le bus de données : c’est le comportement open bus
• Le CPU principal de la SNES est le 65C816, c’est-à-dire le 65816, intégré au package Ricoh 5A22 S-CPU
• Le 65816 est une extension 16 bits du 6502 ; sur SNES, il utilise un bus d’adresses 24 bits, mais la plupart des adresses sont formées par la combinaison d’une bank 8 bits et d’un offset 16 bits
• Beaucoup d’instructions utilisent en interne des adresses 16 bits, avec le program bank register pour le fetch d’instructions et le data bank register pour les accès aux données
• Dans l’état des tonneaux rotatifs de DKC2, le jeu lit $2000 et $2001 dans la bank $B3 ; ces adresses ne sont mappées nulle part dans la bank $B3, ce qui en fait des lectures open bus

Les accès mémoire de la routine problématique

• Lorsque les touches gauche/droite sont relâchées à l’intérieur d’un tonneau rotatif, la routine exécutée à chaque frame effectue une lecture open bus
• L’état initial est le suivant : le data bank register vaut $B3, la direct page vaut $0000, et les flags M/X sont tous deux clear, ce qui rend les registres et les accès mémoire 16 bits
• Cette routine utilise plusieurs adresses dans la plage $0000-$2001
  • $0EE6 : direction actuelle du tonneau
  • $0E0A : quantité de rotation par frame
  • $0032 : emplacement qui semble être une variable temporaire
• Dans les banks $00-$3F et $80-$BF, $0000-$1FFF est mappé sur les 8 premiers Ko des 128 Ko de WRAM de la console
• $2000-$20FF est une zone non mappée, donc l’instruction and $2000 devient une lecture open bus

Comment 0x2020 sert à déterminer la fin de rotation

• La routine ajoute la quantité de rotation à la direction actuelle pour produire une nouvelle direction, puis l’enregistre dans une variable temporaire
• Elle effectue ensuite un XOR entre l’ancienne direction et la nouvelle, applique and $2000 au résultat, puis vérifie si le résultat vaut 0
• Sur une vraie SNES, and $2000, qui est une lecture open bus 16 bits, renvoie toujours 0x2020
  • Le code machine de and $2000 est 2D 00 20
  • Comme le 65816 utilise un bus de données 8 bits, une lecture 16 bits est réalisée via deux lectures 8 bits
  • Dans ce cas, le dernier octet lu est le high byte de l’adresse, 0x20, donc 0x20 est renvoyé deux fois
• Le comportement réel est donc fonctionnellement équivalent à and #$2020
• Si le résultat du AND vaut 0, la nouvelle direction est enregistrée telle quelle et la rotation continue à la frame suivante
• S’il n’est pas nul, la quantité de rotation est mise à 0, 0x1000 est ajouté à la nouvelle direction, puis un masque 0xE000 est appliqué afin d’aligner le tonneau sur la direction multiple de 0x2000 la plus proche

Pourquoi la rotation continue dans ZSNES

• La valeur de direction du tonneau semble utiliser une échelle où 0x0000 pointe vers le bas, 0x4000 vers la gauche, etc.
• Le tonneau analysé a une quantité de rotation horaire de 0x0300 et une quantité de rotation antihoraire de 0xFD00, ce qui donne un tour complet en un peu plus de 85 frames
• À 60 fps, cela représente un peu moins de 1,5 seconde
• Dans l’opération AND avec 0x2020, le changement réellement significatif est le bit 13, soit 0x2000
• Dans la valeur de direction, un changement de 0x2000 correspond à un passage d’un cran de direction principale ou diagonale
• Sur le matériel normal, lorsque les touches directionnelles sont relâchées, le tonneau continue de tourner jusqu’à la direction principale ou diagonale suivante, puis s’arrête en pointant exactement dans cette direction
• Si la lecture open bus renvoie toujours 0, le résultat du AND est lui aussi toujours 0, et le code de fin de rotation n’est jamais exécuté

Probable faute de frappe et résultat du patch de ROM

• and $2000 est une instruction à adressage absolute, alors que, logiquement, il est très probable qu’il aurait fallu utiliser and #$2000 en adressage immediate
• Sur le matériel réel, comme l’open bus renvoie 0x2020, and $2000 fonctionne par hasard comme prévu
• Ce comportement fortuit dépend de la condition selon laquelle les 6 bits de poids faible de la quantité de rotation par frame sont toujours à 0, ce qui rend 0x2020 fonctionnellement équivalent à 0x2000
• L’opcode erroné est exécuté dans la bank $B3 à l’offset $EDAC et, dans la révision analysée, il est mappé à $33EDAC dans la ROM de 4 Mo du jeu
• En remplaçant cet octet de 0x2D par 0x29, les tonneaux rotatifs fonctionnent normalement même si les lectures open bus renvoient toujours 0
• L’emplacement exact dans la ROM peut varier dans d’autres révisions du jeu
• Comme le jeu fonctionne correctement dans presque tous les émulateurs SNES à l’exception du vieux ZSNES, ce cas relève davantage de l’analyse d’un comportement dépendant du matériel que d’un patch réellement pratique

[GN⁺]

Avis sur Hacker News

• J’ai perdu énormément de temps dans ma vie à cause d’erreurs du genre, en écrivant de l’assembleur 6502, oublier le # devant une valeur immédiate et finir par faire un accès mémoire
  Comme dans cet exemple, il arrive souvent que ça fonctionne par hasard dans certains cas. Le pire, c’est quand on dépend non pas d’un bus flottant, mais de RAM non initialisée : à cause des caractéristiques de la DRAM, ça peut toujours marcher sur ma machine ou dans mon émulateur, puis casser sur la machine de quelqu’un d’autre qui utilise une autre puce DRAM. En général, on s’en rend compte sur la machine de la party, 15 minutes avant la présentation à une demoparty

  • Je me demande s’il a existé des architectures combinant un CPU 6502 et de la mémoire dynamique. D’après mon expérience limitée, il me semble que cette plateforme utilisait toujours de la RAM statique
  • Le 6502 a été mon premier langage assembleur, et j’ai toujours fait la distinction ainsi : LDA #2 veut dire « charger le nombre 2 dans A », tandis que LDA 2 veut dire « charger dans A la valeur située à l’emplacement mémoire 2 »
  • Dans ce genre de situation, passer le code dans un LLM peut vraiment aider. Ces fautes de frappe ou erreurs ont un impact important mais échappent très facilement à l’œil humain, alors que les LLM les repèrent plutôt bien

• Comme Open Bus était écrit avec des majuscules dans le titre, j’ai d’abord commencé à lire en pensant qu’il s’agissait du nom propre d’un vieux protocole ou standard de bus dont je n’avais jamais entendu parler
  En lisant, j’ai compris que cela voulait dire que le décodeur des lignes d’adresse n’activait aucun périphérique mémoire à l’adresse spécifiée $2000, laissant donc le bus dans un état « ouvert », connecté à rien. C’est assez amusant que le problème d’un # oublié dans l’adressage immédiat n’apparaisse qu’avec un vieil émulateur qui ne traitait pas les lectures mémoire comme le vrai matériel. La correction consistant à utiliser l’adressage immédiat plutôt que l’adressage absolu évite une lecture mémoire, donc l’exécution devrait aussi être plus rapide. Sur ce bloc de code, on peut gagner environ 2 µs, mais cela n’a probablement de sens que sur bare metal, et l’émulateur n’a sans doute de toute façon pas une précision temporelle parfaite

  • Rare a plusieurs exemples de jeux qui passaient très bien les tests, puis dont des bugs cachés ne sont apparus que des années plus tard sur de nouvelles architectures. Cela ne veut pas dire que les autres studios n’en ont pas, simplement que Rare est un nom facile à citer sur ce sujet
    Donkey Kong 64 avait une fuite mémoire qui, à ma connaissance, faisait planter le jeu après 8 à 9 heures de jeu continu, une durée irréaliste pour l’époque. Elle n’a pas été détectée pendant le développement, mais avec les états de sauvegarde d’un émulateur, si l’on continue au lieu d’utiliser la sauvegarde interne du jeu, ce temps s’accumule vite. L’historique reste toutefois flou. Certaines sources affirment que l’inclusion du Memory Pak était une mesure de dernière minute destinée à masquer le bug en repoussant le crash de 8–9 heures à 13–20 heures, mais des recherches récentes suggèrent plutôt que c’était une coïncidence et que Rare ou Nintendo n’ont pas sorti le jeu en ayant connaissance de ce bug
  • Certains émulateurs SNES sont aujourd’hui, à ce stade, pratiquement parfaits, y compris côté timings [0]. Cela dit, sauf cas exceptionnel, 2 µs ne devraient pas produire de différence perceptible
    [0] https://arstechnica.com/gaming/2021/06/how-snes-emulators-go...

• En travaillant sur la fonction RunAhead de RetroArch et en vérifiant les moments où les états de sauvegarde ne correspondaient pas, j’ai déjà vu SNES Puyo Puyo utiliser l’open bus du PPU
  Après avoir chargé un état, la valeur lue depuis le PPU Open Bus était différente, si bien que les journaux de trace d’exécution du CPU ne correspondaient plus

• Je ne fais pas toujours des erreurs typiques de la famille 6502, mais quand ça arrive, c’est généralement que j’ai écrit une adresse mémoire au lieu d’une valeur immédiate
  C’est une erreur extrêmement courante et facile à commettre, et je suis convaincu que Chuck Peddle lui-même regrettait profondément la syntaxe qui consiste à préfixer les valeurs immédiates avec #, comme dans #$1234. J’ai configuré mon IDE pour afficher # en rouge vif, et ça aide un peu. Même les dieux de l’assembleur chez Rare se sont fait avoir par le même problème

  • Il y a longtemps, j’ai rencontré un problème similaire avec le mode intel_syntax noprefix de l’assembleur GNU
    Dans les instructions pouvant accepter à la fois une valeur immédiate et une adresse mémoire, il existait une ambiguïté syntaxique : une constante nommée utilisée en valeur immédiate, mais référencée plus loin, pouvait être interprétée comme une référence à un symbole inconnu. Résultat : au lieu de la valeur immédiate attendue, l’instruction était assemblée avec une adresse mémoire factice qui serait remplie à l’édition de liens par l’adresse de relocation du symbole. C’était pénible à déboguer
  • Des jeux d’instructions comme ARM rendent ce genre d’erreur pratiquement impossible. Pour manipuler la mémoire, il faut utiliser une autre instruction

• J’aime ce genre d’article. J’ai toujours l’impression de ne suivre le code assembleur qu’à environ 60 %, donc les explications en prose à côté aident vraiment
  C’est aussi amusant d’entendre parler de bugs dans de vieux logiciels que personne n’avait compris, ou que personne n’avait peut-être même remarqués jusqu’à présent

  • L’une des raisons qui rendent les systèmes de cette époque fascinants, c’est l’absence des mécanismes modernes de vérification que l’on considère aujourd’hui comme acquis presque partout
    Des mécanismes indispensables pour les systèmes connectables au réseau, et devenus assez bon marché pour être intégrés même dans des architectures embarquées totalement isolées. Sur la NES d’origine, beaucoup de lectures et d’écritures ne faisaient guère plus que basculer une tension sur une ligne quelque part, et ensuite ce qui arrivait arrivait. L’effet voulu était obtenu en basculant la tension de façon très contrôlée, exactement synchronisée avec le signal indiquant l’intervalle de blanking du CRT. Certaines animations de Super Mario Bros 3 basculaient un multiplexeur de RAM pour sélectionner l’une de plusieurs banques de données de sprites, de sorte que lorsque le matériel graphique récupérait les sprites, il lisait depuis une puce entièrement différente avec une apparence légèrement différente. Comme le timing TV était crucial, il fallait aussi publier des versions logicielles séparées pour les régions TV NTSC et PAL ; les deux systèmes ont des fréquences de balayage différentes, et cette fréquence servait d’horloge pour piloter la logique de rendu. C’était vraiment une époque brutale

• À ma connaissance, l’open bus ne se voit que sur les premiers systèmes qui utilisaient un simple bus synchrone
  Pour la plupart des autres systèmes, accéder à une adresse inexistante renvoie, je crois, une valeur constante remplie uniquement de 0 ou uniquement de 1. C’est parce que le protocole de bus dispose d’un handshake permettant au maître de savoir qu’il n’y a pas de réponse ; dans la terminologie PCI, cela correspond à un « master abort »

• L’open bus signifie littéralement que les lignes du bus de données sont en circuit ouvert.
  Le CPU a placé sur le bus d’adresses une adresse non mappée ou en écriture seule, et comme aucun matériel du bus n’a répondu, les lignes du bus ne sont pas pilotées et restent flottantes. En théorie, c’est un comportement indéfini au niveau matériel.
  Pour comprendre ce qui se passe réellement, il faut regarder d’un peu plus près la structure physique du bus de données. Il y a de longs conducteurs qui transportent les signaux autour de la carte mère et de la cartouche, séparés du plan de masse par une fine couche de substrat isolant. Cela ressemble à un condensateur et, en pratique, les ingénieurs décrivent et modélisent ce phénomène comme une capacité parasite. Comme cet effet limite le débit maximal de transfert de données du bus, on cherche à le minimiser. Mais à cause de lui, lorsque le bus n’est pas piloté, il a tendance à rester à la dernière tension qui l’a piloté. Il se comporte comme une petite cellule de DRAM, ce qui produit l’effet décrit dans l’article : « une lecture sur open bus renvoie la dernière valeur passée sur le bus ».
  Il n’est pas rare que des jeux dépendent par erreur de l’effet d’open bus, comme DKC2. Sur NES, le registre du port série utilisé pour connecter les manettes ne pilote que les bits de poids faible, tandis que les bits de poids fort sont en open bus. Quelques jeux lisent l’entrée de la manette avec l’instruction LDA $4016 et s’attendent à obtenir $40 ou $41. Ici, le 4 est une valeur qui reste à cause de l’open bus.
  Il existe aussi des stratégies de speedrun qui reposent sur le comportement de l’open bus dans le cadre d’exploits de corruption mémoire ou d’exécution de code arbitraire. Par exemple, le credits warp de Super Mario World envoie le compteur de programme dans une zone mémoire non mappée, le laisse avancer pendant un bon moment jusqu’à ce qu’il atteigne finalement la RAM, puis exécute une charge utile construite en manipulant précisément la position des ennemis [1].
  Cela dit, même le comportement généralement prévisible de l’open bus a ses exceptions. Les cartouches non standard peuvent renvoyer une valeur par défaut pour la mémoire non mappée, ou inclure des résistances de pull-up/pull-down qui influencent le comportement de l’open bus. Il existe aussi des interactions intéressantes avec le DMA. La SNES prend en charge une fonction appelée HDMA, qui permet à une application de programmer des transferts de données du CPU vers le matériel graphique à un timing précis afin d’envoyer des données ou de changer des réglages au milieu d’une frame [2]. Ces transferts DMA suspendent brièvement le CPU pour utiliser le bus, et si un transfert DMA s’intercale au milieu de l’exécution d’une instruction, c’est-à-dire après la lecture de l’adresse cible mais avant la lecture open bus proprement dite, il peut modifier le comportement de cette lecture open bus.
  Ce cas limite très particulier a un impact important sur un exploit de speedrun de Super Metroid [3]. Cet exploit provoque un memcpy hors limites pour tenter de déplacer un gros bloc de données depuis l’open bus vers la RAM. Les lectures open bus renvoient presque toujours 0, car le dernier octet de l’instruction de chargement concernée vaut 0. Mais dans certaines salles riches en effets graphiques HDMA, il existe une probabilité non négligeable qu’un transfert DMA influence l’une de ces lectures ; dans ce cas, un octet non nul se retrouve inséré à un emplacement critique, l’exploit ne fonctionne pas correctement et le jeu crashe. Cela a suscité un léger débat dans la communauté. Certaines routes et stratégies ne sont stables que sur émulateur et avec des firmwares non standard. Les joueurs sur le matériel d’origine ou sur des émulateurs très précis ont plus de chances de subir un crash, mais la plupart des émulateurs, y compris toutes les rééditions officielles de Nintendo, n’émulent pas ce cas limite particulier où un transfert HDMA au milieu d’une instruction change la valeur lue sur l’open bus.
  De plus, le TAS de Super Metroid le plus rapide à ce jour [4] repose sur cette interaction HDMA. On avait trouvé une situation où tenter d’exécuter l’open bus provoquait un crash, mais elle était généralement impossible à contrôler utilement. En manipulant les ennemis dans la salle pour influer sur le timing du CPU, il a été possible de faire placer par le HDMA une instruction utile sur le bus au bon moment. Au final, la console en est venue à exécuter les entrées de la manette comme du code, permettant une exécution complète de code arbitraire.
  [1]: https://youtu.be/vAHXK2wut_I
  [2]: https://youtu.be/K7gWmdgXPgk
  [3]: https://youtu.be/CnThmKhtfOs
  [4]: https://tasvideos.org/8214S

  • Au passage où il faut regarder la structure physique du bus de données, j’ai envie de saluer une fois de plus Ben Eater.
    Grâce à sa série de vidéos où il construit un ordinateur sur breadboard avec un 6502, le contenu de l’article et l’explication des problèmes matériels deviennent réellement compréhensibles. Bien sûr, il s’agit d’étendre mentalement son exemple de bus de base à une machine commerciale. Sans cela, je n’y aurais presque rien compris.
    https://eater.net

• Il existe un problème assez similaire quand on programme la puce Parallax Propeller.
  Il faut utiliser JMP #address pour sauter à l’emplacement mémoire indiqué, mais je finis toujours par écrire JMP address, qui saute à l’adresse lue à l’emplacement mémoire indiqué. Sans doute parce que l’assembleur 6502 est encore dans ma mémoire musculaire.
  Propeller : JMP #address
  6502 : JMP address
  Propeller : JMP address
  6502 : JMP (address)
  Le pire, comme dans cet article, c’est que le code Propeller bogué fonctionne parfois. Puis, à un moment, il se bloque, et on passe des heures à essayer de comprendre pourquoi.

• Les graphismes 3D prérendus sur SGI de DKC 1 étaient à la pointe à l’époque. Vector Man sur Genesis faisait quelque chose de similaire, mais a moins attiré l’attention.

  • Vers 1995, j’avais 11 ans, soit exactement le public cible de DKC, et ce jeu m’a vraiment sidéré.
    Je n’arrivais pas à croire ce que je voyais. À l’époque de sa sortie, il y avait une cassette vidéo qui annonçait le jeu et montrait aussi les coulisses du développement ; si je me souviens bien, c’était un objet promotionnel qu’on pouvait commander via une boîte de céréales ou quelque chose du genre. J’ai regardé cette cassette un nombre incalculable de fois. Je n’ai jamais possédé DKC moi-même, mais je pouvais y jouer chez un ami.
  • Enfant, ces graphismes me semblaient quelque part faux. Parce qu’à un certain niveau, je sentais que ce n’était pas « réel ».
    Les magazines de l’époque restaient assez flous sur le sujet et suggéraient souvent que la puissance de la SNES permettait de rendre les personnages et le reste en temps réel. Alors qu’en réalité, c’était essentiellement plus proche d’une animation en flipbook.

• Quand on joue via émulation et qu’on se retrouve bloqué, on finit souvent par se demander si ce n’est pas tout simplement un bug de l’émulateur.
  Pour ce problème précis, j’aurais pensé que le jeu avait été conçu comme ça à l’origine, et qu’il était juste difficile. Ce n’est pas tout à fait lié, mais quand un jeu paraît vraiment difficile, je me surprends de la même façon à me demander : « est-ce que c’est à cause de la latence de l’émulation ? ». À force de creuser ce problème, j’ai fini par me fabriquer un MiSTer FPGA.

  • Il y avait aussi ce genre de chose dans Chrono Trigger.
    Je me souviens d’un passage où, après avoir attrapé le rat, il fallait appuyer simultanément sur quatre touches. Mais l’entrée USB n’en transmettait que 3 à la fois ; pour passer, il fallait donc marteler les quatre touches afin qu’elles finissent toutes par être enregistrées dans un intervalle très court. Il fallait essayer plusieurs fois, et c’était très frustrant.
  • Je n’ai joué à DKC que sur ZSNES, et avant de lire l’article, je n’avais absolument pas réalisé que c’était un bug de l’émulateur.
    Comme dit plus haut, je pensais simplement que le game design prévu consistait à bien caler le timing du tir depuis le tonneau pour obtenir le bon angle. J’ai été vraiment surpris d’apprendre que c’était un bug.
  • Enfant, j’ai beaucoup joué à Bionic Commando.
    Quand je l’ai relancé sur émulateur au début des années 2000, il m’a semblé bien plus difficile que dans mon souvenir. J’ai découvert plus tard qu’il y avait un bug d’émulation : même après avoir fait exploser une base, les ennemis ne disparaissaient pas, et Ladd restait toujours immobilisé. Il fallait donc environ 2 barres de vie supplémentaires pour terminer le niveau. Je l’ai fait une fois pour voir si c’était possible, mais je ne l’ai jamais refait.