Implement rotate functions for ApInts

[AaronKutch]

This will be useful to me for making a fuzzer and for cryptography related purposes. What should it be named? Some names I found include:

• rotl_assign/rotr_assign
• rotate_left_assign/rotate_right_assign
• rotatel_assign/rotater_assign I will implement it.

[Robbepop]

Well in Rust these methods are called rotate_left and rotate_right and I think we should just do the same.

[AaronKutch]

I forgot about those functions. I will use those names.

[AaronKutch]

I am going to postpone finishing this one for a while.

[AaronKutch]

I implemented a working function. Good news is that I found a way to always avoid allocation, do it in O(n), and support non Digit multiple width apints all at the same time, which was really hard. It is slightly faster than the current shift left and right functions, so I will optimize those also. Compared to the ramp crate it is slightly slower than the right shift so we are in a decent place.

[Robbepop]

Hey, sounds good! Can you please make a PR so I can review it? Also would be very nice if you could show some benchmarks here.

How is the algorithm comparable with the one used in std::slice::rotate_{left,right} ?

[AaronKutch]

I looked around online for rotate shift functions in bigint libraries and there seems to be none, and I completely forgot about coarser rotate functions. I have a Digit wise rotate function used as part of the algorithm. I benchmarked it against slice::rotate_left and it starts slower than my function but gets faster than my function after about a slice of length 16. I think I will investigate a little more.

[Robbepop]

Hmm, .. I am currently thinking about the semantic meaning of a rotate function for machine integers. What is it? For shift-left we for example can conclude that it is similar to a multiply by 2 - so it is actually useful to support such an operation. But what is the precise semantics of a rotate left or right for integer arithmetic purposes? I know that in Rust the very generic slices constructs support them, but for those it is useful since rotation could be useful for slice constructs.

[AaronKutch]

It has no numerical meaning but it does have a meaning for the logical bits. The rotate functions are mainly for stuff like hashing and cryptography purposes, which is one of the things the library is targeting as stated in the readme. As far as I know, this library will be the first bigint library ever to support a direct rotation function. I remember now that you based this library initially off some LLVM library that also had an explicit width to its integers, but I can't find the name. Maybe my google-fu is not strong enough.

[Robbepop]

Ah okay for crypto-foo it might be an interesting operation!

It is based on: https://llvm.org/doxygen/classllvm_1_1APInt.html

[AaronKutch]

Ok the LLVM library does include rotate functions as rotl and rotr, which appear to me to use allocation. Should I rename to rotl and into_rotl?

[Robbepop]

I think we should stick to the Rust convention here and use rotate_left and rotate_right here. Could you please also do some elaborations (in form of documentation) on how to the algorithm without allocations works - if you haven't already done that? It seems to be a non-trivial problem if even the LLVM version of ApInt hasn't done it.

[AaronKutch]

Oh it is far from trivial I just pushed my work so far to my fork and the commit titled "Implement barrel or circular shifts" has the stuff. My benchmarks show it takes half as much time as the allocation one.

[Robbepop]

That sounds super awesome! I really appreciate that being merged with proper docs and some benchmarks for a show-off for the next public release. :)