sal/rtl/source/random.c

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: random.c,v $
  10  * $Revision: 1.6 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 #define _RTL_RANDOM_C_ "$Revision: 1.6 $"
  32
  33 #include <sal/types.h>
  34 #include <osl/thread.h>
  35 #include <osl/time.h>
  36 #include <rtl/alloc.h>
  37 #include <rtl/digest.h>
  38 #include <rtl/random.h>
  39 #include <osl/time.h>
  40
  41 /*========================================================================
  42  *
  43  * rtlRandom internals.
  44  *
  45  *======================================================================*/
  46 #define RTL_RANDOM_RNG_1(a) ((a) * 16807L)
  47 #define RTL_RANDOM_RNG_2(a) ((a) * 65539L)
  48
  49 #define RTL_RANDOM_RNG(x, y, z) \
  50 { \
  51     (x) = 170 * ((x) % 178) - 63 * ((x) / 178); \
  52     if ((x) < 0) (x) += 30328L; \
  53     \
  54     (y) = 171 * ((y) % 177) -  2 * ((y) / 177); \
  55     if ((y) < 0) (y) += 30269L; \
  56     \
  57     (z) = 172 * ((z) % 176) - 35 * ((z) / 176); \
  58     if ((z) < 0) (z) += 30307L; \
  59 }
  60
  61 /** RandomData_Impl.
  62  */
  63 typedef struct random_data_impl_st
  64 {
  65     sal_Int16 m_nX;
  66     sal_Int16 m_nY;
  67     sal_Int16 m_nZ;
  68 } RandomData_Impl;
  69
  70 /** __rtl_random_data.
  71  */
  72 static double __rtl_random_data (RandomData_Impl *pImpl);
  73
  74 /** RandomPool_Impl.
  75  */
  76 #define RTL_RANDOM_DIGEST      rtl_Digest_AlgorithmMD5
  77 #define RTL_RANDOM_SIZE_DIGEST RTL_DIGEST_LENGTH_MD5
  78 #define RTL_RANDOM_SIZE_POOL   1023
  79
  80 typedef struct random_pool_impl_st
  81 {
  82     rtlDigest  m_hDigest;
  83     sal_uInt8  m_pDigest[RTL_RANDOM_SIZE_DIGEST];
  84     sal_uInt8  m_pData[RTL_RANDOM_SIZE_POOL + 1];
  85     sal_uInt32 m_nData;
  86     sal_uInt32 m_nIndex;
  87     sal_uInt32 m_nCount;
  88 } RandomPool_Impl;
  89
  90 /** __rtl_random_initPool.
  91  */
  92 static sal_Bool __rtl_random_initPool (
  93     RandomPool_Impl *pImpl);
  94
  95 /** __rtl_random_seedPool.
  96  */
  97 static void __rtl_random_seedPool (
  98     RandomPool_Impl *pImpl, const sal_uInt8 *pBuffer, sal_Size nBufLen);
  99
 100 /** __rtl_random_readPool.
 101  */
 102 static void __rtl_random_readPool (
 103     RandomPool_Impl *pImpl, sal_uInt8 *pBuffer, sal_Size nBufLen);
 104
 105 /*
 106  * __rtl_random_data.
 107  */
 108 static double __rtl_random_data (RandomData_Impl *pImpl)
 109 {
 110     register double random;
 111
 112     RTL_RANDOM_RNG (pImpl->m_nX, pImpl->m_nY, pImpl->m_nZ);
 113     random = (((double)(pImpl->m_nX) / 30328.0) +
 114               ((double)(pImpl->m_nY) / 30269.0) +
 115               ((double)(pImpl->m_nZ) / 30307.0)   );
 116
 117     random -= ((double)((sal_uInt32)(random)));
 118     return (random);
 119 }
 120
 121 /*
 122  * __rtl_random_initPool.
 123  */
 124 static sal_Bool __rtl_random_initPool (RandomPool_Impl *pImpl)
 125 {
 126     pImpl->m_hDigest = rtl_digest_create (RTL_RANDOM_DIGEST);
 127     if (pImpl->m_hDigest)
 128     {
 129         oslThreadIdentifier id;
 130         TimeValue           tv;
 131         RandomData_Impl     rd;
 132         double              seed;
 133
 134         /* The use of uninitialized stack variables as a way to
 135          * enhance the entropy of the random pool triggers
 136          * memory checkers like purify and valgrind.
 137          */
 138
 139         /*
 140         __rtl_random_seedPool (pImpl, (sal_uInt8*)&id, sizeof(id));
 141         __rtl_random_seedPool (pImpl, (sal_uInt8*)&tv, sizeof(tv));
 142         __rtl_random_seedPool (pImpl, (sal_uInt8*)&rd, sizeof(rd));
 143         */
 144
 145         id = osl_getThreadIdentifier (NULL);
 146         id = RTL_RANDOM_RNG_2(RTL_RANDOM_RNG_1(id));
 147         __rtl_random_seedPool (pImpl, (sal_uInt8*)&id, sizeof(id));
 148
 149         osl_getSystemTime (&tv);
 150         tv.Seconds = RTL_RANDOM_RNG_2(tv.Seconds);
 151         tv.Nanosec = RTL_RANDOM_RNG_2(tv.Nanosec);
 152         __rtl_random_seedPool (pImpl, (sal_uInt8*)&tv, sizeof(tv));
 153
 154         rd.m_nX = (sal_Int16)(((id         >> 1) << 1) + 1);
 155         rd.m_nY = (sal_Int16)(((tv.Seconds >> 1) << 1) + 1);
 156         rd.m_nZ = (sal_Int16)(((tv.Nanosec >> 1) << 1) + 1);
 157         __rtl_random_seedPool (pImpl, (sal_uInt8*)&rd, sizeof(rd));
 158
 159         while (pImpl->m_nData < RTL_RANDOM_SIZE_POOL)
 160         {
 161             seed = __rtl_random_data (&rd);
 162             __rtl_random_seedPool (pImpl, (sal_uInt8*)&seed, sizeof(seed));
 163         }
 164         return sal_True;
 165     }
 166     return sal_False;
 167 }
 168
 169 /*
 170  * __rtl_random_seedPool.
 171  */
 172 static void __rtl_random_seedPool (
 173     RandomPool_Impl *pImpl, const sal_uInt8 *pBuffer, sal_Size nBufLen)
 174 {
 175     sal_Size i;
 176     sal_sSize  j, k;
 177
 178     for (i = 0; i < nBufLen; i += RTL_RANDOM_SIZE_DIGEST)
 179     {
 180         j = nBufLen - i;
 181         if (j > RTL_RANDOM_SIZE_DIGEST)
 182             j = RTL_RANDOM_SIZE_DIGEST;
 183
 184         rtl_digest_update (
 185             pImpl->m_hDigest, pImpl->m_pDigest, RTL_RANDOM_SIZE_DIGEST);
 186
 187         k = (pImpl->m_nIndex + j) - RTL_RANDOM_SIZE_POOL;
 188         if (k > 0)
 189         {
 190             rtl_digest_update (
 191                 pImpl->m_hDigest, &(pImpl->m_pData[pImpl->m_nIndex]), j - k);
 192             rtl_digest_update (
 193                 pImpl->m_hDigest, &(pImpl->m_pData[0]), k);
 194         }
 195         else
 196         {
 197             rtl_digest_update (
 198                 pImpl->m_hDigest, &(pImpl->m_pData[pImpl->m_nIndex]), j);
 199         }
 200
 201         rtl_digest_update (pImpl->m_hDigest, pBuffer, j);
 202         pBuffer += j;
 203
 204         rtl_digest_get (
 205             pImpl->m_hDigest, pImpl->m_pDigest, RTL_RANDOM_SIZE_DIGEST);
 206         for (k = 0; k < j; k++)
 207         {
 208             pImpl->m_pData[pImpl->m_nIndex++] ^= pImpl->m_pDigest[k];
 209             if (pImpl->m_nIndex >= RTL_RANDOM_SIZE_POOL)
 210             {
 211                 pImpl->m_nData  = RTL_RANDOM_SIZE_POOL;
 212                 pImpl->m_nIndex = 0;
 213             }
 214         }
 215     }
 216
 217     if (pImpl->m_nIndex > pImpl->m_nData)
 218         pImpl->m_nData = pImpl->m_nIndex;
 219 }
 220
 221 /*
 222  * __rtl_random_readPool.
 223  */
 224 static void __rtl_random_readPool (
 225     RandomPool_Impl *pImpl, sal_uInt8 *pBuffer, sal_Size nBufLen)
 226 {
 227     sal_Int32 j, k;
 228
 229     while (nBufLen > 0)
 230     {
 231         j = nBufLen;
 232         if (j > RTL_RANDOM_SIZE_DIGEST/2)
 233             j = RTL_RANDOM_SIZE_DIGEST/2;
 234         nBufLen -= j;
 235
 236         rtl_digest_update (
 237             pImpl->m_hDigest,
 238             &(pImpl->m_pDigest[RTL_RANDOM_SIZE_DIGEST/2]),
 239             RTL_RANDOM_SIZE_DIGEST/2);
 240
 241         k = (pImpl->m_nIndex + j) - pImpl->m_nData;
 242         if (k > 0)
 243         {
 244             rtl_digest_update (
 245                 pImpl->m_hDigest, &(pImpl->m_pData[pImpl->m_nIndex]), j - k);
 246             rtl_digest_update (
 247                 pImpl->m_hDigest, &(pImpl->m_pData[0]), k);
 248         }
 249         else
 250         {
 251             rtl_digest_update (
 252                 pImpl->m_hDigest, &(pImpl->m_pData[pImpl->m_nIndex]), j);
 253         }
 254
 255         rtl_digest_get (
 256             pImpl->m_hDigest, pImpl->m_pDigest, RTL_RANDOM_SIZE_DIGEST);
 257         for (k = 0; k < j; k++)
 258         {
 259             if (pImpl->m_nIndex >= pImpl->m_nData) pImpl->m_nIndex = 0;
 260             pImpl->m_pData[pImpl->m_nIndex++] ^= pImpl->m_pDigest[k];
 261             *pBuffer++ = pImpl->m_pDigest[k + RTL_RANDOM_SIZE_DIGEST/2];
 262         }
 263     }
 264
 265     pImpl->m_nCount++;
 266     rtl_digest_update (
 267         pImpl->m_hDigest, &(pImpl->m_nCount), sizeof(pImpl->m_nCount));
 268     rtl_digest_update (
 269         pImpl->m_hDigest, pImpl->m_pDigest, RTL_RANDOM_SIZE_DIGEST);
 270     rtl_digest_get (
 271         pImpl->m_hDigest, pImpl->m_pDigest, RTL_RANDOM_SIZE_DIGEST);
 272 }
 273
 274 /*========================================================================
 275  *
 276  * rtlRandom implementation.
 277  *
 278  *======================================================================*/
 279 /*
 280  * rtl_random_createPool.
 281  */
 282 rtlRandomPool SAL_CALL rtl_random_createPool (void)
 283 {
 284     RandomPool_Impl *pImpl = (RandomPool_Impl*)NULL;
 285     pImpl = (RandomPool_Impl*)rtl_allocateZeroMemory (sizeof(RandomPool_Impl));
 286     if (pImpl)
 287     {
 288         if (!__rtl_random_initPool (pImpl))
 289         {
 290             rtl_freeZeroMemory (pImpl, sizeof(RandomPool_Impl));
 291             pImpl = (RandomPool_Impl*)NULL;
 292         }
 293     }
 294     return ((rtlRandomPool)pImpl);
 295 }
 296
 297 /*
 298  * rtl_random_destroyPool.
 299  */
 300 void SAL_CALL rtl_random_destroyPool (rtlRandomPool Pool)
 301 {
 302     RandomPool_Impl *pImpl = (RandomPool_Impl *)Pool;
 303     if (pImpl)
 304     {
 305         rtl_digest_destroy (pImpl->m_hDigest);
 306         rtl_freeZeroMemory (pImpl, sizeof (RandomPool_Impl));
 307     }
 308 }
 309
 310 /*
 311  * rtl_random_addBytes.
 312  */
 313 rtlRandomError SAL_CALL rtl_random_addBytes (
 314     rtlRandomPool Pool, const void *Buffer, sal_Size Bytes)
 315 {
 316     RandomPool_Impl *pImpl   = (RandomPool_Impl *)Pool;
 317     const sal_uInt8 *pBuffer = (const sal_uInt8 *)Buffer;
 318
 319     if ((pImpl == NULL) || (pBuffer == NULL))
 320         return rtl_Random_E_Argument;
 321
 322     __rtl_random_seedPool (pImpl, pBuffer, Bytes);
 323     return rtl_Random_E_None;
 324 }
 325
 326 /*
 327  * rtl_random_getBytes.
 328  */
 329 rtlRandomError SAL_CALL rtl_random_getBytes (
 330     rtlRandomPool Pool, void *Buffer, sal_Size Bytes)
 331 {
 332     RandomPool_Impl *pImpl   = (RandomPool_Impl *)Pool;
 333     sal_uInt8       *pBuffer = (sal_uInt8 *)Buffer;
 334
 335     if ((pImpl == NULL) || (pBuffer == NULL))
 336         return rtl_Random_E_Argument;
 337
 338     __rtl_random_readPool (pImpl, pBuffer, Bytes);
 339     return rtl_Random_E_None;
 340 }
 341