# Programming challenge: wildcard exclusion in cartesian products

Mark Carter me at privacy.net
Mon Mar 20 19:25:37 CET 2006

```I'd like to propose a coding challenge of my own. The challenge is to
reproduce the TEA (Tiny Encryption Algorith):
http://www.simonshepherd.supanet.com/tea.htm

Here's the code, just two simple functions:

void encipher(unsigned long *const v,unsigned long *const w,
const unsigned long *const k)
{
register unsigned long       y=v[0],z=v[1],sum=0,delta=0x9E3779B9,
a=k[0],b=k[1],c=k[2],d=k[3],n=32;

while(n-->0)
{
sum += delta;
y += (z << 4)+a ^ z+sum ^ (z >> 5)+b;
z += (y << 4)+c ^ y+sum ^ (y >> 5)+d;
}

w[0]=y; w[1]=z;
}

void decipher(unsigned long *const v,unsigned long *const w,
const unsigned long *const k)
{
register unsigned long       y=v[0],z=v[1],sum=0xC6EF3720,
delta=0x9E3779B9,a=k[0],b=k[1],
c=k[2],d=k[3],n=32;

/* sum = delta<<5, in general sum = delta * n */

while(n-->0)
{
z -= (y << 4)+c ^ y+sum ^ (y >> 5)+d;
y -= (z << 4)+a ^ z+sum ^ (z >> 5)+b;
sum -= delta;
}

w[0]=y; w[1]=z;
}

I had a crack at it in Lisp. My version doesn't work - but of greater
concern to me is that it doesn't appear nearly as compact as the C
version. Anyway, here's my Lisp code (no prizes for guessing that I'm a
noob to Lisp):

(defconstant delta 2654435769 ) ; delta= 0x9E3779B9

(defun floorn (n) (nth-value 0 (floor n)))

(defun >> (val num-bytes)
"Right-shift positive integer val by num-bytes"
(let* (t1 t2)
(setf t1 (expt 2 num-bytes))
(setf t2 (/ val t1))
(floor t2)))

(defun << (val num-bytes)
"Left-shift positive integer v by num-bytes"
(* val (expt 2 num-bytes)))

(defun <<4 (i) (<< i 4))

(defun byte-n (v n)
"Return the nth byte of a value v"
(let* ((bits-to-shift (* 8 (1- n)))
(shifted-value (>> v bits-to-shift)))
(logand shifted-value 256)))

(defun transform (v1 v2 v3 v4)
(let (t1 t2 t3)
(setf t1 (<<4 v1))
(setf t2 (expt v2 v1))
(setf t3 (expt v3 (>> v2 5)))
(+ t1 t2 t3 v4)))

(defun pack64 (b1 b2) (+ (<< b1 32) b2))

(defun encipher (v k)
(let ((sum 0)
(a (byte-n k 3))  ; a=k[0]
(b (byte-n k 2))  ; b=k[1]
(c (byte-n k 1))  ; c=k[2]
(d (byte-n k 0))  ; d=k[3]
(y (byte-n v 1))  ; y=v[4]
(z (byte-n v 0))) ; z=v[1]

(loop for n from 0 to 31 do  ;n=32, while(n-->0)
(incf sum delta)    ;sum += delta;
(incf y (transform z a sum b)) ; y += (z << 4)+a ^ z+sum ^ (z >> 5)+b
(incf z (transform y c sum d)) ;z += (y << 4)+c ^ y+sum ^ (y >> 5)+d;
)

(pack64 y z) ; w[0]=y; w[1]=z;
))

(defun decipher (v k)
(let ((sum 3337565984)  ; 0xC6EF3720
(a (byte-n k 3))  ; a=k[0]
(b (byte-n k 2))  ; b=k[1]
(c (byte-n k 1))  ; c=k[2]
(d (byte-n k 0))  ; d=k[3]
(y (byte-n v 1))  ; y=v[4]
(z (byte-n v 0))) ; z=v[1]

(loop for n from 0 to 31 do  ;n=32, while(n-->0)
(decf z (transform y c sum d)) ;z -= (y << 4)+c ^ y+sum ^ (y >> 5)+d;
(decf y (transform z a sum b)) ;y -= (z << 4)+a ^ z+sum ^ (z >> 5)+b;
(decf sum delta)    ;sum -= delta;
)

(pack64 y z) ; w[0]=y; w[1]=z;
))

```