はじめてのにき

_ SIZECON

狂ったルールのおかげでたのしい。 ここまで来るとはなぁ。

http://www.spoj.pl/SHORTEN/ranks/SIZECON/

あと 2B は今の方針だと全然ダメ。 どうすればいいかなー

解いた問題数 60 のまんまでトップになりたいとか思いはじめてきた。

(11:39)

_ SHORTEN

http://www.typemiss.net/2011/01/spoj-shorten.html

で書かれてる通りテストケースかなり適当なんだよなぁ。

http://twitter.com/kinaba/status/23392088473214977

まず kinaba さんが書いておられる通り出力フォーマットが適当ってのがあって、 それはまぁたぶん scanf で読んでるっぽい感じの問題が多くて、 そっちはまぁ

https://www.spoj.pl/SHORTEN/embed/rules/

あたりにも書いてあるからまぁいいとして。

問題はテストケース見せてないからなんとかなってるだけーって程度に テストケースが十分に無いやつがあるってことだよな。 例えば SUDCHECK なんてテストケースの数の bit 数があれば 解答埋め込めちゃうから、 こんなもんすごい数のテストケースが無いと ルール無用なゴルフとしては全く成立してないのだよな。

https://www.spoj.pl/SHORTEN/problems/SUDCHECK/

そんなこんなでまぁ色々やる気は起きない要因はあるんだけど、 なんか BF 使う問題とかあったりとかはちょっと面白いかとおもう。

てかこのへんの制約は ICPC のためにほげほげな SPOJ だから、って理由がほとんどだよなぁ。 あくまでゴルフ場ではないっつーか。

あと与えられてる sample inputs が異様に簡単なものばかり、ってのも ICPC 的な感じなんだろうなぁ。 問題の spec から難しいテストケースを考える、 ってのは重要な能力ではあるものの、 なんかどうもプログラムコンテストとしては余計なものに感じちゃったりもする。

まあなんだかんだ言いつつ3位。

一番面白かった問題(というか解いてないが)は INTER で ruby だと gets するだけで TLE 。 https://www.spoj.pl/SHORTEN/problems/INTER/

(08:20)

_ latency

http://d.hatena.ne.jp/kawango/20110107

ニコニコではこのへんが問題になるのなーという感じもあるけど、 本当にそうなんか? グーグルだとなんか色々調べたけど、 ある程度高速な回線だと結局クライアントのオーバヘッドがデカいぞ、 って話で HTML を頑張って色々やったらユーザの幸せがだいぶ増えたとかいう話があって (たしかこの本…だっけ http://www.amazon.com/High-Performance-Web-Sites-Essential/dp/0596529309)、 ニコニコも体感だと動画とか以前に、最初にページ出るまでが結構長いんだけどな。

(10:09)

_ ruby 1.9 と gets

いくらなんでも gets だけでタイムアウトしてるのはおかしいが、 測ってみると ruby1.9 の gets はマジで遅い。 これは M17N の影響だったりするんだろうか。

> time sh -c "ruby -e 'puts %q(c)*10000000' | ruby -e 'gets'"
sh -c "ruby -e 'puts %q(c)*10000000' | ruby -e 'gets'"  0.19s user 0.17s system 91% cpu 0.396 total
> time sh -c "ruby -e 'puts %q(c)*10000000' | ruby1.9 -e 'gets'"
sh -c "ruby -e 'puts %q(c)*10000000' | ruby1.9 -e 'gets'"  1.32s user 0.19s system 94% cpu 1.591 total
> time sh -c "ruby -e 'puts %q(c)*10000000' | perl -e '<>'"
sh -c "ruby -e 'puts %q(c)*10000000' | perl -e '<>'"  0.21s user 0.12s system 93% cpu 0.360 total

(10:46)

_ golf場 TODO

なんか IRC で話してていくつか

• 8 characters hello world 。8種類しか文字使えない hello を書けというもの。 goruby が h だけでいいのはいいかげんあれだし HELLO, WORLD! とかにしてやればいいか
• edit distance がコードサイズになってないといけない cyclic な quine 。これ書けるかまだわからんからとりあえず解いてから…
• rejudge button 。 random base な解答はちょっとアレなので、 deadline つきの新しい問題は rejudge button をつけて、それを押すと解答の check をもう一度走らせる、ってもの。 time limit が厳しい解答がかわいそうになるかもなので、 rejudge の時は time limit を増やすと良い

(05:25)

_ random seed

rejudge よりは rand seed 全部殺すのが良いんじゃないかと言われた。 そんなの無理だと思ってたんだけど、結構できそうな気もしてきた

• rm /dev/urandom; cp /dev/zero /dev/urandom
• personality(personality(0xffffffff) | ADDR_NO_RANDOMIZE) で address randomization は全滅するらしい
• rdtsc は cr4.tsd というのをセットすると殺せるらしい
• gettimeofday はフック
• getrusage あたりが rdtsc 内部的に使ってたりしないだろうか

最後の3つは色々互いに絡んでる恐れがあるかな。

話としては、

• 基本的にはコードが長くならなきゃいいわけなんで、言語実装が勝手に呼ぶ srand の seed として使われてるシステムコールさえ殺せば問題なし
• rdtsc 殺しても kernel 内部で使っててかつそのシステムコールを言語処理系が seed として使ってると終わるので、やはり使ってる system call を全部殺すのが良さげ
• 今時の gettimeofday は vsyscall とかそのへんの仕組みで userland で rdtsc 呼んでるとか無いだろうか→となると libc hook を復活させないといけなくてだるい気もする
• 言語実装が勝手に自力で rdtsc を呼んでる…ってことはさすがに無いだろうか

あとは他に乱数源ってあったかなあ… 普通に考えると /dev/urandom とか time 系だけだと思うけど…

(11:09)

_ るびー

http://www.atdot.net/~ko1/diary/201101.html#d4

まぁこいうのはどこでも時々起きる系なのかなあよく知らんけど

Ruby については ruby-dev は「こわい」という話を ささださんにしたらこわくないよと言われた気がする。 当時もうまく説明できなかったけど、今もよくわからない。 ささださんの書いてる fundamental な人が多いと感じがするというのは、 割とその理由の一つかもしれないけどわからない。

ドキュメントは新しい熱心な人が聞きながら作る、ってのは まぁ一般的によくある話だとなんじゃないかなぁ。 そしてそれでいいんじゃないかなぁと思う。 よくわかってる人が書いたドキュメントって往々にして 新しい人にとって全然便利じゃなかったりするよね…

(23:49)

_ spoj

文字通り一日中ゴルフしてた…

http://www.spoj.pl/SHORTEN/ranks/

とりあえず7位まで。問題多すぎですがな… まぁ codegolf よりは軽い問題が多いのはありがたいか。

トップの人は普通の問題に強烈に強い印象で、 2位の人は bash がおかしいことになってる感じぽい。

しかしなんか bash って使えるコマンド変わってる疑惑があるのがやる気を削がれるが

(01:35)

_ 末尾再帰とか

http://blog.goo.ne.jp/no_orz_no_life/e/e7110098e80d89e28082065d32e9dd6b

の fact とか sum を見てて、 あらなんで3つ式あるのかなーと一瞬思ったんだけど、 まあたぶん末尾再帰の最適化かけたいという話だと思う。

で、そういえば GCC はどのくらい無茶なものを 末尾再帰にしてくれるのかなーとか思って色々やってみたら、 どうもすごく単純な足し算掛け算くらいしかできないぽかった。

まぁそんなもんかーと GCC を見ると、

     if (act->add && !a_acc)
       a_acc = create_tailcall_accumulator ("add_acc", first,
                                            integer_zero_node);

     if (act->mult && !m_acc)
       m_acc = create_tailcall_accumulator ("mult_acc", first,
                                            integer_one_node);

とかあって、やはり足し算と掛け算だけ特殊処理されてるのかな、 って感じだった。

関数型言語系だと、末尾が cons だった場合なんかにも、 似たような処理をしてやれば ずいぶんと色々とラクになるんじゃないかなぁとか思った。

あと、足し算掛け算以外を色々考えてる間に書いた、

def factdiv(n)
  if n==1
    1.0
  else
    n/factdiv(n-1)
  end
end

というような関数は、 つまり (2*4*8*...)/(1*3*5*...) という感じの値を返すわけだけど、 この値は 1.25 sqrt(N) くらいの数字になるみたいだった。 正確には (1*3*5*7*...)/(2*4*6*...) になってる時は 0.8 sqrt(N) くらいになってるので、この二つを繰り返すというか。

さてこれってなんか今まで見たことあるっけ… どうも見たことない気がするんだけど、 なんか有名な法則とかがありそうではある。

(23:39)

_ 年越し

年越す時に書いてたコードは spoj のゴルフだと思う。 たぶん kamil 。 spoj のゴルフはなんかよくわからんくらい短いものが結構あって、 なんか答え埋め込みとかになってるやつもあるのかなぁ。

年明けてからは BF_PRIME で、正月早々 Brainfuck ってのもどうなんですかね… しかもどうも勝てる気配があまりなくてですね…

kinaba さんの書いておられた、 なんかに特化した言語作るってのはいいかもなぁと思ったので、 Brainfuck の短いコードを出力するプログラムに特化した言語というのはどうか…

去年は今一つ、色んなことに慣れすぎてて特に何も無かったなぁ…という感じがした。 そいうことを思いながらはてなとか見てみた。

• 年始の WebKit についての紹介は妙に頑張ってるなあ
• コードを愛でる話はまぁそれなりに色々まとめたなぁ
• 一方 TCC の話はひどいなぁ
• TLE/ICFPC は残念な感じだったなぁ

とかあったんですが、このへんは知ってることまとめたりとかそういうのばっかで、 今一つ新鮮なことではなくて。

というわけで自分的に一番重要だったことは wake は今年作ったんだなぁということな気がする。

あとまぁ後半は Starcraft2 やってたなぁとしか言えないんじゃないかね。

(23:57)

_ あと

電車の中で暇だったのでだいぶ前に書いてた ld-mach-o を見てた。 クラッシュしてるところはどうも strcmp の中らしい。

gdb の reverse-stepi とかあのへんはじめて使ったけど、 さっさとクラッシュしてるようなケースだと便利だなぁ… と気付いた。 実益ないとバカにしてた record だけど、 まぁなんか使いかたあるかもなぁとか思いはじめてきた。

なかなかクラッシュしてくれないプログラムを考えると、 「クラッシュするちょっと前」を探してそこから record してくれると嬉しい。 しかしこれはどう考えても簡単じゃない。

たぶんタイマーみたいなのを仕込んで、 時々止めてみて rip を記録して、 次回は最後に止まったところで止めて record を仕込んで…とか考える。 ただその止まるようなところはどうせ何度も通るようなパスなんですねー。

はてさて

あと raw_write が TCC で動かないのがムカついたので インラインアセンブラをいじりはじめる。 raw_write は動いた。 r8 から先が全く対応されてないのでなんとかしたい、気がする。

(00:01)

_ ゴルフ場

ファイル保存可能問題がふたたび。

どうも /var/lib/php5 と /var/cache/common-lisp-controller が writable だったようだ。

これらはなんか writable であるべきってことで writable ぽいんだけど、 とりあえず hello world くらいなら php も clisp も 755 で動いてやがるので、とりあえずこれでいいかと放置。

問題あればおしえてください

(11:58)

_ addend について考える会

gcc -m32 -fPIC

 12:   8d 83 00 00 00 00       lea    0x0(%ebx),%eax
                       14: R_386_GOTOFF        .LC0
 18:   89 04 24                mov    %eax,(%esp)
 1b:   e8 fc ff ff ff          call   1c <gcc+0x1c>
                       1c: R_386_PLT32 puts

gcc -m32

  6:   c7 04 24 00 00 00 00    movl   $0x0,(%esp)
                       9: R_386_32     .rodata.str1.1
  d:   e8 fc ff ff ff          call   e <gcc+0xe>
                       e: R_386_PC32   puts

gcc -fPIC

  4:   48 8d 3d 00 00 00 00    lea    0x0(%rip),%rdi        # b <gcc+0xb>
                       7: R_X86_64_PC32        .LC0+0xfffffffffffffffc
  b:   e8 00 00 00 00          callq  10 <gcc+0x10>
                       c: R_X86_64_PLT32       puts+0xfffffffffffffffc

ここで addend は両方とも -4

gcc

  4:   bf 00 00 00 00          mov    $0x0,%edi
                       5: R_X86_64_32  .rodata.str1.1
  9:   e8 00 00 00 00          callq  e <gcc+0xe>
                       a: R_X86_64_PC32        puts+0xfffffffffffffffc

addend は後者だけ -4

tcc

  b:   48 8d 05 fc ff ff ff    lea    -0x4(%rip),%rax        # e <gcc+0xe>
                       e: R_X86_64_PC32        L.22
 12:   48 89 c7                mov    %rax,%rdi
 15:   b8 00 00 00 00          mov    $0x0,%eax
 1a:   e8 fc ff ff ff          callq  1b <gcc+0x1b>
                       1b: R_X86_64_PC32       puts

さて!

とか書いてるうちに気付いたが、 PLT 作った場合に rel->r_addend を足してないってだけの話だこれわ

(16:14)

_ とりあえず

• gcc -c でビルドしたバイナリが tcc でロードできない問題
• stdarg で struct 渡せない問題
• struct 渡す時の alignment が 8 じゃない問題

あたりを修正。 副産物として raw_write.h とかいうのができた

WebKit roll は今日はやたら平和

shinh.org はなんもしてない

27c3 とかいうのでゴルフ場使うよって話でいくつか対応

あと twitter/mircbot が止まってるのは twitter API が変わったとかなんとか

chrome extension は engoogle とかは user data を適当に廃棄したらインストールできるようになった。

chrome key config は任意 JS 書けないってことで、 shortcut manager にしようと思ったのだけど、 しかし chromekey が動いた時点でやる気が失せた

chromeswitchproxy は chrome のコードを見た結果、 gconf 経由で設定すれば gconftool-2 コマンドで 適当に動的に変えれる気がしたので、 それのラッパ書いてお茶を濁せば良いのではないかと思った。

(20:21)

_ 雑事

いろいろとやりたいが

• WebKit sheriff
  • とりあえず roll はしたので適当に見張る
• shinh.org
  • とりあえず SMTP サーバは結局上げてしまった
  • あと HTTP と health check
• clipboard 共有
  • 特に windows と virtualbox で
• chrome extension
  • どうも engoogle と chromekey がインストールできない
  • engoogle はなんとかする
  • chromekey は捨てて chrome key config でいく方向でいきたい…
  • あと chromeswitchproxy というのがあるっぽいので入れてみる
  • NPAPI 使ってるので、その前にコード読む
  • linux 版とか作れるといいわけだけどね

(18:20)

_ shinh.org is on vacation

timeline

• 掃除からの現実逃避
• u で apt-get upgrade してたら ssh つながらなくなった
• めんどくさいから再起動した
• 起動しない
• しょうがないから頑張ってディスプレイの文字を読もうとする
• 以前はかろうじて読めたけど全く読めないというかディスプレイが機能停止してる気がする
• しょうがないから外部ディスプレイ
• ダメ :(
• めんどくさいからいい機会なので u を殺そう
• u5 で tiarra 使って mirc を動かす感じに変更
• ゴルフ場の対向も変えた
• health check 殺した
• ssh はとりあえず u5 に

todo

• http://shinh.org
• SMTP は…もう殺す?
  • gmail からの転送設定がうざいことになると思われるが
• health check 復活させる

重要なデータは特に無いはずだから backup から基本全部取れるはず… まあ後で HDD ひっこぬいてデータは抜いておこうと思う

(09:24)