biblioteca de C ++ con soporte para lógica 3 valioso-: 0,1, X

Question

Estoy trabajando en un simulador de un microprocesador, escrito en C ++.

Estoy buscando una manera de elementos de estado de modelo en el hardware que acaban de ser encendidos y aún no se han restablecido de ninguna manera. Un elemento verdadero estado tendría un valor desconocido que es 0 o 1, pero en modelos de software Esto se modela comúnmente como un X, es decir, desconocida .

Busco a una biblioteca en C ++ que pueden modelar estos valores X, incluyendo su propagación. Es decir, tendría que saber cómo manejar las operaciones lógicas y aritméticas con Xes:

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

etc ...

¿Hay cualquier biblioteca que es a la vez estable y rápido?

Editar

Me olvidé de mencionar que mi código actual funciona con bitvectors. Más exactamente, yo uso los tipos de datos uint_*t estándar, y estos son los que desea reemplazar. Sea cual sea el uso de la biblioteca I, debe aritmética de apoyo, turnos y operadores lógicos para que pueda ser de utilidad.

Answer 1

Es posible que desee pensar en lo que permite más de tres estados, si usted está tratando de líneas de hardware modelo. Esto es lo que Altera usos en su simulador de FPGA:

• 1: Fuerte alta (transistor conducido a VDD)
• 0: Fuerte Bajo (transistor conducido a VSS)
• H: Débil alta (resistencia de actuación a VDD)
• L: Débil Low (resistencia de pulldown a VSS)
• Z: de alta impedancia (línea no accionado)
• X: Desconocido
• W: Desconocido Débil
• T: no inicializado
• CC: No me importa

Puede que no necesite W, T y DC. Puede zanja H, L y Z si los autobuses siempre son impulsadas.

Verilog utiliza aún más los niveles de -nivel de la puerta de modelado , con siete unidad fortalezas para cada nivel lógico. Los niveles adicionales modelo de efectos capacitivos en las líneas de señal. Esto es probablemente más de lo necesario.

EDIT: Ya que menciona vectores de bits, tengo que decir que, en mi humilde opinión, no vas a encontrar una biblioteca tal en el uso público y mantenerse al día porque 1) simplemente no hay que muchos programadores que necesitan tal cosa, y 2) aun entre ellos, debido a las opciones mencionadas anteriormente para modelar los niveles de línea, hay poca compatibilidad. tribools de Boost pueden ser puestos en servicio, pero no van a ser rápido, ya que las operaciones serán elemento por elemento y el almacenamiento no será optimizado, sino que puede ser su única opción si alguien es alérgico a la escritura de una biblioteca en la casa que hace exactamente lo que necesita.

Por ejemplo, supongamos que desea una clase que representa los vectores de bits con cuatro niveles posibles: 1, 0, X, Y y Z. En primer lugar, tiene que definir patrones de bits equivalente para cada nivel (por ejemplo X = 00, Z = 01, 0 = 10, 1 = 11; X fue elegido como el estado de reposición)

Para cada operación, hay que escribir la tabla de verdad, preferiblemente en forma de Karnaugh Mapa :

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)

(Tenga en cuenta que X ha recibido una gran cantidad. Esto es cierto para la mayoría de las operaciones.)

A continuación, se resuelve las ecuaciones booleanas de la K-map:

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

Por último, traducir eso en 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:. No he probado el código anterior, por lo que su uso bajo su propio riesgo)

Todo de esto tiene que ser hecho de nuevo si el conjunto de los niveles cambios permitidos. Esta es la razón por estas bibliotecas tienden a ser demasiado especializados para poner en una biblioteca de uso general como Boost.

Edit2: Se acaba caído en la cuenta de que la clase de plantilla BitVector tiene uno de los pocos casos de uso donde la sobrecarga del operador coma tiene sentido:

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

Esto le permite concatenar vectores de bits:

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

... que parece la forma más intuitiva para rellenar un vector hasta el tamaño de otro (que es fácil demostrar que tales acolchado debe no estar implícito, jamás ) o vectores de combinación juntos.

Edit3: Sólo me di cuenta (sí, soy lento) que, si realmente quería hacer una versión generalizada de esto, se podía hacerlo diseño basado en políticas :

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

A continuación, si desea utilizar una representación lógica diferente, digamos nueve niveles, o incluso dos, entonces se podría definir nuevas políticas para apoyar esos formatos. Además, se puede calcular con diferentes políticas en diferentes ámbitos de su problema (por ejemplo, 4 niveles para su tablero, 9 para el chip, y 2 para un simulador de procesador) y definir las funciones de conversión para cerrar las brechas.

Una vez más, no he tratado de construir esto, así que no estoy seguro si esto optimiza perfectamente.

Answer 2

Trate Boost.Tribool .

  

La clase tribool actúa como el tipo incorporado bool, pero para 3-estado lógico booleano. Los tres estados son true, false, y indeterminate, donde los dos primeros estados son equivalentes a los de la C ++ tipo bool y el último estado representa un valor booleano desconocido (que puede ser true o false, no sabemos).

Se puede ver el prueba de traje de y la href="http://www.boost.org/doc/libs/1_44_0/doc/html/tribool/reference.html#header.boost.logic.tribool_hpp" rel="noreferrer"> documentación cabecera por las reglas esto apoya la clase.

bibliotecas Boost están bastante alta calidad y bien mantenido, por lo que no necesita preocuparse por su estabilidad. Y "rápido" ... así que es difícil de ser lento para las clases simples como esto :). Las operaciones se implementan con 2 a 3 Comparación de número entero con 1 o 2 cláusulas if lo que debe ser lo suficientemente eficiente.

Answer 3

Boost cuenta con una biblioteca tribool, pero no puede hacer comentarios sobre su calidad, ya que nunca utilicé:

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

Answer 4

No estoy familiarizado con la biblioteca impulso mencionado anteriormente, pero parece que sólo es compatible con un solo booleano y no un campo de bits. Se podía hacerlo usted mismo sin mucho alboroto utilizando una técnica similar a la siguiente:

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

Aviso Legal - esta verificación necesidades

Si usted planea en hacer muchos de estos a la vez, es mejor usar enteros de 64 bits en vez de tribools individuales.