GCC в макетную плату с помощью шаблонов С++

Я люблю собирать логические схемы. Однако обычно для этого требуется либо симулятор, либо макетная плата. Как-то в дороге у меня был с собой ноутбук с компилятором, но не было интернета. Задача написать небольшую программу с библиотекой цифровых вентилей показалась мне слишком тривиальной. Хм-м, как насчет метапрограммы?

Ты наверняка знаешь (или хотя бы слышал), что шаблоны С++ сами по себе функциональный язык, обладающий полнотой по Тьюрингу. Иными словами, с их помощью можно выполнять стандартные операции, строить выражения и вычислять какие-то значения. Которые затем можно использовать в новых операциях, снова что-то считать, и так по кругу, до получения нужного результата. И все это — во время компиляции основной программы!

РЕКОМЕНДУЕМ:
Логические элементы и биты памяти в компьютере

Но это в теории. На практике шаблоны С всегда были непростыми в использовании, и даже сейчас, когда Комитет по стандартизации языка С многое сделал для их популяризации и облегчения их применения, далеко не все разработчики с энтузиазмом принимаются кодировать логику своих приложений на этих самых шаблонах.

Содержание

GCC в макетную плату с помощью шаблонов С++
Template Temple
В ушах — бит, в классе — тип
Рекурсия — бессердечная ты…
Шаблонный шабаш
Финальные штрихи
Иллюзорность кода

GCC в макетную плату с помощью шаблонов С++

Действительно, перспектива вытащить часть вычислений на этап компиляции выглядит заманчивой, равно как и возможность управлять самим процессом компиляции. Однако на практике попытка сделать что-то полезное на таком высоком уровне абстракции зачастую оборачивается многочисленными ошибками при компиляции, маловразумительными сообщениями и прочими прелестями.

Вообще говоря, шаблоны вошли в состав языка С совсем с другими целями, и их реальные возможности исследователи открыли почти что случайно. Одной из первых метапрограмм такого рода принято считать программу для определения простоты числа за авторством Эрвина Анруха из компании Siemens, написанную в 1994 году. Примечательно, что для вывода результата в процессе компиляции программы тогда использовались сообщения об ошибках. Весьма символично. Впрочем, за четверть века метапрограммирование в С прошло долгий путь, так что сегодня такие ухищрения уже не понадобятся.

Но парочку трюков применить все равно придется. Впрочем, без этого было бы не так интересно, согласен?

Template Temple

Итак, нам предстоит реализовать множество логических операций времени компиляции с помощью шаблонов языка C++. Компилятором был выбран (вернее, оказался) GCC, с опцией -std=c++17 для расширенной поддержки метапрограммирования. Не так давно Комитет по стандартизации языка принял в Праге новую версию С++20, но ожидать, что все производители компиляторов ее поддержат, наверное, пока рановато.

И последнее замечание, прежде чем мы перейдем непосредственно к коду, для тех, кто мало знаком с шаблонами С++. Нужно понимать, что программирование на шаблонах представляет собой работу с типами, а не с переменными, как обычно. Взаимоотношения между шаблоном, типом, классом и объектом класса (переменной) мы обсудим чуть ниже, ну а пока заведем парочку структур для представления нуля и единицы в нашей будущей библиотеке логических элементов.

#include <iostream>

#include <type_traits>

#include <tuple>

using std::cout;

using std::endl;

struct I {

/* HIGH, TRUE, ONE */

};

struct O {

/*LOW, FALSE, ZERO */

};

Обрати внимание, что здесь мы только определили две структуры — без каких-либо конкретных переменных. Структура представляет собой тип в программе, и именно отличие типа I от типа O будет определять различие в состояниях бита в наших цифровых схемах.

Пойдем дальше и создадим пару байтов с помощью встроенных в язык С++ кортежей (они появились в С++11). Для этого используем директиву using, которая по сути представляет собой продвинутый вариант typedef из языка С. Опять же важно заметить: с их помощью мы не создаем новой переменной, а только лишь объявляем некоторый новый тип.

1 2	using op1 = std::tuple< O, O, O, O, I, O, I, I >; using op2 = std::tuple< O, I, O, O, O, O, I, O >;

Выведем наши типы на экран и убедимся, что все работает без ошибок. Здесь мы впервые применяем шаблон функции, чтобы в зависимости от параметра шаблона выводить на экран нули и единицы. Пока ничего сложного.

