← Back to branch summary

~lfaraone/ubuntu/maverick/imagemagick/graphviz-rebuild

« back to all changes in this revision

Viewing changes to magick/random.c

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2008-11-21 08:26:29 UTC
  • mfrom: (1.1.4 upstream)
  • Revision ID: james.westby@ubuntu.com-20081121082629-iy01ycd87bs5fn2g
Tags: 7:6.4.5.4.dfsg1-1ubuntu1
* Merge with Debian; remaining changes:
  - (Build-)depend on libltdl7-dev instead of libltdl3-dev (the armel buildds
    currently have both available).

Show diffs side-by-side

added added

removed removed

Lines of Context:
magick/random.c
9
9
%                 R  R   A   A  N   N  DDDD    OOO   M   M                    %
10
10
%                                                                             %
11
11
%                                                                             %
12
 
%                   Methods to Generate Random Numbers                        %
 
12
%               MagickCore Methods to Generate Random Numbers                 %
13
13
%                                                                             %
14
14
%                             Software Design                                 %
15
15
%                               John Cristy                                   %
54
54
#include "magick/semaphore.h"
55
55
#include "magick/random_.h"
56
56
#include "magick/resource_.h"
57
 
#include "magick/signature.h"
 
57
#include "magick/signature-private.h"
58
58
#include "magick/string_.h"
59
59
#include "magick/utility.h"
 
60
/*
 
61
  Define declarations.
 
62
*/
 
63
#define PseudoRandomHash  SHA256Hash
 
64
#define RandomEntropyLevel  9
 
65
#define RandomFilename  "reservoir.xdm"
 
66
#define RandomFiletype  "random"
 
67
#define RandomProtocolMajorVersion  1
 
68
#define RandomProtocolMinorVersion  0
60
69
 
61
70
/*
62
71
  Typedef declarations.
63
72
*/
64
 
typedef struct _RandomInfo
 
73
struct _RandomInfo
65
74
{
66
 
  unsigned int
67
 
    w,
68
 
    x,
69
 
    y,
70
 
    z;
71
 
} RandomInfo;
 
75
  SignatureInfo
 
76
    *signature_info;
 
77
 
 
78
  StringInfo
 
79
    *nonce,
 
80
    *reservoir;
 
81
 
 
82
  size_t
 
83
    i;
 
84
 
 
85
  unsigned short
 
86
    protocol_major,
 
87
    protocol_minor;
 
88
 
 
89
  SemaphoreInfo
 
90
    *semaphore;
 
91
 
 
92
  long
 
93
    timestamp;
 
94
 
 
95
  unsigned long
 
96
    signature;
 
97
};
 
98
 
 
99
/*
 
100
  External declarations.
 
101
*/
 
102
#if defined(__APPLE__)
 
103
#include <crt_externs.h>
 
104
#define environ (*_NSGetEnviron())
 
105
#endif
 
106
 
 
107
extern char
 
108
  **environ;
72
109
 
73
110
/*
74
111
  Global declarations.
75
112
*/
76
 
static RandomInfo
77
 
  random_info = { ~0U, ~0U, ~0U, ~0U };
78
 
 
79
113
static SemaphoreInfo
80
114
  *random_semaphore = (SemaphoreInfo *) NULL;
81
115
 
82
 
static SignatureInfo
83
 
  *reservoir = (SignatureInfo *) NULL;
84
 
 
85
116
static unsigned long
86
 
  *roulette = (unsigned long *) NULL;
 
117
  random_seed[4] = { ~0UL, 0x50a7f451UL, 0x5365417eUL, 0xc3a4171aUL };
 
118
 
 
119
static MagickBooleanType
 
120
  gather_true_random = MagickFalse;
87
121
 
88
122
/*
89
123
  Forward declarations.
90
124
*/
91
 
static void
92
 
  InitializeRandomReservoir(void);
 
125
static StringInfo
 
126
  *GenerateEntropicChaos(RandomInfo *);
 
127
 
 
128
/*
 
129
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
130
%                                                                             %
 
131
%                                                                             %
 
132
%                                                                             %
 
133
%   A c q u i r e R a n d o m I n f o                                         %
 
134
%                                                                             %
 
135
%                                                                             %
 
136
%                                                                             %
 
137
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
138
%
 
139
%  AcquireRandomInfo() allocates the RandomInfo structure.
 
140
%
 
141
%  The format of the AcquireRandomInfo method is:
 
142
%
 
143
%      RandomInfo *AcquireRandomInfo(void)
 
144
%
 
145
*/
 
146
MagickExport RandomInfo *AcquireRandomInfo(void)
 
