I love C++. It is my second favourite language. The depth of its design and the amount of features it proposes is truly out there. I am sometimes afraid that it will consume me, like an indescribable, immemorial eldritch horror; and once or twice when I contemplate the Abyss, g++ stares back at me, immobile, unquenched…

One (1) abyssal g++ error

One (1) abyssal g++ error

But anyway. You know what is fun? Compile-time string literals concatenation! Let us do that :3

The problem

The formulation of the problem is rather simple, in fact.

For reasons I will not go into detail right now, I want to be able to provide a string literal as a non-type constant in a template, something like that:

1

hello<"world">

Where hello is a type or a function or whatever really, but inside it I do some combining with the aforementioned string literal:

1
2
3
4
5
6
7
8
9

template<??? s>
struct hello {
    static constexpr ??? message = "Hello, " + s + "!";
};

int main() {
    std::cout << hello<"world">::message << "\n";
    return 0;
}

All that without using any library, including the standard library.


Just as a teaser, know that this:

1
2
3
4
5
6
7
8
9

template<auto s>
struct hello {
    static constexpr auto message = "Hello, " + s + "!";
};

int main() {
    std::cout << hello2<"world">::message << "\n";
    return 0;
}

Will, in fact, fail spectacularly, with one of the weirdest error a compiler can come up with:

1
2
3
4
5

test_cstr.cpp: In function ‘int main()’:
test_cstr.cpp:23:32: error: ‘"world"’ is not a valid template argument for type ‘const char*’ because string liter
als can never be used in this context
   23 |     std::cout << hello<"world">::message << "\n";
      |


So, how do I do that (or something close)? How do I allow a template to take as input a string literal and combine it at compile time? What do I replace the ??? with?

That is what we are going to find out!

Weird stuff that exists in C++ that might help us

C++ is rich. My current pet theory is that, whenever a cool paper is accepted at POPL, whatever was developed in said paper will come up in the next C++ standard. You can do everything in C++: functional programming, dependent types, reactive programming; in fact, you may be able to do everything in C++’s template system, including a ray tracer and a Tetris.

I discover new stuff every day in C++, which is part of why I love the language so much: there is always stuff to learn, stuff to try out, and so on.

One such example is that you can pass an array together with its size if it is known at compile time:

1
2
3
4
5
6
7

template<size_t size>
void my_function(int (&my_array)[size]) {
    ...
}

...
my_function({1, 2, 3, 4, 5}); // Guesses size = 5

You read me right. This function can be applied to any array which size is known at compile time, and it summons into the context both the array and the size; is that not wonderful?

This is good news for our purpose, because it means we can handle strings and their size quite easily, especially in constexpr functions. Without that, we would be left with plain old arrays (const char*) without a known length at compile time, making it difficult to allocate “compile-time memory” and have room to combine them.


Speaking of constexpr, it is sometimes a bit hard to grasp what counts as constexpr and what does not. For instance, a for loop with bounds that are constexpr is constexpr:

1
2
3
4
5
6
7
8
9

template<size_t size>
void my_function(char (&my_str)[size]) {
    for (size_t i = 0; i < size; i++) {
        ... my_str[i];
    }
}

...
my_function("abcdefgh");

I think you might be starting to understand where I am getting at…

Let us make a constexpr string wrapper

We will devise a type that stores an array of characters of fixed size, said size being a template argument. This type will have a constructor to build it from an array. In general, everything that can be constexpr, will, so that we can use as much of the type as possible in templates.

Here is how it goes:

1
2
3
4
5
6
7
8
9
10
11
12
13

// Do not mind the typedef 
typedef uint8_t c_size_t;

template<c_size_t Size>
struct str final {
    char _data[Size];

    inline constexpr str(const char(&ct)[Size]) {
        for (c_size_t i = 0; i < Size; i++)
            _data[i] = ct[i];
    }

};

Okay this is a good start. Why not override the array subscript operator, to access the content directly without having to get to the data? While we are at it, let us define a copy constructor, for good measure:

1
2
3
4
5
6
7

inline constexpr str(const str<Size>& other) {
    for (c_size_t i = 0; i < Size; i++) _data[i] = other[i];
}

inline constexpr char operator[](c_size_t i) const {
    return _data[i];
}

One interesting aspect of this design is that we can now overload type conversion to const char*

1
2
3

inline constexpr operator const char*() const {
    return _data;
}

That way, when we have a str, we can just use it in place of a const char* and conversion will happen automatically!

What about concatenating strings?

Recall that we want to be able to add bits of string together using the + operator. This smells like operator overloading, yes; but first, we need to manage the concatenation per se…

This is where it gets kind of strange. We want a constructor that takes two str of potentially different sizes. This constructor builds a str of size Size. So, what are the size of the two str being concatenated?

