Converting bytes to an integer

[Gisle Sælensminde]

I need to convert a byte array representing an integer into a CL
integer type, but I can not find an elegant way of doing it. I can
always make a function like the one below, that converts the bytes
in the given range.

(defun bytes-to-int (bytearr start end)
"Convert the bits of a byte array to an integer"
(let ((intval 0))
(loop for i downfrom end to start
and j from 0 to (- end start)
sum (* (aref bytearr i)
(expt 2 (* j 8)))
into intval
finally return intval)))

Are there any better way?

--
--
Gisle Sælensminde ( gi...@ii.uib.no )

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going
to land, and it could be dangerous sitting under them as they fly
overhead. (from RFC 1925)

[Raymond Wiker]

Gisle Sælensminde <gi...@apal.ii.uib.no> writes:

> I need to convert a byte array representing an integer into a CL
> integer type, but I can not find an elegant way of doing it. I can
> always make a function like the one below, that converts the bytes
> in the given range.
>
> (defun bytes-to-int (bytearr start end)
> "Convert the bits of a byte array to an integer"
> (let ((intval 0))
> (loop for i downfrom end to start
> and j from 0 to (- end start)
> sum (* (aref bytearr i)
> (expt 2 (* j 8)))
> into intval
> finally return intval)))
>
> Are there any better way?

You could use "dpb" for depositing bytes directly into the
destination:

(defun bytes-to-int2 (bytearr start end)
(let ((res 0))

(loop for i downfrom end to start

and j from 0 by 8
do (setf res (dpb (aref bytearr i)
(byte 8 j)
res)))
res))

--
Raymond Wiker Mail: Raymon...@fast.no
Senior Software Engineer Web: http://www.fast.no/
Fast Search & Transfer ASA Phone: +47 23 01 11 60
P.O. Box 1677 Vika Fax: +47 35 54 87 99
NO-0120 Oslo, NORWAY Mob: +47 48 01 11 60

Try FAST Search: http://alltheweb.com/

[Espen Vestre]

Gisle Sælensminde <gi...@apal.ii.uib.no> writes:

> I need to convert a byte array representing an integer into a CL
> integer type, but I can not find an elegant way of doing it. I can
> always make a function like the one below, that converts the bytes
> in the given range.
>
> (defun bytes-to-int (bytearr start end)
> "Convert the bits of a byte array to an integer"
> (let ((intval 0))
> (loop for i downfrom end to start
> and j from 0 to (- end start)
> sum (* (aref bytearr i)
> (expt 2 (* j 8)))
> into intval
> finally return intval)))

Two comments:

1) Your loop can be made more compact by noting that sum has an
implicit "finally":

(defun bytes-to-int (bytearr start end)
"Convert the bits of a byte array to an integer"

(loop for i downfrom end to start
and j from 0 to (- end start)
sum (* (aref bytearr i)

(expt 2 (* j 8)))))

2) You can speed up significantly by using (setf (ldb ...)) instead
of summing:

(defun bytes-to-int2 (bytearr start end)

"Convert the bits of a byte array to an integer"

(loop with intval = 0
with k = (* (- end start) 8)

for i downfrom end to start

and j from 0 to k by 8
do (setf (ldb (byte 8 j) intval)
(aref bytearr i))
finally return intval))

--
(espen)

[Lars Brinkhoff]

Gisle Sælensminde <gi...@apal.ii.uib.no> writes:
> I need to convert a byte array representing an integer into a CL
> integer type, but I can not find an elegant way of doing it. I can
> always make a function like the one below, that converts the bytes
> in the given range.
>
> (defun bytes-to-int (bytearr start end)
> "Convert the bits of a byte array to an integer"
> (let ((intval 0))
> (loop for i downfrom end to start
> and j from 0 to (- end start)
> sum (* (aref bytearr i)
> (expt 2 (* j 8)))
> into intval
> finally return intval)))
>
> Are there any better way?

I'm a novice, but this seems to work:

(defun bytes-to-int (bytearr start end)
"Convert the bits of a byte array to an integer"

(reduce (lambda (x y) (+ (* 256 x) y)) subseq :start start :end end))

