RFR: 8256431: [PPC64] Implement Base64 encodeBlock() for Power64-LE [v4]

[Martin Doerr]

On Wed, 16 Dec 2020 00:28:26 GMT, Corey Ashford <github.com+51754783+CoreyAshford at openjdk.org> wrote:

>>> Btw. I had also thought a bit about the division by constants. It's only used outside the loop. Otherwise I'd have suggested to use mulhd (e.g. positive long can get divided by 3 by mulhd with 0x5555555555555556, division by 12 by mulhd with 0x2aaaaaaaaaaaaaab + right shift by one). Such fast code gets generated by C2 compiler.
>> 
>> That's very interesting.  I'm not clear how that math works, but I tried it out in C using  the__int128 type, and it works as advertised.  However, since the division takes place outside the loop, it's hard to justify putting something this obtuse in the code.  Thanks for the thought, though.  I'll do some google searches to find out why this works for my own education.
>> 
>> I will put the struct change in tomorrow.  I think that's much cleaner.
>
> Ah, I see now.  It's basically multiplying by the binary-point reciprocal, and then accounting for the number of number of binary point digits, which in this case effectively means take the answer from the top 64 bits of the 128-bit result.

Right. It's tricky to make sure there will be no rounding errors, so the algorithm to determine the reciprocal together with the shift amount is not trivial. It's implemented in "magic_int_divide_constants" (divnode.cpp) and taken from "Hacker's Delight by Henry S. Warren, Jr." where you can find a detailed explanation. But we warned, verifying the proof takes time!
However, you can easily compute the constants by compiling a Java long division by C2 and disassembling.

-------------

PR: https://git.openjdk.java.net/jdk/pull/1245