[Openmcl-devel] just when you thought it was safe to go back in the CCL trunk

Ron Garret ron at flownet.com
Mon Sep 14 17:16:44 PDT 2015

On Sep 14, 2015, at 2:09 PM, Gary Byers <gb at clozure.com> wrote:

> Here is the threatened documementation.

Thanks Gary, that’s actually very interesting reading!  (At least it was to me, but I guess that makes me a pretty hard-core geek.)

As long as the compiler is on the table, I have a question that I’ve been meaning to ask for a long time but never quite found the right moment.  I’m not sure this is the right moment, but here goes anyway…

I’m working on cryptography nowadays, and that involves doing a lot of operations on quantities that are constrained to be 32 or 64 bits wide, and it is important that those operations happen in constant time in order not to leak secrets through timing and other side-channel attacks.

Straightforward Lisp code is not suited for this because some N-bit values on an N-bit machine are fixnums and others are bignums.  But there is a way to express the desired semantics cleanly, and that is to declare things as signed-byte and unsigned-byte values.  In particular, vectors whose element types are (un/signed-byte 32) or (un/signed-byte 64) can hold 32-bit and 64-bit values cleanly with no boxing.  In principle, this should allow Lisp code operating on such values and putting the results back in such places to be as fast as C code.

But there is a fly in the ointment: Common Lisp does not include modulo 2^N arithmetic as primitives.  You can only do mod 2^N math as an idiom, i.e. (setf (some-place-that-has-been-declared-to-be (type (un/signed-byte 32)) (mod (op v1 v2) #.(ash 1 32))).  It is asking an awful lot of the compiler to recognize such idioms as optimizable into one or two machine instructions.  And yet, it would be so tremendously useful, not just for crypto, but for image processing as well.

How hard would be to tweak the compiler so that it could make this optimization?  Specifically, how feasible would it be for the compiler to recognize the above as a special case and optimize it to (more or less) what a C compiler would produce?  AFAICT it shouldn’t be too difficult, and if it were done, I think it would let CCL kick some serious benchmarking tushie.

Is such a thing feasible?


More information about the Openmcl-devel mailing list