c++ (XORString): "recursive type or function dependency context too complex"

2

I'm trying to use the following XORString template/macro to encrypt string literals at compile time:

#pragma once

#include <string>

namespace utils {

    template <int X> struct EnsureCompileTime {
        enum : int {
            Value = X
        };
    };

    //Use Compile-Time as seed
#define compile_seed (  (__TIME__[7] - '0') * 1  + (__TIME__[6] - '0') * 10     +   \
                            (__TIME__[4] - '0') * 60   + (__TIME__[3] - '0') * 600  +   \
                            (__TIME__[1] - '0') * 3600 + (__TIME__[0] - '0') * 36000    )

    constexpr int LinearCongruentGenerator(int Rounds) {
        return 1013904223 + 1664525 * ((Rounds > 0) ? LinearCongruentGenerator(Rounds - 1) : compile_seed & 0xFFFFFFFF);
    }

#define Random() EnsureCompileTime<LinearCongruentGenerator(10)>::Value //10 Rounds
#define RandomNumber(Min, Max) (Min + (Random() % (Max - Min + 1)))

    template <int... Pack> struct IndexList {};

    template <typename IndexList, int Right> struct Append;
    template <int... Left, int Right> struct Append<IndexList<Left...>, Right> {
        typedef IndexList<Left..., Right> Result;
    };

    template <int N> struct ConstructIndexList {
        typedef typename Append<typename ConstructIndexList<N - 1>::Result, N - 1>::Result Result;
    };

    template <> struct ConstructIndexList<0> {
        typedef IndexList<> Result;
    };

    template <typename Char, typename IndexList> class XorStringT;
    template <typename Char, int... Index> class XorStringT<Char, IndexList<Index...> > {

    private:
        Char Value[sizeof...(Index)+1];

        static const Char XORKEY = static_cast<Char>(RandomNumber(0, 0xFFFF));

        template <typename Char>
        constexpr Char EncryptCharacterT(const Char Character, int Index) {
            return Character ^ (XORKEY + Index);
        }

    public:
        __forceinline constexpr XorStringT(const Char* const String)
            : Value{ EncryptCharacterT(String[Index], Index)... } {}

        const Char *decrypt() {
            for (int t = 0; t < sizeof...(Index); t++) {
                Value[t] = Value[t] ^ (XORKEY + t);
            }

            Value[sizeof...(Index)] = static_cast<Char>(0);

            return Value;
        }

        const Char *get() {
            return Value;
        }
    };

#define XORSTR( String ) ( utils::XorStringT<char, utils::ConstructIndexList<sizeof( String ) - 1>::Result>( String ).decrypt() )
}

The code is not mine, and I know very little about c++ templates or metaprogramming. The code works as intended on small strings (<250 characters), however, I need to get it working on long strings as well (thousands of characters).

When I use the XORSTR macro on string literals with thousands of characters, I get a "recursive type or function dependency context too complex" error during compilation.

I've tried figuring out exactly what the code does, and it seems like these lines recursively construct some kind of compile-time array (?) from the input string, and the ConstructIndexList line is what generates the error:

template <typename IndexList, int Right> struct Append;
    template <int... Left, int Right> struct Append<IndexList<Left...>, Right> {
        typedef IndexList<Left..., Right> Result;
    };

    template <int N> struct ConstructIndexList {
        typedef typename Append<typename ConstructIndexList<N - 1>::Result, N - 1>::Result Result;
    };

Since I have little knowledge of templates, I'm not sure how exactly to approach this problem.

One idea I had was to pass the macro substrings of the original literal and then concatenate them (in a procedural manner, not manually), however...I have no idea how to do compile-time substring/concatenation operations on literals, and maybe that's impossible.

Another idea was to simply split up my literals manually, passing the split strings to XORSTR individually, and then manually concatenating the results, but that creates a lot of mess in my code....considering that I need to run XORSTR on tens of thousands of characters, and the error pops up when >~250 characters are passed to it.

