<< index

小さなねた 3

S.PROGRAMS NET :: HSP :: KONETA for HSP 3

ここはなに?

HSP (3.0 ～) 向けの微妙なネタをせまく紹介していきます。

掲載スクリプトは著作権フリーです。自分のソフトで流用してもいいし、どっかにそのまま転載してもべつにかまいません。

誤りか何かを見つけられた方は、BBS かメールで報告していただけるとありがたいです。

2007/06/24 HSP で float 型っぽい変数
2007/01/10 HSP でガラス効果のボックス描画
2006/07/27 マジ万能? マージソート
2006/07/27 マウスの戻る・進むボタンの入力を取得する

HSP で float 型っぽい変数

さて今回は、浮動小数点数の話なのに整数演算しか出てこない話題でも。

HSP が変数として保持できる浮動小数点型は 64bit の double 型のみで、32bit の float 型はありません。

普通に使う分には精度の高い double があれば float は要らないので、言語的にもシンプルでよろしいのですが、 HSP と無関係に作られたコンポーネントと連携したい場合、困ったことが起こる場合があります。例えば、float 型を含む構造体や float 配列などを要求する DLL を使いたいとなった場合、HSP ではその型のデータを用意できないのです。

こういう場合は、自前で float 型っぽいデータを作ってやるしかありません。

HSP で float 値を用意する最も手っ取り早い手段として、より高精度の double 型のデータから精度ダウンさせて float 型に変換し、それを int 型変数に入れておく、という方法が考えられます。

浮動小数点数を規定した IEEE 754 (→ Wikipedia) によると、単精度 (32bit float) は、上位ビットから [符号 1][指数 8][仮数 23] の順番でビットが並んでおり、倍精度 (64bit double) は、同じく [符号 1][指数 11][仮数 52] の順番で並んでいます。指数部の正負表現方法は、signed int のそれとは違うバイアス方式となっています。

double bits
 SEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
float bits
 SEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFF

指数部が float の範囲に収まる数ならば、簡単な演算で double から float に落とせそうです。

; double to float

	d = 3.141592 ; 変換したい double 値

	; 符号ビットをセット
	f = lpeek(d, 4) & 0x80000000

	if d ! 0.0 { ; 非ゼロならば :

		; 指数部を変換してセット
		; (double のバイアスは 1023, float は 127)
		f |= (((lpeek(d, 4) >> 20) & 0x7FF) - 1023 + 127) << 23

		; 仮数部 (上位 20bit) をセット
		f |= (lpeek(d, 4) << 3) & 0x7FFFFF

		; 仮数部 (下位 3bit) をセット
		f |= (lpeek(d, 0) >> 29) & 7
	}

	mes f ; 変換された結果 (HSP 変数としては int 型)

指数部のバイアスと、ゼロの表現との関係に注意が必要です。IEEE 754 では、ゼロの表現は指数部、仮数部ともに 0 とすることになっています。0.0 (double) の指数部を普通にバイアス変換してしまうと、結果 (float) はゼロではなくなってしまいます。

ちなみに、浮動小数点数には通常の数値 (正規化数) とゼロの他にも非正規化数, 無限大, NaN がありますが、ここでは考慮していません。

上のコードを短く最適化し、関数にまとめると、下のようになります。

#defcfunc tofloat double p1
	temp = p1
	return lpeek(temp)>>29&7|(p1<0)<<31|lpeek(temp,4)-(p1!0)*0x38000000<<3

lpeek(temp,4)-0x38000000<<3 という部分がキモで、0 より大きい数ならば、これだけでもそこそこの精度で変換されます。

今回のネタは、GDI+ で float 配列が必要になったので、その副産物としてアップしてみました。しかし、そういう DLL を HSP から叩くことはそんなには無いと思うので、なんとも微妙なピンポイントネタです。

- - -

せっかくなので、ここまでの作業の逆変換として、float (のデータが入った int) から double に変換する関数も書いてみます。