template<typename T>

void _print();

template<>

void _print<O>() {

cout << "O " << endl;

}

template<>

void _print<I>() {

cout << "I " << endl;

}

Настало время перейти к логическим элементам. Если ты читал мои статьи из цикла «Основы цифровой схемотехники», то наверняка помнишь, что операция И-НЕ (NAND) образует полноценный базис, на основе которого можно в дальнейшем строить любые другие схемы. Я хочу как можно быстрее получить возможность проектировать новые вентили из уже имеющихся, поэтому начнем с И-НЕ.

template<typename A, typename B>

struct NAND {

using result = std::conditional_t<(std::is_same<A, B>::value &&

std::is_same<A, I>::value), O, I>;

};

В целом не самый сложный кусочек кода, но на всякий случай разберем его подробнее, чтобы в дальнейшем не возвращаться к очевидным вещам. Тут мы объявляем шаблон структуры с двумя шаблонными параметрами. В составе этой структуры единственное «поле» — директива using, которая выводит тип результата как возвращаемое значение шаблона std::conditional_t.

Этот шаблон имеет вид std::conditional_t<условие, тип1, тип2> и по сути является аналогом тернарного оператора ? : из стандартного С++. Если условие (первый параметр) принимает значение true, то возвращается тип1 (второй параметр), иначе — тип2 (третий параметр).

По аналогии с тернарным оператором инструкции std::conditional_t можно вкладывать друг в друга, формируя тем самым выбор сразу из нескольких доступных вариантов. Более того, можно совмещать последовательности std::conditional с тернарными операторами в качестве выражения для выведения первого параметра. Таким образом, у нас есть полноценная возможность программировать нетривиальную логику элементов. Хотя, конечно, монструозный вид подобных конструкций несколько настораживает (спойлер: то ли еще будет!).

Шаблон std::is_same гораздо тривиальнее в применении и банально сравнивает типы в своих угловых скобках. Значение результата (логический ноль или единица) можно забрать из его поля value.

Тут возникает первая возможность «грязного» хака. Формально ничто не мешает нам не сравнивать типы наших шаблонных параметров напрямую. Мы вполне можем определить шаблон функции, которая бы сводила наши пользовательские типы к стандартному типу bool, и, таким образом, строить логику и внутреннее представление элемента на его основе. Что-то типа такого:

template<typename T>

bool state();

template<>

bool state<O>() {

return false;

}

template<>

bool state<I>() {

return true;

}

template<typename A, typename B>

struct NAND {

using result = std::conditional_t<(state<A>() == state<B>()) &&

(state<A>() == true), O, I>;

};

Но я так делать, конечно, не буду. Это все равно что играть в видеоигры на легком уровне сложности — никакой радости от достижения результата.

Код для всех остальных базовых блоков выводится уже с помощью нашей структуры NAND и выглядит так:

template<typename A, typename B = A>

struct NOT {

using result = typename NAND<A,A>::result;

};

template<typename A, typename B>

struct AND {

using result = typename NOT<typename NAND<A, B>::result>::result;

};

template<typename A, typename B>

struct OR {

using result = typename NAND<typename NOT<A>::result,

typename NOT<B>::result>::result;

};

template<typename A, typename B>

struct NOR {

using result = typename NOT<typename OR<A, B>::result>::result;

};

template<typename A, typename B>

struct XOR {

using result = typename NAND<typename NAND<typename NAND<A, B>::result, A>::result, typename NAND<typename NAND<A, B>::result, B>::result>::result;

};

В целом понять, почему некоторые критикуют механизм шаблонов в С++, уже можно. Считая угловые скобочки в выражении для вентиля XOR, невольно даже проникаешься мыслью, что часть этой критики вполне объективна и обоснованна. Слабые духом личности в этот момент переходят на Python или JS, но мы не сдаемся.

В самом деле, не все так плохо. Располагая базовыми блоками, собрать полусумматор и сумматор достаточно просто:

template<typename A, typename B>

struct HALFADDER {

using sum = typename XOR<A, B>::result;

using carry = typename AND<A, B>::result;

};

template<typename A, typename B, typename C = O>

struct FULLADDER {

using sum = typename HALFADDER<typename HALFADDER<A, B>::sum, C>::sum;

using carry = typename OR<HALFADDER<A, B>::carry, HALFADDER<A, B>::sum, C>::carry>::value;

};

