0

I'm starting with this code, part of an implementation for encrypting/decrypting texts using the Vigenère cipher: [Demo]

#include <algorithm>  // for_each, generate_n
#include <array>
#include <iostream>  // cout

struct Vigenere
{
    static constexpr unsigned char letters_size_{ 26 };
    using square_t = std::array<std::array<unsigned char, letters_size_>, letters_size_>;
    square_t square_{};
    // std::string key_{}  // random size between 5 and 10, random lowercase characters

    Vigenere()
    {
        unsigned char letter{ 'a' };
        std::ranges::for_each(square_, [&letter](auto& row) {
            auto increment_letter = [](unsigned char& c) {
                c = (c == 'z') ? 'a' : c + 1;
            };
            std::generate_n(std::begin(row), row.size(), [&increment_letter, &letter]() {
                auto ret{ letter };
                increment_letter(letter);
                return ret;
            });
            increment_letter(letter);
        });
        // key_ generation...
    }
    // encrypt, decrypt methods...
};

int main()
{
    Vigenere v{};
    for (auto& row : v.square_) {
        for (char c : row) { std::cout << c; }
        std::cout << "\n";
    }
}
  • The encryption/decryption key_ will be different for each struct instance.
  • However, the table of letters, square_, should be the same for all the instances, so I could make it static. [Demo]
    static inline square_t square_{};
  • Furthermore, the table of letters could be created and initialized at compile time. Let's say we have a static consteval square_t build_square() method, and we use it to initialize the table as in static constexpr square_t square_{ build_square() }. [Demo]
    [[nodiscard]] static consteval square_t build_square()
    {
        square_t ret{};

        unsigned char letter{ 'a' };
        std::ranges::for_each(ret, [&letter](auto& row) {
            auto increment_letter = [](unsigned char& c) {
                c = (c == 'z') ? 'a' : c + 1;
            };
            std::generate_n(std::begin(row), row.size(), [&increment_letter, &letter]() {
                auto ret{ letter };
                increment_letter(letter);
                return ret;
            });
            increment_letter(letter);
        });
        return ret;
    }
    static constexpr square_t square_{ build_square() };

The code above does not compile.

source>:28:52: error: 'static consteval Vigenere::square_t Vigenere::build_square()' called in a constant expression before its definition is complete
   28 |     static constexpr square_t square_{ build_square() };
      |                                        ~~~~~~~~~~~~^~

My main question at this point was:

  • Is there a way to initialize square_ at compile time by calling build_square()?
     For this case, I could think of defining and initializing it by writing the table contents by hand. However, that may not be feasible in other situations, so I would like to do it programmatically.

And I found some useful answers in this site, one of which is mentioned in my answer below. However, while implementing that solution, I thought of a second question:

  • Is this code (declaring square as const within the class and defining it as constexpr outside the class) just/about as efficient as defining square_ as constexpr within the class?
rturrado
  • 7,699
  • 6
  • 42
  • 62

1 Answers1

1

There is an answer to a Stack Overflow question explaining why the above code doesn't compile:

It seems the error is produced according to [expr.const] §2:

An expression e is a core constant expression unless the evaluation of e, following the rules of the abstract machine (4.6), would evaluate one of the following expressions:

...

(2.3) — an invocation of an undefined constexpr function or an undefined constexpr constructor;

How come it is undefined, when the call is clearly after the definition?

The thing is, member function definitions are delayed until the closing brace of the outermost enclosing class (because they can see members of enclosing classes).

A solution to this is to declare square_ as const, and define it as constexpr and initialize it outside the struct. This way, at the point of the square_ definition, the constexpr method build_square() will be already defined. [Demo]

struct Vigenere
{
    static constexpr unsigned char letters_size_{ 26 };
    using square_t = std::array<std::array<unsigned char, letters_size_>, letters_size_>;

    static const square_t square_;
};

/* static */ constexpr Vigenere::square_t Vigenere::square_{ Vigenere::build_square() };

There is this other answer to another Stack Overflow question explaining why you can declare members as const and define them as constexpr:

constexpr pertains only to the definition of a variable. [...]
It implies const (on the variable itself: [...]), so you haven’t changed the variable’s type.
This is no different from:

// foo.hpp
extern const int x;

// foo.cpp
constexpr int x=2;

Now, is this latter code (static constexpr square_ definition outside the class) just/about as efficient as what would be to have a static constexpr square_ definition within the class? I.e. with something like this: [Demo]

struct Vigenere
{
    static constexpr unsigned char letters_size_{ 26 };
    using square_t = std::array<std::array<unsigned char, letters_size_>, letters_size_>;

