[danlark1]

Hi everyone, the author is here. Yes, I believe the title should be changed to `Optimizing 128-bit Division`

Yet, I was not expecting it to be here. Overall, I put some knowledge hidden in Hacker's Delight book, Knuth, GMP and GNU in the article with my knowledge of low level optimizations. In the end it turned out to be a good thing to write and to submit into LLVM

[drfuchs]

You might want to also check that 128-bit multiplies are implemented as only two 64-bit multiplies and a couple of additions (assuming no overflow; three multiplies if you need to get the right answer mod 2^64).

[ncmncm]

There is an `if` statement in a `for` loop that looks like it could be eliminated. Abbreviating:

  if (dd.all >= dr.all) {
    dd.all -= dr.all;
    quo.s.low |= 1;
  }

could be

  bool c = dd.all >= dr.all;
  dd.all -= (-c & dr.all);
  quo.s.low |= c;

Clang might implement this with `cmov` instructions, coded either way.

[titzer]

Great article, I read to the end.

I faced a similar problem implemented 64/64 division on 32-bit x86. I cribbed some code off the internet and came up with this:

https://github.com/titzer/virgil/blob/2c674dbe3512da23c4a644...

This is the code that my compiler generates for a 64/64 divide when it doesn't know that the divisor is max 32 bits. It works by using the x86 64/32 div instruction. The same trick would work on x86-64 by using the 128/64 divisions.

I am not sure how good the machine code you get out of your C++ is in the end, but it's hard to beat this handwritten assembly. Of course, you can do better on x86-64 because there are more registers and you don't have to spill on to the stack.

[WalterBright]

What's the license? Hopefully, Boost or Boost compatible?

[danlark1]

For compiler-rt it is Apache 2.0 license

https://github.com/llvm/llvm-project/blob/master/compiler-rt...

[WalterBright]

Thank you. We've standardized on the Boost license for D, as it is the least restrictive, and well-accepted in the C++ community.

Is it possible you can make a Boost licensed version of it so we can add it to D?

https://www.boost.org/LICENSE_1_0.txt

[danlark1]

That's a difficult question. As I am working at Google I need to consult each open source I want to publish on my behalf. This does not involve contributing to the list of the approved projects and telling about these contributions.

If you want to workaround this for now, I suggest looking into libdivide (https://github.com/ridiculousfish/libdivide), it is published with the boost license and the library contains all the needed artifacts I described in the article (unfortunately, not combined).

[WalterBright]

Thanks for the pointers. I suspect Google would be ok with Boost, since they are a C++ house and Boost is the major library. A big reason D picked it was because Boost is corporate lawyer approved.