1 /*
2 * $Id: schedule.c 944 2006-11-07 05:54:55Z boote $
3 */
4 /************************************************************************
5 * *
6 * Copyright (C) 2003 *
7 * Internet2 *
8 * All Rights Reserved *
9 * *
10 ************************************************************************/
11 /*
12 * File: schedule.c
13 *
14 * Author: Jeff Boote
15 * Internet2
16 *
17 * Date: Fri Jan 17 09:33:02 2003
18 *
19 * Description:
20 */
21 #include <owamp/owamp.h>
22
23 #include <stdlib.h>
24 #include <string.h>
25 #include <errno.h>
26
27 struct OWPExpContextRec{
28 /* AES random number generator fields */
29 keyInstance key; /* key used to encrypt the counter */
30 uint8_t counter[16]; /* 128-bit counter (network order) */
31 uint8_t out[16]; /* encrypted block buffer. */
32 };
33
34
35 struct OWPScheduleContextRec {
36 OWPContext ctx;
37
38 struct OWPExpContextRec exp;
39
40 uint64_t i; /* current index for generation */
41 uint64_t maxi;
42 uint32_t nslots;
43 OWPSlot *slots;
44 };
45
46 /*
47 * Function: OWPUnifRand64
48 *
49 * Description:
50 * Generate and return a 32-bit uniform random string (saved in the lower
51 * half of the OWPNum64.
52 *
53 * In Args:
54 *
55 * Out Args:
56 *
57 * Scope:
58 * Returns:
59 * Side Effect:
60 */
61 static OWPNum64
OWPUnifRand64(OWPExpContext ectx)62 OWPUnifRand64(
63 OWPExpContext ectx
64 )
65 {
66 uint8_t forth = ectx->counter[15] & (uint8_t)3;
67 uint8_t *buf;
68 int j;
69 OWPNum64 ret = 0;
70
71 /*
72 * Only generate a new AES number every 4'th UnifRand.
73 * The (out) buffer holds 128 random bits - enough for 4 x 32bit
74 * random numbers for the algorithm.
75 */
76 if (!forth){
77 rijndaelEncrypt(ectx->key.rk,ectx->key.Nr,
78 ectx->counter,ectx->out);
79 }
80
81 /*
82 * Increment the counter as a 128-bit single quantity in
83 * network byte order for AES counter mode.
84 */
85 for (j = 15; j >= 0; j--){
86 if (++ectx->counter[j]){
87 break;
88 }
89 }
90
91 /*
92 * Point buf to correct 1/4th of the out buffer.
93 */
94 buf = &ectx->out[4*forth];
95
96 /*
97 * Convert the "raw" buffer to an unsigned integer.
98 * (i.e. The last 4 bytes of ret will contain the random
99 * integer in network byte order after this loop.)
100 *
101 * (If OWPNum64 changes from a 32.32 format uint64_t, this will
102 * need to be modified. It is expecting to set the .32 portion.)
103 */
104 for(j=0;j<4;j++){
105 ret <<= 8;
106 ret += *buf++;
107 }
108
109 return ret;
110 }
111
112 /*
113 * Function: OWPExpContextNext
114 *
115 * Description:
116 *
117 * Generate an exponential deviate using a 32-bit binary string as an input
118 * This is algorithm 3.4.1.S from Knuth's v.2 of "Art of Computer Programming"
119 * (1998), p.133.
120 *
121 * It produces exponential (mean mu) random deviates.
122 *
123 * Algorithm S: the constants
124 *
125 * Q[k] = (ln2)/(1!) + (ln2)^2/(2!) + ... + (ln2)^k/(k!), 1 <= k <= 18
126 *
127 * are precomputed. NOTE: all scalar quantities and arithmetical
128 * operations are in fixed-precision 64-bit arithmetic (32 bits before
129 * and after the decimal point). All 32-bit uniform random strings are
130 * obtained by applying AES in counter mode to a 128-bit unsigned integer
131 * (initialized to be zero) written in network byte order, then picking the
132 * i_th quartet of bytes of the encrypted block, where i is equal to
133 * the value of the counter modulo 4. (Thus, one encrypted block gives
134 * rise to four 32-bit random strings)
135 *
136 * S1. [Get U and shift.] Generate a 32-bit uniform random binary fraction
137 *
138 * U = (.b0 b1 b2 ... b31) [note the decimal point]
139 *
140 * Locate the first zero bit b_j, and shift off the leading (j+1) bits,
141 * setting U <- (.b_{j+1} ... b31)
142 *
143 * NOTE: in the rare case that the zero has not been found it is prescribed
144 * that the algorithm return (mu*32*ln2).
145 *
146 * S2. [Immediate acceptance?] If U < ln2, set X <- mu*(j*ln2 + U) and terminate
147 * the algorithm. (Note that Q[1] = ln2.)
148 *
149 * S3. [Minimize.] Find the least k >= 2 sich that U < Q[k]. Generate
150 * k new uniform random binary fractions U1,...,Uk and set
151 * V <- min(U1,...,Uk).
152 *
153 * S4. [Deliver the answer.] Set X <- mu*(j + V)*ln2.
154 *
155 * In Args:
156 *
157 * Out Args:
158 *
159 * Scope:
160 * Returns:
161 * Side Effect:
162 */
163 /*
164 * This array has been computed according to the formula:
165 *
166 * Q[k] = (ln2)/(1!) + (ln2)^2/(2!) + ... + (ln2)^k/(k!)
167 *
168 * as described in the Knuth algorithm. (The values below have been
169 * multiplied by 2^32 and rounded to the nearest integer.)
170 */
171 static OWPNum64 Q[] = {
172 0, /* Placeholder. */
173 0xB17217F8,
174 0xEEF193F7,
175 0xFD271862,
176 0xFF9D6DD0,
177 0xFFF4CFD0,
178 0xFFFEE819,
179 0xFFFFE7FF,
180 0xFFFFFE2B,
181 0xFFFFFFE0,
182 0xFFFFFFFE,
183 0xFFFFFFFF
184 };
185
186 #define BIT31 (0x80000000UL)
187 #define MASK32(n) (n & 0xFFFFFFFFUL)
188 #define LN2 Q[1] /* this element represents ln2 */
189
190 OWPNum64
OWPExpContextNext(OWPExpContext ectx)191 OWPExpContextNext(
192 OWPExpContext ectx
193 )
194 {
195 uint32_t i, k, j = 0;
196 OWPNum64 U, V, tmp;
197
198 /*
199 * S1. [Get U and shift.] Generate a (t+1)-bit
200 */
201 /* Get U and shift */
202 U = OWPUnifRand64(ectx);
203
204 /*
205 * shift until bit 31 is 0 (bits 31-0 are the 32 Low-Order bits
206 * representing the "fractional" portion of the number.
207 */
208 while((U & BIT31) && (j < 32)){
209 U <<= 1;
210 j++;
211 }
212 /* remove the '0' itself */
213 U <<= 1;
214
215 /* Keep only the fractional part. */
216 U = MASK32(U);
217
218
219 /*
220 * S2. Immediate acceptance?
221 */
222 if (U < LN2){
223 return OWPNum64Add(OWPNum64Mult(OWPULongToNum64(j),LN2),U);
224 }
225
226 /*
227 * S3.
228 */
229 /* Minimize */
230 for(k = 2;k < I2Number(Q); k++){
231 if (U < Q[k]){
232 break;
233 }
234 }
235
236 V = OWPUnifRand64(ectx);
237 for(i = 2;i <= k; i++){
238 tmp = OWPUnifRand64(ectx);
239 if (tmp < V){
240 V = tmp;
241 }
242 }
243
244 /*
245 * S4.
246 */
247 /* Return (j+V)*ln2 */
248 return OWPNum64Mult(OWPNum64Add(OWPULongToNum64(j),V),
249 LN2);
250 }
251
252 /*
253 * Function: CheckSlots
254 *
255 * Description:
256 * This function validates the slots parameter of the TestSpec
257 * for the Create/Reset functions of the ScheduleContext. This ensures
258 * that future calls to the GenerateDelta functions will not fail.
259 *
260 * In Args:
261 *
262 * Out Args:
263 *
264 * Scope:
265 * Returns:
266 * Side Effect:
267 */
268 static
CheckSlots(OWPContext ctx,OWPTestSpec * tspec)269 int CheckSlots(
270 OWPContext ctx,
271 OWPTestSpec *tspec
272 )
273 {
274 uint32_t i;
275
276 for(i=0;i<tspec->nslots;i++){
277
278 switch(tspec->slots[i].slot_type){
279 case OWPSlotRandExpType:
280 case OWPSlotLiteralType:
281 break;
282 default:
283 OWPError(ctx,OWPErrFATAL,EINVAL,
284 "OWPScheduleContextGenerateNextDelta: Invalid slot");
285 return 1;
286 }
287 }
288
289 return 0;
290 }
291
292 /*
293 * Function: OWPScheduleContextFree
294 *
295 * Description:
296 * Free a Schedule context.
297 *
298 * In Args:
299 *
300 * Out Args:
301 *
302 * Scope:
303 * Returns:
304 * Side Effect:
305 */
306 void
OWPScheduleContextFree(OWPScheduleContext sctx)307 OWPScheduleContextFree(
308 OWPScheduleContext sctx
309 )
310 {
311 free(sctx);
312 }
313
314 /*
315 * Function: OWPScheduleContextCreate
316 *
317 * Description:
318 * Seed the random number generator using a 16-byte string.
319 * This is used to initialize the random number generator
320 *
321 * NOTE: This function does NOT copy the slots parameter of the
322 * TestSpec - instead just referencing the one passed into it.
323 * Therefore, the OWPScheduleContext should be free'd before
324 * free'ing the memory associated with the slots!
325 *
326 * In Args:
327 *
328 * Out Args:
329 *
330 * Scope:
331 * Returns:
332 * Side Effect:
333 */
334 OWPScheduleContext
OWPScheduleContextCreate(OWPContext ctx,OWPSID sid,OWPTestSpec * tspec)335 OWPScheduleContextCreate(
336 OWPContext ctx,
337 OWPSID sid,
338 OWPTestSpec *tspec
339 )
340 {
341 OWPScheduleContext sctx;
342
343 if(!tspec || !tspec->slots || !tspec->nslots || CheckSlots(ctx,tspec)){
344 OWPError(ctx,OWPErrFATAL,OWPErrINVALID,
345 "OWPScheduleContextCreate: Invalid tspec");
346 return NULL;
347 }
348
349 sctx = malloc(sizeof(*sctx));
350 if (!sctx){
351 OWPError(ctx,OWPErrFATAL,OWPErrUNKNOWN,"malloc(): %M");
352 return NULL;
353 }
354
355 sctx->ctx = ctx;
356
357 /*
358 * Initialize Key with sid.
359 * (This is only needed for Exponential random numbers, but just
360 * do it.)
361 */
362 bytes2Key(&sctx->exp.key,(uint8_t *)sid);
363
364 memset(sctx->exp.out,0,16);
365 memset(sctx->exp.counter,0,16);
366
367 sctx->i = 0;
368 sctx->maxi = tspec->npackets;
369 sctx->nslots = MIN(tspec->nslots,tspec->npackets);
370 sctx->slots = tspec->slots;
371
372 return(sctx);
373 }
374
375 /*
376 * Function: OWPScheduleContextReset
377 *
378 * Description:
379 * This function resets the sctx so the Delta generation can be
380 * restarted. Additionally, if sid and tspec are non-NULL, then
381 * then the sctx is reset to generate delta's for the distribution
382 * defined by those values.
383 *
384 * In Args:
385 *
386 * Out Args:
387 *
388 * Scope:
389 * Returns:
390 * Side Effect:
391 */
392 OWPErrSeverity
OWPScheduleContextReset(OWPScheduleContext sctx,OWPSID sid,OWPTestSpec * tspec)393 OWPScheduleContextReset(
394 OWPScheduleContext sctx,
395 OWPSID sid,
396 OWPTestSpec *tspec
397 )
398 {
399 memset(sctx->exp.out,0,16);
400 memset(sctx->exp.counter,0,16);
401 sctx->i = 0;
402
403 if(sid && tspec){
404
405 if(CheckSlots(sctx->ctx,tspec)){
406 return OWPErrFATAL;
407 }
408
409 /*
410 * Initialize Key with sid.
411 * (This is only needed for Exponential random numbers, but just
412 * do it.)
413 */
414 bytes2Key(&sctx->exp.key,(uint8_t *)sid);
415
416 sctx->maxi = tspec->npackets;
417 sctx->nslots = MIN(tspec->nslots,tspec->npackets);
418 sctx->slots = tspec->slots;
419
420 }
421
422 return OWPErrOK;
423 }
424
425 /*
426 * Function: OWPScheduleContextGenerateNextDelta
427 *
428 * Description:
429 * Fetch the next time offset.
430 *
431 * In Args:
432 *
433 * Out Args:
434 *
435 * Scope:
436 * Returns:
437 * Side Effect:
438 */
439 OWPNum64
OWPScheduleContextGenerateNextDelta(OWPScheduleContext sctx)440 OWPScheduleContextGenerateNextDelta(
441 OWPScheduleContext sctx
442 )
443 {
444 OWPSlot *slot;
445
446 if(sctx->i >= sctx->maxi){
447 OWPError(sctx->ctx,OWPErrFATAL,OWPErrUNKNOWN,
448 "OWPScheduleContextGenerateNextDelta: Schedule complete");
449 return OWPErrFATAL;
450 }
451 slot = &sctx->slots[sctx->i++ % sctx->nslots];
452
453 switch(slot->slot_type){
454 case OWPSlotRandExpType:
455 return OWPNum64Mult(OWPExpContextNext(&sctx->exp),
456 slot->rand_exp.mean);
457 case OWPSlotLiteralType:
458 return slot->literal.offset;
459 default:
460 /* Create and reset should keep this from happening. */
461 OWPError(sctx->ctx,OWPErrFATAL,OWPErrUNKNOWN,
462 "OWPScheduleContextGenerateNextDelta: Invalid slot");
463 }
464
465 /*NOTREACHED*/
466 abort();
467 return 0;
468 }
469
470 /*
471 * Function: OWPExpContextFree
472 *
473 * Description:
474 * Free an Exp context.
475 *
476 * In Args:
477 *
478 * Out Args:
479 *
480 * Scope:
481 * Returns:
482 * Side Effect:
483 */
484 void
OWPExpContextFree(OWPExpContext ectx)485 OWPExpContextFree(
486 OWPExpContext ectx
487 )
488 {
489 free(ectx);
490 }
491
492 /*
493 * Function: OWPExpContextCreate
494 *
495 * Description:
496 * Seed the random number generator using a 16-byte string.
497 * This is used to initialize the random number generator
498 *
499 * In Args:
500 *
501 * Out Args:
502 *
503 * Scope:
504 * Returns:
505 * Side Effect:
506 */
507 OWPExpContext
OWPExpContextCreate(OWPContext ctx,uint8_t seed[16])508 OWPExpContextCreate(
509 OWPContext ctx,
510 uint8_t seed[16]
511 )
512 {
513 OWPExpContext ectx;
514
515 ectx = malloc(sizeof(*ectx));
516 if (!ectx){
517 OWPError(ctx,OWPErrFATAL,OWPErrUNKNOWN,"malloc(): %M");
518 return NULL;
519 }
520
521 /*
522 * Initialize Key with seed.
523 */
524 bytes2Key(&ectx->key, seed);
525
526 memset(ectx->out,0,16);
527 memset(ectx->counter,0,16);
528
529 return(ectx);
530 }
531