Exact Change, No Exceptions

1 / 1

View past submissions Leaderboard

Back to submissions

Submission #1

PASSED

RankingPercentile

Latency

98.08 (38 cycles)ns

1st

top 1%

Throughput (ranked)

387.45 (100.0%)MHz

1st

top 1%

Throughput (visible)

387.45 (100.0%)MHz

—

top —%

Fmax

387.45MHz

—

top —%

Area

483μm²

1st

top 1%

Score

100.00

1st

top 1%

Throughput is Fmax × the measured percentage. Rankings use hidden tests; visible tests are unranked feedback.

Submitted Solution

// Stream-based solution component
//
// Input stream interface:
//   i_ready (output): Assert when ready to accept input
//   i_valid (input): Asserted when input data is valid
//   i_payload_* (input): Input payload fields
//
// Output interface:
//   o_valid (output): Assert when output data is valid
//   o_payload* (output): Output payload fields
//
// Handshaking: Data transfers when both ready and valid are high

module Solution (
  input wire clk,
  input wire reset,
  output wire i_ready,
  input wire i_valid,
  input wire [3-1:0] i_payload_coins_fragment,
  input wire i_payload_coins_last,
  output wire [1-1:0] o_payload_fragment_1,
  output wire [3-1:0] o_payload_fragment_2,
  output wire o_payload_last,
  output wire o_valid
);

// this problem description was underdefined. it's not clear
// what "last" does.  the machine either keeps the change for
// the next user, keeps the change for itself, or returns the
// change.
// eg:
// +1, +2, +2, +1L.  this ends with 6.  does this get returned?
// stored?  kept?
// 
// for the store/keep cases, an "excess" encoding is nice.
// the accumulator starts at (8-7) = 1.  when 6 is added,
// you'd have 111 in the encoding.  adding 5 will give a value
// of 1100.  the msb is only 1 when the total is 7 or more.
// the remainder is the change in the case a ticket is dispended.
//
// but then the refund case /w last becomes an issue.  this
// would mean and encoding for 5(+1) is 110.  +1L gives 6(+1)
// encoded as 111.  but 111 is not the change.
// 
// to support refunding, we could subtract 1 when 
// (last & !dispense).  this is fine, but it doubles the size
// of the design for this special case.  that's mainly because
// the design started very simple.
//
// there's a lot of variations.  the refunding-on-last is the
// main question.

// Define your design here
localparam REFUND_LAST = 0;
localparam KEEP_LAST = 1;
wire [2:0] change_modifier;
logic [2:0] acc;

wire [3:0] acc_add = {1'b0, acc} + {1'b0, i_payload_coins_fragment};
wire reset_on_last = (REFUND_LAST || KEEP_LAST) && i_payload_coins_last;
  wire dispense = acc_add[3]; // common sub-expression.

generate
if (REFUND_LAST) begin
  assign change_modifier = (acc_add - (!dispense && i_payload_coins_last));
end else begin
  assign change_modifier = acc_add & {(3){dispense}}; // 0 when !dispense.
end
endgenerate

always@(posedge clk) begin
  if (reset) begin
    acc <= 3'b1;
  end else if (i_valid) begin
    if (reset_on_last || dispense) begin
      acc <= 3'b1;
    end else begin
      acc <= acc_add[2:0];
    end
  end
end

assign i_ready = 1'b1;
assign o_payload_fragment_1 = dispense;
assign o_payload_fragment_2 = change_modifier;
assign o_payload_last = i_payload_coins_last;
assign o_valid = i_valid;

endmodule

Generated Verilog

// Stream-based solution component
//
// Input stream interface:
//   i_ready (output): Assert when ready to accept input
//   i_valid (input): Asserted when input data is valid
//   i_payload_* (input): Input payload fields
//
// Output interface:
//   o_valid (output): Assert when output data is valid
//   o_payload* (output): Output payload fields
//
// Handshaking: Data transfers when both ready and valid are high

module Solution (
  input wire clk,
  input wire reset,
  output wire i_ready,
  input wire i_valid,
  input wire [3-1:0] i_payload_coins_fragment,
  input wire i_payload_coins_last,
  output wire [1-1:0] o_payload_fragment_1,
  output wire [3-1:0] o_payload_fragment_2,
  output wire o_payload_last,
  output wire o_valid
);

