swizard (swizard) wrote,
swizard
swizard

Битовые строки: окончание

Идея со схемой временно откладывается -- сложность реализации что-то превысило допустимый порог "code for fun" :) Тем не менее, приведу стандартное решение "в лоб", раз уж обещал показать схему: http://www.beercan.ru/misc/golomb/parser.scm.htm

Здесь я решил все-таки немного подвыебнутся, и сделал подсчет лидирующих нулей не через lookup-table, как было бы разумно, а через макрос, разворачивающийся вот в это, с логарифмической скоростью:

#;1> #;2> ,x (unroll-count-zeroes 24 #xFFFFFF)
(##core#set!
  count-zeroes
  (lambda (value)
    (- 24
       (if (zero? (bitwise-and value 16773120))
         (if (zero? (bitwise-and value 16777152))
           (if (zero? (bitwise-and value 16777208))
             (if (zero? (bitwise-and value 16777214))
               (if (zero? (bitwise-and value 16777215)) 0 1)
               (if (zero? (bitwise-and value 16777212)) 2 3))
             (if (zero? (bitwise-and value 16777184))
               (if (zero? (bitwise-and value 16777200)) 4 5)
               6))
           (if (zero? (bitwise-and value 16776704))
             (if (zero? (bitwise-and value 16776960))
               (if (zero? (bitwise-and value 16777088)) 7 8)
               9)
             (if (zero? (bitwise-and value 16775168))
               (if (zero? (bitwise-and value 16776192)) 10 11)
               12)))
         (if (zero? (bitwise-and value 16515072))
           (if (zero? (bitwise-and value 16744448))
             (if (zero? (bitwise-and value 16760832))
               (if (zero? (bitwise-and value 16769024)) 13 14)
               15)
             (if (zero? (bitwise-and value 16646144))
               (if (zero? (bitwise-and value 16711680)) 16 17)
               18))
           (if (zero? (bitwise-and value 14680064))
             (if (zero? (bitwise-and value 15728640))
               (if (zero? (bitwise-and value 16252928)) 19 20)
               21)
             (if (zero? (bitwise-and value 8388608))
               (if (zero? (bitwise-and value 12582912)) 22 23)
               24)))))))


В результате получил около 3900 инструкций на число, слив-таки хаскелю в тривиальном решении ;)

Что хочется добавить в итоге: во-первых, свою идею я как-нибудь попробую, из академического интереса =) Ну и во-вторых, на практике в своей схеме (я использую chicken) я бы в здравом уме не стал реализовывать всю эту битовую ересь в лоб, благо мне сишный код можно писать прямо как ассемблерные вставки в си:
(define my-strlen
  (foreign-lambda* int ((c-string str))
    "int n = 0; while(*(str++)) ++n; C_return(n);") )

Но правилами это было запрещено :)
Tags: chicken, code, scheme
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.
  • 4 comments