Given a fixed permutation, determine the fastest sequence of microprocessor instructions to rearrange the bits of a word by that permutation. The naive method is bit-shift and mask. We can improve on the naive method a little by opportunistically selecting all the bits that end up in the correct position after the shift.
Probably A* search algorithm. What heuristic?
What is the average number of instructions, over all permutations? What is the most difficult permutation? Interestingly, this task purely in hardware is absurdly simple: just a bunch of wires.
What additional instructions might help? Some bizarre possibilities: Reverse the order of bits in a word (or part of a word). Interleave the high and low half-words, and the inverse. The A-star heuristic becomes more complicated.
The obvious primitive (assuming 64-bit word) takes 10 6-bit numbers packed into a 64-bit argument, and extracts those bit positions from the second argument, and returns a 10-bit number. And the inverse: place the low 10-bits of an argument into the given bit positions. What circuitry implements this dynamic permutation efficiently in hardware? Is it worth it?
Motivation is cryptography, though we are often permuting bit strings longer than a machine word.
No comments :
Post a Comment