so, I am still learning, and toying around with lisp,
having fun; just to check that I might not be completely
off...
ok, I am using Nathan J. Froyd's sha: package that
computes sha1sum (that can be found here:
http://www.cs.rice.edu/~froydnj/lisp/sha1.lisp)
It does what I want, except that, it returns a vector
of integers; for instance
CL-USER> (sha:sha1sum-sequence "zozo")
#(130 154 235 231 1 41 183 140 144 245 ...)
Now, what I really would like instead is a string
like this:
"829AEBE70129B78C90F57C5921D18FFAEC89287C"
Now, I may have missed the very obvious, but I did
not find something that did that directly, so I came
up with this:
(defun sha2string (v)
(let ((s nil))
(map 'vector
#'(lambda (n)
(setf s (concatenate 'string s
(format nil "~2,'0,,X" n))))
v)
s))
(ok, indentation sucks, but I wanted it to fit
into fewer columns so that it is not mangled by
email)
It works, but my questions are: am I completely
off my rockers? and did I miss the obvious one-liner
that true lisper should know? if not, is my
coding style reasonably ok? completely bad?
thanks,
--Sylvain
Replying to myself (sorry for the bad form):
> (defun sha2string (v)
> (let ((s nil))
> (map 'vector
> #'(lambda (n)
> (setf s (concatenate 'string s
> (format nil "~2,'0,,X" n))))
> v)
> s))
what I had initially in mind, which looked more
'lispy' to me (because it doesn't use side effects)
was the following:
(defun sha2str (v &optional (i 0))
(if (eql i (length v))
""
(concatenate 'string
(format nil "~2,'0,,X" (aref v i))
(sha2str v (1+ i)))))
well, I kind of shy away from recursion when I
can easily avoid it, but this one doesn't use
side effect... is there a clear cut style
preference in such cases, or is it pretty
much a matter of personal taste?
--Sylvain
"Sylvain" <····@att.net> wrote in message
···························@speakeasy.net...
> Replying to myself (sorry for the bad form):
>> (defun sha2string (v)
>> (let ((s nil))
>> (map 'vector
>> #'(lambda (n)
>> (setf s (concatenate 'string s
>> (format nil "~2,'0,,X" n))))
>> v)
>> s))
>
> what I had initially in mind, which looked more
> 'lispy' to me (because it doesn't use side effects)
> was the following:
>
> (defun sha2str (v &optional (i 0))
> (if (eql i (length v))
> ""
> (concatenate 'string
> (format nil "~2,'0,,X" (aref v i))
> (sha2str v (1+ i)))))
>
> well, I kind of shy away from recursion when I
> can easily avoid it,
Good instinct.
> but this one doesn't use
> side effect... is there a clear cut style
> preference in such cases, or is it pretty
> much a matter of personal taste?
Don't avoid side effects on principle. Lisp style is not functional, lisp
is a multi-paradigm language, just do what suits the problem.
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
In article <······················@speakeasy.net>,
Sylvain <····@att.net> wrote:
> Replying to myself (sorry for the bad form):
> > (defun sha2string (v)
> > (let ((s nil))
> > (map 'vector
> > #'(lambda (n)
> > (setf s (concatenate 'string s
> > (format nil "~2,'0,,X" n))))
> > v)
> > s))
>
> what I had initially in mind, which looked more
> 'lispy' to me (because it doesn't use side effects)
> was the following:
>
> (defun sha2str (v &optional (i 0))
> (if (eql i (length v))
> ""
> (concatenate 'string
> (format nil "~2,'0,,X" (aref v i))
> (sha2str v (1+ i)))))
>
> well, I kind of shy away from recursion when I
> can easily avoid it, but this one doesn't use
> side effect... is there a clear cut style
> preference in such cases, or is it pretty
> much a matter of personal taste?
But why don't you shy away from a completely inefficient
implementation for a relatively low-level operation
then? This is exactly the style of programming that
Lisp makes look very slow and inefficient.
- Recursion in Common Lisp has limits. Don't use
it like this.
CL-USER 2 > (sha2str (map 'vector 'identity (loop for i below 5000 collect 13)))
Stack overflow (stack size 16000).
1 (continue) Extend stack by 50%.
2 Extend stack by 300%.
3 (abort) Return to level 0.
4 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other options
CL-USER 3 : 1 > (apropos "LIMIT" "CL")
- FORMAT used to output two hex characters.
Most implementations have very inefficient FORMAT
implementations.
- CONCATENATE called in a recursive way,
will produce tons of garbage.
? (sha2str #(0 1 2 3 4 5 6 7 8 9))
Calling (CONCATENATE STRING "09" "")
CONCATENATE returned "09"
Calling (CONCATENATE STRING "08" "09")
CONCATENATE returned "0809"
Calling (CONCATENATE STRING "07" "0809")
CONCATENATE returned "070809"
Calling (CONCATENATE STRING "06" "070809")
CONCATENATE returned "06070809"
Calling (CONCATENATE STRING "05" "06070809")
CONCATENATE returned "0506070809"
Calling (CONCATENATE STRING "04" "0506070809")
CONCATENATE returned "040506070809"
Calling (CONCATENATE STRING "03" "040506070809")
CONCATENATE returned "03040506070809"
Calling (CONCATENATE STRING "02" "03040506070809")
CONCATENATE returned "0203040506070809"
Calling (CONCATENATE STRING "01" "0203040506070809")
CONCATENATE returned "010203040506070809"
Calling (CONCATENATE STRING "00" "010203040506070809")
CONCATENATE returned "00010203040506070809"
"00010203040506070809"
Since you know that your input is a vector (which has a length),
you can allocate a string with the right size and fill it with
the right contents.
>
> --Sylvain
Better still why write it at all.
It is a part of the windows operation system (Win200 up uses this
algorithm to encrypt passwords)
Also it is available as a library in UNIX.
This is a hard algorithm to get cryptographically sound.
Why don't you just interface to a tested and proven algorithm.
Unless you are a security/cryptology expert it is rarely a good idea to
implement these things yourself.
On Wed, 30 Nov 2005 05:47:49 +0100, Rainer Joswig <······@lisp.de> wrote:
> In article <······················@speakeasy.net>,
> Sylvain <····@att.net> wrote:
>
>> Replying to myself (sorry for the bad form):
>> > (defun sha2string (v)
>> > (let ((s nil))
>> > (map 'vector
>> > #'(lambda (n)
>> > (setf s (concatenate 'string s
>> > (format nil "~2,'0,,X" n))))
>> > v)
>> > s))
>>
>> what I had initially in mind, which looked more
>> 'lispy' to me (because it doesn't use side effects)
>> was the following:
>>
>> (defun sha2str (v &optional (i 0))
>> (if (eql i (length v))
>> ""
>> (concatenate 'string
>> (format nil "~2,'0,,X" (aref v i))
>> (sha2str v (1+ i)))))
>>
>> well, I kind of shy away from recursion when I
>> can easily avoid it, but this one doesn't use
>> side effect... is there a clear cut style
>> preference in such cases, or is it pretty
>> much a matter of personal taste?
>
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
In article <·················@mjolner.upc.no>,
John Thingstad <··············@chello.no> wrote:
> Better still why write it at all.
> It is a part of the windows operation system (Win200 up uses this
> algorithm to encrypt passwords)
> Also it is available as a library in UNIX.
> This is a hard algorithm to get cryptographically sound.
> Why don't you just interface to a tested and proven algorithm.
> Unless you are a security/cryptology expert it is rarely a good idea to
> implement these things yourself.
Uh, he's not implementing SHA1. He's just implementing a routine to
turn the numeric output of the SHA1 algorithm into the typical hex
string you usually see.
Even so, how can an implementation of a known algorithm be hard to get
cryptographically sound? You implement the spec and run it against the
test suite. It's either going to work or it's going to not.
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
On Wed, 30 Nov 2005 15:40:20 +0100, Brian Downing
<·············@lavos.net> wrote:
> In article <·················@mjolner.upc.no>,
> John Thingstad <··············@chello.no> wrote:
>> Better still why write it at all.
>> It is a part of the windows operation system (Win200 up uses this
>> algorithm to encrypt passwords)
>> Also it is available as a library in UNIX.
>> This is a hard algorithm to get cryptographically sound.
>> Why don't you just interface to a tested and proven algorithm.
>> Unless you are a security/cryptology expert it is rarely a good idea to
>> implement these things yourself.
>
> Even so, how can an implementation of a known algorithm be hard to get
> cryptographically sound? You implement the spec and run it against the
> test suite. It's either going to work or it's going to not.
Beacuse 100 subdly different SHA1 algorithms are more problem than
it is worth.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
"John Thingstad" <··············@chello.no> writes:
> On Wed, 30 Nov 2005 15:40:20 +0100, Brian Downing
> <·············@lavos.net> wrote:
>
>> Even so, how can an implementation of a known algorithm be hard to get
>> cryptographically sound? You implement the spec and run it against the
>> test suite. It's either going to work or it's going to not.
>
> Beacuse 100 subdly different SHA1 algorithms are more problem than
> it is worth.
No-one mentioned different SHA-1 algorithms, let alone 100 of them,
other than you. It looks very much as though you are constructing a
strawman and attacking it, but you're even failing to communicate your
strawman effectively to others, so you end up making no sense at all.
Christophe
On Wed, 30 Nov 2005 16:34:57 +0100, Christophe Rhodes <·····@cam.ac.uk>
wrote:
> "John Thingstad" <··············@chello.no> writes:
>
>> On Wed, 30 Nov 2005 15:40:20 +0100, Brian Downing
>> <·············@lavos.net> wrote:
>>
>>> Even so, how can an implementation of a known algorithm be hard to get
>>> cryptographically sound? You implement the spec and run it against the
>>> test suite. It's either going to work or it's going to not.
>>
>> Beacuse 100 subdly different SHA1 algorithms are more problem than
>> it is worth.
>
> No-one mentioned different SHA-1 algorithms, let alone 100 of them,
> other than you. It looks very much as though you are constructing a
> strawman and attacking it, but you're even failing to communicate your
> strawman effectively to others, so you end up making no sense at all.
>
> Christophe
Perhaps my view is biased by having to spend a week debugging a Delfi
program that used a SHA1 API incompatible with the OS.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
"John Thingstad" <··············@chello.no> writes:
> Perhaps my view is biased by having to spend a week debugging a Delfi
> program that used a SHA1 API incompatible with the OS.
Yeah, or else perhaps you're just spouting nonsense.
Christophe
John Thingstad wrote:
> Better still why write it at all.
> It is a part of the windows operation system (Win200 up uses this
> algorithm to encrypt passwords)
> Also it is available as a library in UNIX.
note that I was not trying to rewrite sha1sum, I was using
a nice library (and someone pointed out to me a more complete
and recent library from the same author); the only thing
I was trying was to convert the format of the result of
some of its function into a format more convenient for my
application, that's all.
--Sylvain
Rainer Joswig wrote:
>
> But why don't you shy away from a completely inefficient
> implementation for a relatively low-level operation
> then?
well, that's because I don't know what I am doing! :-) I
am learning the language and the different way of thinking
about programming that goes with it (part of the appeal
in the first place) -- getting the syntax right and something
running is the easy part, getting it right takes a little
longer; I did have a hunch though that there
must be a better way of doing the thing, hence my post (lots
of interesting alternative implementations by the way, thanks
a bunch!)
--Sylvain
Sylvain <····@att.net> writes:
> am learning the language and the different way of thinking
> about programming that goes with it (part of the appeal
> in the first place)
Here's a summary of proposed solutions so far. YMMV as to elegance of
implementation and opportunity for optimization.
(defun v1 (v)
;; no problem with CALL-ARGUMENTS-LIMIT since v is expected to be small?
(apply #'concatenate 'string
(loop for e across v collect (format nil "~2,'0,,X" e))))
(defun v2 (v)
;; Use format to iterate across a list
(format nil "~{~2,'0,,X~}" (coerce v 'list)))
(defun v3 (v)
(with-output-to-string (s)
(loop for e across v collect (format s "~2,'0,,X" e))))
;; precompute string of known length and fill it
(let ((a (loop with a = (make-array 256 :element-type 'string)
for i below (length a)
do (setf (aref a i) (format nil "~2,'0,,X" i))
finally (return a))))
;; Use precomputed array #("01" "02" ...)
(defun v4 (v)
(let ((s (make-string (* 2 (length v)))))
(loop for e across v
for i from 0 by 2
do (replace s (aref a e) :start1 i))
s)))
(let ((a (loop for i below 16 collect (digit-char i 16) into l
finally (return (coerce l 'string)))))
;; Favour the aboev instead of
;;(loop with a = (make-string 16)
;; for i below (length a)
;; do (setf (aref a i) (digit-char i 16))
;; finally (return a))
;; Less readable, and strictly equivalent
;; (don't count set-up costs for constant a).
;; Use precomputed array "012345..."
(defun v5 (v)
;; yuck, this starts to resemble C code
(let ((s (make-string (* 2 (length v)))))
(loop for e across v
for i from 0 by 2
do (setf (char s i) (char a (ash e -4))
(char s (1+ i)) (char a (logand e 15))))
s)))
And I didn't even show series code.
The discussion of what happens with incorrect input is left as an
exercise. What form is most robust?
All these functions exhibit varying timing and consing behaviour in
clisp (see measures below). You'll notice that v1-v3 cons up garbage
at run-time, while the others don't. But creation of garbage is not
the only measure to apply. It may even be a misleading performance
measure.
If you dig further into this, you'll learn that it's highly
implementation dependend which of the 5 forms has the best run-time
performance. Whether the implementation compiles to byte code (CLISP)
or native code make a difference as to which goes fastest. Another
difference may be caused by various helper functions (e.g. is REPLACE
or FORMAT compiled or implemented efficiently?).
Also note that my v4-v5 were not bug-free right from the start. More
lines of code is more room for bugs. One should always strike for
readability and some form of conciseness, extensibility and then check
performance (although I tend to not follow that advice myself every so
often...).
BTW, it surprised me that v2 ends up consing less in CLISP than v3
(which seems just more explicit about string-streams), despite COERCE.
(ext:times(v1 #(12 13 1 1 255 0 #xa0 #8r12 240)))
Permanent Temporary
Class instances bytes instances bytes
----- --------- --------- --------- ---------
SIMPLE-STRING 1 28 54 5940
STRING-STREAM 0 0 18 1224
STRING 0 0 27 648
STREAM 0 0 9 648
CONS 0 0 36 288
----- --------- --------- --------- ---------
Total 1 28 144 8748
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 8776 Bytes
"0C0D0101FF00A00AF0"
(ext:times(v2 #(12 13 1 1 255 0 #xa0 #8r12 240)))
Permanent Temporary
Class instances bytes instances bytes
----- --------- --------- --------- ---------
SIMPLE-STRING 1 28 37 4168
STRING-STREAM 0 0 10 680
STREAM 0 0 9 648
STRING 0 0 19 456
CONS 0 0 36 288
----- --------- --------- --------- ---------
Total 1 28 111 6240
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 6268 Bytes
"0C0D0101FF00A00AF0"
(ext:times(v3 #(12 13 1 1 255 0 #xa0 #8r12 240)))
Permanent Temporary
Class instances bytes instances bytes
----- --------- --------- --------- ---------
SIMPLE-STRING 1 28 37 4168
STRING-STREAM 0 0 10 680
STREAM 0 0 9 648
STRING 0 0 19 456
CONS 0 0 45 360
----- --------- --------- --------- ---------
Total 1 28 120 6312
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 6340 Bytes
"0C0D0101FF00A00AF0"
(ext:times(v4 #(12 13 1 1 255 0 #xa0 #8r12 240)))
Permanent Temporary
Class instances bytes instances bytes
----- --------- --------- --------- ---------
SIMPLE-STRING 1 28 0 0
----- --------- --------- --------- ---------
Total 1 28 0 0
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 28 Bytes
"0C0D0101FF00A00AF0"
(ext:times(v5 #(12 13 1 1 255 0 #xa0 #8r12 240)))
Permanent Temporary
Class instances bytes instances bytes
----- --------- --------- --------- ---------
SIMPLE-STRING 1 28 0 0
----- --------- --------- --------- ---------
Total 1 28 0 0
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 28 Bytes
"0C0D0101FF00A00AF0"
Jorg Hohle
Telekom/T-Systems Technology Center
Joerg Hoehle <······@users.sourceforge.net> writes:
Personally I would prefer v2 for simplicity. For more optimal code I
would go along with something similar to v5 if computing the length
(or if you know the length) of the array is cheaper than concatenating
the string result:
(defconstant +hex-arr+
#.(make-array 256
:element-type '(string 2)
:initial-contents (loop for i from 0 below 256
collect (format nil "~2,'0,,X" i))))
(defun bytearray-to-hexstr (v &optional (vlen (* 2 (length v))))
(let ((s (make-string vlen)))
(loop for e across v
for i from 0 by 2
do (setf (char s i) (char (aref +hex-arr+ e) 0)
(char s (1+ i)) (char (aref +hex-arr+ e) 1)))
s))
If the compiler takes into account that the length of each element is
two it should be able to optimize the memory reference quite a bit, if
not you migth use two arrays (strings) to hold each nibble character.
Petter
--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
On Mon, 28 Nov 2005 11:18:29 -0800, Sylvain <····@att.net> wrote:
> Replying to myself (sorry for the bad form):
>> (defun sha2string (v)
>> (let ((s nil))
>> (map 'vector
>> #'(lambda (n)
>> (setf s (concatenate 'string s
>> (format nil "~2,'0,,X" n))))
>> v)
>> s))
>
> what I had initially in mind, which looked more 'lispy' to me (because
> it doesn't use side effects) was the following:
>
> (defun sha2str (v &optional (i 0))
> (if (eql i (length v))
> ""
> (concatenate 'string
> (format nil "~2,'0,,X" (aref v i))
> (sha2str v (1+ i)))))
I'd probably use the loop macro for something similar:
[7] CL-USER(26): (let ((v #(130 154 235 231 1 41 183 140 144 245)))
(apply #'concatenate 'string
(loop for i from 0 to (- (length v) 1)
collect (format nil "~2,'0,,X" (aref v i)))))
"829aebe70129b78c90f5"
[7] CL-USER(27):
Giorgos Keramidas <········@ceid.upatras.gr> writes:
> On Mon, 28 Nov 2005 11:18:29 -0800, Sylvain <····@att.net> wrote:
>> Replying to myself (sorry for the bad form):
>>> (defun sha2string (v)
>>> (let ((s nil))
>>> (map 'vector
>>> #'(lambda (n)
>>> (setf s (concatenate 'string s
>>> (format nil "~2,'0,,X" n))))
>>> v)
>>> s))
>>
>> what I had initially in mind, which looked more 'lispy' to me (because
>> it doesn't use side effects) was the following:
>>
>> (defun sha2str (v &optional (i 0))
>> (if (eql i (length v))
>> ""
>> (concatenate 'string
>> (format nil "~2,'0,,X" (aref v i))
>> (sha2str v (1+ i)))))
>
> I'd probably use the loop macro for something similar:
>
> [7] CL-USER(26): (let ((v #(130 154 235 231 1 41 183 140 144 245)))
> (apply #'concatenate 'string
> (loop for i from 0 to (- (length v) 1)
> collect (format nil "~2,'0,,X" (aref v i)))))
> "829aebe70129b78c90f5"
> [7] CL-USER(27):
>
In this particular case i prefer :
- WITH-OUTPUT-TO-STRING (to avoid CONSing up a list just to concatenate it)
- the ACROSS loop clause (to avoid aref .. we don't need it)
- WRITE (to avoid the fugly format string)
CL-USER> (let ((v #(130 154 235 231 1 41 183 140 144 245)))
(with-output-to-string (s)
(loop for i across v
do (write i :stream s :base 16))))
"829AEBE7129B78C90F5"
CL-USER>
--
drewc at tech dot coop
In article <··············@rift.com>, drewc <·····@rift.com> wrote:
> In this particular case i prefer :
>
> - WRITE (to avoid the fugly format string)
>
> CL-USER> (let ((v #(130 154 235 231 1 41 183 140 144 245)))
> (with-output-to-string (s)
> (loop for i across v
> do (write i :stream s :base 16))))
> "829AEBE7129B78C90F5"
> CL-USER>
Unfortunately the fugly format string does the right thing, whereas
WRITE doesn't:
CL-USER> (let ((v #(1 1 1 1 1 1 1 1 1 1)))
(with-output-to-string (s)
(loop for i across v
do (write i :stream s :base 16))))
"1111111111"
I think making that work without FORMAT will be fuglier than "~2,'0X",
but I'd love to see evidence to the contrary.
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
Brian Downing <·············@lavos.net> writes:
> In article <··············@rift.com>, drewc <·····@rift.com> wrote:
>> In this particular case i prefer :
>>
>> - WRITE (to avoid the fugly format string)
>>
>> CL-USER> (let ((v #(130 154 235 231 1 41 183 140 144 245)))
>> (with-output-to-string (s)
>> (loop for i across v
>> do (write i :stream s :base 16))))
>> "829AEBE7129B78C90F5"
>> CL-USER>
>
> Unfortunately the fugly format string does the right thing, whereas
> WRITE doesn't:
>
> CL-USER> (let ((v #(1 1 1 1 1 1 1 1 1 1)))
> (with-output-to-string (s)
> (loop for i across v
> do (write i :stream s :base 16))))
> "1111111111"
>
> I think making that work without FORMAT will be fuglier than "~2,'0X",
> but I'd love to see evidence to the contrary.
oh hrm... my bad. misread the spec :)
I usually bring up OUT[1] when talking about FORMAT replacements, but
i'm not sure it has anything on FORMAT int this case. I still think format
strings are fugly, although i can't offer a reasonable alternative.
[1] http://cs-www.cs.yale.edu/homes/dvm/format-stinks.html
drewc
>
> -bcd
> --
> *** Brian Downing <bdowning at lavos dot net>
--
drewc at tech dot coop
On Wed, 14 Dec 2005 08:25:39 +0100, drewc <·····@rift.com> wrote:
>
>
> I usually bring up OUT[1] when talking about FORMAT replacements, but
> i'm not sure it has anything on FORMAT int this case. I still think
> format
> strings are fugly, although i can't offer a reasonable alternative.
>
In my experience output and input be it GUI or console is nearly always
ugly. So I like formats that minimize the ugliness by minimizing
the space they take up. As such format strings work fine by my philosophy.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On Tue, 13 Dec 2005 13:29:45 GMT, drewc <·····@rift.com> wrote:
> Giorgos Keramidas <········@ceid.upatras.gr> writes:
>> I'd probably use the loop macro for something similar:
>>
>> [7] CL-USER(26): (let ((v #(130 154 235 231 1 41 183 140 144 245)))
>> (apply #'concatenate 'string
>> (loop for i from 0 to (- (length v) 1)
>> collect (format nil "~2,'0,,X" (aref v i)))))
>> "829aebe70129b78c90f5"
>> [7] CL-USER(27):
>>
>
> In this particular case i prefer :
>
> - WITH-OUTPUT-TO-STRING (to avoid CONSing up a list just to
> concatenate it)
> - the ACROSS loop clause (to avoid aref .. we don't need it)
> - WRITE (to avoid the fugly format string)
>
> CL-USER> (let ((v #(130 154 235 231 1 41 183 140 144 245)))
> (with-output-to-string (s)
> (loop for i across v
> do (write i :stream s :base 16))))
> "829AEBE7129B78C90F5"
> CL-USER>
Much cleaner, thanks.
I still have a lot to learn about the way loop works :)
Giorgos Keramidas <········@ceid.upatras.gr> writes:
> On Tue, 13 Dec 2005 13:29:45 GMT, drewc <·····@rift.com> wrote:
>> Giorgos Keramidas <········@ceid.upatras.gr> writes:
>>> I'd probably use the loop macro for something similar:
>>>
>>> [7] CL-USER(26): (let ((v #(130 154 235 231 1 41 183 140 144 245)))
>>> (apply #'concatenate 'string
>>> (loop for i from 0 to (- (length v) 1)
>>> collect (format nil "~2,'0,,X" (aref v i)))))
>>> "829aebe70129b78c90f5"
>>> [7] CL-USER(27):
>>>
>>
>> In this particular case i prefer :
>>
>> - WITH-OUTPUT-TO-STRING (to avoid CONSing up a list just to
>> concatenate it)
If you don't want consing, then you should allocate the output beforehand.
>> - the ACROSS loop clause (to avoid aref .. we don't need it)
>> - WRITE (to avoid the fugly format string)
>>
>> CL-USER> (let ((v #(130 154 235 231 1 41 183 140 144 245)))
>> (with-output-to-string (s)
>> (loop for i across v
>> do (write i :stream s :base 16))))
>> "829AEBE7129B78C90F5"
>> CL-USER>
( (lambda (v)
(loop :with s = (make-string (* 2 (length v)))
:with h = "0123456789abcdef"
:with i = -1
:for byte :across v
:do (setf (aref s (incf i)) (aref h (truncate byte 16))
(aref s (incf i)) (aref h (mod byte 16)))
:finally (return s)))
#(130 154 235 231 1 41 183 140 144 245))
--> "829aebe70129b78c90f5"
WRITE-OUTPUT-TO-STRING can allocate in O(log(n)) in time at the cost
of allocating between two and four times the needed space, in addition
to the final copy. Compared to this allocating N cons cells will
probably be more efficient (given a non-idiotic allocator), and
CONCATENATE has the opportunity to tally the exact size needed for the
result. Or WRITE-OUTPUT-TO-STRING can be implemented doing exactly
that, building a list of the written chunks and concatenating them at
the end, so you don't win anything, in the best case.
Now if you had written:
(with-output-to-string (s (make-string (length (* 2 v)))) ...)
it would be different...
But if you're in for performance I bet most compilers will be able to
open-code AREF and not WRITE.
> Much cleaner, thanks.
>
> I still have a lot to learn about the way loop works :)
--
__Pascal Bourguignon__ http://www.informatimago.com/
"You cannot really appreciate Dilbert unless you read it in the
original Klingon"
Giorgos Keramidas <········@ceid.upatras.gr> writes:
> I'd probably use the loop macro for something similar:
>
> [7] CL-USER(26): (let ((v #(130 154 235 231 1 41 183 140 144 245)))
> (apply #'concatenate 'string
> (loop for i from 0 to (- (length v) 1)
> collect (format nil "~2,'0,,X" (aref v i)))))
> "829aebe70129b78c90f5"
You can loop across vectors like this:
(apply #'concatenate 'string (loop for e across v
collect (format nil "~2,'0,,X" e)))
Or you could convert the vector into a list and just use format:
(format t "~{~2,'0,,X~}" (coerce v 'list))
Petter
--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
"Sylvain" <····@att.net> wrote in message
·····································@speakeasy.net...
>
> Now, I may have missed the very obvious, but I did
> not find something that did that directly, so I came
> up with this:
>
> (defun sha2string (v)
> (let ((s nil))
> (map 'vector
> #'(lambda (n)
> (setf s (concatenate 'string s
> (format nil "~2,'0,,X" n))))
> v)
> s))
>
> (ok, indentation sucks, but I wanted it to fit
> into fewer columns so that it is not mangled by
> email)
>
> It works, but my questions are: am I completely
> off my rockers? and did I miss the obvious one-liner
> that true lisper should know? if not, is my
> coding style reasonably ok? completely bad?
>
No. Yes. Yes. No.
How about...
(defun sha2string (v)
(format nil "~{~2,'0,,X~}" (coerce v 'list)))
--
Geof
Sylvain <····@att.net> writes:
> ok, I am using Nathan J. Froyd's sha: package that
> computes sha1sum (that can be found here:
> http://www.cs.rice.edu/~froydnj/lisp/sha1.lisp)
[ You might be interested in ironclad by the same author, which has
bug fixes relative to that code. ]
> Now, what I really would like instead is a string
> like this:
>
> "829AEBE70129B78C90F57C5921D18FFAEC89287C"
I'd probably write
(defun digest2string (v)
(format nil "~{~2,'0X~}" (coerce v 'list)))
or maybe
(defun digest2string (v)
(with-output-to-string (s)
(loop for x across v
do (format s "~2,'0X" x))))
> Now, I may have missed the very obvious, but I did
> not find something that did that directly, so I came
> up with this:
>
> (defun sha2string (v)
> (let ((s nil))
> (map 'vector
> #'(lambda (n)
> (setf s (concatenate 'string s
> (format nil "~2,'0,,X" n))))
> v)
> s))
>
> (ok, indentation sucks, but I wanted it to fit
> into fewer columns so that it is not mangled by
> email)
>
> It works, but my questions are: am I completely
> off my rockers? and did I miss the obvious one-liner
> that true lisper should know? if not, is my
> coding style reasonably ok? completely bad?
It's a little bit eccentric: you're doing a lot of needless work
(though for one-liners like this it doesn't really matter, since the
length of the digest is 20 8-bit elements). The mapping of a
concatenate expression smells to me -- in this case, you'll get O(n^2)
performance for an O(n) operation.
Christophe
Christophe Rhodes wrote:
> I'd probably write
> (defun digest2string (v)
> (format nil "~{~2,'0X~}" (coerce v 'list)))
ah! this one I like a lot better than my code :-)
I did play around with coerce but without success
because I didn't think of using it to turn the
vector into a list first (thought I could go to
strings directly, duh)...
thanks!
--Sylvain
Sylvain wrote:
> Christophe Rhodes wrote:
> > I'd probably write
> > (defun digest2string (v)
> > (format nil "~{~2,'0X~}" (coerce v 'list)))
>
> ah! this one I like a lot better than my code :-)
> I did play around with coerce but without success
> because I didn't think of using it to turn the
> vector into a list first (thought I could go to
> strings directly, duh)...
>
> thanks!
>
> --Sylvain
You could also do something like,
(defun digest2string (v)
(let ((*print-base* 16))
(with-output-to-string (s)
(map nil #'(lambda (e) (princ e s)) v)
s)))
which shows off some other features, and avoids format line noise, not
that I think that is so bad.
This exercise gives me a surprisingly bad feeling.
1) Format doesn't iterate over general sequences.
2) I originally expected with-output-to-string to capture princ's
output, and tried just
(with-output-to-string (s) (map nil #'princ v) s)
but of course princ still goes to *standard-ouput* without the extra
argument, which requires an anonymous function. I had expected to find
a built-in macro to divert everything destined for a stream (defaulting
to *standard-output*) to a string, then return that string.
··············@hotmail.com wrote:
> You could also do something like,
>
> (defun digest2string (v)
> (let ((*print-base* 16))
> (with-output-to-string (s)
> (map nil #'(lambda (e) (princ e s)) v)
> s)))
This of course has the same problem with non-two-digit vector elements
that Pascal Bourguignon pointed out on another example using format
"~x".
Ugh.
In article <························@g14g2000cwa.googlegroups.com>,
··············@hotmail.com <············@gmail.com> wrote:
> 2) I originally expected with-output-to-string to capture princ's
> output, and tried just
>
> (with-output-to-string (s) (map nil #'princ v) s)
>
> but of course princ still goes to *standard-ouput* without the extra
> argument, which requires an anonymous function.
(asdf:operate 'asdf:load-op :arnesi)
(with-output-to-string (s) (map nil (arnesi:rcurry #'princ s) v))
> I had expected to find
> a built-in macro to divert everything destined for a stream (defaulting
> to *standard-output*) to a string, then return that string.
(with-output-to-string (*standard-output*) (map nil #'princ v))
Remember, any binding construct with a special variable will make a
dynamic binding, not just LET and friends.
You also needn't return the string-stream out of the expression as you
did above. WITH-OUTPUT-TO-STRING always returns the generated string.
If it returned the stream you wouldn't get what you wanted.
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
Brian Downing wrote:
> In article <························@g14g2000cwa.googlegroups.com>,
> ··············@hotmail.com <············@gmail.com> wrote:
>
> > I had expected to find
> > a built-in macro to divert everything destined for a stream (defaulting
> > to *standard-output*) to a string, then return that string.
>
> (with-output-to-string (*standard-output*) (map nil #'princ v))
>
> Remember, any binding construct with a special variable will make a
> dynamic binding, not just LET and friends.
OW! You made my head hurt. :-)
> You also needn't return the string-stream out of the expression as you
> did above. WITH-OUTPUT-TO-STRING always returns the generated string.
> If it returned the stream you wouldn't get what you wanted.
Not sure what mistake I got that made me think otherwise. I think
reading the CLHS entry bit about the optional argument "string"
confused me.
Still, to get dependable 2-digit results, I'm not sure I like anything
better than
(format t "~2,'0X" e)
> -bcd
> --
> *** Brian Downing <bdowning at lavos dot net>
(defun digest2string (v)
(with-output-to-string (s)
(map nil #'(lambda (e) (format s "~2,'0X" e)) v)))
···············@hotmail.com" <············@gmail.com> writes:
> Still, to get dependable 2-digit results, I'm not sure I like anything
> better than
> (format t "~2,'0X" e)
Well, what about:
(defconstant *hex-values* #("00" "01" ... "FF"))
(aref *hex-values* e)
--
Thomas A. Russ, USC/Information Sciences Institute
Christophe Rhodes <·····@cam.ac.uk> writes:
(defun digest2string (v)
(with-output-to-string (s)
(loop for x across v
do (format s "~2,'0X" x))))
This is nice, since it uses the string stream to collect the values. If
efficiency is really critical, one could avoid the FORMAT call (which
often tends to be slow) and subsitute a 256 element lookup table:
(defconstant *hex-codes* #("00" "01" ... "FF"))
(defun digest2string (v)
(with-output-to-string (s)
(loop for x across v
do (write-string (aref *hex-codes* x) s))))
--
Thomas A. Russ, USC/Information Sciences Institute
···@sevak.isi.edu (Thomas A. Russ) writes:
> Christophe Rhodes <·····@cam.ac.uk> writes:
>
> (defun digest2string (v)
> (with-output-to-string (s)
> (loop for x across v
> do (format s "~2,'0X" x))))
>
>
> This is nice, since it uses the string stream to collect the values. If
> efficiency is really critical, one could avoid the FORMAT call (which
> often tends to be slow) and subsitute a 256 element lookup table:
>
> (defconstant *hex-codes* #("00" "01" ... "FF"))
Surely we don't have to write that by hand; that's not The Lisp Way!
(defconstant *hex-codes* #.(coerce (loop for i from #x00 to #xff collect (format nil "~2,'0x" i)) 'vector))
;-)
-Peter
--
Peter Seibel * ·····@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/
Peter Seibel <·····@gigamonkeys.com> writes:
> ···@sevak.isi.edu (Thomas A. Russ) writes:
>
>> This is nice, since it uses the string stream to collect the values. If
>> efficiency is really critical, one could avoid the FORMAT call (which
>> often tends to be slow) and subsitute a 256 element lookup table:
>>
>> (defconstant *hex-codes* #("00" "01" ... "FF"))
>
> Surely we don't have to write that by hand; that's not The Lisp Way!
>
> (defconstant *hex-codes* #.(coerce (loop for i from #x00 to #xff collect (format nil "~2,'0x" i)) 'vector))
Well, you can write that, but it's not the SBCL way, as it will rudely
remind you if you reexecute that definition ;-)
Christophe
[ (let ((hex-codes #.(coerce ...)))
(defun ...)) ]
Christophe Rhodes <·····@cam.ac.uk> writes:
> Peter Seibel <·····@gigamonkeys.com> writes:
>
>> ···@sevak.isi.edu (Thomas A. Russ) writes:
>>
>>> This is nice, since it uses the string stream to collect the values. If
>>> efficiency is really critical, one could avoid the FORMAT call (which
>>> often tends to be slow) and subsitute a 256 element lookup table:
>>>
>>> (defconstant *hex-codes* #("00" "01" ... "FF"))
>>
>> Surely we don't have to write that by hand; that's not The Lisp Way!
>>
>> (defconstant *hex-codes* #.(coerce (loop for i from #x00 to #xff collect (format nil "~2,'0x" i)) 'vector))
>
> Well, you can write that, but it's not the SBCL way, as it will rudely
> remind you if you reexecute that definition ;-)
Yeah, but doesn't the original (defconstant ...) with the handwritten
vector suffer from the same problem?
-Peter
--
Peter Seibel * ·····@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/
Peter Seibel <·····@gigamonkeys.com> writes:
> Yeah, but doesn't the original (defconstant ...) with the handwritten
> vector suffer from the same problem?
Yes, it does.
Christophe
Sylvain wrote:
> so, I am still learning, and toying around with lisp,
> having fun; just to check that I might not be completely
> off...
>
> ok, I am using Nathan J. Froyd's sha: package that
> computes sha1sum (that can be found here:
> http://www.cs.rice.edu/~froydnj/lisp/sha1.lisp)
>
> It does what I want, except that, it returns a vector
> of integers; for instance
>
> CL-USER> (sha:sha1sum-sequence "zozo")
> #(130 154 235 231 1 41 183 140 144 245 ...)
>
> Now, what I really would like instead is a string
> like this:
>
> "829AEBE70129B78C90F57C5921D18FFAEC89287C"
>
And YAW ...
(defun integer8v-string (v)
(flet ((hexn (n) (char "0123456789ABCDEF" n)))
(let ((string (make-array (* 2 (length v)) :element-type 'character
:fill-pointer 0)))
(loop for n across v do
(vector-push (hexn (ldb (byte 4 4) n)) string)
(vector-push (hexn (ldb (byte 4 0) n)) string))
string)))
CL-USER 10 > (integer8v-string #(130 154 235 231 1 41 183 140 144))
"829AEBE70129B78C90"
Wade
On Mon, 28 Nov 2005 10:46:45 -0800, Sylvain <····@att.net> wrote:
> so, I am still learning, and toying around with lisp,
> having fun; just to check that I might not be completely
> off...
>
> ok, I am using Nathan J. Froyd's sha: package that
> computes sha1sum (that can be found here:
> http://www.cs.rice.edu/~froydnj/lisp/sha1.lisp)
>
> It does what I want, except that, it returns a vector
> of integers; for instance
>
> CL-USER> (sha:sha1sum-sequence "zozo")
> #(130 154 235 231 1 41 183 140 144 245 ...)
>
> Now, what I really would like instead is a string
> like this:
>
> "829AEBE70129B78C90F57C5921D18FFAEC89287C"
>
maybe:
* (defun to-hex-str (ar)
(format nil "~x" (reduce (lambda (a b) (+ (* a 256) b)) ar)))
* (to-hex-str #(130 154 235 231 1 41 183 140 144 245))
"829AEBE70129B78C90F5"
*
-- Michael
Michael Naunton <···@news.bellatlantic.net> writes:
> * (defun to-hex-str (ar)
> (format nil "~x" (reduce (lambda (a b) (+ (* a 256) b)) ar)))
>
> * (to-hex-str #(130 154 235 231 1 41 183 140 144 245))
>
> "829AEBE70129B78C90F5"
This is going to look a bit petty, but your function gets the string
wrong in one sixteenth of the cases, when the first element is less
than 16 (and so the first hex digit is 0).
Christophe
Christophe Rhodes <·····@cam.ac.uk> writes:
> Michael Naunton <···@news.bellatlantic.net> writes:
>
>> * (defun to-hex-str (ar)
>> (format nil "~x" (reduce (lambda (a b) (+ (* a 256) b)) ar)))
>>
>> * (to-hex-str #(130 154 235 231 1 41 183 140 144 245))
>>
>> "829AEBE70129B78C90F5"
>
> This is going to look a bit petty, but your function gets the string
> wrong in one sixteenth of the cases, when the first element is less
> than 16 (and so the first hex digit is 0).
Slightly more often than that.
(to-hex-str #(0 0 0 0 0 1 2)) --> "102"
--
__Pascal Bourguignon__ http://www.informatimago.com/
Pascal Bourguignon <····@mouse-potato.com> writes:
> Christophe Rhodes <·····@cam.ac.uk> writes:
>
>> This is going to look a bit petty, but your function gets the string
>> wrong in one sixteenth of the cases, when the first element is less
>> than 16 (and so the first hex digit is 0).
>
> Slightly more often than that.
No, exactly that often.
> (to-hex-str #(0 0 0 0 0 1 2)) --> "102"
The first hex digit is 0 here, and so this is not a counterexample to
my claim.
Christophe