../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: