title: How does the GCC implementation of modulo (%) work, and why does it not use the div instruction?
body: <p>I was trying to work out how to calculate modulo 10 in assembly so i compiled the following c code in gcc to see what it came up with.</p>
  
  <pre><code>unsigned int i=999;
  unsigned int j=i%10;
  </code></pre>
  
  <p>To my surprise I got</p>
  
  <pre><code>movl    -4(%ebp), %ecx
  movl    $-858993459, %edx
  movl    %ecx, %eax
  mull    %edx
  shrl    $3, %edx
  movl    %edx, %eax
  sall    $2, %eax
  addl    %edx, %eax
  addl    %eax, %eax
  movl    %ecx, %edx
  subl    %eax, %edx
  movl    %edx, %eax
  movl    %eax, -12(%ebp)
  </code></pre>
  
  <p>Where -4(%ebp) or "i" is the input and -12(%ebp) or "j" is the answer. I've tested this and it does work no matter what number you make -4(%ebp).</p>
  
  <p>My question is how does this code work and how is it better than using the div operand.</p>