Собственно, описание задачи и варианты её решения можно почитать
здесь у
nponeccop. Один из вариантов там
предложен на CL лавсанчиком. Собственно, он меня немножечко возмутил, поэтому пришлось писать этот пост :)
Суть токова:
это вполне себе рабочий код, но так на common lisp писать
не надо :) Потому что так надо писать на си. На сях этот же код будет вдвое короче (хотя бы за счет отсутствия скобок и более лаконичного синтаксиса) и вдвое быстрее.
Писать руками такую простыню низкоуровнего кода на CL -- это явный провал. На лиспе надо писать программу, которая будет генерировать низкоуровневый код, это ежу понятно.
Условия нам благоприятсвуют: диапазоны грузятся один раз, а дальше только лукап. Поэтому мы попробуем решить эту задачу классическим лисповым способом: «расставить скобки вокруг спецификации и заставить её запуститься». Вот прямо так, буквально. Итак, имеем файл
ranges.list такого вида:
104.72.221.173,220.57.219.35
16.65.26.150,133.42.154.151
80.241.37.220,93.109.90.13
35.165.212.97,105.166.11.16
122.143.149.115,246.17.13.31
20.44.170.80,144.105.12.169
122.132.114.84,184.165.60.95
102.111.151.45,120.152.236.26
53.252.70.24,171.51.24.110
101.103.12.180,224.55.178.136 |
Отлично, давайте расставим вокруг скобки, чтобы получить
ranges.list.lisp:
(in-package :ip-ranges)
(gen-test-proc
"104.72.221.173,220.57.219.35"
"16.65.26.150,133.42.154.151"
"80.241.37.220,93.109.90.13"
"35.165.212.97,105.166.11.16"
"122.143.149.115,246.17.13.31"
"20.44.170.80,144.105.12.169"
"122.132.114.84,184.165.60.95"
"102.111.151.45,120.152.236.26"
"53.252.70.24,171.51.24.110"
"101.103.12.180,224.55.178.136"
) |
Только, конечно же, не руками, а вот так:
(defun preprocess-ranges-file (filename)
(let ((lisp-file (format nil "~a.lisp" filename)))
(with-open-file (f-in filename)
(with-open-file (f-out lisp-file
:direction :output
:if-exists :supersede
:if-does-not-exist :create
:external-format :ascii)
(format f-out "(in-package :ip-ranges)~%(gen-test-proc~%")
(iter (for range in-stream f-in using #'read-line)
(format f-out " \"~a\"~%" range))
(format f-out ")~%~%")))
lisp-file)) |
Переходим ко второму этапу: надо заставить полученную скобочную спецификацию компилироваться. Давайте сначала быстренько распарсим строчку ip-адреса и диапазона, плюнем на перфоманс:
(defpackage #:ip-ranges
(:use :cl :iterate :metatilities)
(:shadowing-import-from :metatilities #:minimize #:finish)
(:export #:check))
(in-package :ip-ranges)
(defun extract-values (string)
(unless (zerop (length string))
(multiple-value-bind (value rest-index)
(parse-integer string :junk-allowed t)
(if value
(cons value (extract-values (subseq string rest-index)))
(extract-values (subseq string 1)))))) |
Работать это должно так:
IP-RANGES> (extract-values "104.72.221.173,220.57.219.35")
(104 72 221 173 220 57 219 35) |
Теперь надо немного пораскинуть мозгами. Вот у нас есть диапазон, заданный ip-адресами, каждый из которых представлен четырьмя октетами -- в нашем случае
'(104 72 221 173) и
'(220 57 219 35). Допустим, нам выдали адрес в таком же формате: ip =
(list ip-0 ip-1 ip-2 ip-3); какой код должен быть в программе, которым можно проверить принадлежность этого адреса заданному диапазону? Собственно, тут даже не надо ничего делать руками (например, склеивать октеты в 32-х битный адрес и т.п.), просто тупо сгенерируем сравнение в лесенкой столбик :)
(defun ip-range (range-string)
(let ((values (extract-values range-string))
(vars '(ip-0 ip-1 ip-2 ip-3)))
(assert (= (length values) 8))
(labels ((stairs (cmp values vars)
(if (null values)
t
`(or (,cmp ,(car vars) ,(car values))
(and (= ,(car vars) ,(car values))
,(stairs cmp (cdr values) (cdr vars)))))))
`(and ,(stairs '> (subseq values 0 4) vars)
,(stairs '< (subseq values 4 8) vars))))) |
IP-RANGES> (ip-range "104.72.221.173,220.57.219.35")
(AND
(OR (> IP-0 104)
(AND (= IP-0 104)
(OR (> IP-1 72)
(AND (= IP-1 72)
(OR (> IP-2 221)
(AND (= IP-2 221)
(OR (> IP-3 173) (AND (= IP-3 173) T))))))))
(OR (< IP-0 220)
(AND (= IP-0 220)
(OR (< IP-1 57)
(AND (= IP-1 57)
(OR (< IP-2 219)
(AND (= IP-2 219)
(OR (< IP-3 35) (AND (= IP-3 35) T))))))))) |
Ну а теперь у нас есть все для того, чтобы "скомпилировать спецификацию":
(defmacro gen-test-proc (&rest ranges)
`(defun ip-check (ip-0 ip-1 ip-2 ip-3)
(or ,@(mapcar #'ip-range ranges))))
(defun check (ip-string)
(apply #'ip-check (extract-values ip-string))) |
Вуаля:
IP-RANGES> (load (compile-file (preprocess-ranges-file #p"ranges.list")))
; compiling file "/home/swizard/devel/lisp/ip-ranges/ranges.list.lisp" (written 03 NOV 2011 11:16:02 PM):
; compiling (IN-PACKAGE :IP-RANGES)
; compiling (GEN-TEST-PROC "104.72.221.173,220.57.219.35" ...)
; /home/swizard/devel/lisp/ip-ranges/ranges.list.fasl written
; compilation finished in 0:00:00.045
T
IP-RANGES> (check "192.168.0.1")
T
IP-RANGES> (check "10.0.0.0")
NIL |
Итак, еще раз, что мы сейчас сделали:
- Расставили скобки вокруг списка ip-диапазонов.
- Сгенерировали по описанию функцию ip-check, решающую задачу.
- ...
- Profit!
Красотища? Да, но пока что не особо.
- Несмотря на константные проверки и восьмибитную сегментацию адреса, у нас получилась последовательная проверка.
- Несмотря на автоматическую генерацию условия по диапазону, это условие генерируется какое-то кривоватое и сильно избыточное.
- Несмотря на то, что какие-то диапазоны проверять нет смысла, так как они "поглощаются" более широкими, все равно проверяются все.
- По условиям задачи диапазонов могут быть сотни: поэтому код надо сегментировать по функциям, чтобы не нагнуть компилятор при стратегии (optimize (speed 3))
Собственно, все это я выношу в следующий пост: суперкомпиляция условий, сегментация и препроцессинг кода и так далее. В идеале мы должны не только решить задачу, а еще и получить самый производительный код.