Tim's Blog

De-obfuscating cable1.c

tim@timmontague.com (Tim Montague) — Wed, 31 Dec 2014 00:00:00 +0000

This code is one of the winners of the 22nd International Obfuscated C Code Contest. It takes 3 arguments: the last name of any of the last 31 US Presidents, the string “republican” and the string “democrat”. The program then prints out either “republican” or “democrat” depending on which political party the president was affiliated with. The code is surprisingly small, which means it shouldn’t be too difficult to figure out how it works.

main(int riguing,char**acters){puts(1[acters-~!(*(int*)1[acters]%4796%275%riguing)]);}

The first thing to do is rename the variables to sensible names and add some standard main() code.

int main(int argc, char **argv) {
	puts(1[argv-~!(*(int*)1[argv]%4796%275%argc)]);
	return 0;
}

In C var[1] and 1[var] are equivalent, so let’s swap it around to look more normal.

int main(int argc, char **argv) {
	puts((argv-~!(*(int*)argv[1]%4796%275%argc))[1]);
	return 0;
}

The next step is to pull out the magic math into a separate statement. And since argc is always 4, replace it with that constant.

int main(int argc, char **argv) {
	int i = *(int*)argv[1]%4796%275%4;
	puts((argv-~!(i))[1]);
	return 0;
}

This helps with understanding what the magic math is doing. The integer i is either 0 or 1, which is then used to print out either the 2nd or 3rd argument to the program. What I did was hard code the strings “democrat” and “republican” so that it isn’t necessary to pass them as arguments.

int main(int argc, char **argv) {
	int i = *(int*)argv[1]%4796%275%4;
	if (i == 0) {
		puts("democrat");
	} else {
		puts("republican");
	}
	return 0;
}

The integer i is made up of the first 4 characters of the President’s name, the next step is to replace the pointer casting with more explicit steps.

int main(int argc, char **argv) {
	char *name = argv[1];
	int i = name[0]<<0 | name[1]<<8 | name[2]<<16 | name[3]<<24;
	i = i%4796%275%4;
	if (i == 0) {
		puts("democrat");
	} else {
		puts("republican");
	}
	return 0;
}

This is about as clear as the code can be. The only mystery left is why the constants 4796, 275 and 4 were chosen. I imagine that the original author ran a bruteforce calculation to determine what numbers would cause the correct division between the names.

Computing e - Revisited

tim@timmontague.com (Tim Montague) — Sun, 06 Jan 2013 03:48:42 +0000

I decided to revisit the problem of computing digits of e after talking to someone who thought that a spigot algorithm would work without a loss of precision. I felt pretty embarrassed when it took about 30 seconds to find some code that did exactly what I wanted it to. It took only a few minutes to convert the algorithm from Javascript into C, it works great!

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

int main(int argc, const char *argv[])
{
	int i;
	int len;
	int *a;
	int x = 0;

	if (argc < 2) {
		fprintf(stderr, "Usage: %s n\nn - number of decimal places\n", argv[0]);
		return -1;
	}

	len = strtol(argv[1], NULL, 10);
	if (!len) {
		fprintf(stderr, "Error parsing argument\n");
		fprintf(stderr, "Usage: %s n\nn - number of decimal places\n", argv[0]);
		return -1;
	}
	len += 9;
	a = malloc(len*sizeof(int));
	if (!a) {
		fprintf(stderr, "malloc error\n");
		return -1;
	}
	a[0] = 0;
	a[1] = 0;
	for (i = 2; i < len; i++) {
		a[i] = 1;
	}
	printf("2.");
	while (len > 9) {
		for (i = len; i > 0; i--) {
			a[i] = x%i;
			x = 10*a[i-1] + x/i;
		}
		len--;
		printf("%d", x);
	}
	printf("\n");

	return 0;
}

Then after consulting some documentation to look up the finer points of Bash syntax, I rewrote it:

#!/bin/bash

