Rijndael S-Box algorithm: Can someone please explain how this code calculates the multiplicative inverse? Wikipedia's explanation of the Rijndael Cipher's S-Box gives c code for calculating the S-Box.
I've been able to calculate the S-Box values using exponent and log look-up tables to calculate the multiplicative inverse, but I can't see how this code generates the same values.
I understand how the "S-Box index" (i.e. 'p') is calculated (multiplied by x+1, i.e. the generator, 0x03), and I can see how the Affine Transformation is performed, but I don't understand the part in between that "divides by x+1".

  /* divide q by x+1 */
    q ^= q << 1;
    q ^= q << 2;
    q ^= q << 4;
    q ^= q & 0x80 ? 0x09 : 0;


How does this code divide by x+1?
Where do the values 1, 2, and 4 come from?
Where does the value 0x09 come from?
I'm wondering if this is just a highly efficient but obfuscated way to divide.
 A: The inverse of $x+1$ is $(x+1)^{-1} = x + x^2 + x^4 + x^5 + x^6 + x^7$, so instead of dividing by $x+1$, we multiply by $(x+1)^{-1}$.
Now, it is not that hard to multiply an arbitrary element of $\mathbb F_{256}$ with $(x+1)^{-1}$ and calculate what it will be. Let
$$a = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + a_5x^5 + a_6x^6 + a_7x^7$$
be an arbitrary element. Then:
$$\begin{align}
a(x+1)^{-1} &= a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7 \\
& + x \left(a_0+a_1\right)\\
&+x^2 \left(a_0+a_1+a_2\right) \\
&+x^3 \left(a_4+a_5+a_6+a_7\right) \\
&+x^4 \left(a_0+a_1+a_2+a_3+a_4\right)\\
&+x^5 \left(a_0+a_1+a_2+a_3+a_4+a_5\right)\\
&+x^6 \left(a_0+a_1+a_2+a_3+a_4+a_5+a_6\right)\\
&+x^7 \left(a_0+a_1+a_2+a_3+a_4+a_5+a_6+a_7\right)
\end{align}$$
I will skip over the details, since I did not do this by hand (but it is simple to do it by hand, just tedious). ;)
The first three lines of the code calculates $(1+x)(1+x^2)(1+x^4)q$ and also truncates the polynomial (i.e. drops all monomials with power larger than 7) after each multiplication. This will result in the element:
$$\begin{align}
q_3 &= a_0\\
&+x \left(a_0+a_1\right)\\
&+x^2 \left(a_0+a_1+a_2\right)\\
&+x^3 \left(a_0+a_1+a_2+a_3\right)\\
&+x^4 \left(a_0+a_1+a_2+a_3+a_4\right)\\
&+x^5 \left(a_0+a_1+a_2+a_3+a_4+a_5\right)\\
&+x^6 \left(a_0+a_1+a_2+a_3+a_4+a_5+a_6\right)\\
&+x^7 \left(a_0+a_1+a_2+a_3+a_4+a_5+a_6+a_7\right)
\end{align}$$
where we can note that only the cofficients for $x^0$ and $x^3$ are incorrect.
So, let's look at the last line. The last line says that if the coefficient of $x^7$ is not zero, we add $1+x^3$ to $q_3$, otherwise we do nothing.
Let's look at the case where $x^7$'s coefficient is zero. Then
$$a_0+a_1+a_2+a_3+a_4+a_5+a_6+a_7 = 0$$
which is equivalent to
$$a_0+a_1+a_2+a_3 = a_4+a_5+a_6+a_7$$
so the coefficient of $x^3$ in $q_3$ is correct. Using the same reasoning, we see that
$$a_0 = a_1+a_2+a_3+a_4+a_5+a_6+a_7$$
so the coefficient of $x^0$ in $q_3$ is correct, so we do not need to do anything.
If the coefficient of $x^7$ is not zero, i.e. it is one, we have:
$$a_0+a_1+a_2+a_3+a_4+a_5+a_6+a_7 = 1$$
we get that the coefficient of $x^0$ in $q_3$ is:
$$a_0 = 1 + a_1+a_2+a_3+a_4+a_5+a_6+a_7$$
so we need to add 1 to get the correct result. Use the same reasoning to see that we also need to add $x^3$.
This is of course a post-hoc explanation of what is happening. It would be much more interesting to have an algorithmic approach to construct these kind of code segments.
