lib/lfsr.c

   1 #include <stdio.h>
   2
   3 #include "lfsr.h"
   4
   5 /*
   6  * Trom table 3 of
   7  *
   8  * http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
   9  */
  10 static struct lfsr_taps lfsr_taps[] = {
  11         {
  12                 .length = 16,
  13                 .taps   = { 16, 15, 13, 4, },
  14         },
  15         {
  16                 .length = 17,
  17                 .taps   = { 17, 14, },
  18         },
  19         {
  20                 .length = 18,
  21                 .taps   = { 18, 11, },
  22         },
  23         {
  24                 .length = 19,
  25                 .taps   = { 19, 6, 2, 1, },
  26         },
  27         {
  28                 .length = 20,
  29                 .taps   = { 20, 17, },
  30         },
  31         {
  32                 .length = 21,
  33                 .taps   = { 21, 19, },
  34         },
  35         {
  36                 .length = 22,
  37                 .taps   = { 22, 21, },
  38         },
  39         {
  40                 .length = 23,
  41                 .taps   = { 23, 18, },
  42         },
  43         {
  44                 .length = 24,
  45                 .taps   = { 24, 23, 22, 17, },
  46         },
  47         {
  48                 .length = 25,
  49                 .taps   = { 25, 22, },
  50         },
  51         {
  52                 .length = 26,
  53                 .taps   = {26, 6, 2, 1, },
  54         },
  55         {
  56                 .length = 27,
  57                 .taps   = { 27, 5, 2, 1, },
  58         },
  59         {
  60                 .length = 28,
  61                 .taps   = { 28, 25, },
  62         },
  63         {
  64                 .length = 29,
  65                 .taps   = {29, 27, },
  66         },
  67         {
  68                 .length = 30,
  69                 .taps   = { 30, 6, 4, 1, },
  70         },
  71         {
  72                 .length = 31,
  73                 .taps   = { 31, 28, },
  74         },
  75         {
  76                 .length = 32,
  77                 .taps   = { 32, 22, 2, 1, },
  78         },
  79         {
  80                 .length = 33,
  81                 .taps   = { 33, 20, },
  82         },
  83         {
  84                 .length = 34,
  85                 .taps   = { 34, 27, 2, 1, },
  86         },
  87         {
  88                 .length = 35,
  89                 .taps   = { 35, 33, },
  90         },
  91         {
  92                 .length = 36,
  93                 .taps   = { 36, 25, },
  94         },
  95         {
  96                 .length = 37,
  97                 .taps   = { 37, 5, 4, 3, 2, 1, },
  98         },
  99         {
 100                 .length = 38,
 101                 .taps   = { 38, 6, 5, 1, },
 102         },
 103         {
 104                 .length = 39,
 105                 .taps   = { 39, 35, },
 106         },
 107         {
 108                 .length = 40,
 109                 .taps   = { 40, 38, 21, 19, },
 110         },
 111         {
 112                 .length = 41,
 113                 .taps   = { 41, 38, },
 114         },
 115         {
 116                 .length = 42,
 117                 .taps   = { 42, 41, 20, 19, },
 118         },
 119         {
 120                 .length = 43,
 121                 .taps   = { 43, 42, 38, 37, },
 122         },
 123         {
 124                 .length = 44,
 125                 .taps   = { 44, 43, 38, 37, },
 126         },
 127         {
 128                 .length = 45,
 129                 .taps   = { 45, 44, 42, 41, },
 130         },
 131         {
 132                 .length = 46,
 133                 .taps   = { 46, 45, 26, 25, },
 134         },
 135         {
 136                 .length = 47,
 137                 .taps   = { 47, 42, },
 138         },
 139         {
 140                 .length = 48,
 141                 .taps   = { 48, 47, 21, 20, },
 142         },
 143         {
 144                 .length = 49,
 145                 .taps   = { 49, 40, },
 146         },
 147         {
 148                 .length = 50,
 149                 .taps   = { 50, 49, 36, 35, },
 150         },
 151         {
 152                 .length = 51,
 153                 .taps   = { 51, 50, 36, 35, },
 154         },
 155         {
 156                 .length = 52,
 157                 .taps   = { 52, 49, },
 158         },
 159         {
 160                 .length = 53,
 161                 .taps   = { 53, 52, 38, 37 },
 162         },
 163         {
 164                 .length = 54,
 165                 .taps   = { 54, 53, 18, 17 },
 166         },
 167         {
 168                 .length = 55,
 169                 .taps   = { 55, 31, },
 170         },
 171         {
 172                 .length = 56,
 173                 .taps   = { 56, 55, 35, 34, },
 174         },
 175         {
 176                 .length = 57,
 177                 .taps   = { 57, 50, },
 178         },
 179         {
 180                 .length = 58,
 181                 .taps   = { 58, 39, },
 182         },
 183         {
 184                 .length = 59,
 185                 .taps   = { 59, 58, 38, 37, },
 186         },
 187         {
 188                 .length = 60,
 189                 .taps   = { 60, 59, },
 190         },
 191         {
 192                 .length = 61,
 193                 .taps   = { 61, 60, 46, 45, },
 194         },
 195         {
 196                 .length = 62,
 197                 .taps   = { 62, 61, 6, 5, },
 198         },
 199         {
 200                 .length = 63,
 201                 .taps   = { 63, 62, },
 202         },
 203 };
 204
 205 static uint64_t __lfsr_next(uint64_t v, struct lfsr_taps *lt)
 206 {
 207         uint64_t xor_mask = 0;
 208         int i;
 209
 210         for (i = 0; lt->taps[i]; i++)
 211                 xor_mask ^= (v << (lt->taps[i] - 1));
 212
 213         xor_mask &= ~(~0UL << 1) << (lt->length - 1);
 214         return xor_mask | (v >> 1);
 215 }
 216
 217 int lfsr_next(struct fio_lfsr *fl, uint64_t *off)
 218 {
 219         if (fl->num_vals > fl->max_val)
 220                 return 1;
 221
 222         do {
 223                 fl->last_val = __lfsr_next(fl->last_val, &fl->taps);
 224                 if (fl->last_val - 1 <= fl->max_val)
 225                         break;
 226         } while (1);
 227
 228         *off = fl->last_val - 1;
 229         fl->num_vals++;
 230         return 0;
 231 }
 232
 233 static struct lfsr_taps *find_lfsr(uint64_t size)
 234 {
 235         int i;
 236
 237         for (i = 0; lfsr_taps[i].length; i++)
 238                 if ((1UL << lfsr_taps[i].length) >= size)
 239                         return &lfsr_taps[i];
 240
 241         return NULL;
 242 }
 243
 244 int lfsr_init(struct fio_lfsr *fl, uint64_t size)
 245 {
 246         struct lfsr_taps *tap;
 247         int i;
 248
 249         tap = find_lfsr(size);
 250         if (!tap)
 251                 return 1;
 252
 253         fl->last_val = 1;
 254         fl->max_val = size - 1;
 255         fl->num_vals = 0;
 256         fl->taps.length = tap->length;
 257         for (i = 0; i < FIO_MAX_TAPS; i++) {
 258                 fl->taps.taps[i] = tap->taps[i];
 259                 if (!fl->taps.taps[i])
 260                         break;
 261         }
 262
 263         return 0;
 264 }