src/add/nmigen_add_experiment.py

   1 # IEEE Floating Point Adder (Single Precision)
   2 # Copyright (C) Jonathan P Dawson 2013
   3 # 2013-12-12
   4
   5 from nmigen import Module, Signal, Cat
   6 from nmigen.cli import main
   7
   8
   9 class FPNum:
  10     """ Floating-point Number Class, variable-width TODO (currently 32-bit)
  11
  12         Contains signals for an incoming copy of the value, decoded into
  13         sign / exponent / mantissa.
  14         Also contains encoding functions, creation and recognition of
  15         zero, NaN and inf (all signed)
  16
  17         Four extra bits are included in the mantissa: the top bit
  18         (m[-1]) is effectively a carry-overflow.  The other three are
  19         guard (m[2]), round (m[1]), and sticky (m[0])
  20     """
  21     def __init__(self, width, m_width=None):
  22         self.width = width
  23         if m_width is None:
  24             m_width = width - 5 # mantissa extra bits (top,guard,round)
  25         self.v = Signal(width)      # Latched copy of value
  26         self.m = Signal(m_width)    # Mantissa
  27         self.e = Signal((10, True)) # Exponent: 10 bits, signed
  28         self.s = Signal()           # Sign bit
  29
  30     def decode(self):
  31         """ decodes a latched value into sign / exponent / mantissa
  32
  33             bias is subtracted here, from the exponent.
  34         """
  35         v = self.v
  36         return [self.m.eq(Cat(0, 0, 0, v[0:23])), # mantissa
  37                 self.e.eq(Cat(v[23:31]) - 127),   # exponent (take off bias)
  38                 self.s.eq(Cat(v[31])),            # sign
  39                 ]
  40
  41     def create(self, s, e, m):
  42         """ creates a value from sign / exponent / mantissa
  43
  44             bias is added here, to the exponent
  45         """
  46         return [
  47           self.v[31].eq(s),          # sign
  48           self.v[23:31].eq(e + 127), # exp (add on bias)
  49           self.v[0:23].eq(m)         # mantissa
  50         ]
  51
  52     def shift_down(self):
  53         """ shifts a mantissa down by one. exponent is increased to compensate
  54
  55             accuracy is lost as a result in the mantissa however there are 3
  56             guard bits (the latter of which is the "sticky" bit)
  57         """
  58         return self.create(self.s,
  59                            self.e + 1,
  60                            Cat(self.m[0] | self.m[1], self.m[1:-5], 0))
  61
  62     def nan(self, s):
  63         return self.create(s, 0x80, 1<<22)
  64
  65     def inf(self, s):
  66         return self.create(s, 0x80, 0)
  67
  68     def zero(self, s):
  69         return self.create(s, -127, 0)
  70
  71     def is_nan(self):
  72         return (self.e == 128) & (self.m != 0)
  73
  74     def is_inf(self):
  75         return (self.e == 128) & (self.m == 0)
  76
  77     def is_zero(self):
  78         return (self.e == -127) & (self.m == 0)
  79
  80
  81 class FPADD:
  82     def __init__(self, width):
  83         self.width = width
  84
  85         self.in_a     = Signal(width)
  86         self.in_a_stb = Signal()
  87         self.in_a_ack = Signal()
  88
  89         self.in_b     = Signal(width)
  90         self.in_b_stb = Signal()
  91         self.in_b_ack = Signal()
  92
  93         self.out_z     = Signal(width)
  94         self.out_z_stb = Signal()
  95         self.out_z_ack = Signal()
  96
  97     def get_fragment(self, platform):
  98         m = Module()
  99
 100         # Latches
 101         a = FPNum(self.width)
 102         b = FPNum(self.width)
 103         z = FPNum(self.width, 24)
 104
 105         guard = Signal()
 106         round_bit = Signal()
 107         sticky = Signal()
 108
 109         tot = Signal(28)
 110
 111         with m.FSM() as fsm:
 112
 113             # ******
 114             # gets operand a
 115
 116             with m.State("get_a"):
 117                 with m.If((self.in_a_ack) & (self.in_a_stb)):
 118                     m.next = "get_b"
 119                     m.d.sync += [
 120                         a.v.eq(self.in_a),
 121                         self.in_a_ack.eq(0)
 122                     ]
 123                 with m.Else():
 124                     m.d.sync += self.in_a_ack.eq(1)
 125
 126             # ******
 127             # gets operand b
 128
 129             with m.State("get_b"):
 130                 with m.If((self.in_b_ack) & (self.in_b_stb)):
 131                     m.next = "get_a"
 132                     m.d.sync += [
 133                         b.v.eq(self.in_b),
 134                         self.in_b_ack.eq(0)
 135                     ]
 136                 with m.Else():
 137                     m.d.sync += self.in_b_ack.eq(1)
 138
 139             # ******
 140             # unpacks operands into sign, mantissa and exponent
 141
 142             with m.State("unpack"):
 143                 m.next = "special_cases"
 144                 m.d.sync += a.decode()
 145                 m.d.sync += b.decode()
 146
 147             # ******
 148             # special cases: NaNs, infs, zeros, denormalised
 149
 150             with m.State("special_cases"):
 151
 152                 # if a is NaN or b is NaN return NaN
 153                 with m.If(a.is_nan() | b.is_nan()):
 154                     m.next = "put_z"
 155                     m.d.sync += z.nan(1)
 156
 157                 # if a is inf return inf (or NaN)
 158                 with m.Elif(a.is_inf()):
 159                     m.next = "put_z"
 160                     m.d.sync += z.inf(a.s)
 161                     # if a is inf and signs don't match return NaN
 162                     with m.If((b.e == 128) & (a.s != b.s)):
 163                         m.d.sync += z.nan(b.s)
 164
 165                 # if b is inf return inf
 166                 with m.Elif(b.is_inf()):
 167                     m.next = "put_z"
 168                     m.d.sync += z.inf(b.s)
 169
 170                 # if a is zero and b zero return signed-a/b
 171                 with m.Elif(a.is_zero() & b.is_zero()):
 172                     m.next = "put_z"
 173                     m.d.sync += z.create(a.s & b.s, b.e[0:8], b.m[3:26])
 174
 175                 # if a is zero return b
 176                 with m.Elif(a.is_zero()):
 177                     m.next = "put_z"
 178                     m.d.sync += z.create(b.s, b.e[0:8], b.m[3:26])
 179
 180                 # if b is zero return a
 181                 with m.Elif(b.is_zero()):
 182                     m.next = "put_z"
 183                     m.d.sync += z.create(a.s, a.e[0:8], a.m[3:26])
 184
 185                 # Denormalised Number checks
 186                 with m.Else():
 187                     m.next = "align"
 188                     # denormalise a check
 189                     with m.If(a.e == -127):
 190                         m.d.sync += a.e.eq(-126) # limit a exponent
 191                     with m.Else():
 192                         m.d.sync += a.m[26].eq(1) # set highest mantissa bit
 193                     # denormalise b check
 194                     with m.If(b.e == -127):
 195                         m.d.sync += b.e.eq(-126) # limit b exponent
 196                     with m.Else():
 197                         m.d.sync += b.m[26].eq(1) # set highest mantissa bit
 198
 199             # ******
 200             # align.  NOTE: this does *not* do single-cycle multi-shifting,
 201             #         it *STAYS* in the align state until the exponents match
 202
 203             with m.State("align"):
 204                 # exponent of a greater than b: increment b exp, shift b mant
 205                 with m.If(a.e > b.e):
 206                     m.d.sync += b.shift_down()
 207                 # exponent of b greater than a: increment a exp, shift a mant
 208                 with m.Elif(a.e < b.e):
 209                     m.d.sync += a.shift_down()
 210                 # exponents equal: move to next stage.
 211                 with m.Else():
 212                     m.next = "add_0"
 213
 214             # ******
 215             # First stage of add.  covers same-sign (add) and subtract
 216             # special-casing when mantissas are greater or equal, to
 217             # give greatest accuracy.
 218
 219             with m.State("add_0"):
 220                 m.next = "add_1"
 221                 m.d.sync += z.e.eq(a.e)
 222                 # same-sign (both negative or both positive) add mantissas
 223                 with m.If(a.s == b.s):
 224                     m.d.sync += [
 225                         tot.eq(a.m + b.m),
 226                         z.s.eq(a.s)
 227                     ]
 228                 # a mantissa greater than b, use a
 229                 with m.Elif(a.m >= b.m):
 230                     m.d.sync += [
 231                         tot.eq(a.m - b.m),
 232                         z.s.eq(a.s)
 233                     ]
 234                 # b mantissa greater than a, use b
 235                 with m.Else():
 236                     m.d.sync += [
 237                         tot.eq(b.m - a.m),
 238                         z.s.eq(b.s)
 239                 ]
 240
 241             # ******
 242             # Second stage of add: preparation for normalisation.
 243             # detects when tot sum is too big (tot[27] is kinda a carry bit)
 244
 245             with m.State("add_1"):
 246                 m.next = "normalise_1"
 247                 # tot[27] gets set when the sum overflows. shift result down
 248                 with m.If(tot[27]):
 249                     m.d.sync += [
 250                         z.m.eq(tot[4:28]),
 251                         guard.eq(tot[3]),
 252                         round_bit.eq(tot[2]),
 253                         sticky.eq(tot[1] | tot[0]),
 254                         z.e.eq(z.e + 1)
 255                 ]
 256                 # tot[27] zero case
 257                 with m.Else():
 258                     m.d.sync += [
 259                         z.m.eq(tot[3:27]),
 260                         guard.eq(tot[2]),
 261                         round_bit.eq(tot[1]),
 262                         sticky.eq(tot[0])
 263                 ]
 264
 265             # ******
 266             # First stage of normalisation.
 267             # NOTE: just like "align", this one keeps going round every clock
 268             #       until the result's exponent is within acceptable "range"
 269             # NOTE: the weirdness of reassigning guard and round is due to
 270             #       the extra mantissa bits coming from tot[0..2]
 271
 272             with m.State("normalise_1"):
 273                 with m.If((z.m[23] == 0) & (z.e > -126)):
 274                     m.d.sync +=[
 275                         z.e.eq(z.e - 1),  # DECREASE exponent
 276                         z.m.eq(z.m << 1), # shift mantissa UP
 277                         z.m[0].eq(guard), # steal guard bit (was tot[2])
 278                         guard.eq(round_bit), # steal round_bit (was tot[1])
 279                     ]
 280                 with m.Else():
 281                     m.next = "normalize_2"
 282
 283             # ******
 284             # Second stage of normalisation.
 285             # NOTE: just like "align", this one keeps going round every clock
 286             #       until the result's exponent is within acceptable "range"
 287             # NOTE: the weirdness of reassigning guard and round is due to
 288             #       the extra mantissa bits coming from tot[0..2]
 289
 290             with m.State("normalise_2"):
 291                 with m.If(z.e < -126):
 292                     m.d.sync +=[
 293                         z.e.eq(z.e + 1),  # INCREASE exponent
 294                         z.m.eq(z.m >> 1), # shift mantissa DOWN
 295                         guard.eq(z.m[0]),
 296                         round_bit.eq(guard),
 297                         sticky.eq(sticky | round_bit)
 298                     ]
 299                 with m.Else():
 300                     m.next = "round"
 301
 302             # ******
 303             # rounding stage
 304
 305             with m.State("round"):
 306                 m.next = "pack"
 307                 with m.If(guard & (round_bit | sticky | z.m[0])):
 308                     m.d.sync += z.m.eq(z.m + 1) # mantissa rounds up
 309                     with m.If(z.m == 0xffffff): # all 1s
 310                         m.d.sync += z.e.eq(z.e + 1) # exponent rounds up
 311
 312             # ******
 313             # pack stage
 314             with m.State("pack"):
 315                 m.next = "put_z"
 316                 m.d.sync += [
 317                     z[0:22].eq(z_m[0:22]),
 318                     z[22:31].eq(z_e[0:7]),
 319                     z[31].eq(z_s)
 320             ]
 321                 with m.If(z_e == -126 & z_m[23] == 0):
 322                     m.d.sync += z[23:31].eq(0)
 323                 with m.If(z_e == -126 & z_m[0:23] == x): #how to convert 24'h0 into format understandable by nmigen?
 324                     m.d.sync += z[23:31].eq(0)
 325                 with m.If(z_e > 127):
 326                     m.d.sync += [
 327                         z[0:22].eq(0),
 328                         z[23:31].eq(255),
 329                         z[31].eq(z_s),
 330                 ]
 331             """ TODO: see if z.create can be used *later*.  convert
 332                 verilog first (and commit), *second* phase, convert nmigen
 333                 code to use FPNum.create() (as a separate commit)
 334
 335               pack:
 336               begin
 337                 z[22 : 0] <= z_m[22:0];
 338                 z[30 : 23] <= z_e[7:0] + 127;
 339                 z[31] <= z_s;
 340                 if ($signed(z_e) == -126 && z_m[23] == 0) begin
 341                   z[30 : 23] <= 0;
 342                 end
 343                 if ($signed(z_e) == -126 && z_m[23:0] == 24'h0) begin
 344                   z[31] <= 1'b0; // FIX SIGN BUG: -a + a = +0.
 345                 end
 346                 //if overflow occurs, return inf
 347                 if ($signed(z_e) > 127) begin
 348                   z[22 : 0] <= 0;
 349                   z[30 : 23] <= 255;
 350                   z[31] <= z_s;
 351                 end
 352                 state <= put_z;
 353               end
 354             """
 355
 356             # ******
 357             # put_z stage
 358
 359             """
 360               put_z:
 361               begin
 362                 s_out_z_stb <= 1;
 363                 s_out_z <= z;
 364                 if (s_out_z_stb && out_z_ack) begin
 365                   s_out_z_stb <= 0;
 366                   state <= get_a;
 367                 end
 368               end
 369             """
 370
 371         return m
 372
 373 """
 374   always @(posedge clk)
 375   begin
 376
 377     case(state)
 378
 379       get_a:
 380       begin
 381         s_in_a_ack <= 1;
 382         if (s_in_a_ack && in_a_stb) begin
 383           a <= in_a;
 384           s_in_a_ack <= 0;
 385           state <= get_b;
 386         end
 387       end
 388
 389       get_b:
 390       begin
 391         s_in_b_ack <= 1;
 392         if (s_in_b_ack && in_b_stb) begin
 393           b <= in_b;
 394           s_in_b_ack <= 0;
 395           state <= unpack;
 396         end
 397       end
 398
 399       unpack:
 400       begin
 401         a_m <= {a[22 : 0], 3'd0};
 402         b_m <= {b[22 : 0], 3'd0};
 403         a_e <= a[30 : 23] - 127;
 404         b_e <= b[30 : 23] - 127;
 405         a_s <= a[31];
 406         b_s <= b[31];
 407         state <= special_cases;
 408       end
 409
 410       special_cases:
 411       begin
 412         //if a is NaN or b is NaN return NaN
 413         if ((a_e == 128 && a_m != 0) || (b_e == 128 && b_m != 0)) begin
 414           z[31] <= 1;
 415           z[30:23] <= 255;
 416           z[22] <= 1;
 417           z[21:0] <= 0;
 418           state <= put_z;
 419         //if a is inf return inf
 420         end else if (a_e == 128) begin
 421           z[31] <= a_s;
 422           z[30:23] <= 255;
 423           z[22:0] <= 0;
 424           //if a is inf and signs don't match return nan
 425           if ((b_e == 128) && (a_s != b_s)) begin
 426               z[31] <= b_s;
 427               z[30:23] <= 255;
 428               z[22] <= 1;
 429               z[21:0] <= 0;
 430           end
 431           state <= put_z;
 432         //if b is inf return inf
 433         end else if (b_e == 128) begin
 434           z[31] <= b_s;
 435           z[30:23] <= 255;
 436           z[22:0] <= 0;
 437           state <= put_z;
 438         //if a is zero return b
 439         end else if ((($signed(a_e) == -127) && (a_m == 0)) && (($signed(b_e) == -127) && (b_m == 0))) begin
 440           z[31] <= a_s & b_s;
 441           z[30:23] <= b_e[7:0] + 127;
 442           z[22:0] <= b_m[26:3];
 443           state <= put_z;
 444         //if a is zero return b
 445         end else if (($signed(a_e) == -127) && (a_m == 0)) begin
 446           z[31] <= b_s;
 447           z[30:23] <= b_e[7:0] + 127;
 448           z[22:0] <= b_m[26:3];
 449           state <= put_z;
 450         //if b is zero return a
 451         end else if (($signed(b_e) == -127) && (b_m == 0)) begin
 452           z[31] <= a_s;
 453           z[30:23] <= a_e[7:0] + 127;
 454           z[22:0] <= a_m[26:3];
 455           state <= put_z;
 456         end else begin
 457           //Denormalised Number
 458           if ($signed(a_e) == -127) begin
 459             a_e <= -126;
 460           end else begin
 461             a_m[26] <= 1;
 462           end
 463           //Denormalised Number
 464           if ($signed(b_e) == -127) begin
 465             b_e <= -126;
 466           end else begin
 467             b_m[26] <= 1;
 468           end
 469           state <= align;
 470         end
 471       end
 472
 473       align:
 474       begin
 475         if ($signed(a_e) > $signed(b_e)) begin
 476           b_e <= b_e + 1;
 477           b_m <= b_m >> 1;
 478           b_m[0] <= b_m[0] | b_m[1];
 479         end else if ($signed(a_e) < $signed(b_e)) begin
 480           a_e <= a_e + 1;
 481           a_m <= a_m >> 1;
 482           a_m[0] <= a_m[0] | a_m[1];
 483         end else begin
 484           state <= add_0;
 485         end
 486       end
 487
 488       add_0:
 489       begin
 490         z_e <= a_e;
 491         if (a_s == b_s) begin
 492           tot <= a_m + b_m;
 493           z_s <= a_s;
 494         end else begin
 495           if (a_m >= b_m) begin
 496             tot <= a_m - b_m;
 497             z_s <= a_s;
 498           end else begin
 499             tot <= b_m - a_m;
 500             z_s <= b_s;
 501           end
 502         end
 503         state <= add_1;
 504       end
 505
 506       add_1:
 507       begin
 508         if (tot[27]) begin
 509           z_m <= tot[27:4];
 510           guard <= tot[3];
 511           round_bit <= tot[2];
 512           sticky <= tot[1] | tot[0];
 513           z_e <= z_e + 1;
 514         end else begin
 515           z_m <= tot[26:3];
 516           guard <= tot[2];
 517           round_bit <= tot[1];
 518           sticky <= tot[0];
 519         end
 520         state <= normalise_1;
 521       end
 522
 523       normalise_1:
 524       begin
 525         if (z_m[23] == 0 && $signed(z_e) > -126) begin
 526           z_e <= z_e - 1;
 527           z_m <= z_m << 1;
 528           z_m[0] <= guard;
 529           guard <= round_bit;
 530           round_bit <= 0;
 531         end else begin
 532           state <= normalise_2;
 533         end
 534       end
 535
 536       normalise_2:
 537       begin
 538         if ($signed(z_e) < -126) begin
 539           z_e <= z_e + 1;
 540           z_m <= z_m >> 1;
 541           guard <= z_m[0];
 542           round_bit <= guard;
 543           sticky <= sticky | round_bit;
 544         end else begin
 545           state <= round;
 546         end
 547       end
 548
 549       round:
 550       begin
 551         if (guard && (round_bit | sticky | z_m[0])) begin
 552           z_m <= z_m + 1;
 553           if (z_m == 24'hffffff) begin
 554             z_e <=z_e + 1;
 555           end
 556         end
 557         state <= pack;
 558       end
 559
 560       pack:
 561       begin
 562         z[22 : 0] <= z_m[22:0];
 563         z[30 : 23] <= z_e[7:0] + 127;
 564         z[31] <= z_s;
 565         if ($signed(z_e) == -126 && z_m[23] == 0) begin
 566           z[30 : 23] <= 0;
 567         end
 568         if ($signed(z_e) == -126 && z_m[23:0] == 24'h0) begin
 569           z[31] <= 1'b0; // FIX SIGN BUG: -a + a = +0.
 570         end
 571         //if overflow occurs, return inf
 572         if ($signed(z_e) > 127) begin
 573           z[22 : 0] <= 0;
 574           z[30 : 23] <= 255;
 575           z[31] <= z_s;
 576         end
 577         state <= put_z;
 578       end
 579
 580       put_z:
 581       begin
 582         s_out_z_stb <= 1;
 583         s_out_z <= z;
 584         if (s_out_z_stb && out_z_ack) begin
 585           s_out_z_stb <= 0;
 586           state <= get_a;
 587         end
 588       end
 589
 590     endcase
 591
 592     if (rst == 1) begin
 593       state <= get_a;
 594       s_in_a_ack <= 0;
 595       s_in_b_ack <= 0;
 596       s_out_z_stb <= 0;
 597     end
 598
 599   end
 600   assign in_a_ack = s_in_a_ack;
 601   assign in_b_ack = s_in_b_ack;
 602   assign out_z_stb = s_out_z_stb;
 603   assign out_z = s_out_z;
 604
 605 endmodule
 606 """
 607
 608 if __name__ == "__main__":
 609     alu = FPADD(width=32)
 610     main(alu, ports=[
 611                     alu.in_a, alu.in_a_stb, alu.in_a_ack,
 612                     alu.in_b, alu.in_b_stb, alu.in_b_ack,
 613                     alu.out_z, alu.out_z_stb, alu.out_z_ack,
 614         ])
 615
 616
 617 """
 618 print(verilog.convert(alu, ports=[in_a, in_a_stb, in_a_ack, #doesnt work for some reason
 619                     in_b, in_b_stb, in_b_ack,
 620                     out_z, out_z_stb, out_z_ack]))
 621 """