C++库支持三值逻辑:0、1、X

6
我正在编写一个用C++编写的微处理器模拟器。
我正在寻找一种方法来模拟硬件中刚刚上电并且尚未被任何方式重置的状态元素。实际的状态元素具有未知值,可能为0或1,但在软件模型中,通常将其建模为“X”,表示未知。
我正在寻找一个能够模拟这些“X”值及其传播的C ++库。也就是说,它必须知道如何处理逻辑和算术运算与“X”:
1 AND X = X
0 AND X = 0
1  +  X = X

有没有既稳定又快速的库可以使用?

编辑:

我忽略了提到我目前的代码使用位向量。更准确地说,我使用标准的uint_*t数据类型,并且这些是我想要替换的类型。无论使用什么库,它都必须支持算术、移位和逻辑运算才能发挥作用。


只是出于好奇,使用哪种微控制器? - S.C. Madsen
@S.C. 下一代英特尔酷睿处理器 - Nathan Fellman
4个回答

12

试试使用 Boost.Tribool

tribool 类型像内置的 bool 类型一样,但用于三态布尔逻辑。这三种状态分别是 truefalseindeterminate,其中前两个状态等同于 C++ bool 类型,而最后一个状态表示未知的布尔值(可能为 truefalse,我们不知道)。

您可以查看测试集头文件文档了解此类支持的规则。

Boost 库具有相当高的质量和良好的维护性,因此您不必担心其稳定性。而“快速”... 对于像这样简单的类来说,要变得慢很难 :)。操作使用 2 到 3 个整数比较和 1 或 2 个 if 语句实现,因此应该足够高效。


这看起来不错,但似乎仅支持位级操作。你知道它是否也支持位向量吗? - Nathan Fellman
@Nathan:您可以使用 std::vector/boost::array 存储 tribool,然后使用 std::transform 函数将两个向量/数组(进行 &|^)逐个组合。 - kennytm

7
如果您试图建模硬件线路,则可能希望考虑允许超过三个状态。以下是Altera在其FPGA模拟器中使用的内容:
1: 强高(晶体管驱动到VDD) 0: 强低(晶体管驱动到VSS) H: 弱高(电阻上拉到VDD) L: 弱低(电阻下拉到VSS) Z: 高阻(未驱动的线路) X: 未知 W: 弱未知 U: 未初始化 DC: 不关心
如果总线始终被驱动,您可能不需要W、U和DC。 Verilog在门级建模中使用更多级别,并为每个逻辑电平提供7个驱动强度。额外的级别模拟信号线上的电容效应。这可能比您所需的要多。

编辑: 既然你提到了位向量,我必须说,在公共使用并保持最新状态的库中,你不太可能找到这样一个库,因为1)需要这样东西的程序员并不是很多,2)即使在他们中间,由于前面提到的建模线路电平的选项,兼容性很小。Boost的tribool可以被用来解决问题,但它们不会很快,因为操作将逐个元素进行,存储也不会被优化,但如果有人对编写一个完全符合您需求的内部库过敏,它们可能是您唯一的选择。

例如,假设你想要一个表示具有四个可能级别的位向量的类:1、0、X和Z。首先,你必须为每个级别定义等效的位模式(例如,X=00,Z=01,0=10,1=11;X被选为复位状态)

对于每个操作,你必须编写真值表,最好以Karnaugh Map形式呈现:

op: &  | X (00) | Z (01) | 1 (11) | 0 (10)
-------+--------+--------+--------+--------
X (00) | X (00) | X (00) | X (00) | X (00)
-------+--------+--------+--------+--------
Z (01) | X (00) | X (00) | X (00) | X (00)
-------+--------+--------+--------+--------
1 (11) | X (00) | X (00) | 1 (11) | 0 (10)
-------+--------+--------+--------+--------
0 (10) | X (00) | X (00) | 0 (10) | 0 (10)

请注意,X经常获胜。这对大多数操作来说都是正确的。
然后从K图中计算布尔方程:
C = A & B
=> C1 = A1 & B1
   C0 = A1 & B1 & A0 & B0 = C1 & A0 & B0

