cppRange 多维范围计算库

范围计算是电路综合中的一个常见问题。在计算一个多比特信号是否被完全赋值,或者是否存在多驱动的时候,都需要计算该信号的范围。比如说一个信号(sig)有8比特(Verilog HDL):

wire [7:0] sig;
assign sig[3:0] = 4'd5;
assign sig[6:3] = 4'd3;

对于sig的两次赋值就造成了对sig[3]的多驱(两个assign同时对其赋值)。同时,sig[7]没有驱动。

为了检查没有驱动的情况,可以判断[7:0] 是否等于 [3:0] 和 [6:3]的并集([3:0] | [6:3])。检查多驱,则可查看[3:0]和[6:3]的交集是否为空([3:0] & [6:3])。这似乎很简单。但是一旦信号的范围支持多维,就复杂很多。比如下面的例子:

wire [7:0][3:0] multi_sig;
assign multi_sig[0] = 4'd9;
assign multi_sig[7:2] = 24'd96;
assign multi_sig[1][2:0] = 3'd7;
assign multi_sig[4][0]=1'b1;

multi_sig[4][0]被驱动了两次,而multi_sig[1][3]没有驱动。为了判断驱动,需要计算 [0] | [7:2] | [1][2:0] | [4][0]。这种一维和两维的混合是非常难计算的。将信号的声明考虑在内,则可以规范化范围计算,从而计算 [0][3:0] | [7:2][3:0] | [1:1][2:0] | [4:4][0:0]。可是,这仍然是一个难题,比如说如何表示 [1:1][2:0] | [4:4][0:0]?

这种问题在硬件综合之外的其他环境中也可能出现,但是到现在好像还没有一个很好的解决方按,更别说开源库。

所以我自己写了一个简单的多维范围计算库(C++)[https://github.com/wsong83/cppRange]

这个库可以用来计算一维或多维范围表达式。现在支持功能如下:

========
一个范围可以表示为:

1比特:            [3:3] or [3]
一维:             [3:0]
多维:             [5:0][2:-1]

* 范围默认为[上边界:下边界]。如果上边界<下边界,该范围非法。
* 该库使用STL支持任何可以比较和加减的数据类型。支持负数范围。

========
支持的计算:

包含 (>)
    [7:0] > [3:2]                               真
    [7:0][4:0][3:-2] > [1:0][3][1:0]            真
    [5:3][2:0] > [5:1][2:0]                     假
    [5:3][2:0] > [5:1]                          假 (非法计算)
* 相判断的两个多维范围必须有相同的维数,否则非法。

其他支持的比较 >=, <, <=, ==, !=

并集运算 (|)
    [7:3] | [4:0]                            -> [7:0]
    [5:4] | [1:0]                            -> []              // 空 (无法求值)
    [4:0][3:1] | [4:0][5:2]                  -> [4:0][5:1]
    [1:0][5:1] | [4:2][5:1]                  -> [4:0][5:1]
    [1:0][3:1] | [4:0][5:2]                  -> []              // 空 (非法运算)
    [1:0][3:1] | [4:0]                       -> []              // 空 (非法运算)
* 合并两个多维范围时,只能有一个纬度上的范围不等,同时该不等范围相邻才可计算。
交集运算 (&)
    [7:3] & [4:0]                            -> [4:3]
    [5:4] & [1:0]                            -> []
    [4:0][3:1] & [4:0][5:2]                  -> [4:0][3:2]
    [2:0][5:1] & [4:2][5:1]                  -> [2:2][5:1]
    [1:0][3:1] & [4:0][5:2]                  -> [1:0][3:2]
    [1:0][3:1] & [4:0]                       -> []
* 求取两个多维范围的交集时,两个范围必须有相同的维度。

去除 (-)
    [7:3] - [4:0]                            -> [7:5]
    [5:4] - [1:0]                            -> [5:4]
    [4:0][3:1] - [4:0][5:2]                  -> [4:0][1]
    [2:0][5:1] - [4:2][5:1]                  -> [1:0][5:1]
    [1:0][3:1] - [4:0][5:2]                  -> []
    [1:0][3:1] - [4:0]                       -> []
* 多维范围运算时,只能有一个维度上的范围不等。 

标准分割 (^)
    [7:3] ^ [4:0]                            -> [7:5],[4:3],[2:0]
    [5:4] ^ [1:0]                            -> []
    [4:0][3:1] ^ [4:0][5:2]                  -> [4:0][5:4],[4:0][3:2],[4:0][1:1]
    [2:0][5:1] ^ [4:2][5:1]                  -> [4:2][5:1],[2:2][5:1],[1:0][5:1]
    [1:0][3:1] ^ [4:0][5:2]                  -> []
    [1:0][3:1] ^ [4:0]                       -> []
* A ^ B = {High, A&B, Low}
* 多维范围运算时,只能有一个维度上的范围不等。同时范围相邻才可计算。

详细的使用则只能查看具体的代码了。

我计划在不久的将来扩展该库的运算,让其支持多维运算时多个维度上的不等范围。不过该计算的计算复杂度和时间则会大幅增长。

Advertisements