HACKvent 2015: Day 12

Challenge

We were given this little piece of code to run.
Unfortunately it takes a bit too long to terminate on our systems and even gcc's -O3 does not seem to help.

Maybe you want to run it on your new peta-flop CPU for a couple of years?

The following C code is also provided:

#include <stdio.h>
#include <stdint.h>

uint64_t foo(uint64_t a) {
	uint64_t s = a - 42;
	s += 23*2-3;
	return s;
}

uint64_t bar(uint64_t a) {
	uint64_t s = a + 42;
	s -= 23*2-3;
	return s;
}

uint64_t baz(uint64_t a, uint64_t b) {
	uint64_t r = 0;
	for(uint64_t i=0; i<a; i++)
		r = foo(r);
	for(uint64_t i=0; i<b; i++)
		r = foo(r);
	
	return r;
}

uint64_t spam(uint64_t a, uint64_t b) {
	uint64_t r = baz(0,a);
	for(uint64_t i=0; i<b; i++)
		r = bar(r);
	
	return r;
}

uint64_t eggs(uint64_t a, uint64_t b) {
	uint64_t r = 0;
	for(uint64_t i=0; i<a; i++)
		r = baz(r, b);
	return r;
}

uint64_t merry(uint64_t a, uint64_t b) {
	uint64_t i;
	for(i=0; a>=b; i++)
		a = spam(a, b);
	return i;
}

uint64_t xmas(uint64_t a, uint64_t b) {
	return spam(a, eggs(merry(a,b),b));
}

uint64_t hackvent(uint64_t a, uint64_t b) {
	uint64_t r = 1;
	for(uint64_t i=0; i<a; i++)
		r = eggs(r, b);
	return r;	
}


int main() {
	uint64_t val=0;
	for(uint64_t i=0; i<0xC0DE42; i++) {
		val = xmas(eggs(baz(hackvent(merry(i,42),3),val),i),0x42DEADBABEC0FFEE);
	}
	printf("HV15-mHPC-%04llx-%04llx-%04llx-%04llx\n",
		val>>48,(val&0x0000FFFF00000000)>>32,
		(val&0x00000000FFFF0000)>>16, (val&0x000000000000FFFF));

	return 0;
}

Solution

Clearly the issue here is that this program is very inefficient.
So what does the program do? First it sets the unsigned 64 bit integer variables val and i to 0. Then 0xC0DE42 iterations occur and the val is recomputed each calculation. The previous val and i values are used to recompute the new val value.

After all this, it appears as if the nugget we need is printed out! The 4 missing blocks in the nugget are based on 4 groups of 16 bits which come from the final val value.
So we begin to optimize the code!

foo and bar

We start with the foo and bar functions which are very similar to each other.
It turns out that they simplify to:

uint64_t foo(uint64_t a) { return (a - 42) + 23 * 2 - 3; }
uint64_t foo(uint64_t a) { return (a - 42) + 43; }
uint64_t foo(uint64_t a) { return (a + 1); }

uint64_t bar(uint64_t a) { return (a + 42) - 23 * 2 - 3; }
uint64_t bar(uint64_t a) { return (a + 42) - 43; }
uint64_t bar(uint64_t a) { return (a - 1); }

So we have just optimised these two functions slightly. The next step is go through the code and replace all calls to foo and bar with simply increments or decrements. I'm not going to show the changes I made to each call as that would make this post too long but you get the idea.

Optimized functions:

uint64_t foo(uint64_t a) {
	return a + 1;
}

uint64_t bar(uint64_t a) {
	return a - 1;
}

baz

baz should look like this at this stage:

uint64_t baz(uint64_t a, uint64_t b) {
	uint64_t r = 0;
	for(uint64_t i=0; i<a; i++)
		r += 1;
	for(uint64_t i=0; i<b; i++)
		r += 1;
	
	return r;
}

It is clear from the code that baz can be optimised. First the variable r is set to zero and then a 1 is added to r, a times. Then 1 is added to r, b times.
This is simply the same as adding a to b and storing the result in r.

Optimized function:

uint64_t baz(uint64_t a, uint64_t b) {
  return a + b;
}

spam

Spam should look like this at this stage:

uint64_t spam(uint64_t a, uint64_t b) {
	uint64_t r = a;
	for(uint64_t i=0; i<b; i++)
		r -= 1;
	
	return r;
}

This function is simply setting r to a and then taking away 1 from r, b times before returning the result in r.
This is the same as returning a - b.

Optimized function:

uint64_t spam(uint64_t a, uint64_t b) {
  return a - b;
}

eggs

eggs should look like this at this stage:

uint64_t eggs(uint64_t a, uint64_t b) {
	uint64_t r = 0;
	for(uint64_t i=0; i<a; i++)
		r += b;
	return r;
}

Well all that is happening here is r is increasing by b, a times. That means we are adding a number of b's to r.
This is the same as returning a * b.

Optimized function:

uint64_t eggs(uint64_t a, uint64_t b) {
  return a * b;
}

merry

merry should look like this at this stage:

uint64_t merry(uint64_t a, uint64_t b) {
	uint64_t i;
	for(i=0; a>=b; i++)
		a -= b;
	return i;
}

So at this stage, we are taking away b from a while a is still bigger than b. The value of i is then returned which is the number of times we took away b from a.
This is clearly a simple division operation: a / b

Optimized function:

uint64_t merry(uint64_t a, uint64_t b) {
  return a / b;
}

xmas

xmas should look like this at this stage:

uint64_t xmas(uint64_t a, uint64_t b) {
	return a - (a/b) * b;
}

This one is a little more tough. a is divided by b then multiplied by b and this result is subtracted from a. You may be tempted to think that this returns 0 all the time but it does not.
This is because the division operation that occurs is integer division and multiplying that result by b may not result in the original a being restored.
A small example: 10/3 = 3.33 but is stored as 3 in an integer. However, 3*3 = 9 and not 10!

In this case, a modulo operation is happening: a % b

Optimized function:

uint64_t xmas(uint64_t a, uint64_t b) {
  return a % b;
}

hackvent

hackvent should look like this at this stage:

uint64_t hackvent(uint64_t a, uint64_t b) {
	uint64_t r = 1;
	for(uint64_t i=0; i<a; i++)
		r *= b;
	return r;	
}

This is a fun one. Notice how r is set to 1 initially, that is important. r is then multiplied by b, a number of times.
This is the same as calculating b to the power of a.
However, we cannot just use the pow function defined in <math.h>.
We are dealing with uint64_t data types and must thus get a power function that can handle these larger numbers.
I decide to find one online and use it.

Optimized function (ipow and hackvent):

//Altered version found online
//Source: http://stackoverflow.com/q/15224911/1800854
uint64_t ipow(uint64_t base, uint64_t exp)
{
  uint64_t result = 1ULL;
  while (exp)
  {
    if (exp & 1)
    {
      result *= (uint64_t)base;
    }
    exp >>= 1;
    base *= base;
  }
  return result;
}

uint64_t hackvent(uint64_t a, uint64_t b) {
  return ipow(b, a);
}

Putting it all together

At this stage you can do two things.
You can either run your program as is to find the answer or you can inline your function or convert the function calls in main so you save making all those function frames.
In this case it doesn't really matter but this is what the calculation of val in main should look like with no function calls:

val = ((ipow(3, i / 42) + val) * i) % 0x42DEADBABEC0FFEE;

Then you run your program and within a few seconds you get the flag!

Flag:

HV15-mHPC-067e-751e-f50e-17e3

Note: You can download my final solution C file here: