Xincrol - unique and random number generation algorithm.

Xincrol - unique and random number generation algorithm.

The challenge.

Every serious programmer writing serious code at least once in his life has been stuck with this problem.
How to generate random numbers, but in a way so each number will appear only once. 
Regular Random Number Generators (RNG) don't guaranty any uniqueness of provided numbers.
Programmers were using large random numbers like UUID(MD5) to hope that the same number will not appear twice in their life . But this does happen, I have seen it many times with large and dynamically changing databases, where object IDs were collided and this caused applications to crash, reports to fail, data lost etc.
The other common practice is to create huge array, fill it with serial numbers and shuffle this array for long time to have more-less acceptable level of randomness.
Those solutions are very CPU and memory consuming.
At the same time there are millions of SW applications which are seriously require URNGs.
Some examples of such applications:

  • Video and Image Effects
  • Encryption 
  • Steganography
  • All kinds of unique but secure (not serial) IDs (ex. any website with big DB)
  • Random serial numbers for money bills, car license plates, airplane part numbers etc. 
  • MP3 player playlist shuffling
  • Playing Cards shuffling for Casinos
  • Absolutely every Computer game needs unique randomization
  • ASCII to ASCII encryption/decryption 
  • Random memory or disk space addressing
  • more...

We all needed a function which will do the job.
I discovered it!


 

The Discovery.

If your input is serial numbers stream (like 0,1,2,3...) and you will perform cycling and directional bitwise operations in some predefined order you will get the same set of numbers but placed in different positions.
Magical operations are XOR, INC and ROL (the name of algorithm).

private int XOR(int iA, int iB, int iBaseMask) {
return ((iA ^ iB) & iBaseMask);
}
 
private int INC(int iA, int iBaseMask) {
return ((++iA) & iBaseMask);
}
 
private int ROL(int iA, int iBaseMask) {
iA = (iA & iBaseMask) << 1;
if (iA > iBaseMask) {
iA = (iA & iBaseMask) | 1;
}
return (iA);
}

There are also DEC and ROR operations which could be used instead of INC and ROL.

There are 4 possible groups of operations: 

 

  • XOR, INC, ROL 

  • XOR, DEC, ROL

  • XOR, INC, ROR

  • XOR, DEC, ROR

 

where...

XOR - exclusive disjunction, 

INC - cyclic incrementation, 

DEC - cycling decrementation, 

ROL - rotation left, 

ROR - rotation right.

 

Why is this happening? Well, because those operations are cyclic and directional. When you increment a variable, it grows up to biggest number in the range and then drops to 0. So, regardless on how many times you will perform this operation, but if you will always repeat it the same number of times, you will get the unique numbers output if your input is unique. One such operation doesn't really shuffle the input stream but if combined with other two, shuffling and randomness becomes really strong.

 
Important: Don't use INC and DEC  in the same cycle, don't use ROR and ROL in the same cycle!
 
 
Here I am publishing simple Java code of one of my Xincrol implementations.
This implementation also has ability to set a different range for generated unique numbers.
There is main() method below that demonstrates how it works. 
Have it! Enjoy it! 
Stop working with huge arrays, hashcodes and UUIDs!
 
If you need some help to integrate Xincrol into your project please leave me a comment here or write me an email. 
 
---------------------------------------------------------------
 
 

 

 

 

 

 

 

 

 

/**
 * Xincrol - Unique and Random Number Generator
 * Xincrol.java
 * Purpose: Generating unique random numbers in specified range.
 *
 * @author Tofig Kareemov
 * @version 1.5 2013.04.30
 * 
 * v1.5 notes: Fixed bug in ROL and ROR functions
 * 
 * v1.4 notes: added REFLECT and NOT methods
 */
package androphic.estereos.lib.algs;

public class Xincrol {
    // Private Data...
    private int iUniqueSeed = 0;
    private int[] iKey = new int[8];
    private int iSet = 0;
    private String sSystemID = "";

    // Constructor
    public Xincrol() {
        sSystemID = System.getProperties().toString();
        hashKey(sSystemID, true);
        iSet = iKey[iKey.length - 1] & 3;
        reset(Integer.MAX_VALUE);
    }

    // .

    // Private Methods...
    private void reset(int iBase) {
        iUniqueSeed = 0;
        hashKey("" + System.nanoTime(), false);
        hashKey("" + System.currentTimeMillis(), false);
        glueKey(iBase);
        iSet = iKey[iKey.length - 1] & 3;
    }

    private void hashKey(String sKey, boolean bNew) {
        if ((sKey == null) || ("".equals(sKey))) {
            return;
        }
        if (bNew) {
            for (int i = 0; i < iKey.length; ++i) {
                int iKeyValue = 0;
                for (int i1 = 0; i1 < 4; ++i1) {
                    int iBit = (i >>> i1) & 1;
                    if (iBit == 1) {
                        iKeyValue = (iKeyValue | 0x5a);
                    } else {
                        iKeyValue = (iKeyValue | 0xa5);
                    }
                    if (i1 < 3) {
                        iKeyValue <<= 8;
                    }
                }
                iKey[i] = iKeyValue;
            }
        }
        for (int i = 0; i < sKey.length(); ++i) {
            int iChar = sKey.charAt(i);
            int iKeyIndex = i % iKey.length;
            iKey[iKeyIndex] ^= iChar;
            iKey[iKeyIndex] = ROL(iKey[iKeyIndex], 0xffffffff);
        }
    }

