ページ

2015年5月4日月曜日

C++で超シンプルなFFTの実装

Cooley & TukeyによるFFTアルゴリズムの発表から今年でちょうど50年だということに気づいて,久しぶりにFFTを自分で実装してみた.以下は,大浦 先生による有名なFFT (高速フーリエ・コサイン・サイン変換) の概略と設計法1.2 Cooley-Tukey 型 FFTにある最初の分解式(基数2の周波数間引きFFT)を,C++で素直に実装したものだ.できる限りシンプルに記述することだけを考えて,実行速度やメモリ効率はあえて一切気にしていない.

xが入出力の複素数配列.lengthが配列の長さで,2のべき乗数でなければならない.

実装してみて,あまりにもアッサリしたコードになったので驚いた.教科書やWebで見かけるFFTのコードは,配列をインターリーブまたはスプリットして複素数を表現していたり,呼び出し側で与えた有限長の作業領域を使い回したりするために,もう少し複雑になっているものが多い.そういったコードよりは,周波数間引きFFTの本質的な部分をシンプルに表現できているのではないかと思う. 

念のため付記しておくが,パフォーマンスを気にする場合は,こんなウンコードを書いてはいけない.再帰呼び出しによる実装はループによる実装に比べてスタックのpush/popにコストがかかるし,オーバーロード演算 子の利用は一時変数のためのオーバーヘッドの可能性があるし,何より関数内でstd::vectorの領域確保などすべきではない.

2014年6月7日土曜日

Xcode 5 でwxWidgetsアプリのビルド

前回のエントリでwxWidgetsのこれでようやくwxWidgetsを使ってアプリケーションを開発することが出来る.サンプルコードのようにMakefileでビルドするのも悪くないのだけど,私はコマンドラインデバッガをまともに使えないので,やはりアプリの開発はXcodeでやりたい.

まずはプロジェクトの新規作成.テンプレートはOS X ApplicationのCocoa Applicationを選択する.

プロジェクトが作成されたら,以下の2個以外の構成ファイルを全部削除する.

  • (プロジェクト名)-Info.plist
  • main.m


main.mをmain.cppに変更して,Objective-Cの文法を全部消す.

ここからBuild Settingsにいくつかの設定をしなければないが,毎回やるのが面倒なので,以下のような設定ファイルを記述した.私はこの設定ファイルをwxWidgetsのインストールディレクトリに置いておき,新しくアプリを作るときにコピーして使っている.

mywx.xcconfig

WXTOOLKIT = cocoa
WXTOOLKITUPPER = COCOA
WXROOT = /Users/USERNAME/Develop/wxWidgets-3.0.0
HEADER_SEARCH_PATHS = $(inherited) $(WXROOT)/lib/wx/include/osx_cocoa-unicode-static-3.0 $(WXROOT)/include/wx-3.0LIBRARY_SEARCH_PATHS = $(inherited) $(WXROOT)/lib
GCC_PREFIX_HEADER = $(WXROOT)/include/wx-3.0/wx/wxprec.h
GCC_PRECOMPILE_PREFIX_HEADER = YES
MACOSX_DEPLOYMENT_TARGET = 10.7
ARCHS = i386 x86_64
GCC_PREPROCESSOR_DEFINITIONS = $(WX_PREPROCESSOR_DEFINITIONS) __WX__ __WXMAC_XCODE__=1 __WXOSX_COCOA__ wxUSE_BASE=1 WX_PRECOMP=1 wxUSE_UNICODE_UTF8=0 wxUSE_UNICODE_WCHAR=1 _FILE_OFFSET_BITS=64 _LARGE_FILES SCI_LEXER
CLANG_CXX_LIBRARY = libstdc++
OTHER_LDFLAGS = -framework WebKit -framework IOKit -framework Carbon -framework Cocoa -framework AudioToolbox -framework OpenGL -framework QTKit -lz -liconv -lwx_baseu-3.0 -lwx_baseu_net-3.0 -lwx_baseu_xml-3.0 -lwx_osx_cocoau_adv-3.0 -lwx_osx_cocoau_aui-3.0 -lwx_osx_cocoau_core-3.0 -lwx_osx_cocoau_gl-3.0 -lwx_osx_cocoau_html-3.0 -lwx_osx_cocoau_media-3.0 -lwx_osx_cocoau_propgrid-3.0 -lwx_osx_cocoau_qa-3.0 -lwx_osx_cocoau_ribbon-3.0 -lwx_osx_cocoau_richtext-3.0 -lwx_osx_cocoau_stc-3.0 -lwx_osx_cocoau_webview-3.0 -lwx_osx_cocoau_xrc-3.0 -lwxpng-3.0 -lwxregexu-3.0 -lwxscintilla-3.0 -lwxtiff-3.0


