Final Fantasy 7 "Missing Formation" glitch explanation

An explanation of the "missing formation" bug that causes a few maps to have only one formation when they should theoretically have more than one:

When determining what battle formation to start, after the code has determined that you should not get a special encounter, the following snippet is run:

```
; s0 is zero
; a2 has the RNG value used to determine which encounter to get
loop:
lhu   v1, $2(a1)     ; load two bytes of encounter data into register v1
sll   v0, v1, $10    ; copy the contents of register v1 to register v0 and shift them left 16 bits
sra   v0 $1A         ; !!! THE BUG !!! shift v0 right by 26 bits (using the arithmetic shift right operation)
addu  s0, v0         ; add v0 to s0
andi  v0, s0, $FF    ; replace v0 with the least significant 8 bits of s0
sltu  v0, a2, v0     ; if a2 < v0, put 1 into v0, otherwise put 0 there
bne   v0, 0, exit    ; exit the loop if v0 is not 0 (if v0 is 1)
andi  v0, v1, $3FF   ; replace v0 with the least significant 10 bits of v1
addiu a0, 1          ; add 1 to a0
slti  v0, a0, 5      ; if a0 < 5, put 1 into v0, otherwise put 0 there
addiu a1, 2          ; add 2 to a1 (to put the pointer to the next encounter slot there)
bne   v0, 0, loop    ; jump back to the start of the loop if v0 is not 0
```

Encounter data is stored internally in two bytes as follows:
`rrrrrrff ffffffff`
where `r` is the rate for each formation (number from 0 to 63) and `f` is the formation ID for that encounter

The above code essentially loops through each of the normal formations and adds their rates to a running total. Once an encounter pushes the total above a "randomly" generated number (determined by the formation accumulator), you get that encounter (well in reality it'll then check if it's the same encounter as your last one to reroll, but that's outside the scope of what we're talking about here)

Say you get an encounter on field 464 and it's determined to not be a special encounter. The first encounter the game checks against is formation ID 508, which has a rate of 24. It is represented internally as:
`01100001 11111100`
It is loaded into register v1 (all registers are 32 bits) as:
`00000000 00000000 01100001 11111100`
then v1 is copied to v0 and shifted left 16 bits to become:
`01100001 11111100 00000000 00000000`
then v0 is shifted right by 26 bits to become:
`00000000 00000000 00000000 00011000`
This effectively just removes the formation part of the encounter data and keeps only the rate.

However, the shift-right operation used here is the arithmetic shift right, not the logical shift right.

The logical shift right operation will ignore if the number it is shifting is positive or negative and just shift the bits, filling in the bits it leaves with 0's. The arithmetic shift right operation, however, interprets its input as a signed integer, meaning it can be positive or negative. A signed number is negative if its most significant bit is set, and the arithmetic shift right operation will fill the empty space left of the shifted value with 1's instead of 0's if the number being shifted is negative. Usually this will result in the shifted number staying negative and its absolute value being divided by two, just like it were a positive value.

Let's replay the scenario, but this time on the bridge (field 467). The first standard encounter here is formation 513 with a rate of 34, represented internally as:
`10001010 00000001`
It is loaded into register v1 as:
`00000000 00000000 10001010 00000001`
then v1 is copied to v0 and shifted left 16 bits to become:
`10001010 00000001 00000000 00000000`
then v0 is shifted right (arithmetically) by 26 bits to become:
`11111111 11111111 11111111 11100010`

Woah, that's different. Because the most significant bit of register v0 was a 1 this time, the arithmetic shift right operation filled the empty space it left behind with 1's instead of 0's. If we look backwards, this bit comes from the most significant bit in this formation's encounter rate. If this encounter rate is greater than or equal to 32, this bit will be set. Later, register v0 is added to s0 (which contains 0 right now so it just copies it), then the least significant 8 bits of s0 are copied back to v0, so v0 now contains:
`00000000 00000000 00000000 11100010`
which in decimal is the number 226. This is compared to the random value which is between 0 and 63, and if it's greater than that value, which it will always be, then this encounter is chosen.

Effectively, this means that if any encounter has a rate of 32 or greater, the 0th and 1st bits are set due to an arithmetic shift right being used instead of a logical shift right, and so the actual value used to compare with the random encounter value is 192 plus the original rate, which will always pass the check and this encounter will always be chosen.