最后,将其翻译成C++:
template<size_t NBits> class BitVector
{private:
    enum { NWords = (NBits+31)/32 };
    int32_t storage[NWords][2];
public:
    BitVector<NBits> operator &(BitVector<NBits>& rhs)
    {    BitVector<NBits> result;
         for(unsigned k = 0; k < NWords; ++k)
         {   int32_t x = storage[k][1] & rhs.storage[k][0];
             result.storage[k][1] = x;
             result.storage[k][0] = storage[k][0] & rhs.storage[k][0] & x;
         }
         return result;
    }
};   

(注:我还没有测试上面的代码,所以使用时需自担风险。)

如果允许级别的集合发生变化,所有这些都必须重新做。这就是为什么这些库往往过于专业化,无法放入像Boost这样的通用库中。

编辑2:我突然想到BitVector模板类是少数几个重载逗号运算符有意义的用例之一:

template<size_t NBitsR>
BitVector<NBits+NBitsR> operator ,(const BitVector<NBitsR>& rhs);

这允许您连接位向量:
BitVector<8> a("1110 0111");
BitVector<4> b("0000");
BitVector<12> c = (a, b); // == BitVector<12>("0000 1110 0111")

...这似乎是将一个向量填充到另一个向量大小的最直观的方法(很容易证明这样的填充不应该是隐式的,永远不应该),或者将向量合并在一起。

编辑3:我突然意识到(是的,我很慢),如果你真的想做一个通用版本,你可以使用基于策略的设计

struct TwoLevelLogic
{   enum
    {   kNumPlanes = 1
    };
    static void And(int32_t[] result, int32_t[] lhs, int32_t[] rhs)
    {    result[0] = lhs[0] & rhs[0];
    }
};

struct FourLevelLogic
{   enum
    {   kNumPlanes = 2
    };
    static void And(int32_t[] result, int32_t[] lhs, int32_t[] rhs)
    {    int32_t x = lhs[1] & rhs[1];
         result[1] = x;
         result[0] = lhs[0] & rhs[0] & x;
    }
};

template<typename LogicType, size_t NBits>
class BitVector
{private:
    enum { NWords = (NBits+31)/32 };
    int32_t storage[NWords][LogicType::kNumPlanes];
public:
    BitVector<LogicType, NBits> operator &(BitVector<LogicType, NBits>& rhs)
    {    BitVector<LogicType, NBits> result;
         for(unsigned k = 0; k < NWords; ++k)
             LogicType::And(result.storage[k], storage[k], rhs.storage[k]);
         return result;
    }
};

template<size_t NBits> 
class BitVector4L: public BitVector<FourLevelLogic, NBits> {};

然后,如果您想使用不同的逻辑表示,比如九个级别,甚至两个级别,那么您可以定义新的策略来支持这些格式。此外,您可以在问题的不同领域中使用不同的策略进行计算(例如,板子上使用4个级别,芯片上使用9个级别,处理器模拟器上使用2个级别),并定义转换函数来弥合差距。
同样,我还没有尝试构建它,所以我不确定它是否完美优化。

5

0

我不熟悉上述提到的boost库,但它似乎只支持单个布尔值而不是位域。您可以使用以下技术自己完成,而不需要太多麻烦:

class Logic
{
    unsigned x, xu;

public:
    Logic(unsigned x, unsigned xu)
    {
        this->x = x;
        this->xu = xu;
    }

    Logic operator&(const Logic &rhs) const
    {
        return Logic(
            x & rhs.x,
            xu & (rhs.x | rhs.xu) | rhs.xu & (x | xu));
    }

    Logic operator|(const Logic &rhs) const
    {
        return Logic(
            x | rhs.x,
            xu & (~rhs.x | rhs.xu) | rhs.xu & (~x | xu));
    }
};

免责声明 - 需要验证!

如果您计划同时执行许多此类操作,则最好使用64位整数而不是单个tribool。


xxu代表什么? - Nathan Fellman
x 表示一系列的值位,而 xu 表示一系列已定义(0)或未定义(1)的位。 - Reinderien

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接