1 /*
2 * Copyright (c) 2014 Mellanox Technologies, Inc.
3 * All rights reserved.
4 * Copyright (c) 2016 Research Organization for Information Science
5 * and Technology (RIST). All rights reserved.
6 * Copyright (c) 2016 Intel, Inc. All rights reserved.
7 * $COPYRIGHT$
8 *
9 * Additional copyrights may follow
10 *
11 * $HEADER$
12 */
13
14 #include <src/include/pmix_config.h>
15
16 #include <string.h>
17
18 #include "alfg.h"
19
20 /* Mask corresponding to the primitive polynomial
21 *---------------------------------------------------
22 *
23 * p(x) = 1 + x^25 + x^27 + x^29 + x^30 + x^31 + x^32
24 *
25 *---------------------------------------------------
26 */
27 #define MASK 0x80000057U
28
29 /* Additive lagged Fibonacci parameters:
30 *---------------------------------------------------
31 *
32 * x_n = (x_(n - TAP1) + x_(n - TAP2) ) mod M
33 *
34 *---------------------------------------------------
35 */
36 #define TAP1 127
37 #define TAP2 97
38 #define CBIT 21 /* Canonical bit */
39
40
41 /**
42 * @brief Galois shift register: Used to seed the ALFG's
43 * canonical rectangle
44 *
45 * @param[in] unsigned int *seed: used to seed the Galois register
46 * @param[out] uint32_t lsb: least significant bit of the Galois
47 * register after shift
48 */
49 static uint32_t galois(unsigned int *seed){
50
51 uint32_t lsb;
52 lsb = (*seed & 1) ? 1 : 0;
53 *seed >>= 1;
54 /* tap it with the mask */
55 *seed = *seed ^ (lsb*MASK);
56
57 return lsb;
58 }
59
60 /* PMIX global rng buffer */
61 static pmix_rng_buff_t alfg_buffer;
62
63 /**
64 * @brief Routine to seed the ALFG register
65 *
66 * @param[in] uint32_t seed
67 * @param[out] pmix_rng_buff_t *buff: handle to ALFG buffer state
68 */
69 int pmix_srand(pmix_rng_buff_t *buff, uint32_t seed) {
70
71 int i, j;
72 uint32_t seed_cpy = seed;
73 buff->tap1 = TAP1 - 1;
74 buff->tap2 = TAP2 - 1;
75
76 /* zero out the register */
77 for( i = 0; i < TAP1; i++){
78 buff->alfg[i] = 0;
79 }
80 /* set the canonical bit */
81 buff->alfg[CBIT] = 1;
82
83 /* seed the ALFG register by blasting
84 * the canonical rectangle with bits
85 */
86 for ( j = 1; j < TAP1; j++){
87 for( i = 1; i < 32; i++){
88 buff->alfg[j] = buff->alfg[j] ^ ((galois(&seed_cpy))<<i);
89 }
90 }
91 /* copy the ALFG to the global buffer */
92 memcpy(&alfg_buffer, buff, sizeof(alfg_buffer));
93
94 return 1;
95
96 }
97
98 /**
99 * @brief The additive lagged Fibonnaci PRNG
100 *
101 * @param[in] pmix_rng_buff_t *buff: handle to ALFG buffer state
102 * @param[out] 32-bit unsigned random integer
103 */
104
105 uint32_t pmix_rand(pmix_rng_buff_t *buff){
106
107 int *tap1 = &(buff->tap1);
108 int *tap2 = &(buff->tap2);
109 uint64_t overflow;
110 uint32_t temp;
111
112 /* prevent overflow */
113 overflow = (uint64_t) buff->alfg[*tap1] + (uint64_t) buff->alfg[*tap2];
114 /* circular buffer arithmetic */
115 temp = (*tap1 + 1) == TAP1 ? 0 : (*tap1 + 1);
116 /* Division modulo 2^32 */
117 buff->alfg[temp] = (uint32_t) ( overflow & ((1ULL<<32) -1));
118
119 /* increment tap points */
120 *tap1 = (*tap1 + 1)%TAP1;
121 *tap2 = (*tap2 + 1)%TAP1;
122
123 return buff->alfg[temp];
124
125 }
126
127 /**
128 * @brief A wrapper for pmix_rand() with our global ALFG buffer;
129 *
130 * @param[in] none
131 * @param[out] int, the same as normal rand(3)
132 */
133 int pmix_random(void){
134 /* always return a positive int */
135 return (int)(pmix_rand(&alfg_buffer) & 0x7FFFFFFF);
136 }