前幾天參加樂鑫的筆試,遇到一道題目,很有價值,分享給大家。
題目要求是
將一個序列執行的C語言演算法轉化為單拍完成的並行可綜合verilog。
C語言原始碼如下:
unsigned char cal_table_high_first(unsigned char value)
{
unsigned char i ;
unsigned char checksum = value ;
for (i=8;i>0;——i)
{
if (check_sum & 0x80)
{
check_sum = (check_sum<<1) ^ 0x31;
}
else
{
check_sum = (check_sum << 1);
}
}
return check_sum;
}
演算法C語言實現:
#include
int main() {
unsigned char cal_table_high_first(unsigned char value);
unsigned char data;
for (unsigned char i = 0; i < 16; ++i)
{
data = cal_table_high_first(i);
printf(“value =0x%0x:check_sum =0x%0x \n”, i, data);
}
getchar();
}
unsigned char cal_table_high_first(unsigned char value)
{
unsigned char i;
unsigned char check_sum = value;
for (i = 8; i > 0; ——i)
{
if (check_sum & 0x80)
{
check_sum = (check_sum << 1) ^ 0x31;
}
else
{
check_sum = (check_sum << 1);
}
}
return check_sum;
}
輸出結果:
value =0x0:check_sum =0x0
value =0x1:check_sum =0x31
value =0x2:check_sum =0x62
value =0x3:check_sum =0x53
value =0x4:check_sum =0xc4
value =0x5:check_sum =0xf5
value =0x6:check_sum =0xa6
value =0x7:check_sum =0x97
value =0x8:check_sum =0xb9
value =0x9:check_sum =0x88
value =0xa:check_sum =0xdb
value =0xb:check_sum =0xea
value =0xc:check_sum =0x7d
value =0xd:check_sum =0x4c
value =0xe:check_sum =0x1f
value =0xf:check_sum =0x2e
C語言作為參考模型,用於後續Verilog的功能模擬。
該演算法邏輯如下,輸入一個8bit的數,首先判斷最高位是否為1,如果為1則左移一位,並且和8‘b00110001異或;如果最高位不為1則左移一位。此過程執行8次。
此時我們來看一下異或操作的真值表
我們可以看出:任何數與0異或都等於它本身,即0^x=x。所以我們可以把演算法流程變換為:
‘h31 = ’b00110001, ’h00 = ’b00000000,設左移前最高位為M,可以將判斷左移前最高位是否為1的過程省略,直接與 ‘b00MM000M異或,此時流程圖可以簡化為:
由此,我們可以將迴圈解開。
根據上述結果,可以用verilog描述。
module loop1(
input clk,
input rst_n,
input [7:0] check_sum,
output reg [7:0] check_sum_o
);
//reg [7:0] check_sum_o;
always @ (posedge clk or negedge rst_n)
if (!rst_n)
begin
check_sum_o <= 8‘h0;
end
else
begin
check_sum_o[7] <= check_sum[3]^check_sum[2]^check_sum[5];
check_sum_o[6] <= check_sum[2]^check_sum[1]^check_sum[4]^check_sum[7];
check_sum_o[5] <= check_sum[1]^check_sum[7]^check_sum[0]^check_sum[3]^check_sum[6];
check_sum_o[4] <= check_sum[7]^check_sum[0]^check_sum[3]^check_sum[6];
check_sum_o[3] <= check_sum[3]^check_sum[7]^check_sum[6];
check_sum_o[2] <= check_sum[2]^check_sum[6]^check_sum[5];
check_sum_o[1] <= check_sum[1]^check_sum[5]^check_sum[4]^check_sum[7];
check_sum_o[0] <= check_sum[0]^check_sum[4]^check_sum[3]^check_sum[6];
end
endmodule
testbench:
module loop1_tb;
reg clk;
reg rst_n;
reg [7:0] check_sum;
wire [7:0] check_sum_o;
always #1 clk=~clk;
initial
begin
clk = 0;
rst_n = 0;
#10
rst_n = 1;
for (check_sum=0;check_sum<16;check_sum=check_sum+1)
begin
#2
//check_sum = i;
$display (“check_sum = %h”, check_sum_o);
if (check_sum == 15) $stop;
end
//$stop;
end
loop1 loop1_i1(
。clk(clk),
。rst_n(rst_n),
。check_sum(check_sum),
。check_sum_o(check_sum_o)
);
endmodule
列印結果為:
# check_sum = 00
# check_sum = 31
# check_sum = 62
# check_sum = 53
# check_sum = c4
# check_sum = f5
# check_sum = a6
# check_sum = 97
# check_sum = b9
# check_sum = 88
# check_sum = db
# check_sum = ea
# check_sum = 7d
# check_sum = 4c
# check_sum = 1f
# check_sum = 2e
loop2.v的實現和loop1.v類似,只是程式碼量更少。
module loop2(
input clk,
input rst_n,
input [7:0] check_sum,
output reg [7:0] check_sum_o
);
integer i;
//reg [7:0] check_sum_o;
reg [7:0] ccc;
always @ (posedge clk or negedge rst_n)
if (!rst_n)
begin
check_sum_o = 8’h0;
end
else
begin
ccc = check_sum;
for(i=0;i<8;i=i+1)
begin
ccc = {ccc[6:0],1‘b0}^({8{ccc[7]}} & 8’h31);
end
check_sum_o = ccc;
end
endmodule
其實也可以將C語言函式封裝成Verilog的function,然後在在單週期內進行賦值。
module loop3(
input clk,
input rst_n,
input [7:0] check_sum,
output reg [7:0] check_sum_o
);
integer i;
function [7:0] cal_table_high_first;
input [7:0] value;
reg [7:0] ccc ;
reg [7:0] flag ;
begin
ccc = value;
for(i=0;i<8;i=i+1)
begin
flag = ccc & 8‘h80 ;
if(flag != 0 ) ccc = (ccc <<1) ^ 8’h31 ;
else ccc = (ccc <<1) ;
end
cal_table_high_first = ccc;
end
endfunction
always @ (posedge clk or negedge rst_n)
if (!rst_n)
begin
check_sum_o = 8‘h0;
end
else
begin
check_sum_o <= cal_table_high_first(check_sum) ;
end
endmodule
綜上,loop1.v和loop2.v的主要貢獻是解開了演算法實現的if-else判斷。至於loop3.v中將C語言描述的功能封裝成fucntion,直接單週期完成賦值的實現方式在邏輯綜合後是否增加了硬體開銷不在本文討論範圍內
。這和設計者施加的時序約束和綜合工具演算法有關。