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.

Generate random 32bit integers until you've got enough to randomly set each byte. — JustinDanielson
– JustinDanielson, Commented Apr 22, 2015 at 23:43
To clarify, do you want to permute in the technical sense of a permutation? Or do you just want basically random bytes in the array? If the former, what do you mean by "randomly" permuting them? If the latter, is Random.nextBytes what you're looking for? — yshavit
– yshavit, Commented Apr 23, 2015 at 1:26
Is your random lookup table equivalent to the mathematical concept of a permutation in the sense that there is some number n such that every input will be mapped to itself when P is applied n times? — muued
– muued, Commented Apr 27, 2015 at 13:56
I think P is basically an array of numbers 0 to blocksize*8 with no repeats in random order. That is it is a bidirectional lossless mapping of one domain integer to another integer within the same range. He also apparently has guaranteed that P[i] never maps to itself. — Adam Gent
– Adam Gent, Commented Apr 27, 2015 at 14:21

muued · Accepted Answer · 2015-07-10 08:20:55Z

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;
}

edited Jul 10, 2015 at 8:20

answered Apr 27, 2015 at 17:21

muued

1,67614 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Paul Uszak Over a year ago

I've just substituted this code for mine and re-profiled it in NetBeans. The new code saves 25% in overall run time. The bulk of the time is equally shared between the .nextSetBit and .set methods.

Paul Uszak Over a year ago

Came back to this recently. Could I avoid the toing & froing of a bitset and just convert the input to a boolean array? Performing the permutation operations on a boolean array might be faster than converting bits -> longs (in bitset) and visa versa..?

muued Over a year ago

i can't imagine that twofold conversion would give you a speedup compared to working on a byte[] directly. I added such a solution to my answer.

Collectives™ on Stack Overflow

Fastest way to permute bits in a Java array

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related