diff options
Diffstat (limited to 'LibOVR/Src/OVR_SerialFormat.cpp')
| -rw-r--r-- | LibOVR/Src/OVR_SerialFormat.cpp | 477 |
1 files changed, 3 insertions, 474 deletions
diff --git a/LibOVR/Src/OVR_SerialFormat.cpp b/LibOVR/Src/OVR_SerialFormat.cpp index 027aed2..0b9a95b 100644 --- a/LibOVR/Src/OVR_SerialFormat.cpp +++ b/LibOVR/Src/OVR_SerialFormat.cpp @@ -6,16 +6,16 @@ Content : General kernel initialization/cleanup, including that Created : September 19, 2012 Notes : -Copyright : Copyright 2014 Oculus VR, Inc. All Rights reserved. +Copyright : Copyright 2014 Oculus VR, LLC All Rights reserved. -Licensed under the Oculus VR Rift SDK License Version 3.1 (the "License"); +Licensed under the Oculus VR Rift SDK License Version 3.2 (the "License"); you may not use the Oculus VR Rift SDK except in compliance with the License, which is provided at the time of installation or download, or which otherwise accompanies this software in either electronic or hard copy form. You may obtain a copy of the License at -http://www.oculusvr.com/licenses/LICENSE-3.1 +http://www.oculusvr.com/licenses/LICENSE-3.2 Unless required by applicable law or agreed to in writing, the Oculus VR SDK distributed under the License is distributed on an "AS IS" BASIS, @@ -357,343 +357,6 @@ void DK2PrintedSerialFormat::FromBinary(const DK2BinarySerialFormat& bin) } -//// Human Strings - -// For generator polynomial 101111b: -static const uint8_t GF32_LOG_TABLE[32] = { - 64, 31, 1, 12, 2, 24, 13, 27, 3, 8, 25, 10, 14, 18, 28, 5, - 4, 17, 9, 7, 26, 23, 11, 30, 15, 21, 19, 20, 29, 22, 6, 16 -}; -static const uint8_t GF32_ALOG_TABLE[129] = { - 1, 2, 4, 8, 16, 15, 30, 19, 9, 18, 11, 22, 3, 6, 12, 24, - 31, 17, 13, 26, 27, 25, 29, 21, 5, 10, 20, 7, 14, 28, 23, 1, - 2, 4, 8, 16, 15, 30, 19, 9, 18, 11, 22, 3, 6, 12, 24, 31, - 17, 13, 26, 27, 25, 29, 21, 5, 10, 20, 7, 14, 28, 23, 1, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0 -}; -static const uint8_t GF32_INV_TABLE[32] = { - 0, 1, 23, 26, 28, 19, 13, 16, 14, 21, 30, 25, 17, 6, 8, 20, - 7, 12, 29, 5, 15, 9, 27, 2, 31, 11, 3, 22, 4, 18, 10, 24 -}; - -// Multiplication in GF(32) : x * y = e^(log(x) + log(y)) -OVR_FORCE_INLINE uint8_t GF32Multiply(uint8_t x, uint8_t y) -{ - return GF32_ALOG_TABLE[GF32_LOG_TABLE[x] + GF32_LOG_TABLE[y]]; -} -OVR_FORCE_INLINE uint8_t GF32Divide(uint8_t x, uint8_t y) -{ - return GF32_ALOG_TABLE[GF32_LOG_TABLE[x] + 31 - GF32_LOG_TABLE[y]]; -} - -// Normally these inputs are constant so this is just useful for development -static bool ValidateHumanStringBits(int dataBits, int checkBits) -{ - // If no data bits or data bits leave no room for a checksum, - if (dataBits < 1 || dataBits >= 160) - { - OVR_ASSERT(false); - return false; - } - - // If no check bits or check bits leave no room for a checksum, - if (checkBits < 1 || checkBits >= 160) - { - OVR_ASSERT(false); - return false; - } - // Note: It's recommended to have at least 5 check bits so that - // character typos can be caught. - - // The sum of check bits and data bits must be a multiple of 5! - if ((checkBits + dataBits) % 5 != 0) - { - OVR_ASSERT(false); - return false; - } - - // The total number of human string digits cannot exceed 32. - if ((checkBits + dataBits + 4) / 5 > 32) - { - OVR_ASSERT(false); - return false; - } - - return true; -} - -// Generate check buffer -static void GenerateChecks(const uint8_t* data, int dataCount, uint8_t* checks, int checkCount, int msbCount) -{ - // For each check symbol to generate, - for (int i = 0; i < checkCount; ++i) - { - // Matrix multiplication inner loop - uint8_t x = 0; - for (int j = 0; j < dataCount; ++j) - { - // GF(32): x += d[i,j] * k, k = 1 / (j - i), ie. Cauchy matrix - x ^= GF32Multiply(data[j], GF32_INV_TABLE[(checkCount + j) ^ i]); - } - checks[i] = x; - } - - // Clear high bits of checks - if (msbCount > 0) - { - checks[checkCount - 1] &= (1 << msbCount) - 1; - } -} - -// Generates a Human-readable labels with built-in checksums -// Returns false on error -bool GenerateHumanString(int dataBits, // Number of bits to store - int checkBits, // Number of extra bits of checksum data - const unsigned char* input, // Bytes stored LSB-first - const int dataBytes, // Size of data buffer in bytes - String& resultStr) // Output string -{ - if (!ValidateHumanStringBits(dataBits, checkBits)) - { - return false; - } - - // If the buffer is the wrong size, - if (dataBytes < (dataBits + 7) / 8) - { - OVR_ASSERT(false); - return false; - } - - resultStr.Clear(); - - // Copy data bits - int dataCount = (dataBits + 4) / 5; - uint8_t data[32] = { 0 }; // Initialized to zeros - for (int i = 0; i < dataBits; ++i) - { - // Grab bit - int bit = (input[i / 8] >> (i % 8)) & 1; - - // Copy to data - data[i / 5] |= bit << (i % 5); - } - - // Generate checks - int checkCount = (checkBits + 4) / 5; - uint8_t checks[32]; - GenerateChecks(data, dataCount, checks, checkCount, checkBits % 5); - - // Copy full parts of checks after the partial character (if it exists) - int fullCheckCount = checkBits / 5; - for (int i = 0; i < fullCheckCount; ++i) - { - data[dataCount + i] = checks[i]; - } - - // If there is a partial check character, - int partialCheckBits = checkBits % 5; - if (partialCheckBits > 0) - { - // Write the high bits of the partial high symbol there - int word = checks[fullCheckCount] << (5 - partialCheckBits); - word &= 0x1f; - data[dataCount - 1] |= word; - } - - // Write base-32 representation of data - int outCount = (dataBits + checkBits) / 5; - for (int i = 0; i < outCount; ++i) - { - resultStr += CharFromBase32[data[i]]; - } - - return true; -} - -// Fix errors in data found by checks -static bool FixHumanChecksum(uint8_t* data, int dataCount, uint8_t* checks, int checkCount, int msbCount) -{ - uint8_t actualChecks[32]; - GenerateChecks(data, dataCount, actualChecks, checkCount, msbCount); - - // Search for check mismatches - int checkFails = 0; - for (int i = 0; i < checkCount; ++i) - { - if (actualChecks[i] != checks[i]) - { - ++checkFails; - } - } - - // Calculate full check count - int fullCheckCount = checkCount; - if (msbCount > 0) - { - fullCheckCount--; - } - - // If there is a lot of full check data, - if (fullCheckCount >= 2) - { - // Accept one error in the checks - if (checkFails <= 1) - { - return true; - } - - // Attempt to correct single errors: - for (int errPosition = 0; errPosition < dataCount; ++errPosition) - { - uint8_t oldData = data[errPosition]; - - // Use the first check symbol for corrections - uint8_t x = 0; - for (int j = 0; j < dataCount; ++j) - { - if (j != errPosition) - { - x ^= GF32Multiply(data[j], GF32_INV_TABLE[checkCount + j]); - } - } - x ^= checks[0]; - - // Calculate missing symbol - data[errPosition] = GF32Divide(x, GF32_INV_TABLE[checkCount + errPosition]); - - GenerateChecks(data, dataCount, actualChecks, checkCount, msbCount); - - // Search for check mismatches again: - int checkFails = 0; - for (int i = 0; i < checkCount; ++i) - { - if (actualChecks[i] != checks[i]) - { - // Ignore the partial checksum in case it got corrupted too - if (msbCount > 0 && - errPosition == dataCount - 1 && - i == checkCount - 1) - { - continue; - } - ++checkFails; - break; - } - } - - // Accept the correction if all checks agree now - if (checkFails == 0) - { - // Keep the correction if it succeeded - return true; - } - - data[errPosition] = oldData; - } - } - else - { - // Do not accept any check fails - if (checkFails <= 0) - { - return true; - } - } - - return false; -} - -// Returns number of bytes written to result, or zero on failure -int ProcessHumanString(int dataBits, // Number of bits to expect - int checkBits, // Number of extra bits of checksum data - String humanStr, // Human readable input string - unsigned char* result, // Output data buffer stored LSB-first - const int resultBytes) // Size of result buffer in bytes -{ - if (!ValidateHumanStringBits(dataBits, checkBits)) - { - return 0; - } - - // If the string is not precisely the right length, - if (humanStr.GetLengthI() != (dataBits + checkBits + 4) / 5) - { - return 0; - } - - // If the result buffer is not large enough, - int dataBytes = (dataBits + 7) / 8; - if (dataBytes > resultBytes) - { - OVR_ASSERT(false); // Programming error - return 0; - } - - // Convert human string to 5-bit symbols - uint8_t data[32]; - const char* cHumanStr = humanStr.ToCStr(); - for (int i = 0; i < humanStr.GetLengthI(); ++i) - { - char word = Base32FromChar[(unsigned char)cHumanStr[i]]; - if (word < 0) - { - // Attempt to replace invalid characters, - // and rely on error correction to fix it. - word = 0; - } - data[i] = word; - } - - // Extract checks from data - int dataCount = (dataBits + 4) / 5; - int checkCount = (checkBits + 4) / 5; - uint8_t checks[32]; - - // Copy full check characters - int fullCheckCount = checkBits / 5; - for (int i = 0; i < fullCheckCount; ++i) - { - checks[i] = data[dataCount + i]; - } - - // If there is a partial check character, - int partialCheckBits = checkBits % 5; - if (partialCheckBits > 0) - { - // Read high bits as the check high partial symbol - uint8_t word = data[dataCount - 1] >> (5 - partialCheckBits); - checks[fullCheckCount] = word; - - // Clear high bits of data that contain check bits - data[dataCount - 1] ^= word << (5 - partialCheckBits); - } - - // Fuzzy accept input - if (!FixHumanChecksum(data, (dataBits + 4) / 5, checks, checkCount, checkBits % 5)) - { - return 0; - } - - // Copy data bits to output buffer - memset(result, 0, resultBytes); - for (int i = 0; i < dataBits; ++i) - { - // Grab data bit - int bit = (data[i / 5] >> (i % 5)) & 1; - - // Write it into result - result[i / 8] |= bit << (i % 8); - } - - return dataBytes; -} - - //// Unit Tests #ifdef SERIAL_FORMAT_UNIT_TEST @@ -780,140 +443,6 @@ void TestSerialFormatStuff() psn2.FromBase32(s.ToCStr()); OVR_ASSERT(psn == psn2); - - unsigned char data[32]; - unsigned char result[32]; - - int trials = 0; - int trial_failures = 0; - - for (int seed = 0; seed < 20; ++seed) - { - srand(seed); - - for (int dataBits = 1; dataBits < 160; ++dataBits) - { - for (int checkBits = 1; checkBits < 160 - dataBits; ++checkBits) - { - String human; - - int fillCheckBits = (checkBits + dataBits) % 5; - if (fillCheckBits > 0) - { - fillCheckBits = 5 - fillCheckBits + checkBits; - } - else - { - fillCheckBits = checkBits; - } - - for (int i = 0; i < sizeof(data); ++i) - { - data[i] = (unsigned char)rand(); - if (seed == 1) - { - data[i] = 0; - } - else if (seed == 0) - { - data[i] = 0xff; - } - } - - if (dataBits % 8 != 0) - { - data[dataBits / 8] &= (1 << (dataBits % 8)) - 1; - } - - if (!GenerateHumanString(dataBits, fillCheckBits, data, sizeof(data), human)) - { - OVR_ASSERT(false); - } - - int bytes = ProcessHumanString(dataBits, fillCheckBits, human, result, sizeof(result)); - - if (bytes <= 0) - { - OVR_ASSERT(false); - } - - OVR_ASSERT(bytes == (dataBits + 7) / 8); - - for (int i = 0; i < bytes; ++i) - { - OVR_ASSERT(data[i] == result[i]); - } - - // Produce maximal failures and verify that we catch them: - - if (fillCheckBits >= 5) - { - char* cstr = (char*)human.ToCStr(); - - for (int i = 0; i < fillCheckBits / 5; ++i) - { - cstr[i] ^= 1; - } - - trials++; - bytes = ProcessHumanString(dataBits, fillCheckBits, cstr, result, sizeof(result)); - - // Undo errors - for (int i = 0; i < fillCheckBits / 5; ++i) - { - cstr[i] ^= 1; - } - - if (bytes > 0) - { - for (int i = 0; i < bytes; ++i) - { - if (data[i] != result[i]) - { - trial_failures++; - break; - } - } - } - - // If enough check bits, - if (fillCheckBits >= 10) - { - // Introduce one error at all positions and verify it is corrected: - char* cstr = (char*)human.ToCStr(); - - for (int j = 0; j < human.GetLengthI(); ++j) - { - if (dataBits % 5 != 0 && j == (dataBits / 5)) - { - // Note: Corrupting a shared character - // effectively breaks two symbols at once and recovery is not possible.. - continue; - } - - cstr[j] ^= 1; - - bytes = ProcessHumanString(dataBits, fillCheckBits, cstr, result, sizeof(result)); - - OVR_ASSERT(bytes > 0); - - for (int i = 0; i < bytes; ++i) - { - OVR_ASSERT(data[i] == result[i]); - } - - cstr[j] ^= 1; - } - } - } - } - } - } - - // Allow some number of false positives in exchange for error correction - OVR_ASSERT(trial_failures <= 0.008 * trials); - - LogText("[SerialFormatUnitTest] Success: False accept rate = %d / %d\n", trial_failures, trials); } #endif // SERIAL_FORMAT_UNIT_TEST |