Big Sky

2012/01/13

勝手に添削 - strncpyの罠

追記: 良く見たらstrncpyの罠でもなんでもなく、バッファがクリアされてないのが原因だった。って事であとでpullreqでも送っとくかな。

まぁソート関数自身の問題じゃないので控えめに。

strncpyは必ず \0 で埋めてくれるとは限らない。

404 Blog Not Found:algorithm - bucketsort.[ch] - 汎用かつlibcの*sortより高速な

dankogai/c-bucketsort - GitHub
http://blog.livedoor.jp/dankogai/archives/51764911.html

dankogai/c-bucketsort - GitHub

bucketsort - bucket sort that can be used for general purpose
https://github.com/dankogai/c-bucketsort

strncpy(3)のmanページにはこう書いてある。

The strcpy() function copies the string pointed to by src, including the terminating null byte ('\0'), to the buffer pointed to by dest. The strings may not overlap, and the destination string dest must be large enough to receive the copy.

The strncpy() function is similar, except that at most n bytes of src are copied. Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.

なので...


# ./bucketsort README

とかするとNULストップしてないバッファで画面が賑やかになり、時にはけたたましいビープ音で心躍る。

サンプルプログラムの仕様が最終行の改行コードなしでも動く様にすべきなのかどうなのかが分からないので


diff --git a/main.c b/main.c

index 67e4e00..48391b4 100644

--- a/main.c

+++ b/main.c

@@ -74,6 +74,7 @@ int main(int argc, char **argv)

        if (!lines[lcur])

            EXIT("malloc failed");

        strncpy(lines[lcur], buf, slen - 1);    // do not copy \n

+       lines[lcur][slen - 1] = 0;

     }

     size_t i;

     // for (i = 0; i < lcur; i++) printf("%s\n", lines[i]);

こういうワークアラウンドでもOKなのかもしれないが(そういう点でfork/pullreqはやめた)、おそらくツールとして扱うなら改行コードがあった場合には削除...という動きが望ましいのでstrpbrk(3)やstrchr(3)と使ったり、自作strchrぽい処理を入れていくと他のsortと比較しておられる状況も少し変わったりするのかもしれませんね。確認してないけど。
sort(1)とはやってる事が違いすぎるのでそもそもな気もしなくない。どこを比較したんだろう...。

ちなみに全然オフトピだけど、GNU textutilsに入ってるsort(1)にはコア数によって動的にスレッドを生成してソートする処理が入ってるのでそういうの興味ある人はコード読むといいと思います。

Posted at by mattn

2012/01/10

HaskellでGUI

WXやCocoaもあるみたいなんですが、Gtk慣れてるのもあるのでGtkで。
以前から、memcachedに対して簡単なコマンドをやり取りできるGUIクライアントを各言語でやってみようという一人プロジェクトをやっているのだけど、haskellって触った事が殆ど無かったのでやってみた。


module Main (Main.main) where



import Text.Regex

import Graphics.UI.Gtk as Gtk

import Network.Memcache

import Network.Memcache.Protocol

 

main :: IO ()

main = do

  server <- Network.Memcache.Protocol.connect "localhost" 11211



  Gtk.initGUI

  

  window <- Gtk.windowNew

  Gtk.onDestroy window Gtk.mainQuit

  Gtk.set window [ containerBorderWidth := 10, windowTitle := "memcachedclient"]



  vbox <- Gtk.vBoxNew False 0



  swin <- scrolledWindowNew Nothing Nothing

  Gtk.scrolledWindowSetPolicy swin Gtk.PolicyAutomatic Gtk.PolicyAutomatic

  Gtk.containerAdd vbox swin



  tview <- textViewNew 

  Gtk.set tview [ containerBorderWidth := 1 ]

  buf <- Gtk.textViewGetBuffer tview

  Gtk.textViewSetEditable tview False

  Gtk.containerAdd swin tview



  entry <- Gtk.entryNew

  Gtk.onEntryActivate entry $ do

    end <- textBufferGetEndIter buf

    t <- Gtk.get entry entryText

    let tt = splitRegex (mkRegex " ") t

    if (length tt == 2 && (head tt == "get" || head tt == "delete")) ||

       (length tt == 3 && head tt == "set")

    then do

      case head tt of

        "get" -> do

          let

            key = (tt !! 1)

          r <- Network.Memcache.get server key

          case r of

            Nothing -> textBufferInsert buf end ((show key) ++ " not found")

            Just v -> textBufferInsert buf end ((v::String) ++ "\n")

        "set" -> do

          let key = (tt !! 1)

          let val = (tt !! 2)

          r <- Network.Memcache.set server key val

          case r of

            True -> textBufferInsert buf end "OK\n"

            False -> textBufferInsert buf end "ERROR\n"

        "delete" -> do

          let

            key = (tt !! 1)

          r <- Network.Memcache.delete server key 0

          case r of

            True -> textBufferInsert buf end "OK\n"

            False -> textBufferInsert buf end "ERROR\n"

    else

      textBufferInsert buf end "Unknown command\n"

    Gtk.entrySetText entry ""



  Gtk.boxPackEnd vbox entry Gtk.PackNatural 0

  Gtk.set window [ containerChild := vbox ]

  Gtk.windowSetDefaultSize window 400 300

  Gtk.widgetShowAll window

  Gtk.widgetGrabFocus entry



  Gtk.mainGUI



-- vim: set et ts=2:

むむむー。haskell難しい。
なぜif-thenにelseが必須なのか、何故他の言語の変数というものに近い物が存在しないのか、Justってなんだよコノヤロ、gtk2hsのAPIがGTKっぽくないよ！とかいろいろ...

Posted at by mattn

2012/01/04

Vimで書初め

まず中平さんの vim-paint をインストール。

ynkdir/vim-paint - GitHub
https://github.com/ynkdir/vim-paint

このままだと日本語出せないのでパッチを当てる。


diff --git a/autoload/paint/bdf.vim b/autoload/paint/bdf.vim

index 8485995..e8323b8 100644

--- a/autoload/paint/bdf.vim

+++ b/autoload/paint/bdf.vim

@@ -139,6 +139,98 @@ let s:font.hexbits = [

       \ [1, 1, 1, 1],

       \ ]

 

+let s:utf8len = [

+\ 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

+\ 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

+\ 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

+\ 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

+\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

+\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

+\ 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,

+\ 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,6,6,0,0,

+\]

+

+function! s:dec2bin(v)

+  let v = a:v

+  if v == 0 | return 0 | endif

+  let ret = ""

+  while v > 0

+    let i = v % 2

+    let ret = i . ret

+    let v = v / 2

+  endwhile

+  return ret

+endfunction

+

+function! s:bin2dec(v)

+  let v = a:v

+  if len(v) == 0 | return 0 | endif

+  let i = 1

+  let ret = ""

+  for n in reverse(split(v, '\zs'))

+    if n == 1

+      let ret = ret + i

+    endif

+    let i = i * 2

+  endfor

+  return ret

+endfunction

+

+function! s:bitshift(a,b)

+  let a = s:dec2bin(a:a)

+  let a = repeat('0', 32-len(a)) . a

+  if a:b < 0

+    let a = (repeat('0', -a:b) . a[: a:b-1])[-32:]

+  elseif a:b > 0

+    let a = (a . repeat('0', a:b))[-32:]

+  endif

+  return s:bin2dec(a)

+endfunction

+

+function! s:bitand(a,b)

+  let a = s:dec2bin(a:a)

+  let b = s:dec2bin(a:b)

+  return s:bin2dec(tr((a + b), '21', '10'))

+endfunction

+

+function! s:byte2code(byte)

+  let p = a:byte

+  let n0 = char2nr(p[0])

+  if n0 < 0x80

+    return n0

+  endif

+  let l = s:utf8len[n0]

+  let n1 = char2nr(p[1])

+  if l > 1 && s:bitand(n1, 0xc0) == 0x80

+    if l == 2

+      return s:bitshift(s:bitand(n0, 0x1f), 6) + s:bitand(n1, 0x3f)

+    endif

+    let n2 = char2nr(p[2])

+    if s:bitand(n2, 0xc0) == 0x80

+      if l == 3

+        return s:bitshift(s:bitand(n0, 0x0f), 12) + s:bitshift(s:bitand(n1, 0x3f), 6) + s:bitand(n2, 0x3f)

+      endif

+      let n3 = char2nr(p[3])

+      if s:bitand(n3, 0xc0) == 0x80

+        if l == 4

+          return s:bitshift(s:bitand(n0, 0x07), 18) + s:bitshift(s:bitand(n1, 0x3f), 12) + s:bitshift(s:bitand(n2, 0x3f), 6) + s:bitand(n3, 0x3f)

+        endif

+        let n4 = char2nr(p[4])

+        if s:bitand(n4, 0xc0) == 0x80

+          if (l == 5)

+            return s:bitshift(s:bitand(n0, 0x03), 24) + s:bitshift(s:bitand(n1, 0x3f), 18) + s:bitshift(s:bitand(n2, 0x3f), 12) + s:bitshift(s:bitand(n3 & 0x3f), 6) + s:bitand(n4, 0x3f)

+          endif

+          let n5 = char2nr(p[5])

+          if s:bitand(n5, 0xc0) == 0x80 && l == 6

+            return s:bitshift(s:bitand(n0, 0x01), 30) + s:bitshift(s:bitand(n1, 0x3f), 24) + s:bitshift(s:bitand(n2, 0x3f), 18) + s:bitshift(s:bitand(n3, 0x3f), 12) + s:bitshift(s:bitand(n4, 0x3f), 6) + s:bitand(n5, 0x3f)

+          endif

+        endif

+      endif

+    endif

+  endif

+  return n0

+endfunction

+

 "

 " |hello, world

 " +------------

@@ -146,7 +238,8 @@ let s:font.hexbits = [

 " origin

 function s:font.draw_text(canvas, text, org, color)

   let [ox, oy] = a:org

-  for c in map(split(a:text, '\zs'), 'char2nr(v:val)')

+  for c in map(split(a:text, '\zs'), 's:byte2code(iconv(v:val, &encoding, "utf-8"))')

+    call garbagecollect()

     if !has_key(self.glyphs, c)

       let c = self.default_char

     endif

ビットシフト関数は結構適当。最新のvimならbitwize関数が入ってるはずなので、そっちを使った方が良い。さらにunifontからbdfフォントを貰ってくる。

GNU Unifont Glyphs

This page contains the latest release of the GNU Unifont, with glyphs for every printable code point...
http://unifoundry.com/unifont.html

そしてコード


scriptencoding utf-8

let canvas = paint#canvas#new(100, 50)

let font = paint#bdf#loadfile(globpath(&rtp, 'font/unifont/unifont-5.1.20080820.bdf'))

let text = "あけまして"

call canvas.draw_text(text, [10, 20], font, [0, 0, 0])

let text = "おめでとう"

call canvas.draw_text(text, [10, 40], font, [0, 0, 0])



call canvas.save('kakizome.bmp')

出来上がり

ちなみに画像ファイル出力までに5分くらいかかります。

Posted at by mattn