Any other ideas would be appreciated...or if someone has another compile-time string obfuscation implementation that can take string literals of any arbitrary length...that would be great!

c++
c++11
templates
variadic-templates
template-meta-programming
asked on Stack Overflow Sep 21, 2017 by Tyson • edited Nov 20, 2018 by max66

2 Answers

1

Compilers have limits and you're trying to nest templates to the depth of the length of your string. A few years ago your compiler would have set your computer on fire for this, today you get a nice error message, it's unlikely to improve in the future. (Even if the compiler actually found its way to the end of the string you'd be very unhappy with the speed of your compiles.)

You should consider encoding your literals offline - i.e., with a separate tool that runs (via your makefile or whatever build system you've got) over selected source headers producing generated headers (or cpps, whatever) - the latter of which you #include. Perhaps you can repurpose an existing programmable template generator, or maybe you use an existing tool with "markers" in the code to indicate which strings to encode - awk would work well here - you could even put your strings in a separate "message" file and generate headers from that.

P.S. Some of these limits are documented in the specific compiler's documentation. You could look there for limits on template nesting, or on the number of template variadic parameters, stuff like that. To the best of my knowledge the standard only suggests minimums for these maximum limits, and those are very low.

answered on Stack Overflow Sep 21, 2017 by davidbak • edited Mar 5, 2018 by O'Neil
1

If I'm not wrong, your ConstructIndexList make (rougly) the work of std::make_integer_sequence (available from C++14).

So I suppose you can write

template <typename>
struct cilH;

template <int ... Is>
struct cilH<std::integer_sequence<int, Is...>>
 { using type = IndexList<Is...>; };

template <int N>
struct ConstructIndexList
 { using Result = typename cilH<decltype(std::make_integer_sequence<int, N>{})>::type; };

avoiding you recursion bottleneck.

(but remember to #include <utility>).

But, I suppose, ConstructIndexList can be avoided at all if you use the type std::size_t, instead of int, for your indexes.

I suppose your code can be simplified as follows

#include <array>
#include <string>
#include <utility>
#include <iostream>

namespace utils
 {
   constexpr std::size_t compSeed {
          (__TIME__[7] - '0') * 1U
        + (__TIME__[6] - '0') * 10U
        + (__TIME__[4] - '0') * 60U
        + (__TIME__[3] - '0') * 600U
        + (__TIME__[1] - '0') * 3600U
        + (__TIME__[0] - '0') * 36000U };

   constexpr std::size_t linCongrGen (std::size_t rou)
    { return 1013904223U + 1664525U * ((rou > 0U)
        ? linCongrGen(rou - 1U)
        : compSeed & 0xFFFFFFFFU); }

   constexpr std::size_t randNumber (std::size_t mn, std::size_t mx)
    { return mn + (linCongrGen(10U) % (mx - mn + 1U)); }

   template <typename, typename>
   class XorStringT;

   template <typename Char, std::size_t ... Is>
   class XorStringT<Char, std::index_sequence<Is...>>
    {
      private:
         Char Value[sizeof...(Is)+1U];

         static constexpr Char XORKEY = Char(randNumber(0, 0xFFFF));

      public:
         constexpr XorStringT (Char const * const String)
            : Value{ Char(String[Is] ^ (XORKEY + Is))... }
          { }

         constexpr std::array<Char, sizeof...(Is)+1U> decrypt () const
          { return { { Char(Value[Is] ^ (XORKEY + Is)) ..., Char(0) } }; }

         Char const * get () const
          { return Value; }
    };
 }

template <typename T, std::size_t N>
constexpr auto xorStr (T (&s)[N])
 { return utils::XorStringT<T,
      decltype(std::make_index_sequence<N - 1U>{})>( s ); }

int main()
 {
   constexpr auto xst = xorStr("secrettext");

   std::cout << xst.get() << std::endl;
   std::cout << xst.decrypt().data() << std::endl;
 }
answered on Stack Overflow Sep 21, 2017 by max66 • edited Sep 21, 2017 by max66

User contributions licensed under CC BY-SA 3.0