// this problem description was underdefined. it's not clear
// what "last" does.  the machine either keeps the change for
// the next user, keeps the change for itself, or returns the
// change.
// eg:
// +1, +2, +2, +1L.  this ends with 6.  does this get returned?
// stored?  kept?
// 
// for the store/keep cases, an "excess" encoding is nice.
// the accumulator starts at (8-7) = 1.  when 6 is added,
// you'd have 111 in the encoding.  adding 5 will give a value
// of 1100.  the msb is only 1 when the total is 7 or more.
// the remainder is the change in the case a ticket is dispended.
//
// but then the refund case /w last becomes an issue.  this
// would mean and encoding for 5(+1) is 110.  +1L gives 6(+1)
// encoded as 111.  but 111 is not the change.
// 
// to support refunding, we could subtract 1 when 
// (last & !dispense).  this is fine, but it doubles the size
// of the design for this special case.  that's mainly because
// the design started very simple.
//
// there's a lot of variations.  the refunding-on-last is the
// main question.

// Define your design here
localparam REFUND_LAST = 0;
localparam KEEP_LAST = 1;
wire [2:0] change_modifier;
logic [2:0] acc;

wire [3:0] acc_add = {1'b0, acc} + {1'b0, i_payload_coins_fragment};
wire reset_on_last = (REFUND_LAST || KEEP_LAST) && i_payload_coins_last;
  wire dispense = acc_add[3]; // common sub-expression.

generate
if (REFUND_LAST) begin
  assign change_modifier = (acc_add - (!dispense && i_payload_coins_last));
end else begin
  assign change_modifier = acc_add & {(3){dispense}}; // 0 when !dispense.
end
endgenerate

always@(posedge clk) begin
  if (reset) begin
    acc <= 3'b1;
  end else if (i_valid) begin
    if (reset_on_last || dispense) begin
      acc <= 3'b1;
    end else begin
      acc <= acc_add[2:0];
    end
  end
end

assign i_ready = 1'b1;
assign o_payload_fragment_1 = dispense;
assign o_payload_fragment_2 = change_modifier;
assign o_payload_last = i_payload_coins_last;
assign o_valid = i_valid;

endmodule

Timing Analysis

Path 1-2.583 ns

From: acc[1]$_SDFFE_PP0P_/Q

To: acc[1]$_SDFFE_PP0P_/D

Data Arrival: 2.414 ns

Arrival (ns)	Cell	Pin
0.000	Solution	`clk`
0.000	sky130_fd_sc_hvl__dfxtp_1	`acc[1]$_SDFFE_PP0P_/CLK`
0.715	sky130_fd_sc_hvl__dfxtp_1	`acc[1]$_SDFFE_PP0P_/Q`
0.715	sky130_fd_sc_hvl__xnor2_1	`$abc$191$auto$blifparse.cc:396:parse_blif$199/A`
1.089	sky130_fd_sc_hvl__xnor2_1	`$abc$191$auto$blifparse.cc:396:parse_blif$199/Y`
1.089	sky130_fd_sc_hvl__o21a_1	`$abc$191$auto$blifparse.cc:396:parse_blif$200/A2`
1.502	sky130_fd_sc_hvl__o21a_1	`$abc$191$auto$blifparse.cc:396:parse_blif$200/X`
1.502	sky130_fd_sc_hvl__a21o_1	`$abc$191$auto$blifparse.cc:396:parse_blif$201/A2`
1.878	sky130_fd_sc_hvl__a21o_1	`$abc$191$auto$blifparse.cc:396:parse_blif$201/X`
1.878	sky130_fd_sc_hvl__inv_1	`$abc$191$auto$blifparse.cc:396:parse_blif$202/A`
2.035	sky130_fd_sc_hvl__inv_1	`$abc$191$auto$blifparse.cc:396:parse_blif$202/Y`
2.035	sky130_fd_sc_hvl__nor3_1	`$abc$191$auto$blifparse.cc:396:parse_blif$211/B`
2.155	sky130_fd_sc_hvl__nor3_1	`$abc$191$auto$blifparse.cc:396:parse_blif$211/Y`
2.155	sky130_fd_sc_hvl__o21a_1	`$abc$191$auto$blifparse.cc:396:parse_blif$213/A2`
2.414	sky130_fd_sc_hvl__o21a_1	`$abc$191$auto$blifparse.cc:396:parse_blif$213/X`
2.414	sky130_fd_sc_hvl__dfxtp_1	`acc[1]$_SDFFE_PP0P_/D`

