Библиотека C ++ с поддержкой 3-значной логики:0,1,X
https://stackoverflow.com/questions/3872717
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я работаю над симулятором микропроцессора, написанным на C ++.
Я ищу способ моделировать элементы состояния в оборудовании, которые только что были включены и еще не были сброшены каким-либо образом.Реальный элемент состояния будет иметь неизвестное значение, равное либо 0, либо 1, но в программных моделях это обычно моделируется как X, означающий неизвестный.
Я ищу библиотеку на C ++, которая может моделировать эти X ценности, включая их распространение.То есть он должен был бы знать, как обрабатывать логические и арифметические операции с Xes:
1 AND X = X
0 AND X = 0
1 + X = X
и т.д...
Есть ли какая-нибудь такая библиотека, которая была бы стабильной и быстрой?
Редактировать:
Я забыл упомянуть, что мой текущий код работает с bitvectors.Более точно, я использую стандартный uint_*t типы данных, и это те, которые я хочу заменить.Какую бы библиотеку я ни использовал, она должен поддерживайте арифметику, сдвиги и логические операторы, чтобы это было полезно.
Решение
Возможно, вам захочется разрешить более трех состояний, если вы пытаетесь моделировать аппаратные линии.Вот что Altera использует в своем симуляторе FPGA:
- 1:Сильный Высокий (транзистор, работающий на VDD)
- 0:Сильный низкий уровень (транзистор, подключенный к VSS)
- H:Слабый высокий (подтягивание резистора к VDD)
- L:Слабый низкий уровень (переключение резистора на VSS)
- Z:Высокий импеданс (непривитая линия)
- X:Неизвестный
- W:Слабый Неизвестный
- U:Неинициализированный
- Постоянный ток:Мне все равно
Возможно, вам не понадобятся W, U и DC.Вы можете отказаться от H, L и Z, если ваши автобусы всегда ходят.
Verilog использует еще больше уровней для моделирование на уровне ворот, с семью мощностями привода для каждого логического уровня.Дополнительные уровни моделируют емкостные эффекты на сигнальных линиях.Вероятно, это больше, чем вам нужно.
Редактировать: Поскольку вы упомянули векторы битов, я должен сказать, что, ИМХО, вы не найдете такую библиотеку в общедоступном доступе и постоянно обновляемой, потому что 1) просто не так много программистов, нуждающихся в такой вещи, и 2) даже среди них, из-за вышеупомянутых опций для моделирования уровней строк, совместимость невелика.Tribools от Boost можно запустить в эксплуатацию, но это будет не быстро, поскольку операции будут выполняться поэлементно, а хранилище не будет оптимизировано, но они могут быть вашим единственным выбором, если у кого-то аллергия на написание собственной библиотеки, которая делает именно то, что вам нужно.
Например, предположим, вам нужен класс, представляющий векторы битов с четырьмя возможными уровнями:1, 0, X и Z.Во-первых, вы должны определить эквивалентные битовые шаблоны для каждого уровня (например,X=00, Z=01, 0=10, 1=11;X было выбрано в качестве состояния сброса)
Для каждой операции вы должны выписать таблицу истинности, предпочтительно в Карта Карно форма:
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)
(Обратите внимание, что X часто выигрывает.Это верно для большинства операций.)
Затем вычислите булевы уравнения из K-карты:
C = A & B
=> C1 = A1 & B1
C0 = A1 & B1 & A0 & B0 = C1 & A0 & B0
Наконец, переведите это на 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;
}
};
(Примечание:Я не тестировал приведенный выше код, поэтому используйте на свой страх и риск.)
Все все это должно быть переделано, если набор разрешенных уровней изменится.Вот почему эти библиотеки, как правило, слишком специализированы, чтобы их можно было поместить в библиотеку общего пользования, такую как Boost.
РЕДАКТИРОВАТЬ 2: До меня только что дошло, что шаблонный класс BitVector имеет один из немногих вариантов использования, когда перегрузка оператора запятой имеет смысл:
template<size_t NBitsR>
BitVector<NBits+NBitsR> operator ,(const BitVector<NBitsR>& rhs);
Это позволяет вам объединять битовые векторы:
BitVector<8> a("1110 0111");
BitVector<4> b("0000");
BitVector<12> c = (a, b); // == BitVector<12>("0000 1110 0111")
...который кажется наиболее интуитивно понятным способом увеличения размера одного вектора до размера другого (легко показать, что такое дополнение должно нет быть неявным, когда - либо) или объединить векторы вместе.
РЕДАКТИРОВАТЬ 3: До меня только что дошло (да, я тугодум), что, если ты в самом деле если бы вы хотели сделать обобщенную версию этого, вы могли бы сделать это с помощью разработка на основе политики:
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> {};
Затем, если вы хотите использовать другое логическое представление, скажем, девять уровней или даже два, вы могли бы определить новые политики для поддержки этих форматов.Кроме того, вы можете выполнять вычисления с использованием разных политик в разных областях вашей проблемы (скажем, 4 уровня для вашей платы, 9 для чипа и 2 для симулятора процессора) и определять функции преобразования для устранения пробелов.
Опять же, я не пытался создать это, поэтому я не уверен, что это идеально оптимизируется.
Другие советы
Пытаться Boost.tribool..
То
triboolкласс действует как встроенныйboolТип, но для 3-го булевой логики. Три государстваtrue,false, а такжеindeterminate, где первые два состояния эквивалентны тем, которые C ++boolтип и последнее состояние представляет собой неизвестное логическое значение (которое может бытьtrueилиfalse, Мы не знаем).
Вы можете увидеть тестовый костюм и то Заголовок документации Для правил этого класса поддерживает.
Boost Библиотеки довольно высокого качества и ухоженные, поэтому вам не нужно беспокоиться о своей стабильности. И "Быстро" ... ну, трудно быть медленным для простых классов, как это :). Операции реализованы с 2 до 3 целочисленного сравнения с 1 или 2 if пункты, так что это должно быть достаточно эффективно.
У Boost есть библиотека ТРБОЛ, но я не могу прокомментировать его качество, так как я никогда не использовал это:
Я не знаком с библиотекой Boost, упомянутой выше, но кажется, что она поддерживает только один логический и не битфилд. Вы могли бы сделать это самостоятельно без слишком много суеты, используя методику, как следующее:
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));
}
};
Отказ от ответственности - это требует проверки!
Если вы планируете делать много из них одновременно, вам лучше использовать 64-битные целые числа вместо индивидуальных труб.