147
{
 
148
  RandomInfo
 
149
    *random_info;
 
150
 
 
151
  StringInfo
 
152
    *entropy;
 
153
 
 
154
  random_info=(RandomInfo *) AcquireMagickMemory(sizeof(*random_info));
 
155
  if (random_info == (RandomInfo *) NULL)
 
156
    ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
 
157
  (void) ResetMagickMemory(random_info,0,sizeof(*random_info));
 
158
  random_info->signature_info=AcquireSignatureInfo();
 
159
  random_info->nonce=AcquireStringInfo(GetSignatureDigestsize(
 
160
    random_info->signature_info));
 
161
  ResetStringInfo(random_info->nonce);
 
162
  random_info->reservoir=AcquireStringInfo(GetSignatureDigestsize(
 
163
    random_info->signature_info));
 
164
  ResetStringInfo(random_info->reservoir);
 
165
  random_info->semaphore=AllocateSemaphoreInfo();
 
166
  random_info->protocol_major=RandomProtocolMajorVersion;
 
167
  random_info->protocol_minor=RandomProtocolMinorVersion;
 
168
  random_info->timestamp=(long) time(0);
 
169
  random_info->signature=MagickSignature;
 
170
  /*
 
171
    Seed random reservoir with entropic data.
 
172
  */
 
173
  entropy=GenerateEntropicChaos(random_info);
 
174
  if (entropy == (StringInfo *) NULL)
 
175
    ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
 
176
  if (GetStringInfoLength(entropy) > GetStringInfoLength(random_info->nonce))
 
177
    {
 
178
      StringInfo
 
179
        *nonce;
 
180
 
 
181
      nonce=SplitStringInfo(entropy,GetStringInfoLength(random_info->nonce)/2);
 
182
      if (nonce != (StringInfo *) NULL)
 
183
        {
 
184
          /*
 
185
            Use some of the entropy to set a random nonce.
 
186
          */
 
187
          SetStringInfo(random_info->nonce,nonce);
 
188
          nonce=DestroyStringInfo(nonce);
 
189
        }
 
190
    }
 
191
  UpdateSignature(random_info->signature_info,entropy);
 
192
  FinalizeSignature(random_info->signature_info);
 
193
  SetStringInfo(random_info->reservoir,GetSignatureDigest(
 
194
    random_info->signature_info));
 
195
  entropy=DestroyStringInfo(entropy);
 
196
  return(random_info);
 
197
}
 
198
 
 
199
/*
 
200
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
201
%                                                                             %
 
202
%                                                                             %
 
203
%                                                                             %
 
204
+   D e s t r o y R a n d o m I n f o                                         %
 
205
%                                                                             %
 
206
%                                                                             %
 
207
%                                                                             %
 
208
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
209
%
 
210
%  DestroyRandomInfo() deallocates memory associated with the random
 
211
%  reservoir.
 
212
%
 
213
%  The format of the DestroyRandomInfo method is:
 
214
%
 
215
%      RandomInfo *DestroyRandomInfo(RandomInfo *random_info)
 
216
%
 
217
%  A description of each parameter follows:
 
218
%
 
219
%    o random_info: the random info.
 
220
%
 
221
*/
 
222
MagickExport RandomInfo *DestroyRandomInfo(RandomInfo *random_info)
 
223
{
 
224
  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
 
225
  assert(random_info != (RandomInfo *) NULL);
 
226
  assert(random_info->signature == MagickSignature);
 
227
  (void) LockSemaphoreInfo(random_info->semaphore);
 
228
  if (random_info->reservoir != (StringInfo *) NULL)
 
229
    random_info->reservoir=DestroyStringInfo(random_info->reservoir);
 
230
  if (random_info->nonce != (StringInfo *) NULL)
 
231
    random_info->nonce=DestroyStringInfo(random_info->nonce);
 
232
  if (random_info->signature_info != (SignatureInfo *) NULL)
 
233
    random_info->signature_info=DestroySignatureInfo(
 
234
      random_info->signature_info);
 
235
  random_info->signature=(~MagickSignature);
 
236
  (void) UnlockSemaphoreInfo(random_info->semaphore);
 
237
  DestroySemaphoreInfo(&random_info->semaphore);
 
238
  random_info=(RandomInfo *) RelinquishMagickMemory(random_info);
 
239
  return(random_info);
 
240
}
93
241
 
94
242
/*
95
243
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
113
261
MagickExport void DestroyRandomReservoir(void)
114
262
{
115
263
  AcquireSemaphoreInfo(&random_semaphore);
116
 
  if (reservoir != (SignatureInfo *) NULL)
117
 
    {
118
 
      (void) ResetMagickMemory(reservoir,0,sizeof(*reservoir));
119
 
      reservoir=(SignatureInfo *) RelinquishMagickMemory(reservoir);
120
 
    }
121
 
  if (roulette != (unsigned long *) NULL)
122
 
    {
123
 
      (void) ResetMagickMemory(roulette,0,sizeof(*roulette));
124
 
      roulette=(unsigned long *) RelinquishMagickMemory(roulette);
125
 
    }
126
 
  (void) ResetMagickMemory(&random_info,0xff,sizeof(random_info));
127
 
  RelinquishSemaphoreInfo(random_semaphore);
128
 
  random_semaphore=DestroySemaphoreInfo(random_semaphore);
129
 
}
130
 
 
131
 
/*
132
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
133
 
%                                                                             %
134
 
%                                                                             %
135
 
%                                                                             %
136
 
%   D i s t i l l R a n d o m E v e n t                                       %
137
 
%                                                                             %
138
 
%                                                                             %
139
 
%                                                                             %
140
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
141
 
%
142
 
%  DistillRandomEvent() distills randomness from an event and stores it int
143
 
%  the reservoir.  This method should be called before GetRandomKey() and it
144
 
%  should be called a number of times using different random events (e.g.
145
 
%  thread completion time, fine grained time-of-day clock in a tight loop,
146
 
%  keystroke timing, etc.) to build up sufficient randomness in the reservoir.
147
 
%
148
 
%  The format of the DistillRandomEvent method is:
149
 
%
150
 
%      DistillRandomEvent(const unsigned char *event,const size_t length)
151
 
%
152
 
%  A description of each parameter follows:
153
 
%
154
 
%    o event: A random event.
155
 
%
156
 
%    o length: The length of the event.
157
 
%
158
 
*/
159
 