--
Lars Brinkhoff http://lars.nocrew.org/ Linux, GCC, PDP-10,
Brinkhoff Consulting http://www.brinkhoff.se/ HTTP programming

[Lars Brinkhoff]

Lars Brinkhoff <lars...@nocrew.org> writes:
> (defun bytes-to-int (bytearr start end)
> "Convert the bits of a byte array to an integer"
> (reduce (lambda (x y) (+ (* 256 x) y)) subseq :start start :end end))

Typo, new try:

(defun bytes-to-int (bytearr start end)
"Convert the bits of a byte array to an integer"

(reduce (lambda (x y) (+ (* 256 x) y)) bytearr :start start :end end))

[Espen Vestre]

Espen Vestre <espen@*do-not-spam-me*.vestre.net> writes:

> (defun bytes-to-int2 (bytearr start end)
> "Convert the bits of a byte array to an integer"
> (loop with intval = 0
> with k = (* (- end start) 8)
> for i downfrom end to start
> and j from 0 to k by 8
> do (setf (ldb (byte 8 j) intval)
> (aref bytearr i))
> finally return intval))

the limit check on j is unnecessary, as I noted in Raymonds code, so
this is cleaner:

(defun bytes-to-int2 (bytearr start end)
"Convert the bits of a byte array to an integer"
(loop with intval = 0

for i downfrom end to start

and j from 0 by 8

do (setf (ldb (byte 8 j) intval)
(aref bytearr i))
finally return intval))

I noted that your version (or the reduce-version) is faster
(at least in my implementation) if you're summing small arrays
(e.g. result is a fixnum). However, for a 1000-element array,
the ldb-version is about 4x faster and uses half the memory.

--
(espen)

[Espen Vestre]

Espen Vestre <espen@*do-not-spam-me*.vestre.net> writes:

> I noted that your version (or the reduce-version) is faster
> (at least in my implementation) if you're summing small arrays
> (e.g. result is a fixnum). However, for a 1000-element array,
> the ldb-version is about 4x faster and uses half the memory.

Or maybe not. The reduce-version is actually the fastest for
both small and large numbers.

So I think Lars B. found both the most beautiful (*) _and_ the
fastest solution!

(*) nice applications of reduce are _always_ beuatiful ;-)
--
(espen)

[Frode Vatvedt Fjeld]

Lars Brinkhoff <lars...@nocrew.org> writes:

> (defun bytes-to-int (bytearr start end)
> "Convert the bits of a byte array to an integer"

> (reduce (lambda (x y) (+ (* 256 x) y)) bytearr :start start :end end))

This looks good to me, but I'd prefer something like this:

(defun bytes-to-int (bytes start end)
"Convert the bits of a little-endian 8-bit byte array to an integer."
(reduce (lambda (x y) (+ (* 256 x) y)) bytes :start start :end end))

--
Frode Vatvedt Fjeld

[Barry Margolin]

In article <2hhegvj...@vserver.cs.uit.no>,

I don't see any significant differences. Just the name of a variable and
rewording of the documentation string.

--
Barry Margolin, bar...@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

[Raymond Toy]

>>>>> "Barry" == Barry Margolin <bar...@genuity.net> writes:

Barry> In article <2hhegvj...@vserver.cs.uit.no>,

Barry> Frode Vatvedt Fjeld <fro...@acm.org> wrote:
>> Lars Brinkhoff <lars...@nocrew.org> writes:
>>
>>> (defun bytes-to-int (bytearr start end)
>>> "Convert the bits of a byte array to an integer"
>>> (reduce (lambda (x y) (+ (* 256 x) y)) bytearr :start start :end end))
>>
>> This looks good to me, but I'd prefer something like this:
>>
>> (defun bytes-to-int (bytes start end)
>> "Convert the bits of a little-endian 8-bit byte array to an integer."
>> (reduce (lambda (x y) (+ (* 256 x) y)) bytes :start start :end end))

Barry> I don't see any significant differences. Just the name of a variable and
Barry> rewording of the documentation string.