Path 2-2.450 ns

From: acc[1]$_SDFFE_PP0P_/Q

To: acc[0]$_SDFFE_PP1P_/D

Data Arrival: 2.306 ns

Arrival (ns)	Cell	Pin
0.000	Solution	`clk`
0.000	sky130_fd_sc_hvl__dfxtp_1	`acc[1]$_SDFFE_PP0P_/CLK`
0.715	sky130_fd_sc_hvl__dfxtp_1	`acc[1]$_SDFFE_PP0P_/Q`
0.715	sky130_fd_sc_hvl__xnor2_1	`$abc$191$auto$blifparse.cc:396:parse_blif$199/A`
1.089	sky130_fd_sc_hvl__xnor2_1	`$abc$191$auto$blifparse.cc:396:parse_blif$199/Y`
1.089	sky130_fd_sc_hvl__o21a_1	`$abc$191$auto$blifparse.cc:396:parse_blif$200/A2`
1.502	sky130_fd_sc_hvl__o21a_1	`$abc$191$auto$blifparse.cc:396:parse_blif$200/X`
1.502	sky130_fd_sc_hvl__a21o_1	`$abc$191$auto$blifparse.cc:396:parse_blif$201/A2`
1.878	sky130_fd_sc_hvl__a21o_1	`$abc$191$auto$blifparse.cc:396:parse_blif$201/X`
1.878	sky130_fd_sc_hvl__inv_1	`$abc$191$auto$blifparse.cc:396:parse_blif$202/A`
2.035	sky130_fd_sc_hvl__inv_1	`$abc$191$auto$blifparse.cc:396:parse_blif$202/Y`
2.035	sky130_fd_sc_hvl__nor3_1	`$abc$191$auto$blifparse.cc:396:parse_blif$204/B`
2.156	sky130_fd_sc_hvl__nor3_1	`$abc$191$auto$blifparse.cc:396:parse_blif$204/Y`
2.156	sky130_fd_sc_hvl__o21ai_1	`$abc$191$auto$blifparse.cc:396:parse_blif$206/A2`
2.306	sky130_fd_sc_hvl__o21ai_1	`$abc$191$auto$blifparse.cc:396:parse_blif$206/Y`
2.306	sky130_fd_sc_hvl__dfxtp_1	`acc[0]$_SDFFE_PP1P_/D`

Path 3-2.333 ns

From: acc[1]$_SDFFE_PP0P_/Q

To: acc[2]$_SDFFE_PP0P_/D

Data Arrival: 2.147 ns

Arrival (ns)	Cell	Pin
0.000	Solution	`clk`
0.000	sky130_fd_sc_hvl__dfxtp_1	`acc[1]$_SDFFE_PP0P_/CLK`
0.715	sky130_fd_sc_hvl__dfxtp_1	`acc[1]$_SDFFE_PP0P_/Q`
0.715	sky130_fd_sc_hvl__xnor2_1	`$abc$191$auto$blifparse.cc:396:parse_blif$199/A`
1.089	sky130_fd_sc_hvl__xnor2_1	`$abc$191$auto$blifparse.cc:396:parse_blif$199/Y`
1.089	sky130_fd_sc_hvl__o21a_1	`$abc$191$auto$blifparse.cc:396:parse_blif$200/A2`
1.502	sky130_fd_sc_hvl__o21a_1	`$abc$191$auto$blifparse.cc:396:parse_blif$200/X`
1.502	sky130_fd_sc_hvl__a21o_1	`$abc$191$auto$blifparse.cc:396:parse_blif$201/A2`
1.878	sky130_fd_sc_hvl__a21o_1	`$abc$191$auto$blifparse.cc:396:parse_blif$201/X`
1.878	sky130_fd_sc_hvl__nand3_1	`$abc$191$auto$blifparse.cc:396:parse_blif$215/B`
2.012	sky130_fd_sc_hvl__nand3_1	`$abc$191$auto$blifparse.cc:396:parse_blif$215/Y`
2.012	sky130_fd_sc_hvl__a21oi_1	`$abc$191$auto$blifparse.cc:396:parse_blif$217/A2`
2.147	sky130_fd_sc_hvl__a21oi_1	`$abc$191$auto$blifparse.cc:396:parse_blif$217/Y`
2.147	sky130_fd_sc_hvl__dfxtp_1	`acc[2]$_SDFFE_PP0P_/D`

Post-Synthesis Verilog

Download synth.v