Using Template Metaprogramming for AVR Microcontrollers
AVR
Atmel AVR microcontrollers are well known to developers and do not need any special introduction. These devices use a modified Harvard architecture and demonstrate decent performance with low power consumption. Apparently it is no exaggeration to say that today's popularity of AVR is largely due to the Arduino project.
Arduino
Arduino is an open platform for prototyping. Currently available in a rich variety of different Arduino boards and additional devices. An easy-to-learn subset of the C programming language, along with a rich set of libraries created by enthusiasts from around the world, allow you to create any application to solve an almost unlimited number of tasks. Both a professional and a beginner in programming have the ability to quickly test any idea or create a prototype of the future device in the shortest possible time. However, it is unlikely that anyone will use the Arduino software for real projects. The main reason is the inefficiency of the resulting code [8]. The desire for versatility and simplicity of the Arduino toolkit does not allow to fully use the potential of the AVR microcontroller, its performance and the natural possibilities of parallelism.
Embedded Software Development Approaches
Old school
Representatives of the old school are experts in the field of both software and hardware. Their tools are C language and assembler. Their main goal is to squeeze everything from each byte, to achieve maximum code performance with minimal memory usage and power consumption. At the same time, the code created by them is not always easy to understand, which can greatly complicate further support and development of the code.
New school
People brought up in the epoch of objects tend to see an object in every entity. Classes are a great example of reusable code. The use of classes encourages the developer to achieve a better code structure and thoughtful distribution of responsibilities between components. Properly written object-oriented code is easy to understand and maintain. The disadvantages of code written using C ++ are often its performance. Object-oriented features of the language are its undoubted advantage, but it often has to be paid for. Automatic generation of methods, the implicit creation of temporary objects can lead to a noticeable decrease in
')
C ++ Templates
One of the strengths of C ++ is the template engine. The main idea is the possibility of a generalized definition of code behavior without explicitly specifying the entities used. As an obvious example of using templates, you can cite a standard template library. STL provides three basic types of entities — containers, algorithms, and iterators. Generic containers allow you to specify the required types of stored data at the point of use. Algorithms do not know anything about containers; communication algorithms and containers through the mechanism of iterators. Thus, STL demonstrates amazing flexibility and allows you to solve an infinite number of practical problems.
The undoubted advantage of template classes is that the compiler instantiates only those class methods that are actually used in the code. The rest of the code passes only a syntax correctness check. This eliminates unused code and thus reduces memory consumption. The specialization mechanism allows you to fine-tune the behavior depending on the template parameters, which provides excellent opportunities for code optimization. The disadvantage of templates is the complexity of development and the unfriendliness of the compiler to the template code.
The idea of templates is easiest to show by example:
Suppose we need the min function to work with integers. The obvious solution for a C programmer would be something like:
int min(int a, int b) { return (a < b) ? a : b; } If a similar function is needed for working with a floating point, you will have to write another function:
float min(float a, float b) { return (a < b) ? a : b; }
Each new type will require a new feature.
For a C ++ programmer, the problem is solved by writing something like the following template:
template<typename T> T min(T a, T b) { return (a < b) ? a : b; }
In this case, the type of values used is not explicitly indicated; instead, we use the notation T, which is present in the template definition with the keyword typename. For template functions (as well as class methods), the compiler is able to independently deduce the required parameter type based on the types of values passed. If a pair of parameters with different types is passed to this min function, the compiler will justifiably express its dissatisfaction. Moreover, if the transfer of parameters of different types is done intentionally, it is possible to help the compiler by explicitly specifying the type of the template parameter when calling the function:
float float_variable = 3.141; int integer_variable = 3; int result = min<int>(float_variable, integer_variable);
or depending on what you need:
float result = min<float>(float_variable, integer_variable);
The function declared in this way can work with any data type, the only condition is the presence of the operation "<" (less) defined for this type. This is very similar to the behavior of languages with dynamic typing, but there is a fundamental difference. In languages like Python, a function can exist in a single copy. Being a language with
Very convenient, but it is this circumstance that can cause another problem of the templates - the code bloat. This particular function is not a problem, since it is small in size and is an obvious candidate for inlining. However, the presence in the code of many differently parameterized instances of template classes that have volumetric methods can actually lead to a significant increase in the code, thus creating a real problem. Todd Veldhuzen makes recommendations [5] to avoid this.
Meta programming
In 1994, at a meeting of the C ++ Standardization Committee, Erwin Unruh for the first time demonstrated the ability to perform computations at the compilation stage. During the compilation process, the code presented to them produced a series of diagnostic messages containing the values of a series of prime numbers. Further studies have shown that the possibilities of performing mathematical operations are computationally complete [6]: indeed, it is possible to use arithmetic operations, organize cycles through the use of recursion, and branching through the use of specializations.
Some similarity between patterns and habitual execution time functions was noticed [3].
The template parameters play the role of the parameters of ordinary functions, and the nested types and constant values of enumerated types are analogous to the returned values. As parameters of metafunctions and return values, the same entities that can be template parameters can be used, these include:
- constant values of enumerated types,
- types as well
- pointers
1. The simplest and most understandable case is the use of enumerated types.
The following meta-function raises the value of BASE to the power of PWR.
template // < unsigned PWR, unsigned BASE = 10 // // > struct power { enum{value = BASE * power<PWR-1,BASE>::value}; }; template<unsigned BASE> // struct power<0,BASE> { enum{value = 1}; };
As you can see, to calculate the result, the power pattern calls itself recursively with a modified PWR value. To prevent infinite recursion, specialization is needed, in this case for a zero PWR value.
Usage example:
unsigned KILO = power<3,10>::value; // KILO 1000 unsigned MEGA = power<6,10>::value; // MEGA 1000000 unsigned kBytes = power<10,2>::value; // kBytes 1024
2. Calculations over types
Imagine that we need to pass an input parameter of type ValueType to the function. We would like the optimal method for passing a parameter (by a constant link or by value) to be selected automatically, depending on the target platform and the size of a particular type of parameter.
template < typename ValueType > struct PARAM { typedef typename type_selector< (sizeof(ValueType*) < sizeof(ValueType)), const ValueType&, ValueType >::type type; };
The type_selector template used inside our meta-function is described by many authors [for example 3, 4] and may look like this:
template // < bool CONDITION, // typename TYPE0, // , , typename TYPE1 // , , > struct type_selector { typedef TYPE0 type; }; // CONDITION == false template<typename TYPE0,typename TYPE1> struct type_selector<0,TYPE0,TYPE1> { typedef TYPE1 type; };
Depending on the value of the CONDITION condition, the type_selector template selects either TYPE0 (CONDITION == true) or TYPE1 (CONDITION == false). As a condition in this case, we use the logical expression: sizeof (ValueType)> sizeof (ValueType *). For example, if the parameter is of type uint32_t, we use the following definition for our function:
void function(typename PARAM<uint32_t>::type value){...}
In this case, the compiler requires the typename keyword to be specified before referring to the template, since the type used to pass the parameter is nested. Such a declaration / definition of a function looks somewhat cumbersome, however, the task is solved: - on 32 and 64-bit platforms the parameter will be passed by value, and for example, if compiled under an AVR microcontroller, where the address size is two bytes, the parameter will be transmitted by a constant link.
3. Pointers as template parameters
Suppose, inside some code, we need to make a callback call, a function whose type is defined as:
typedef void (*CALLBACK_FUNCTION_TYPE)(); // callback
Now, by defining our code as a template:
// cb_func, // CALLBACK_FUNCTION_TYPE template<CALLBACK_FUNCTION_TYPE cb_func> void some_code(...) { ... cb_func(); // ... }
we can pass the required function when calling our code as follows:
some_code<&our_callback_function>(...);
Since the address of our_callback_function is known at compile time, it can be successfully inlined by the compiler [5]. You can read about the impact of embedding functions on the size and efficiency of a code [7] - the three chapters of this book are entirely devoted to issues of embedding functions. In his article [5], Todd Veldhusen demonstrates very interesting examples of using meta-functions, including loop unfolding using the example of the dotproduct function for matrix multiplication, the calculation of trigonometric constants for Fast Fourier Transform algorithms by summing a series. Here it is important to understand that during execution all these actions have zero cost, since they are performed at the compilation stage.
Design
When it comes to code that is supposed to be used repeatedly, the question of the interface comes to the fore. The importance of a well-defined interface has been repeatedly discussed on the Web. The set of requirements traditionally imposed on a good interface includes correctly defined abstractions, hiding implementation details, minimality and sufficiency, ease of use, complexity or impossibility of improper use, and others [9]. When using metaprogramming, some of the requirements can be realized only by great efforts, and some may not be realized at all. The fact that the language property used in our case was discovered by chance, explains the reason for the rather awkward syntax. This does not add convenience when developing metaprogram code and using template-based interfaces. The impossibility of specifying diagnostic messages during compilation makes control over the correct use of the code difficult to implement, although some attempts have been made in this direction, for example Static assertions in the boost library and new language standards.
When developing code to control a hardware device, you must provide the user with full control over all of his (device) components. At the same time the requirement of minimality in the interface remains. A reasonable approach here seems to be the use of the correct order of parameters in the device interface. The most frequently changed parameters should go first, for all others (parameters), you should determine the default values corresponding to the most typical use cases.
A convenient approach to building an interface is design using classes of strategies, described in [1, 2]. The idea is very simple. Part of the implemented functionality is delegated to external classes (strategies), which are used as template parameters. If you need to change the behavior, just choose another strategy. This is very similar to the use of parameters of ordinary (runtime) functions, where, thanks to parameters, we have the opportunity to get different results when passing various values of arguments to a function. A function with hard-coded argument values will always return the same result, which does not make much sense. As template parameters (strategies) types (classes) with full functionality can be used. This makes it possible to parameterize the algorithm at the point of use by specifying strategies with the required behavior as template arguments. This gives a new level of flexibility and generalization.
Consider an example implementation of a USART device interface (Universal Synchronous Asynchronous Transceiver) included in a typical AVR controller.
enum USART_ID // { USART0, USART1, USART2, USART3, }; enum BAUD_RATE // { BR_2400 = 2400, ... BR_921600 = 921600, BR_CUSTOM = CUSTOM_BAUD_RATE }; // - ( ) template < BAUD_RATE baud = BR_9600, // (enum) DATA_BITS data_bits = DATA_BITS_8, // (enum) PARITY parity = NO_PARITY, // (enum) STOP_BITS stop_bits = STOP_1, // (enum) ... > struct FRAME_CONTROL;
Strong C ++ typing will require as parameters the specification of values that exactly correspond to the declared data types. For example, to indicate the rate of exchange, only those values that are declared in the BAUD_RATE enumeration can be selected. If you need some special (non-standard) speed value, you can use the value BR_CUSTOM, after announcing the macro CUSTOM_BAUD_RATE with the desired value of the data transfer rate.
The definition of the USART class is as follows:
template < USART_ID id, // (enum) class usart_ctrl = FRAME_CONTROL<>, // - () - FRAME_CONTROL class receiver = USART_RECEIVER<>, // - () - USART_RECEIVER class transmitter = USART_TRANSMITTER<> // - () - USART_TRANSMITTER > struct USART { static void inline init(){...} static size_type send(const uint8_t* data, size_type data_size){...} static size_type print(const char* fmt, ...){...} static size_type _vprintf(const char* fmt, va_list ap){...} ... static void USART_UDRE_handler(){...} };
Here for brevity, the definition of many enumerations and structures is omitted. For use in real code, we include a header file with a description of all these structures using the include directive and determine the required parameters for our device:
#define SEND_BUFFER_SIZE 32 #define RECV_BUFFER_SIZE 16 typedef USART< USART0, FRAME_CONTROL<BR_921600>, RECEIVER_DISABLED, USART_TRANSMITTER<SEND_BUFFER_SIZE> > usart_0; // USART0, 921600 , 8N1, , 32 typedef USART< USART1, FRAME_CONTROL<BR_9600, DATA_BITS_7, EVEN_PARITY, STOP_2> USART_RECEIVER<RECV_BUFFER_SIZE>, USART_TRANSMITTER<SEND_BUFFER_SIZE> > usart_1; // USART1, 9600-7E2, 16 , 32 typedef TWI<400000> I2C; // TWI - 400 kHz
So, the USART structure accepts four template parameters:
- device identifier - allows you to work with any of the four available devices (only Mega256, for lower chips you should use USART0)
- usart_ctrl strategy with a single implementation - FRAME_CONTROL - for the specification of exchange parameters (see above).
- receiver strategy - a receiver for which there are only two implementations - USART_RECEIVER, which allows you to set the required receiver parameters (specify the buffer size and control the interrupt) and RECEIVER_DISABLED, which allows you to disable the receiver if necessary
- transmitter strategy — transmitter parameters with implementations USART_TRANSMITTER (buffer size, interrupt control) and TRANSMITTER_DISABLED, which disables the transmitter and the corresponding interrupts.
This set of strategies provides complete control over the device and, through the use of default values, simplifies the parameterization of the class for the most typical use cases.
Next, we initialize the device:
usart_0::init(); I2C::init();
Here you should pay attention to the unusual syntax of the method call. Instead of the usual “.” Operator, there is a reference to a member of the structure (structure reference), here the operator “::” is used - the disclosure of scope. The fact is that all the methods of the USART class (as well as TWI) are defined as static, and here we work not with objects, but with types. This avoids the overhead of the construction and destruction of the object, and in addition, clearly reflects the singleton-like nature of the device. This does not mean that we completely abandon normal objects in favor of using types and their static members. Most likely, the code will contain many familiar objects, but if we talk about structures for controlling hardware components, this approach makes more sense.
The assembler generated for this (for Mega256) looks something like this:
000000ba <_Z10usart_initv>: ba: 10 92 c4 00 sts 0x00C4, r1 be: 10 92 c5 00 sts 0x00C5, r1 c2: 10 92 c0 00 sts 0x00C0, r1 c6: 88 e2 ldi r24, 0x28 ; 40 c8: 80 93 c1 00 sts 0x00C1, r24 cc: 86 e0 ldi r24, 0x06 ; 6 ce: 80 93 c2 00 sts 0x00C2, r24 d2: 10 92 26 01 sts 0x0126, r1 d6: 08 95 ret 000000d8 <_Z8twi_initv>: d8: 8c e0 ldi r24, 0x0C ; 12 da: 80 93 b8 00 sts 0x00B8, r24 de: 10 92 b9 00 sts 0x00B9, r1 e2: 85 e4 ldi r24, 0x45 ; 69 e4: 80 93 bc 00 sts 0x00BC, r24 e8: 10 92 03 01 sts 0x0103, r1 ec: 08 95 ret
From the above listing, it is clear that calculations of all the necessary constants for initializing devices are performed at the compilation stage.
One more example
If we develop our own exchange protocol, its announcement (using strategies) may look like this:
template < class transport, class params = PROTO_PARAMETERS<...> // - ... > struct SUPER_DUPPER_EXCHANGE_PROTOCOL;
Here the following point is interesting: the transport for the protocol is specified as a template parameter. This allows you to customize our protocol at the point of use, for example:
typedef SUPER_DUPPER_EXCHANGE_PROTOCOL<usart_0, PROTO_PARAMETERS<>, ...> PROTO_SERIAL;
If you wish, we can use the same protocol with another device, such as SPI or TWI, that is:
typedef SUPER_DUPPER_EXCHANGE_PROTOCOL<TWI<200000>, PROTO_PARAMETERS<>, ...> PROTO_TWI;
For strategy classes, there are no additional restrictions, such as the requirement to inherit from a common ancestor. The only requirement for the type used as a transport is the presence of methods (for example, send and receive) with the required signature.
Any necessary number of strategies can be defined, each of which should be responsible for a certain aspect of functionality, thus ensuring their orthogonality [2].
For each strategy, in turn, there may be many different implementations. As a result, the number of different behaviors (many possible combinations of strategies) can be quite large. This provides excellent code flexibility without introducing typical performance problems associated with inheritance and is an excellent example of static polymorphism.
Having thus determined the types we need, we use them in the code as follows:
PROTO_SERIAL::send(data, size); // data usart_0 PROTO_TWI::send(data, size); // data TWI
Debugging
There is no need to repeat that debugging software code is not an easy task. Debugging the template code presents even more difficulties for the developer due to the unfriendliness of the compiler. Any typo in the text leads to the conclusion of long diagnostic listings, which are additionally doubled due to the two-pass compiler mode. It is necessary to read these listings from the very beginning, making the minimum number of code modifications before another compilation attempt. Some messages may be caused by induced errors and disappear when the error is corrected - the root causes.
Pattern specializations are not related to the primary template by any kindred relationship. In fact, the specialization can be considered as a separate independent class, which is substituted for the primary template in case of coincidence of specialized parameters. Thus, in order to be at least somewhat confident in the performance of the template code, you need to at least once instantiate each template specialization. All this makes the process of debugging template code quite a long process.
Debugging embedded code, in turn, can be a nightmare for the developer, especially in the absence of special equipment. In this case, the only way out is the brute force method - inserting debug messages.
Suppose we are debugging the DEVICE class, which has the following interface:
template < class params = DEVICE_SETTINGS<...>, class dbg = NO_DEBUG > struct DEVICE { static uint8_t some_method(uint8_t parameter) { dbg::print("%s:%d\n", __FUNCTION__, parameter); .... dbg:: print("retval:%d\n", retval); return retval; } };
Here we are interested in the template parameter dbg, which by default is initialized with the value NO_DEBUG. dbg::print.
:
typedef DEVICE_SETTINGS<...> DEV_SETTINGS; // typedef typedef DEVICE<DEV_SETTINGS, AVR_DEBUG<usart_0> > device; //
, dbg AVR_DEBUG, usart_0. AVR_DEBUG, :
template < class SENDER > struct AVR_DEBUG { ... static void print(const char* fmt, ...) { va_list ap; va_start(ap, fmt); uint8_t retval = SENDER::_vprintf(fmt, ap); va_end(ap); } };
, , dbg::print print AVR_DEBUG<usart_0>, _vprintf usart_0. , , usart_0.
:
typedef DEVICE<DEV_SETTINGS, NO_DEBUG> device;
or more simply, use the default value NO_DEBUG for the dbg parameter:
typedef DEVICE<DEV_SETTINGS> device;
The implementation of the print function of the NO_DEBUG class has an empty body and may look like this:
struct NO_DEBUG { ... static void inline print(const char* , ...){} };
Here we again rely on a compiler that successfully performs inlining and removal of bodies of empty functions. When assembling the release version of the code, all unused code will be deleted.
Thus, we have a mechanism to control the output of debug information.
Unit tests
Atmel recommends using the minimum data types for storing data in its documents. The recommendation is based on the analysis of the size of the resulting code, reduces the cost of memory used by the application and implies the use of types whose size does not depend on the platform. And this in turn contributes to the creation of a code that has better portability (portability). Ideally, we can get the opportunity to run our code on a PC, which during development allows us to use unit tests. Much of the code intended for the microcontroller can be tested on tests long before it is downloaded to the controller.
, (mock/fake), , .
, PC.
, , (TWI, SPI...) . , , .. . () .
, . , . (COM USB), . , . , , . , .
. SD card SPI ( serial to SPI), , TWI ( serial to TWI).
[ avr_meta ] . avr8-gnu-toolchain-3.4.5.1522-linux, - TUT (C++ Template Unit Test Framework). . , - :
bin , . avr_adc AVR ADC – Analog to Digital Converter avr_debug AVR_DEBUG avr_interrupt/ext_int_control AVR avr_interrupt/pin_ch_int_control Pin Change AVR avr_misc avr_pin AVR avr_power_mgmt AVR avr_spi AVR SPI – Serial Peripheral Interface avr_twi AVR 2-wire Serial Interface ( ) avr_usart AVR USART ( ) container/bit_field bit field container/circular_buffer event_driven meta misc state/led_blinker () state/state_machine state/switch_case switch case
Conclusion
The use of object-oriented features of the C ++ language allows you to improve the structure, readability and clarity of the code. Classes are the perfect embodiment of code reuse.
The flexibility inherent in templates allows the development of a generic and at the same time very efficient code. Independence of the code on the types of data used allows you to make many design decisions at the final stage of development or modify these solutions without significant alterations of the source code.
The use of strategies can provide many variants of code behavior without the use of inheritance and typical performance problems inherent in dynamic polymorphism. Template specializations provide the developer with excellent opportunities to optimize and fine tune code behavior.
C++, 1994 , , . . C++ , , Blitz++ boost::MPL.
, , . ( ) ( ), ( ). C++ (two-level language).
, . , ( ) — . , , , , . , , . [10] , AVR Atmel .
- . , , , [3].
(portability) . , . . , , , , .
, , . - , C ASM .
Literature
1. David Vandevoorde and Nicolai M. Josuttis. C++ Templates: The Complete Guide
2. Andrei Alexandrescu. C++ Design: Generic Programming and Design Patterns Applied
3. David Abrahams and Aleksey Gurtovoy, C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond
4. Davide Di Gennaro. Advanced C++ metaprogramming
5. Todd Veldhuizen. Techniques for Scientific C++. Indiana University Computer Science Technical Report #542
6. Todd L. Veldhuizen. C++ Templates are Turing Complete (2003).
7. Dov Bulka and David Mayhew. Efficient C++. Performance Programming Techniques. Addison-Wesley 2000.
8. Dale Wheat. Arduino Internals. Apress.
9. Martin Reddy. API Design for C++. 2011 Morgan Kaufmann Publishers
10. Christoph Steup, Michael Schulze, Jorg Kaiser. Exploiting Template-Metaprogramming for Highly Adaptable Device Drivers – a Case Study on CANARY an AVR CAN-Driver. Department for Distributed Systems Universitat Magdeburg
11. XXIV . “ . ”.
Source: https://habr.com/ru/post/357910/
All Articles