Обрати внимание, что в нескольких местах при описании списка шаблонных параметров шаблона мы задаем параметры по умолчанию. Это упрощает интерфейс наших логических элементов. В дальнейшем я планирую использовать шаблоны этих структур как шаблонные параметры структуры регистров. И тут унифицированный интерфейс придется как нельзя кстати.

Действительно, стандартно функция отрицания НЕ ( NOT) принимает на вход только один параметр. Но в целях стандартизации мы унифицируем ее список шаблонных параметров с остальными вентилями, добавляя второй «вход В», чтобы иметь возможность применять ее даже в тех местах, где требуются два входа. Аналогично и с шаблоном сумматора.

В ушах — бит, в классе — тип

Прежде чем мы перейдем к рассмотрению вложенных шаблонов структур (классов) и шаблонов в качестве параметров шаблонов (в том числе использованию шаблона контейнера std::tuple), предлагаю сделать небольшое лирическое отступление и более детально рассмотреть взаимоотношения между нашими абстрактными категориями.

Как правило, мало у кого возникают трудности с восприятием переменных в программе (за исключением, быть может, переменных — указателей на переменные). Любая переменная (если ее в процессе безжалостно не отоптимизировал компилятор) располагается в памяти и занимает какое-то количество байтов. Где именно эта переменная оказалась — на стеке, в куче или в статической памяти, не столь уж и важно.

Тип переменной, напротив, в программу никак явно не попал. В методологии ООП, которой стараются придерживаться в С++, класс представляет собой тип, а конкретный объект класса — переменную, сконструированную по некоторому шаблону. Сколько полей имеет объект, какие права доступа к ним — все это содержится в определении класса.

РЕКОМЕНДУЕМ:
Как снять дамп прошивки и получить доступ к консоли управления гаджета

Таким образом, принцип шаблонов, порождающих новые сущности в нашей программе, появляется на самом деле гораздо раньше. Под другим именем, но это уже детали. Шаблоны классов, в свою очередь, не определяют какой-либо новый тип. Но они определяют принцип, по которому этот тип может быть сконструирован.

Сам по себе шаблон структуры NAND не имеет смысла далее в нашей программе, за исключением применения в каком-либо списке параметров в качестве шаблонного параметра шаблона. Что именно интересует компилятор после его определения, так это конкретизация шаблонной структуры NAND с помощью существующих типов. В нашем случае это O и I. Только тогда появляется новый тип (при условии, что определение шаблонной структуры допускает такое использование).

Резюмируя: в метапрограммировании С++ шаблон — это тип, а тип — это переменная. В сущности, не так уж и сложно.

Рекурсия — бессердечная ты…

Наша основная проблема — переменные в их изначальном, «традиционном» понимании отсутствуют. У нас есть параметры шаблона (они могут быть целочисленными) — но это немного не то. Параметры определяют конкретный тип, а внутри этого типа они константны. Чтобы проиллюстрировать это, попробуем итерировать наш кортеж (он же «байт») и вывести его на экран.

using byte = std::tuple< O, I, O, I, O, I, O, I>;

template<int N>

struct bit {

static void out() {

print<std::tuple_element_t<N, byte>>();

}

};

Это слабо приблизило нас к успеху. Нам по-прежнему нужно пройтись по битам от нуля до семи, чтобы напечатать их состояния. Циклы while или for решили бы нашу проблему, но они требуют «настоящих» переменных. Блеск и нищета «плюсовых» шаблонов в этот момент видны особенно отчетливо.

Как ты наверняка уже догадался, нас спасет рекурсия. Мы рекурсивно пройдем в нашей структуре каждый элемент, ровно до точки выхода, которую придется конкретизировать для шаблона структуры. Это завершит стек вызовов, и компилятор пройдет обратно, формируя код для вывода элементов кортежа на экран. Посмотрим, как это выглядит на практике:

template<typename T, int N = std::tuple_size<T> - 1>

struct print {

static void out() {

print<T, N — 1>::out();

_print<std::tuple_element_t<N, T>>();

}

};

template<typename T>

struct print<T, 0> {

static void out() {

_print<std::tuple_element_t<0, T>>;

}

};

