Archive

Posts Tagged ‘GUID’

GUID generation

September 21, 2011 1 comment

I recently had to generate globally unique identifiers (GUIDs) for a personal project that I have at home. They could be generated concurrently on several threads and on multiple machines over the network, and the only rules I wanted to stick with were to avoid duplicates and be as fast as possible. Here’s what I ended up with:

void GUID::GenerateUnique()
{
    Time Time;
    GetTime(Time);

    static tU16 StaticMask = 0;
    StaticMask = InterlockedIncrement(StaticMask);

    A = GUUID;
    B = GMACAddress >> 16;
    C = (StaticMask << 16) | (GMACAddress & 0xffff);
    D = (Time.Second + Time.Minute * 60 + Time.Hour * 60 * 60) | (Time.Month << 17) | (Time.Day << 22) | ((Time.Year - 2011) << 27);

    // Simple encryption
    tU32 Mask = (StaticMask << 16) | ((StaticMask * 0x0bb38435) + 0x3619636b);
    A = ~A ^ Mask;
    B = ~B ^ Mask;
    C = ~C ^ StaticMask; // don't encrypt the mask itself
    D = ~D ^ Mask;
}

A, B, C and D are 32-bits unsigned values. A contains a CRC32 of the PC’s username. The PC’s MAC address is encoded in B and C parts. The remaining 16 bits of C also contains a sequential number which is atomically incremented at each call to avoid generating the same GUID when called from multiple threads. D contains a timestamp, similar to a Unix Time. At the end, a quite simple encryption scheme is used to make sure that the MAC address isn’t easily exposed directly in the GUID.

One cool thing about this is that at any point, a GUID can be decrypted and everything can be extracted from it; the CRC32 of the user who generated it, the MAC address and the timestamp:

String GUID::GetDescStr() const
{
    tU16 StaticMask = ~(C >> 16);
    tU32 Mask = (StaticMask << 16) | (StaticMask * 0x0bb38435) + 0x3619636b;
    tU32 Mac0 = ~(B ^ Mask);
    tU32 Mac1 = ~(C ^ StaticMask);

    String Result = String::Printf(
        "UUID:%08x MAC:%02x-%02x-%02x-%02x-%02x-%02x ",
        ~(A ^ Mask),
        (tU32)((Mac0 & 0xff000000) >> 24),
        (tU32)((Mac0 & 0xff0000) >> 16),
        (tU32)((Mac0 & 0xff00) >> 8),
        (tU32)((Mac0 & 0xff)),
        (tU32)((Mac1 & 0xff00) >> 8),
        (tU32)((Mac1 & 0xff))
    );

    tU32 Timestamp = ~(D ^ Mask);
    tU32 Seconds = (Timestamp & 0x1ffff);
    tU32 Month = ((Timestamp >> 17) & 0x1f);
    tU32 Day = ((Timestamp >> 22) & 0x1f);
    tU32 Year = (Timestamp >> 27) + 2011;
    tU32 Hour = (Seconds / (60 * 60));
    Seconds -= Hour * 60 * 60;
    tU32 Minute = (Seconds / 60);
    Seconds -= Minute * 60;

    Result += String::Printf("Date:%d-%02d-%02d %d:%02d:%02d ", Year, Month, Day, Hour, Minute, Seconds);
    Result += String::Printf("Mask:0x%08x", Mask);

    return Result;
}

Size didn’t matter in my case, but this could be easily reduced to 96-bits by removing the CRC32 of the username, without changing the uniqueness of the GUIDs. If the size really matters, one could possibly reduce it to 64-bits by using the CRC32 of the username and the timestamp, but the function would possibly need to be protected by a critical-section to avoid 2 threads generating the exact same GUID.

Advertisements
Categories: Programming Tags:
%d bloggers like this: