Reputation: 1026

Cartesian product of two arrays in C using preprocessor

I'd like to populate an array with cartesian product of two other arrays. They contain 4-bit values, which should go to lower and upper nibble of the element in the resulting array.

Example:

const char a1[2] = {0x1, 0x2};
const char a2[2] = {0x3, 0x4};

const char a21[4] = {0x31, 0x32, 0x41, 0x42};

I know I can construct it at run-time, but I would like to generate the array at compile-time. As the program is written in C, I think the preprocessor is the only option.

Actual arrays will be bigger than in example, they will contain 16 elements, and the result will contain 256 elements. That is why I would like to avoid typing the values myself.

I need it to speed up an encryption routine on a 16-bit micro-controller, since it can handle larger data than 4-bit nibbles.

I think I will be able to adapt the solution to 16 elements if it works on 2 or 3.

Upvotes: 2

Answers (5)

tstanisl

Reputation: 14157

You could use Xmacro for content of each array. It's similar to other answers but requires no extra libs and it is easy to grasp.

#define A(X, ...) \
    X(1, __VA_ARGS__) \
    X(2, __VA_ARGS__)

#define B(X, ...) \
    X(3, __VA_ARGS__) \
    X(4, __VA_ARGS__)

#define SIMPLE(VAL,...) 0x ##VAL, 
#define JOIN(X,Y,...) 0x ## Y ## X,
#define EXPAND_A(...) A(JOIN, __VA_ARGS__)

const char a1[2] = { A(SIMPLE,) };
const char a2[2] = { B(SIMPLE,) };
const char a21[4] = { B(EXPAND_A,) };

Produces:

const char a1[2] = { 0x1, 0x2, };
const char a2[2] = { 0x3, 0x4, };
const char a21[4] = { 0x31, 0x32, 0x41, 0x42, };

The initializers for a1 and a2 are created with SIMPLE macro. The cartesian product is created by expanding A Xmacro within B Xmacro, finalized by applying JOIN. Extra commas after macro arguments are used to silence C99 compliant compiler that requires ... to contain at least one argument.

Surprisingly an empty token is a valid argument!

Upvotes: 0

Paul Mensonides

Reputation: 126

Using Chaos and a compiler with a good preprocessor (e.g. GCC):

#include <stdio.h>
#include <stdlib.h>

#include <chaos/preprocessor/algorithm/for_each_product.h>
#include <chaos/preprocessor/recursion/expr.h>
#include <chaos/preprocessor/seq/core.h>
#include <chaos/preprocessor/seq/elem.h>
#include <chaos/preprocessor/seq/enumerate.h>

#define A(l, h) \
    const unsigned char \
        a1[] = { CHAOS_PP_SEQ_ENUMERATE(l) }, \
        a2[] = { CHAOS_PP_SEQ_ENUMERATE(h) }, \
        a21[] = { \
            CHAOS_PP_SEQ_ENUMERATE( \
                CHAOS_PP_EXPR(CHAOS_PP_FOR_EACH_PRODUCT( \
                    B, \
                    ((CHAOS_PP_SEQ) l) \
                    ((CHAOS_PP_SEQ) h) \
                )) \
            ) \
        }; \
    /**/
#define B(s, seq) \
    (CHAOS_PP_SEQ_ELEM(0, seq) | (CHAOS_PP_SEQ_ELEM(1, seq) << 4)) \
    /**/

A((0x1)(0x2), (0x3)(0x4))

#undef A
#undef B

int main() {
    for (int i = 0; i != sizeof(a21) / sizeof(unsigned char); ++i) {
        printf("0x%x\n", a21[i]);
    }
    return EXIT_SUCCESS;
}

Upvotes: 2

Alexandr Zarubkin

Reputation: 1026

Okay, so here it comes, the solution I've found in the Internet. In my opinion, it contains tons of mad macros, but it does the job in the end. Of course, generating the array contents in Excel or by script is much easier to understand, but for the sake of completeness, I've decided to post macros solution here.

#define CAT(x, y) CAT_I(x, y)
#define CAT_I(x, y) x ## y

#define APPLY(macro, args) APPLY_I(macro, args)
#define APPLY_I(macro, args) macro args

#define STRIP_PARENS(x) EVAL((STRIP_PARENS_I x), x)
#define STRIP_PARENS_I(...) 1,1

#define EVAL(test, x) EVAL_I(test, x)
#define EVAL_I(test, x) MAYBE_STRIP_PARENS(TEST_ARITY test, x)

#define TEST_ARITY(...) APPLY(TEST_ARITY_I, (__VA_ARGS__, 2, 1))
#define TEST_ARITY_I(a,b,c,...) c

#define MAYBE_STRIP_PARENS(cond, x) MAYBE_STRIP_PARENS_I(cond, x)
#define MAYBE_STRIP_PARENS_I(cond, x) CAT(MAYBE_STRIP_PARENS_, cond)(x)

#define MAYBE_STRIP_PARENS_1(x) x
#define MAYBE_STRIP_PARENS_2(x) APPLY(MAYBE_STRIP_PARENS_2_I, x)
#define MAYBE_STRIP_PARENS_2_I(...) __VA_ARGS__ 

#define M1(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,_11,_12,_13,_14,_15,_16, a) _1 + (a << 4),\
                                                                      _2 + (a << 4),\
                                                                      _3 + (a << 4),\
                                                                      _4 + (a << 4),\
                                                                      _5 + (a << 4),\
                                                                      _6 + (a << 4),\
                                                                      _7 + (a << 4),\
                                                                      _8 + (a << 4),\
                                                                      _9 + (a << 4),\
                                                                      _10 + (a << 4),\
                                                                      _11 + (a << 4),\
                                                                      _12 + (a << 4),\
                                                                      _13 + (a << 4),\
                                                                      _14 + (a << 4),\
                                                                      _15 + (a << 4),\
                                                                      _16 + (a << 4),
#define M2(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,_11,_12,_13,_14,_15,_16, a) M1(a, _1)\
                                                                      M1(a, _2)\
                                                                      M1(a, _3)\
                                                                      M1(a, _4)\
                                                                      M1(a, _5)\
                                                                      M1(a, _6)\
                                                                      M1(a, _7)\
                                                                      M1(a, _8)\
                                                                      M1(a, _9)\
                                                                      M1(a, _10)\
                                                                      M1(a, _11)\
                                                                      M1(a, _12)\
                                                                      M1(a, _13)\
                                                                      M1(a, _14)\
                                                                      M1(a, _15)\
                                                                      M1(a, _16)
#define M3(a2, a1) M2(a2, STRIP_PARENS(a1))
#define M4(a2, a1) M3(STRIP_PARENS(a2), a1)

// source data (arrays to be combined)
// if anyone is interested, they represent S-boxes of GOST 28147-89 encryption algorithm.
#define s1 (4, 0xA, 9, 2, 0xD, 8, 0, 0xE, 6, 0xB, 1, 0xC, 7, 0xF, 5, 3)
#define s2 (0xE, 0xB, 4, 0xC, 6, 0xD, 0xF, 0xA, 2, 3, 8, 1, 0, 7, 5, 9)
#define s3 (5, 8, 1, 0xD, 0xA, 3, 4, 2, 0xE, 0xF, 0xC, 7, 6, 0, 9, 0xB)
#define s4 (7, 0xD, 0xA, 1, 0, 8, 9, 0xF, 0xE, 4, 6, 0xC, 0xB, 2, 5, 3)
#define s5 (6, 0xC, 7, 1, 5, 0xF, 0xD, 8, 4, 0xA, 9, 0xE, 0, 3, 0xB, 2)
#define s6 (4, 0xB, 0xA, 0, 7, 2, 1, 0xD, 3, 6, 8, 5, 9, 0xC, 0xF, 0xE)
#define s7 (0xD, 0xB, 4, 1, 3, 0xF, 5, 9, 0, 0xA, 0xE, 7, 6, 8, 2, 0xC)
#define s8 (1, 0xF, 0xD, 0, 5, 7, 0xA, 4, 9, 2, 3, 0xE, 6, 0xB, 8, 0xC)

const BYTE s21[256] = {M4(s2, s1)};
const BYTE s43[256] = {M4(s4, s3)};
const BYTE s65[256] = {M4(s6, s5)};
const BYTE s87[256] = {M4(s8, s7)};

Upvotes: 2

Lundin

Reputation: 214780

There is no sane way you can solve this with the pre-processor, if you aim to create readable and maintainable code. The only thing you could do is something like:

#define VAL1_1 0x1
#define VAL1_2 0x2
#define VAL2_1 0x3
#define VAL2_2 0x4

static const char a1[2]  = {VAL1_1, VAL1_2};
static const char a2[2]  = {VAL2_1, VAL2_2};
static const char a21[4] =
{
  VAL1_1 | (VAL2_1 << 4),
  VAL1_2 | (VAL2_1 << 4),
  VAL1_1 | (VAL2_2 << 4),
  VAL1_2 | (VAL2_2 << 4),
};

But this code isn't very generic or maintainable. If this isn't generic enough, then the only sane solution is to generate the source code externally, based on a file with raw input data. Programmers tend to forget that they know programming :) Writing a program which spits out a text file in a given format shouldn't be much of a problem.

You really shouldn't run off and create some pre-processor madness with macros creating other macros etc. That can only end badly.

Upvotes: 0

dbush

Reputation: 224952

What you need is a short piece of code to generate a header file. Something like this:

genheader.c:

#include <stdio.h>

const char a1[] = {0x1, 0x2};
const char a2[] = {0x3, 0x4};

int main()
{
    int i, j, first;

    printf("const char a12[] = {");
    first = 1;
    for (j=0;i<sizeof(a2);j++) {
        for (i=0;i<sizeof(a1);i++) {
            if (first) {
                first = 0;
            } else {
                printf(", ");
            }
            printf("0x%d%d", a2[j], a1[i]);
        }
    }
    printf("};\n");
}

Then run:

gcc -o genheader genheader.c
./genheader > header.h

header.h:

const char a12[] = {0x31, 0x32, 0x41, 0x42};

Upvotes: 0

Cartesian product of two arrays in C using preprocessor

Answers (5)

Related Questions