misoclib/com/liteusb/core/crc.py

   1 from collections import OrderedDict
   2 from migen.fhdl.std import *
   3 from migen.genlib.fsm import FSM, NextState
   4 from migen.genlib.record import *
   5 from migen.genlib.misc import chooser, optree
   6 from migen.flow.actor import Sink, Source
   7 from migen.actorlib.fifo import SyncFIFO
   8
   9 from misoclib.com.liteusb.common import *
  10
  11
  12 class CRCEngine(Module):
  13     """Cyclic Redundancy Check Engine
  14
  15     Compute next CRC value from last CRC value and data input using
  16     an optimized asynchronous LFSR.
  17
  18     Parameters
  19     ----------
  20     dat_width : int
  21         Width of the data bus.
  22     width : int
  23         Width of the CRC.
  24     polynom : int
  25         Polynom of the CRC (ex: 0x04C11DB7 for IEEE 802.3 CRC)
  26
  27     Attributes
  28     ----------
  29     d : in
  30         Data input.
  31     last : in
  32         last CRC value.
  33     next :
  34         next CRC value.
  35     """
  36     def __init__(self, dat_width, width, polynom):
  37         self.data = Signal(dat_width)
  38         self.last = Signal(width)
  39         self.next = Signal(width)
  40
  41         # # #
  42
  43         def _optimize_eq(l):
  44             """
  45             Replace even numbers of XORs in the equation
  46             with an equivalent XOR
  47             """
  48             d = OrderedDict()
  49             for e in l:
  50                 if e in d:
  51                     d[e] += 1
  52                 else:
  53                     d[e] = 1
  54             r = []
  55             for key, value in d.items():
  56                 if value%2 != 0:
  57                     r.append(key)
  58             return r
  59
  60         # compute and optimize CRC's LFSR
  61         curval = [[("state", i)] for i in range(width)]
  62         for i in range(dat_width):
  63             feedback = curval.pop() + [("din", i)]
  64             for j in range(width-1):
  65                 if (polynom & (1<<(j+1))):
  66                     curval[j] += feedback
  67                 curval[j] = _optimize_eq(curval[j])
  68             curval.insert(0, feedback)
  69
  70         # implement logic
  71         for i in range(width):
  72             xors = []
  73             for t, n in curval[i]:
  74                 if t == "state":
  75                     xors += [self.last[n]]
  76                 elif t == "din":
  77                     xors += [self.data[n]]
  78             self.comb += self.next[i].eq(optree("^", xors))
  79
  80
  81 @DecorateModule(InsertReset)
  82 @DecorateModule(InsertCE)
  83 class CRC32(Module):
  84     """IEEE 802.3 CRC
  85
  86     Implement an IEEE 802.3 CRC generator/checker.
  87
  88     Parameters
  89     ----------
  90     dat_width : int
  91         Width of the data bus.
  92
  93     Attributes
  94     ----------
  95     d : in
  96         Data input.
  97     value : out
  98         CRC value (used for generator).
  99     error : out
 100         CRC error (used for checker).
 101     """
 102     width = 32
 103     polynom = 0x04C11DB7
 104     init = 2**width-1
 105     check = 0xC704DD7B
 106
 107     def __init__(self, dat_width):
 108         self.data = Signal(dat_width)
 109         self.value = Signal(self.width)
 110         self.error = Signal()
 111
 112         # # #
 113
 114         self.submodules.engine = CRCEngine(dat_width, self.width, self.polynom)
 115         reg = Signal(self.width, reset=self.init)
 116         self.sync += reg.eq(self.engine.next)
 117         self.comb += [
 118             self.engine.data.eq(self.data),
 119             self.engine.last.eq(reg),
 120
 121             self.value.eq(~reg[::-1]),
 122             self.error.eq(self.engine.next != self.check)
 123         ]
 124
 125
 126 class CRCInserter(Module):
 127     """CRC Inserter
 128
 129     Append a CRC at the end of each packet.
 130
 131     Parameters
 132     ----------
 133     layout : layout
 134         Layout of the dataflow.
 135
 136     Attributes
 137     ----------
 138     sink : in
 139         Packets input without CRC.
 140     source : out
 141         Packets output with CRC.
 142     """
 143     def __init__(self, crc_class, layout):
 144         self.sink = sink = Sink(layout)
 145         self.source = source = Source(layout)
 146         self.busy = Signal()
 147
 148         # # #
 149
 150         dw = flen(sink.data)
 151         crc = crc_class(dw)
 152         fsm = FSM(reset_state="IDLE")
 153         self.submodules += crc, fsm
 154
 155         fsm.act("IDLE",
 156             crc.reset.eq(1),
 157             sink.ack.eq(1),
 158             If(sink.stb & sink.sop,
 159                 sink.ack.eq(0),
 160                 NextState("COPY"),
 161             )
 162         )
 163         fsm.act("COPY",
 164             crc.ce.eq(sink.stb & source.ack),
 165             crc.data.eq(sink.data),
 166             Record.connect(sink, source),
 167             source.eop.eq(0),
 168             If(sink.stb & sink.eop & source.ack,
 169                 NextState("INSERT"),
 170             )
 171         )
 172         ratio = crc.width//dw
 173         if ratio > 1:
 174             cnt = Signal(max=ratio, reset=ratio-1)
 175             cnt_done = Signal()
 176             fsm.act("INSERT",
 177                 source.stb.eq(1),
 178                 chooser(crc.value, cnt, source.data, reverse=True),
 179                 If(cnt_done,
 180                     source.eop.eq(1),
 181                     If(source.ack, NextState("IDLE"))
 182                 )
 183             )
 184             self.comb += cnt_done.eq(cnt == 0)
 185             self.sync += \
 186                 If(fsm.ongoing("IDLE"),
 187                     cnt.eq(cnt.reset)
 188                 ).Elif(fsm.ongoing("INSERT") & ~cnt_done,
 189                     cnt.eq(cnt - source.ack)
 190                 )
 191         else:
 192             fsm.act("INSERT",
 193                 source.stb.eq(1),
 194                 source.eop.eq(1),
 195                 source.data.eq(crc.value),
 196                 If(source.ack, NextState("IDLE"))
 197             )
 198         self.comb += self.busy.eq(~fsm.ongoing("IDLE"))
 199
 200
 201 class LiteUSBCRC32Inserter(CRCInserter):
 202     def __init__(self):
 203         CRCInserter.__init__(self, CRC32, user_description(8))
 204
 205
 206 class CRCChecker(Module):
 207     """CRC Checker
 208
 209     Check CRC at the end of each packet.
 210
 211     Parameters
 212     ----------
 213     layout : layout
 214         Layout of the dataflow.
 215
 216     Attributes
 217     ----------
 218     sink : in
 219         Packets input with CRC.
 220     source : out
 221         Packets output without CRC and "error" set to 0
 222         on eop when CRC OK / set to 1 when CRC KO.
 223     """
 224     def __init__(self, crc_class, layout):
 225         self.sink = sink = Sink(layout)
 226         self.source = source = Source(layout)
 227         self.busy = Signal()
 228
 229         # # #
 230
 231         dw = flen(sink.data)
 232         crc = crc_class(dw)
 233         self.submodules += crc
 234         ratio = crc.width//dw
 235
 236         error = Signal()
 237         fifo = InsertReset(SyncFIFO(layout, ratio + 1))
 238         self.submodules += fifo
 239
 240         fsm = FSM(reset_state="RESET")
 241         self.submodules += fsm
 242
 243         fifo_in = Signal()
 244         fifo_out = Signal()
 245         fifo_full = Signal()
 246
 247         self.comb += [
 248             fifo_full.eq(fifo.fifo.level == ratio),
 249             fifo_in.eq(sink.stb & (~fifo_full | fifo_out)),
 250             fifo_out.eq(source.stb & source.ack),
 251
 252             Record.connect(sink, fifo.sink),
 253             fifo.sink.stb.eq(fifo_in),
 254             self.sink.ack.eq(fifo_in),
 255
 256             source.stb.eq(sink.stb & fifo_full),
 257             source.sop.eq(fifo.source.sop),
 258             source.eop.eq(sink.eop),
 259             fifo.source.ack.eq(fifo_out),
 260             source.payload.eq(fifo.source.payload),
 261
 262             source.error.eq(sink.error | crc.error),
 263         ]
 264
 265         fsm.act("RESET",
 266             crc.reset.eq(1),
 267             fifo.reset.eq(1),
 268             NextState("IDLE"),
 269         )
 270         fsm.act("IDLE",
 271             crc.data.eq(sink.data),
 272             If(sink.stb & sink.sop & sink.ack,
 273                 crc.ce.eq(1),
 274                 NextState("COPY")
 275             )
 276         )
 277         fsm.act("COPY",
 278             crc.data.eq(sink.data),
 279             If(sink.stb & sink.ack,
 280                 crc.ce.eq(1),
 281                 If(sink.eop,
 282                     NextState("RESET")
 283                 )
 284             )
 285         )
 286         self.comb += self.busy.eq(~fsm.ongoing("IDLE"))
 287
 288
 289 class LiteUSBCRC32Checker(CRCChecker):
 290     def __init__(self):
 291         CRCChecker.__init__(self, CRC32, user_description(8))