Provide hardware-accelerated assembly versions

[joshtriplett]

Various architectures provide native instructions that compute this operation, or parts of it. For instance, there exist instructions to convert or lookup many bytes/words/dwords at once as a vectorized operation. http://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c#24058332 provides one approach, which uses a vector register directly as a lookup table for nibbles.

[EugeneGonzalez]

I'm glad you posted this issue. This is in the future plans of the library after I finish more basic issues. Interesting I don't know of any ISA that has a bit reversal instruction, if you could point me towards one that would great.

The main problem with implementing the StackOverflow algorithm is the general lack of stability in SIMD instruction in Rust. There is a SIMD crate, but it doesn't support all the SIMD architectures and hasn't seen progress in awhile. There is a LLVM Intrinsics crate, but that is diving off the deep end in terms of compatibility and maintainability. Lastly, there is this current discussion on SIMDs in Rust/rfcs that might provide more context to the problem.

So while I could drop down to ASM to implement the enhanced vectored algorithm, I would like to wait until Rust has support to do it itself. That said this is still a running goal and when the opportunity arises, it will be addressed. If you submit a PR for this, I would be glad to accept it.

[joshtriplett]

I don't know of an architecture that directly has such an instruction, just architectures that can do it in a small handful of instructions.

I agree that ideally Rust should handle this without requiring inline assembly or LLVM intrinsics. I don't know how much it would take to make that work.