Programming challenge: wildcard exclusion in cartesian products

[Christophe Rhodes]

[ note followups ]

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 mine, in Common Lisp.

(defmacro define-tea-pair ((encrypt decrypt) (delta n) (i1 j1 i2 j2))
  `(macrolet ((32bitize (form) `(logand ,form #xffffffff))
              (tea-kernel (x i j)
               `(logxor (+ (ash ,x 4) (aref key ,i)) (+ ,x sum)
                        (+ (ash ,x -5) (aref key ,j))))
              (tea-loop ((text n sum) &body body)
               `(let ((result (make-array 2 :element-type '(unsigned-byte 32)))
                      (y (aref ,text 0))
                      (z (aref ,text 1)))
                 (do ((n ,n (- n 1)) (sum ,sum))
                     ((<= n 0)
                      (prog1 result
                        (setf (aref result 0) y (aref result 1) z)))
                   , at body))))
    (defun ,encrypt (plaintext key &aux (delta ,delta))
      (declare (type (simple-array (unsigned-byte 32) (2)) plaintext)
               (type (simple-array (unsigned-byte 32) (4)) key))
      (tea-loop (plaintext ,n 0)
        (setq sum (32bitize (+ sum delta))
              y (32bitize (+ y (tea-kernel z ,i1 ,j1)))
              z (32bitize (+ z (tea-kernel y ,i2 ,j2))))))
    (defun ,decrypt (ciphertext key &aux (delta ,delta))
      (declare (type (simple-array (unsigned-byte 32) (2)) ciphertext)
               (type (simple-array (unsigned-byte 32) (4)) key))
      (tea-loop (ciphertext ,n (32bitize (* ,n delta)))
        (setq z (32bitize (- z (tea-kernel y ,i2 ,j2)))
              y (32bitize (- y (tea-kernel z ,i1 ,j1)))
              sum (32bitize (- sum delta)))))))

(define-tea-pair (encipher decipher) (#x9e3779b9 32) (0 1 2 3))

So far, so ordinary; only marginally shorter than the C version; I'm
certainly nowhere near Pascal's 14 lines, although my version has the
advantage over his that each constant is mentioned only once, and all
quantities derived from it are computed at compile-time; I can define
a different pair with

  (define-tea-pair (eprime dprime) (#xabcdef01) (3 1 2 0))

and the new functions are inverses of each other as before.

The other thing that might be of interest is the inner loop.  There
are no declarations other than the argument declarations, and all the
code that I have written is portable Common Lisp, and should work in
any conforming implemenation.  In SBCL (on the PowerPC; other
platforms are similar), the inner loop for ENCIPHER is

  addis $nl0,$nl3,-25033
  addi $nl3,$nl0,31161
  rlwinm $nl5,$nl2,4,0,27
  lwz $nl6,1($fdefn)
  add $nl6,$nl5,$nl6
  add $nl0,$nl2,$nl3
  xor $cfunc,$nl6,$nl0
  rlwinm $nl0,$nl2,27,5,31
  mr $nl5,$nl0
  lwz $nl6,5($fdefn)
  add $nl6,$nl5,$nl6
  xor $nl6,$cfunc,$nl6
  add $nl1,$nl1,$nl6
  rlwinm $nl5,$nl1,4,0,27
  lwz $nl6,9($fdefn)
  add $nl6,$nl5,$nl6
  add $nl0,$nl1,$nl3
  xor $cfunc,$nl6,$nl0
  rlwinm $nl0,$nl1,27,5,31
  mr $nl5,$nl0
  lwz $nl6,13($fdefn)
  add $nl6,$nl5,$nl6
  xor $nl6,$cfunc,$nl6
  add $nl2,$nl2,$nl6
  addi $nl4,$nl4,-4
  cmpwi cr0,$nl4,0
  bt gt,l0

and while this may be opaque to some readers, the point is that it is
pretty much comparable to the C code in performance (the differences
between this disassembly and gcc -O2 lie in the fact that SBCL's
instruction scheduler is pretty much nonexistent on the PowerPC
architecture).

Christophe