ship: CarrySaveAdder

== Ports ===========================================================
in:   in

out:  out

  
== TeX ==============================================================

The Carry-Save Adder computes the carry-save sum of three input
values, provided sequentially at {\tt in}, and produces.


== Fleeterpreter ====================================================

int state = 0;
long temp;
long out;
public void reset() {
  super.reset();
  state = 0;
  temp = 0;
  out = 0;
}
private long maj(long a, long b, long c) {
  long ret = 0;
  for(int i=0; i<64; i++) {
    boolean a_ = (a&(1L<<i))!=0L;
    boolean b_ = (b&(1L<<i))!=0L;
    boolean c_ = (c&(1L<<i))!=0L;
    if ( (a_ && b_) || (b_ && c_) || (a_ && c_) )
      ret |= (1L << i);
  }
  return ret;
}
public void service() {
  if (!box_out.readyForDataFromShip()) return;
  if (state!=3 && !box_in.dataReadyForShip()) return;
  switch(state) {
    case 0: out = box_in.removeDataForShip(); break;
    case 1: temp = box_in.removeDataForShip(); break;
    case 2:
      long in = box_in.removeDataForShip();
      long mm = maj(temp, out, in);
      box_out.addDataFromShip(mm << 1, ((mm >> (getFleet().getWordWidth()-1)) & 1L)!=0);
      temp = (temp ^ out) ^ in;
      break;
    case 3: box_out.addDataFromShip(temp, false); break;
  }
  state = (state+1) % 4;
}


== FPGA ==============================================================

  reg [(`WORDWIDTH-1):0] temp;
  reg [(`WORDWIDTH):0]   out_d;
  reg [1:0] state;
  initial state = 0;
  assign out_d_ = out_d;

  wire [(`WORDWIDTH-1):0] majority;
  wire [(`WORDWIDTH-1):0] xors;
  genvar i;
  generate
    for(i=0; i<`WORDWIDTH; i=i+1) begin : OUT
      assign majority[i] = (temp[i] & out_d[i]) | (in_d[i] & out_d[i]) | (temp[i] & in_d[i]);
      assign xors[i]     = temp[i] ^ out_d[i] ^ in_d[i];
    end
  endgenerate

  always @(posedge clk) begin
    if (rst) begin
      `reset
      state <= 0;
    end else begin
      `cleanup
      if (`out_empty && state==3) begin
        out_d <= { 1'b0, temp };
        `fill_out
        state <= state + 1;
      end else if (`in_full && `out_empty) begin
        if (state == 0) begin
          out_d <= { 1'b0, in_d };
        end else if (state == 1) begin
          temp <= in_d;
        end else if (state == 2) begin
          out_d <= { majority[`WORDWIDTH-1:0], 1'b0 };
          temp  <= xors;
          `fill_out
        end
        state <= state + 1;
        `drain_in
      end
    end
  end

== Test ==============================================================
// expected output
#expect 0x3c4bc6
#expect 0x1796d2
#expect 0x24b4f4
#expect 0x3c4bc6

// ships required in order to run this code
#ship debug        : Debug
#ship csa          : CarrySaveAdder
#ship alu          : Alu
#ship fifo         : Fifo

fifo.in:
   set word=1018217;  deliver;
   set word=771820;   deliver;
   set word=2161521;  deliver;
fifo.out:
   collect, send to csa.in; send to alu.in1;
   collect, send to csa.in; send to alu.in2;
   collect, send to csa.in; send to alu.in2;

alu.in1: set ilc=4; recv, deliver;
alu.in2: set ilc=4; recv, deliver;
alu.inOp:
   set word=Alu.inOp[ADD];
   set ilc=4; deliver;   
alu.out:
   collect, send to alu.in1;
   collect; send to debug.in;
   recv token;
   collect; send to debug.in;

csa.in:
   set ilc=*;
   recv, deliver;

csa.out:
   recv token;
   collect, send to debug.in;
   send to alu.in1;
   collect, send to debug.in;
   send to alu.in2;

debug.in:
   recv, deliver;
   send token to csa.out;
   set ilc=2;
   recv, deliver;
   send token to alu.out;
   recv, deliver;


== Contributors =========================================================
Adam Megacz <megacz@cs.berkeley.edu>