Fast & Lightweight Random “Shuffle” Functionality – FIXED!

In this post I’m going to show a way to make an iterator that will visit items in a list in a random order, only visit each item once, and tell you when it’s visited all items and is finished. It does this without storing a shuffled list, and it also doesn’t have to keep track of which items it has already visited.

This means you could have a list that is a million items long and no matter how many you have visited, it will only take two uint32s to store the current state of the iterator, and it will be very fast to get the next item in the list (somewhere around 1 to 4 times the cost of calling the rand() function!).

This is a follow up post to an older post called Fast & Lightweight Random “Shuffle” Functionality.

In that older post, things didn’t work quite like I expected them to so it was back to the drawing board for a little while to do some research and experimentation to find a better solution. I’m not going to go back over the basics I talked about in that article so go back and have a read there first if anything is confusing.

High Level

In the last post on this topic we talked about how the high level goal was to map the index to a random number, and because we were randomizing the bits in a deterministic (and non destructive) way, we needed to iterate over the whole “next power of 2” items and reject any that were too large. Only doing this could we be sure that we visited every index. The problem I hit last time though was that I could not get the numbers to look random enough.

To solve this, i decided what i needed to do was ENCRYPT the index with a block cipher. When you encrypt data, it should come out looking like random data, even though the data you put in may be sequential or have other easily seen patterns. What else is great, is that when using a block cipher, each unique input should equate to a unique output which means that if we encrypt the full power of 2 range as input, we will get the full power of 2 range out as output, but just in a different order.

Once I realized this was a good solution, my next problem to tackle was that I knew of no block algorithms that would work for a variable number of bits. There are block cipher algorithms that will work for LARGE number of bits, but there is no algorithm I knew of where you can tell it “hey, i only want to use 4 bits” or “i only want to use 5 bits”.

In the end the answer I found was to roll my own, but use existing, well established technology to do so. In my specific case, I’m also aiming for high speed functions since I want this functionality used in real time gaming applications.

What I came up with in the end is not cryptographically secure, but using the same techniques I have laid out, you should be able to drop in a different block cipher algorithm if that is a requirement.

Feistel Network

As it turns out, there is a basic primitive of cryptography called a Feistel Network. It’s used by quite a number of modern ciphers and hash functions, and it is surprisingly simple.

For a balanced Feistel Network, you split the data into a left and a right side, and do the following, which consists of a single round (you can do as many rounds as you like):

Left[i+1]  = Right[i];
Right[i+1] = Left[i] ^ RoundFunction(Right[i], key);

After performing however many rounds you wish, you combine the left and the right sides again to get your encrypted data.

To unencrypt, the feistel network works much the same but only in reverse, looking like the below:

Right[i] = Left[i+1];
Left[i] = Right[i+1] ^ RoundFunction(Left[i+1], key);

Check out the wikipedia page if you are interested in more info.

The neat thing about Feistel Networks is that the round function can be any deterministic function that performs whatever operations it wants – even destructive and irreversible operations such as division or bit shifts. Even so, the feistel network as a whole is reversible, no matter what you do in the round function, and you can unencrypt to get your origional data back.

This threw me for quite a loop and I couldn’t get my head around why this worked for a long while until I found a webpage that explained it pretty well. unfortunately I lost the link and cannot find it again but the basic idea is this… For each round of encryption, the right side is encrypted using the key and the left side. This means that at any point, no matter how many rounds you’ve done on your data, the right side should be able to be decrypted using the key and the left side. If you have the key, and you know how many rounds were used in encryption, you have all the data you need to decrypt it again. Hopefully that makes sense… I had to work it out on paper a little bit to see it fully.

The other great thing about Feistel Networks is that you can make them be however many bits you want. So, if i want each side of the Feistel Network to be 1 bit, I can do that. Or, if i want each side to be 128 bits, I can do that too!

You can also tune the quality / performance a bit by doing less or more rounds.

BTW the Tiny Encryption Algorithm uses a Feistel Network if you want to see a simple example in action.

With the “variable bit size support” problem solved, next I needed to come up with a round function that did a good job of taking sequential numbers as input and spitting out seemingly random numbers as output. Thanks to what I was saying before, the round function doesn’t need to be reversible, so there are a lot of options available.

I ended up deciding to go with a hash function, specifically Murmur Hash 2 (which I actually also used in my last post if you’d like to see some more information on it! The Incredible Time Traveling Random Number Generator).

Since the hash spits out numbers that might be anything in the range of an unsigned int, but I only want N bits, I just AND the hash against a mask to get the number of bits I want. There’s probably a higher quality method of smashing down the bits using XOR or something, but my quality needs aren’t very high so I just opted to AND it.

A downside of going with the balanced Feistel Network approach is that before this, I only had to round up to the next power of 2, but now, since each half of the data needs to be a power of 2, I actually have to make sure I have an even number of bits and have to round up to the next power of 4. This means that when it’s looking for valid indices to return in the shuffle, it may have to calculate up to 4 different indices on average before it finds a valid one. Not the greatest thing in the world, but also not the worst and definitely not a deal breaker in my eyes.

The Code