MagickExport void DistillRandomEvent(const unsigned char *event,
160
 
  const size_t length)
161
 
{
162
 
  SignatureInfo
163
 
    digest_info;
164
 
 
165
 
  /*
166
 
    Distill a random event.
167
 
  */
168
 
  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
169
 
  assert(event != (const unsigned char *) NULL);
170
 
  if ((reservoir == (SignatureInfo *) NULL) ||
171
 
      (roulette == (unsigned long *) NULL))
172
 
    {
173
 
      AcquireSemaphoreInfo(&random_semaphore);
174
 
      if (reservoir == (SignatureInfo *) NULL)
175
 
        reservoir=(SignatureInfo *) AcquireMagickMemory(sizeof(*reservoir));
176
 
      if (roulette == (unsigned long *) NULL)
177
 
        roulette=(unsigned long *) AcquireMagickMemory(sizeof(*roulette));
178
 
      RelinquishSemaphoreInfo(random_semaphore);
179
 
      if ((reservoir == (SignatureInfo *) NULL) ||
180
 
          (roulette == (unsigned long *) NULL))
181
 
        ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
182
 
      (void) ResetMagickMemory(reservoir,0,sizeof(*reservoir));
183
 
      (void) ResetMagickMemory(roulette,0,sizeof(*roulette));
184
 
      (void) ResetMagickMemory(&random_info,0xff,sizeof(random_info));
185
 
    }
186
 
  AcquireSemaphoreInfo(&random_semaphore);
187
 
  GetSignatureInfo(&digest_info);
188
 
  UpdateSignature(&digest_info,(const unsigned char *) reservoir->digest,
189
 
    sizeof(reservoir->digest));
190
 
  UpdateSignature(&digest_info,event,length);
191
 
  FinalizeSignature(&digest_info);
192
 
  (void) CopyMagickMemory(reservoir->digest,digest_info.digest,
193
 
    sizeof(reservoir->digest));
194
 
  RelinquishSemaphoreInfo(random_semaphore);
195
 
}
196
 
 
197
 
/*
198
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
199
 
%                                                                             %
200
 
%                                                                             %
201
 
%                                                                             %
202
 
%   G e t R a n d o m K e y                                                   %
203
 
%                                                                             %
204
 
%                                                                             %
205
 
%                                                                             %
206
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
207
 
%
208
 
%  GetRandomKey() gets a random key from the reservoir.
209
 
%
210
 
%  The format of the GetRandomKey method is:
211
 
%
212
 
%      GetRandomKey(unsigned char *key,const size_t length)
213
 
%
214
 
%  A description of each parameter follows:
215
 
%
216
 
%    o key: The key.
217
 
%
218
 
%    o length: The key length.
219
 
%
220
 
*/
221
 
MagickExport void GetRandomKey(unsigned char *key,const size_t length)
222
 
{
223
 
  SignatureInfo
224
 
    digest_info;
225
 
 
226
 
  long
227
 
    n;
228
 
 
229
 
  assert(key != (unsigned char *) NULL);
230
 
  if ((roulette == (unsigned long *) NULL) ||
231
 
      (reservoir == (SignatureInfo *) NULL))
232
 
    InitializeRandomReservoir();
233
 
  AcquireSemaphoreInfo(&random_semaphore);
234
 
  for (n=(long) length; n > 0; n-=sizeof(reservoir->digest))
235
 
  {
236
 
    GetSignatureInfo(&digest_info);
237
 
    UpdateSignature(&digest_info,(const unsigned char *) reservoir->digest,
238
 
      sizeof(reservoir->digest));
239
 
    UpdateSignature(&digest_info,(const unsigned char *) roulette,
240
 
      sizeof(roulette));
241
 
    FinalizeSignature(&digest_info);
242
 
    (*roulette)++;
243
 
    (void) CopyMagickMemory(key,digest_info.digest,(size_t) (n < (long)
244
 
      sizeof(reservoir->digest) ? n : (long) sizeof(reservoir->digest)));
245
 
    key+=sizeof(reservoir->digest);
246
 
  }
247
 
  RelinquishSemaphoreInfo(random_semaphore);
248
 
}
249
 
 
250
 
/*
251
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
252
 
%                                                                             %
253
 
%                                                                             %
254
 
%                                                                             %
255
 
%   G e t R a n d o m V a l u e                                               %
256
 
%                                                                             %
257
 
%                                                                             %
258
 
%                                                                             %
259
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
260
 
%
261
 
%  GetRandomValue() return a non-negative double-precision floating-point
262
 
%  value uniformly distributed over the interval [0.0, 1.0) with a 2 to the
263
 
%  128th-1 period.
264
 
%
265
 
%  The format of the GetRandomValue method is:
266
 
%
267
 
%      double GetRandomValue(void)
268
 
%
269
 
*/
270
 
