# Shamir’s Quest: Collect Any 3 Keys To Unlock The Secret!

This post is on something called Shamir’s Secret Sharing. It’s a technique where you can break a secret number up into $M$ different pieces, where if you have any $N$ of those $M$ pieces, you are able to figure out the secret.

Thinking of it in video game terms, imagine there are 10 keys hidden in a level, but you can escape the level whenever you find any 7 of them. This is what Shamir’s Secret Sharing enables you to set up cryptographically.

Interestingly in this case, the term sharing in “secret sharing” doesn’t mean sharing the secret with others. It means breaking the secret up into pieces, or SHARES. Secret sharing means that you make shares out of a secret, such that if you have enough of the shares, you can recover the secret.

## How Do You Share (Split) The Secret?

The basic idea of how it works is actually really simple. This is good for us trying to learn the technique, but also good to show it’s security since there are so few moving parts.

It relies on something called the Unisolvence Theorem which is a fancy label meaning these things:

• If you have a linear equation, it takes two (x,y) points to uniquely identify that line. No matter how you write a linear equation, if it passes through those same two points, it’s mathematically equivelant.
• If you have a quadratic equation, it takes three (x,y) points to uniquely identify that quadratic curve. Again, no matter how you write a quadratic equation, if it passes through those same three points, it’s mathematically equivalent.
• The pattern continues for equations of any degree. Cubic equations require four points to be uniquely identified, Quartic equations require five points, and so on.

At a high level, how this technique works is that the number of shares (keys) you want someone to collect ($N$) defines the degree of an equation.

You use random numbers as the coefficients of the powers of $x$ in that equation, but use your secret number as the constant term.

You then create $M$ data points of the form $(x,y)$ aka $(x,f(x))$. Those are your shares. You then give individual shares to people, or go hide them in your dungeon or do whatever you are going to do with them.

As soon as any one person has $N$ of those $M$ shares (data points), they will be able to figure out the equation of the curve and thus get the secret.

The secret number is the constant term of the polynomial, which is also just $f(0)$.

This image below from wikipedia is great for seeing how you may have two points of a cubic curve, but without a third point you can’t be sure what the quadratic equation is. In fact, there are an infinite number of quadratic curves that pass through any two points! Because of that, it takes the full number of required shares for you to be able to unlock the secret.

## Example: Sharing (Splitting) The Secret

First you decide how many shares you want it to take to unlock the secret. This determines the degree of your equation.

Let’s say you wanted a person to have to have four shares to unlock the secret. This means our equation will be a cubic equation, since it takes four points to uniquely define a cubic equation.

Our equation is:

$f(x) = R_1x^3 + R_2x^2 + R_3x + S$

Where the $R_i$ values are random numbers, and $S$ is the secret value.

Let’s say that our secret value is 435, and that we picked some random numbers for the equation, making the below:

$f(x) = 28x^3 + 64x^2 + 9x + 435$

We now have a function that is uniquely identifiable by any 4 points of data on it’s curve.

Next we decide how many pieces we are going to create total. We need at least 4 so that it is in fact solvable. Let’s make 6 shares.

To do this, you just plug in 6 different values of x and pair each x value with it’s y value. Let’s do that:

$\begin{array}{c|c} x & f(x) \\ \hline 1 & 536 \\ 2 & 933 \\ 3 & 1794 \\ 4 & 3287 \\ 5 & 5580 \\ 6 & 8841 \\ \end{array}$

When doing this part, remember that the secret number is $f(0)$, so make sure and not share what the value of the function is when x is 0!

You could then distribute the shares (data pairs) as you saw fit. Maybe some people are more important, so you give them more than one share, requiring a smaller amount of cooperation with them to unlock the secret.

Share distribution details are totally up to you, but we now have our shares, whereby if you have any of the 4 of the 6 total shares, you can unlock the secret.

## How Do You Join The Secret?

Once you have the right number of shares and you know the degree of the polynomial (pre-shared “public” information), unlocking the secret is a pretty straightforward process too. To unlock the secret, you just need to use ANY method available for creating an equation of the correct degree from a set of data points.

This can be one of several different interpolation techniques, but the most common one to use seems to be Lagrange interpolation, which is something I previously wrote up that you can read about here: Lagrange Interpolation.

Once you have the equation, you can either evaluate $f(0)$, or you can write the equation in polynomial form and the constant term will be the secret value.

## Example: Joining the Secret

