With the recent discussion both here and on cmucl-help about
optimizing md5, I thought I'd suggest a function that might be useful
for implementing it efficiently.
Obviously, using the reference implementation in this case doesn't buy
the user much, as it is likely that the compiler will not be able to
spot that particular examples can be compiled in few machine
instructions; however, I have a proof-of-concept implementation for
cmucl/sbcl/x86 that can compile (rotate-byte x (byte 32 0) y) for
positive y efficiently.
I don't know whether this is useful to anyone (apart from
md5-transform writers); in any case, here it is (comments welcome):
Function ROTATE-BYTE
Syntax:
rotate-byte count bytespec integer => result-integer
Arguments and Values:
count---an integer.
bytespec---a byte specifier.
integer---an integer.
result-integer---an integer.
Description:
Rotates a field of bits within integer; specifically, returns an
integer that contains the bits of integer rotated count times
leftwards within the byte specified by bytespec, and elsewhere
contains the bits of integer.
Examples:
(rotate-byte 3 (byte 32 0) 3) => 24
(rotate-byte 3 (byte 5 5) 3) => 3
(rotate-byte 6 (byte 8 0) -3) => -129
Side Effects: None.
Affected By: None.
Exceptional Situations: None.
See Also:
byte
Reference implementation:
(defun rotate-byte (count bytespec integer)
(let* ((size (byte-size bytespec))
(count (mod count size)))
(labels ((rotate-byte-from-0 (count size integer)
(let ((bytespec (byte size 0)))
(if (> count 0)
(logior (ldb bytespec (ash integer count))
(ldb bytespec (ash integer (- count size))))
(logior (ldb bytespec (ash integer count))
(ldb bytespec (ash integer (+ count size))))))))
(dpb (rotate-byte-from-0 count size (ldb bytespec integer))
bytespec
integer))))
Cheers,
Christophe
--
Jesus College, Cambridge, CB5 8BL +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
Christophe Rhodes <·····@cam.ac.uk> wrote:
+---------------
| ... however, I have a proof-of-concept implementation for
| cmucl/sbcl/x86 that can compile (rotate-byte x (byte 32 0) y) for
| positive y efficiently.
|
| I don't know whether this is useful to anyone (apart from
| md5-transform writers)...
+---------------
Should also prove useful for AES (a.k.a Rijndael a.k.a. FIPS-197)
<URL:http://csrc.nist.gov/encryption/aes/index.html>, which has
several 32-bit rotates of different amounts per round.
-Rob
p.s Anybody done AES in CL yet...?
-----
Rob Warnock, 30-3-510 <····@sgi.com>
SGI Network Engineering <http://www.meer.net/~rpw3/>
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
[Note: ·········@sgi.com and ········@sgi.com aren't for humans ]
>>>>> "Rob" == Rob Warnock <····@rigden.engr.sgi.com> writes:
Rob> p.s Anybody done AES in CL yet...?
Simon Josefsson has written Rijndael in Emacs Lisp (ECB only)
http://josefsson.org/aes/
together with Sam Steingold's library it might work under CL too [no I
haven't tried that].
HTH
Roland Kaufmann
>>>>> "RW" == Rob Warnock <····@rigden.engr.sgi.com> writes:
RW> p.s Anybody done AES in CL yet...?
I found it quite straightforward to translate the mathematical
operations described in the AES specification
(http://www.esat.kuleuven.ac.be/~rijmen/rijndael/rijndaeldocV2.zip)
into a collection of CL functions. my code is not at all optimized
for performance, so with CMUCL on a Pentium III it encrypts at only 4k
per second.
FWIW this is the rotation function I have been using:
(defun rotate-integer (integer num-bits byte-spec)
"Returns integer obtained by rotating the BYTE-SPEC'd part of INTEGER
by NUM-BITS bits. If NUM-BITS is negative, rotation is rightward."
(let ((width (byte-size byte-spec)))
(if (zerop width)
integer
(let ((num-bits-leftward (mod num-bits width))
(field (ldb byte-spec integer))
(position (byte-position byte-spec)))
(dpb (ldb (byte num-bits-leftward (- width num-bits-leftward))
field)
(byte num-bits-leftward position)
(dpb field (byte (- width num-bits-leftward)
(+ num-bits-leftward position))
integer))))))
--
I. M. Ikram ·····@cs.pdn.ac.lk
Ikram <> writes:
> >>>>> "RW" == Rob Warnock <····@rigden.engr.sgi.com> writes:
>
> RW> p.s Anybody done AES in CL yet...?
>
> I found it quite straightforward to translate the mathematical
> operations described in the AES specification
> (http://www.esat.kuleuven.ac.be/~rijmen/rijndael/rijndaeldocV2.zip)
> into a collection of CL functions. my code is not at all optimized
> for performance, so with CMUCL on a Pentium III it encrypts at only 4k
> per second.
If you would let me have a copy of the code, I could see what happens
if I run this on a compiler that understands rotation
operations. Alternatively, if you want to see what it takes to make
SBCL (closely related to CMUCL) understand rotation, see
<URL:http://www.geocrawler.com/lists/3/SourceForge/1663/25/7234222/>;
a translation for CMUCL should be straightforward. As has been
discussed here and elsewhere, the "traditional" way of making CMUCL
optimize rotation is with truly-the and a bit of stretching the
truth...
> FWIW this is the rotation function I have been using:
>
> (defun rotate-integer (integer num-bits byte-spec)
Well, we went for the same arguments, but in a different order :)
Cheers,
Christophe
--
Jesus College, Cambridge, CB5 8BL +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)