MagickExport double GetRandomValue(void)
271
 
{
272
 
  unsigned int
273
 
    range,
274
 
    t;
275
 
 
276
 
  if ((roulette == (unsigned long *) NULL) ||
277
 
      (reservoir == (SignatureInfo *) NULL))
278
 
    InitializeRandomReservoir();
279
 
  while ((random_info.w == ~0U) || (random_info.x == (~0U)) ||
280
 
         (random_info.y == (~0U)) || (random_info.z == (~0U)))
281
 
  {
282
 
    GetRandomKey((unsigned char *) &random_info.w,sizeof(random_info.w));
283
 
    GetRandomKey((unsigned char *) &random_info.x,sizeof(random_info.x));
284
 
    GetRandomKey((unsigned char *) &random_info.y,sizeof(random_info.y));
285
 
    GetRandomKey((unsigned char *) &random_info.z,sizeof(random_info.z));
286
 
  }
287
 
  range=(~0U);
288
 
  do
289
 
  {
290
 
    t=(random_info.x ^ (random_info.x << 11));
291
 
    random_info.x=random_info.y;
292
 
    random_info.y=random_info.z;
293
 
    random_info.z=random_info.w;
294
 
    random_info.w=(random_info.w ^ (random_info.w >> 19)) ^ (t ^ (t >> 8));
295
 
  }
296
 
  while (random_info.w == range);
297
 
  return((double) random_info.w/range);
298
 
}
299
 
 
300
 
/*
301
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
302
 
%                                                                             %
303
 
%                                                                             %
304
 
%                                                                             %
305
 
+   I n i t i a l i z e R a n d o m R e s e r v i o r                         %
306
 
%                                                                             %
307
 
%                                                                             %
308
 
%                                                                             %
309
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
310
 
%
311
 
%  InitializeRandomReservoir() initializes the random reservoir with entropy.
312
 
%
313
 
%  The format of the InitializeRandomReservoir method is:
314
 
%
315
 
%      InitializeRandomReservoir(void)
316
 
%
317
 
*/
318
 
static void InitializeRandomReservoir(void)
319
 
{
320
 
  char
321
 
    filename[MaxTextExtent];
322
 
 
323
 
  int
324
 
    file;
 
264
  (void) UnlockSemaphoreInfo(random_semaphore);
 
265
  DestroySemaphoreInfo(&random_semaphore);
 
266
}
 
267
 
 
268
/*
 
269
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
270
%                                                                             %
 
271
%                                                                             %
 
272
%                                                                             %
 
273
+   G e n e r a t e E n t r o p i c C h a o s                                 %
 
274
%                                                                             %
 
275
%                                                                             %
 
276
%                                                                             %
 
277
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
278
%
 
279
%  GenerateEntropicChaos() generate entropic chaos used to initialize the
 
280
%  random reservoir.
 
281
%
 
282
%  The format of the GenerateEntropicChaos method is:
 
283
%
 
284
%      StringInfo *GenerateEntropicChaos(RandomInfo *random_info)
 
285
%
 
286
%  A description of each parameter follows:
 
287
%
 
288
%    o random_info: the random info.
 
289
%
 
290
*/
 
291
 
 
292
static ssize_t ReadRandom(int file,unsigned char *source,size_t length)
 
293
{
 
294
  register unsigned char
 
295
    *q;
 
296
 
 
297
  ssize_t
 
298
    offset,
 
299
    count;
 
300
 
 
301
  offset=0;
 
302
  for (q=source; length != 0; length-=count)
 
303
  {
 
304
    count=(ssize_t) read(file,q,length);
 
305
    if (count <= 0)
 
306
      {
 
307
        count=0;
 
308
        if (errno == EINTR)
 
309
          continue;
 
310
        return(-1);
 
311
      }
 
312
    q+=count;
 
313
    offset+=count;
 
314
  }
 
315
  return(offset);
 
316
}
 
317
 
 
318
static StringInfo *GenerateEntropicChaos(RandomInfo *random_info)
 
319
{
 
320
#define MaxEntropyExtent  64
325
321
 
326
322
  long
327
323
    pid;
328
324
 
329
 
  time_t
 
325
  StringInfo
 
326
    *chaos,
 
327
    *entropy;
 
328
 
 
329
  unsigned long
330
330
    nanoseconds,
331
331
    seconds;
332
332
 
333
 
  unsigned char
334
 
    random[MaxTextExtent];
335
 
 
336
333
  /*
337
334
    Initialize random reservoir.
338
335
  */
 
336
  entropy=AcquireStringInfo(0);
 
337
  (void) LockSemaphoreInfo(random_info->semaphore);
 
338
  chaos=AcquireStringInfo(sizeof(unsigned char *));
 
339
  SetStringInfoDatum(chaos,(unsigned char *) &entropy);
 
340
  ConcatenateStringInfo(entropy,chaos);
 
341
  SetStringInfoDatum(chaos,(unsigned char *) entropy);
 
342
  ConcatenateStringInfo(entropy,chaos);
 
343
  pid=(long) getpid();
 
344
  SetStringInfoLength(chaos,sizeof(pid));
 
345
  SetStringInfoDatum(chaos,(unsigned char *) &pid);
 
346
  ConcatenateStringInfo(entropy,chaos);
339
347
  seconds=time((time_t *) 0);
340
348
  nanoseconds=0;
341
349
#if defined(MAGICKCORE_HAVE_GETTIMEOFDAY)
346
354
    if (gettimeofday(&timer,0) == 0)
347
355
      {
348
356
        seconds=timer.tv_sec;
349
 
        nanoseconds=(time_t) (1000*timer.tv_usec);
 
357
        nanoseconds=1000UL*timer.tv_usec;
350
358
      }
351
359
  }
