osa1 github gitlab twitter cv rss

Binary dosyaları okumak için basit bir DSL

January 31, 2012 - Tagged as: lisp, tr.

Hiçbir motivasyonum olmaksızın Common Lisp ile uğraştığım şu günlerde(şu ana kadar kullandığım diller arasında bariz bir şekilde kullanması en zevkli olanı, bu konu hakkında bir yazı yazdım birkaç düzenlemeye hazır olur), staj projem için yaptığım çalışmalar sırasında öğrendiğim bazı şeyleri Common Lisp ile uyguluyorum. Bunlardan birisi de JVM yapısı. Common Lisp ile basit bir JVM işine giriştim. Şimdilik epey iyi gidiyorum, amacım birkaç JVM komutu(instructuion, opcode, artık ne derseniz) çalıştırabilen bir altyapı. Tüm native kütüphaneleriyle beraber Java programlarını çalıştırabilecek bir JVM yapmıyorum tabii ki.

İlk adım olarak bir Java class dosyasını okuyup, istediğim kısımlarına kolayla ulaşabileceğim bir şekilde yüklemekti. class dosyalarının yapısını şuradan inceleyebilirsiniz.

Bunu yaparken bazı kod parçalarının çok tekrar ettiğini farkettim, örneğin n byte’lık bir kısmı, bir sonraki kısımdan(bu 1 byte’lık bir veri de olabilir, tamamen farklı bir yapı da olabilir, örneğin bir interface referansı) kaç tane olduğunu bilmek için okumak. Şu şekilde birşeyler yani:

(let* ((constant-count (read-bytes 2 stream))
       (constants (make-array constant-count)))
  (loop for i from 0 to (1- constant-count) do
    (setf (elt constants i) (read-constant stream))))

Burda yaptığım, 2 byte okuyarak constant pool’da kaç tane sabit olduğunu öğrenmek. Buna göre kaç byte daha okuyacağıma karar vereceğim çünkü.

Tabii bir de class dosyasının istediğim kısımlarına kolayca ulaşabilmek için dosyayı farklı parçaları için structlara bölmem gerekti. Bir yerden sonra her bir struct için farklı bir okuma fonksiyonu oluşturmuştum. Ve bu okuma fonksiyonlarında da bir sürü ortak kısım vardı. Bir DSL’e çevirmeye karar verdim.

Aslında DSL ile API’ın arasındaki fark tam belli değil. Benim DSL’den kastettiğim arayüzü sunarken kendisine özel bir syntax ile sunmak. Bu yaptığım biraz da yeni birşey öğrenince hemen uygulamaya çalışma merakı aslında.

Önce nasıl kullanıldığını göstereyim, sonra macrolardan bahsedeceğim. Tüm kodu görmek isteyenler için, şu class dosyasını ayrıştıran kod, şu da DSL macroları. Tüm class dosyasını tanımladığım yapı şöyle birşey:

(defbinstruct class-file
  (magic 4)
  (minor-version 2)
  (major-version 2)
  (constant-pool (:struct constant-pool))
  (access-flags 2)
  (this-class 2)
  (super-class 2)
  (:temp (interfaces-count 2))
  (interfaces (:list 2 interfaces-count))
  (:temp (fields-count 2))
  (fields (:list (:struct field) fields-count))
  (:temp (jmethods-count 2))
  (methods (:list (:struct jmethod) jmethods-count))
  (:temp (attributes-count 2))
  (attributes (:list (:struct attribute) attributes-count)))

Tanımın yukarıda linkini verdiğim class dosyası yapısına ne kadar benzediğine dikkat edin. Şöyle çalışıyor, her defbinstruct için bir struct oluşturuluyor, içindeki her bir liste için gerekiyorsa(:temp olup olmadığına göre) struct’a slot ekleniyor. :temp değişkenler farklı amaçlar için gerekebilir. Örneğin dosyadaki boşluklar(padding diye geçer genelde) için, veya dosyada bir yapıdan kaç tane olduğunu okumanız gerektiğinde, ama bu değeri okuduyup oluşturduğunuz yapıya dahil etmek istemiyorsanız. Her bir defbinstruct için bir de okuma fonksiyonu oluşturuluyor, yapının adına “read” eklenerek(burdaki örnek için read-class-file yani).

Değişken isminden sonra gelen kısım eğer tamsayı ise, o tamsayı kadar byte okunup bu slota atanıyor, eğer (:list a b) veya (:vector a b) şeklinde birşeyse, adan b kere okunup, liste veya vector olarak atanıyor. Eğer tamsayı kısmına (:struct a) gibi birşey gelmişse, anın bir defbinstruct ile oluşturulmuş yapı olması gerekiyor(yani read-a diye bir fonksiyon olmalı). Bu tanımlamaların recursive bir formda olabileceğine dikkat. Şöyle birşey olabilir mesela: (field-1 (:list (:list (:struct sub-field) sub-field-count) field-count)).

Dönüş değeri de tanımladığınız yapıdan oluşturulmuş bir struct. Örnekteki kodda class-file-interfaces ile interfaces alanına ulaşabilirsiniz mesela.

