Damage overflow glitch in Final Fantasy VII

320px|right|thumb|The glitch in action by 4-8Productions
Damage overflow is a glitch in Final Fantasy VII. It is an instance of the more general overflow glitch present in various games.
== The basics ==
In 32-bit Operating Systems (the original PlayStation being one of them) integer numbers are encoded in 4 bytes (32 bits). In particular, for signed integers, the OS employs the so called two's complement representation. In two's complement the leftmost bit is negative weighted (see below), while all the others have a positive value.
Given a generic n-bit two's complement representation, every bit (from right to left) represents a power of 2, starting from 2^{0} up to 2^{n-1}. The corresponding value in base 10 is calculated by adding all those powers of two, each one weighted (multiplied) by the corresponding bit value (0 or 1). The leftmost bit multiplier, if such bit is 1, becomes -1, otherwise 0.
Working with the two's complement representation, the largest signed positive number that can be represented with n bits is the one starting with a 0 (zero) followed by n - 1 1s (ones). In the 32-bit scenario, its binary representation is
0111 1111 1111 1111 1111 1111 1111 1111
Since the leftmost bit (the one which encodes the n-1 exponent) is 0, and all the other bits are 1s, the value of the number above is the sum of all the powers of two from 2^{0} to 2^{n-2}, as represented by the following summation:
\sum_{i \mathop =0}^{n-2}2^{i}
Given an integer k, the sum of all the powers of 2 with the exponent in the range [0, k - 1] is equal to 2^{k} - 1. In the above case, k - 1 is equal to n - 2. Therefore, k = n - 1 = 32 -1 = 31. After calculating the sum, the result in base 10 is
2^{31} - 1 = 2,147,483,647
which is the upper bound for 32-bit signed integers.
Similarly, the largest negative number which can be represented with n bits is the one starting with a 1 (one) followed by n - 1 0s (zeroes). Since only the first bit is different from zero and, given the negative weight of such bit, the numerical value in base 10 is -2^{n-1}. In the 32-bit scenario, its binary representation is
1000 0000 0000 0000 0000 0000 0000 0000
and its value in base 10 is
-2^{31} = -2,147,483,648
In a 32-bit OS, if, at any point, the computation of any value results in a number greater that the upper bound or smaller than the lower bound, an overflow occurs and the software (the game) exhibits abnormal behavior(s).
== Description ==
There are several instances of integer overflow. The best known one is the damage overflow glitch, which triggers when the console computes a number out of the aforementioned bounds during the computation of the damage formula.
Unless a healing overflow, and/or multiple overflows are triggered, and/or the target is immune to or absorbs the attack, the most visible effect of the glitch is the instant defeat of the target of an attack whose damage calculation triggered an overflow. Graphically, random symbols are displayed instead of the usual damage digits, although it is possible that up to 4 random digits are rendered.
Because of its notoriety, the glitch is often referred as "the overflow glitch", despite it not being the only kind of overflow possible in Final Fantasy VII.
== The damage formula ==
The general damage formula is
Damage = BD * PVMs * RVM * PoVMs
BD is the so called Base Damage, calculated as
(POWM * DEFM * ATKM) / (16 * 512)
where DEFM is the defense multiplier:
512 - TDEF
with the target Defense stat expressed as TDEF.
ATKM is the attack multiplier:
ATK+((LV + ATK)/32) * ((LV * ATK)/32)
where LV is the attacker's Level (max 99) and ATK is the attacker's Attack stat. The latter is the sum of the attacker's Strength and the equipped weapon attack bonus. ATK is capped at 255, but during a battle it can be temporarily increased up to 510 by using 4 Hero Drinks. In particular the first 3 Hero Drinks give +30% and the last one +10%. Even if ATK is < 510 after 4 Hero Drinks, additional Hero Drinks do not increase it above the 200% of the original value.
POWM is the power multiplier, which depends on TPOW (the Technique Power) and the equipped weapon. For most of the in-game weapons POWM is
TPOW / 16
but each final weapon has its own POWM formula, which includes TPOW along with other parameters.
TPOW is 16 for physical attacks, while all the commands/spells/summons have their own values.
Limits ignore any ultimate weapon power modifier, as they force POWM to be
LMUL * (TPOW / 16)
where LMUL is a Limit-specific multiplier. For instance, every Omnislash hit has 0.75 as LMUL. Limits may have other properties (like auto-critical for Omnislash), but they are considered in other steps of the damage computation.
PVMs is the product of the sequence of Pre-Variance Multipliers, which are
:Critical: x2 if a critical hit occurs, x1 otherwise.
:Berserk: x1.5 if the attacker is in Berserk, x1 otherwise.
:Row: x1 if the attacker and the target are both in the front row, x0.5 in all the other cases.
:Defend: x0.5 if the target is in defend mode, x1 otherwise.
:Back: x2 (x4 for Air Buster and x8 for Acrophies) if the target is attacked on the back, x1 otherwise.
:Frog: x0.25 if the attacker is in Frog status, x1 otherwise.
:Sadness: x0.7 if the target is in Sadness status, x1 otherwise.
:Split: x2/3 if the attack hits multiple targets, x1 otherwise.
:Barrier: x0.5 if the target is in Barrier status, x1 otherwise.
:Mini: x0 if the attacker is in Small status, x1 otherwise.
As for Small, a rescaling makes 1 HP the minimum damage one can deal (without it the damage would be 0, since the Mini multiplier itself is 0).
RVM is the Random Variance modifier: the game selects a random number between 0 and 255 (including the bounds), and adds it to 3841 to get RVMN, the RVM numerator, which spans from 3841 to 4096 by construction. A this point the random variance is applied by means of
PoRVD = (PRVD * RVMN) / 4096
being PoRVD the post random variance damage, PRVD the pre random variance damage and 4096 the fixed denominator of RVM. For this reason the random variance can be technically expressed as
RVMN/4096
even though that fraction is actually never computed.
Finally, PoVMs is the product of the sequence of Post-Variance Multipliers, which are the target elemental affinities w.r.t. the attack element(s) and special modifiers like Aeris's Princess Guard multiplier. The result is the actual damage dealt to the target, capped at 9999.
== The overflow ==
During the calculation, being the floating point division a time consuming operation, whenever the divisor (denominator) is a power of 2, the operation is performed by means of a right shift of the bits by n = log {2}({divisor}), resulting in an integer division (the n rightmost bits are lost). The console parses the chain of operations to calculate and first computes as many products as possible, then performs the right shift(s).
Therefore, there are two points where the partial results can go out of bounds: while computing the numerator of BD and after multiplying PRVD by RVNM. When the positive bound has been exceeded the leftmost bit becomes "1", turning the number into a negative integer. For instance,
(2^{31} - 1) + 1 =overflow= - 2^{31}
or, visualizing the bits:
 0111 1111 1111 1111 1111 1111 1111 1111 + 1 =
1000 0000 0000 0000 0000 0000 0000 0000
The division by means of right shifts does not alter the sign of the result, since the n bits lost on the right are added to the left by leveraging the sign extension rule: if the leftmost bit is "0", then the number is left-padded with "0"s, otherwise with "1"s. This preserves both the number value and its sign, while re-extending it on 32 bits. For instance, being 8 the logarithm in base 2 of 256,
(2^{31} - 1) / 256 =integer= 2^{23} - 1
 0111 1111 1111 1111 1111 1111 1111 1111 >> 8 =
 0000 0000 0111 1111 1111 1111 1111 1111
while
(-2^{32} + 5) / 256 =integer= -2^{23}
1000 0000 0000 0000 0000 0000 0000 0101 >> 8 =
1111 1111 1000 0000 0000 0000 0000 0000
which means a negative numerator will remain negative even after any division operation (right shift), resulting in negative damage. Final Fantasy VII does not treat negative damage as healing, since there is a special flag between the elemental modifiers for that (all the restorative spells/items have the Restorative element, and all the characters/enemies, except for the undead, absorb that element). Instead, the game code probably thinks the final damage overflowed (despite the overflow occurring at an earlier stage of the computation) by going beyond 2^31 - 1. Since no target in the game has enough HP to survive such damage, the game mechanics kill the target.
To sum up, the overflow condition is
(POWM * DEFM * ATKM) > 2^{31} - 1
or
(PRVD * RVMN) > 2^{31} - 1
Post-Variance Multipliers are not going to help when trying to trigger the glitch, since they are applied at a point where it is impossible to get large enough partial results anymore. As such, elemental affinities and some special weapons modifiers are completely irrelevant for the damage overflow.
== Multiple overflows ==
Since there are two possible points in which an overflow can take place, a composition between overflows may happen. In the base damage calculation, if the potentially overflowable value could be extended to a sufficiently large number of bits to avoid the overflow, the result would always be a positive integer. However, while applying random variance, it is possible that the first factor (PRVD) is negative due to a base damage overflow. In this condition, the same extension procedure would always yield a negative integer (as expected from the product between two numbers with different signs).
To explain all the possible cases, one can imagine the extended base damage numerator as a quantity to deplete in different steps on a circuit. The circuit begins at step 0 and goes through all the natural numbers up to step 2^31 - 1. The successive step is step -2^31 and, then, the circuit continues until step 0, where a lap is considered completed, being step 0 the starting point. The extended numerator starts traveling through the circuit and, at every step, subtracts 1 from itself. When the numerator value becomes 0 the procedure ends. The correspondent circuit value is what the game considers the base damage numerator. The number of times the extended numerator went from step 2^31 - 1 to step -2^31 is the number of base damage overflows (BDOV), where the numerator becomes negative, while the number of completed laps is the number of base damage anti-overflows (BDAOV), where the numerator becomes non-negative.
During random variance application, if the extended numerator is positive, the very same procedure can be employed to calculate PoRVD and the number of random variance overflows (RVOV) and anti-overflows (RVAOV). If the extended numerator is negative, the lap goes in the opposite direction: it begins at step 0 down to step -2^31, after that it continues at step 2^31 - 1, down to step 0 again. The extended numerator adds 1 to itself at every step. The finishing point is still the extended numerator becoming 0. In this situation the ending point is PoRVD, the number of times the extended numerator travels from step -2^31 to step 2^31 - 1 is RVOV, and the number of times it travels from step 0 to step -1 is RVAOV.
The number of overflows and anti-overflow combine in this way:
BDFOV = BDOV - BDAOV
RVFOV = RVOV - RVAOV
FOV = BDFOV + sign(BDFOV) * RVFOV
FOV, by construction, can only be 0 or 1. In the former case, a global overflow (in the sense of negative final damage) will not happen and the damage inflicted will be in the range 1–9999. In the latter case a global overflow will take place. The game will kill the target only if the final damage is in the negative range. Sometimes, instead of weird symbols, the game displays a number between 1 and 9999 when the attack is performed and kills the enemy anyway; it is possible for the game to display digits instead of random symbols, even when the resulting damage is negative.
== Overflow examples ==
The most famous instance of the damage overflow glitch involves the Death Penalty. Its POWM is
((TPOW * (K/128))/16) + 10
where K is the number of enemies killed by Vincent, capped at 65,535. Since the division by 16 is a 4 bits right shift, the maximum POWM (regarding a certain TPOW) is reached as soon as Vincent has killed 65,408 enemies.
Barret's Missing Score can overflow damage if it is powered up by equipping large amounts of AP (the upper bound being eight mastered Knights of Round Materia) and also having other relevant stats sufficiently high. In particular the POWM for the Missing score is
((TPOW \times (nAP/10000))/16) + 1
where nAP is the total number of AP contained in the Materia pieces equipped on the weapon. Each Materia piece has a cap, consisting in the AP amount needed to become master. The Missing Score always treats the Underwater Materia as if it had 0 AP, regardless the actual AP on it.
Vincent and Barret are the two best known characters for triggering the overflow glitch, but most characters can do it if they consume enough Hero Drinks and get the best outcome from the pre random variance modifiers. For instance, Red XIII can overflow with Cosmo Memory and Yuffie with All Creation; however, the maximum target defense stat for the overflow to be possible is lower than the ones allowed for Barret and Vincent. Furthermore, Vincent has the highest upper bound on the target defense stat for the overflow to be possible (421) because the maxed Death Penalty has the highest POWM for all the possible TPOW values. Only Ruby Weapon has a defense stat over 421 (480, to be precise), making it the only non-overflowable enemy in the game.
Aeris cannot overflow without cheating, since her final weapon modifier is applied after the random variance without altering the POWM calculation, leading to the impossibility to get a high enough partial result during the computation. If one wants to cheat, it is possible to add Aeris back into the party in Part II and III and overflow against an Acrophies by leveraging his x8 back attack multiplier. However, an additional cheat is required, since the Acrophies enemy normally cannot be encountered in a pre-emptive or side attack.
== Healing overflow ==
320px|right|Healing Overflow by XeroKynos
If an attacker causes an overflow while attacking a target with an element he absorbs, the overflow effect is reversed and the target's HP is fully restored.
If an overflow happens with an attack linked in some way to HP Absorb or MP Absorb, the attacking character will be killed in the former case or deprived of all his/her MP in the latter one.
Combining the two properties, if a character who is equipped with HP Absorb or MP Absorb causes an overflow while attacking a target with an element he absorbs, the character will get either his/her HP completely restored, or his/her MP restored by a large amount, which depends on the pre-cap damage value. The target's HP are still fully restored.
== External links ==
*A simulator of the Final Fantasy VII damage system, including overflow(s), is available here.
Category:Bugs in Final Fantasy VII