celebrating fall with fletcher’s checksum
To break up the bustle of preparing for my third FPGA tapeout, working on final projects for classes, and firing off job applications, I spent some time during fall break revisiting an unfinished project from a few summers ago. A SystemVerilog implementation of Fletcher’s checksum, which came as an off-shoot of my research toward some bitstream verification logic done for the QuickLogic Corporation, that I would eventually like to submit to TinyTapeout.
why are checksums useful for fpga development?
Checksum functions are useful for error detection and data integrity. With respect to FPGA architecture development, a checksum can ensure the system is able to retain its state. For example, an FPGA programmed to behave like an AND gate should not start to act like an OR gate due fluctuations in voltage or temperature. Such problems may be caught by computing the checksum of the bitstream before configuring the FPGA, operating the device in the lab, and then extracting the bitstream and re-computing the checksum to ensure it has not changed.
The last two FPGAs that I worked on-with Indiana University’s SAIL-IN Lab and the QuickLogic Corporation-used a scan chain configuration interface which lent itself well to bitstream verification via checksum. The scan chain acts like a serial shift register, stringing together all the configuration chain flip-flops in the FPGA fabric. As the bitstream flows through the head of the scan chain, one bit at a time, its checksum may be computed; and later re-computed as it flows out of the tail. For context, imagine a small, thirty-two flop scan chain and the corresponding bitstream, 0xdeadbeef. On the way in, the Fletcher’s (32-bit) checksum will be 0xf13b. If the post-configuration checksum does not match, the engineers would know that there is an issue with the FPGA architecture.
Fletcher’s checksum also produces check bytes (or a “tag”), which can be appended to the end of the original data, such that the new checksum of the data and the check bytes is zero. For the example bitstream 0xdeadbeef, the resulting check bytes are 0xd2f1. And the checksum of 0xdeadbeefd2f1 is 0x0.
fletcher’s checksum in systemverilog
Based mostly on the Wikipedia entry for Fletcher’s checksum, I produced a parameterized, three-state module which computes the checksum and check bytes of a data stream. The SystemVerilog closesly follows the below psuedo-code. For the Fletcher-32 checksum, data arrives as 16-bit half-words.
#define MODULO (2^(16) - 1)
int32 fletcher_N(int16 *data, int count) {
int16 sum1 = 0;
int16 sum2 = 0;
for (int i = 0; i < count; i++) {
sum1 = (sum1 + data[index]) % MODULO;
sum2 = (sum2 + sum1) % MODULO;
}
return (sum2 << Nby2) | sum1;
}
int32 check_bytes(int_N checksum) {
int16 f0 = checksum & MODULO;
int16 f1 = (checksum >> 16) & MODULO;
int16 c0 = MODULO - ((f0 + f1) % MODULO;
int16 c1 = MODULO - ((f0 + c0) % MODULO;
return (c0 << 16) | c1;
}
Eventually, I’d like to wrap it in a SPI interface and submit it to TinyTapeout, but for now here’s the bare RTL. The most up-to-date code is also available on GitHub:
// Description: Parameterized implementation of Fletcher's checksum
//
// Operation: After asserting reset, place bytes on data_i on each rising edge
// of the clock. On the last byte in the stream, also assert done_i. On the
// next positive edge of the clock, the checksum and check bytes will appear on
// their respective output ports
//
// Author: Joseph Bellahcen <[email protected]>
// Reference: https://en.wikipedia.org/wiki/Fletcher%27s_checksum
`timescale 1ns / 1ps
module fletcher #(
parameter integer CHECKSUM_WIDTH = 32,
parameter integer DATA_WIDTH = CHECKSUM_WIDTH / 2,
parameter integer MODULO = $pow(2, DATA_WIDTH) - 1
) (
// FPGA Interface
input logic clock_i,
input logic reset_i,
// Module Input/Control
input logic done_i,
input logic [DATA_WIDTH-1:0] data_i,
// Module Output
output logic [CHECKSUM_WIDTH-1:0] check_sum_o,
output logic [CHECKSUM_WIDTH-1:0] check_bytes_o
);
////////////////////////////////////////////////////////////////////////////
// FSM Variables
////////////////////////////////////////////////////////////////////////////
enum {
RESET_S,
CHECKSUM_S,
CHECKBYTES_S
}
state, state_ns;
logic [DATA_WIDTH-1:0] lower_sum, lower_sum_ns;
logic [DATA_WIDTH-1:0] upper_sum, upper_sum_ns;
////////////////////////////////////////////////////////////////////////////
// Combinational Logic
////////////////////////////////////////////////////////////////////////////
wire [DATA_WIDTH-1:0] c0, c1;
// The check bytes, which when appended to the original data will produce a
// checksum of zero, can be computed combinatorially from the checksum
assign c0 = MODULO - ((lower_sum + upper_sum) % MODULO);
assign c1 = MODULO - ((lower_sum + c0) % MODULO);
////////////////////////////////////////////////////////////////////////////
// FSM
////////////////////////////////////////////////////////////////////////////
always_ff @(posedge clock_i) begin
if (reset_i) begin
state <= RESET_S;
lower_sum <= 0;
upper_sum <= 0;
end else begin
state <= state_ns;
lower_sum <= lower_sum_ns;
upper_sum <= upper_sum_ns;
end
end
always_comb begin
// FSM Defaults
state_ns = state;
lower_sum_ns = lower_sum;
upper_sum_ns = upper_sum;
case (state)
// Asserting reset is the only way to re-start the checksum
RESET_S: begin
lower_sum_ns = 0;
upper_sum_ns = 0;
check_sum_o = 0;
check_bytes_o = 0;
state_ns = CHECKSUM_S;
end
CHECKSUM_S: begin
lower_sum_ns = (lower_sum + data_i) % MODULO;
upper_sum_ns = (upper_sum + lower_sum_ns) % MODULO;
if (done_i === 1) begin
state_ns = CHECKBYTES_S;
end
end
// De-asserting done will NOT reset the checksum
CHECKBYTES_S: begin
check_sum_o = {upper_sum, lower_sum};
check_bytes_o = {c0, c1};
if (done_i === 0) begin
state_ns = CHECKSUM_S;
end
end
endcase
end
endmodule : fletcher