I'm bashing together a small bunch of functions for manipulating IP
addresses, since I haven't been able to find anything similar online.
This is bottom-up stuff aimed at future project that will need fast
storage and search of collections of IP addresses and CIDR blocks (I'm
thinking tries).
If this code is useful to anyone, great ... if you spot anything
obviously bogus in it and feel like telling me, also great. :)
;
; Byte and byte collection operations
(defun nth-byte (n int &optional (byte-len 8))
"Extract the Nth lowest byte from INT."
(declare (integer n byte-len int))
(ldb (byte byte-len (* n byte-len)) int))
(defun integer->bytevec (int byte-count &optional (byte-len 8))
"Make a vector of BYTE-COUNT bytes from the bottom of integer INT.
Defaults to 8-bit bytes; set BYTE-LEN for different size."
(declare (unsigned-byte int byte-count byte-len))
(let ((new-vector (make-array byte-count
:element-type `(unsigned-byte ,byte-len)))
(top-byte (1- byte-count)))
(loop for byte-pos downfrom top-byte to 0
do (setf (elt new-vector byte-pos)
(nth-byte (- top-byte byte-pos) int byte-len)))
new-vector))
(defun integer->bytelist (int byte-count &optional (byte-len 8))
"Make a list of BYTE-COUNT bytes from the bottom of integer INT.
Defaults to 8-bit bytes; set BYTE-LEN for different size."
(declare (unsigned-byte int byte-count byte-len))
(loop for byte-pos downfrom (1- byte-count) to 0
collect (nth-byte byte-pos int byte-len)))
(defun bytelist->integer (list &optional (byte-len 8))
"Compact a list of bytes into an integer."
(let ((total 0))
(mapc (lambda (x) (setf total (+ (ash total byte-len) x))) list)
total))
(defun bytevec->integer (vec &optional (byte-len 8))
"Compact a vector of bytes into an integer."
(bytelist->integer (coerce vec 'list) byte-len))
;
; 32-bit IP address operations
(defun ipaddr-int->vec (ipaddr)
(integer->bytevec ipaddr 4))
(defun ipaddr-int->list (ipaddr)
(integer->bytelist ipaddr 4))
(defun dotted-quad (ipaddr)
"Format a 32-bit IP address integer into a dotted quad string."
(format nil "~{~S~^.~}" (ipaddr-int->list ipaddr)))
;
; CIDR block objects
(defclass cidr ()
((address :type (unsigned-byte 32)
:accessor address
:initarg :address
:initform (error "Must supply :address")
:documentation "Like, a 32-bit IP address.")
(netmask :type (unsigned-byte 32)
:accessor netmask
:initarg :netmask
:initform (error "Must supply :netmask")
:documentation "A network mask. 1 bits to the left please.")))
(defun count-one-bits (n)
"Count the number of 1 bits in a 32-bit integer. (HAKMEM 169.)"
(declare (type (unsigned-byte 32) n))
; yes, this would look prettier in *read-base* 8.
; probably needs to be bummed with THE some, too.
(let ((tmp (- n (logand (ash n -1) 3681400539)
(logand (ash n -2) 1227133513))))
(mod (logand (+ tmp (ash tmp -3)) 3340530119) 63)))
(defmethod cidr-quad ((cidr cidr))
"Format a cidr in w.x.y.z/a string form."
(format nil "~A/~A"
(dotted-quad (address cidr))
(count-one-bits (netmask cidr))))
--
Karl A. Krueger <········@example.edu>
Woods Hole Oceanographic Institution
Email address is spamtrapped. s/example/whoi/
"Outlook not so good." -- Magic 8-Ball Software Reviews
On Tue, Aug 03, 2004 at 08:33:23PM +0000, Karl A. Krueger wrote:
> (defun bytelist->integer (list &optional (byte-len 8))
> "Compact a list of bytes into an integer."
> (let ((total 0))
> (mapc (lambda (x) (setf total (+ (ash total byte-len) x))) list)
> total))
Consider using (SETF LDB) here?
> (defun count-one-bits (n)
> "Count the number of 1 bits in a 32-bit integer. (HAKMEM 169.)"
> (declare (type (unsigned-byte 32) n))
> ; yes, this would look prettier in *read-base* 8.
> ; probably needs to be bummed with THE some, too.
> (let ((tmp (- n (logand (ash n -1) 3681400539)
> (logand (ash n -2) 1227133513))))
> (mod (logand (+ tmp (ash tmp -3)) 3340530119) 63)))
See LOGCOUNT.
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
Matthew Danish <·······@andrew.cmu.edu> wrote:
> On Tue, Aug 03, 2004 at 08:33:23PM +0000, Karl A. Krueger wrote:
>> (defun bytelist->integer (list &optional (byte-len 8))
>> "Compact a list of bytes into an integer."
>> (let ((total 0))
>> (mapc (lambda (x) (setf total (+ (ash total byte-len) x))) list)
>> total))
>
> Consider using (SETF LDB) here?
Not sure how ... I don't know how many bytes are in the list without
wastefully taking (LENGTH LIST), so I don't know what the bit position
of the first byte is. So I have to repeatedly shift anyway.
I tried the following, with DPB instead of addition, but it was slower:
(defun bytelist->integer/dpb (list &optional (byte-len 8))
"Compact a list of bytes into an integer."
(let ((total 0)
(bytespec (byte byte-len 0)))
(mapc (lambda (x)
(setf total (dpb x bytespec (ash total byte-len)))) list)
total))
>> (defun count-one-bits (n)
>> "Count the number of 1 bits in a 32-bit integer. (HAKMEM 169.)"
>> (declare (type (unsigned-byte 32) n))
>> ; yes, this would look prettier in *read-base* 8.
>> ; probably needs to be bummed with THE some, too.
>> (let ((tmp (- n (logand (ash n -1) 3681400539)
>> (logand (ash n -2) 1227133513))))
>> (mod (logand (+ tmp (ash tmp -3)) 3340530119) 63)))
>
> See LOGCOUNT.
Jeez. This language thinks of everything. :)
--
Karl A. Krueger <········@example.edu>
Woods Hole Oceanographic Institution
Email address is spamtrapped. s/example/whoi/
"Outlook not so good." -- Magic 8-Ball Software Reviews
In article <············@baldur.whoi.edu>,
"Karl A. Krueger" <········@example.edu> wrote:
> Matthew Danish <·······@andrew.cmu.edu> wrote:
> > On Tue, Aug 03, 2004 at 08:33:23PM +0000, Karl A. Krueger wrote:
> >> (defun bytelist->integer (list &optional (byte-len 8))
> >> "Compact a list of bytes into an integer."
> >> (let ((total 0))
> >> (mapc (lambda (x) (setf total (+ (ash total byte-len) x))) list)
> >> total))
> >
> > Consider using (SETF LDB) here?
>
> Not sure how ... I don't know how many bytes are in the list without
> wastefully taking (LENGTH LIST), so I don't know what the bit position
> of the first byte is. So I have to repeatedly shift anyway.
If you process the list starting with the low-order bytes, you don't
need to keep shifting.
(defun bytelist->integer (list &optional (byte-len 8))
(do ((total 0)
(cur-pos 0 (+ cur-pos byte-len))
(cur-list (reverse list) (cdr cur-list)))
((null cur-list) total)
(setf (ldb (byte byte-len cur-pos) total) (car cur-list))))
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
Barry Margolin <······@alum.mit.edu> wrote:
> (defun bytelist->integer (list &optional (byte-len 8))
> (do ((total 0)
> (cur-pos 0 (+ cur-pos byte-len))
> (cur-list (reverse list) (cdr cur-list)))
> ((null cur-list) total)
> (setf (ldb (byte byte-len cur-pos) total) (car cur-list))))
I've tested both -- in SBCL with (optimize speed) on my system (a
Pentium 4 Xeon), the addition version is faster than the LDB one in
every test case I've tried. At one million repetitions and a list
length of 4, here's my time results for the two:
byte length bytelist->integer/+ bytelist->integer/ldb
-------------------------------------------------------------
8 1.731 sec 2.747 sec
16 2.504 sec 4.74 sec
32 3.037 sec 8.192 sec
64 3.366 sec 8.923 sec
Here's the function used to test them:
(defun time-bi (n f l)
"n = repeats, f = function, l = byte length"
(let ((result 0))
(time (loop for i below n
for x = (mod i (ash 2 (1- l)))
do (setf result (funcall f (list x x x x) l))
finally (return result)))))
Increasing the list length to 8 preserves the disparity:
byte length bytelist->integer/+ bytelist->integer/ldb
-------------------------------------------------------------
8 4.329 sec 7.709 sec
64 8.175 sec 19.249 sec
--
Karl A. Krueger <········@example.edu>
Woods Hole Oceanographic Institution
Email address is spamtrapped. s/example/whoi/
"Outlook not so good." -- Magic 8-Ball Software Reviews
"Karl A. Krueger" <········@example.edu> writes:
> Barry Margolin <······@alum.mit.edu> wrote:
>> (defun bytelist->integer (list &optional (byte-len 8))
>> (do ((total 0)
>> (cur-pos 0 (+ cur-pos byte-len))
>> (cur-list (reverse list) (cdr cur-list)))
>> ((null cur-list) total)
>> (setf (ldb (byte byte-len cur-pos) total) (car cur-list))))
>
> I've tested both -- in SBCL with (optimize speed) on my system (a
> Pentium 4 Xeon), the addition version is faster than the LDB one in
> every test case I've tried. At one million repetitions and a list
> length of 4, here's my time results for the two:
>
> byte length bytelist->integer/+ bytelist->integer/ldb
> -------------------------------------------------------------
> 8 1.731 sec 2.747 sec
> 16 2.504 sec 4.74 sec
> 32 3.037 sec 8.192 sec
> 64 3.366 sec 8.923 sec
If you use fixed-width bytes and you have a limit on the number of
bytes, you can precompute some tables:
(defconstant *byte-table*
(if (boundp '*byte-table*)
(symbol-value '*byte-table*)
(let ((table (make-array '(8 128))))
(dotimes (i 8 table)
(dotimes (j 128)
(setf (aref table i j) (ash j (* i 8))))))))
(defun bytelist->integer (list)
(do ((l list (cdr l))
(i 0 (+ i 1))
(result 0 (+ result (aref *byte-table* i (car l)))))
((null l) result)))