Сам вывод на экран придется осуществить в рантайме. Аналогом потока cout, наверное, могла бы стать печать отладочных сообщений времени компиляции, типа директивы препроцессора #warning или static_assert. Но эксперименты с этим я, пожалуй, отложу на следующий раз.

int main() {

cout << "Byte is: ";

print<byte>::out();

cout << endl;

}

$ g++ tmpl.cpp -Os -o tmpl -std=c++17

$ ./tmpl

Byte is: O I O I O I O I

Шаблонный шабаш

Теперь перейдем к основной части, ради чего все, собственно, и затевалось. Я бы хотел в своем симуляторе оперировать не отдельными логическими вентилями, а целыми блоками. Примерно как микросхемы объединяют несколько элементов в одном корпусе, я планирую использовать регистры, в основу которых лягут наши шаблоны NAND, OR, AND и другие.

При этом ширина регистра — это параметр, тип используемой функции — параметр (шаблонный параметр шаблона, если точнее), операнды — тоже параметры. Ах да, скорее всего, еще потребуется рекурсия и связанный с ней счетчик. Еще один параметр. Ну и совсем хорошо, если это будет вменяемо выглядеть. В целом меня устроит какой-то такой синтаксис:

1	using result = BYTE::XOR::OP<OP1, OP2>::result;

Здесь BYTE — это ширина результата (восемь бит), XOR — тип используемой логической функции (исключающее ИЛИ), OP1 и OP2 — операнды (существующие к этому моменту в программе), а result — конечный результат вычислений. По-моему, достаточно симпатично. По сути, нам удалось сократить число параметров до двух, как и число угловых скобочек.

Начнем с простого:

template<int D>

