[mvanotti]

Just an FYI for anyone reading: It's not the multiplicative inverse of 10 modulo 2^64. Multiplying by it only works if the number is divisible by 10.

What it's happening here is something more clever:

  let z be: (2^67 + 2)/10. 

2^67 isn't divisible by 10 (that's why we add 2).

  z = 14757395258967641293L

Now, I claim that

  n/10 = floor(z * n/ 2^67)

z is an integer, but it represents the exact division of

  (2^67 + 2)/10
 

we distribute the n:

  (n * 2^67)/10 + 2 * n/10

we distribute the 2^67 division:

  (n * 2^67)/(10 * 2^67) + 2 * n / (10 * 2^67)

simplify the terms:

  n/10 + n/(10 * 2^66)  [1]

Now:

  floor(x/d + c) == floor(x/d) if c < 1/d

we want to take floor of that number[1], but as

  n/(10 * 2^66) < 1/10

(the maximum value for n is 2^64 - 1), it follows that

  floor(z * n / 2^67) = n/10.

That's what the code is doing: 0xcccccccccccccccd is 14757395258967641293L the multiplication of z * n fits in 128 bits, and the mul instruction stores the higher 64 bits of $rax * $rdx into $rdx.

We need to divide by 2^67, whichs is shift 3 67 bits to the right. If we take the higher part (rdx) we get the higher 64 bits, and then we shift 3 bits to the right (shr $0x3, %rax) and that's our answer :).

Cool trick.