Programming challenge: wildcard exclusion in cartesian products

[Pascal Bourguignon]

Mark Carter <me at privacy.net> writes:

> 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
> in your language of choice.
>
> 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 get it shorter than in C:

(defun op (x a b sum) (logxor (+ (ash x 4) a) (+ x sum) (+ (ash x -5) b)))
(declaim (inline op))
(defmacro ciploop ((v w k y z a b c d (sum init-sum) delta) &body body)
  `(let ((,y  (aref ,v 0)) (,z  (aref ,v 1)) (,sum  ,init-sum) (,delta  #x9E3779B9)
         (,a  (aref ,k 0)) (,b  (aref ,k 1)) (,c  (aref ,k 2)) (,d  (aref ,k 3)))
     (loop repeat 32 do , at body finally (setf (aref ,w 0) ,y (aref ,w 1) ,z))))
(defmacro c-incf (var expr) `(setf ,var (mod (+ ,var ,expr) #x100000000)))
(defmacro c-decf (var expr) `(setf ,var (mod (- ,var ,expr) #x100000000)))
(defun encipher (v w k)
  (ciploop (v w k y z a b c d (sum 0) delta)
           (c-incf sum delta) (c-incf y (op z a b sum)) (c-incf z (op y c d sum))))
(defun decipher (v w k)
  (ciploop (v w k y z a b c d (sum #xC6EF3720) delta)
           (c-decf z (op y c d sum)) (c-decf y (op z a b sum)) (c-decf sum delta)))


You can also easily modify it to implement the improved version of TEA...
Note that this Lisp programs will work equally well on a 16-bit,
32-bit or 64-bit Common Lisp implementation.  The same cannot be said
of the C program above.



;; Let's add a testbed:

(defun word (a b c d) 
  (dpb a (byte 8 24) (dpb b (byte 8 16) (dpb c (byte 8 8) d))))

(defun read-words (bits what)
  (loop
     for bytes = (progn (format *query-io* "Please enter ~D bits of ~A: " 
                                bits what)
                        (ext:convert-string-to-bytes
                         (read-line *query-io* nil nil) ext:*TERMINAL-ENCODING*))
     while (< (* 8 (length bytes)) bits)
     finally (return
               (loop for i from 0 by 4 below (truncate (+ 7 bits) 8)
                  collect (word (aref bytes (+ i 0))
                                (aref bytes (+ i 1))
                                (aref bytes (+ i 2))
                                (aref bytes (+ i 3))) into words
                  finally (return (coerce words 'vector))))))

(defun test ()
    (loop 
       with code = (vector 0 0)
       with decr = (vector 0 0)
       for clear = (read-words  64 "clear text")
       for key   = (read-words 128 "key")
       do (progn (encipher clear code key)
                 (format t "(encipher ~S ~S)~% -->      ~S~%" clear key code)
                 (decipher code decr key)      
                 (format t "(decipher ~S ~S)~% -->      ~S~%" code key decr)
                 (unless (equalp clear decr) (format t "!!! ERROR !!!~%")))))


[11]> (test)
Please enter 64 bits of clear text: Hello World!
Please enter 128 bits of key: John McCarthy invented LISP.
(encipher #(1214606444 1864390511) #(1248815214 541942595 1634890856 2032167278))
 -->      #(913593965 183139965)
(decipher #(913593965 183139965) #(1248815214 541942595 1634890856 2032167278))
 -->      #(1214606444 1864390511)
Please enter 64 bits of clear text: Big Secret: LISP!
Please enter 128 bits of key: A very very secure key.
(encipher #(1114203936 1399153522) #(1092646501 1920540790 1702000928 1936024437))
 -->      #(3198111104 1851109064)
(decipher #(3198111104 1851109064) #(1092646501 1920540790 1702000928 1936024437))
 -->      #(1114203936 1399153522)
Please enter 64 bits of clear text: ^C





-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

ATTENTION: Despite any other listing of product contents found
herein, the consumer is advised that, in actuality, this product
consists of 99.9999999999% empty space.