    static constexpr square_t square_{{
        { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' },
        { 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a' },
        { 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b' },
        { 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c' },
        { 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd' },
        { 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e' },
        { 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f' },
        { 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g' },
        { 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h' },
        { 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i' },
        { 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' },
        { 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k' },
        { 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l' },
        { 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm' },
        { 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n' },
        { 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o' },
        { 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p' },
        { 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q' },
        { 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r' },
        { 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's' },
        { 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't' },
        { 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u' },
        { 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v' },
        { 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w' },
        { 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x' },
        { 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y' }
    }};  
};

We can examine the assembler output in Compiler Explorer:

  1. Solution creating the table with static consteval square_t build_square() and defining the table member outside the struct as /* static */ constexpr Vigenere::square_t Vigenere::square_{ Vigenere::build_square() }:
  • The table is indeed generated at compile time.
Vigenere::square_:
        .byte   97
        .byte   98
        .byte   99
        .byte   100
...
  • There is some static initialization and destruction code at the end of the binary, but this code doesn't call build_square(). I understand it is performing the std::array initialization and destruction, and that this happens during the early and final stages of the program execution, respectively.
__static_initialization_and_destruction_0(int, int):
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     DWORD PTR [rbp-4], edi
        mov     DWORD PTR [rbp-8], esi
        cmp     DWORD PTR [rbp-4], 1
        jne     .L18
        cmp     DWORD PTR [rbp-8], 65535
        jne     .L18
        mov     edi, OFFSET FLAT:_ZStL8__ioinit
        call    std::ios_base::Init::Init() [complete object constructor]
        mov     edx, OFFSET FLAT:__dso_handle
        mov     esi, OFFSET FLAT:_ZStL8__ioinit
        mov     edi, OFFSET FLAT:_ZNSt8ios_base4InitD1Ev
        call    __cxa_atexit
.L18:
        nop
        leave
        ret
_GLOBAL__sub_I_main:
        push    rbp
        mov     rbp, rsp
        mov     esi, 65535
        mov     edi, 1
        call    __static_initialization_and_destruction_0(int, int)
        pop     rbp
        ret
  • Interestingly, if square_ is defined with const instead of constexpr, the only difference is the GLOBAL__sub_I_main label at the end of the binary, that is now called _GLOBAL__sub_I_Vigenere::square_.
  1. Solution defining the table as static constexpr square_t square_{ /* values */ } within the struct.
  • The table is also generated at compile time.
Vigenere::square_:
        .ascii  "abcdefghijklmnopqrstuvwxyz"
        .ascii  "bcdefghijklmnopqrstuvwxyza"
        .ascii  "cdefghijklmnopqrstuvwxyzab"
        .ascii  "defghijklmnopqrstuvwxyzabc"
        .ascii  "efghijklmnopqrstuvwxyzabcd"
        .ascii  "fghijklmnopqrstuvwxyzabcde"
        .ascii  "ghijklmnopqrstuvwxyzabcdef"
        .ascii  "hijklmnopqrstuvwxyzabcdefg"
        .ascii  "ijklmnopqrstuvwxyzabcdefgh"
        .ascii  "jklmnopqrstuvwxyzabcdefghi"
        .ascii  "klmnopqrstuvwxyzabcdefghij"
        .ascii  "lmnopqrstuvwxyzabcdefghijk"
        .ascii  "mnopqrstuvwxyzabcdefghijkl"
        .ascii  "nopqrstuvwxyzabcdefghijklm"
        .ascii  "opqrstuvwxyzabcdefghijklmn"
        .ascii  "pqrstuvwxyzabcdefghijklmno"
        .ascii  "qrstuvwxyzabcdefghijklmnop"
        .ascii  "rstuvwxyzabcdefghijklmnopq"
        .ascii  "stuvwxyzabcdefghijklmnopqr"
        .ascii  "tuvwxyzabcdefghijklmnopqrs"
        .ascii  "uvwxyzabcdefghijklmnopqrst"
        .ascii  "vwxyzabcdefghijklmnopqrstu"
        .ascii  "wxyzabcdefghijklmnopqrstuv"
        .ascii  "xyzabcdefghijklmnopqrstuvw"
        .ascii  "yzabcdefghijklmnopqrstuvwx"
        .ascii  "zabcdefghijklmnopqrstuvwxy"
  • The static initialization and destruction code at the end of the binary seems exactly the same as in the first case.
__static_initialization_and_destruction_0(int, int):
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     DWORD PTR [rbp-4], edi
        mov     DWORD PTR [rbp-8], esi
        cmp     DWORD PTR [rbp-4], 1
        jne     .L18
        cmp     DWORD PTR [rbp-8], 65535
        jne     .L18
        mov     edi, OFFSET FLAT:_ZStL8__ioinit
        call    std::ios_base::Init::Init() [complete object constructor]
        mov     edx, OFFSET FLAT:__dso_handle
        mov     esi, OFFSET FLAT:_ZStL8__ioinit
        mov     edi, OFFSET FLAT:_ZNSt8ios_base4InitD1Ev
        call    __cxa_atexit
.L18:
        nop
        leave
        ret
_GLOBAL__sub_I_main:
        push    rbp
        mov     rbp, rsp
        mov     esi, 65535
        mov     edi, 1
        call    __static_initialization_and_destruction_0(int, int)
        pop     rbp
        ret

Conclusion: using a consteval method to create the table, declaring square_ as const within the struct, and defining it as constexpr and initializing it outside the struct:

  1. Creates the table at compile time.
  2. Produces exactly the same code as declaring square_ as constexpr, and defining it and initializing it within the struct (the assembly for the table definition is different, one uses .byte, the other .ascii, but the binary code should be the same).
rturrado
  • 7,699
  • 6
  • 42
  • 62