We could go for Size1 and Size2 but this is not specific enough for the template system. We need to guarantee that Size1 + Size2 = Size + 1 (recall that strings in C/C++ are 0-terminated, so having two strings means we have two zeros, one more than the resulting concatenated string).

Solve for Size2 and you get Size - Size1 + 1, bingo! What is left is to copy everything but the 0 of the first string and then everything including the 0 of the second string (again, for loops with constexpr bounds are constexpr):

1
2
3
4
5

template<c_size_t Size1>
inline constexpr str(const str<Size1>& left, const str<Size - Size1 + 1>& right) {
    for (c_size_t i = 0; i < Size1; i++) _data[i] = left[i];
    for (c_size_t i = 0; i < Size - Size1 + 1; i++) _data[i + Size1 - 1] = right[i];
}

And now there is just one thing left: to define the + overload (outside of the str type):

1
2
3
4

template<c_size_t size1, c_size_t size2>
constexpr str<size1 + size2 - 1> operator+(const str<size1>& left, const str<size2>& right) {
    return str<size1 + size2 - 1>(left, right);
}

Lo and behold: it works!

We have to adapt a little bit the “proof of concept” example (and assuming my str class is in a str namespace):

1
2
3
4
5
6
7
8
9

template<str::str s>
struct hello {
    static constexpr auto message = str::str("Hello, ") + s + str::str("!");
};

int main() {
    std::cout << hello<"world">::message << "\n";
    return 0;
}

And it prints Hello, world! ~wah all of that to print hello world on a terminal…~

Extension: numbers to text?

Okay I am almost satisfied with what I got (at last it aligns with my evil plan). I just need one thing more, that is, the ability to use numbers in the string:

1
2
3
4
5
6

template<uint8_t value>
struct hello2 {
    static constexpr auto message = str::str("Hello, ") + str::dec(value);
};

std::cout << hello2<21>::message << "\n"; // Should output "Hello, 21"

How do we do that? You might have realised that one of the main problem here is that we generate fixed-size strings. What is the length of the string depending on the number?

“Why of course!”, I hear you say, “It is the whole part of log~10~(value)!”

Yeah right. Do you want to compute the base 10 logarithm of an integer in the template system? No? Yeah, thought so.

So basically we have no choice: let us go the ugly road. Let us assume we only want numbers of uint8_t type, which maximum is 255; this means that we need at most 3 digits. So, why not generate those three digits by hand and put them in a string?

1
2
3
4
5
6
7
8

inline constexpr auto dec(uint8_t val) 
    -> str<4> {
    char d1 = (val / 100) + '0';
    char d2 = ((val % 100) / 10) + '0';
    char d3 = (val % 10) + '0';

    return str<4>({ d1, d2, d3, 0 });
}

And voilà! Or… Does it?

1
2

str::cout << hello2<9>::message << "\n";
// Prints: "Hello, 009"

Oh no, it looks like a bad octal number! I do not want that in my secret evil plan!

Okay do not panic. Recall that a 0 ends the string independently from the size of the array. That is:

1

str<4>({ d3, 0, 0, 0 });

This would in fact correspond to a 1-character string (in a size 4 array). So, we can eliminate the leading 0s with a few ifs:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

inline constexpr auto dec(uint8_t val) 
    -> str<4> {
    char d1 = (val / 100) + '0';
    char d2 = ((val % 100) / 10) + '0';
    char d3 = (val % 10) + '0';

    if (d1 == '0') {
        if (d2 == '0') {
            return str<4>({ d3, 0, 0, 0 });
        } else {
            return str<4>({ d2, d3, 0, 0 });
        }
    } else {
        return str<4>({ d1, d2, d3, 0 });
    }
}

And voilà!

1
2
3

str::cout << hello2<9>::message << "\n"; // Prints: "Hello, 9"
str::cout << hello2<99>::message << "\n"; // Prints: "Hello, 99"
str::cout << hello2<199>::message << "\n"; // Prints: "Hello, 199"

This is brutal but it works like a charm! :3

Of course this would have to be rewritten/adapted for a different integer type… But how well…

Why not do that for hex numbers?

The advantage of hexadecimal numbers is that, for a given type coded on n bytes, there are 2 × n digits (+ 0x so really 2 × n + 2). This means that we can write an actual algorithm to transform a number into its hex representation in a string.

The basic principle of the algorithm is as so:

This looks like a recursive algorithm to me. The only thing a bit cumbersome is that we need to keep track of which digit we are generating to properly guess the size of the string coming out of the function.

Of course, generating two digits yields a string of size 3, and if the octet being generated is the n^th^, then the remainder of what is to generate is 2 × n. The resulting string is of size 2 + 2 × n + 1 (do not forget the 0 at the end of the string).

Whenever n = 0, there is nothing left to generate, save for the 0x (of size 3).