At long last, here is the code! Use it in good health (:

There are some example runs of the program below it as well.

#include
#include
#include

// MurmurHash code was taken from https://sites.google.com/site/murmurhash/
//—————————————————————————–
// MurmurHash2, by Austin Appleby

// Note – This code makes a few assumptions about how your machine behaves –

// 1. We can read a 4-byte value from any address without crashing
// 2. sizeof(int) == 4

// And it has a few limitations –

// 1. It will not work incrementally.
// 2. It will not produce the same results on little-endian and big-endian
// machines.

unsigned int MurmurHash2 ( const void * key, int len, unsigned int seed )
{
// ‘m’ and ‘r’ are mixing constants generated offline.
// They’re not really ‘magic’, they just happen to work well.

const unsigned int m = 0x5bd1e995;
const int r = 24;

// Initialize the hash to a ‘random’ value

unsigned int h = seed ^ len;

// Mix 4 bytes at a time into the hash

const unsigned char * data = (const unsigned char *)key;

while(len >= 4)
{
unsigned int k = *(unsigned int *)data;

k *= m;
k ^= k >> r;
k *= m;

h *= m;
h ^= k;

data += 4;
len -= 4;
}

// Handle the last few bytes of the input array

switch(len)
{
case 3: h ^= data[2] << 16; case 2: h ^= data[1] << 8; case 1: h ^= data[0]; h *= m; }; // Do a few final mixes of the hash to ensure the last few // bytes are well-incorporated. h ^= h >> 13;
h *= m;
h ^= h >> 15;

return h;
}

struct SShuffler
{
public:
SShuffler(unsigned int numItems, unsigned int seed)
{
// initialize our state
m_numItems = numItems;
m_index = 0;
m_seed = seed;

// calculate next power of 4. Needed sice the balanced feistel network needs
// an even number of bits to work with
m_nextPow4 = 4;
while (m_numItems > m_nextPow4)
m_nextPow4 *= 4;

// find out how many bits we need to store this power of 4
unsigned int numBits = 0;
unsigned int mask = m_nextPow4 – 1;
while(mask)
{
mask = mask >> 1;
numBits++;
}

// calculate our left and right masks to split our indices for the feistel
// network
m_halfNumBits = numBits / 2;
m_rightMask = (1 << m_halfNumBits) - 1; m_leftMask = m_rightMask << m_halfNumBits; } void Restart() { Restart(m_seed); } void Restart(unsigned int seed) { // store the seed we were given m_seed = seed; // reset our index m_index = 0; } // Get the next index in the shuffle. Returning false means the shuffle // is finished and you should call Restart() if you want to start a new one. bool Shuffle(unsigned int &shuffleIndex) { // m_index is the index to start searching for the next number at while (m_index < m_nextPow4) { // get the next number shuffleIndex = NextNumber(); // if we found a valid index, return success! if (shuffleIndex < m_numItems) return true; } // end of shuffled list if we got here. return false; } // Get the previous index in the shuffle. Returning false means the shuffle // hit the beginning of the sequence bool ShuffleBackwards(unsigned int &shuffleIndex) { while (m_index > 1)
{
// get the last number
shuffleIndex = LastNumber();

// if we found a valid index, return success!
if (shuffleIndex < m_numItems) return true; } // beginning of shuffled list if we got here return false; } private: unsigned int NextNumber() { unsigned int ret = EncryptIndex(m_index); m_index++; return ret; } unsigned int LastNumber() { unsigned int lastIndex = m_index - 2; unsigned int ret = EncryptIndex(lastIndex); m_index--; return ret; } unsigned int EncryptIndex(unsigned int index) { // break our index into the left and right half unsigned int left = (index & m_leftMask) >> m_halfNumBits;
unsigned int right = (index & m_rightMask);

// do 4 feistel rounds
for (int index = 0; index < 4; ++index) { unsigned int newLeft = right; unsigned int newRight = left ^ (MurmurHash2(&right, sizeof(right), m_seed) & m_rightMask); left = newLeft; right = newRight; } // put the left and right back together to form the encrypted index return (left << m_halfNumBits) | right; } private: // precalculated values unsigned int m_nextPow4; unsigned int m_halfNumBits; unsigned int m_leftMask; unsigned int m_rightMask; // member vars unsigned int m_index; unsigned int m_seed; unsigned int m_numItems; // m_index assumptions: // 1) m_index is where to start looking for next valid number // 2) m_index - 2 is where to start looking for last valid number }; // our songs that we are going to shuffle through const unsigned int g_numSongs = 10; const char *g_SongList[g_numSongs] = { " 1. Head Like a Hole", " 2. Terrible Lie", " 3. Down in It", " 4. Sanctified", " 5. Something I Can Never Have", " 6. Kinda I Want to", " 7. Sin", " 8. That's What I Get", " 9. The Only Time", "10. Ringfinger" }; int main(void) { // create and seed our shuffler. If two similar numbers are hashed they should give // very different results usually, so for a seed, we can hash the time in seconds, // even though that number should be really similar from run to run unsigned int currentTime = time(NULL); unsigned int seed = MurmurHash2(&currentTime, sizeof(currentTime), 0x1337beef); SShuffler shuffler(g_numSongs, seed); // shuffle play the songs printf("Listen to Pretty Hate Machine (seed = %u)\r\n", seed); unsigned int shuffleIndex = 0; while(shuffler.Shuffle(shuffleIndex)) printf("%s\r\n",g_SongList[shuffleIndex]); system("pause"); return 0; } [/cpp] shuf1

shuf2

shuf3

shuf4

Comments

comments

About Demofox

I'm a game and engine programmer at Blizzard Entertainment and have been making games since 1990 (starting out with QBasic and TI-85 games) My shipped titles include: * Heroes of the Storm * StarCraft II: Heart of the Swarm & Legacy of the void * Insanely Twisted Shadow Planet (PC) * Gotham City Impostors (PC, 360, PS3) * Line Rider (PC, Wii, DS) I also like hiking, making music, learning cool new stuff and attempting the impossible.