- キット各種完売。
- msBerryDAC改造情報
2008/01/15(火)WindowsですべてのインターフェイスからUDPブロードキャスト
要:winsock2
INTERFACE_INFO if_list[20]; unsigned long ifsize; if (WSAIoctl(sock, SIO_GET_INTERFACE_LIST, 0, 0, &if_list, sizeof(if_list), &ifsize, 0, 0) == SOCKET_ERROR) throw("Failed Interface List"); int if_num = ifsize / sizeof(INTERFACE_INFO); for (int i=0; i<if_num; i++) { sockaddr_in *adr_ip, *adr_net; adr_ip = (sockaddr_in *)&if_list[i].iiAddress; adr_net = (sockaddr_in *)&if_list[i].iiNetmask; sockaddr.sin_addr.s_addr = adr_ip ->sin_addr.s_addr; sockaddr.sin_addr.s_addr &= adr_net->sin_addr.s_addr; sockaddr.sin_addr.s_addr |= ~(adr_net->sin_addr.s_addr); // strcpy(s,inet_ntoa(sockaddr.sin_addr)); sendto(sock, "Find", 4, 0, (struct sockaddr *)&sockaddr, sizeof(struct sockaddr)); }
2007/08/24(金)実数FFT/IFFT関数
長年理解するのを拒否していたFFTとここ何週間か格闘しています。楽々とアルゴリズムを導出・実装できる人はいいのでしょうが、FFTのようなアルゴリズムをきちんと理解して実装するのは思うほど容易ではありません。既に導出されたアルゴリズム(や雛形サンプル)を何も考えず実装すれば簡単ですが、そういうことが生理的にできない場合、改良とかを考え出して簡単には実装できなくなるんですよね。
前置きはともかく、今日やっと実数専用のFFT/IFFTが作成できました。実数専用にすることで理論的には通常のFFTの半分の時間で処理できます。
見ての通り、実数FFTの対称性を利用したものすごく面倒くさく複雑な作りになっているんですが、有名なFFTの概略と設計法のソースと速度比較をしたら倍近く遅い……。64K点、double型、VIA C3 500MHzで動作させて、自作が100ms、リンク先のソースが60ms。
いかに細かい最適化をしても実装アルゴリズムの時点で差があると非常に大きいですね……。あとでアルゴリズムの差を検証予定。
ソース解読メモ
大浦氏のFFTソース(fft4g.c)解読メモ。つまりリバースエンジニアリングです。
サブルーチンの機能
cdft() | 複素数FFT/IFFT。データサイズは N/2 |
rdft() | 実数FFT/IFFT。内部的に複素FFTを呼び出し |
makewt() | sin/cosテーブルを w[] に格納(ただし格納位置はビット反転) |
makect() | cosテーブルを w[nw~] に格納(ただし格納位置はビット反転) |
bitrv2() | ビット反転を実行 |
bitrv2conj() | ビット反転しつつ、読込データの複素共役を取る |
cftfsub() | 複素IFFT(f=forward, 回転子が正であるという意味) |
cftbsub() | 複素FFT(b=backward, 回転子が負であるという意味) |
rftfsub() | 実数IFFT |
rftbsub() | 実数FFT |
IFFTをFFTで代用する方法
なんだけども、複素共役を考えると
つまり前処理と後処理としてデータの複素共役を取ってあげれば、同じFFTルーチンを使い回すことができる(効率を考えて、初段部分と終段部分だけ個別特別に実装すれば、中段部分は使い回せる)。
その他メモ
- 一般的なFFT(DFT)と比べ虚数部の符号が逆になっている。*1
周波数間引きFFTである
やっとこのプログラムの要が理解出来ました。
先にデータをスクランブルして(並べ替えて)いるため「時間間引きFFT」に見えますが、実際には周波数間引きFFTです。sin/cosテーブルもわざわざスクランブル位置に格納しています。
こうすることでFFT実行時のデータアクセスをシーケンシャルに行え*2、それが功を奏して実行速度が飛躍的に速くなっています。またsin/cosテーブル、偶数番地に cos、奇数番地に sin を格納し、全体としても π/2 しか用意しないことで、データアクセス量を減らしキャッシュが効きやすくなっています。
256点の複素FFTを実行させたときの、cos/sinテーブル参照位置およびデータ参照位置は次のようになります。
call cftmdl(512, 8) k1=1 (0.923880,0.382683), k2=2 (0.707107,0.707107) 32 36 40 44 33 37 41 45 34 38 42 46 35 39 43 47 k1=2 (0.980785,0.195090), k2=4 (0.923880,0.382683) 64 68 72 76 65 69 73 77 66 70 74 78 67 71 75 79 k1=3 (0.831470,0.555570), k2=6 (0.382683,0.923880) 96 100 104 108 97 101 105 109 98 102 106 110 99 103 107 111 k1=4 (0.995185,0.098017), k2=8 (0.980785,0.195090) 128 132 136 140 129 133 137 141 130 134 138 142 131 135 139 143 k1=5 (0.881921,0.471397), k2=10 (0.555570,0.831470) 160 164 168 172 161 165 169 173 162 166 170 174 163 167 171 175 k1=6 (0.956940,0.290285), k2=12 (0.831470,0.555570) 192 196 200 204 193 197 201 205 194 198 202 206 195 199 203 207 k1=7 (0.773010,0.634393), k2=14 (0.195090,0.980785) 224 228 232 236 225 229 233 237 226 230 234 238 227 231 235 239 call cftmdl(512, 32) k1=1 (0.923880,0.382683), k2=2 (0.707107,0.707107) 128 144 160 176 129 145 161 177 (中略) 142 158 174 190 143 159 175 191
ほんと、この実装はすごいなぁ。
2007/07/07(土)プラットホーム汎用で、固定長の整数型を使う
int型は整数型ですが、int や long や long long などは環境によってサイズが違ったりします。これらの型は、元もとサイズ(バイト長)を固定する目的で作られたものではないからです。
プラットホーム汎用でプログラムを書く際、固定長のデータを扱う時(バイナリデータ列など)は特に注意する必要があります。C99という規格で固定長整数型として int32t などが規定されましたが、すべての環境で使えるわけではありません。また Windows プラットホームならば、__int32 などが利用出来ますが、Windows以外では利用出来ません。
自分は、だいたいの環境でうまく動くマクロを作って、これを使っています。
#if defined(__C99__) || (defined(__GNUC__) && __GNUC__ >= 3) # include <inttypes.h> # include <stdint.h> #else # if defined(__GNUC__) typedef short int16_t; typedef unsigned short uint16_t; typedef int int32_t; typedef unsigned int uint32_t; typedef long long int64_t; typedef unsigned long long uint64_t; # elif (_MSC_VER || __BORLANDC__) typedef __int16 int16_t; typedef unsigned __int16 uint16_t; typedef __int32 int32_t; typedef unsigned __int32 uint32_t; typedef __int64 int64_t; typedef unsigned __int64 uint64_t; # endif #endif
2007/05/23(水)UDPをTCPにクローンするプログラム
UDPを受信してTCPにクローンするプログラム(複数クライアント対応)。本当はマルチスレッドで書いてあげるべきなのですが、そこまですると(実現する処理に対して)高級するぎる気がしたのでポーリングにしました。
というのも、TCPの通信エラーとかが出たときに(ブロックしないはずの)ソケットへの書き込み(データの送信)がバッファ一杯になるとストールして(止まって)しまうんですよね。もちろんソケットや書き込み時の関数はノンブロッキングに設定しておいても、です。C ではまだ確認していませんが、Perlで書いたときはそうでした。
TCP/IPはただ通信するだけなら簡単ですが、この手のエラー処理を考えはじめると非常に頭を使います。
プログラム
メイン部のみ。適当に main ルーチンを書けば Windows でも Unix系 でも動きます。
int max_connections=100; char buffer[0x10000]; int connection_pool[max_connections]; int accept_client(int listen_sock) { int sock, len; struct sockaddr_in sin; // accept len = sizeof(sin); sock = accept(listen_sock, (struct sockaddr *)&sin, &len); if (sock<0) error_return("client accept error"); // 接続者情報 printf("[%02d] Connection from %s\n", sock, inet_ntoa(sin.sin_addr)); // ソケットの設定 set_non_blocking(sock); return sock; } ////////////////////////////////////////////////////////////////////////////// // server main ////////////////////////////////////////////////////////////////////////////// int udp2tcp_server_main(int udp_sock, int tcp_sock) { int i; char buf[1024]; // select用の設定 fd_set fdbits; fd_set fdbits_org; FD_ZERO(&fdbits_org); FD_SET(udp_sock, &fdbits_org); FD_SET(tcp_sock, &fdbits_org); while(1) { // Select memcpy(&fdbits, &fdbits_org, sizeof(fdbits_org)); select(FD_SETSIZE, &fdbits, NULL, NULL, NULL); // New connection from TCP if ( FD_ISSET(tcp_sock, &fdbits) ) { int newsock = accept_client(tcp_sock); if (newsock>0) { // search for free connection pool point for(i=0; i<max_connections; i++) if (!connection_pool[i]) break; if (i<max_connections) { // ソケット番号をセーブ FD_SET(newsock, &fdbits_org); connection_pool[i] = newsock; dbg("[%02d] save to connection_pool[%d]\n", newsock, i); } else { // 接続を切る printf("Connections max\n"); close(newsock); } } } // Recieved from UDP int size = 0; if ( FD_ISSET(udp_sock, &fdbits) ) { size = recv(udp_sock, buffer, BUF_SIZE, MSG_DONTWAIT); if (size<0) error_exit2("UDP recv error(%d)", size); dbg("[%02d] Recieved UDP %d bytes\n", udp_sock, size); } // TCP接続クライアントにデータを送信 for(i=0; i<max_connections; i++) { int sock = connection_pool[i]; if (!sock) continue; // socket からデータ受信 if ( FD_ISSET(sock, &fdbits) ) { int s = recv(sock, buf, 1024, MSG_DONTWAIT); if (s<0) { FD_CLR(sock, &fdbits_org); connection_pool[i] = 0; dbg("[%02d] clear to connection_pool[%d]\n", sock, i); printf("[%02d] Connection close\n", sock); close(sock); continue; } } // データ送信 if (size>0) { //int s = write(sock, buf, size); int s = send(sock, buf, size, MSG_DONTWAIT); dbg("[%02d] write TCP %d bytes\n", sock, s); } } } }