Okunan değerlere göre daha kompleks işler yapmanız gerektiğinde :custom keywordu ile read fonksiyonunu kendiniz tanımlayabilirsiniz. :custom keywordunden sonraki kısım da yapıda olacak slotların listesi. Örneğin constant-poolu okumak biraz daha zor(mesela double ve long sabitler constant-pool’da 2 slot kaplıyor), şöyle:

(defbinstruct constant-pool
  :custom
  (constants)
  (let* ((constant-pool-count (1- (read-bytes 2 stream)))
         (constants (make-array constant-pool-count)))
    (loop for i from 0 to (1- constant-pool-count) do
      (let ((tag (read-bytes 1 stream)))
        (if (or (= tag 5) (= tag 6))
            (let ((constant (if (= tag 5)
                                (read-jlong stream)
                                (read-jdouble stream))))
              (setf (elt constants i) constant
                    (elt constants (1+ i)) constant)
              (incf i))
            (setf (elt constants i)
                  (funcall
                   (case tag
                     (1 #'read-utf-8)
                     (8 #'read-string-ref)
                     (3 #'read-jinteger)
                     (4 #'read-jfloat)
                     (7 #'read-class-ref)
                     (9 #'read-field-ref)
                     (10 #'read-method-ref)
                     (11 #'read-interface-method-ref)
                     (12 #'read-descriptor))
                   stream)))))
    (make-constant-pool :constants constants)))

Bu tanımladığımız read fonksiyonuna stream diye bir parametre aktarıldığını varsayıyoruz(macro tarafından oluşturulmuş kodda aktarılıyor). Burda aslında stream yerine lexical scope ile *standard-input*a bu stream atanabilir. Yine de çaktırmadan *standard-input* ile oynamak bana çok iyi bir yolmuş gibi gelmedi.

Bir başka örnek olarak da yine constant-pooldaki string sabitlerini nasıl okuduğumu göstereyim:

(defbinstruct utf-8
  (:temp (length 2))
  (value (:vector 1 length)))

İlk 2 byte, string’in uzunluğunu veriyor. Daha sonra bu uzunluk kadar 1 byte okuyup bir vector olarak kaydediyorum.

Şimdi macrolara bakalım. İlk önce defbinstruct kodundaki keywordleri(:vector, :list, :struct) recursive olarak silip yerine gerekli Lisp kodunu ekleyen remove-keywords macrosu:

(defmacro remove-keywords (form)
  (cond ((null form) '())
        ((integerp form)
         `(read-bytes ,form stream))
        ((and (consp form) (keywordp (first form)))
         (case (first form)
           ((:list)
            `(loop for s from 0 to (1- ,(third form))
                   collect (remove-keywords ,(second form))))
           ((:vector)
            `(coerce (loop for s from 0 to (1- ,(third form))
                           collect (remove-keywords ,(second form)))
                     'vector))
           ((:struct)
            `(,(intern (concatenate 'string "READ-" (string (second form)))) stream))))
        (t form)))

Yaptığı şey çok basit, her :struct keywordu gördüğü yere (read-x) fonksiyonunu ekliyor, :list veya :vector gördüğü yerde de gereken loop kodunu. İkinci olarak olarak defbinstruct:

(defmacro defbinstruct (name &body attributes)
  (labels ((make-reader-name (name-symbol)
             (intern (concatenate 'string "READ-" (string name-symbol)))))
    (if (and (keywordp (first attributes))
             (eql (first attributes) :custom))
        (let ((attributes (second attributes))
              (body (cddr attributes)))
          `(progn
             (defstruct ,name
               ,@attributes)
             (defun ,(make-reader-name name) (stream)
               ,@body)))
        (let ((attr-struct-names (remove-if-not #'identity
                                                (mapcar (lambda (attr)
                                                          (unless (keywordp (first attr))
                                                            (first attr)))
                                                        attributes))))
          `(progn
             (defstruct ,name
               ,@attr-struct-names)
             (defun ,(make-reader-name name) (stream)
               (let* (,@(mapcar (lambda (attr)
                                  (destructuring-bind (attr-name . bytes)
                                      (if (keywordp (first attr))
                                          (cons (caadr attr) (cadadr attr))
                                          (cons (first attr) (second attr)))
                                    `(,attr-name ,(if (integerp bytes)
                                                      `(read-bytes ,bytes stream)
                                                      `(remove-keywords ,bytes)))))
                                attributes))
                 
                 (,(intern (concatenate 'string "MAKE-" (string name)))
                  ,@(mapcan (lambda (name) (list (intern (string name) "KEYWORD") name))
                            attr-struct-names)))))))))

Burda da defbinstruct altındaki listeleri gezip, oluşturulacak olan structa gerekli slotları ekliyorum ve read fonksiyonunu oluşturuyorum. Her bir defbinstruct için bir struct bir de fonksiyon tanımlıyorum yani.

Kütüphane toplam 52 satır. İkinci bir örnek olarak da ID3 etiketlerini okuyacaktım ama çok kompleks geldi. Dikkat edilmesi gereken çok fazla istisna var. Aklıma daha basit bir örnek gelirse ekleyeceğim(ara ara kütüphaneyi de güncelliyorum, gistlerden takip edebilirsiniz).