I think the fact that he says "little-endian" is significant, having
been bitten lately by not knowing which endian some code was.

Ray

[Frode Vatvedt Fjeld]

Barry Margolin <bar...@genuity.net> writes:

> I don't see any significant differences. Just the name of a
> variable and rewording of the documentation string.

It was just a comment on coding style. I happen to believe that
documentation strings and variable names _are_ significant :)
Specifically I find the combination of hungarian notation and
abbreviated names in lisp code to be tasteless.

Come to think about it, function names are important too: I'd prefer
the function to either be named such that it's reasonably clear how
the byte-vector is interpreted, or that it accepts endianness and/or
byte-size as parameters, explicitly or implicitly via special
variables.

--
Frode Vatvedt Fjeld

[Erik Naggum]

* Frode Vatvedt Fjeld <fro...@acm.org>

| This looks good to me, but I'd prefer something like this:
|
| (defun bytes-to-int (bytes start end)
| "Convert the bits of a little-endian 8-bit byte array to an integer."
| (reduce (lambda (x y) (+ (* 256 x) y)) bytes :start start :end end))

I would much prefer

(reduce (lambda (x y) (logior (ash x 8) y)) bytes :start start :end end)

This is not a job for multiplication and addition.

--
Erik Naggum, Oslo, Norway

Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.

[Thomas F. Burdick]

Barry Margolin <bar...@genuity.net> writes:

> In article <2hhegvj...@vserver.cs.uit.no>,
> Frode Vatvedt Fjeld <fro...@acm.org> wrote:
> >Lars Brinkhoff <lars...@nocrew.org> writes:
> >
> >> (defun bytes-to-int (bytearr start end)
> >> "Convert the bits of a byte array to an integer"
> >> (reduce (lambda (x y) (+ (* 256 x) y)) bytearr :start start :end end))
> >
> >This looks good to me, but I'd prefer something like this:
> >
> > (defun bytes-to-int (bytes start end)
> > "Convert the bits of a little-endian 8-bit byte array to an integer."
> > (reduce (lambda (x y) (+ (* 256 x) y)) bytes :start start :end end))
>
> I don't see any significant differences. Just the name of a variable and
> rewording of the documentation string.

As someone who works almost exclusively on big-endian systems, I think
it's a pretty important change. In fact, I'd rewrite it like this:

(defun byteseq-integer (byteseq &key (byte-size 8) (start 0)
(end (length byteseq)) from-end)
"Convert the bits of an array of bytes to an integer.
Defaults to 8-bit bytes in little-endian order."
(let ((shift (expt 2 byte-size)))
(reduce (lambda (x y) (+ (* shift x) y))
byteseq :start start :end end :from-end from-end)))

or even

(defvar *default-endianness* :big-endian)

(defun byteseq-integer (byteseq &key (byte-size 8) (start 0)
(end (length byteseq))
(from-end (ecase *default-endianness*
(:big-endian t)
(:little-endian nil))))
"Convert the bits of an array of bytes to an integer.
Defaults to 8-bit bytes in the order specified by *default-endianness*"
(let ((shift (expt 2 byte-size)))
(reduce (lambda (x y) (+ (* shift x) y))
byteseq :start start :end end :from-end from-end)))

--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'

[Vassil Nikolov]

Erik Naggum <er...@naggum.no> wrote in message news:<32408407...@naggum.no>...

> * Frode Vatvedt Fjeld <fro...@acm.org>
> | This looks good to me, but I'd prefer something like this:
> |
> | (defun bytes-to-int (bytes start end)
> | "Convert the bits of a little-endian 8-bit byte array to an integer."
> | (reduce (lambda (x y) (+ (* 256 x) y)) bytes :start start :end end))
>
> I would much prefer
>
> (reduce (lambda (x y) (logior (ash x 8) y)) bytes :start start :end end)
>
> This is not a job for multiplication and addition.

I would say there is a tradeoff here between solving the
specific problem at hand (bytes into integer), for which
LOGIOR×ASH is the way to go, and being general, that is,
able to compute the polynomial for an arbitrary argument
by using the composition of + and * and `parameterizing'
the constant 256.

---Vassil.