common/rand/randparkmiller.cpp

	randparkmiller.cpp revision c7814cf6e1240a519cbec0441e033d0e2470ed00
/* $Id$ */
/** @file
 * IPRT - Random Numbers, Park-Miller Pseudo Random.
 */

/*
 * Copyright (C) 2008-2012 Oracle Corporation
 *
 * This file is part of VirtualBox Open Source Edition (OSE), as
 * available from http://www.virtualbox.org. This file is free software;
 * you can redistribute it and/or modify it under the terms of the GNU
 * General Public License (GPL) as published by the Free Software
 * Foundation, in version 2 as it comes in the "COPYING" file of the
 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
 *
 * The contents of this file may alternatively be used under the terms
 * of the Common Development and Distribution License Version 1.0
 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
 * VirtualBox OSE distribution, in which case the provisions of the
 * CDDL are applicable instead of those of the GPL.
 *
 * You may elect to license modified versions of this file under the
 * terms and conditions of either the GPL or the CDDL or both.
 */

/*******************************************************************************
*   Header Files                                                               *
*******************************************************************************/
#include <iprt/rand.h>
#include "internal/iprt.h"

#include <iprt/asm-math.h>
#include <iprt/mem.h>
#include <iprt/string.h>
#include <iprt/err.h>
#include "internal/rand.h"
#include "internal/magics.h"


DECLINLINE(uint32_t) rtRandParkMillerU31(uint32_t *pu32Ctx)
{
    /*
     * Park-Miller random number generator:
     *      X2 = X1 * g mod n.
     *
     * We use the constants suggested by Park and Miller:
     *      n = 2^31 - 1 = INT32_MAX
     *      g = 7^5 = 16807
     *
     * This will produce numbers in the range [0..INT32_MAX-1], which is
     * almost 31-bits. We'll ignore the missing number for now and settle
     * for just filling in the missing bit instead (the caller does this).
     */
    uint32_t x1 = *pu32Ctx;
    if (!x1)
        x1 = 20080806;
    /*uint32_t x2 = ((uint64_t)x1 * 16807) % INT32_MAX;*/
    uint32_t x2 = ASMModU64ByU32RetU32(ASMMult2xU32RetU64(x1, 16807), INT32_MAX);
    return *pu32Ctx = x2;
}


/** @copydoc RTRANDINT::pfnGetU32 */
static DECLCALLBACK(uint32_t) rtRandParkMillerGetU32(PRTRANDINT pThis, uint32_t u32First, uint32_t u32Last)
{
    uint32_t off;
    uint32_t offLast = u32Last - u32First;
    if (offLast == UINT32_MAX)
    {
        /* 30 + 2 bit (make up for the missing INT32_MAX value) */
        off = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx);
        if (pThis->u.ParkMiller.cBits < 2)
        {
            pThis->u.ParkMiller.u32Bits = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx);
            pThis->u.ParkMiller.cBits = 30;
        }
        off >>= 1;
        off |= (pThis->u.ParkMiller.u32Bits & 3) << 30;
        pThis->u.ParkMiller.u32Bits >>= 2;
        pThis->u.ParkMiller.cBits -= 2;
    }
    else if (offLast == (uint32_t)INT32_MAX - 1)
        /* The exact range. */
        off = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx);
    else if (offLast < UINT32_C(0x07ffffff))
    {
        /* Requested 23 or fewer bits, just lose the lower bit. */
        off = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx);
        off >>= 1;
        off %= (offLast + 1);
    }
    else
    {
        /*
         * 30 + 6 bits.
         */
        uint64_t off64 = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx);
        if (pThis->u.ParkMiller.cBits < 6)
        {
            pThis->u.ParkMiller.u32Bits = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx);
            pThis->u.ParkMiller.cBits = 30;
        }
        off64 >>= 1;
        off64 |= (uint64_t)(pThis->u.ParkMiller.u32Bits & 0x3f) << 30;
        pThis->u.ParkMiller.u32Bits >>= 6;
        pThis->u.ParkMiller.cBits -= 6;
        off = ASMModU64ByU32RetU32(off64, offLast + 1);
    }
    return off + u32First;
}


/** @copydoc RTRANDINT::pfnSeed */
static DECLCALLBACK(int) rtRandParkMillerSeed(PRTRANDINT pThis, uint64_t u64Seed)
{
    pThis->u.ParkMiller.u32Ctx = (uint32_t)u64Seed;
    pThis->u.ParkMiller.u32Bits = 0;
    pThis->u.ParkMiller.cBits = 0;
    return VINF_SUCCESS;
}


/** @copydoc RTRANDINT::pfnSaveState */
static DECLCALLBACK(int) rtRandParkMillerSaveState(PRTRANDINT pThis, char *pszState, size_t *pcbState)
{
#define RTRAND_PARKMILLER_STATE_SIZE (3+8+1+8+1+2+1+1)

    if (*pcbState < RTRAND_PARKMILLER_STATE_SIZE)
    {
        *pcbState = RTRAND_PARKMILLER_STATE_SIZE;
        return VERR_BUFFER_OVERFLOW;
    }
    RTStrPrintf(pszState, *pcbState, "PM:%08RX32,%08RX32,%02x;",
                pThis->u.ParkMiller.u32Ctx,
                pThis->u.ParkMiller.u32Bits,
                pThis->u.ParkMiller.cBits);
    return VINF_SUCCESS;
}


/** @copydoc RTRANDINT::pfnRestoreState */
static DECLCALLBACK(int) rtRandParkMillerRestoreState(PRTRANDINT pThis, char const *pszState)
{
    /* marker */
    if (    pszState[0] != 'P'
        ||  pszState[1] != 'M'
        ||  pszState[2] != ':')
        return VERR_PARSE_ERROR;
    pszState += 3;

    /* u32Ctx */
    char *pszNext = NULL;
    uint32_t u32Ctx;
    int rc = RTStrToUInt32Ex(pszState, &pszNext, 16, &u32Ctx);
    if (    rc != VWRN_TRAILING_CHARS
        ||  pszNext !=  pszState + 8
        ||  *pszNext != ',')
        return VERR_PARSE_ERROR;
    pszState += 8 + 1;

    /* u32Bits */
    uint32_t u32Bits;
    rc = RTStrToUInt32Ex(pszState, &pszNext, 16, &u32Bits);
    if (    rc != VWRN_TRAILING_CHARS
        ||  pszNext !=  pszState + 8
        ||  *pszNext != ',')
        return VERR_PARSE_ERROR;
    pszState += 8 + 1;

    /* cBits */
    uint32_t cBits;
    rc = RTStrToUInt32Ex(pszState, &pszNext, 16, &cBits);
    if (    rc != VWRN_TRAILING_CHARS
        ||  pszNext !=  pszState + 2
        ||  *pszNext != ';'
        ||  pszNext[1] != '\0')
        return VERR_PARSE_ERROR;

    /* commit */
    pThis->u.ParkMiller.u32Ctx  = u32Ctx;
    pThis->u.ParkMiller.u32Bits = u32Bits;
    pThis->u.ParkMiller.cBits   = cBits;
    return VINF_SUCCESS;
}


RTDECL(int) RTRandAdvCreateParkMiller(PRTRAND phRand) RT_NO_THROW
{
    PRTRANDINT pThis = (PRTRANDINT)RTMemAlloc(sizeof(*pThis));
    if (!pThis)
        return VERR_NO_MEMORY;
    pThis->u32Magic = RTRANDINT_MAGIC;
    pThis->pfnGetBytes= rtRandAdvSynthesizeBytesFromU32;
    pThis->pfnGetU32  = rtRandParkMillerGetU32;
    pThis->pfnGetU64  = rtRandAdvSynthesizeU64FromU32;
    pThis->pfnSeed    = rtRandParkMillerSeed;
    pThis->pfnSaveState = rtRandParkMillerSaveState;
    pThis->pfnRestoreState = rtRandParkMillerRestoreState;
    pThis->pfnDestroy = rtRandAdvDefaultDestroy;
    pThis->u.ParkMiller.u32Ctx = 0x20080806;
    pThis->u.ParkMiller.u32Bits = 0;
    pThis->u.ParkMiller.cBits = 0;
    *phRand = pThis;
    return VINF_SUCCESS;
}
RT_EXPORT_SYMBOL(RTRandAdvCreateParkMiller);