Let’s say that we have these four shares and are ready to get the cubic function and then unlock the secret number:

$\begin{array}{c|c} x & y \\ \hline 1 & 536 \\ 2 & 933 \\ 4 & 3287 \\ 6 & 8841 \\ \end{array}$

We could bust out some Lagrange interpolation and figure this out, but let’s be lazy… err efficient I mean. Wolfram alpha can do this for us!

Wolfram Alpha: cubic fit (1, 536), (2, 933), (4, 3287), (6, 8841)

That gives us this equation, saying that it is a perfect fit (which it is!)
$28x^3 + 64x^2 + 9x + 435$

You can see that our constant term (and $f(0)$) is the correct secret value of 435.

Daaaayummm Bru… that is lit AF! We just got hacked by wolfram alpha 😛

## A Small Complication

Unfortunately, the above has a weakness. The weakness is that each share you get gives you a little bit more information about the secret value. You can read more about this in the links section at the end if you want to know more details.

Ideally, you wouldn’t have any information about the secret value until you had the full number of shares required to unlock the secret.

To address this problem, we are going to choose some prime number $k$ and instead of shares being $(x,y)$ data points on the curve, they are going to be $(x,y \bmod k)$. In technical terms we are going to be using points on a finite field, or a Galois field.

The value we choose for $k$ needs to be larger than any of the coefficients of our terms (the random numbers) as well as larger than our secret value and larger than the number of shares we want to create. The larger the better besides that, because a larger $k$ value means a larger “brute force” space to search.