352
360
#endif
362
370
      }
363
371
  }
364
372
#endif
365
 
  DistillRandomEvent((const unsigned char *) &seconds,sizeof(seconds));
366
 
  DistillRandomEvent((const unsigned char *) &nanoseconds,sizeof(nanoseconds));
 
373
  SetStringInfoLength(chaos,sizeof(seconds));
 
374
  SetStringInfoDatum(chaos,(unsigned char *) &seconds);
 
375
  ConcatenateStringInfo(entropy,chaos);
 
376
  SetStringInfoLength(chaos,sizeof(nanoseconds));
 
377
  SetStringInfoDatum(chaos,(unsigned char *) &nanoseconds);
 
378
  ConcatenateStringInfo(entropy,chaos);
367
379
  nanoseconds=0;
 
380
#if defined(MAGICKCORE_HAVE_CLOCK)
 
381
  nanoseconds=clock();
 
382
#endif
368
383
#if defined(MAGICKCORE_HAVE_TIMES)
369
384
  {
370
385
    struct tms
373
388
    (void) times(&timer);
374
389
    nanoseconds=timer.tms_utime+timer.tms_stime;
375
390
  }
376
 
#else
 
391
#endif
 
392
  SetStringInfoLength(chaos,sizeof(nanoseconds));
 
393
  SetStringInfoDatum(chaos,(unsigned char *) &nanoseconds);
 
394
  ConcatenateStringInfo(entropy,chaos);
 
395
#if defined(MAGICKCORE_HAVE_MKSTEMP)
 
396
  {
 
397
    char
 
398
      *filename;
 
399
 
 
400
    int
 
401
      file;
 
402
 
 
403
    filename=ConstantString("magickXXXXXX");
 
404
    file=mkstemp(filename);
 
405
    if (file != -1)
 
406
      (void) close(file);
 
407
    (void) remove(filename);
 
408
    SetStringInfoLength(chaos,strlen(filename));
 
409
    SetStringInfoDatum(chaos,(unsigned char *) filename);
 
410
    ConcatenateStringInfo(entropy,chaos);
 
411
    filename=DestroyString(filename);
 
412
  }
 
413
#endif
377
414
#if defined(__WINDOWS__)
378
 
  nanoseconds=(time_t) (NTElapsedTime()+NTUserTime());
 
415
  {
 
416
    double
 
417
      seconds;
 
418
 
 
419
    LARGE_INTEGER
 
420
      nanoseconds;
 
421
 
 
422
    MagickBooleanType
 
423
      status;
 
424
 
 
425
    /*
 
426
      Not crytographically strong but better than nothing.
 
427
    */
 
428
    seconds=NTElapsedTime()+NTUserTime();
 
429
    SetStringInfoLength(chaos,sizeof(seconds));
 
430
    SetStringInfoDatum(chaos,(unsigned char *) &seconds);
 
431
    ConcatenateStringInfo(entropy,chaos);
 
432
    if (QueryPerformanceCounter(&nanoseconds) != 0)
 
433
      {
 
434
        SetStringInfoLength(chaos,sizeof(nanoseconds));
 
435
        SetStringInfoDatum(chaos,(unsigned char *) &nanoseconds);
 
436
        ConcatenateStringInfo(entropy,chaos);
 
437
      }
 
438
    /*
 
439
      Our best hope for true entropy.
 
440
    */
 
441
    SetStringInfoLength(chaos,MaxEntropyExtent);
 
442
    status=NTGatherRandomData(MaxEntropyExtent,GetStringInfoDatum(chaos));
 
443
    ConcatenateStringInfo(entropy,chaos);
 
444
  }
379
445
#else
380
 
  nanoseconds=clock();
381
 
#endif
382
 
#endif
383
 
  DistillRandomEvent((const unsigned char *) &nanoseconds,sizeof(nanoseconds));
384
 
  pid=(long) getpid();
385
 
  DistillRandomEvent((const unsigned char *) &pid,sizeof(pid));
386
 
  DistillRandomEvent((const unsigned char *) &roulette,sizeof(roulette));
387
 
  (void) AcquireUniqueFilename(filename);
388
 
  DistillRandomEvent((const unsigned char *) filename,strlen(filename));
389
 
  (void) RelinquishUniqueFileResource(filename);
390
 
  file=open("/dev/urandom",O_RDONLY | O_BINARY);
391
 
  if (file != -1)
392
 
    {
393
 
      ssize_t
394
 
        count;
395
 
 
396
 
      count=read(file,random,MaxTextExtent);
397
 
      file=close(file)-1;
398
 
      DistillRandomEvent(random,(size_t) count);
399
 
    }
400
 
}
401
 
 
402
 
