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