If you want to use this technique in a situation which has real needs for security, please make sure and read more on this technique from more authoritative sources. I’m glossing over the details of security quite a bit, and just trying to give an intuitive understanding of this technique (:

## Source Code

Below is some sample source code that implements Shamir’s Secret Sharing in C++.

I use 64 bit integers, but if you were going to be using this in a realistic situation you could very well overflow 64 bit ints and get the wrong answers. I hit this problem for instance when trying to require more than about 10 shares, using a prime of 257, and generating 50 shares. If you hit the limit of 64 bit ints you can use a multi precision math library instead to have virtually unlimited sized ints. The boost multiprecision header library is a decent choice for multi precision integers, specifically cpp_int.

#include <stdio.h>
#include <array>
#include <vector>
#include <math.h>
#include <random>
#include <assert.h>
#include <stdint.h>
#include <inttypes.h>

typedef int64_t TINT;
typedef std::array<TINT, 2> TShare;
typedef std::vector<TShare> TShares;

class CShamirSecretSharing
{
public:
CShamirSecretSharing (size_t sharesNeeded, TINT prime)
: c_sharesNeeded(sharesNeeded), c_prime(prime)
{
// There needs to be at least 1 share needed
assert(sharesNeeded > 0);
}

// Generate N shares for a secretNumber
TShares GenerateShares (TINT secretNumber, TINT numShares) const
{
// calculate our curve coefficients
std::vector<TINT> coefficients;
{
// store the secret number as the first coefficient;
coefficients.resize((size_t)c_sharesNeeded);
coefficients[0] = secretNumber;

// randomize the rest of the coefficients
std::array<int, std::mt19937::state_size> seed_data;
std::random_device r;
std::generate_n(seed_data.data(), seed_data.size(), std::ref(r));
std::seed_seq seq(std::begin(seed_data), std::end(seed_data));
std::mt19937 gen(seq);
std::uniform_int_distribution<TINT> dis(1, c_prime - 1);
for (TINT i = 1; i < c_sharesNeeded; ++i)
coefficients[(size_t)i] = dis(gen);
}

// generate the shares
TShares shares;
shares.resize((size_t)numShares);
for (size_t i = 0; i < numShares; ++i)
shares[i] = GenerateShare(i + 1, coefficients);
return shares;
}

// use lagrange polynomials to find f(0) of the curve, which is the secret number
TINT JoinShares (const TShares& shares) const
{
// make sure there is at elast the minimum number of shares
assert(shares.size() >= size_t(c_sharesNeeded));

// Sigma summation loop
TINT sum = 0;
for (TINT j = 0; j < c_sharesNeeded; ++j)
{
TINT y_j = shares[(size_t)j][1];

TINT numerator = 1;
TINT denominator = 1;

// Pi product loop
for (TINT m = 0; m < c_sharesNeeded; ++m)
{
if (m == j)
continue;

numerator = (numerator * shares[(size_t)m][0]) % c_prime;
denominator = (denominator * (shares[(size_t)m][0] - shares[(size_t)j][0])) % c_prime;
}

sum = (c_prime + sum + y_j * numerator * modInverse(denominator, c_prime)) % c_prime;
}
return sum;
}

const TINT GetPrime () const { return c_prime; }
const TINT GetSharesNeeded () const { return c_sharesNeeded; }

private:

// Generate a single share in the form of (x, f(x))
TShare GenerateShare (TINT x, const std::vector<TINT>& coefficients) const
{
TINT xpow = x;
TINT y = coefficients[0];
for (TINT i = 1; i < c_sharesNeeded; ++i) {
y += coefficients[(size_t)i] * xpow;
xpow *= x;
}
return{ x, y % c_prime };
}

// Gives the decomposition of the gcd of a and b.  Returns [x,y,z] such that x = gcd(a,b) and y*a + z*b = x
static const std::array<TINT, 3> gcdD (TINT a, TINT b) {
if (b == 0)
return{ a, 1, 0 };

const TINT n = a / b;
const TINT c = a % b;
const std::array<TINT, 3> r = gcdD(b, c);

return{ r[0], r[2], r[1] - r[2] * n };
}

// Gives the multiplicative inverse of k mod prime.  In other words (k * modInverse(k)) % prime = 1 for all prime > k >= 1
static TINT modInverse (TINT k, TINT prime) {
k = k % prime;
TINT r = (k < 0) ? -gcdD(prime, -k)[2] : gcdD(prime, k)[2];
return (prime + r) % prime;
}

private:

// Publically known information
const TINT          c_prime;
const TINT          c_sharesNeeded;
};

void WaitForEnter ()
{
printf("Press Enter to quit");
fflush(stdin);
getchar();
}

int main (int argc, char **argv)
{
// Parameters
const TINT c_secretNumber = 435;
const TINT c_sharesNeeded = 7;
const TINT c_prime = 439;   // must be a prime number larger than the other three numbers above

// set up a secret sharing object with the public information
CShamirSecretSharing secretSharer(c_sharesNeeded, c_prime);

// split a secret value into multiple shares

// shuffle the shares, so it's random which ones are used to join
std::array<int, std::mt19937::state_size> seed_data;
std::random_device r;
std::generate_n(seed_data.data(), seed_data.size(), std::ref(r));
std::seed_seq seq(std::begin(seed_data), std::end(seed_data));
std::mt19937 gen(seq);
std::shuffle(shares.begin(), shares.end(), gen);

// join the shares
TINT joinedSecret = secretSharer.JoinShares(shares);

// show the public information and the secrets being joined
printf("%" PRId64 " shares needed, %i shares maden", secretSharer.GetSharesNeeded(), shares.size());
printf("Prime = %" PRId64 "nn", secretSharer.GetPrime());
for (TINT i = 0, c = secretSharer.GetSharesNeeded(); i < c; ++i)
printf("Share %" PRId64 " = (%" PRId64 ", %" PRId64 ")n", i+1, shares[i][0], shares[i][1]);

// show the result
printf("nJoined Secret = %" PRId64 "nActual Secret = %" PRId64 "nn", joinedSecret, c_secretNumber);
assert(joinedSecret == c_secretNumber);
WaitForEnter();
return 0;
}


## Example Output

Here is some example output of the program:

Wikipedia: Shamir’s Secret Sharing (Note: for some reason the example javascript implementation here only worked for odd numbered keys required)
Wikipedia: Finite Field
Cryptography.wikia.com: Shamir’s Secret Sharing
Java Implementation of Shamir’s Secret Sharing (Note: I don’t think this implementation is correct, and neither is the one that someone posted to correct them!)

When writing this post I wondered if maybe you could use the coefficients of the other terms as secrets as well. These two links talk about the details of that:
Cryptography Stack Exchange: Why only one secret value with Shamir’s secret sharing?
Cryptography Stack Exchange: Coefficients in Shamir’s Secret Sharing Scheme

Now that you understand this, you are probably ready to start reading up on elliptic curve cryptography. Give this link below a read if you are interested in a gentle introduction on that!
A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography

# Turning a Truth Table Into A digital Circuit (ANF)

In this post I’m going to show how you turn a truth table into a digital logic circuit that uses XOR and AND gates.

## My Usage Case

My specific usage case for this is in my investigations into homomorphic encryption, which as you may recall is able to perform computation on encrypted data. This lets encrypted data be operated on by an untrusted source, given back to you, and then you can decrypt your data to get a result.

Lots of use cases if this can ever get fast enough to become practical, such as doing cloud computing with private data. However, when doing homomorphic encryption (at least currently, for the techniques I’m using), you only have XOR and AND logic operations.

So, I’m using the information in this post to be able to turn a lookup table, or a specific boolean function, into a logic circuit that I can feed into a homomorphic encryption based digital circuit.

Essentially I want to figure out how to do a homomorphic table lookup to try and make some simple as possible circuits, that will in turn be as fast and lean as possible.

If you want to know more about homomorphic encryption, here’s a post I wrote which explains a very simple algorithm: Super Simple Symmetric Leveled Homomorphic Encryption Implementation

## Algebraic Normal Form

Algebraic normal form (ANF) is a way of writing a boolean function using only XOR and AND.

Since it’s a normal form, two functions that do the same thing will be the same thing in ANF.

There are other forms for writing boolean logic, but ANF suits me best for my homomorphic encryption circuit needs!

An example of boolean logic in ANF is the below:

$f(x_1, x_2, x_3, x_4) = x_1 x_2 \oplus x_1 x_3 \oplus x_1 x_4$

It is essentially a boolean polynomial, where AND is like multiplication, and XOR is like addition. It even factors the same way. In fact, ANF is not always the smallest circuit possible, you’d have to factor common ANDs to find the smallest way you could represent the circuit, like the below:

$f(x_1, x_2, x_3, x_4) = x_1 (x_2 \oplus x_3 \oplus x_4)$

That smaller form does 1 AND and 2 XORs, versus the ANF which does 3 ANDs and 2 XORs. In homomorphic encryption, since AND is so much more costly than XOR, minimizing the ANDs is a very nice win, and worth the effort.

## Truth Tables and Lookup Tables

A truth table is just where you specify the inputs into a boolean function and the output of that boolean function for the given input:

$\begin{array}{c|c|c|c} x_1 & x_2 & x_3 & f(x_1, x_2, x_3) \\ \hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ \end{array}$

A lookup table is similar in functionality, except that it has multi bit output. When dealing with digital circuits, you can make a lookup table by making a truth table per output bit. For instance, the above truth table might just be the low bit of the lookup table below, which is just a truth table for addition of the input bits.

$\begin{array}{c|c|c|c} x_1 & x_2 & x_3 & f(x_1, x_2, x_3) \\ \hline 0 & 0 & 0 & 00 \\ 0 & 0 & 1 & 01 \\ 0 & 1 & 0 & 01 \\ 0 & 1 & 1 & 10 \\ 1 & 0 & 0 & 01 \\ 1 & 0 & 1 & 10 \\ 1 & 1 & 0 & 10 \\ 1 & 1 & 1 & 11 \\ \end{array}$

## Converting Truth Table to ANF

When I first saw the explanation for converting a truth table to ANF, it looked pretty complicated, but luckily it turns out to be pretty easy.

The basic idea is that you make a term for each possible combination of x inputs, ANDing a term by each constant, and then solving for those constants.

Let’s use the truth table from the last section:

$\begin{array}{c|c|c|c} x_1 & x_2 & x_3 & f(x_1, x_2, x_3) \\ \hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ \end{array}$

For three inputs, the starting equation looks like this:

$f(x_1, x_2, x_3) = \\ a_0 \\ \oplus a_1 x_1 \oplus a_2 x_2 \oplus a_3 x_3 \\ \oplus a_{12} x_1 x_2 \oplus a_{13} x_1 x_3 \oplus a_{23} x_2 x_3 \\ \oplus a_{123} x_1 x_2 x_3$

Now we have to solve for the a values.

To solve for $a_{123}$, we just look in the truth table for function $f(x_1, x_2, x_3)$ to see if we have an odd or even number of ones in the output of the function. If there is an even number, it is 0, else it is a 1.

Since we have an even number of ones, the value is 0, so our equation becomes this:

$f(x_1, x_2, x_3) = \\ a_0 \\ \oplus a_1 x_1 \oplus a_2 x_2 \oplus a_3 x_3 \\ \oplus a_{12} x_1 x_2 \oplus a_{13} x_1 x_3 \oplus a_{23} x_2 x_3 \\ \oplus 0 \land x_1 x_2 x_3$

Note that $\land$ is the symbol for AND. I’m showing it explicitly because otherwise the equation looks weird, and a multiplication symbol isn’t correct.

Since 0 ANDed with anything else is 0, and also since n XOR 0 = n, that whole last term disappears, leaving us with this equation:

$f(x_1, x_2, x_3) = \\ a_0 \\ \oplus a_1 x_1 \oplus a_2 x_2 \oplus a_3 x_3 \\ \oplus a_{12} x_1 x_2 \oplus a_{13} x_1 x_3 \oplus a_{23} x_2 x_3$

Next up, to solve for $a_{12}$, we need to limit our truth table to $f(x_1, x_2, 0)$. That truth table is below, made from the original truth table, but throwing out any row where $x_{3}$ is 1.

$\begin{array}{c|c|c|c} x_1 & x_2 & x_3 & f(x_1, x_2, 0) \\ \hline 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ \end{array}$

We again just look at whether there are an odd or even number of ones in the function output, and use that to set $a_{12}$ appropriately. In this case, there are an even number, so we set it to 0, which makes that term disappear again. Our function is now down to this:

$f(x_1, x_2, x_3) = \\ a_0 \\ \oplus a_1 x_1 \oplus a_2 x_2 \oplus a_3 x_3 \\ \oplus a_{13} x_1 x_3 \oplus a_{23} x_2 x_3$

If we look at $f(x_1,0,x_3)$, we find that it also has an even number of ones, making $a_{13}$ become 0 and making that term disappear.

Looking at $f(0,x_2,x_3)$, it also has an even number of ones, making $a_{23}$ become 0 and making that term disappear as well.

That leaves us with this equation:

$f(x_1, x_2, x_3) = \\ a_0 \\ \oplus a_1 x_1 \oplus a_2 x_2 \oplus a_3 x_3$

To solve for $a_1$, we look at the truth table for $f(x_1,0,0)$, which is below:

$\begin{array}{c|c|c|c} x_1 & x_2 & x_3 & f(x_1, 0, 0) \\ \hline 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ \end{array}$

There are an odd number of ones in the output, so $a_1$ becomes 1. Finally, we get to keep a term! The equation is below:

$f(x_1, x_2, x_3) = \\ a_0 \\ \oplus 1 \land x_1 \oplus a_2 x_2 \oplus a_3 x_3$

Since 1 AND n = n, we can drop the explicit 1 to become this:

$f(x_1, x_2, x_3) = \\ a_0 \\ \oplus x_1 \oplus a_2 x_2 \oplus a_3 x_3$

If you do the same process for $a_2$ and $a_3$, you’ll find that they also have odd numbers of ones in the output so also become ones. That puts our equation at:

$f(x_1, x_2, x_3) = \\ a_0 \\ \oplus x_1 \oplus x_2 \oplus x_3$

Solving for $a_0$, is just looking at whether there are an odd or even number of ones in the function $f(0,0,0)$ which you can look up directly in the lookup table. It’s even, so $a_0$ becomes 0, which makes our full final equation into this:

$f(x_1, x_2, x_3) = x_1 \oplus x_2 \oplus x_3$

We are done! This truth table can be implemented with 3 XORs and 0 ANDs. A pretty efficient operation!

You can see this is true if you work it out with the truth table. Try it out and see!

$\begin{array}{c|c|c|c} x_1 & x_2 & x_3 & f(x_1, x_2, x_3) \\ \hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ \end{array}$

## Sample Code

Here is some sample code that lets you define a lookup table by implementing an integer function, and it generates the ANF for each output bit for the truth table. It also verifies that the ANF gives the correct answer. It shows you how to use this to make various circuits: bit count, addition, multiplication, division and modulus.

#include <stdio.h>
#include <array>
#include <vector>

#define PRINT_TRUTHTABLES() 0
#define PRINT_NUMOPS() 1
#define PRINT_ANF() 1

void WaitForEnter ()
{
printf("Press Enter to quit");
fflush(stdin);
getchar();
}

template <size_t NUM_INPUT_BITS>
{
for (size_t i = 0; i < NUM_INPUT_BITS; ++i)
{
const size_t bitMask = 1 << i;
return false;
}
return true;
}

template <size_t NUM_INPUT_BITS>
bool ANFHasTerm (const std::array<size_t, 1 << NUM_INPUT_BITS> &lookupTable, size_t outputBitIndex, size_t termMask)
{
const size_t c_inputValueCount = 1 << NUM_INPUT_BITS;

int onesCount = 0;
for (size_t i = 0; i < c_inputValueCount; ++i)
{
onesCount++;
}

return (onesCount & 1) != 0;
}

template <size_t NUM_INPUT_BITS>
void MakeANFTruthTable (const std::array<size_t, 1 << NUM_INPUT_BITS> &lookupTable, std::array<size_t, 1 << NUM_INPUT_BITS> &reconstructedLookupTable, size_t outputBitIndex)
{
const size_t c_inputValueCount = 1 << NUM_INPUT_BITS;
printf("-----Output Bit %u-----rn", outputBitIndex);

// print truth table if we should
#if PRINT_TRUTHTABLES()
for (size_t inputValue = 0; inputValue < c_inputValueCount; ++inputValue)
printf("  [%u] = %urn", inputValue, ((lookupTable[inputValue] >> outputBitIndex) & 1) ? 1 : 0);
printf("rn");
#endif

// find each ANF term
std::vector<size_t> terms;
{
}

// print function params
#if PRINT_ANF()
printf("f(");
for (size_t i = 0; i < NUM_INPUT_BITS; ++i)
{
if (i > 0)
printf(",");
printf("x%i",i+1);
}
printf(") = rn");
#endif

// print ANF and count XORs and ANDs
size_t numXor = 0;
size_t numAnd = 0;
if (terms.size() == 0)
{
#if PRINT_ANF()
printf("0rn");
#endif
}
else
{
for (size_t termIndex = 0, termCount = terms.size(); termIndex < termCount; ++termIndex)
{
if (termIndex > 0) {
#if PRINT_ANF()
printf("XOR ");
#endif
++numXor;
}

size_t term = terms[termIndex];
if (term == 0)
{
#if PRINT_ANF()
printf("1");
#endif
}
else
{
bool firstProduct = true;
for (size_t bitIndex = 0; bitIndex < NUM_INPUT_BITS; ++bitIndex)
{
const size_t bitMask = 1 << bitIndex;
if ((term & bitMask) != 0)
{
#if PRINT_ANF()
printf("x%i ", bitIndex + 1);
#endif
if (firstProduct)
firstProduct = false;
else
++numAnd;
}
}
}
#if PRINT_ANF()
printf("rn");
#endif
}
}
#if PRINT_ANF()
printf("rn");
#endif

#if PRINT_NUMOPS()
printf("%u XORs, %u ANDsrnrn", numXor, numAnd);
#endif

// reconstruct a bit of the reconstructedLookupTable for each entry to be able to verify correctness
const size_t c_outputBitMask = 1 << outputBitIndex;
for (size_t valueIndex = 0; valueIndex < c_inputValueCount; ++valueIndex)
{
bool xorSum = false;
for (size_t termIndex = 0, termCount = terms.size(); termIndex < termCount; ++termIndex)
{
size_t term = terms[termIndex];
if (term == 0)
{
xorSum = 1 ^ xorSum;
}
else
{
bool andProduct = true;
for (size_t bitIndex = 0; bitIndex < NUM_INPUT_BITS; ++bitIndex)
{
const size_t bitMask = 1 << bitIndex;
if ((term & bitMask) != 0)
{
if ((valueIndex & bitMask) == 0)
andProduct = false;
}
}
xorSum = andProduct ^ xorSum;
}
}
if (xorSum)
}
}

template <size_t NUM_INPUT_BITS, size_t NUM_OUTPUT_BITS, typename LAMBDA>
void MakeANFLookupTable (const LAMBDA& lambda)
{
// make lookup table
const size_t c_outputValueMask = (1 << NUM_OUTPUT_BITS) - 1;
const size_t c_inputValueCount = 1 << NUM_INPUT_BITS;
std::array<size_t, c_inputValueCount> lookupTable;
for (size_t inputValue = 0; inputValue < c_inputValueCount; ++inputValue)
lookupTable[inputValue] = lambda(inputValue, NUM_INPUT_BITS, NUM_OUTPUT_BITS) & c_outputValueMask;

// make the anf for each truth table (each output bit of the lookup table)
std::array<size_t, c_inputValueCount> reconstructedLookupTable;
std::fill(reconstructedLookupTable.begin(), reconstructedLookupTable.end(), 0);
for (size_t outputBitIndex = 0; outputBitIndex < NUM_OUTPUT_BITS; ++outputBitIndex)
MakeANFTruthTable<NUM_INPUT_BITS>(lookupTable, reconstructedLookupTable, outputBitIndex);

// verify that our anf expressions perfectly re-create the lookup table
for (size_t inputValue = 0; inputValue < c_inputValueCount; ++inputValue)
{
if (lookupTable[inputValue] != reconstructedLookupTable[inputValue])
printf("ERROR: expression / lookup mismatch for index %urn", inputValue);
}
printf("expression / lookup verification complete.rnrn");
}

size_t CountBits (size_t inputValue, size_t numInputBits, size_t numOutputBits)
{
// Count how many bits there are
int result = 0;
while (inputValue)
{
if (inputValue & 1)
result++;
inputValue = inputValue >> 1;
}
return result;
}

size_t AddBits (size_t inputValue, size_t numInputBits, size_t numOutputBits)
{
// break the input bits in half and add them
const size_t bitsA = numInputBits / 2;
const size_t mask = (1 << bitsA) - 1;

size_t a = inputValue & mask;
size_t b = inputValue >> bitsA;

return a+b;
}

size_t MultiplyBits (size_t inputValue, size_t numInputBits, size_t numOutputBits)
{
// break the input bits in half and add them
const size_t bitsA = numInputBits / 2;
const size_t mask = (1 << bitsA) - 1;

size_t a = inputValue & mask;
size_t b = inputValue >> bitsA;

return a * b;
}

size_t DivideBits (size_t inputValue, size_t numInputBits, size_t numOutputBits)
{
// break the input bits in half and add them
const size_t bitsA = numInputBits / 2;
const size_t mask = (1 << bitsA) - 1;

size_t a = inputValue & mask;
size_t b = inputValue >> bitsA;

// workaround for divide by zero
if (b == 0)
return 0;

return a / b;
}

size_t ModulusBits (size_t inputValue, size_t numInputBits, size_t numOutputBits)
{
// break the input bits in half and add them
const size_t bitsA = numInputBits / 2;
const size_t mask = (1 << bitsA) - 1;

size_t a = inputValue & mask;
size_t b = inputValue >> bitsA;

// workaround for divide by zero
if (b == 0)
return 0;

return a % b;
}

int main (int argc, char **argv)
{
//MakeANFLookupTable<3, 2>(CountBits);    // Output bits needs to be enough to store the number "input bits"
//MakeANFLookupTable<4, 3>(AddBits);      // Output bits needs to be (InputBits / 2)+1
//MakeANFLookupTable<4, 4>(MultiplyBits); // Output bits needs to be same as input bits
//MakeANFLookupTable<4, 2>(DivideBits);   // Output bits needs to be half of input bits (rounded down)
//MakeANFLookupTable<4, 2>(ModulusBits);  // Output bits needs to be half of input bits (rounded down)
//MakeANFLookupTable<10, 5>(DivideBits);  // 5 bit vs 5 bit division is amazingly complex!
MakeANFLookupTable<4, 2>(ModulusBits);  // Output bits needs to be half of input bits (rounded down)
WaitForEnter();
return 0;
}


## Sample Code Runs

Here is the program output for a “bit count” circuit. It counts the number of bits that are 1, in the 3 bit input, and outputs the answer as 2 bit output. Note that the bit 0 output is the same functionality as the example we worked through by hand, and you can see that it comes up with the same answer.

Here is the program output for an adder circuit. It adds two 2 bit numbers, and outputs a 3 bit output.

Here is the program output for a multiplication circuit. It multiplies two 2 bit numbers, and outputs a 4 bit number.

Here is the program output for a division circuit. It divides a 2 bit number by another 2 bit number and outputs a 2 bit number. When higher bit counts are involved, the division circuit gets super complicated, it’s really crazy! 5 bit divided by 5 bit is several pages of output for instance. Note that it returns 0 whenever it would divide by 0.

Lastly, here is the program output for a modulus circuit. It divides a 2 bit number by another 2 bit number and outputs the remainder as a 2 bit number.

While the above shows you how to turn a single bit truth table into ANF, extending this to a multi bit lookup table is super simple; you just do the same process for each output bit in the lookup table.

Finding Boolean/Logical Expressions for truth tables in algebraic normal form(ANF)

Finding Boolean/Logical Expressions for truth tables

# Game Development Needs Data Pipeline Middleware

In 15 years I’ve worked at 7 different game studios, ranging from small to large, working on many different kinds of projects in a variety of roles.

At almost every studio, there was some way for the game to load data at runtime that controlled how it behaved – such as the damage a weapon would do or the cost of an item upgrade.

The studios that didn’t have this setup could definitely have benefited from having it. After all, this is how game designers do their job!

Sometimes though, this data was maintained via excel spreadsheets (export as csv for instance and have the game read that). That is nearly the worst case scenario for data management. Better though is to have an editor which can edit that data, preferably able to edit data described by schemas, which the game also uses to generate code to load that data.

Each studio I’ve worked at that did have game data each had their own solution for their data pipeline, and while they are all of varying qualities, I have yet to see something that is both fast and has most of the features you’d reasonably want or expect.

We really need some middleware to tackle this “solved problem” and offer it to us at a reasonable price so we can stop dealing with it. Open sourced would be fine too. Everyone from engineers to production to content people will be much happier and more productive!

# Required Features

Here are the features I believe are required to satisfy most folks:

1. Be able to define the structure of your data in some format (define data schema).
2. Have an editor that is able to quickly launch, quickly load up data in the data schema and allow a nice interface to editing the data as well as searching the data.
3. This edited data should be in some format that merges well (for dealing with branching), and preferably is standardized so you can use common tools on the data – such as XSLT if storing data as xml. XML isn’t commonly very mergable so not sure the solution there other than perhaps a custom merge utility perhaps?
4. The “data solution” / project file should store your preferences about how you want the final data format to be: xml, json, binary, other? Checkboxes for compression and encryption, etc. Switching the data format should take moments.
5. There should be a cooking process that can be run from the data editor or via command line which transforms the edited data into whatever format the destination data should be in. AKA turn the human friendly XML into machine friendly binary files which you load in with a single read and then do pointer fixup on.
6. This pipeline should generate the code that loads and interacts with the data as described in the data schema. For instance you say “load my data” and it does all the decompression, decryption, parsing, etc giving you back a root data structure which contains compile time defined strongly typed structures. This is important because when you change the format of the data that the game uses, no game code actually has to know or care. Whatever it takes to load your data happens when you call the function.

# Bonus Points

Here are some bonus point features that would be great to have:

1. Handle live editing of data. When the game and editor is both open, and data is edited, have it change the data on the game side in real time, and perhaps allow a callback to be intercepted in case the game needs to clear out any cached values or anything. This helps iteration time by letting people make data changes without having to relaunch the game. Also needs to be able to connect to a game over tcp/ip and handle endian correction as needed as well as 32 vs 64 bit processes using the same data.
2. Handle the usual problems associated with DLC and versioning in an intelligent way. Many data systems that support DLC / Patching / Schema Updates post ship have strange rules about what data you can and can’t change. Often times if you get it wrong, you make a bug that isn’t always obvious. If support for this was built in, and people didnt have to concern themselves with it, it’d be great.
3. On some development environments, data must be both forwards and backwards compatible. Handling that under the covers in an intelligent way would be awesome.
4. The editor should be extensible with custom types and plugins for visualizations of data, as well as interactive editing of data. This same code path could be used to integrate parts of the game engine with the editor for instance (slippery slope to making the editor slow, however).
5. Being able to craft custom curves, and being able to query them simply and efficiently from the game side at runtime would be awesome.
6. Support “cook time computations”. The data the user works with isn’t always set up the way that would be best for the machine. It’d be great to be able to do custom calculations and computations at runtime. Also great for building acceleration data structures.
7. You should be able to run queries against the data or custom scripts. To answer questions like “Is anyone using this feature?” and “I need to export data from our game into a format that this other program can read”
8. Being able to export data as c++ literal data structures, for people who want to embed (at least some of) their data in the exe to reduce complexity, loading times, etc.

It should also be as fast and lightweight as possible. It should allow games to specify memory and file i/o overrides.

Localized text is also a “solved problem” that needs an available solution. It could perhaps be rolled into this, or maybe it would make most sense for it to be separate.

As another example of how having something like this would be useful, on multiple occasions at previous studios, people have suggested we change the format of the data that the game uses at runtime. For instance, from json to a binary format. In each case this has come up so far, people have said it would take too long and it got backlogged (ie killed). With data pipeline middleware that works as i describe it, you would click a few checkboxes, recook your data and test it to have your runtime results. That’s as hard as it SHOULD be, but in practice it’s much harder because everyone rolls their own and the cobbler never has time to fix his shoes (;

Anyone out there want to make this happen? (: