XOR Logic

It's winter break, so I have had less "essential" programming to do. I have been wasting time on projecteuler.net. This site is an on-line competition devoted to solving very difficult math problems of the type that require programs to solve. I've been on the site for about two weeks and I've solved a third of the problems.

The problem that has interested me the most is problem #59: Brute force decryption using XOR Logic. I can't talk about the solution here, because that would only help people who are trying to win the competition by Googling answers, but I can talk about XOR Logic.

XOR Logic is the comparison between two items where the results is true if one is true and the other isn't. If both are false or if both are true, the result is false. In programming terms, we think of it like this:

unsigned char a, b, c;
scanf("%c",&a);
scanf("%c",&b);
c = (~a&b)|(a&~b); // XOR Logic Here!
printf("%c(%d) -> %c(%d) -> %c(%d)\n", a,a, b,b, c,c);

In this example, we have two terms: a and b. We wish to XOR these two items to make a result c. Using C's bitwise and "&", bitwise or "|", and bitwise negate "~", we can create the XOR gate. We have two inputs, and one has to be true and the other must be false for the result to be true. It doesn't matter the order. Output c is true if input a is true and input b is false or if a is false and b is true. In fact, that sentence is pretty much how I programmed it.

English:
Output c is true if input a is true and input b is false
or if a is false and b is true.

English and C:
Output c is true [c = ] if [(] input a is true [a] and(&)
input b is false[~b] [)] or[|] if[(] a is false[~a] and[&]
b is true[b] [)].[;]

C:
c = (~a&b)|(a&~b);

So how is this useful? Cryptography is based on the practice of taking a message, encrypting it, then taking the encrypted message and decrypting it. The great thing about XOR logic is that it is used for both encrypting and decrypting text.

Let's say that your secret message consist of one character: "L". "L" on the ASCII table is decimal 76 or binary "01001100". You need a secret password to encrypt the letter "L". For that, we'll use "!" which is decimal 33 or binary "00100001".

01001100 L (76)
00100001 ! (33)
-------- XOR
01101101 m (109)

"L" has now been encrypted. The encrypted text is now "m". Using our password "!", we can now decrypt the text:

01101101 m (109)
00100001 ! (33)
-------- XOR
01001100 L (76)

We just decrypted our message "m" using the same XOR method and password "!" that we used to encrypt the message. XOR Logic is pretty useful because it provides the method to both encrypt and decrypt messages quickly.

Matrix Fun in Haskell

I have always thought that the snobbiest of programmers are those that use Haskell, which is a language so academic that I'm not sure if it's been used outside academia. Haskell is known for what it doesn't have. Haskell doesn't have the same loop structure. It doesn't have variables. It doesn't have the imperative design like most languages. I like Haskell. Any time I need to jump on a math program, I usually solve it in Haskell first, then the language I need second.

A friend of mine is a physics Ph.D. student who is trying to learn C. He wanted to write a program to find all of the 2-by-2 determinants found in a 4-by-4 matrix. There are 36 total. He had his own ideas on how to solve this, but I still think the quickest way is to brute force all of the possibilities.

The following patches of Haskell and C are almost identical. They use the exact same variables ("labels" for the Haskell code) to accomplish the same task. The Haskell code returns an array of floats, where the C code prints each of the 36 determinants.

twoByTwo :: [[Float]] -> [Float]
twoByTwo m = concat (map(\i->
                 concat (map(\j->
                     concat (map(\p->
                         map(\q->
                             (m!!i!!j)*(m!!p!!q)-(m!!i!!q)*(m!!p!!j)
                         )[(j+1)..(n-1)]
                     )[(i+1)..(n-1)])
                 )[0..(n-2)])
             )[0..(n-2)])
             where
                 n = length m

Yes, Haskell fans, there is a quadruple-nested lambda expression there, which does seem a little confusing. It's short and elegant, which is why Haskell reminds me of Python.

void twoByTwo(float *m, int n) {
    int i, j, p, q;
    for (i = 0; i < n-1; i++)
        for (j = 0; j < n-1; j++)
            for (p = i+1; p < n; p++)
                for (q = j+1; q < n; q++)
                    printf("%3.1f\n", m[i*n+j]*m[p*n+q] - m[i*n+q]*m[p*n+j]);
}

No one ever said C was pretty. I also wrote a recursive Matrix determinant algorithm in Haskell, but I may save that for another time.

The Impossible FFTW Bug

Ever had a computer bug that you spent weeks working on it? You might try every trick you know to solve it: debugging messages, profilers, Google, professors, coworkers, fellow students. You might try to explain the code to someone who doesn't even program just so you have to describe the logic in simple terms. Nothing seems to fix the problem.

