Tricherie sur Game Boy
Série 5 – corrigé
Introduction
Le code du corrigé vous est fourni dans une archive Zip et les solutions aux différents exercices sont présentées ci-dessous.
Exercice 1 : Super Mario Land 2
La lecture des fichiers se fait en empilant deux flots d'entrée d'octets : un FileInputStream, qui permet de lire les données depuis un fichier, et un GZIPInputStream, qui permet de décompresser (au moyen de l'algorithme de gzip) les octets du flot qu'on lui passe.
La lecture en elle-même ne pose pas d'énorme problème, surtout si on se simplifie la vie en utilisant la méthode read retournant un octet à la fois. La solution présentée ci-dessous utilise l'autre méthode read qui en lit plusieurs à la fois.
byte[] readMemDump(String fileName) {
try (InputStream s =
new GZIPInputStream(new FileInputStream(fileName))) {
byte[] memDump = new byte[0x1_0000];
int totalRead = 0;
while (totalRead != memDump.length) {
int read = s.read(memDump,
totalRead,
memDump.length - totalRead);
assert read > 0;
totalRead += read;
}
return memDump;
} catch (IOException e) {
throw new UncheckedIOException(e);
}
}
Une fois les données mémoires lues dans un tableau d'octets, obtenir l'ensemble des adresses contenant un octet particulier est très simple.
Set<Integer> addressesContaining(byte[] dump, int v) {
Set<Integer> s = new TreeSet<>();
for (int a = 0; a < dump.length; ++a) {
if (Byte.toUnsignedInt(dump[a]) == v)
s.add(a);
}
return s;
}
Une fois ces méthodes écrites, il ne reste plus qu'à les utiliser pour charger chacun des trois fichiers, calculer l'ensemble des adresses qui pourraient, dans chacun des cas, contenir le nombre de vies, puis en faire l'intersection au moyen de la méthode retainAll. C'est ce que fait la méthode superMarioLand2 ci-dessous, en affichant quelques informations intéressantes.
private static void superMarioLand2() {
Set<Integer> s3 =
addressesContaining(readMemDump("sml_3.bin.gz"), 3);
Set<Integer> s4 =
addressesContaining(readMemDump("sml_4.bin.gz"), 4);
Set<Integer> s5 =
addressesContaining(readMemDump("sml_5.bin.gz"), 5);
System.out.printf("3 vies : %d candidats%n", s3.size());
System.out.printf("4 vies : %d candidats%n", s4.size());
System.out.printf("5 vies : %d candidats%n", s5.size());
s5.retainAll(s4);
s5.retainAll(s3);
System.out.println("Adresses :");
for (int a: s5)
System.out.printf(" %04X%n", a);
}
Lorsqu'on l'exécute, on obtient le résultat suivant :
3 vies : 242 candidats 4 vies : 407 candidats 5 vies : 147 candidats Adresses : A043 A22C
On constate que chacune des valeurs recherchées (3, 4 ou 5) se retrouve dans plus de 100 positions mémoires différentes. Ce n'est donc qu'en déterminant l'intersection des ensembles d'adresses candidates que l'on peut savoir où se trouve vraiment le nombre de vies.
Un aspect surprenant, et difficile à expliquer, de ce résultat est que le nombre de vies est stocké à deux endroits différents.
Pour vérifier que ces adresses sont bien celles contenant le nombre de vies de Mario, on peut utiliser une version modifiée du corrigé du projet pour incrémenter la valeur à ces adresses lors de la pression sur une touche. Le résultat de cette manipulation est visible dans la petite vidéo suivante :
Exercice 2 : Tetris
La recherche des adresses contenant potentiellement le score de Tetris est plus difficile que dans l'exercice précédent, car il faut désormais rechercher une séquence d'octets.
Ce problème est en fait équivalent à celui de la recherche d'une chaîne de caractères dans un texte, qui est un problème fondamental en informatique. En effet, tous les éditeurs de texte comme celui d'Eclipse, les navigateurs, etc. offrent la possibilité de rechercher une chaîne dans un fichier, page Web ou autre. Il existe donc de très nombreux algorithmes permettant de résoudre ce problème efficacement, répertoriés sur la page Wikipedia qui leur est consacrée.
Pour cet exercice, un algorithme très simple suffit. Il consiste à parcourir toute la mémoire au moyen d'une première boucle, et à comparer la séquence d'octets commençant à chaque adresse à celle recherchée, au moyen d'une seconde boucle imbriquée dans la première.
Set<Integer> addressesContaining(byte[] dump, byte[] bytes) {
Set<Integer> s = new TreeSet<>();
for (int a = 0; a <= dump.length - bytes.length; ++a) {
int equalBytes = 0;
for (int i = 0;
i < bytes.length && dump[a + i] == bytes[i];
++i) {
equalBytes += 1;
}
if (equalBytes == bytes.length)
s.add(a);
}
return s;
}
Notez que cet algorithme peut aussi s'écrire au moyen d'une fonctionnalité peu connue de Java, les énoncés étiquetés (labeled statements). L'idée est d'attacher une étiquette (outer ci-dessous) à la boucle externe, puis de passer à sa prochaine itération au moyen d'un énoncé continue se trouvant dans la seconde boucle. L'étiquette est nécessaire ici, car sans elle l'énoncé continue aurait pour effet de passer à l'itération suivante de la boucle imbriquée, ce qui n'est pas le comportement désiré.
Set<Integer> addressesContaining(byte[] dump, byte[] bytes) {
Set<Integer> s = new TreeSet<>();
outer:
for (int a = 0; a <= dump.length - bytes.length; ++a) {
for (int i = 0; i < bytes.length; ++i) {
if (dump[a + i] != bytes[i])
continue outer;
}
s.add(a);
}
return s;
}
Une fois cette méthode écrite, il reste à correctement deviner la manière dont le score de Tetris est représenté en mémoire.
Une première possibilité est que ce score soit représenté en binaire, sous la forme d'une valeur 16 bits stockés dans deux octets. Si tel était le cas, le score 3979 (F8B16) serait représenté par les octets 0F16 et 8B16. Comme le processeur du Game Boy stocke les valeurs 16 bits dans l'ordre petit-boutien, ces octets apparaîtraient dans l'ordre 8B16 0F16.
Cela dit, il faut se rendre compte que cette représentation serait problématique, car le score est affiché à l'écran en base 10. Dès lors, le programme devrait convertir la valeur stockée en mémoire vers la base 10, ce qui est loin d'être facile sur le processeur du Game Boy qui ne dispose pas d'instruction de division.
Dès lors, il est plus probable que le score soit stocké au format décimal codé binaire, qui rend la conversion en base 10 triviale. Si tel est le cas, les deux octets représentant le score 3979 sont, dans l'ordre petit-boutien, 7916 3916. De même, ceux représentant le score 799 sont 9916 0716. Et ceux représentant le score 11 sont 1116 0016.
En utilisant ces valeurs dans la recherche, on obtient les résultats suivants, qui confirment notre hypothèse :
score 11 : 293 candidats score 799 : 2 candidats score 3979 : 2 candidats Adresses : C0A0 E0A0
Là encore, on constate que le score apparaît à deux adresses différentes, mais dans ce cas il s'agit d'une illusion ! En effet, ces deux adresses représentent le même octet en mémoire, qui est visible à deux endroits en raison de la « zone d'écho » (voir la §3.4 de l'étape 2).
Une fois l'adresse du score déterminée, il est à nouveau facile de modifier le corrigé du projet pour lui faire stocker une très grande valeur à cette adresse lorsqu'une touche spéciale est pressée. On obtient le résultat visible dans la vidéo ci-dessous :