/*
403
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
404
 
%                                                                             %
405
 
%                                                                             %
406
 
%                                                                             %
407
 
%   S e e d R a n d o m E v e n t                                             %
408
 
%                                                                             %
409
 
%                                                                             %
410
 
%                                                                             %
411
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
412
 
%
413
 
%  SeedRandomReservoir() sets its argument as the seed for a new sequence of
414
 
%  pseudo-random numbers to be returned by GetRandomValue().
415
 
%
416
 
%  The format of the SeedRandomReservoir method is:
417
 
%
418
 
%      SeedRandomReservoir(const unsigned long seed)
419
 
%
420
 
%  A description of each parameter follows:
421
 
%
422
 
%    o seed: The seed.
423
 
%
424
 
*/
425
 
MagickExport void SeedRandomReservoir(const unsigned long seed)
426
 
{
 
446
  {
 
447
    char
 
448
      *filename;
 
449
 
 
450
    int
 
451
      file;
 
452
 
 
453
    ssize_t
 
454
      count;
 
455
 
 
456
    StringInfo
 
457
      *device;
 
458
 
 
459
    /*
 
460
      Not crytographically strong but better than nothing.
 
461
    */
 
462
    if (environ != (char **) NULL)
 
463
      {
 
464
        register long
 
465
          i;
 
466
 
 
467
        /*
 
468
          Squeeze some entropy from the sometimes unpredicatble environment.
 
469
        */
 
470
        for (i=0; environ[i] != (char *) NULL; i++)
 
471
        {
 
472
          SetStringInfoLength(chaos,strlen(environ[i]));
 
473
          SetStringInfoDatum(chaos,(unsigned char *) environ[i]);
 
474
          ConcatenateStringInfo(entropy,chaos);
 
475
        }
 
476
      }
 
477
    filename=AcquireString("/dev/urandom");
 
478
    device=StringToStringInfo(filename);
 
479
    device=DestroyStringInfo(device);
 
480
    file=open(filename,O_RDONLY | O_BINARY);
 
481
    filename=DestroyString(filename);
 
482
    if (file != -1)
 
483
      {
 
484
        SetStringInfoLength(chaos,MaxEntropyExtent);
 
485
        count=ReadRandom(file,GetStringInfoDatum(chaos),MaxEntropyExtent);
 
486
        (void) close(file);
 
487
        SetStringInfoLength(chaos,(size_t) count);
 
488
        ConcatenateStringInfo(entropy,chaos);
 
489
      }
 
490
    if (gather_true_random != MagickFalse)
 
491
      {
 
492
        /*
 
493
          Our best hope for true entropy.
 
494
        */
 
495
        filename=AcquireString("/dev/random");
 
496
        device=StringToStringInfo(filename);
 
497
        device=DestroyStringInfo(device);
 
498
        file=open(filename,O_RDONLY | O_BINARY);
 
499
        filename=DestroyString(filename);
 
500
        if (file == -1)
 
501
          {
 
502
            filename=AcquireString("/dev/srandom");
 
503
            device=StringToStringInfo(filename);
 
504
            device=DestroyStringInfo(device);
 
505
            file=open(filename,O_RDONLY | O_BINARY);
 
506
          }
 
507
        if (file != -1)
 
508
          {
 
509
            SetStringInfoLength(chaos,MaxEntropyExtent);
 
510
            count=ReadRandom(file,GetStringInfoDatum(chaos),MaxEntropyExtent);
 
511
            (void) close(file);
 
512
            SetStringInfoLength(chaos,(size_t) count);
 
513
            ConcatenateStringInfo(entropy,chaos);
 
514
          }
 
515
      }
 
516
  }
 
517
#endif
 
518
  chaos=DestroyStringInfo(chaos);
 
519
  (void) UnlockSemaphoreInfo(random_info->semaphore);
 
520
  return(entropy);
 
521
}
 
522
 
 
523
/*
 
524
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
525
%                                                                             %
 
526
%                                                                             %
 
527
%                                                                             %
 
528
%   G e t P s e u d o R a n d o m V a l u e                                   %
 
529
%                                                                             %
 
530
%                                                                             %
 
531
%                                                                             %
 
532
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
533
%
 
534
%  GetPseudoRandomValue() return a non-negative double-precision floating-point
 
535
%  value uniformly distributed over the interval [0.0, 1.0) with a 2 to the
 
536
%  128th-1 period.
 
537
%
 
538
%  The format of the GetPseudoRandomValue method is:
 
539
%
 
540
%      double GetPseudoRandomValue(void)
 
541
%
 
542
*/
 
543
MagickExport double GetPseudoRandomValue(void)
 
544
{
 
545
  double
 
546
    random;
 
547
 
 
548
  unsigned long
 
549
    alpha,
 
550
    range;
 
551
 
 
552
  AcquireSemaphoreInfo(&random_semaphore);
 
553
  if (random_seed[0] == ~0UL)
 
554
    SeedPseudoRandomGenerator(~0UL);
 
555
  range=(~0UL);
 
556
  do
 
557
  {
 
558
    alpha=(unsigned long) (random_seed[1] ^ (random_seed[1] << 11));
 
559
    random_seed[1]=random_seed[2];
 
560
    random_seed[2]=random_seed[3];
 
561
    random_seed[3]=random_seed[0];
 
562
    random_seed[0]=(random_seed[0] ^ (random_seed[0] >> 19)) ^ (alpha ^
 
563
      (alpha >> 8));
 
564
  } while (random_seed[0] == range);
 
565
  random=(double) random_seed[0]/range;
 
566
  (void) UnlockSemaphoreInfo(random_semaphore);
 
567
  return(random);
 
568
}
 