    private void glueKey(int iBase) {
        int iGlue = iKey[iKey.length - 1];
        int iBaseMask = iBase - 1;
        for (int i1 = 0; i1 < iKey.length; ++i1) {
            iGlue ^= i1;
            for (int i = 0; i < iKey.length; ++i) {
                iGlue ^= i;
                iGlue ^= iKey[i];
                switch (iKey[i] & 3) {
                case 0:
                    iGlue = rolror(iGlue, iSet, iBaseMask);
                    break;
                case 1:
                    iGlue = incdec(iGlue, iSet, iBaseMask);
                    break;
                case 2:
                    iGlue = REFLECT(iGlue, iBaseMask);
                    break;
                case 3:
                    iGlue = NOT(iGlue, iBaseMask);
                    break;
                }
                iKey[i] = XOR(iGlue, iKey[i], iBaseMask);
            }
        }
    }

    // Main Function
    private int XOR(int iA, int iB, int iBaseMask) {
        return ((iA ^ iB) & iBaseMask);
    }

    private int INC(int iA, int iBaseMask) {
        return ((++iA) & iBaseMask);
    }

    private int ROL(int iA, int iBaseMask) {
        iA = (iA & iBaseMask) << 1;
        if (iA > iBaseMask) {
            iA = (iA & iBaseMask) | 1;
        }
        return (iA);
    }

    // .

    // Additional Functions
    private int DEC(int iA, int iBaseMask) {
        return ((--iA) & iBaseMask);
    }

    private int ROR(int iA, int iBaseMask) {
        if ((iA & 1) == 1) {
            return ((iA & iBaseMask) >>> 1) | ((iBaseMask + 1) >>> 1);
        } else {
            return ((iA & iBaseMask) >>> 1);
        }
    }

    private int NOT(int iA, int iBaseMask) {
        return ((iA ^ iBaseMask) & iBaseMask);
    }

    private int REFLECT(int iA, int iBaseMask) {
        int iB = 0;
        for (; iBaseMask > 0; iBaseMask >>>= 1) {
            iA = ROR(iA, iBaseMask);
            iB |= iA & ((iBaseMask + 1) >>> 1);
        }
        return iB;
    }

    // .
    // .

    // Public Methods

    public synchronized void randomize(int iRange) {
        int iBase = 1;

        if (iRange <= 0) {
            return;
        }
        for (; iBase < iRange; iBase <<= 1) {
        }
        reset(iBase);
    }

    public int incdec(int iA, int iSet, int iBaseMask) {
        switch (iSet) {
        case 0:
            return INC(iA, iBaseMask);
        case 1:
            return DEC(iA, iBaseMask);
        case 2:
            return INC(iA, iBaseMask);
        case 3:
            return DEC(iA, iBaseMask);
        default:
            return 0;
        }
    }

    public int rolror(int iA, int iSet, int iBaseMask) {
        switch (iSet) {
        case 0:
            return ROL(iA, iBaseMask);
        case 1:
            return ROL(iA, iBaseMask);
        case 2:
            return ROR(iA, iBaseMask);
        case 3:
            return ROR(iA, iBaseMask);
        default:
            return 0;
        }
    }

    public synchronized int next(int iRange) {
        int iResult = iRange;
        int iBase = 1;

        for (; iBase < iRange; iBase <<= 1) {
        }
        if ((iKey == null) || (iUniqueSeed >= iBase)) {
            reset(iBase);
        }
        int iBaseMask = iBase - 1;
        for (int i = 0; (i < iBase) && (iResult >= iRange); ++i) {
            iUniqueSeed = (++iUniqueSeed) % iBase;
            iResult = iUniqueSeed;
            for (int i1 = 0; i1 < iKey.length; ++i1) {
                iResult = XOR(iResult, iKey[i1], iBaseMask);
                for (int i2 = iKey[i1] | iBase; i2 > 1; i2 >>>= 1) {
                    switch (i2 & 3) {
                    case 0:
                        iResult = rolror(iResult, iSet, iBaseMask);
                        break;
                    case 1:
                        iResult = incdec(iResult, iSet, iBaseMask);
                        break;
                    case 2:
                        iResult = REFLECT(iResult, iBaseMask);
                        break;
                    case 3:
                        iResult = NOT(iResult, iBaseMask);
                        break;
                    }
                }
            }
        }
        return iResult;
    }

    public synchronized int prev(int iRange) {
        int iResult = iRange;
        int iBase = 1;

        if (iRange <= 0) {
            return 0;
        }
        for (; iBase < iRange; iBase <<= 1) {
        }
        if ((iKey == null) || (iUniqueSeed >= iBase)) {
            reset(iBase);
        }
        int iBaseMask = iBase - 1;
        for (int i = 0; (i < iBase) && (iResult >= iRange); ++i) {
            iUniqueSeed = (--iUniqueSeed)