#defcfunc todouble int p1
	temp = 0.0
	lpoke temp, 4, (p1 & 0x80000000) | (((p1 & 0x7fffffff) >> 3) + ((p1 & 0x7fffffff) ! 0) * 0x38000000)
	lpoke temp, 0, p1 << 29
	return temp

2007/07/05
上のコードの青文字部分「 ((p1 & 0x7fffffff) ! 0) * 」を追加。ひどいことに、少し上で自分で書いていたゼロ判定をすっかり忘れていましたよ。

これで、double と float の相互変換ができるようになりました。

HSP2 の頃 hgimg に実装されていたような、float の四則演算関数も作れますね。無意味に．．．

#define global ctype	fadd(%1, %2)	tofloat(todouble(%1) + todouble(%2))
#define global ctype	fsub(%1, %2)	tofloat(todouble(%1) - todouble(%2))
#define global ctype	fmul(%1, %2)	tofloat(todouble(%1) * todouble(%2))
#define global ctype	fdiv(%1, %2)	tofloat(todouble(%1) / todouble(%2))
#define global ctype	fneg(%1)	((%1) ^ 0x80000000)

最後に、double と float でどれだけ精度が違うのか比較観察しておしまい。

; float for HSP モジュール

#module
#defcfunc todouble int p1
	temp = 0.0
	lpoke temp, 4, (p1 & 0x80000000) | (((p1 & 0x7fffffff) >> 3) + ((p1 & 0x7fffffff) ! 0) * 0x38000000)
	lpoke temp, 0, p1 << 29
	return temp

#defcfunc tofloat double p1
	temp = p1
	return lpeek(temp)>>29&7|(p1<0)<<31|lpeek(temp,4)-(p1!0)*0x38000000<<3

#define global ctype	fadd(%1, %2)	tofloat(todouble(%1) + todouble(%2))
#define global ctype	fsub(%1, %2)	tofloat(todouble(%1) - todouble(%2))
#define global ctype	fmul(%1, %2)	tofloat(todouble(%1) * todouble(%2))
#define global ctype	fdiv(%1, %2)	tofloat(todouble(%1) / todouble(%2))
#define global ctype	fneg(%1)	((%1) ^ 0x80000000)
#global

	a = 10.0 / 3.0

	mes strf("%.16f", a)
	mes strf("%.16f", a * a)

	a = tofloat(a)

	mes strf("%.16f", todouble(a))
	mes strf("%.16f", todouble(fmul(a, a)))

HSP でガラス効果のボックス描画

作ったけど結局使わなかった小モジュールで、見た目だけよさそうなものがあったのでアップしてみます。

2000 年? 2001 年? くらいから流行りだしたアレ、Aqua をマネた感じのデザイン要素を描画するためのモジュールです。ゲームやメディアプレイヤーなどで、アプリケーションの UI をすべて独自に描画するような場合に使えるかもと思って書いてみました。

上のような質感の矩形を boxf 命令感覚で画面に出せるようにします。(誇大広告くさいけど)

・モジュール本体

#module "glsbox"

; stripebox  x, y, w, h
; 現在の選択色でストライプ模様のボックスを描画
#deffunc stripebox int x, int y, int w, int h
	if h * w <= 0 : return
	r = ginfo_r
	g = ginfo_g
	b = ginfo_b
	repeat h
		c = (y+cnt&2)*5
		color limit(r + c, 0, 255), limit(g + c, 0, 255), limit(b + c, 0, 255)
		boxf x, y+cnt, x+w-1, y+cnt
	loop
	color r, g, b
	return

; glassbox  x, y, w, h
; 現在の選択色でガラス質感のボックスを描画
#deffunc glassbox int x, int y, int w, int h
	if h * w <= 0 : return
	r = ginfo_r
	g = ginfo_g
	b = ginfo_b
	repeat h
		c = cnt * 128 / h
		color limit(r + sr.c, 0, 255), limit(g + sr.c, 0, 255), limit(b + sr.c, 0, 255)
		boxf x, y+cnt, x+w-1, y+cnt
	loop
	color r, g, b
	boxf x, y, x, y+h-1
	boxf x+w-1, y, x+w-1, y+h-1
	boxf x, y+h-1, x+w-1, y+h-1
	return

#global

; ガラス質感 固定テーブル (128)
sr@glsbox = 0,1,7,10,16,21,27,30,36,38,42,42,43,41,42,42,42,41,42,41,41,40,39,38,38,37,36,35,34,33,32,32,30,30,28,28,26,26,24,24,22,22,19,19,17,17,15,16,13,13,11,8,-1,-12,-21,-26,-28,-27,-27,-26,-26,-26,-26,-26,-26,-26,-25,-25,-24,-24,-23,-23,-22,-22,-21,-21,-20,-20,-19,-19,-17,-17,-16,-16,-15,-14,-12,-13,-11,-12,-10,-10,-8,-8,-6,-6,-5,-5,-3,-3,-2,-2,-1,0,1,2,2,3,3,4,5,6,6,7,7,8,8,10,9,11,11,12,12,13,13,14,13,15

; モジュールここまで

glassbox 命令はガラス風のボックスを、stripebox 命令はストライプ状のボックスを描画します。パラメータとして、描画する左上 x, y 座標と、横幅 w、縦幅 h を指定します。描画色は、現在の選択色です。

ガラスの質感 (輝度カーブ) は、サンプリングされた固定データを使って出しています。ダサいというか関数的でないというかアレな方法ですが、それなりに速く描画できます。ストライプの位相は、描画スクリーンの絶対値を基準にしているため、どこに描いても模様がズレることはありません。

上のほうのスクリーンショットの画像は、下記のテストスクリプトの実行結果です。実際に独自 UI に使おうとしたら、もう 1 階層処理をまとめてモジュール化する必要があることでしょう．．．

; (モジュール本体をここにペースト)

	sysfont 17
	redraw 0

	; 背景全体
	color 238, 238, 238
	stripebox 0, 0, 640, 480

	; ボタン領域の背景
	x = 10
	y = 10
	w = 400
	h = 120
	color 192, 192, 192
	stripebox x-1, y, w+2, h
	stripebox x, y-1, w, h+2
	color 224, 224, 224
	stripebox x, y, w, h

	px = x+w/2-40
	py = y+h+10

	color 128, 128, 128
	pos px, py
	mes "ボタンサンプル"

	; カラーボタン見本
	repeat 16
		x = cnt / 4 * 100 + 15
		y = cnt \ 4 * 30 + 15

		; ボタンの周囲の影
		color 192, 192, 192
		stripebox x-1, y, 90+2, 20
		stripebox x, y-1, 90, 20+2

		hsvcolor cnt * 12, 128, 192
		if cnt & 2 {
			glassbox x, y, 90, 20	; グラス
		} else {
			stripebox x, y, 90, 20	; ストライプ
		}
	loop

	; プログレスバー見本
	x = 10
	y = 170
	w = 400
	h = 8
	color 192, 192, 192
	stripebox x-1, y, w+2, h
	stripebox x, y-1, w, h+2
	color 224, 224, 224
	glassbox x, y, w, h

	px = x+w/2-40
	py = y+h+10

	repeat w / 3
		redraw 0

		color 224/3, 224/2, 224
		glassbox x, y, cnt, h

		color 238, 238, 238
		stripebox px, py, 100, 20

		color 128, 128, 128
		pos px, py
		mes "プログレス " + (cnt*100/w) + " %"

		redraw
		await 10
	loop

コード内容についての解説はありません。今回はネタ紹介じゃなくて更新間隔埋めっぽいモジュール紹介でした．．．

マジ万能? マージソート

HSP のコードはインタプリタで走っているので、速度的な制約を感じる場面はよくあります。そういう時は、小手先の高速化テクニックだけでなく、アルゴリズムの改良による処理量の削減が効果的です。今回は、その好例であるソートアルゴリズムについて書いてみます。