569
 
 
570
/*
 
571
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
572
%                                                                             %
 
573
%                                                                             %
 
574
%                                                                             %
 
575
%   G e t R a n d o m K e y                                                   %
 
576
%                                                                             %
 
577
%                                                                             %
 
578
%                                                                             %
 
579
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
580
%
 
581
%  GetRandomKey() gets a random key from the reservoir.
 
582
%
 
583
%  The format of the GetRandomKey method is:
 
584
%
 
585
%      StringInfo *GetRandomKey(RandomInfo *random_info,const size_t length)
 
586
%
 
587
%  A description of each parameter follows:
 
588
%
 
589
%    o random_info: the random info.
 
590
%
 
591
%    o length: the key length.
 
592
%
 
593
*/
 
594
MagickExport StringInfo *GetRandomKey(RandomInfo *random_info,
 
595
  const size_t length)
 
596
{
 
597
  StringInfo
 
598
    *key;
 
599
 
 
600
  assert(random_info != (RandomInfo *) NULL);
 
601
  key=AcquireStringInfo(length);
 
602
  SetRandomKey(random_info,length,GetStringInfoDatum(key));
 
603
  return(key);
 
604
}
 
605
 
 
606
/*
 
607
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
608
%                                                                             %
 
609
%                                                                             %
 
610
%                                                                             %
 
611
%   G e t R a n d o m V a l u e                                               %
 
612
%                                                                             %
 
613
%                                                                             %
 
614
%                                                                             %
 
615
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
616
%
 
617
%  GetRandomValue() return a non-negative double-precision floating-point
 
618
%  value uniformly distributed over the interval [0.0, 1.0) with a 2 to the
 
619
%  128th-1 period (not cryptographically strong).
 
620
%
 
621
%  The format of the GetRandomValue method is:
 
622
%
 
623
%      double GetRandomValue(void)
 
624
%
 
625
*/
 
626
MagickExport double GetRandomValue(RandomInfo *random_info)
 
627
{
 
628
  unsigned long
 
629
    key,
 
630
    range;
 
631
 
 
632
  range=(~0UL);
 
633
  do
 
634
  {
 
635
    SetRandomKey(random_info,sizeof(key),(unsigned char *) &key);
 
636
  } while (key == range);
 
637
  return((double) key/range);
 
638
}
 
639
 
 
640
/*
 
641
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
642
%                                                                             %
 
643
%                                                                             %
 
644
%                                                                             %
 
645
%   S e e d P s e u d o R a n d o m G e n e r a t o r                         %
 
646
%                                                                             %
 
647
%                                                                             %
 
648
%                                                                             %
 
649
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
650
%
 
651
%  SeedPseudoRandomGenerator() initializes the pseudo-random number generator
 
652
%  with a random seed.
 
653
%
 
654
%  The format of the SeedPseudoRandomGenerator method is:
 
655
%
 
656
%      void SeedPseudoRandomGenerator(const unsigned long seed)
 
657
%
 
658
%  A description of each parameter follows:
 
659
%
 
660
%    o seed: the seed.
 
661
%
 
662
*/
 
663
 
 
664
static inline size_t MagickMin(const size_t x,const size_t y)
 
665
{
 
666
  if (x < y)
 
667
    return(x);
 
668
  return(y);
 
669
}
 
670
 
 
671
MagickExport void SeedPseudoRandomGenerator(const unsigned long seed)
 
672
{
 
673
  const StringInfo
 
674
    *digest;
 
675
 
 
676
  SignatureInfo
 
677
    *signature_info;
 
678
 
 
679
  StringInfo
 
680
    *key;
 
681
 
427
682
  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
428
 
  DestroyRandomReservoir();
429
 
  DistillRandomEvent((const unsigned char *) &seed,sizeof(seed));
 
683
  if (seed == ~0UL)
 
684
    {
 
685
      RandomInfo
 
686
        *random_info;
 
687
 
 
688
      StringInfo
 
689
        *key;
 
690
 
 
691
 
 
692
      /*
 
693
        Initialize pseudo random number generator with random seed.
 
694
      */
 
695
      random_info=AcquireRandomInfo();
 
696
      key=GetRandomKey(random_info,sizeof(random_seed));
 
697
      (void) CopyMagickMemory(random_seed,GetStringInfoDatum(key),
 
698
        GetStringInfoLength(key));
 
699
      key=DestroyStringInfo(key);
 
700
      random_info=DestroyRandomInfo(random_info);
 
701
      return;
 
702
    }
 
703
  /*
 
704
    Initialize pseudo random number generator with a user-supplied seed.
 
705
  */
 
706
  signature_info=AcquireSignatureInfo();
 
707
  key=AcquireStringInfo(sizeof(seed));
 
708
  SetStringInfoDatum(key,(unsigned char *) &seed);
 
709
  UpdateSignature(signature_info,key);
 
710
  key=DestroyStringInfo(key);
 
711
  FinalizeSignature(signature_info);
 
712
  digest=GetSignatureDigest(signature_info);
 
713
  (void) CopyMagickMemory(random_seed,GetStringInfoDatum(digest),
 
714
    MagickMin(GetSignatureDigestsize(signature_info),sizeof(random_seed)));
 
715
  signature_info=DestroySignatureInfo(signature_info);
 
716
}
 
