Libreria C++ con supporto per logica a 3 valori:0,1,X

Question

Sto lavorando su un simulatore per un microprocessore, scritto in C++.

Sto cercando un modo per modellare gli elementi di stato nell'hardware che sono appena stati accesi e non sono stati ancora ripristinati in alcun modo.Un elemento di stato reale avrebbe un valore sconosciuto che può essere 0 o 1, ma nei modelli software questo è comunemente modellato come un X, Senso sconosciuto.

Sto cercando una libreria in C++ che possa modellarli X valori, inclusa la loro propagazione.Dovrebbe cioè sapere come gestire le operazioni logiche e aritmetiche Xes:

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

eccetera...

Esiste una libreria del genere che sia stabile e veloce?

Modificare:

Ho trascurato di menzionare che il mio codice attuale funziona con bitvettori.Più precisamente, utilizzo lo standard uint_*t tipi di dati e questi sono quelli che voglio sostituire.Qualunque sia la libreria che utilizzo, it dovere supportare l'aritmetica, i turni e gli operatori logici affinché sia ​​utile.

Answer 1

Potresti pensare di consentire più di tre stati, se stai cercando di modellare le linee hardware.Ecco cosa utilizza Altera nel suo simulatore FPGA:

• 1:Forte Alto (transistor pilotato su VDD)
• 0:Forte Basso (transistor pilotato su VSS)
• H:Debole Alto (pull-up del resistore su VDD)
• L:Debole Basso (pulldown del resistore su VSS)
• Z:Alta impedenza (linea non pilotata)
• X:Sconosciuto
• W:Debole sconosciuto
• U:Non inizializzata
• CC:Non importa

Potrebbe non essere necessario W, U e DC.Puoi abbandonare H, L e Z se i tuoi autobus vengono sempre guidati.

Verilog utilizza ancora più livelli per modellazione a livello di gate, con sette forze motrici per ciascun livello logico.I livelli aggiuntivi modellano gli effetti capacitivi sulle linee di segnale.Questo è probabilmente più del necessario.

MODIFICARE: Dato che hai menzionato i vettori di bit, devo dire che, IMHO, non troverai una libreria del genere di uso pubblico e tenuta aggiornata perché 1) semplicemente non ci sono molti programmatori che necessitano di una cosa del genere , e 2) anche tra loro, a causa delle opzioni sopra menzionate per la modellazione dei livelli di linea, c'è poca compatibilità.I tribool di Boost possono essere messi in servizio, ma non saranno veloci, poiché le operazioni saranno elemento per elemento e l'archiviazione non sarà ottimizzata, ma potrebbero essere la tua unica scelta se qualcuno è allergico alla scrittura di una libreria interna che fa esattamente quello di cui hai bisogno.

Ad esempio, supponiamo di volere una classe che rappresenti vettori di bit con quattro possibili livelli:1, 0, X e Z.Innanzitutto, devi definire modelli di bit equivalenti per ciascun livello (ad es.X=00, Z=01, 0=10, 1=11;X è stato scelto come stato di ripristino)

Per ogni operazione bisogna scrivere la tavola della verità, preferibilmente in formato Mappa di Karnaugh modulo:

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)

(Nota che X vince molto.Questo è vero per la maggior parte delle operazioni.)

Quindi elabora le equazioni booleane dalla K-map:

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

Infine, traducilo in 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;
    }
};   

(Nota:Non ho testato il codice sopra, quindi utilizzalo a tuo rischio e pericolo.)

Tutto di questo deve essere rifatto se l'insieme dei livelli consentiti cambia.Questo è il motivo per cui queste librerie tendono ad essere troppo specializzate per essere inserite in una libreria di uso generale come Boost.

EDIT2: Mi è appena venuto in mente che la classe del modello BitVector ha uno dei pochi casi d'uso in cui ha senso sovraccaricare l'operatore virgola:

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

Ciò ti consente di concatenare i vettori di bit:

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

...che sembra il modo più intuitivo per riempire un vettore fino alla dimensione di un altro (è facile dimostrare che tale riempimento dovrebbe non essere implicito, mai) o unire i vettori insieme.

EDIT3: Mi è appena venuto in mente (sì, sono lento) che, se tu Veramente volevo fare una versione generalizzata di questo, potresti farlo con progettazione basata sulle politiche:

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

Quindi, se si desidera utilizzare una rappresentazione logica diversa, diciamo nove livelli, o anche due, è possibile definire nuove policy per supportare tali formati.Inoltre, puoi calcolare con policy diverse in diversi domini del tuo problema (ad esempio, 4 livelli per la tua scheda, 9 per il chip e 2 per un simulatore di processore) e definire funzioni di conversione per colmare le lacune.

Ancora una volta, non ho provato a crearlo, quindi non sono sicuro che sia ottimizzato perfettamente.

Answer 2

Boost.Tribool .

  

La classe tribool agisce come il built-in di tipo bool, ma per 3-state logica booleana. I tre stati sono true, false, e indeterminate, dove i primi due stati sono equivalenti a quelli di tipo bool C ++ e l'ultima condizione rappresenta un valore booleano sconosciuta (che può essere true o false, non sappiamo).

È possibile vedere il prova costume e il documentazione intestazione per le regole questo sostiene di classe.

librerie Boost sono piuttosto alta qualità e ben mantenuto, quindi non c'è bisogno di preoccuparsi per la sua stabilità. E "veloce" ... beh è difficile essere lento per le classi semplici come questo :). Le operazioni sono implementate con 2-3 confronto intero con 1 o 2 clausole if quindi dovrebbe essere abbastanza efficace.

Answer 3

Boost ha una biblioteca tribool, ma non posso commentare la sua qualità in quanto non ho mai usato:

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

Answer 4

Non ho familiarità con la libreria di spinta di cui sopra, ma sembra che supporta solo un singolo booleano e non un campo di bit. Si potrebbe fare da soli senza troppo clamore utilizzando una tecnica simile alla seguente:

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 -! Questa necessità di verifica

Se si ha intenzione di fare molti di questi in un momento, è meglio utilizzare interi a 64 bit al posto dei singoli tribools.