ソートアルゴリズムといえば速度ばかりが話題に上ることが多いですが、クイックソートのように速くて、しかも安定 (つまり同値のデータがあれば入力順と同じ順番で出力される) なアルゴリズムに、「マージソート」というものがあります。クイックソートの HSP での実装例はたまに見かけるので、今回は、あまり有名でなさそうな、HSP でのマージソートの実装を紹介します。

[マージソートについての一般的で詳しくて分かりやすい説明は省略ググる]

─というような特徴のあるマージソートですが、このアルゴリズムは再帰を前提として解説されている場合も多く、関数の引数以外に純粋な (スタック型の) ローカル変数を持たない HSP では実装しにくいような印象があります。

が、このアルゴリズムの本質から、再帰を使わない方法で実装することも可能です。HSP でのコードは、下のようになります。

#module

; msort v1 整数配列をソート
; (引数に指定された配列の全要素を単純にソート)
#deffunc msort array ar

	; マージソート

	len = length(ar)	; ソートする配列長
	dim tr, len		; temp arry

	repeat
		; セグメントサイズ定義
		n = 1 << cnt	; マージサイズ
		m = n * 2	; セグメント サイズ

		; 全セグメントに対して
		repeat
			; セグメント 領域定義
			p  = m * cnt			; セグメント開始点
			p1 = p				; パート 1 開始点
			e1 = p1 + n			; パート 1 終了点
			p2 = e1				; パート 2 開始点
			e2 = limit(p2 + n, 0, len)	; パート 2 終了点 (clipping)
			s  = e2 - p1			; セグメント サイズ

			if s <= n : break		; セグメント サイズが閾値以下なら マージしない

			; セグメント内 マージ
			repeat s
				if p2 >= e2 { ; p2 領域外
					tr(cnt) = ar(p1) : p1++
				} else:if p1 >= e1 { ; p1 領域外
					tr(cnt) = ar(p2) : p2++
				} else:if ar(p1) < ar(p2) { ; 比較 & マージ (Core)
					tr(cnt) = ar(p1) : p1++
				} else {
					tr(cnt) = ar(p2) : p2++
				}
			loop

			; マージされた配列をソース配列に貼り付け
			memcpy ar(p), tr, s * 4
		loop

		; ソート 完了
		if n >= len : break
	loop


	return

#global

	; テスト用 乱数数列 作成
	max = 1000
	dim a, max
	repeat max
		a.cnt = rnd(10000)
	loop

	; マージソート
	msort a

	; ソート結果 表示
	repeat max
		mes a.cnt
	loop

このコードは、再帰的に配列を分割していく方式ではなく、配列の部分領域 (上ではセグメントと呼んでいる) をまず最小単位に分割し、それを倍々に拡大しながらマージしていく方式になっています。下の図のように、リーグ表のような構造でマージが繰り返され、一番上で最終的な (ソートされた) 結果が出力されます。この方式のマージソートは、「ボトムアップ型」と呼ばれるらしいです。

比較式部分の不等号の向きを変えれば昇順・降順どちらにでもソートでき、この行の変更だけで文字列配列のインデックスを文字列の大小によってソートすることもできます。

下は、文字列配列のインデックスをソートする例です。(HSP の変てこな文字列比較の書き方に注意 ("a"!"b" = -1, "b"!"a" = 1))

	; ソート基準となる文字列配列
	sdim st, 64, 7
	st = "ABC", "CBR", "RDB", "HOGE", "LED", "CCFL", "GERO"

	repeat length(st)
		ar.cnt = cnt
	loop


	; マージソート

	len = length(ar)	; ソートする配列長
	dim tr, len		; temp arry

	repeat
		; セグメントサイズ定義
		n = 1 << cnt	; マージサイズ
		m = n * 2	; セグメント サイズ

		; 全セグメントに対して
		repeat
			; セグメント 領域定義
			p  = m * cnt			; セグメント開始点
			p1 = p				; パート 1 開始点
			e1 = p1 + n			; パート 1 終了点
			p2 = e1				; パート 2 開始点
			e2 = limit(p2 + n, 0, len)	; パート 2 終了点 (clipping)
			s  = e2 - p1			; セグメント サイズ

			if s <= n : break		; セグメント サイズが閾値以下なら マージしない

			; セグメント内 マージ
			repeat s
				if p2 >= e2 { ; p2 領域外
					tr(cnt) = ar(p1) : p1++
				} else:if p1 >= e1 { ; p1 領域外
					tr(cnt) = ar(p2) : p2++
				} else:if (st(ar(p1)) ! st(ar(p2))) <= 0 { ; 比較 & マージ (strcmp)
					tr(cnt) = ar(p1) : p1++
				} else {
					tr(cnt) = ar(p2) : p2++
				}
			loop

			; マージされた配列をソース配列に貼り付け
			memcpy ar(p), tr, s * 4
		loop

		; ソート 完了
		if n >= len : break
	loop


	; ソート結果 表示
	repeat length(st)
		mes st(ar.cnt) + " (" + ar.cnt + ")"
	loop

マージソートは、その「安定」という性質から、データベースのレコード ID をフィールドごとの優先順位つきで並べ替えるような、わりと高度な用途にも使えます。(これは、クイックソートには無い利点です。)

(もう少しわかりやすい例で言うと、たとえばファイルリストの整列で、「拡張子順」に表示したい場合、

・不安定ソート (クイックソート、ヒープソート、シェルソート ...)
1. まずファイルリストをファイル名でソート
2. 次に、拡張子でソート
→ ソート結果は拡張子でソートはされているけど、同じ拡張子のファイルの並び順はめちゃくちゃ

・安定ソート (マージソート、基数ソート、バブルソート ...)
1. まずファイルリストをファイル名でソート
2. 次に、拡張子でソート
→ ソート結果は拡張子でソートされていて、同じ拡張子のファイルはファイル名でソートされている

─ということになります。用途によっては、不安定ソートでは困ることがあるわけです。)

計算量

一番底のレベルの repeat の繰り返し回数は、log2(len) 回になるので、一番上のレベルのマージループの総繰り返し回数は、len * log2(len) 回となります。よって、原理どおり、このコードの計算量オーダーはおおむね O(N log N) になります。

乱数列でのソート時間を実測すると、配列の長さによらず、再帰で組まれたクイックソートの 90% くらいの速度になるようです。ソートする配列と同じ量のメモリを temp として使用しますが、安定ソートであること、ソート時間が入力データ列に左右されにくいことといった特徴があるため、メリット・デメリットを差し引くと、マージソートが最も汎用性があり使いやすいアルゴリズムではないかと思います。

このように、マージソートは意外と? HSP でも実装しやすく、応用の幅が広いソートアルゴリズムですので、使ってみて損は無いでしょう。

- - -

バブルソート再考

そういえば、配列の要素数が非常に少ない場合は、モダンなソートアルゴリズムよりもシンプルなバブルソートとか挿入法とかのほうがオーバーヘッドが少なく高速になると、どこかで読んだ記憶があります。

そこで、下のような単純なバブルソートコードに乱数列を入力して、要素数によってマージソートとの速度差がどのように変化するか、実測してみました。

(こういうくだらない実験て、ふらっとやりたくなるものです。)

#deffunc busort array ar

	; 一般的なバブルソート
	len = length(ar)
	repeat len
		repeat len - cnt - 1
			if ar(cnt) > ar(cnt+1) {
				ar(cnt) ^= ar(cnt+1)
				ar(cnt+1) ^= ar(cnt)
				ar(cnt) ^= ar(cnt+1)
			}
		loop
	loop

	return

テスト結果は、下の表のようになりました。(テスト環境 : Pentium 4 2.6CGHz)

(余談ですが、マージソートを HSPLet 3 で実行してみたら、HSP 3 インタープリタ時の 2.5 倍くらい高速でした。)

