swizard (swizard) wrote,
swizard
swizard

Categories:

И еще раз о задачке про ip-диапазоны.

Собственно, описание задачи и варианты её решения можно почитать здесь у 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))


Собственно, все это я выношу в следующий пост: суперкомпиляция условий, сегментация и препроцессинг кода и так далее. В идеале мы должны не только решить задачу, а еще и получить самый производительный код.
Tags: article, code, code generation, common lisp, dsl, ip, ip range, lisp
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 16 comments