Fastest way to permute bits in a Java array

Question

What is the fastest way to randomly (but repeatedly) permute all the bits within a Java byte array? I've tried successfully doing it with a BitSet, but is there a faster way? Clearly the for-loop consumes the majority of the cpu time.

I've just done some profiling in my IDE and the for-loop constitutes 64% of the cpu time within the entire permute() method.

To clarify, the array (preRound) contains an existing array of numbers going into the procedure. I want the individual set bits of that array to be mixed up in a random manner. This is the reason for P[]. It contains a random list of bit positions. So for example, if bit 13 of preRound is set, it is transferred to place P[13] of postRound. This might be at position 20555 of postRound. The whole thing is part of a substitution - permutation network, and I'm looking to the fastest way to permute the incoming bits.

My code so far...

 private byte[] permute(byte[] preRound) {
    BitSet beforeBits = BitSet.valueOf(preRound);
    BitSet afterBits = new BitSet(blockSize * 8);


    for (int i = 0; i < blockSize * 8; i++) {
        assert i != P[i];


        if (beforeBits.get(i)) {
            afterBits.set(P[i]);
        }
    }


    byte[] postRound = afterBits.toByteArray();
    postRound = Arrays.copyOf(postRound, blockSize);      // Pad with 0s to the specified length
    assert postRound.length == blockSize;


    return postRound;
}

FYI, blockSize is about 60,000 and P is a random lookup table.

Answer 1

I didn't perform any performance tests, but you may want to consider the following: To omit the call to Arrays.copyOf (which copies the copy of the long[] used interally, which is kind of annoying), just set the last bit in case it wasn't set before and unset it afterwards.

Furthermore, there is a nice idiom to iterate over the set bits in the input permutation.

private byte[] permute(final byte[] preRound) {
    final BitSet beforeBits = BitSet.valueOf(preRound);
    final BitSet afterBits = new BitSet(blockSize*8);
    for (int i = beforeBits.nextSetBit(0); i >= 0; i =
            beforeBits.nextSetBit(i + 1)) {
        final int to = P[i];
        assert i != to;
        afterBits.set(to);
    }
    final int lastIndex = blockSize*8-1;
    if (afterBits.get(lastIndex)) {
        return afterBits.toByteArray();
    }
    afterBits.set(lastIndex);
    final byte[] postRound = afterBits.toByteArray();
    postRound[blockSize - 1] &= 0x7F;
    return postRound;
}

If that doesn't cut it, in case you use the same P for lots of iterations, it may be worthwhile to consider transforming the permutation into cycle notation and perform the transformation in-place. This way you can linearly iterate over P which may enable you to better exploit caching (P is 32 times as large as the byte array, assuming its an int array). Yet, you will lose the advantage that you only have to look at 1s and end up shifting around every single bit in the byte array, set or not.

If you want to avoid using the BitSet, you can just do it by hand:

private byte[] permute(final byte[] preRound) {
    final byte[] result = new byte[blockSize];
    for (int i = 0; i < blockSize; i++) {
        final byte b = preRound[i];
        // if 1s are sparse, you may want to use this:
        // if ((byte) 0 == b) continue;
        for (int j = 0; j < 8; ++j) {
            if (0 != (b & (1 << j))) {
                final int loc = P[i * 8 + j];
                result[loc / 8] |= (1 << (loc % 8));
            }
        }
    }
    return result;
}