I had this bug in my code for about two weeks. I had to write a program to compute the 2 dimensional FFT of an image. That's it. I'll just use FFTW, the most popular open source library for computing FFTs.

The Wrong Solution for computing FFTs with FFTW:

int j;
fftw_plan myplan;
fftw_complex in[x*y], out[x*y];

for (j = 0; j < x*y; j++) {
    in[j][0] = r[j];
    in[j][1] = i[j];
} // End For

myplan = (dir == 1)? fftw_plan_dft_2d(x, y, in, out, FFTW_FORWARD,  FFTW_MEASURE) :
                     fftw_plan_dft_2d(x, y, in, out, FFTW_BACKWARD, FFTW_MEASURE) ;

fftw_execute(myplan);

In these few lines of code lies a problem that I've spent weeks trying to find. There are no syntax errors, nor are there logic errors. Every time I ran this code, the result would be all zeros. If I ran it multiple times, I got the correct results for every execution after the first. I dropped the data into a prepared array, made a plan (as defined by the FFTW C library), then executed that library. Should work, right? Wrong.

The Correct Solution for computing FFTs with FFTW:

int j;
fftw_plan myplan;
fftw_complex in[x*y], out[x*y];

myplan = (dir == 1)? fftw_plan_dft_2d(x, y, in, out, FFTW_FORWARD,  FFTW_MEASURE) :
                     fftw_plan_dft_2d(x, y, in, out, FFTW_BACKWARD, FFTW_MEASURE) ;

for (j = 0; j < x*y; j++) {
    in[j][0] = r[j];
    in[j][1] = i[j];
} // End For

fftw_execute(myplan);

I found buried in the FFTW FAQ that I'm suppose to make a plan before giving it the data. I switched two sets of lines around and everything magically works for reasons I fail to understand. Let this be a lesson to anyone having to use FFTW.

File Character Frequency

In my machine learning course, our first project was to write a program to sort e-mail into nine class labels A through I. In my implementation after every e-mail was classified, I would write a single character to the screen. There were several thousand of e-mails that needed sorting, so I needed a program that displayed a final tally of the results.

I could have easily built something into the program I was writing, but I thought something more general purpose would be useful. I quickly wrote the following code. It takes a tally of each character in a file and then uses a quick sort to sort the data and then prints the results. I even added a switch to ignore whitespace characters.

#include <stdio.h> /* Author: James Church * Date: 09/11/06 * Program: charfreq * Version: 0.3 * Description: Takes a single file from the command line as input and * reports the character frequence of each character in order * from most common to least common. * * Copyright © 2006 Free Software Foundation, Inc. * * Copying and distribution of this file, with or without modification, * are permitted in any medium without royalty provided the copyright * notice and this notice are preserved. */ #define CHARRANGE 256 typedef struct _charcount { unsigned char c; long count; } CharCount; void quicksort (CharCount *a, int i, int j); int partition (CharCount *a, int i, int j); int main(int argc, char **argv) { int i; unsigned char c; CharCount freq[CHARRANGE]; FILE *file; int ignore_whitespace = 0; int argparse = 1; if (argc == 1) { printf("\nUsage: %s [-s] [filename] - Reports character frequence of file.\n", argv[0]); printf(" -s Ignores whitespace (optional)\n"); return 0; } // End If if (strcmp("-s", argv[argparse]) == 0) { ignore_whitespace = 1; argparse++; } // End If if ((file = fopen(argv[argparse], "r")) == NULL) { printf("Error: Cannot open %s\n", argv[1]); return 0; } // End If argparse++; for (i = 0; i < CHARRANGE; i++) { freq[i].c = (unsigned char) i; freq[i].count = 0; } // End For while (1) { fread (&c, sizeof(unsigned char), 1, file); if (feof(file)) break; if (ignore_whitespace && (c == ' ' || c == '\t' || c == '\r' || c == '\n')) continue; freq[c].count++; } // End While quicksort(freq, 0, CHARRANGE-1); for (i = CHARRANGE-1; i >= 0; i--) { if (freq[i].count == 0) break; printf("%c[%3d]: %d\n", freq[i].c, freq[i].c, freq[i].count); } // End For fclose(file); return 0; } // End Main void quicksort (CharCount *a, int i, int j) { int p; if (i < j) { p = partition (a, i, j); quicksort (a, i, p-1); quicksort (a, p+1, j); } /* End If */ } /* End mergesort */ int partition (CharCount *a, int i, int j) { int val = a[i].count; int h = i; int k; CharCount temp; for (k = i+1; k <= j; k++) if (a[k].count < val) { h++; temp = a[h]; a[h] = a[k]; a[k] = temp; } /* End If */ temp = a[i]; a[i] = a[h]; a[h] = temp; return h; } /* End partition */

Enjoy!