if [[ ( $# < 1 ) || !( $1 =~ ^[0-9]+$ ) ]]; then
	echo "Usage: $0 n"
	echo "   n - number of decimal places of e to output"
	exit -1
fi

len=$(($1 + 9))

A[0]=0
A[1]=0
for (( i = 2; i < $len; i++ )); do
	A[$i]=1
done

echo -n "2."

X=0
while [[ $len -gt 9 ]]; do
	for (( i = $len; i > 0; i-- )); do
		A[$i]=$(( $X % $i ))
		X=$(( 10 * ${A[$i-1]} + $X / $i ))
	done
	len=$(( $len - 1 ))
	echo -n "$X"
done
echo

And it works! I tested it and compared it to the first several thousand digits that are listed on http://apod.nasa.gov/htmltest/gifcity/e.1mil and they were identical.

It’s amazing how these problems can initially seem so difficult, but once the correct approach to the problem is found, the solution is actually quite simple.

Dashboard

tim@timmontague.com (Tim Montague) — Mon, 19 Nov 2012 04:06:09 +0000

I bought a cheap Android tablet from China recently, it was $60 including shipping. Despite the hilariously bad translation in the documentation, it works great, although slowly. The idea was to mount the tablet on the wall near the front door, and have it show some relevant real-time information. After a week of procrastinating, I finally wrote it. The source is up on GitHub. The code is very messy and needs to be re-factored and commented, but it works.

The app gets data from 3 data sources, the Yahoo! Weather RSS Feed, the WMATA developer API and the Capital Bikeshare Station XML feed. The data is updated every 30 seconds and has works remarkably well. As a metro train approaches, the background of the text turns yellow and red as the window of opportunity for catching the train closes. The status of 2 Bikeshare stations is also shown, the station closest to my house, and the station nearest my gym.

One feature that I’d like to add if I have time, is to add a rotating background that updates from Facebook automatically.

Calculating Microcontroller Timer Parameters

tim@timmontague.com (Tim Montague) — Fri, 02 Nov 2012 19:27:46 +0000

Recently I was working on a project involving an ARM processor and a Bluetooth module which required a clock signal at 32.768 kHz. To avoid adding an external oscillator, we tried to use the ARM processor as a clock source. The clock speed on the ARM was 72 MHz, with a user specified 16 bit pre-scaler and 16 bit compare register. To determine what pre-scaler and compare values could be used to get closest to the required frequency, I wrote the following small program:

/*
 * Finds prescaler and compare register values that result in an output closest
 * to a goal frequency via brute force.
 */
#include <stdio.h>
#include <math.h>
int main(int argc, const char *argv[]) {
	unsigned int clock = 72000000;
	unsigned int prescaler;
	unsigned int compare;
	double goal = 32768;
	double i;
	double min = 100;
	for (prescaler = 1; prescaler <= 65536; prescaler++) {
		for (compare = 1; compare <= 65536; compare++) {
			i = (clock / prescaler) / compare;
			if (fabs(goal - i) <= min) {
				min = fabs(goal - i);
				printf("prescaler: %d, compare: %d, freq: %f\n", prescaler, compare, i);
			}
		}
	}
	return 0;
}

In less than 20 seconds, it found out that with a prescaler of 2197 and a compare value of 1, the output frequency would be 32881 Hz. Unfortunately that was not within the tolerances of the bluetooth module, so an external oscillator was added to the schematic.

Project Euler

tim@timmontague.com (Tim Montague) — Fri, 31 Aug 2012 14:31:23 +0000

I recently started going through the problems on Project Euler, and put my solutions up at my GitHub account. The problems are mostly mathematical problems that can be solved programmatically. Most of the solutions that I’ve written are just naive brute force algorithms. A few of them take a long time to run, so I wrote the program to be threaded; in particular finding sum of all primes below 2 million and finding the first triangle number to have over 500 divisors.

I’ve written most of my solutions in C, with 1 solution in Java (finding the sum of the digits of 2^1000) because BigInteger is super easy to use. It’s fun to write little C programs, and I’ve gotten the chance to learn about pthreads and the GMP library. Most of my solutions could be further refined to reduce the runtime, but since each solution only needs to be run once (I only need to find the answer once!), there isn’t a huge incentive to keep working on a solution once it works. Hopefully I have time to solve more problems soon.

Dynamic DNS on Route 53

tim@timmontague.com (Tim Montague) — Tue, 10 Jul 2012 20:56:03 +0000

The dynamic DNS setup that I wrote about previously didn’t work out very well. After several weeks of running smoothly, the VPS provider I was using had an issue with a DDoS attack on one of its clients which forced them to move datacenters. Obviously this caused some unexpected downtime and my only DNS server for timmontague.com was unavailable. Luckily, I was able to change the name server back to the servers provided by Gandi.net, my registrar, within a few hours so hopefully I didn’t bounce too many emails. In hindsight, it’s probably not the best idea to place your sole name server on a VPS that costs less than $2 a month.

I decided to go with another route, Amazon’s Route 53. They offer servers across the world and their SLA states that they expect 100% availability. More importantly, they have an API that allows adding, deleting and updating records.

It was extremely easy to get set up. I already had an Amazon AWS account, so I simply logged in, created a new hosted zone, and added my existing DNS records using the web interface. I found a utility that makes it incredibly easy to administer the DNS records from the command line called cli53.

One obstacle I encountered was finding my external IP address without relying on a service that may be sporadically unavailable. With a little searching, I was able to find a command that connects to the Airport Extreme that I’m using as a router via SNMP and extracts the external IP address.

I updated my DDNS update script to the following:

#!/bin/bash

DIR="/home/tim/ddns"
TTL="300"
HOSTS="@
www
home
sync"

# use -f to force ip change
if [[ $# -gt 0 && -n "`echo $1 | grep -- -f`" ]]; then
	FORCE=true
else
	FORCE=false
fi

cd $DIR
LASTIP=`cat lastip.txt`

# get WAN IP address from airport extreme via snmp interface
WAN=`snmpwalk -c public -v 2c 192.168.2.1 ipAdEntIfIndex \
	| sed 's/.*ipAdEntIfIndex.\([0-9]*.[0-9]*.[0-9]*.[0-9]*\).*/\1/' \
	| grep -v -E "^((127)|(192)|(169)|(10))\."`

if [[ "$LASTIP" != "$WAN" || $FORCE == true ]]; then
	echo "IP changed from $LASTIP to $WAN"
	echo $WAN > lastip.txt
else
	exit
fi

for h in $HOSTS
do
	echo $h
	cli53 rrcreate --replace --ttl $TTL timmontague.com $h A $WAN
done

With the extremely low traffic of this site, the monthly AWS fees should be about $1. Not too bad at all.

Domain Name Notifications with Python

tim@timmontague.com (Tim Montague) — Fri, 06 Jul 2012 18:45:14 +0000

I wanted to write a small program to automatically alert me if certain domain names became available to register. My first thought was to write a Bash script to run the whois command and parse the output with a combination of Grep and Sed, but after looking at the mess that whois returns, I opted to go another route.

I found a Python module to retrieve WHOIS data and installed it with pip install whois. I played around it for a few minutes and realized that while the website mentions support for .net addresses, the .net domain wasn’t actually coded into the module. Luckily, the data returned by whois is in the same format for both .net and .com domain names. I added the following few lines to /usr/lib/python3.2/site-packages/whois/tld_regexpr.py and it started to work fine.

net = {
'extend' : 'com'
}

I wanted to have the script only output something when a domain name was close to being expired so that it could be easily installed into a cron job. The final script is here:

#!/usr/bin/env python

'''
File: domain-expiration-check.py
Author: Tim Montague
Description: Checks expiration dates of domain names
'''

import argparse
import whois
import sys
import datetime

def main():
	parser = argparse.ArgumentParser(
		description="Outputs remaining days until domain name expires if the\
		number of days is less then a specified amount (defaults to 7 days)")
	parser.add_argument("domainnames", nargs='+')
	parser.add_argument("-v", "--verbose", action="store_true",
			help="print days remaining even if less than threshold")
	parser.add_argument("-d", "--days", help="set days remaining threshold",
			type=int, default=7)
	args = parser.parse_args()

	for d in args.domainnames:
		try:
			w = whois.query(d, ignore_returncode=1)
			if w:
				days = (w.expiration_date - datetime.datetime.utcnow()).days
				if args.verbose or days < args.days:
					print (d, "expires in", days, "days!")
			else:
				print("Domain not found: ", d, file=sys.stderr)
		except Exception as e:
			print(e, file=sys.stderr)
	
if __name__ == '__main__':
	main()

This script works perfectly for me. I set up cron to run it daily, so whenever one of the domains I’m watching comes close to being available, I’ll get an email notification.

Running Your Own Dynamic DNS Server

tim@timmontague.com (Tim Montague) — Thu, 21 Jun 2012 16:03:04 +0000

I recently moved my web server from an internet connection with a static IP address to an internet connection with a dynamic IP address, which presents some issues with DNS. I looked at some dynamic DNS services such as Dyn and no-ip (which I’ve used before and was happy with), but I decided that I’d rather implement my own solution. I found a VPS provider at ipxcore that had a virtual server for only $1.16 a month (well within impulse buy range), so I got one.

The first thing I did was install the Debian image and boot it up. I chose Debian because I wanted a binary package manager so I didn’t have to worry about compiling a bunch of packages on a small VPS with little RAM, and I figured that Debian would have less cruft than the Ubuntu image. Unfortunately, the default Debian image included a bunch of things pre-installed that I didn’t want including Apache, a mail server, and a bunch of other services. I spent 30 minutes or so removing packages trying to get back to a bare-bones system before I decided to try the Gentoo image. Gentoo has been my Linux distribution of choice for 7 years, so I’m fairly adept at getting it configured just the way I want it. Luckily, the Gentoo image provided by ipxcore contained a very minimal set of installed packages.

Following directions found on the Free BSD Wiki and the Gentoo Wiki, I was able to get BIND installed and configured. It was a lot simpler that I thought it would be. I set up a zone file for timmontague.com that contained the SOA, NS, MX, TXT and other various records that are static and won’t change based on the dynamic IP address. I generated a cryptographic key to allow for remote DNS updates via the nsupdate command and copied it to my web server.

The first semi-difficult part was writing the script to automatically update the DNS records, in particular determining the external IP address of the web server (because it is behind a NAT). The dynamic DNS resources that I found suggested running a small PHP or Perl script in a web server that simply printed the REMOTE_ADDR. I didn’t want to install a PHP on my minimal VPS, and Perl also seemed a little overkill, so I decided to write a small CGI program in C.

#include <stdio.h>
#include <stdlib.h>
int main() {
	char* ip = getenv("REMOTE_ADDR");
	printf("Content-type: text/plain\n\n");
	if (ip)
		printf("%s\n", ip);
	return 0;
}

I installed a small web server and configured it to run CGI scripts. When I attempted to access the script from a remote location however, I kept getting 500 Internal Error messages (There was an unusual problem serving the requested URL '/myip.cgi'.). It’s exceedingly difficult to Google for such errors, but eventually I concluded that it was because the web server was sand-boxed, the binary would have to be statically linked. I recompiled it using gcc -o myip.cgi myip.c -static -L/lib -lc and started working perfectly.

I wrote a bash script on my web server to automatically determine it’s external IP address, and if it has changed, update the BIND server using nsupdate.

#!/bin/bash

DIR="/home/tim/ddns"
URL="http://ns.timmontague.com:8080/myip.cgi"
NAMESERVER="ns.timmontague.com"
TTL="10"
KEYFILE="Ktimmontague.com.+157+08540.private"
HOSTS="timmontague.com.
www.timmontague.com.
home.timmontague.com.
sync.timmontague.com."

cd $DIR
LASTIP=`cat lastip.txt`

WAN=`curl -s $URL`
if [[ $? -ne 0 ]]; then
	echo "Could not open $URL"
	exit
fi

if [[ "$LASTIP" == "$WAN" ]]; then
	exit # IP address hasn't changed
else
	echo "IP address changed from $LASTIP to $WAN"
	echo $WAN > lastip.txt
fi

TMPFILE=`tempfile`
echo "server $NAMESERVER" > $TMPFILE

for h in $HOSTS
do
	echo "update delete $h A" >> $TMPFILE
	echo "update add $h $TTL A $WAN" >> $TMPFILE
done
echo "send" >> $TMPFILE

/usr/bin/nsupdate -k "$KEYFILE" $TMPFILE
rm $TMPFILE

I set up cron to run the script every minute and it seems to be working fine, but so far (the last 4 days), the dynamic IP address hasn’t changed. I set the TTL to be 10 seconds, so when it does change, the downtime should be minimal.

The last step was updating the nameserver on my domain registrar’s website. I updated the nameserver to ns.timmontague.com, and added a glue record for ns.timmontague.com to 68.171.100.161 (the static IP of my VPS). I waited a few hours for the changes to propagate, and it worked!

All in all, setting up my own nameserver was much easier than expected. It only took a few hours to configure and install the BIND DNS server on a bare-bones VPS. In the end, my VPS is still incredibly small; the only extra packages I installed are:

app-admin/logrotate
app-admin/sudo
app-admin/sysklogd
app-editors/vim
mail-client/mailx
net-dns/bind
net-dns/bind-tools
net-firewall/iptables
sys-process/vixie-cron
www-servers/thttpd

I also set up backups on my VPS containing /etc/, /var/www/ns, and /home/tim. After gzip, the backups are less than 150kB. It’s nice knowing that if I ever need to switch VPS providers, I will be able to get another name server up and running with a minimal amount of effort.

Computing e

tim@timmontague.com (Tim Montague) — Thu, 07 Jun 2012 16:25:53 +0000

I saw a job posting on Hacker News with an interesting problem which promptly sucked me in.

Send a bash program that calculates Euler’s number to N decimal places (where N is specified on the command line) to email.

I thought it looked like an interesting problem so I opened up Vim and started working on it in my language of choice, C, with the intention of porting it to Bash after I got it working.

The first step was determining how to calculate e programmatically, which brought me to Wikipedia. The infinite series at the top of the article seemed like a good place to start so I implemented it quickly and hackily.

#include <stdio.h>
int main(int argc, const char *argv[])
{
	double e = 0;
	double e_prev = 0;

	double n = 1;
	int i = 2;
	int places;
	int temp;

	if (argc < 2) {
		printf("Usage: %s n\nn - number of decimal places\n", argv[0]);
		return -1;
	}
	places = atoi(argv[1]);

	printf("2.");
	n = n*(i++);
	e = e+(1.0/n);
	while (places) {
		e_prev = e;
		n = n*(i++);
		e = e+(1.0/n);
		// if digit in tenths place is the same, output and shift left
		while(places && (int)(e*10) == (int)(e_prev*10)) {
			temp = (int)(e*10);
			printf("%d", temp);
			e *= 10;
			e_prev *= 10;
			n = n / 10;
			e -= temp;
			e_prev -= temp;
			places--;
		}
	}
	printf("\n");
	return 0;
}

That worked for the first 11 digits (2.71828182845), but failed on the 12th (2.718281828458 instead of 2.78281828459)

I thought that the issue would be the denominator of the infinite series being extremely large and overflowing, but that’s not the case. Before that happens, the double holding e loses precision after too many divide-by-10s.

I did some Googling (actually DuckDuckGo-ing, but that doesn’t have the same ring to it) and found a website describing how one person wrote a program to do exactly what I wanted. It referenced a paper on an finding digits of pi. I read through the paper and concluded that I am bad at reading and understanding academic papers, especially since the code snippets are written in Haskell, a language that I don’t know. I was able to read the blog post though and implement it in C (after spending way too much time figuring out the matrix math).

#include <stdio.h>
int main(int argc, const char *argv[])
{
	double e_low = 0;
	double e_high = 1;
	double m [2][2];
	int temp;
	
	int max;
	int i=3;

	if (argc < 2) {
		printf("Usage: %s n\nn - number of decimal places\n", argv[0]);
		return -1;
	}
	max = atoi(argv[1]);

	m[0][0] = .5;
	m[0][1] = 1;
	m[1][0] = 0;
	m[1][1] = 1;

	printf("2.");
	while (max--) {
		// keep multiplying terms until we converge on a digit
		while (((int)(e_low*10)) != ((int)(e_high*10))) {
			m[0][1] = m[0][0] + m[0][1];
			m[0][0] = m[0][0] * (1.0/i);
			i++;
			//m[1][0] = 0;
			//m[1][1] = 1;

			e_low = m[0][0]*1 + m[0][1];
			e_high = m[0][0]*2 + m[0][1];
		}
		temp = (int)(e_low*10);
		e_low = e_low*10;
		e_low = e_low-temp;
		e_high = e_high*10;
		e_high = e_high-temp;
		m[0][0] *= 10;
		m[0][1] *= 10;
		m[0][1] -= temp;
		printf("%d", temp%10);
		
	}
	printf("\n");
	return 0;
}

This algorithm works using a different infinite sequence, but it still has the same precision errors. After 15 digits, the first error occurs (2.7182818284590453 instead of 2.7182818284590452). I spent a long time going over the code and couldn’t find any errors that were causing my program to fail while it seemed to work for the guy who’s blog I was reading. I came to the conclusion that the author must have used BigInteger or another library.

I still really wanted to solve the problem, so I decided to give it one last shot. I decided to go back to the original problem statement, and I wrote it in Bash. It isn’t written using only Bash, but at least it gives me some closure. It works for up to 1,000,000 digits of e.

#!/bin/bash

if [[ ( $# < 1 ) || !( $1 =~ ^[0-9]+$ ) ]]; then
	echo "Usage: $0 n"
	echo "   n - number of decimal places of e to output"
	exit -1
fi

# output the first 2 digits ("2.")
n=$((2 + $1))

# grab first 1 million digits from internet, remove header and newlines, print
# first $n characters
curl -s http://apod.nasa.gov/htmltest/gifcity/e.1mil | tail -c +1298 | \
	tr -d '\n' | head -c +$n
echo

If I have time, and motivation, I may revisit this problem. The next step I’d try would be to use a fixed point library, such as the GNU MPFR.