Biblioteca C ++ com suporte para lógica de 3 valor: 0,1, x
https://stackoverflow.com/questions/3872717
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Estou trabalhando em um simulador para um microprocessador, escrito em C ++.
Estou procurando uma maneira de modelar elementos de estado no hardware que acabaram de ser ligados e ainda não foram redefinidos de forma alguma. Um elemento de estado real teria um valor desconhecido que é 0 ou 1, mas em modelos de software, isso é comumente modelado como um X, significado desconhecido.
Estou procurando uma biblioteca em C ++ que possa modelá -los X valores, incluindo sua propagação. Isto é, teria que saber como lidar com operações lógicas e aritméticas com Xes:
1 AND X = X
0 AND X = 0
1 + X = X
etc ...
Existe alguma biblioteca que seja estável e rápida?
Editar:
Eu deixei de mencionar que meu código atual funciona com o BitVectors. Com mais precisão, eu uso o padrão uint_*t Tipos de dados, e esses são os que eu quero substituir. Qualquer biblioteca que eu uso, isso devo Suporte a aritmética, turnos e operadores lógicos para que seja útil.
Solução
Você pode pensar em permitir mais de três estados, se estiver tentando modelar linhas de hardware. Aqui está o que a Altera usa em seu simulador FPGA:
- 1: alto forte (transistor dirigido a VDD)
- 0: Low forte (transistor dirigido a VSS)
- H: Alto fraco (pullup de resistor para VDD)
- L: Baixa fraca (pulldown do resistor para VSS)
- Z: Alta impedância (linha não movida)
- X: Desconhecido
- W: fraco desconhecido
- U: Não inicializado
- DC: Não se importe
Você pode não precisar de W, U e DC. Você pode abandonar H, L e Z se seus ônibus forem sempre acionados.
Verilog usa ainda mais níveis para Modelagem no nível do portão, com sete pontos fortes para cada nível lógico. Os níveis adicionais modelam efeitos capacitivos nas linhas de sinal. Provavelmente isso é mais do que você precisa.
EDITAR: Desde que você mencionou vetores de bits, devo dizer que, IMHO, você não encontrará uma biblioteca dessas em uso público e mantido atualizado porque 1) não há muitos programadores que precisam de tal coisa e 2) mesmo entre eles, devido às opções mencionadas para modelar os níveis de linha, há pouca compatibilidade. Os tribools do Boost podem ser pressionados ao serviço, mas não serão rápidos, pois as operações serão elementos por elementos e o armazenamento não serão otimizados, mas podem ser sua única escolha se alguém for alérgico a escrever uma biblioteca interna que faz exatamente o que você precisa.
Por exemplo, digamos que você deseja uma classe que represente vetores de bits com quatro níveis possíveis: 1, 0, x e Z. Primeiro, você deve definir padrões de bits equivalentes para cada nível (por exemplo, x = 00, z = 01, 0 = 10, 1 = 11; x foi escolhido como o estado de redefinição)
Para cada operação, você deve escrever a tabela de verdade, de preferência em Mapa de Karnaugh Formato:
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)
(Observe que X ganha muito. Isso é verdade para a maioria das operações.)
Em seguida, elabore as equações booleanas do K-map:
C = A & B
=> C1 = A1 & B1
C0 = A1 & B1 & A0 & B0 = C1 & A0 & B0
Finalmente, traduza isso em 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: eu não testei o código acima, então use por sua conta e risco.)
Tudo disso deve ser refeito se o conjunto de níveis permitidos mudarem. É por isso que essas bibliotecas tendem a ser especializadas demais para colocar em uma biblioteca de uso geral como o Boost.
Edit2: Acabou com mim que a classe BitVector Model tem um dos poucos casos de uso em que a sobrecarga do operador de vírgula faz sentido:
template<size_t NBitsR>
BitVector<NBits+NBitsR> operator ,(const BitVector<NBitsR>& rhs);
Isso permite concatenar vetores de bits:
BitVector<8> a("1110 0111");
BitVector<4> b("0000");
BitVector<12> c = (a, b); // == BitVector<12>("0000 1110 0111")
... que parece ser a maneira mais intuitiva de encaixar um vetor até o tamanho de outro (é fácil mostrar que esse preenchimento deve não estar implícito, sempre) ou mesclar vetores.
Edit3: Apenas me ocorreu (sim, estou lento) que, se você verdade queria fazer uma versão generalizada disso, você poderia fazer isso com Design baseado em 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> {};
Então, se você deseja usar uma representação lógica diferente, digamos nove níveis, ou até dois, poderá definir novas políticas para apoiar esses formatos. Além disso, você pode calcular com diferentes políticas em diferentes domínios do seu problema (por exemplo, 4 níveis para sua placa, 9 para o chip e 2 para um simulador de processador) e definir funções de conversão para preencher as lacunas.
Novamente, não tentei construir isso, então não tenho certeza se isso otimiza perfeitamente.
Outras dicas
Tentar Boost.tribool.
o
triboolA classe age como o embutidoboolTipo, mas para a lógica booleana de três estados. Os três estados sãotrue,false, eindeterminate, onde os dois primeiros estados são equivalentes aos do C ++booltipo e o último estado representa um valor booleano desconhecido (que pode sertrueoufalse, não sabemos).
Você pode ver o traje de teste e a Documentação do cabeçalho Para as regras que essa classe suporta.
As bibliotecas de impulso são de alta qualidade e bem conservadas, então você não precisa se preocupar com sua estabilidade. E "rápido" ... bem, é difícil ser lento para aulas simples como esta :). As operações são implementadas com 2 a 3 comparação inteira com 1 ou 2 if cláusulas para que sejam eficientes o suficiente.
Boost tem uma biblioteca do Tribool, mas não posso comentar sua qualidade, pois nunca a usei:
Não estou familiarizado com a biblioteca Boost mencionada acima, mas parece que só suporta um único booleano e não um campo de bits. Você pode fazer isso sozinho sem muita confusão usando uma técnica como a seguinte:
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));
}
};
Isenção de responsabilidade - isso precisa de verificação!
Se você planeja fazer muitos deles de cada vez, é melhor usar números inteiros de 64 bits em vez de tribools individuais.
