数字IC校招手撕代码：找序列中的第一个&#39;1&#39;

题目

用Verilog实现，不断寻找序列中的第一个1，并输出其index，当寻找完毕后输出结束信号。（以LSB为例）

分析

常见的寻找数组或序列中第一个‘1’，有以下两种思路：

右移判断最低bit。第一次出现‘1’，记录右移次数，但时间复杂度为O(n)。
二分法。分析低半区数据是否存在‘1’，如果存在，则无需分析高半区数据，即本次对应的索引最高位是‘0’，之后继续二分。

此外，本文将在此基础上设计一个，能够检测数组中多个‘1’的索引，并在检测结束后，触发done信号。
并针对本文设计进行仿真与综合，希望给有类似需求的朋友们更多具体性能参考。

代码

module find_one(

clk,
rst_n,

din_vld,
din,

idx,
idx_vld,
idx_rdy,

done
);

parameter                   DATA_WIDTH      =       8;
localparam                  IDX_LEN         =       log2(DATA_WIDTH);

input                       clk;
input                       rst_n;

input                       din_vld;
input   [DATA_WIDTH-1:0]    din;

output  [IDX_LEN-1:0]       idx;
output                      idx_vld;
input                       idx_rdy;

output                      done;


reg     [DATA_WIDTH-1:0]    data;


wire    [3:0]               tmp0;
wire    [1:0]               tmp1;

wire    [IDX_LEN-1:0]       idx_tmp;
reg     [IDX_LEN-1:0]       idx;

reg                         din_vld_dly;
reg                         idx_vld;

reg                         done;
wire                        done_tmp;
reg                         cal_flag;       //0 indicate not run, 1indicate already run

reg                         idx_rdy_dly;
//===========================================

always @(posedge clk or negedge rst_n)begin
    if(!rst_n)
        data[DATA_WIDTH-1:0] <= {(DATA_WIDTH){1'b0}};
    else if(din_vld)
        data[DATA_WIDTH-1:0] <= din[DATA_WIDTH-1:0];
    else if(idx_rdy & idx_vld)
        data[DATA_WIDTH-1:0] <= data[DATA_WIDTH-1:0] ^ {{(DATA_WIDTH-1){1'b0}},1'b1} << idx[IDX_LEN-1:0];
end


assign idx_tmp[2] = ~(|data[3:0]);
assign tmp0 = idx_tmp[2] ? data[7:4] : data[3:0];

assign idx_tmp[1] = ~(|tmp3[1:0]);
assign tmp1 = idx_tmp[1] ? tmp0[3:2] : tmp0[1:0];

assign idx_tmp[0] = ~tmp1[0];


always @(posedge clk or negedge rst_n)begin
    if(!rst_n)
        cal_flag <= 1'b0;
    else if(done_tmp)
        cal_flag <= 1'b0;
    else if(din_vld)
        cal_flag <= 1'b1;
end


assign done_tmp = cal_flag & (~(|data[DATA_WIDTH-1:0]));

always @(posedge clk or negedge rst_n)begin
    if(!rst_n)
        done <= 1'b0;
    else
        done <= done_tmp;
end

always @(posedge clk or negedge rst_n)begin
    if(!rst_n)
        din_vld_dly <= 1'b0;
    else
        din_vld_dly <= din_vld;
end

always @(posedge clk or negedge rst_n)begin
    if(!rst_n)
        idx_rdy_dly <= 1'b0;
    else
        idx_rdy_dly <= idx_rdy;
end


always @(posedge clk or negedge rst_n)begin
    if(!rst_n)
        idx_vld <= 1'b0;
    else if(done_tmp | idx_rdy)
        idx_vld <= 1'b0;
    else if(din_vld_dly | (idx_rdy_dly & !done))
        idx_vld <= 1'b1;
end

always @(posedge clk or negedge rst_n)begin
    if(!rst_n)
        idx[IDX_LEN-1:0] <= {(IDX_LEN){1'b0}};
    else 
        idx[IDX_LEN-1:0] <= idx_tmp[IDX_LEN-1:0];
end

endmodule

对上述代码进行仿真，输入0x2c，索引为2、3、5存在‘1’，仿真波形与理论一致，共输出三次脉冲，索引分别对应2、3、5。