Fixed Shedinja hash collision

A Shedinja will always have the same IVs, personality value, and
original trainer as the Nincada that generated it, meaning that it is
guaranteed to have the same hash as the Ninjask that the Nincada evolved
into. To cirvument this, there is now a boolean field in the hash
determiner that is set if and only if the Pokémon is a Shedinja. This
allows the Ninjask to be considered the same Pokémon as the Nincada it
evolved from, but for the Shedinja to be considered a new Pokémon.

Because the hash determiner has changed, all old hashes are now invalid.

2 files changed, 33 insertions, 5 deletions

@@ -12,6 +12,20 @@
 #include "dexorder.h"
 #include "sha2.h"
 
+// See pokemon.h for more information about this.
+struct HashDeterminer {
+  u32 otId;
+  u32 personality;
+  u32 hpIV:5;
+  u32 attackIV:5;
+  u32 defenseIV:5;
+  u32 speedIV:5;
+  u32 spAttackIV:5;
+  u32 spDefenseIV:5;
+  u32 isShedinja:1;
+  u32 zero:1;
+};
+
 u32 CalculateStat(
   u8 base,
   u32 iv,
@@ -50,13 +64,20 @@ void PokemonIntermediateInit(
   struct PokemonSubstruct2* sub2 = GetBoxPokemonSubstruct2(bpkm);
   struct PokemonSubstruct3* sub3 = GetBoxPokemonSubstruct3(bpkm);
 
-  u32 identifier[3];
-  identifier[0] = bpkm->otId;             // original trainer
-  identifier[1] = bpkm->personality;      // personality value
-  identifier[2] = ((const u32*)sub3)[1];  // IVs (plus two non-random bits)
+  struct HashDeterminer identifier;
+  identifier.otId = bpkm->otId;
+  identifier.personality = bpkm->personality;
+  identifier.hpIV = sub3->hpIV;
+  identifier.attackIV = sub3->attackIV;
+  identifier.defenseIV = sub3->defenseIV;
+  identifier.speedIV = sub3->speedIV;
+  identifier.spAttackIV = sub3->spAttackIV;
+  identifier.spDefenseIV = sub3->spDefenseIV;
+  identifier.isShedinja = (sub0->species == SHEDINJA_SPECIES_INDEX) ? 1 : 0;
+  identifier.zero = 0;
 
   sha224(
-    (const unsigned char*)identifier,
+    (const unsigned char*)&identifier,
     12,
     (unsigned char*)pki->key);
 
@@ -35,6 +35,13 @@ struct __attribute__((aligned(4))) PokemonIntermediate {
   // while not uniformly random (amongst Pokémon), is included as a sort of
   // "namespace", in that any Pokémon with matching PVs and IVs must also have
   // the same OT, thus preventing collaboratively finding PV and IV collisions.
+  // there is one deterministic way that two Pokémon can have the same hash:
+  // when a Nincada evolves into a Ninjask and a Shedinja is generated, the
+  // Shedinja is guaranteed to have the same IVs and personality value as the
+  // Ninjask. we circumvent this by also including a boolean in the hash which
+  // is set to true if the Pokémon is a Shedinja, and false otherwise. this
+  // differentiates a Shedinja from the Ninjask it came from, but also allows
+  // the Ninjask to be associated with the Nincada it used to be.
   u32 key[7];
 
   u32 experience;