717
 
 
718
/*
 
719
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
720
%                                                                             %
 
721
%                                                                             %
 
722
%                                                                             %
 
723
%   S e t R a n d o m K e y                                                   %
 
724
%                                                                             %
 
725
%                                                                             %
 
726
%                                                                             %
 
727
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
728
%
 
729
%  SetRandomKey() sets a random key from the reservoir.
 
730
%
 
731
%  The format of the SetRandomKey method is:
 
732
%
 
733
%      void SetRandomKey(RandomInfo *random_info,const size_t length,
 
734
%        unsigned char *key)
 
735
%
 
736
%  A description of each parameter follows:
 
737
%
 
738
%    o random_info: the random info.
 
739
%
 
740
%    o length: the key length.
 
741
%
 
742
%    o key: the key.
 
743
%
 
744
*/
 
745
 
 
746
static inline void IncrementRandomNonce(StringInfo *nonce)
 
747
{
 
748
  register long
 
749
    i;
 
750
 
 
751
  unsigned char
 
752
    *datum;
 
753
 
 
754
  datum=GetStringInfoDatum(nonce);
 
755
  for (i=(long) (GetStringInfoLength(nonce)-1); i != 0; i--)
 
756
  {
 
757
    datum[i]++;
 
758
    if (datum[i] != 0)
 
759
      return;
 
760
  }
 
761
  ThrowFatalException(RandomFatalError,"SequenceWrapError");
 
762
}
 
763
 
 
764
MagickExport void SetRandomKey(RandomInfo *random_info,const size_t length,
 
765
  unsigned char *key)
 
766
{
 
767
  register size_t
 
768
    i;
 
769
 
 
770
  register unsigned char
 
771
    *p;
 
772
 
 
773
  SignatureInfo
 
774
    *signature_info;
 
775
 
 
776
  unsigned char
 
777
    *datum;
 
778
 
 
779
  assert(random_info != (RandomInfo *) NULL);
 
780
  if (length == 0)
 
781
    return;
 
782
  (void) LockSemaphoreInfo(random_info->semaphore);
 
783
  signature_info=random_info->signature_info;
 
784
  datum=GetStringInfoDatum(random_info->reservoir);
 
785
  i=length;
 
786
  for (p=key; (i != 0) && (random_info->i != 0); i--)
 
787
  {
 
788
    *p++=datum[random_info->i];
 
789
    random_info->i++;
 
790
    if (random_info->i == GetSignatureDigestsize(signature_info))
 
791
      random_info->i=0;
 
792
  }
 
793
  while (i >= GetSignatureDigestsize(signature_info))
 
794
  {
 
795
    InitializeSignature(signature_info);
 
796
    UpdateSignature(signature_info,random_info->nonce);
 
797
    FinalizeSignature(signature_info);
 
798
    IncrementRandomNonce(random_info->nonce);
 
799
    (void) CopyMagickMemory(p,GetStringInfoDatum(GetSignatureDigest(
 
800
      signature_info)),GetSignatureDigestsize(signature_info));
 
801
    p+=GetSignatureDigestsize(signature_info);
 
802
    i-=GetSignatureDigestsize(signature_info);
 
803
  }
 
804
  if (i != 0)
 
805
    {
 
806
      InitializeSignature(signature_info);
 
807
      UpdateSignature(signature_info,random_info->nonce);
 
808
      FinalizeSignature(signature_info);
 
809
      IncrementRandomNonce(random_info->nonce);
 
810
      SetStringInfo(random_info->reservoir,GetSignatureDigest(signature_info));
 
811
      random_info->i=i;
 
812
      datum=GetStringInfoDatum(random_info->reservoir);
 
813
      while (i-- != 0)
 
814
        p[i]=datum[i];
 
815
    }
 
816
  (void) UnlockSemaphoreInfo(random_info->semaphore);
 
817
}
 
818
 
 
819
/*
 
820
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
821
%                                                                             %
 
822
%                                                                             %
 
823
%                                                                             %
 
824
%   S e t R a n d o m T r u e R a n d o m                                     %
 
825
%                                                                             %
 
826
%                                                                             %
 
827
%                                                                             %
 
828
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
829
%
 
830
%  SetRandomTrueRandom() declares your intentions to use true random numbers.
 
831
%  True random numbers are encouraged but may not always be practical because
 
832
%  your application may block while entropy is gathered from your environment.
 
833
%
 
834
%  The format of the SetRandomTrueRandom method is:
 
835
%
 
836
%      void SetRandomTrueRandom(const MagickBooleanType true_random)
 
837
%
 
838
%  A description of each parameter follows:
 
839
%
 
840
%    o true_random: declare your intentions to use true-random number.
 
841
%
 
842
*/
 
843
MagickExport void SetRandomTrueRandom(const MagickBooleanType true_random)
 
844
{
 
845
  gather_true_random=true_random;
430
846
}