C++ library with support for 3-valued logic: 0,1,X

Question

I am working on a simulator for a microprocessor, written in C++.

I am looking for a way to model state elements in the hardware that have just been powered up and have not yet been reset in any way. A real state element would have an unknown value that is either 0 or 1, but in software models this is commonly modeled as an X, meaning unknown.

I am looking for a library in C++ that can model these X values, including their propagation. That is, it would have to know how to handle logical and arithmetical operations with Xes:

1 AND X = X
0 AND X = 0
1  +  X = X

etc...

Is there any such library that is both stable and fast?

Edit:

I neglected to mention that my current code works with bitvectors. More accurately, I use the standard uint_*t data types, and these are the ones I want to replace. Whatever library I use, it must support arithmetic, shifts and logical operators for it to be useful.

Answer 1

You might want to think of allowing more than three states, if you're trying to model hardware lines. Here's what Altera uses in its FPGA simulator:

• 1: Strong High (transistor driven to VDD)
• 0: Strong Low (transistor driven to VSS)
• H: Weak High (resistor pullup to VDD)
• L: Weak Low (resistor pulldown to VSS)
• Z: High Impedance (undriven line)
• X: Unknown
• W: Weak Unknown
• U: Uninitialized
• DC: Don't Care

You might not need W, U, and DC. You can ditch H, L, and Z if your buses are always driven.

Verilog uses even more levels for gate-level modeling, with seven drive strengths for each logic level. The additional levels model capacitive effects on signal lines. This is probably more than you need.

EDIT: Since you mentioned vectors of bits, I have to say that, IMHO, you're not going to find such a library in public use and kept up-to-date because 1) there just aren't that many programmers needing such a thing, and 2) even among them, due to the aforementioned options for modeling line levels, there is little compatibility. Boost's tribools can be pressed into service, but they will not be fast, since operations will be element-by-element and storage will not be optimized, but they may be your only choice if someone is allergic to writing an in-house library that does exactly what you need.

For example, say you want a class that represents vectors of bits with four possible levels: 1, 0, X, and Z. First, you have to define equivalent bit patterns for each level (e.g. X=00, Z=01, 0=10, 1=11; X was chosen as the reset state)

For each operation, you have to write out the truth table, preferably in Karnaugh Map form:

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)

(Note that X wins a lot. This is true for most operations.)

Then work out the boolean equations from the K-map:

C = A & B
=> C1 = A1 & B1
   C0 = A1 & B1 & A0 & B0 = C1 & A0 & B0

Finally, translate that into 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;
    }
};   

(Note: I haven't tested the code above, so use at your own risk.)

All of this has to be redone if the set of allowed levels changes. This is why these libraries tend to be too specialized to put into a general-use library like Boost.

EDIT2: It just dawned on me that the BitVector template class has one of the few use cases where overloading the comma operator makes sense:

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

This lets you concatenate bit vectors:

BitVector<8> a("1110 0111");
BitVector<4> b("0000");
BitVector<12> c = (a, b); // == BitVector<12>("0000 1110 0111")

... which seems like the most intuitive way to pad one vector up to the size of another (it's easy to show that such padding should not be implicit, ever) or merge vectors together.

EDIT3: It just dawned on me (yeah, I'm slow) that, if you really wanted to do a generalized version of this, you could do it with policy-based design:

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> {};

Then, if you want to use a different logic representation, say nine levels, or even two, then you could define new policies to support those formats. Additionally, you can compute with different policies in different domains of your problem (say, 4 levels for your board, 9 for the chip, and 2 for a processor simulator) and define conversion functions to bridge the gaps.

Again, I haven't tried to build this, so I'm not sure if this optimizes perfectly.

Answer 2

Try Boost.Tribool.

The tribool class acts like the built-in bool type, but for 3-state boolean logic. The three states are true, false, and indeterminate, where the first two states are equivalent to those of the C++ bool type and the last state represents an unknown boolean value (that may be true or false, we don't know).

You can see the test suit and the header documentation for the rules this class supports.

Boost libraries are pretty high quality and well maintained, so you don't need to worry about its stability. And "fast"... well it's hard to be slow for simple classes like this :). The operations are implemented with 2 to 3 integer comparison with 1 or 2 if clauses so it should be efficient enough.

Answer 3

Boost has a tribool library, but I cannot comment on its quality since I never used it:

http://www.boost.org/doc/libs/1_44_0/doc/html/tribool.html

Answer 4

I'm not familiar with the boost library mentioned above, but it seems it only supports a single boolean and not a bitfield. You could do it yourself without too much fuss using a technique like the following:

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));
    }
};

Disclaimer - this needs verification!

If you plan on doing many of these at a time, you're better off using 64-bit integers instead of individual tribools.