root / xseg / peers / user / bench-lfsr.c @ 9e593ec0
History | View | Annotate | Download (7.6 kB)
| 1 |
#include <stdio.h> |
|---|---|
| 2 |
#include <math.h> |
| 3 |
|
| 4 |
#include <bench-lfsr.h> |
| 5 |
|
| 6 |
/*
|
| 7 |
* LFSR taps retrieved from:
|
| 8 |
* http://home1.gte.net/res0658s/electronics/LFSRtaps.html
|
| 9 |
*
|
| 10 |
* The memory overhead of the following tap table should be relatively small,
|
| 11 |
* no more than 400 bytes.
|
| 12 |
*/
|
| 13 |
static uint8_t taps[64][MAX_TAPS] = |
| 14 |
{
|
| 15 |
{0}, {0}, {0}, //LFSRs with less that 3-bits cannot exist
|
| 16 |
{3, 2}, //Tap position for 3-bit LFSR
|
| 17 |
{4, 3}, //Tap position for 4-bit LFSR
|
| 18 |
{5, 3}, //Tap position for 5-bit LFSR
|
| 19 |
{6, 5}, //Tap position for 6-bit LFSR
|
| 20 |
{7, 6}, //Tap position for 7-bit LFSR
|
| 21 |
{8, 6, 5 ,4}, //Tap position for 8-bit LFSR
|
| 22 |
{9, 5}, //Tap position for 9-bit LFSR
|
| 23 |
{10, 7}, //Tap position for 10-bit LFSR
|
| 24 |
{11, 9}, //Tap position for 11-bit LFSR
|
| 25 |
{12, 6, 4, 1}, //Tap position for 12-bit LFSR
|
| 26 |
{13, 4, 3, 1}, //Tap position for 13-bit LFSR
|
| 27 |
{14, 5, 3, 1}, //Tap position for 14-bit LFSR
|
| 28 |
{15, 14}, //Tap position for 15-bit LFSR
|
| 29 |
{16, 15, 13, 4}, //Tap position for 16-bit LFSR
|
| 30 |
{17, 14}, //Tap position for 17-bit LFSR
|
| 31 |
{18, 11}, //Tap position for 18-bit LFSR
|
| 32 |
{19, 6, 2, 1}, //Tap position for 19-bit LFSR
|
| 33 |
{20, 17}, //Tap position for 20-bit LFSR
|
| 34 |
{21, 19}, //Tap position for 21-bit LFSR
|
| 35 |
{22, 21}, //Tap position for 22-bit LFSR
|
| 36 |
{23, 18}, //Tap position for 23-bit LFSR
|
| 37 |
{24, 23, 22, 17}, //Tap position for 24-bit LFSR
|
| 38 |
{25, 22}, //Tap position for 25-bit LFSR
|
| 39 |
{26, 6, 2, 1}, //Tap position for 26-bit LFSR
|
| 40 |
{27, 5, 2, 1}, //Tap position for 27-bit LFSR
|
| 41 |
{28, 25}, //Tap position for 28-bit LFSR
|
| 42 |
{29, 27}, //Tap position for 29-bit LFSR
|
| 43 |
{30, 6, 4, 1}, //Tap position for 30-bit LFSR
|
| 44 |
{31, 28}, //Tap position for 31-bit LFSR
|
| 45 |
{32, 31, 29, 1}, //Tap position for 32-bit LFSR
|
| 46 |
{33, 20}, //Tap position for 33-bit LFSR
|
| 47 |
{34, 27, 2, 1}, //Tap position for 34-bit LFSR
|
| 48 |
{35, 33}, //Tap position for 35-bit LFSR
|
| 49 |
{36, 25}, //Tap position for 36-bit LFSR
|
| 50 |
{37, 5, 4, 3, 2, 1},//Tap position for 37-bit LFSR
|
| 51 |
{38, 6, 5, 1}, //Tap position for 38-bit LFSR
|
| 52 |
{39, 35}, //Tap position for 39-bit LFSR
|
| 53 |
{40, 38, 21, 19}, //Tap position for 40-bit LFSR
|
| 54 |
{41, 38}, //Tap position for 41-bit LFSR
|
| 55 |
{42, 41, 20, 19}, //Tap position for 42-bit LFSR
|
| 56 |
{43, 42, 38, 37}, //Tap position for 43-bit LFSR
|
| 57 |
{44, 43, 18, 17}, //Tap position for 44-bit LFSR
|
| 58 |
{45, 44, 42, 41}, //Tap position for 45-bit LFSR
|
| 59 |
{46, 45, 26, 25}, //Tap position for 46-bit LFSR
|
| 60 |
{47, 42}, //Tap position for 47-bit LFSR
|
| 61 |
{48, 47, 21, 20}, //Tap position for 48-bit LFSR
|
| 62 |
{49, 40}, //Tap position for 49-bit LFSR
|
| 63 |
{50, 49, 24, 23}, //Tap position for 50-bit LFSR
|
| 64 |
{51, 50, 36, 35}, //Tap position for 51-bit LFSR
|
| 65 |
{52, 49}, //Tap position for 52-bit LFSR
|
| 66 |
{53, 52, 38, 37}, //Tap position for 53-bit LFSR
|
| 67 |
{54, 53, 18, 17}, //Tap position for 54-bit LFSR
|
| 68 |
{55, 31}, //Tap position for 55-bit LFSR
|
| 69 |
{56, 55, 35, 34}, //Tap position for 56-bit LFSR
|
| 70 |
{57, 50}, //Tap position for 57-bit LFSR
|
| 71 |
{58, 39}, //Tap position for 58-bit LFSR
|
| 72 |
{59, 58, 38, 37}, //Tap position for 59-bit LFSR
|
| 73 |
{60, 59}, //Tap position for 60-bit LFSR
|
| 74 |
{61, 60, 46, 45}, //Tap position for 61-bit LFSR
|
| 75 |
{62, 61, 6, 5}, //Tap position for 62-bit LFSR
|
| 76 |
{63, 62}, //Tap position for 63-bit LFSR
|
| 77 |
}; |
| 78 |
|
| 79 |
#define __LFSR_NEXT(__lfsr, __v) \
|
| 80 |
__v = ((__v >> 1) | __lfsr->cached_bit) ^ \
|
| 81 |
(((__v & 1UL) - 1UL) & __lfsr->xormask); |
| 82 |
|
| 83 |
static inline void __lfsr_next(struct bench_lfsr *lfsr, unsigned int spin) |
| 84 |
{
|
| 85 |
/*
|
| 86 |
* This should be O(1) since most compilers will create a jump table for
|
| 87 |
* this switch.
|
| 88 |
*/
|
| 89 |
switch (spin) {
|
| 90 |
case 16: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 91 |
case 15: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 92 |
case 14: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 93 |
case 13: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 94 |
case 12: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 95 |
case 11: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 96 |
case 10: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 97 |
case 9: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 98 |
case 8: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 99 |
case 7: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 100 |
case 6: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 101 |
case 5: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 102 |
case 4: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 103 |
case 3: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 104 |
case 2: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 105 |
case 1: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 106 |
case 0: __LFSR_NEXT(lfsr, lfsr->last_val); |
| 107 |
default: break; |
| 108 |
} |
| 109 |
} |
| 110 |
|
| 111 |
/*
|
| 112 |
* lfsr_next does the following:
|
| 113 |
*
|
| 114 |
* a. Return if the number of max values has been exceeded.
|
| 115 |
* b. Check if we have a spin value that produces a repeating subsequence.
|
| 116 |
* This is previously calculated in `prepare_spin` and cycle_length should
|
| 117 |
* be > 0. If we do have such a spin:
|
| 118 |
*
|
| 119 |
* i. Decrement the calculated cycle.
|
| 120 |
* ii. If it reaches zero, add "+1" to the spin and reset the cycle_length
|
| 121 |
* (we have it cached in the struct fio_lfsr)
|
| 122 |
*
|
| 123 |
* In either case, continue with the calculation of the next value.
|
| 124 |
* c. Check if the calculated value exceeds the desirable range. In this case,
|
| 125 |
* go back to b, else return.
|
| 126 |
*/
|
| 127 |
uint64_t lfsr_next(struct bench_lfsr *lfsr)
|
| 128 |
{
|
| 129 |
lfsr->num_vals++; |
| 130 |
|
| 131 |
do {
|
| 132 |
if (lfsr->cycle_length) {
|
| 133 |
lfsr->cycle_length--; |
| 134 |
if (!lfsr->cycle_length) {
|
| 135 |
__lfsr_next(lfsr, lfsr->spin + 1);
|
| 136 |
lfsr->cycle_length = lfsr->cached_cycle_length; |
| 137 |
goto check;
|
| 138 |
} |
| 139 |
} |
| 140 |
__lfsr_next(lfsr, lfsr->spin); |
| 141 |
check: ;
|
| 142 |
} while (lfsr->last_val > lfsr->max_val);
|
| 143 |
|
| 144 |
return lfsr->last_val;
|
| 145 |
} |
| 146 |
|
| 147 |
static uint64_t lfsr_create_xormask(uint8_t *taps)
|
| 148 |
{
|
| 149 |
int i;
|
| 150 |
uint64_t xormask = 0;
|
| 151 |
|
| 152 |
for(i = 0; i < MAX_TAPS && taps[i] != 0; i++) |
| 153 |
xormask |= 1UL << (taps[i] - 1); |
| 154 |
|
| 155 |
return xormask;
|
| 156 |
} |
| 157 |
|
| 158 |
static uint8_t *find_lfsr(uint64_t size)
|
| 159 |
{
|
| 160 |
int i;
|
| 161 |
|
| 162 |
for (i = 3; i < 64; i++) |
| 163 |
if ((1UL << i) > size) /* TODO: Explain why. */ |
| 164 |
return taps[i];
|
| 165 |
|
| 166 |
return NULL; |
| 167 |
} |
| 168 |
|
| 169 |
/*
|
| 170 |
* It is well-known that all maximal n-bit LFSRs will start repeating
|
| 171 |
* themselves after their 2^n iteration. The introduction of spins however, is
|
| 172 |
* possible to create a repetition of a sub-sequence before we hit that mark.
|
| 173 |
* This happens if:
|
| 174 |
*
|
| 175 |
* [1]: ((2^n - 1) * i) % (spin + 1) == 0,
|
| 176 |
* where "n" is LFSR's bits and "i" any number within the range [1,spin]
|
| 177 |
*
|
| 178 |
* It is important to know beforehand if a spin can cause a repetition of a
|
| 179 |
* sub-sequence (cycle) and its length. However, calculating (2^n - 1) * i may
|
| 180 |
* produce a buffer overflow for "n" close to 64, so we expand the above to:
|
| 181 |
*
|
| 182 |
* [2]: (2^n - 1) -> (x * (spin + 1) + y), where x >= 0 and 0 <= y <= spin
|
| 183 |
*
|
| 184 |
* Thus, [1] is equivalent to (y * i) % (spin + 1) == 0;
|
| 185 |
* Also, the cycle's length will be (x * i) + (y * i) / (spin + 1)
|
| 186 |
*/
|
| 187 |
int prepare_spin(struct bench_lfsr *lfsr, unsigned int spin) |
| 188 |
{
|
| 189 |
uint64_t max = (lfsr->cached_bit << 1) - 1; |
| 190 |
uint64_t x, y; |
| 191 |
int i;
|
| 192 |
|
| 193 |
if (spin > 15) |
| 194 |
return 1; |
| 195 |
|
| 196 |
x = max / (spin + 1);
|
| 197 |
y = max % (spin + 1);
|
| 198 |
lfsr->cycle_length = max; /* This is the expected cycle */
|
| 199 |
lfsr->spin = spin; |
| 200 |
|
| 201 |
for (i = 1; i <= spin; i++) { |
| 202 |
if ((y * i) % (spin + 1) == 0) { |
| 203 |
lfsr->cycle_length = (x * i) + (y * i) / (spin + 1);
|
| 204 |
break;
|
| 205 |
} |
| 206 |
} |
| 207 |
lfsr->cached_cycle_length = lfsr->cycle_length; |
| 208 |
|
| 209 |
return 0; |
| 210 |
} |
| 211 |
|
| 212 |
int lfsr_reset(struct bench_lfsr *lfsr, unsigned long seed) |
| 213 |
{
|
| 214 |
uint64_t bitmask = (lfsr->cached_bit << 1) - 1; |
| 215 |
|
| 216 |
lfsr->num_vals = 0;
|
| 217 |
lfsr->last_val = seed & bitmask; |
| 218 |
|
| 219 |
/* All-ones state is illegal for XNOR LFSRs */
|
| 220 |
if (lfsr->last_val == bitmask)
|
| 221 |
return 1; |
| 222 |
|
| 223 |
return 0; |
| 224 |
} |
| 225 |
|
| 226 |
int lfsr_init(struct bench_lfsr *lfsr, uint64_t nums, unsigned long seed, |
| 227 |
unsigned int spin) |
| 228 |
{
|
| 229 |
uint8_t *lfsr_taps; |
| 230 |
|
| 231 |
lfsr_taps = find_lfsr(nums); |
| 232 |
if (!lfsr_taps)
|
| 233 |
return 1; |
| 234 |
|
| 235 |
lfsr->max_val = nums - 1;
|
| 236 |
lfsr->xormask = lfsr_create_xormask(lfsr_taps); |
| 237 |
lfsr->cached_bit = 1UL << (lfsr_taps[0] - 1); |
| 238 |
|
| 239 |
if (prepare_spin(lfsr, spin))
|
| 240 |
return 1; |
| 241 |
|
| 242 |
if (lfsr_reset(lfsr, seed))
|
| 243 |
return 1; |
| 244 |
|
| 245 |
return 0; |
| 246 |
} |
| 247 |
|