C ++ library with support for 3-digit 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 equipment that has just been turned on and has not yet been reset. The real state element will have an unknown value equal to 0 or 1, but in software models this is usually modeled as X , which means unknown.

I am looking for a C ++ library that can model these X values, including their distribution. That is, he would have to know how to handle logical and arithmetic operations using X es:

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

etc...

Is there such a library that is stable and fast?

Edit:

I forgot to mention that my current code works with bitvectors. More precisely, I use the standard uint_*t data types, and these are the ones I want to replace. No matter which library I use, it must support arithmetic, shifts, and logical operators in order to be useful.

Answer 1

You might want to consider resolving more than three states if you are trying to simulate hardware lines. Here is what Altera uses in its FPGA simulator:

• 1: Strong high (transistor connected to VDD)
• 0: strong low (transistor connected to VSS)
• H: weak maximum (rectification resistor for VDD)
• L: weak low (resistor output voltage for VSS)
• Z: high impedance (line off)
• X: Unknown
• W: Weak Unknown
• U: Uninitialized
• DC: Don’t care

You may not need W, U, and DC. You can cut H, L, and Z if your tires are always steered.

Verilog uses even more levels to model the shutter , with seven powerful models for each logical level. Additional levels simulate capacitive effects on signal lines. This is probably more than you need.

EDIT: Since you mentioned bit vectors, I have to say that, IMHO, you will not find such a library in public use and will not be updated, because 1) there are simply not many programmers who need this, and 2) even among of them, due to the aforementioned linear level modeling options, there is little compatibility. Boost tribools can be activated, but they won’t be fast, because the operations will be phased in and storage will not be optimized, but they may be your only choice if someone is allergic to creating an internal library that does exactly what you necessary.

For example, say you need a class that represents bit vectors with four possible levels: 1, 0, X, and Z. First you must define equivalent bit patterns for each level (for example, X = 00, Z = 01, 0 = 10, 1 = 11, X was selected as reset state)

For each operation you need to write a truth table, preferably in the form of a Carnot 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) 

(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 this 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 have not tested the code above, so use it at your own risk.)

All this needs to be redone if the set of acceptable levels changes. This is why these libraries are usually too specialized to be included in a shared library, such as 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 allows you to 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 put one vector to the size of another (it's easy to show that such a complement doesn't have to be implicit, ever) or combine vectors together.

EDIT3: It just dawned on me (yes, I'm slow) that if you really wanted to make a generalized version of this, you could do it with the help of political 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 another logical representation, say, nine levels or even two, you can define new policies to support these formats. In addition, you can calculate using different policies in different areas of your problem (say, 4 levels for your board, 9 for a chip and 2 for a processor simulator) and define conversion functions to fill in the gaps.

Again, I did not try to build it, so I'm not sure if this is perfectly optimized.

Answer 2

Try Boost.Tribool .

The tribool class acts as a built-in bool type, but for the logic of the 3rd state. Three states: true , false and indeterminate , where the first two states are equivalent to C ++ bool types, and the last state is an unknown logical value (this can be true or false , we do not know).

You can see the test case and header documentation for the rules supported by this class.

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 for simple classes like this :). Operations are performed with 2 to 3 whole comparisons with 1 or 2 if sentences, so they should be quite effective.

Answer 3

Boost has a tribool library, but I can not 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 am not familiar with the boost library mentioned above, but it seems to support only one logical, not a bitfield. You can do it yourself without fussing too much using the following technique:

 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 requires verification!

If you plan to execute many of them at once, you are better off using 64-bit integers instead of separate tribulas.