Taking all that into account, this is what I came up with:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

template<typename Integer, c_size_t nth>
inline constexpr auto hexn(Integer x)
    -> str<2 + 2 * nth + 1> {
    static constexpr char num[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
    return hexn<Integer, nth - 1>(x / 256) + str<3>({ num[(x % 256) / 16], num[x % 16], 0 });
}

template<typename Integer>
inline constexpr auto hexn<Integer, 0>(Integer x)
    -> str<3> {
    return str("0x");
}

template<typename Integer>
inline constexpr auto hex(Integer x)
    -> str<sizeof(Integer) * 2 + 2 + 1> {
    return hexn<Integer, sizeof(Integer)>(x);
}

Here we see another neat feature of C++: static constexpr arrays in function, which I use to generate the individual digits. Notice also how all this is allowed in constexpr functions despite being recursive!

This works… On paper. In practice, lines 8-9 are not legal C++, because the language forbids this kind of partial specialisation, unfortunately. This means that we have to provide full specialisation, one for each type we want to cover :(

1
2
3
4
5
6
7
8
9
10
11

template<>
inline constexpr auto hexn<uint8_t, 0>(uint8_t x)
    -> str<3> {
    return str("0x");
}

template<>
inline constexpr auto hexn<uint16_t, 0>(uint16_t x)
    -> str<3> {
    return str("0x");
}

Not ideal, but at least that works! :3

1
2
3
4
5
6

template<uint16_t value>
struct hello3 {
    static constexpr auto message = str::str("Hello, ") + str::hex<uint16_t>(value);
};

std::cout << hello3<0x0123>::message << "\n"; // Outputs "Hello, 0x0123"!!

The real deal: generating inline asm

Now I hope you did not think that my ultimate goal was to generate static constexpr strings to be output by cout. Although this is very fun and all, this is mostly useless, in fact.

My true goal stems from a simple webpage I read, taken from the GNU GCC documentation, in which one can read:

In C++ with -std=gnu++11 or later, strings that appear in asm syntax—specifically, the assembler template, constraints, and clobbers—can be specified as parenthesized compile-time constant expressions as well as by string literals.

Meaning, the content of an asm template can be a constexpr string literal, meaning, we can generate it using our system, at compile time! MWAHAHAHAH!

Note that there is a catch though (that is not mentioned in this part of the doc), valid “string literal-like” objects must define a data() and size() method, the former converting the literal to a const char* and the second yielding the size of the string.

That is alright, we can add that to str:

1
2
3
4
5
6
7

inline constexpr const char* data() const {
    return _data;
}

inline constexpr c_size_t size() const {
    return Size;
}

And now the goal is to generate, at compile time, inline assembly for AVR type microcontroller (which assembly is rather simple, especially compared to x86).

Thus, we may write stupid stuff like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

template<str::str rname, uint8_t value>
struct ldi {
    static constexpr auto loadasm = str::str("ldi ") + rname + str::str(", ") + str::hex(value);

    static inline void operator()() {
        asm volatile((loadasm) ::: (rname));
    }
};

template<str::str rname, uint16_t address>
struct lds {
    static constexpr auto loadasm = str::str("lds ") + rname + str::str(", ") + str::hex(address);

    static inline void operator()() {
        asm volatile((loadasm) ::: (rname));
    }
};

int main() {
    ldi<"r21",0x12>{}();
    lds<"r18",0x3ef4>{}();
    return 0;
}

And when we may generate assembly from that, and we get:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

main:
/* prologue: function */
/* frame size = 0 */
/* stack size = 0 */
.L__stack_usage = 0
/* #APP */
 ;  9 "main.cpp" 1
        ldi r21, 0x12
 ;  0 "" 2
 ;  18 "main.cpp" 1
        lds r18, 0x3EF4
 ;  0 "" 2
/* #NOAPP */
        ldi r24,0
        ldi r25,0
/* epilogue start */
        ret

With the actual generated assembly code between #APP and #NOAPP!! Fantastic!

Conclusion

Generating assembly using constexpr string literal is quite a niche feature, I am not gonna lie (in fact, it lead to me discovering a bug in GCC), but it is quite fun and very powerful, in my opinion.

This is all part of my adventure to program AVR microcontrollers using C++, and inline assembly has its place in that context, for writing lightweight implementations, typically. The problem I had with “normal” asm is that it did not allow a lot of headroom; this problem is now addressed, with the system presented in this article.

Even if you are not interested in inline asm, I think the small bit of code we came up with is quite neat and might get useful for a variety of application.

Of course, there is always more to do; if I had time, I would probably extend the system to involve more types (characters and floating points, typically), and maybe even write various overloads to have a simple “string algebra” on hand, which can be used for further applications.

Feel free to take my code and do just that though, I am happy if it helped you :3