条件		処理時間 [ms]		時間比 (busort : msort)
要素数	実行回数	バブル	マージ	時間比 (busort : msort)
10	10000	703	876	0.803 : 1
100	1000	6672	1250	5.33 : 1
1000	100	66657	1671	39.9 : 1
10000	10	670000	2188	306 : 1
100000	1	-	2578	- (2600 程度?)

見た目がシンプルなバブルソートにも少しは期待していたのですが、バブルソートのほうが速いケースは、要素数わずか 12～13 あたりまででした。バブルソートのほうが速い領域でも、その速度差はわずかしかありません。当然ながら、要素数が多くなっていくと、バブルソートとマージソートの速度差は急速に開いていきます。

要素数が 10 程度と決まっている状況なら、バブルソートを使う価値も十分にあるようですが、それ以上の要素数のソートで速度も要求されるような場合は、バブルソートに小手先の改良を加えたりしないで、用途に適した他のアルゴリズムを使用すべきでしょう。

ちなみに、正の整数とか、最大バイト数が 16 バイト程度と決まっている文字列とかの場合は、ここで紹介したマージソートよりも基数ソートのほうが速くなると思います。基数ソートは、基数のとり方によってはメモリを非常に消費しますが、比較処理を行わないソート方法のため (基数のとり方にもよりますが) 非常に高速です。これも、安定なソート方法です。

マウスの戻る・進むボタンの入力を取得する

5 ボタンマウスについている、「戻る・進む」といったボタンの入力を HSP から取得したいと思ったことはありませんか?

このボタンの付いていないマウスを使っているユーザーにはもしかしたらピンと来ないかもしれませんが、このボタンは Web ブラウジング時に無いと困るくらい便利なボタンです。自作アプリにも使わない手はありません。

HSP 2.x の頃は標準命令でこれを実現することはできませんでしたが、HSP 3.0 からは、oncmd 命令でウィンドウメッセージ WM_APPCOMMAND (= 0x0319) を捕まえれば楽に対応することができます。

	oncmd gosub *proc_WM_APPCOMMAND, 0x0319

	stop

*proc_WM_APPCOMMAND

	; コマンドの種別は GET_APPCOMMAND_LPARAM(lParam) で知る
	cmd = lparam >> 16 & 0x7fff ; == GET_APPCOMMAND_LPARAM(lParam)

	; 押されたボタンの種類を見る
	mes strf("0x%x", cmd)

	return 0

WM_APPCOMMAND は、マウスの拡張ボタンの他にも、「インターネットボタン」や「メディアボタン」といったいらんボタンのついたキーボードや、Windows MCE 用リモコンのボタンにも対応しています。もしそういうデバイスを持っていたら、いろいろ押して試してみてください。

WM_APPCOMMAND メッセージを受けて何らかの処理を行った場合は、return 0 で抜けてください。逆に、未対応のボタンが押された場合など、何もしなかった場合は単に return だけで抜けます。戻り値なしの return で抜けた場合は、OS のデフォルトのボタン処理が行われます。(メールボタンならメーラーの起動、ホームページボタンならブラウザの起動などが行われます)

WM_APPCOMMAND メッセージは、Windows Me / 2000 からサポートされています。

- - -

参考までに、WM_APPCOMMAND 以外に WM_XBUTTONDOWN (0x020B), WM_XBUTTONUP (0x020C) メッセージでもマウスの拡張ボタンの入力を知ることができます。このメッセージは、それぞれボタンの押し下げ、押し上げのタイミングで呼ばれます。

	oncmd gosub *proc_WM_XBUTTONDOWN, 0x020B
	oncmd gosub *proc_WM_XBUTTONUP, 0x020C

	stop

*proc_WM_XBUTTONDOWN
*proc_WM_XBUTTONUP

	; 押されたボタンの種類を見る
	mes strf("0x%x", wparam)

	return

しかし、マウスポインタが button 等のウィンドウオブジェクトの上にある時は、WM_XBUTTONDOWN, WM_XBUTTONUP メッセージは送られて来ないので、おそらく使い勝手は良くないでしょう。WM_APPCOMMAND なら、その心配は無いみたいです。