Find the lowest XOR combination

Question

Consider the following code:

#include <stdio.h> #include <stdlib.h> #include <string.h> int main (int argc, char *argv[]) { time_t seed; time (&seed); srand (seed); int i, j, k, l; // init random values s1 .. s8 int s[8]; for (l = 0; l < 8; l++) s[l] = rand (); // zero result int r[16]; for (j = 0; j < 16; j++) r[j] = 0; // do 100 random xor functions for (i = 0; i < 100; i++) { // generates random function to show why CSE must be computed in runtime int steps[16]; for (j = 0; j < 16; j++) steps[j] = rand (); // _here_ is optimization possible // run function MANY times to show that optimization makes sense for (l = 0; l < 1000000; l++) { for (j = 0; j < 16; j++) { int tmp = 0; for (k = 0; k < 8; k++) tmp ^= ((steps[j] >> k) & 1) ? s[k] : 0; r[j] += tmp; } } for (j = 0; j < 16; j++) printf ("%08x\n", r[j]); puts (""); } return 0; } 

Inside the code, a multiple-time function is executed in loops:

 r[ 0] += s01 ^ s03; r[ 1] += s02 ^ s04; r[ 2] += s03 ^ s05; r[ 3] += s02; r[ 4] += s03; r[ 5] += s04 ^ s06; r[ 6] += s03; r[ 7] += s04; r[ 8] += s02 ^ s04 ^ s05 ^ s07; r[ 9] += s03 ^ s04 ^ s05 ^ s07; r[10] += s04 ^ s05 ^ s06; r[11] += s05 ^ s06 ^ s08; r[12] += s03 ^ s06; r[13] += s06; r[14] += s02 ^ s03 ^ s04 ^ s05 ^ s06 ^ s07; r[15] += s03 ^ s04 ^ s05 ^ s06; 

Makes a total of 23 XOR .

But the implementation is bad. Optimized Version:

 int s04___s05 = s04 ^ s05; int s03___s06 = s03 ^ s06; int s04___s05___s07 = s04___s05 ^ s07; int s03___s04___s05___s06 = s03___s06 ^ s04___s05; r[ 0] += s01 ^ s03; r[ 1] += s02 ^ s04; r[ 2] += s03 ^ s05; r[ 3] += s02; r[ 4] += s03; r[ 5] += s04 ^ s06; r[ 6] += s03; r[ 7] += s04; r[ 8] += s02 ^ s04___s05___s07; r[ 9] += s03 ^ s04___s05___s07; r[10] += s04___s05 ^ s06; r[11] += s05 ^ s06 ^ s08; r[12] += s03___s06; r[13] += s06; r[14] += s02 ^ s03___s04___s05___s06 ^ s07; r[15] += s03___s04___s05___s06; 

Makes a total of 15 XOR .

I am looking for an algorithm that automates this step and finds a solution that uses the lowest XOR number .

If there are several solutions, find the one that has the least amount of storage for precomputing.

If there are several more solutions, it does not matter what to choose.

Additional Information:

• In a real XOR program, functions may be random, as they depend on user input.
• There are always 16 steps.
• The XOR number per step can be between 0 and 7 XOR.
• The amount of memory required for pre-calculated values ​​does not matter.

I lost a little how to write this.

Answer 1

We want to compute r[i] . It is equal to a maximum of 8 XOR'ed inputs between each other.
Now think about it: s8 ^ s6 ^ s5 ^ s4 ^ s3 ^ s2 ^ s1, as well as the number 10111111.
1 if we use the corresponding s in XORing, 0 if not.
We can pre-calculate all possible 2 ^ 8 options:

 t[0] = 0 (00000000, nothing) t[1] = s1 (00000001) t[2] = s2 (00000010) t[3] = s2 ^ s1 (00000011) t[4] = s3 (00000100) t[5] = s3 ^ s1 (00000101) ... t[255] = s8 ^ s7 ^ s6 ^ s5 ^ s4 ^ s3 ^ s2 ^ s1 (11111111) 

Then in a loop, if you want, for example, to calculate:

 r[0] = s1 ^ s3 

s1 ^ s3 in our view 00000101 = 5, which gives us an index for a pre-computed lookup table:

 r[0] = t[5] 

This solves your problem without any XOR cycles.

Answer 2

First, find the definition of an abstract problem: you have a 8-bit long vector type, which is a combination of your 8 input signals. For each signal, you have a bitvector value, for example 10000000 (first signal) or 00100000 (third signal). These values ​​are given. You want to generate the following values ​​(I forgot the trivial ones):

 r[0] = 10100000 r[1] = 01010000 r[2] = 00101000 r[5] = 00010100 r[8] = 01011010 r[9] = 00111010 r[10] = 00011100 r[11] = 00001101 r[12] = 00100100 r[14] = 01111110 r[15] = 00111100 

Now we want to find the minimum combinations ( XOR execution) to generate these values. This is an optimization problem. I will not do full proof for the least amount of XOR executions here, but this is what I get:

 int i1 = s02 ^ s04; // 01010000 int i2 = s03 ^ s05; // 00101000 int i3 = s04 ^ s06; // 00010100 int i4 = s05 ^ s07; // 00001010 int i5 = s03 ^ s06; // 00100100 int i6 = i1 ^ i4; // 01011010 int i7 = i2 ^ i3; // 00111100 int i8 = s06 ^ s07; // 00000110 r[0] = s01 ^ s03; r[1] = i1; r[2] = i2; r[5] = i3; r[8] = i6; r[9] = i7 ^ i8; r[10] = i3 ^ s05; r[11] = i4 ^ i8 ^ s08; r[12] = i5; r[14] = i6 ^ i5; r[15] = i7; 

14 XOR s.

To formulate a general algorithm: you start with Set S={10000000, 01000000, ... , 00000001} . You need a weighing function that tells you the value of your set. Define this as: The XOR number needed to calculate all the target values ​​from the values ​​in S without saving any additional time values plus the number of values ​​in S minus 8 (initial values). The first part of the weighing function can be implemented using brute force (find all possible combinations for the target value that use each value in S no more than once, select the one that runs with the smallest XOR ).

To optimize the value of your weight function, you combine the two values ​​from S with XOR and add them to S , providing S1 . Choose those two values ​​that give the lowest new value of the weight function (again, this can be determined by brute force). S1 now has another value (which will be a temporary value, such as the i values ​​in my solution). To create this value, one XOR is required (therefore, the weight function calculates the number of values ​​in S ).

Continue this step until you find a new value to add to S , which reduces the value of the weighing function. The resulting set contains the initial values ​​plus all the temporary values ​​that you must calculate. The steps you take will tell you how to calculate the closest values.

This is a greedy algorithm. It will not necessarily find the minimum amount of XOR s, but it will show you a simple way to at least get a good solution. Maybe the algorithm actually always finds the best solution, but this should be proved. If you want to be absolutely sure, you can make a complete detour of all possible steps that reduce the value of the weight function, starting with the initial values ​​of S This will be a tree traversal, and the tree will be finite - since the value cannot go below 0 - so it will definitely resolve.

Answer 3

What you did here manually is actually a classic compiler optimization called general sub-expression elimination (CSE).

Before doing this manually or using the tool to execute CSE in the source code, check the resulting assembly to see if your compiler performs CSE for you. Most likely, this is - and note that the compiler is really the place where you need to perform CSE, as there is a trade-off: the more aggressively you perform CSE, the more you reduce the amount of computation you need to do, but you need more storage (then there are registers or RAM). Running CSE too aggressively can hurt performance if it forces you to spill registers or increase memory bandwidth - the compiler will usually have knowledge on how to make such a compromise.