ごとむにっき
先月 2005年12月 来月
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

2005年12月04日() [n年日記]

#1 Binary 2.0 カンファレンスと発表資料

2005年12月02日(金)に開催された Binary 2.0カンファレンス2005 のライトニングトークのネタを web で公開しました。以下が資料です。

「斜め下を行くバイナリ書き換えの探求」( HTML版, PDF版 OpenOffice Impress ver1 (SXI)版

少々ネタに走っていますが、ご自由にご賞味ください。
今回はレベルの低い人々が集まって、ここまでもか、と様々なネタが提供されて存分に楽しむことができました。 開催者の高林さんをはじめ、発表者皆様お疲れ様でした。

2005年12月06日(火) [n年日記]

#1 3c59xのイーサネットアドレス書き換え

電源を別のマシンに差しかえたため、しばらく使っていなかったマシン(Athlon 1.8GHz) に電源を新規購入し、カーネルを最新版にした。しかし、ethernet が認識しなくなった。 使ってるカードは 3c59x なわけだが、2.6.14にアップグレードしたカーネルでドライバをinsmodすると 以下のようなつれない返事が戻ってくる。
 kernel: 3c59x: Donald Becker and others. www.scyld.com/network/vortex.html
 kernel: 0000:02:06.0: 3Com PCI 3c905C Tornado at 0xa000. Vers LK1.1.19
 kernel: *** EEPROM MAC address is invalid.
 kernel: 3c59x: vortex_probe1 fails.  Returns -22
 kernel: 3c59x: probe of 0000:02:06.0 failed with error -22
該当するカーネルコード drivers/net/3c59x.c は以下の通り。
        ...
                for (i = 0; i < 0x40; i++) {
                        int timer;
                        outw(base + i, ioaddr + Wn0EepromCmd);
                        /* Pause for at least 162 us. for the read to take place. */
                        for (timer = 10; timer >= 0; timer--) {
                                udelay(162);
                                if ((inw(ioaddr + Wn0EepromCmd) & 0x8000) == 0)
                                        break;
                        }
                        eeprom[i] = inw(ioaddr + Wn0EepromData);
                }
        }
	...
        for (i = 0; i < 3; i++)
                ((u16 *)dev->dev_addr)[i] = htons(eeprom[i + 10]);
        if (print_info) {
                for (i = 0; i < 6; i++)
                        printk("%c%2.2x", i ? ':' : ' ', dev->dev_addr[i]);
        }
        /* Unfortunately an all zero eeprom passes the checksum and this
           gets found in the wild in failure cases. Crypto is hard 8) */
        if (!is_valid_ether_addr(dev->dev_addr)) {
                retval = -EINVAL;
                printk(KERN_ERR "*** EEPROM MAC address is invalid.\n");
                goto free_ring; /* With every pack */
        }
どうやら読み取った EEPROM に格納されている MAC アドレスがおかしいか、EEPROM が読めていないらしい(まあ、今までよく 00:00:00:00:00:00 で何も問題にならずに動いていたな…という感じはするが):
 wurlitzer:> sudo ifconfig eth0
 eth0      Link encap:Ethernet  HWaddr 00:00:00:00:00:00  
           inet addr:192.168.0.XX  Bcast:192.168.0.255  Mask:255.255.255.0
           UP BROADCAST RUNNING MULTICAST  MTU:1500  Metric:1
           RX packets:731 errors:0 dropped:0 overruns:0 frame:0
           TX packets:409 errors:0 dropped:0 overruns:0 carrier:1
           collisions:0 txqueuelen:1000 
           RX bytes:66588 (65.0 KiB)  TX bytes:61242 (59.8 KiB)
           Interrupt:17 Base address:0xa000 
エラーチェックはAlan Coxのパッチによって導入されたようだ:
* PATCH: 3c59x 00:00:00:00:00:00 MAC failure (http://www.ussg.iu.edu/hypermail/linux/kernel/0409.3/1330.html)
 The 3com EEPROM has a checksum but unfortunately it seems that a zapped
 EEPROM returning all zero values passes the checksum test fine and we try
 and use it.
最初 ethtool で EEPROM 情報をとろうとするが、これはサポートされていないらしい。 Donald Becker 作の vortex_ethtool_ops には EEPROM 操作関数が入っていない (遊びでサポートするのは良いかも。簡単にできるし):
 wurlitzer:~> sudo ethtool -e eth0
 Cannot get EEPROM data: Operation not supported
色々探していると、どうやら nictools-pci なるものが ethtool とは別にあり、 その中の vortex-diag が 3c59x 系 NIC の情報を読み書きできるらしい:
* Linux Ethercard Status, Diagnostic and Setup Utilities. (http://www.scyld.com/ethercard_diag.html)
これを使えば EEPROM が本当に読めていないのか、それとも EEPROM に入っている情報がおかしいのかが分る。 早速試してみると:
 wurlitzer:~> sudo vortex-diag -ee
 vortex-diag.c:v2.16 1/12/2004 Donald Becker (becker@scyld.com)
  http://www.scyld.com/diag/index.html
 Index #1: Found a 3c920 Series NIC adapter at 0xa000.
  Station address 00:00:00:00:00:00.
   Receive mode is 0x07: Normal unicast and all multicast.
 EEPROM format 64x16, configuration table at offset 0:
     00: 00e0 187a d5XX 9200 ffff ffff ffff 6d51
   0x08: 2940 0000 0000 0000 0000 0010 0000 00aa
   0x10: 72a2 0000 0000 0180 0000 0000 0000 10b7
   0x18: 1000 000a 0000 6300 ffb7 b7b7 0000 0000
   0x20: 0000 1234 5670 0000 0000 0000 0000 0000
   0x28: 0000 0000 0000 0000 0000 0000 0000 0000
   0x30: ffff ffff ffff ffff ffff ffff ffff ffff
       ...
 
  The word-wide EEPROM checksum is 0x30XX.
 Saved EEPROM settings of a 3Com Vortex/Boomerang:
  3Com Node Address 00:E0:18:7A:D5:XX (used as a unique ID only).
  OEM Station address 00:00:00:00:00:00 (used as the ethernet address).
   Device ID 9200,  Manufacturer ID 6d51.
   Manufacture date (MM/DD/YYYY) 15/31/2027, division , product .
   No BIOS ROM is present.
  Transceiver selection: Autonegotiate.
    Options: negotiated duplex, link beat required.
    PCI bus requested settings --  minimum grant 10, maximum latency 10 (250ns units).
  PCI Subsystem IDs: Vendor 10b7 Device 1000.
  100baseTx 10baseT.
   Vortex format checksum is incorrect (93 vs. 10b7).
   Cyclone format checksum is incorrect (0x2e vs. 00).
   Hurricane format checksum is incorrect (0x05 vs. 00).
ちゃんと EEPROM の中身は読めているらしい。よく中をみてみると、3Com Node Address は 00:E0:18:7A:D5:XX に対し、OEM Station address が設定されておらず、まっ白である。 先ほどのコードをみると、EEPROM に入っている MAC アドレスは、word 単位で 10 番地目からに相当するが、 該当の個所は確かに 00:00:00:00:00:00 で埋められてる。 なお、00:E0:18 は
* IEEE OUI and Company_id Assignments (http://standards.ieee.org/regauth/oui/index.shtml)
で検索すると
 00-E0-18   (hex)		ASUSTEK COMPUTER INC.
 00E018     (base 16)		ASUSTEK COMPUTER INC.
 				150 LI-TE RD.
 				PEITOU, TAIPEI  
 				TAIWAN, REPUBLIC OF CHINA
マザボベンダの名前がついているのに、OEMアドレスには何も埋められずに出荷されたらしい。 これはおそらくマザボ側のバグではないかと思われる。 ただ、カーネルもOEMアドレスが入ってなかったら3Com Node Addressをみるようにしておくと親切といえば親切だったかも(今回は3Comのカードの仕様に詳しくないので、ドライバ変更はパスした)。
そこで、3Com Node Address に基づき OEM Station Address を次のようにして変更した(マニュアルにはやり方が詳しく書いてないので、結局 nictools-pci のソースコードを読んで変更方法を理解した…)。
 wurlitzer:~> sudo vortex-diag -H 00:E0:18:7A:D5:XX -w
 vortex-diag.c:v2.16 1/12/2004 Donald Becker (becker@scyld.com)
  http://www.scyld.com/diag/index.html
 Index #1: Found a 3c920 Series NIC adapter at 0xa000.
  Station address 00:00:00:00:00:00.
   Receive mode is 0x07: Normal unicast and all multicast.
  Would write new 10 entry 0x00e0 (old value 0x0000).
  Would write new 11 entry 0x187a (old value 0x0000).
  Would write new 12 entry 0xd5XX (old value 0x0000).
  Would write new 32 entry 0x0091 (old value 0x0000).
  Use '-a' or '-aa' to show device registers,
      '-e' to show EEPROM contents, -ee for parsed contents,
   or '-m' or '-mm' to show MII management registers.
これで EEPROM が無事変更された。
 EEPROM format 64x16, configuration table at offset 0:
     00: 00e0 187a d5XX 9200 ffff ffff ffff 6d51
   0x08: 2940 0000 00e0 187a d5XX 0010 0000 00aa
   0x10: 72a2 0000 0000 0180 0000 0000 0000 10b7
   0x18: 1000 000a 0000 6300 ffb7 b7b7 0000 0000
   0x20: 0091 1234 5670 0000 0000 0000 0000 0000
   0x28: 0000 0000 0000 0000 0000 0000 0000 0000
   0x30: ffff ffff ffff ffff ffff ffff ffff ffff
2.6.14 カーネルでも
 wurlitzer:~> sudo ifconfig
 eth0      Link encap:Ethernet  HWaddr 00:E0:18:7A:D5:XX  
           inet addr:192.168.0.13  Bcast:192.168.0.255  Mask:255.255.255.0
           inet6 addr: fe80::2e0:18ff:fe7a:d5e8/64 Scope:Link
           UP BROADCAST RUNNING MULTICAST  MTU:1500  Metric:1
           RX packets:97 errors:0 dropped:0 overruns:0 frame:0
           TX packets:87 errors:0 dropped:0 overruns:0 carrier:0
           collisions:0 txqueuelen:1000 
           RX bytes:8541 (8.3 KiB)  TX bytes:7207 (7.0 KiB)
           Interrupt:169 Base address:0xa000 
ちゃんと認識するようになったようだ。 3c59x の NIC を持っていて MAC アドレスがうまく設定されない場合、上記を参考に設定すると良いだろう。
最後になるが、EEPROM の設定変更に際しては、折角もらった MAC アドレスや設定データ、チェックサムを破壊する可能性がある。自己責任で注意して作業されたい。

2005年12月08日(木) [n年日記]

#1 組み合わせとGMP

 shom> 順列組合せの計算て奥深いな
 shom> 精度を保ちながら、nCr 計算する方法がわからんな
 shom> 内部はなんでもいいんだけどさ。
 shom> ちょっと確率計算をjavascriptでやるかなーと思ってなんも考えずに組んでみたら、
 shom> やっぱだめだなとw
 ukai> javascriptか
 shom> 100 C 90 とかしちゃうと破綻だ
 shom> しょせんは組合せだから、ちゃんとやれば整数だけでいけるはずなんだけどねぇ。
 ukai> 近似で
 shom> 素因数分解でもしてやるのが一番いいんだろうかw
 gotom< nCr = n!/(r!(n-r)!) だっけか
 shom> んむ 階乗計算があふれて近似になりそうだ
 gotom< (n*(n-1)*(n-2)*...(n-r+1))/(n-r)!
 ukai> http://ja.wikipedia.org/wiki/%E4%BA%8C%E9%A0%85%E5%88%86%E5%B8%83
 gotom< (n*(n-1)*(n-2)*...(n-r+1))/r!か
 gotom< n/r * (n-1)/(r-1) * ... or n/1 * (n-1)/2 *...
 shom> 前者をやってみたらさ、
 shom> 100 C 10 はいけるが、100 C 90 でふつーに小数点がw
 gotom< しばらくかけ算して縮約かなあ
 shom> 1.0089134454556417e+29
 shom> 100 C 50 はこんなことにw
 shom> 有効桁数判断しながら、できるだけ少ない誤差になるような計算ステップを踏むべしなのかな
という話を小耳にはさんだので、まず自前で有効桁数を越えないように時々割り算しながら double 型に値を累積させていく方法をC言語で試してみた。

適宜割り算する方法:

 #include <stdio.h>
 
 unsigned long long int n = 100;
 unsigned long long int r = 50;
 
 int main(void)
 {
   unsigned long long int prev, pc;
   unsigned long long int denom, dc;
   unsigned long long int test;
   double res = 1;
   int i;
 
   if (n - r < r) {
     r = n - r;
   }
   prev = n;
   denom = r;
   for (i = 1; i < r; i++) {
     pc = prev;
     pc *= (n - i);
     dc = denom;
     dc *= (r - i);
     test = pc / (n - i);
     printf("%d start %llu %llu %llu %llu %llu\n", i, test, pc, prev, dc, denom);
     if (test != prev) {
       /* reduction */
       res *= (prev / denom);
       prev = (n - i);
       denom = (r - i);
       printf("%d reduction %llu %llu %llu %llu %f\n", i, prev, denom, pc, dc, res);
     } else {
       prev = pc;
       denom = dc;
       printf("%d %llu %llu\n", i, prev, denom);
     }
   }
   res *= (prev / denom);
   printf("%lf\n", res);
 }
だいぶ手抜きしているが、なんとなく動くはず。ただ、数を大きくするほど、 徐々に答えがあやしくなる。そこはdouble型の限界(かバグかも)。このプログラムだと 100c50 = 100850159033511756859346780160 と出力されるが、次に述べる GMP を使用すると、 正確な答え 100891344545564193334812497256 となる(桁数途中まではあっているので、やはり doubleの精度が全く足りないのだろう)。4倍精度が使えるFPUであれば、もう少しまともな 答えが出そうであるが…。

GMPを使う方法:

続いてGMPを使ってみた。 GMP (GNU Multi Precision) ライブラリ とは、多倍長計算を簡単に実現できるライブラリである。GMPを使ったのが以下のプログラムである。
 #include <stdio.h>
 #include <gmp.h>
 unsigned long n = 2000;
 unsigned long r = 1000;
 int main()
 {
   mpq_t q, s;
   unsigned long i;
   if (n - r < r) {
     r = n - r;
   }
   mpq_init(q);
   mpq_init(s);
   mpq_set_ui(q, n, 1);
   for (i = 1; i < r; i++) {
     mpq_set_ui(s, n - i, i + 1);
     mpq_mul(q, q, s);
   }
   mpq_canonicalize(q);
   mpq_out_str(stdout, 10, q);
   printf("\n");
 }
難しいことをあまり考えずにすっきりと書けている。
解説すると、mpq_t はGMP有理数型。mpq_initで型の値を初期化し、mpq_set_ui でunsigned long int型の値を代入し、mpq_mulで掛け算。mpq_canonicalize で答えを正規化し(これをやらないと有理数のまま出力されることがある)、mpq_out_str で標準出力に答えを出す。
うーん、GMPを使うとこの手のプログラムは一気に楽に書けそうだ。ちなみに 100000c50000 の答えは約3万桁だそうで、P4 2.4GHzを使えば約5秒弱で結果が出る。

以上、3 日分です。
タイトル一覧
カテゴリ分類
Powered by hns-2.19.5, HyperNikkiSystem Project