random.c

eaayarm101自制小车源代码 周立功公司原创

//*****************************************************************************
//
// random.c - Random number generator utilizing MD4 hash function of
//            environmental noise captured via the the sensors.
//
// Copyright (c) 2005-2007 Luminary Micro, Inc.  All rights reserved.
//
// Software License Agreement
//
// Luminary Micro, Inc. (LMI) is supplying this software for use solely and
// exclusively on LMI's microcontroller products.
//
// The software is owned by LMI and/or its suppliers, and is protected under
// applicable copyright laws.  All rights are reserved.  Any use in violation
// of the foregoing restrictions may subject the user to criminal sanctions
// under applicable laws, as well as to civil liability for the breach of the
// terms and conditions of this license.
//
// THIS SOFTWARE IS PROVIDED "AS IS".  NO WARRANTIES, WHETHER EXPRESS, IMPLIED
// OR STATUTORY, INCLUDING, BUT NOT LIMITED TO, IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE APPLY TO THIS SOFTWARE.
// LMI SHALL NOT, IN ANY CIRCUMSTANCES, BE LIABLE FOR SPECIAL, INCIDENTAL, OR
// CONSEQUENTIAL DAMAGES, FOR ANY REASON WHATSOEVER.
//
// This is part of revision 199 of an01245.
//
//*****************************************************************************

#include "compiler.h"
#include "random.h"

//*****************************************************************************
//
//! \page random_intro Introduction
//!
//! In order to enable random behavior of the car, a reliably random set of
//! numbers needs to be generated.  Using something simple like a linear
//! congruential generator (i.e. x(i) = a * x(i - 1) + b) provides a set of
//! random numbers that are very repeatable (given starting with the same seed
//! each time, which is the only thing possible in a closed system without a
//! time of day reference).
//!
//! With a good source of environmental noise (which is available through the
//! sensors), an especially effective random number generation scheme is to
//! compute the hash of an entropy pool containing the environmental noise.
//! This is the random number generator utilized by the car.
//!
//! For environmental noise, the sensor readings are used.  These readings
//! contain both true environmental noise (i.e. the varying distance to
//! objects, which will never be precisely the same from run to run) and system
//! injected noise (i.e. slight inaccuracies with the sensor itself,
//! inaccuracies introduced by the non-perfect ADC, etc.).  This environmental
//! noise is collected into an entropy pool that is constantly updated as new
//! sensor readings are captured.
//!
//! When a random number is required, the MD4 hash function is computed for the
//! entropy pool contents.  MD4 was chosen for two reasons: it is relatively
//! fast to compute (compared to other hash functions) and its application to
//! generate random numbers is not compromised by the fact that the security
//! properties of the MD4 hash were cracked over ten years ago.
//!
//! Since the random number returned is simply the first 32 bits of the MD4
//! hash of the entropy pool, the same "random" number will be returned again
//! if the entropy pool has not changed.  When a large number of random numbers
//! (indeed, more than one) is needed in a short period of time, the random
//! number computed from the entropy pool should be used as the seed for a
//! linear congruential generator.  This staged approach to random numbers
//! allows good random number to be generated without requiring a onerous
//! update rate on the entropy pool.
//!
//! The random number generator is contained in <tt>random.c</tt>, with
//! <tt>random.h</tt> containing the API definitions for use by the remainder
//! of the application.
//
//*****************************************************************************

//*****************************************************************************
//
//! \defgroup random_api Definitions
//! @{
//
//*****************************************************************************

//*****************************************************************************
//
//! This array contains the entropy pool data that has been collected during
//! the execution of the application.
//
//*****************************************************************************
static ZERO_INIT unsigned long g_pulEntropy[16];

//*****************************************************************************
//
//! The index into the entropy pool where the next byte of entropy data should
//! be added.  In other words, this points to the oldest byte of entropy data
//! in the pool.
//
//*****************************************************************************
static ZERO_INIT unsigned long g_ulIndex;

//*****************************************************************************
//
//! Adds a byte of entropy to the entropy pool.
//!
//! \param ulEntropy is the entropy data to be added.  Only the lower eight
//! bits are utilized.
//!
//! This function adds a new bytes of environmental data to the entropy pool,
//! overwriting the oldest piece of environmental data in the entropy pool.
//!
//! \return None.
//
//*****************************************************************************
void
RandomAddEntropy(unsigned long ulEntropy)
{
    //
    // Add this byte to the entropy pool.
    //
    ((unsigned char *)g_pulEntropy)[g_ulIndex] = ulEntropy & 0xff;

    //
    // Increment to the next byte of the entropy pool.
    //
    g_ulIndex = (g_ulIndex + 1) & 63;
}

//*****************************************************************************
//
//! Generates a random number.
//!
//! This fucntion generates a random number by running a MD4 hash on the
//! entropy pool.  The quality of the random numbers is dependent upon the
//! quality of the environmental data provided to the entropy pool.  Sampling
//! environmental data that is noisy in nature and/or outside the control of
//! the application provides the best random numbers.
//!
//! The random numbers generated by this function will be identical if the
//! entropy pool has not changed between calls.  If it can not be guaranteed
//! that the entropy pool will change between calls, or if more than one random
//! number is needed at a particular point in time, the random number returned
//! by this function should be used as the seed for a linear congruential
//! random number generator.
//!
//! \note The entropy pool may change at any time, but for the purposes of
//! generating random numbers this is not a concern.  Also, the MD4 hash was
//! broken long ago, but since it is being used to generate random numbers
//! instead of providing security this is not a concern (and its a lot faster
//! than the MD5 hash, though that was also recently broken).
//!
//! \return A random number.
//
//*****************************************************************************
unsigned long
RandomNumber(void)
{
    unsigned long ulA, ulB, ulC, ulD, ulTemp, ulIdx;

    //
    // Initialize the digest.
    //
    ulA = 0x67452301;
    ulB = 0xefcdab89;
    ulC = 0x98badcfe;
    ulD = 0x10325476;

    //
    // Perform the first round of operations.
    //
#define F(a, b, c, d, k, s)                                 \
    {                                                       \
        ulTemp = a + (d ^ (b & (c ^ d))) + g_pulEntropy[k]; \
        a = (ulTemp << s) | (ulTemp >> (32 - s));           \
    }
    for(ulIdx = 0; ulIdx < 16; ulIdx += 4)
    {
        F(ulA, ulB, ulC, ulD, ulIdx + 0, 3);
        F(ulD, ulA, ulB, ulC, ulIdx + 1, 7);
        F(ulC, ulD, ulA, ulB, ulIdx + 2, 11);
        F(ulB, ulC, ulD, ulA, ulIdx + 3, 19);
    }

    //
    // Perform the second round of operations.
    //
#define G(a, b, c, d, k, s)                                            \
    {                                                                  \
        ulTemp = a + ((b & c) | (b & d) | (c & d)) + g_pulEntropy[k] + \
                 0x5a827999;                                           \
        a = (ulTemp << s) | (ulTemp >> (32 - s));                      \
    }
    for(ulIdx = 0; ulIdx < 4; ulIdx++)
    {
        G(ulA, ulB, ulC, ulD, ulIdx + 0, 3);
        G(ulD, ulA, ulB, ulC, ulIdx + 4, 5);
        G(ulC, ulD, ulA, ulB, ulIdx + 8, 9);
        G(ulB, ulC, ulD, ulA, ulIdx + 12, 13);
    }

    //
    // Perform the third round of operations.
    //
#define H(a, b, c, d, k, s)                                      \
    {                                                            \
        ulTemp = a + (b ^ c ^ d) + g_pulEntropy[k] + 0x6ed9eba1; \
        a = (ulTemp << s) | (ulTemp >> (32 - s));                \
    }
    for(ulIdx = 0; ulIdx < 4; ulIdx += 2)
    {
        H(ulA, ulB, ulC, ulD, ulIdx + 0, 3);
        H(ulD, ulA, ulB, ulC, ulIdx + 8, 9);
        H(ulC, ulD, ulA, ulB, ulIdx + 4, 11);
        H(ulB, ulC, ulD, ulA, ulIdx + 12, 15);

        if(ulIdx == 2)
        {
            ulIdx -= 3;
        }
    }

    //
    // Return the first word of the resulting digest as the random number.
    //
    return(ulA + 0x67452301);
}

//*****************************************************************************
//
// Close the Doxygen group.
//! @}
//
//*****************************************************************************