struct DIM { /* result`s width */

template<template <typename, typename> class T0>

struct EXP { /* type of expression */

template<typename OP1, typename OP2 = OP1>

struct OP { /* operands */

...

};

Теперь нам нужно определить выражение для вычисления результата. Собирать результат будем итеративно, по битам, поэтому сперва выведем его.

template<int N>

using bit = typename T0<std::tuple_element_t<N, OP1>,

std::tuple_element_t<N, OP2>>::result;

Мы забираем по элементу из кортежей наших операндов и применяем к ним битовую логическую операцию. Это понятно, но как нам теперь собрать весь байт результата (или несколько)?

Предположим, что у нас уже есть один бит. Значит, нужно вычислить остальные. Они к нам придут в формате кортежа, который нужно будет «склеить» с нашим промежуточным результатом в новый кортеж. И так по цепочке, пока мы не пройдем весь регистр до двух крайних битов, из которых можно будет сделать обычный кортеж прямо на месте. Это и будет условием выхода для нашей рекурсии.

Выразим все в коде:

template<int N = D>

using result = decltype(std::tuple_cat(std::declval<std::tuple<bit<N>>>(),

std::declval<typename DIM<D>::template

typename EXP<T0>::template

typename OP<OP1, OP2>::template

result<D - 1>>()));

Думаю, без комментариев тут обойтись не получится. Мы склеиваем кортеж с помощью функции std::tuple_cat. Так как она возвращает некоторое промежуточное представление нашего кортежа, мы используем decltype для получения действительного типа результата. Кроме того, уже имеющийся бит мы тоже оборачиваем в кортеж, чтобы его можно было использовать в функции конкатенации. Дополнительно нам помогает шаблон std::declval — он возвращает тип результата, который мы могли бы получить, если бы дело происходило в рантайме.

Осталось разобраться с «хвостом». Это громоздкое выражение по сути означает следующее: «я хочу получить тип результата ( typename), который образуется в конкретном шаблонном варианте структуры DIM, содержащей результат во вложенном шаблоне ( template) другой структуры ( typename), которая, в свою очередь, содержит…» и так далее. Думаю, принцип ты понял. Остается только выяснить, будет ли это работать?

РЕКОМЕНДУЕМ:
Прием и декодирование сигналов из космоса Inmarsat и Iridium

Нет, не будет. Мы забыли про рекурсию. Она требует свой собственный шаблонный параметр и, как мы обсуждали, условие выхода, реализованное в качестве конкретизации шаблона некоторым значением. Наша проблема в том, что частичная конкретизация вложенного шаблона (без конкретизации внешних шаблонов) запрещена стандартом языка. Такие дела: либо определяй все полностью, либо никак.

Поэтому нам придется вытащить параметр условия на верхний уровень, чтобы была возможность далее определить конкретизацию для самого глубокого случая (два последних бита результата). Догадался до этого я не сразу, но это и впрямь не самая очевидная вещь.

template<int D, int d = 0>

struct DIM {

…

template<int N = d>

using result = decltype(std::tuple_cat(std::declval<std::tuple<bit<N>>>(),

std::declval<typename DIM<D, N + 1>::template

typename EXP<T0>::template

typename OP<OP1, OP2>::template

result<N + 1>>()));

Теперь определим условие выхода для нашего выражения:

template<int D>

struct DIM<D, D - 2> {

template<template <typename, typename> class T0>

struct EXP {

template<typename OP1, typename OP2>

struct OP {

template<int N>

using bit = typename T0<std::tuple_element_t<N, OP1>,

std::tuple_element_t<N, OP2>>::result;

template<int N>

using result = decltype(std::tuple_cat(std::declval<std::tuple<bit<D - 2>>>(),

std::declval<std::tuple<bit<D - 1>>>()));

};

Готово, можно выдохнуть. Теперь нашими, кхм-м, сущностями можно пользоваться далее в программе.

using value = DIM<8>::EXP<XOR>::OP<byte1, byte2>::result<>;

int main() {

print<value>();

cout << endl;

}

Финальные штрихи

Шаблоны работают, но форма записи пока еще далека от совершенства. Предлагаю ее слегка упростить. Для этого в первую очередь объявим псевдонимы для размерности наших регистров.

using BIT = DIM<1>;

using BYTE = DIM<8>; /* Atmel’s AVR simulation */

using WORD = DIM<16>; /* Microchip’s PIC24 */

using DWORD = DIM<32>; /* ARM’s Cortex-M */

using QWORD = DIM<64>; /* Intel’s Core family */

Кроме того, псевдонимы можно объявить и для конкретных операций. Я переименовал NAND, OR и остальные с приставкой из нижнего подчеркивания и уже в шаблоне DIM добавил следующие объявления:

using NAND = EXP<_NAND>;

using NOT = EXP<_NOT>;

using AND = EXP<_AND>;

using OR = EXP<_OR>;

using XOR = EXP<_XOR>;

Верхний регистр был выбран везде сознательно, так как символы or, and, not и остальные зарезервированы компилятором для его собственных логических операций. Насколько я помню, это было нововведением стандарта С++03, но откатываться на С++98 ради них одних как-то не было желания. Заключительные изменения пришлись на шаблон DIM. Лишний параметр в списке не давал мне покоя, и я сделал так, чтобы он наследовался от этой структуры, скрыв его таким образом в базовом классе:

template<int D>

struct DIM : public _DIM<D> {

};

Наконец, я убрал угловые скобочки из поля result и добавил шаблонное поле для отдельных битов:

using result = _result<0>;

template<int N>

using bit = typename std::tuple_element_t<N, result>;

В результате вызов main выглядит теперь следующим образом:

using R1 = BYTE::NOT<OP1>::result;

using R2 = BYTE::XOR<OP1, OP2>::result;

int main() {

print<R1>();

cout << endl;

print<R2>();

cout << endl;

}

Иллюзорность кода

Однако самый главный вопрос остается открытым: что в итоге? Получится ли у компилятора разобрать все наши выражения и не утечет ли часть вычислений в рантайм? По идее, как будто бы не должна, но лучше проверить. Для этого в одной папке с файлом tmpl.cpp я создал еще smpl.cpp со следующим кодом:

#include <iostream>

int main() {

std::cout << "O I O O I I O I" << std::endl;

std::cout << "O O O I I O I O" << std::endl;

}

И скомпилировал их с одними и теми же настройками. Бинарники не совпали до байта, но оказались практически схожих размеров. Беглый анализ ассемблерного листинга выявил причину: в tmpl вывод выполнялся посимвольно, а в smpl сразу целыми строками.

$stat -f "Size: %z" smpl

Size: 10620

$stat -f "Size: %z" tmpl

Size: 10652

Как видишь, магия нашей шаблонной метапрограммы действительно рассеялась при компиляции, а множественные абстрактные типы бесследно исчезли, как только дело дошло до реального выполнения. В этом определенно что-то есть, что-то поэтическое и мимолетное. Я только пока не понял, что именно.