../src/lowrisc_prim_all_0.1/rtl/prim_lfsr.sv Cov: 97.2%

   1: // Copyright lowRISC contributors.
   2: // Licensed under the Apache License, Version 2.0, see LICENSE for details.
   3: // SPDX-License-Identifier: Apache-2.0
   4: //
   5: // This module implements different LFSR types:
   6: //
   7: // 0) Galois XOR type LFSR ([1], internal XOR gates, very fast).
   8: //    Parameterizable width from 4 to 64 bits.
   9: //    Coefficients obtained from [2].
  10: //
  11: // 1) Fibonacci XNOR type LFSR, parameterizable from 3 to 168 bits.
  12: //    Coefficients obtained from [3].
  13: //
  14: // All flavors have an additional entropy input and lockup protection, which
  15: // reseeds the state once it has accidentally fallen into the all-zero (XOR) or
  16: // all-one (XNOR) state. Further, an external seed can be loaded into the LFSR
  17: // state at runtime. If that seed is all-zero (XOR case) or all-one (XNOR case),
  18: // the state will be reseeded in the next cycle using the lockup protection mechanism.
  19: // Note that the external seed input takes precedence over internal state updates.
  20: //
  21: // All polynomials up to 34 bit in length have been verified in simulation.
  22: //
  23: // Refs: [1] https://en.wikipedia.org/wiki/Linear-feedback_shift_register
  24: //       [2] https://users.ece.cmu.edu/~koopman/lfsr/
  25: //       [3] https://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
  26: 
  27: `include "prim_assert.sv"
  28: 
  29: module prim_lfsr #(
  30:   // Lfsr Type, can be FIB_XNOR or GAL_XOR
  31:   parameter                    LfsrType     = "GAL_XOR",
  32:   // Lfsr width
  33:   parameter int unsigned       LfsrDw       = 32,
  34:   // Width of the entropy input to be XOR'd into state (lfsr_q[EntropyDw-1:0])
  35:   parameter int unsigned       EntropyDw    =  8,
  36:   // Width of output tap (from lfsr_q[StateOutDw-1:0])
  37:   parameter int unsigned       StateOutDw   =  8,
  38:   // Lfsr reset state, must be nonzero!
  39:   parameter logic [LfsrDw-1:0] DefaultSeed  = LfsrDw'(1),
  40:   // Custom polynomial coeffs
  41:   parameter logic [LfsrDw-1:0] CustomCoeffs = '0,
  42:   // Enable this for DV, disable this for long LFSRs in FPV
  43:   parameter bit                MaxLenSVA    = 1'b1,
  44:   // Can be disabled in cases where seed and entropy
  45:   // inputs are unused in order to not distort coverage
  46:   // (the SVA will be unreachable in such cases)
  47:   parameter bit                LockupSVA    = 1'b1,
  48:   parameter bit                ExtSeedSVA   = 1'b1
  49: ) (
  50:   input                         clk_i,
  51:   input                         rst_ni,
  52:   input                         seed_en_i, // load external seed into the state (takes precedence)
  53:   input        [LfsrDw-1:0]     seed_i,    // external seed input
  54:   input                         lfsr_en_i, // enables the LFSR
  55:   input        [EntropyDw-1:0]  entropy_i, // additional entropy to be XOR'ed into the state
  56:   output logic [StateOutDw-1:0] state_o    // (partial) LFSR state output
  57: );
  58: 
  59:   // automatically generated with get-lfsr-coeffs.py script
  60:   localparam int unsigned GAL_XOR_LUT_OFF = 4;
  61:   localparam logic [63:0] GAL_XOR_COEFFS [61] =
  62:     '{ 64'h9,
  63:        64'h12,
  64:        64'h21,
  65:        64'h41,
  66:        64'h8E,
  67:        64'h108,
  68:        64'h204,
  69:        64'h402,
  70:        64'h829,
  71:        64'h100D,
  72:        64'h2015,
  73:        64'h4001,
  74:        64'h8016,
  75:        64'h10004,
  76:        64'h20013,
  77:        64'h40013,
  78:        64'h80004,
  79:        64'h100002,
  80:        64'h200001,
  81:        64'h400010,
  82:        64'h80000D,
  83:        64'h1000004,
  84:        64'h2000023,
  85:        64'h4000013,
  86:        64'h8000004,
  87:        64'h10000002,
  88:        64'h20000029,
  89:        64'h40000004,
  90:        64'h80000057,
  91:        64'h100000029,
  92:        64'h200000073,
  93:        64'h400000002,
  94:        64'h80000003B,
  95:        64'h100000001F,
  96:        64'h2000000031,
  97:        64'h4000000008,
  98:        64'h800000001C,
  99:        64'h10000000004,
 100:        64'h2000000001F,
 101:        64'h4000000002C,
 102:        64'h80000000032,
 103:        64'h10000000000D,
 104:        64'h200000000097,
 105:        64'h400000000010,
 106:        64'h80000000005B,
 107:        64'h1000000000038,
 108:        64'h200000000000E,
 109:        64'h4000000000025,
 110:        64'h8000000000004,
 111:        64'h10000000000023,
 112:        64'h2000000000003E,
 113:        64'h40000000000023,
 114:        64'h8000000000004A,
 115:        64'h100000000000016,
 116:        64'h200000000000031,
 117:        64'h40000000000003D,
 118:        64'h800000000000001,
 119:        64'h1000000000000013,
 120:        64'h2000000000000034,
 121:        64'h4000000000000001,
 122:        64'h800000000000000D };
 123: 
 124:   // automatically generated with get-lfsr-coeffs.py script
 125:   localparam int unsigned FIB_XNOR_LUT_OFF = 3;
 126:   localparam logic [167:0] FIB_XNOR_COEFFS [166] =
 127:     '{ 168'h6,
 128:        168'hC,
 129:        168'h14,
 130:        168'h30,
 131:        168'h60,
 132:        168'hB8,
 133:        168'h110,
 134:        168'h240,
 135:        168'h500,
 136:        168'h829,
 137:        168'h100D,
 138:        168'h2015,
 139:        168'h6000,
 140:        168'hD008,
 141:        168'h12000,
 142:        168'h20400,
 143:        168'h40023,
 144:        168'h90000,
 145:        168'h140000,
 146:        168'h300000,
 147:        168'h420000,
 148:        168'hE10000,
 149:        168'h1200000,
 150:        168'h2000023,
 151:        168'h4000013,
 152:        168'h9000000,
 153:        168'h14000000,
 154:        168'h20000029,
 155:        168'h48000000,
 156:        168'h80200003,
 157:        168'h100080000,
 158:        168'h204000003,
 159:        168'h500000000,
 160:        168'h801000000,
 161:        168'h100000001F,
 162:        168'h2000000031,
 163:        168'h4400000000,
 164:        168'hA000140000,
 165:        168'h12000000000,
 166:        168'h300000C0000,
 167:        168'h63000000000,
 168:        168'hC0000030000,
 169:        168'h1B0000000000,
 170:        168'h300003000000,
 171:        168'h420000000000,
 172:        168'hC00000180000,
 173:        168'h1008000000000,
 174:        168'h3000000C00000,
 175:        168'h6000C00000000,
 176:        168'h9000000000000,
 177:        168'h18003000000000,
 178:        168'h30000000030000,
 179:        168'h40000040000000,
 180:        168'hC0000600000000,
 181:        168'h102000000000000,
 182:        168'h200004000000000,
 183:        168'h600003000000000,
 184:        168'hC00000000000000,
 185:        168'h1800300000000000,
 186:        168'h3000000000000030,
 187:        168'h6000000000000000,
 188:        168'hD800000000000000,
 189:        168'h10000400000000000,
 190:        168'h30180000000000000,
 191:        168'h60300000000000000,
 192:        168'h80400000000000000,
 193:        168'h140000028000000000,
 194:        168'h300060000000000000,
 195:        168'h410000000000000000,
 196:        168'h820000000001040000,
 197:        168'h1000000800000000000,
 198:        168'h3000600000000000000,
 199:        168'h6018000000000000000,
 200:        168'hC000000018000000000,
 201:        168'h18000000600000000000,
 202:        168'h30000600000000000000,
 203:        168'h40200000000000000000,
 204:        168'hC0000000060000000000,
 205:        168'h110000000000000000000,
 206:        168'h240000000480000000000,
 207:        168'h600000000003000000000,
 208:        168'h800400000000000000000,
 209:        168'h1800000300000000000000,
 210:        168'h3003000000000000000000,
 211:        168'h4002000000000000000000,
 212:        168'hC000000000000000018000,
 213:        168'h10000000004000000000000,
 214:        168'h30000C00000000000000000,
 215:        168'h600000000000000000000C0,
 216:        168'hC00C0000000000000000000,
 217:        168'h140000000000000000000000,
 218:        168'h200001000000000000000000,
 219:        168'h400800000000000000000000,
 220:        168'hA00000000001400000000000,
 221:        168'h1040000000000000000000000,
 222:        168'h2004000000000000000000000,
 223:        168'h5000000000028000000000000,
 224:        168'h8000000004000000000000000,
 225:        168'h18600000000000000000000000,
 226:        168'h30000000000000000C00000000,
 227:        168'h40200000000000000000000000,
 228:        168'hC0300000000000000000000000,
 229:        168'h100010000000000000000000000,
 230:        168'h200040000000000000000000000,
 231:        168'h5000000000000000A0000000000,
 232:        168'h800000010000000000000000000,
 233:        168'h1860000000000000000000000000,
 234:        168'h3003000000000000000000000000,
 235:        168'h4010000000000000000000000000,
 236:        168'hA000000000140000000000000000,
 237:        168'h10080000000000000000000000000,
 238:        168'h30000000000000000000180000000,
 239:        168'h60018000000000000000000000000,
 240:        168'hC0000000000000000300000000000,
 241:        168'h140005000000000000000000000000,
 242:        168'h200000001000000000000000000000,
 243:        168'h404000000000000000000000000000,
 244:        168'h810000000000000000000000000102,
 245:        168'h1000040000000000000000000000000,
 246:        168'h3000000000000006000000000000000,
 247:        168'h5000000000000000000000000000000,
 248:        168'h8000000004000000000000000000000,
 249:        168'h18000000000000000000000000030000,
 250:        168'h30000000030000000000000000000000,
 251:        168'h60000000000000000000000000000000,
 252:        168'hA0000014000000000000000000000000,
 253:        168'h108000000000000000000000000000000,
 254:        168'h240000000000000000000000000000000,
 255:        168'h600000000000C00000000000000000000,
 256:        168'h800000040000000000000000000000000,
 257:        168'h1800000000000300000000000000000000,
 258:        168'h2000000000000010000000000000000000,
 259:        168'h4008000000000000000000000000000000,
 260:        168'hC000000000000000000000000000000600,
 261:        168'h10000080000000000000000000000000000,
 262:        168'h30600000000000000000000000000000000,
 263:        168'h4A400000000000000000000000000000000,
 264:        168'h80000004000000000000000000000000000,
 265:        168'h180000003000000000000000000000000000,
 266:        168'h200001000000000000000000000000000000,
 267:        168'h600006000000000000000000000000000000,
 268:        168'hC00000000000000006000000000000000000,
 269:        168'h1000000000000100000000000000000000000,
 270:        168'h3000000000000006000000000000000000000,
 271:        168'h6000000003000000000000000000000000000,
 272:        168'h8000001000000000000000000000000000000,
 273:        168'h1800000000000000000000000000C000000000,
 274:        168'h20000000000001000000000000000000000000,
 275:        168'h48000000000000000000000000000000000000,
 276:        168'hC0000000000000006000000000000000000000,
 277:        168'h180000000000000000000000000000000000000,
 278:        168'h280000000000000000000000000000005000000,
 279:        168'h60000000C000000000000000000000000000000,
 280:        168'hC00000000000000000000000000018000000000,
 281:        168'h1800000600000000000000000000000000000000,
 282:        168'h3000000C00000000000000000000000000000000,
 283:        168'h4000000080000000000000000000000000000000,
 284:        168'hC000300000000000000000000000000000000000,
 285:        168'h10000400000000000000000000000000000000000,
 286:        168'h30000000000000000000006000000000000000000,
 287:        168'h600000000000000C0000000000000000000000000,
 288:        168'hC0060000000000000000000000000000000000000,
 289:        168'h180000006000000000000000000000000000000000,
 290:        168'h3000000000C0000000000000000000000000000000,
 291:        168'h410000000000000000000000000000000000000000,
 292:        168'hA00140000000000000000000000000000000000000 };
 293: 
 294:   logic lockup;
 295:   logic [LfsrDw-1:0] lfsr_d, lfsr_q;
 296:   logic [LfsrDw-1:0] next_lfsr_state, coeffs;
 297: 
 298: 
 299:   ////////////////
 300:   // Galois XOR //
 301:   ////////////////
 302:   if (64'(LfsrType) == 64'("GAL_XOR")) begin : gen_gal_xor
 303: 
 304:     // if custom polynomial is provided
 305:     if (CustomCoeffs > 0) begin : gen_custom
 306:       assign coeffs = CustomCoeffs[LfsrDw-1:0];
 307:     end else begin : gen_lut
 308:       assign coeffs = GAL_XOR_COEFFS[LfsrDw-GAL_XOR_LUT_OFF][LfsrDw-1:0];
 309:       // check that the most significant bit of polynomial is 1
 310:       `ASSERT_INIT(MinLfsrWidth_A, LfsrDw >= $low(GAL_XOR_COEFFS)+GAL_XOR_LUT_OFF)
 311:       `ASSERT_INIT(MaxLfsrWidth_A, LfsrDw <= $high(GAL_XOR_COEFFS)+GAL_XOR_LUT_OFF)
 312:     end
 313: 
 314:     // calculate next state using internal XOR feedback and entropy input
 315:     assign next_lfsr_state = LfsrDw'(entropy_i) ^ ({LfsrDw{lfsr_q[0]}} & coeffs) ^ (lfsr_q >> 1);
 316: 
 317:     // lockup condition is all-zero
 318:     assign lockup = ~(|lfsr_q);
 319: 
 320:     // check that seed is not all-zero
 321:     `ASSERT_INIT(DefaultSeedNzCheck_A, |DefaultSeed)
 322: 
 323: 
 324:   ////////////////////
 325:   // Fibonacci XNOR //
 326:   ////////////////////
 327:   end else if (64'(LfsrType) == "FIB_XNOR") begin : gen_fib_xnor
 328: 
 329:     // if custom polynomial is provided
 330:     if (CustomCoeffs > 0) begin : gen_custom
 331:       assign coeffs = CustomCoeffs[LfsrDw-1:0];
 332:     end else begin : gen_lut
 333:       assign coeffs = FIB_XNOR_COEFFS[LfsrDw-FIB_XNOR_LUT_OFF][LfsrDw-1:0];
 334:       // check that the most significant bit of polynomial is 1
 335:       `ASSERT_INIT(MinLfsrWidth_A, LfsrDw >= $low(FIB_XNOR_COEFFS)+FIB_XNOR_LUT_OFF)
 336:       `ASSERT_INIT(MaxLfsrWidth_A, LfsrDw <= $high(FIB_XNOR_COEFFS)+FIB_XNOR_LUT_OFF)
 337:     end
 338: 
 339:     // calculate next state using external XNOR feedback and entropy input
 340:     assign next_lfsr_state = LfsrDw'(entropy_i) ^ {lfsr_q[LfsrDw-2:0], ~(^(lfsr_q & coeffs))};
 341: 
 342:     // lockup condition is all-ones
 343:     assign lockup = &lfsr_q;
 344: 
 345:     // check that seed is not all-ones
 346:     `ASSERT_INIT(DefaultSeedNzCheck_A, !(&DefaultSeed))
 347: 
 348: 
 349:   /////////////
 350:   // Unknown //
 351:   /////////////
 352:   end else begin : gen_unknown_type
 353:     `ASSERT_INIT(UnknownLfsrType_A, 0)
 354:   end
 355: 
 356: 
 357:   //////////////////
 358:   // Shared logic //
 359:   //////////////////
 360: 
 361:   assign lfsr_d = (seed_en_i)           ? seed_i          :
 362:                   (lfsr_en_i && lockup) ? DefaultSeed     :
 363:                   (lfsr_en_i)           ? next_lfsr_state :
 364:                                           lfsr_q;
 365: 
 366:   assign state_o  = lfsr_q[StateOutDw-1:0];
 367: 
 368:   always_ff @(posedge clk_i or negedge rst_ni) begin : p_reg
 369:     if (!rst_ni) begin
 370:       lfsr_q <= DefaultSeed;
 371:     end else begin
 372:       lfsr_q <= lfsr_d;
 373:     end
 374:   end
 375: 
 376: 
 377:   ///////////////////////
 378:   // shared assertions //
 379:   ///////////////////////
 380: 
 381:   `ASSERT_KNOWN(DataKnownO_A, state_o)
 382: 
 383: // the code below is not meant to be synthesized,
 384: // but it is intended to be used in simulation and FPV
 385: `ifndef SYNTHESIS
 386:   function automatic logic[LfsrDw-1:0] compute_next_state(logic[LfsrDw-1:0]    lfsrcoeffs,
 387:                                                           logic[EntropyDw-1:0] entropy,
 388:                                                           logic[LfsrDw-1:0]    state);
 389:     logic state0;
 390: 
 391:     // Galois XOR
 392:     if (64'(LfsrType) == 64'("GAL_XOR")) begin
 393:       if (state == 0) begin
 394:         state = DefaultSeed;
 395:       end else begin
 396:         state0 = state[0];
 397:         state = state >> 1;
 398:         if (state0) state ^= lfsrcoeffs;
 399:         state ^= LfsrDw'(entropy);
 400:       end
 401:     // Fibonacci XNOR
 402:     end else if (64'(LfsrType) == "FIB_XNOR") begin
 403:       if (&state) begin
 404:         state = DefaultSeed;
 405:       end else begin
 406:         state0 = ~(^(state & lfsrcoeffs));
 407:         state = state << 1;
 408:         state[0] = state0;
 409:         state ^= LfsrDw'(entropy);
 410:       end
 411:     end else begin
 412:       $error("unknown lfsr type");
 413:     end
 414: 
 415:     return state;
 416:   endfunction : compute_next_state
 417: 
 418:   // check whether next state is computed correctly
 419:   `ASSERT(NextStateCheck_A, lfsr_en_i && !seed_en_i |=> lfsr_q ==
 420:     compute_next_state(coeffs, $past(entropy_i,1), $past(lfsr_q,1)))
 421: `endif
 422: 
 423:   `ASSERT_INIT(InputWidth_A, LfsrDw >= EntropyDw)
 424:   `ASSERT_INIT(OutputWidth_A, LfsrDw >= StateOutDw)
 425: 
 426:   // MSB must be one in any case
 427:   `ASSERT(CoeffCheck_A, coeffs[LfsrDw-1])
 428: 
 429:   // output check
 430:   `ASSERT_KNOWN(OutputKnown_A, state_o)
 431:   `ASSERT(OutputCheck_A, state_o == StateOutDw'(lfsr_q))
 432: 
 433:   // if no external input changes the lfsr state, a lockup must not occur (by design)
 434:   //`ASSERT(NoLockups_A, (!entropy_i) && (!seed_en_i) |=> !lockup, clk_i, !rst_ni)
 435:   `ASSERT(NoLockups_A, lfsr_en_i && !entropy_i && !seed_en_i |=> !lockup)
 436: 
 437:   // this can be disabled if unused in order to not distort coverage
 438:   if (ExtSeedSVA) begin : gen_ext_seed_sva
 439:     // check that external seed is correctly loaded into the state
 440:     // rst_ni is used directly as part of the pre-condition since the usage of rst_ni
 441:     // in disable_iff is unsampled.  See #1985 for more details
 442:     `ASSERT(ExtDefaultSeedInputCheck_A, (seed_en_i && rst_ni) |=> lfsr_q == $past(seed_i))
 443:   end
 444: 
 445:   // if the external seed mechanism is not used,
 446:   // there is theoretically no way we end up in a lockup condition
 447:   // in order to not distort coverage, this SVA can be disabled in such cases
 448:   if (LockupSVA) begin : gen_lockup_mechanism_sva
 449:     // check that a stuck LFSR is correctly reseeded
 450:     `ASSERT(LfsrLockupCheck_A, lfsr_en_i && lockup && !seed_en_i |=> !lockup)
 451:   end
 452: 
 453:   if (MaxLenSVA) begin : gen_max_len_sva
 454: 
 455: `ifndef SYNTHESIS
 456:     // the code below is a workaround to enable long sequences to be checked.
 457:     // some simulators do not support SVA sequences longer than 2**32-1.
 458:     logic [LfsrDw-1:0] cnt_d, cnt_q;
 459:     logic perturbed_d, perturbed_q;
 460:     logic [LfsrDw-1:0] cmp_val;
 461: 
 462:     assign cmp_val = {{(LfsrDw-1){1'b1}}, 1'b0}; // 2**LfsrDw-2
 463:     assign cnt_d = (lfsr_en_i && lockup)             ? '0           :
 464:                    (lfsr_en_i && (cnt_q == cmp_val)) ? '0           :
 465:                    (lfsr_en_i)                       ? cnt_q + 1'b1 :
 466:                                                        cnt_q;
 467: 
 468:     assign perturbed_d = perturbed_q | (|entropy_i) | seed_en_i;
 469: 
 470:     always_ff @(posedge clk_i or negedge rst_ni) begin : p_max_len
 471:       if (!rst_ni) begin
 472:         cnt_q       <= '0;
 473:         perturbed_q <= 1'b0;
 474:       end else begin
 475:         cnt_q       <= cnt_d;
 476:         perturbed_q <= perturbed_d;
 477:       end
 478:     end
 479: 
 480:     `ASSERT(MaximalLengthCheck0_A, cnt_q == 0 |-> lfsr_q == DefaultSeed,
 481:         clk_i, !rst_ni || perturbed_q)
 482:     `ASSERT(MaximalLengthCheck1_A, cnt_q != 0 |-> lfsr_q != DefaultSeed,
 483:         clk_i, !rst_ni || perturbed_q)
 484: `endif
 485:   end
 486: 
 487: endmodule
 488: