Oculus Rift DK2 IR-LED ECC Generator Algorithm

oculus_led_ecc.c

/*
** This is the algorithm that generates the error correction code (ECC) used to identify each IR-LED in
** the Oculus Rift DK2.
** More information on the DK2 optical tracking system can be found in the blog post series
** "Hacking the Oculus Rift DK2" by Oliver Kreylos: http://doc-ok.org/?p=1095
** 
** This algorithm was *not* found in the binaries provided by Oculus (they only include pre-computed LUTs).
** 
** The algorithm is pretty simple:
** All code words need to fulfil two requirements:
** - Each code word must be different enough from all other code words (Hamming distance >= 3)
** - If a code word is rotated (bit-wise) it may never match any other code word
** Try each 10-bit integer starting at 1. If both conditions are met, the number is a valid code word.
**
** Public domain
** https://github.com/nairol
*/

#include <stdio.h>
#include <stdlib.h>

// Returns the number of bits to flip to get from one code word to the other.
unsigned int hammingDistance( unsigned int codeWordA, unsigned int codeWordB )
{
    unsigned int difference = codeWordA ^ codeWordB;
    unsigned int distance = 0;
    while( difference != 0 ) // Count all "1" bits (=differences)
    {                        // Slow but simple. Use compiler intrinsic "popcnt" for more speed.
        distance += difference & 1;
        difference = difference >> 1;
    }
    return distance;
}

// Returns the number of rotations to the right required to produce a match between both code words.
// Returns <maxBits> if no match was found.
unsigned int rotateAndMatch( unsigned int codeWordA, unsigned int codeWordB, unsigned int maxBits )
{
    unsigned int codeBitMask = (1<<maxBits)-1;
    unsigned int offset;
    for( offset = 1; offset < maxBits; offset++ )
    {
        unsigned int rotated = ((codeWordA >> offset) | (codeWordA << maxBits-offset)) & codeBitMask;
        if( rotated == codeWordB )
            break;
    }
    return offset;
}

// Parameters: <codeWords>: Filled by this function with up to <maxCodeWords> code words
//             <maxBits>: Length of the code words in bits
//             <minDistance>: Hamming distance of the code
//             <startAt>: First integer that should be tested
// Returns the number of code words written
unsigned int generateOculusECC( unsigned int codeWords[], unsigned int maxCodeWords,
                                unsigned int maxBits, unsigned int minDistance, unsigned int startAt )
{
    unsigned int maxCandidates = 1<<maxBits;
    unsigned int codeWordCount = 0;
    
    for( unsigned int candidate = startAt; candidate < maxCandidates; candidate++ )
    {
        int checkFailed = 0;
        for( unsigned int codeWordIndex = 0; codeWordIndex < codeWordCount; codeWordIndex++ )
        {
            // Check Hamming distance to all other code words:
            unsigned int distance = hammingDistance( candidate, codeWords[codeWordIndex] );
            if( distance < minDistance )
            {
                checkFailed = 1; break; // Hamming distance too small, try next candidate
            }
            
            // Check if any (bit-)rotated version of this codeword matches any other code word:
            unsigned int rotations = rotateAndMatch( candidate, codeWords[codeWordIndex], maxBits );
            if( maxBits > rotations )
            {
                checkFailed = 2; break; // A rotated version of this candidate already exists, try next
            }
        }
        
        if( checkFailed > 0 )
            continue;
        
        codeWords[codeWordCount] = candidate;
        codeWordCount++;
        if( codeWordCount >= maxCodeWords )
            break;
    }
    return codeWordCount;
}

int main( )
{
    unsigned int code[100];
    unsigned int codeLength = 100;
    char stringBuffer[11];
    
    codeLength = generateOculusECC( code, codeLength, 10, 3, 1 );
    
    printf(" LED | Pattern(b) | Pattern(d)\n");
    printf("-----+------------+-----------\n");
    for( int i = 0; i < codeLength; i++ )
    {
        itoa( code[i], stringBuffer, 2 );
        printf("  %2d | %010s | %3d\n", i, stringBuffer, code[i]);
    }
}

/* Output:

 LED | Pattern(b) | Pattern(d)
-----+------------+-----------
   0 | 0000000001 |   1
   1 | 0000000110 |   6
   2 | 0000011010 |  26
   3 | 0000011101 |  29
   4 | 0000101000 |  40
   5 | 0000101111 |  47
   6 | 0000110011 |  51
   7 | 0001001011 |  75
   8 | 0001001100 |  76
   9 | 0001010111 |  87
  10 | 0001100010 |  98
  11 | 0001100101 | 101
  12 | 0001111001 | 121
  13 | 0001111110 | 126
  14 | 0010010000 | 144
  15 | 0010100100 | 164
  16 | 0100010100 | 276
  17 | 0101010001 | 337
  18 | 0110000011 | 387
  19 | 0110001100 | 396
  20 | 0110011001 | 409
  21 | 0110101010 | 426
  22 | 0110110101 | 437
  23 | 0111000000 | 448
  24 | 0111001111 | 463
  25 | 0111010110 | 470
  26 | 0111101001 | 489
  27 | 0111110011 | 499
  28 | 0111111100 | 508
  29 | 1000110000 | 560
  30 | 1001010010 | 594
  31 | 1010000010 | 642
  32 | 1010000101 | 645
  33 | 1010011011 | 667
  34 | 1010011100 | 668
  35 | 1010101110 | 686
  36 | 1010110111 | 695
  37 | 1011001000 | 712
  38 | 1011010001 | 721
  39 | 1011100011 | 739
  40 | 1011101101 | 749
  41 | 1011111010 | 762
  42 | 1100000111 | 775
  43 | 1100001001 | 777
  44 | 1100011110 | 798
  45 | 1100100100 | 804
  46 | 1100111011 | 827
  47 | 1101001010 | 842
  48 | 1101011101 | 861
  49 | 1101100001 | 865
  50 | 1101101111 | 879
  51 | 1101111000 | 888
  52 | 1110110010 | 946
*/