さて,mywx.xcconfigをプロジェクトにコピーする.そしてプロジェクトのConfigurationsにmywx.xcconfigを適用する.

どうもmywx.xcconfigだけでは設定しきれない箇所があるので,TargetのBuildSettingsを手動で設定する.

まずPrefix Headerの設定から,最初に削除した(プロジェクト名)-Prefix.pchファイルの設定を削除する.

次に,C++ Standard Libraryをlibc++に変更する.

さて本来ならここでビルドが通るべきだと思うのだが,ビルドしてみると,config_xcode.hがないとかいうエラーが出る.探してみると,wxWidgetsをダウンロードして展開したディレクトリのinclude/wx/osx/の中にこのファイルがあるようだが,インストールディレクトリにコピーされていない.よくわからないけど,このファイルを手動でインストールディレクトリのinclude/wx-3.0/wx/osx/にコピーしてしまった.

以上の設定で,ようやくビルドが通った.mywx.xcconfigだけで設定しきれない部分も結構あるので,Xcodeプロジェクトのテンプレートにできると良いのだけど,やり方がいまいちよくわからないのでとりあえず保留.まぁ手作業でやっても慣れれば1分もかからないだろう.

あとはwxWidgets tutorial(http://zetcode.com/gui/wxwidgets/)などをやってみると,基本的なだいたい使い方がわかる.



Max OS X 10.9 (Mavericks)でwxWidgets

概要

目標


  • wxWidgetsのMac OS X用静的リンクライブラリを作る
  • ターゲット環境は以下の通り
    • CPUアーキテクチャ : Intel Mac (32bit/64bitユニバーサルバイナリ)
    • 最低動作OSバージョン: Mac OS X 10.7 (Lion)

ビルド環境


  • iMac 21.5-inch, Late 2009
  • Mac OS X 10.9 (Mavericks)
  • Xcode 5.1.1
  • Apple LLVM version 5.1


ダウンロードとconfigure

まずは公式サイトからwxWidgets 3.0.0のソースコードをダウンロードして(Source for Linux, OS X, etcってやつ),適当なディレクトリに展開した

ビルドには以下ページを参考にした(若干情報が古いものもある).



Xcodeを使ってビルドする方法もあるようだけど,4番目のページに
"Building wxWidgets using Xcode is generally less flexible and reliable than use the terminal."
とか書いてあるので,今回はconfigureでビルドすることにする.

configureは以下のように実行した.できれば1個の静的ライブラリにまとめられればスッキリするのだけど,--disable-sharedと--enable-monolithicは一緒に使うなと2番目のページに書いてあったので,--disable-sharedだけにしておく.

./configure --disable-shared --enable-unicode --with-osx_cocoa --enable-universal-binary=i386,x86_64 --with-macosx-version-min=10.7 --with-macosx-sdk=/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.9.sdk --prefix=/Users/USERNAME/Develop/wxWidgets-3.0.0

後から知ったところによると,--enable-unicodeはデフォルトになっているらしいので,ここで明示的に指定する必要はなかったかも.

なおこの設定ではC++標準ライブラリとしてlibstdc++を使うようにビルドされるので,アプリでlibc++を使いたい場合は明示的にその設定を加える必要がある.

PowerPCのMacを相手にすることは今後恐らく無いので,--enable-universal-binary=i386,x86_64にしてある(i386さえ既に不要かもしれない),
--with-macosx-version-minは最低動作OSバージョン.--with-macosx-sdkはビルドに使うSDKで,基本的には現在Xcode.appの中に入っている最新のSDKを指定すれば良いと思う.--prefixは,wxWidgetsをインストールするディレクトリを指定する.これを明示的に指定しないとたぶん/usr/local配下に入ってしまって,複数バージョンの共存やアンインストールが難しくなる.私の場合は自分のホームディレクトリにDevelopというディレクトリを作ってあるので,その配下にwxWidgets-3.0.0というディレクトリを作って(予め作っておく必要がある)インストールすることにした.

ビルド

さてconfigureが完了したのでmakeしてみると,以下のようなエラーが出る.
./src/tiff/libtiff/tif_lzma.c:38:10: fatal error: 'lzma.h' file not found
#include "lzma.h"
./src/common/imagjpeg.cpp:45:14: fatal error: 'jpeglib.h' file not found
#include "jpeglib.h"

ググってみると,似たようなトラブルに遭遇している人がいる.
https://bugs.launchpad.net/kicad/+bug/1285317

要するに,homebrewでxzとlibjpegをインストールして,インクルードパスとリンクパスを通せば良いらしい.私の場合は既に両方インストール済みだったので,

export CFLAGS="$CFLAGS -I/usr/local/Cellar/xz/5.0.5/include"
export CFLAGS="$CFLAGS -I/usr/local/Cellar/jpeg/8d/include"
export CPPFLAGS="$CFLAGS"
export CXXFLAGS="$CFLAGS"
export LDFLAGS="$LDFLAGS -L/usr/local/Cellar/xz/5.0.5/lib"
export LDFLAGS="$LDFLAGS -L/usr/local/Cellar/jpeg/8d/lib"

のように環境変数としてパスを指定して,
./configure (オプションは上記の通り)

そして
make -j 2

このmakeにはかなり時間がかかることが試行錯誤しているうちにわかっていたので,-j 2オプションをつけて並列実行したのだけど,それでも30分ぐらいかかった.私のiMacがだいぶ古いせいかもしれない.

インストール

make install

すると,アプリ開発に必要なファイルが,configureの--prefixで指定したディレクトリにコピーされる.

念のため,libディレクトリ以下の静的バイナリがちゃんとUniversalバイナリになっているか確認.
lipo -info libwx_osx_cocoau_core-3.0.a

Architectures in the fat file: libwx_osx_cocoau_core-3.0.a are: i386 x86_64

うまくいったようだ.

2012年8月5日日曜日

花火の音を畳み込む

今日は寮の近所で花火をやっていた.人の声に花火の音を畳み込んだら,大空から叫んだような音になるだろうか?

まずは人の声を録音


続いて花火の音を録音


畳み込んだ結果がこちら


なんか神話系のB級映画に出てくる神の声みたいで気持ち悪い...誰か爽やかな叫び声の提供求む.

2012年2月22日水曜日

MacOS X Lion で portaudio

クロスプラットフォームのオーディオIOライブラリであるportaudioを使ってみた。導入に少々手こずったのでメモ。

【環境】
MacOS X 10.7 (Lion)
Xcode 4.3 (Command Line Toolsインストール済)

【問題】
本家サイトのチュートリアル通りに ./configure &&  make すると
lipo: can't figure out the architecture type of: /var/folders/nc/xfr4g99532d8907r35nypqcc0000gn/T//ccNT0oeE.out
make: *** [src/common/pa_allocation.lo] Error 1

とかいうエラーが出てmakeが止まる。

【解決方法】
1.  portaudio/include/pa_mac_core.h の49行目
#include <audiotoolbox/audiotoolbox.h>
のコメントをはずす。

2.  portaudio/ で以下を実行
$ ./configure --disable-mac-universal

3. 生成されたMakefileの CFLAGS にある -Werror を削除

4. portaudio/ で make を実行
(いちど make に失敗している場合は make clean してから)

以上の手順で portaudio 自体のmakeは通るはず。ただしx86_64バイナリ専用(私はppcもi386も必要ない)。以下のファイルが生成されていればOK。

【プログラムのコンパイル方法】
portaudio/examples/paex_sine.cをコンパイルする例。こんな感じのMakefileで静的リンクできた。動的リンクはよくわからない。
CC = gcc
LIBS = -framework CoreAudio -framework AudioToolbox -framework AudioUnit -framework Carbon
INCLUDES = -I/(portaudioのパス)/include
LIBPA = /(portaudioのパス)/lib/.libs/libportaudio.a
OBJS    = paex_sine.o

paex_sine: $(OBJS)
$(CC) $(LIBS) -o $@ $(OBJS) $(LIBPA)
.c.o:
$(CC) $(INCLUDES) -c $<

【参考リンク】
Building PortAudio under OS X 10.7 Lion