2013年03月13日

高速で質もよい疑似乱数生成アルゴリズム xorshift(xor128)

こんにちは、タマキです。

さて、今回は擬似乱数生成アルゴリズムの話を。

乱数生成といえば、『メルセンヌ・ツイスタ(MT)』がよく使われているだろうと思います。
(MT : http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/mt.html)

MT系なのですが、MTよりも高速でよりよい均等分布特性を持つ『SFMT』も発表されていますので、こちらを利用する方も多そうですね。
(SFMT : http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index-jp.html)

WELL』という実装もあります。
(WELL : http://www.iro.umontreal.ca/~panneton/WELLRNG.html)

***

また、高速で品質も高いランダムの生成に『xorshift』があります。
(xorshift : http://www.jstatsoft.org/v08/i14/paper。Marsaglia (July 2003). “Xorshift RNGs”)

実装は、XORとビットシフトだけ


unsigned long xor128() {
static unsigned long x=123456789, y=362436069, z=521288629, w=88675123;
unsigned long t=(xˆ(x<<11));
x=y; y=z; z=w;
return ( w=(wˆ(w>>19))ˆ(tˆ(t>>8)) );
}

(ちなみに、このマジックナンバー 123456789 を不思議に思った方もいると思いますが、これは超越数の一部を抜粋したものになります。ふざけているわけではないのですわーい(嬉しい顔))

見ただけでも、MTより速そうだな、という印象ですよね。
内部状態が非常に少ないのも使い勝手が良さそうですしね。

周期も2^128-1とのことなので、実用的にも十分かなと思います(MTは2^19937-1)。

***

今回のランダムだけでなく、用途や仕様に合った手法や実装を選択するためにも、いろんな調査をし、準備ができていれば安心ですよね。

せめて、存在を知っておくということだけでも大切かなと思います。
いつでも検証でき、とりあえず選択肢になるという意味でも。

2010-10-14-0.png

追記<2013.03.14>

公開後、いろんな方から「xorshiftのseed setはどうすればいいの?」といった問い合わせが個人宛てにありましたので、その辺を追記します。

基本的には、論文の6ページ目に「全て0の場合を除いて、何を設定してもいい」とあります。

そのあたりの実装をいろいろ見てみると、
・zやwの部分などをランダムに設定する
・一つのseed setから、x,y,z,wを生成
といったパターンが多いですね。

参考までにサンプルを。

・zやwの部分などをランダムに設定する

static unsigned long x=123456789, y=362436069, z=521288629, w=88675123;

void init_xor128(unsigned long s) {
z ^= s;
z ^= z >> 21; z ^= z << 35; z ^= z >> 4;
z *= 2685821657736338717LL;
}

unsigned long xor128() {
unsigned long t=(xˆ(x<<11));
x=y; y=z; z=w;
return ( w=(wˆ(w>>19))ˆ(tˆ(t>>8)) );
}


・一つのseed setから、x,y,z,wを生成

static unsigned long seed[4]={ 123456789, 362436069, 521288629, 88675123 };

void init_xor128(unsigned long s) {
for (unsigned long i=0; i<4; ++i) seed[i]=s=1812433253U*(s^(s>>30))+i;
}

unsigned long xor128() {
unsigned long *a=seed;
unsigned long t=(a[0]^(a[0]<<11));
a[0]=a[1]; a[1]=a[2]; a[2]=a[3];
return ( a[3]=(a[3]^(a[3]>>19))^(t^(t>>8)) );
}


posted by 管理人 at 16:24 | プログラミング

2013年01月21日

Luaがさらに高速に

おひさしぶりです。タマキです。


Luaは、ゲームでは、World of Warcraftを始め、ファイナルファンタジーXIV、Far Cry、アイドルマスター2などでも利用されてるスクリプト言語になります。

その軽量さや実績などから、ルータなどの組み込み機器にも導入されるようになりました。

また、いろんな改善もなされています。
その一つをご紹介。

少し前の記事になりますが、"LuaJIT gets allocation sinking; Complex numbers on par with C; Better than java"にもあるように、短寿命のアグリゲートを再利用することで数十倍速くなったとのことです。
(低レベルの小さいデータの場合はCに近い速度にもなる、と)

これはゲーム開発での利用に、うれしい最適化ですね。


また、4年ほど前に紹介させていただきました(私も少し関わらせていただきました)Luaの本ですが、新訂版として発売されましたので、興味がありましたら是非に。


20130121_LuaBook-thumbnail.jpg




Squirrelの記事もありますので、スクリプト言語の導入の一助となればと思います。

posted by 管理人 at 16:39 | プログラミング

2012年12月17日

Squirrel

はじめまして!
今月より正社員となりました 店長 です。

ゲームプログラマとしてはおよそ7年の経験がありますが、
ヘキサドライブの皆についていくために、
ますます力を入れて頑張っております手(グー)



さて、そんな私が最近勉強したスクリプト言語
Squirrel
について書いていきます。

まずこの言語に着目した理由ですが、
ゲーム開発をしていくと、管理のため、ビルド時間の短縮のため、などの事情で、
色々なパラメータなどをソースコード外に置いて管理することが増えていきますが、
たまにソースコードの一部をまるごと外に置きたいことがあります。


・シューティングのボスの複雑な動き
・ゲームエンジンのUI拡張部分
・頻繁に調整が入るNPCの動き

大規模なゲーム開発になると、ビルド時間が開発時間を大幅に消耗していくこともあるため、
できるだけそういう時間を減らしたいと思っていました。
そこで、実行中に一部分だけを逐次コンパイルしやすい言語を使ってみようと思ったわけです。

特にSquirrelは手続き型言語、オブジェクト指向言語、関数型言語、データ駆動
などの特性を併せ持つ
というゲームで利用しやすい面もあります。

サンプルとして作ったコンソールアプリのソースコードを掲載いたします。
C++で定義したクラスをSquirrelで使用する方法
Squirrelで定義したクラスをC++で使用する方法

のサンプルです。

実行後Cキーで逐次Squirrelのファイルがコンパイルされ、実行されます。

#include "stdafx.h"
#include <sqrat.h> // squirrel.h もインクルードされる
#include <sqstdaux.h> // sqstd_seterrorhandlers

#include <stdio.h>
#include <stdarg.h>
#include <Windows.h>

// 文字列出力
static void printfunc(HSQUIRRELVM vm, const SQChar* format, ...)
{
va_list args;
va_start(args, format);
#ifdef SQUNICODE
vwprintf(format, args);
#else
vprintf(format, args);
#endif
va_end(args);
}

// 敵クラス
class Enemy
{
public:
void up(){ printf("%sが上へ移動\n", m_name); }
void down(){ printf("%sが下へ移動\n", m_name); }
void left(){ printf("%sが左へ移動\n", m_name); }
void right(){ printf("%sが右へ移動\n", m_name); }
void shot(){ printf("%sが弾を発射\n", m_name); }
void name(){ printf("名前 %s\n", m_name); }
public:
int m_hp;
char* m_name;
};

// 数値出力関数
void printNum(int n)
{
printf("num = %d\n", n);
}


// テーブルへのバインド
void bindMyTable(HSQUIRRELVM vm)
{
using namespace Sqrat;

// テーブルを作成
Table myTable(vm);

// Enemy オブジェクトを作成
Class<Enemy> enemy(vm);

// Enemy オブジェクトにバインド
// メンバ関数のバインド
enemy.Func(_SC("up"), &Enemy::up);
enemy.Func(_SC("down"), &Enemy::down);
enemy.Func(_SC("left"), &Enemy::left);
enemy.Func(_SC("right"), &Enemy::right);
enemy.Func(_SC("shot"), &Enemy::shot);
enemy.Func(_SC("name"), &Enemy::name);

// メンバ変数のバインド
enemy.Var(_SC("m_hp"), &Enemy::m_hp);
enemy.Var(_SC("m_name"), &Enemy::m_name);

// ルートテーブルに enemy を "Enemy" としてバインド
RootTable(vm).Bind(_SC("Enemy"), enemy);
RootTable(vm).Func(_SC("printNum"), &printNum);
}


// メイン
int main(int argc, char** argv)
{
// Sqratの名前空間
using namespace Sqrat;

// VMの作成
HSQUIRRELVM vm = sq_open(1024);

// エラーハンドラを設定
sqstd_seterrorhandlers(vm);

// 文字列出力関数を設定
sq_setprintfunc(vm, printfunc,printfunc);

// 標準で使うVMの設定
DefaultVM::Set(vm);

// C++からSquirrelへのバインド
bindMyTable(vm);


printf("---manual---\n");
printf("Q = Exit\n");
printf("C = Compile Start\n\n");


// ここからスクリプトのコンパイルと実行
{
Script script;
// Qで終了
// Cでコンパイル
while( !::GetAsyncKeyState( 'Q' ) )
{
// コンパイル
if( ::GetAsyncKeyState( 'C' ) & 0x01 )
{
// C++ 定義のクラスをSquirrelから扱う
printf("\n--- Compile Squirrel Start---\n");
script.CompileFile("enemy.nut");
script.Run();

script.CompileFile("enemySquirrel.nut");
script.Run();

// Squirrel 側で定義したクラスを C++ 内部で扱う
// enemy2 <- EnemySquirrel("敵2");
Object objValClass = RootTable(vm).GetSlot(_SC("enemy2"));
if( !objValClass.IsNull() )
{
/// メンバ変数へのアクセス
Object name = objValClass.GetSlot(_SC("name"));
if( !name.IsNull() )
{
// 文字型にキャスト
Sqrat::string name_str = name.Cast<Sqrat::string>();
printf("name = %s\n",name_str.c_str());
}

/// メンバ関数へのアクセス
Function func = Function(objValClass,_SC("printName"));
if( !func.IsNull() )
{
func.Execute();
}
}
}
}
}


// VMを解放
sq_close(vm);

return 0;
}

SquirrelのコンパイラはC++のライブラリとしてリンクしております。
また、バインダにSqratを利用しております。


Squirrelのファイルとして
enemy.nut
enemySquirrel.nut

を用意します。

enemy.nutの中身は単純に各関数の実行確認と名前の設定です。

local inst = Enemy();
inst.m_hp = 2;
inst.m_name = "敵1";

inst.name();

inst.shot();
inst.up();
inst.down();
inst.left();
inst.right();
inst.shot();

enemySquirrel.nutの中身はクラスの定義と
そのインスタンスを作ってます。

// Squirrel 内部で定義した敵クラス
class EnemySquirrel
{
constructor(v)
{
name = v;
}

function printName()
{
print(name + "(.nut内の関数)\n");
}

name = null;
}

// ルートテーブルに敵2設定
enemy2 <- EnemySquirrel("敵2(.nut内部)");

順を追って解説をしていきます。

初めにSquirrelのコンパイラなどはvirtual machine上で動くため
その生成と利用するための設定を行なっております。

次にbindMyTable関数の中で
C++ 内部で定義したクラスをSquirrelで使用する準備をしております。
Squirrelは、テーブルとスロットという機能があり、
そこに変数やクラス、関数を設定していきます。

SqratのScriptクラスを使ってコンパイル実行することができます。

Script script;

// C++ 定義のクラスをSquirrelから扱う
printf("\n--- Compile Squirrel Start---\n");
script.CompileFile("enemy.nut");
script.Run();


これでC++で定義した機能をSquirrelで呼び出すことができました。
一つの機能だけを外に置いておきたい場合などはこれだけでも利用ができます。

ただし、もっと複雑なことをしたい時は、
Squirrel側でクラスを定義してC++側で利用したいこともあるはずです。

その時は、Squirrelのファイルをコンパイル、実行した後、
C++で利用します。


script.CompileFile("enemySquirrel.nut");
script.Run();

// Squirrel 側で定義したクラスを C++ 内部で扱う

// enemy2 <- EnemySquirrel("敵2");
Object objValClass = RootTable(vm).GetSlot(_SC("enemy2"));
if( !objValClass.IsNull() )
{
/// メンバ変数へのアクセス
Object name = objValClass.GetSlot(_SC("name"));
if( !name.IsNull() )
{
// 文字型にキャスト
Sqrat::string name_str = name.Cast<Sqrat::string>();
printf("name = %s\n",name_str.c_str());
}

/// メンバ関数へのアクセス
Function func = Function(objValClass,_SC("printName"));
if( !func.IsNull() )
{
func.Execute();
}
}

これでSquirrel側で定義したクラスをC++で実行することができるようになりました。
初期化、毎フレームの処理、終了処理などの関数名を事前に決めておき、
その処理をSquirrel側で書いてC++で利用すればクラスの機能に修正が入っても
長いビルド時間など待たずに修正と実行が可能となります。


Squirrelが実際のゲームに使用された例として
ファイナルファンタジー・クリスタルクロニクルが上げられます。
また、多くのゲームエンジンにこういったスクリプト言語が組み込んであり、
修正と実行のサイクルが素早く行えるようになっております。

是非、Squirrelの面白さに皆さんも触れてくださいわーい(嬉しい顔)

Squirrel
Sqrat
ライセンスは MIT licence となります。

今回のサンプルが動かせる実行ファイルを置いておきます。
細かいエラー処理は行なっておりませんがご了承ください。
SquirrelTest



posted by 管理人 at 16:18 | プログラミング

2012年11月26日

WebGL(中身入り)

気が付いたらもう冬雪が傍までやってきていますね。
ハートは冬にも負けずにホットです。
とてもお久しぶりです。
GoodSun晴れ!こと山口です。

ご無沙汰していましたが、今回こそWebGLネタをやってみました。
何か面白そうなネタは無いかなと考えてみた結果、RayTraceでもやってみようと思い至りました。
RayTraceをやるにしても普通にやったのでは面白くない!
という事で今回は古典的ではありますがRayMarchingに挑戦してみました。

みなさん色々と凄い事をやっている為、
プログラムのソースコードを書くようなblogは毎回恐縮の極みですふらふら


さて、このRayMarchingというのはボリュームレンダリング等に利用される技法でして、
一言で言い表すなら"力技"といった感じで個人的に大好きな技法の一つです。

雲のような3次元ボリュームデータをレンダリングする時がイメージしやすいのですが、
場所によって密度や色が違う情報に対して少しずつレイを進ませながら密度や色を収集して、
最終的な色味を決定します。
まさに積分を力技で表現している直観的な技法ではないでしょうか?

簡単な図解。
20121126_raymarching.png

解説よりも動いているものを見てもらうのが一番かと思います。
デモ兼ソースコードはこちらから。(ソースコードはリンク先をファイルとして保存したり、開いたページのソース表示を行って下さい。)
※今回のサンプルはMacOSX(Lion)とWindows7のGoogle Chromeにて動作確認を行っています。
残念ながらOperaでは動きませんでした。今度はきっとOperaでも動くものを目指そうと思います。
※GPUに多大な負担がかかる為、環境によっては動作が非常に遅い可能性があります。

ボックスのシェーダにRayMarchingするシェーダを適応していて、
ヒットした面から視線方向に順次レイを進めていきます。
そのため、通常は表面の表現を行うシェーダはボックスの内部を表現する振る舞いになっています。

少し怪しいところがありますが...まぁ概ね期待通りの結果です。
かなり重いシェーダも動かす事が出来て驚きです。
今更ながらRayTraceアピールという事で床を作って反射やればよかったと思っています。

この手法を利用すれば床面に広がるドライアイスの煙とかをよりいい感じに表現出来るかもしれません。
(処理が重すぎる為現実的ではないですが...)

今回のサンプルではオープンソースの以下のライブラリを利用させて頂きました。
ぴかぴか(新しい)glMatrix(ジオメトリ計算 https://github.com/toji/gl-matrix ※今回はhttp://code.google.com/p/glmatrix/ こちらを使用)
ぴかぴか(新しい)webgl-noise(ノイズ https://github.com/ashima/webgl-noise )
先人様ありがとうございます。

これからもJavaScriptの面白さを皆さんにお伝えしていこうと思います。
(今回は直接的にJavaScript全く関係なかったですけど)
では、本日はこの辺で手(パー)

posted by 管理人 at 17:22 | プログラミング

2012年11月19日

ホーミングミサイル

こんばんは、平尾です!わーい(嬉しい顔)
最近寒かったのでコタツを設置、早速居眠りして変な汗をかきました…ふらふら
コタツは心地良いですが風邪をひかないように要注意ですね!

2010-10-14-0.png


今日はホーミングミサイルの実装方法について説明したいと思います。
といっても考え方は非常にシンプルですひらめき

1自分の向いている方向とターゲットの方向を取得
2自分の向いている方向からターゲットまでの角度(差分)を取得
3ターゲットへ回したい角度だけ回す

といった感じです。
C#(Unity上)で実装したソースはこちらになりますメモ


using UnityEngine;
using System.Collections;

public class Bullet : MonoBehaviour
{
private GameObject _target = null; // ロックオンしたターゲット
private float _speed = 6.0f; // 1秒間に進む距離
private float _rotSpeed = 180.0f; // 1秒間に回転する角度

public GameObject Target
{
set { _target = value; }
get { return _target; }
}

// Update is called once per frame
void Update()
{
if (_target == null)
{
return;
}

// ターゲットまでの角度を取得
Vector3 vecTarget = _target.transform.position - transform.position; // ターゲットへのベクトル
Vector3 vecForward = transform.TransformDirection(Vector3.forward); // 弾の正面ベクトル
float angleDiff = Vector3.Angle(vecForward, vecTarget); // ターゲットまでの角度
float angleAdd = (_rotSpeed * Time.deltaTime); // 回転角
Quaternion rotTarget = Quaternion.LookRotation(vecTarget); // ターゲットへ向けるクォータニオン
if (angleDiff <= angleAdd)
{
// ターゲットが回転角以内なら完全にターゲットの方を向く
transform.rotation = rotTarget;
}
else
{
// ターゲットが回転角の外なら、指定角度だけターゲットに向ける
float t = (angleAdd / angleDiff);
transform.rotation = Quaternion.Slerp(transform.rotation, rotTarget, t);
}

// 前進
transform.position += transform.TransformDirection(Vector3.forward) * _speed * Time.deltaTime;
}
}


このソースで肝になるのは、指定角度だけ向けるところでしょうか。
ターゲットまでの残り角度を求め、指定角度が残り角度の何%か(t=0.0f〜1.0f)を求めます。
何%かを計算したら、Quaternion.Slerp() で現在の向きからターゲット方向への補間を行い、
最終的な向きを求めています右斜め上

簡単ではありますが、Web上で実行出来るものをアップしました
画面クリックで弾を発射するだけのプログラムです。
(※実行には別途 Unity WebPlayer のインストールが必要になりますのでご注意下さい。)


角度を扱うにはクォータニオンexclamation
とても便利なので是非覚えていって下さいわーい(嬉しい顔)ぴかぴか(新しい)

posted by 管理人 at 22:09 | プログラミング

2012年11月13日

C#の便利なクラス紹介 その1

おひさしぶりです。 みやじーです。

最近C#でツールの作成をしている際に、
20Gバイト程度のファイルを扱う必要が出てきてしまい、
一度にメモリには載らないので困っていたのですが・・・

"メモリマップドファイル"というものを耳にしたので調べてみましたぴかぴか(新しい)

System.IO.MemoryMappedFiles名前空間にある
"MemoryMappedFile"というクラスが非常に便利ですexclamation×2

このクラスは、メモリ上にファイルをマッピングして扱うことができます。
シーク処理などは、クラス内部で隠ぺいしてくれているため、
非常に簡単にデータを取り扱うことが可能です。
一度にメモリに載らないファイルもこれで簡単に扱えます手(チョキ)


(使用例)

string fileName = "test.dat"
using (var memoryMappedFile = MemoryMappedFile.CreateFromFile(fileName))
{
using (var viewAccessor = memoryMappedFile.CreateViewAccessor())
{
// 100000byte目に書き込む
byte val = 100;
viewAccessor.Write(100000, val);

  // 100000byte目から読み込む
val = viewAccessor.ReadByte(100000);
}
}


詳しくは
http://msdn.microsoft.com/ja-jp/library/vstudio/dd267544.aspx

同様の機能のクラスを自作しようとしていたのですが、
こちらを使用して事なきを得ました。

また、プロセス間で情報を共有する手段としても使えるので、
こちらの用途でもお世話になりそうですあせあせ(飛び散る汗)

非常に便利なクラスなのでぜひ使用してみて下さい手(グー)











posted by 管理人 at 21:33 | プログラミング

2012年10月26日

VisualStudioコマンドを検索ボックスで実行する方法

こんにちは。イノウエです。

もう少しで、ヘキサドライブ東京開発が出来てから3年になります。
長い時間が経ったような、あっという間だったような、不思議な感覚です。
いくつかのプロジェクトに関わり、社員も倍以上に増え、
自分も会社も大きくなっていっていると実感できています。
これからも、グングン伸びていけるように頑張りますグッド(上向き矢印)


さて、今日は、VisualStudioのちょっとした便利機能を紹介します。
本当にちょっとした事なので、すぐ覚えられると思いまするんるん

やる事は
「VisualStudioコマンドを、検索ボックスで実行する」
というだけですいい気分(温泉)

例)
1、Ctrl+Dを入力して検索ボックスにフォーカス
2、「>of ファイル名」で、指定したファイルをオープン

たったこれだけです。

"of"は、"File.OpenFile"のエイリアスです。

ファイル名の途中が曖昧でも、ソリューションに含まれるファイルの中から
補完して検索出来るので、すぐに見つける事が可能です。

フォルダを複数に分けてソースを管理している場合、
ソリューションエクスプローラーから該当ファイルを探したり、
Ctrl+Oで開くウィンドウからフォルダジャンプして該当ファイルを探したりだと、
なかなか見つからなかったり手間がかかりますが、"of"を使うと一瞬です。
(ファイル名を全く覚えていなかったら…もうやだ〜(悲しい顔)

他にもコマンドは色々ありますが、
これら機能について詳しく知りたい方は、
下記のヘルプをご参照ください。

http://msdn.microsoft.com/ja-jp/library/1665hyw1%28v=vs.100%29.aspx
http://msdn.microsoft.com/ja-jp/library/c3a0kd3x%28v=vs.100%29.aspx


便利な機能を使って、快適なVisualStudioライフを送りましょうぴかぴか(新しい)


posted by 管理人 at 10:59 | プログラミング

2012年08月20日

VisualStudio2010 Tips

おはようございます。平尾ですわーい(嬉しい顔)
最近関西ではゲリラ豪雨に見舞われることがちょこちょこあり、
携帯している折りたたみの傘では歯が立たないこともしばしば台風
突然すぎて対応仕切れないときもあるかと思いますが、みなさんお気を付けください。

2010-10-14-0.png


本日は Visual Studio 2010 のtipsを3つ紹介したいと思います。
1.VC++ディレクトリの設定方法
2.ツールバーの長さ変更方法
3.矩形選択時の文字入力


1.VC++ディレクトリの設定方法
VS2008には「オプション」→「VC++ディレクトリ」でインクルードパスの設定などを行う事ができました。
ところがVS2010ではできませんがく〜(落胆した顔)
    ↓
  20120820_d00.png

良く読むとユーザープロパティーシートから設定できるとのことなので、そのやり方を紹介します。
まずは、プロパティーマネージャを開きます。
  20120820_d01.png

Debug | Win32 などがありますが、どれでも良いので開き、
Microsoft.Cpp.Win32.userをダブルクリック。
  20120820_d02.png


するとプロパティの中に「VC++ディレクトリ」が!
  20120820_d03.png
設定し放題ですexclamationexclamation


2.ツールバーの長さ変更方法
VS2008でもツールバーを伸ばすのは一手間いりましたが、
VS2010ではやり方が変わってました。

個人的にはソリューション構成のバーは長めにしておきたいのです!
  20120820_t00.png

というわけでツールバー横の空欄を右クリックしましょう。
  20120820_t01.png

メニューの一番下に「カスタマイズ」という項目があります。
(あまりに長いので図では割愛しています)
  20120820_t02.png

カスタマイズを開くと、いろいろ設定できるところがありますが、
下図を参考に選択していってください。
  20120820_t03.png

すると目当ての「ソリューション構成」が出てきましたので、ボタンを編集!
今回は幅を数値入力する形になっているので、
お好みの長さになるまで数値を編集して下さいメモ
  20120820_t04.png
スッキリですぴかぴか(新しい)



3.矩形選択時の文字入力
VSでは「ALT + SHIFT + 矢印キー」で矩形選択ができます。
以前マイキーも紹介していました
評判の矩形選択ですが、VS2010では矩形選択中にも文字入力ができます!

こういう状態から↓
  20120820_b00.png

ALT + SHIFT + ↓ キーで矩形選択をすると、うっすら縦のラインが出ます。
(矩形というかライン選択?)
  20120820_b01.png

そこで文字を入力すると、選択した領域に文字を入力できます!
  20120820_b02.png
使う頻度はそんなに無いかも知れませんが、覚えておくとどこかで使える日がくるかもしれませんひらめき


2010-10-14-0.png


こんなふうに開発中にひっかかったりして調べたものは、
きっと他の人も同じように検索してると思いますのでサーチ(調べる)
出来るだけ情報を共有できればと思いました目

今後もいろいろ見つけたらお知らせしたいと思いまするんるん

posted by 管理人 at 09:00 | プログラミング

2012年07月26日

メモリイメージ再び

晴れ夏です!
毎日暑い日が続きますねあせあせ(飛び散る汗)
完全にタンクトップ化してしまった「オクダ」です。

今日は前回の「メモリイメージ」の続きでメモリについて更に深く掘り下げていきます。

前回、4スタック
に関しては存在を紹介しただけでサラッと流してしまいました。
まずは「スタック」とはどういうモノなのか掘り下げていきましょう。

スタックをウィキペディアで調べてみましょう。
説明が多岐にわたっていて難しいかもしれません。

重要なのは「後入れ先出し」という事と、そのイメージになります。
買ってきた本をどんどん積み上げていって、読む時は上から順番に取り出します。
途中や下から抜き出すような事をしません。

プログラムにおけるスタックも同じでメモリの最後のほうから順に積み上げていき、
新しい物から取り出します。
この動作を push - pop と言います。

様々なデータを扱う時に使用されるデータ構造ですが、プログラムの根幹部分でもこの仕組みを使用しています。
あまりにも使用頻度が高いのでCPUでハードウェア的にサポートしているくらいです。
どこで使われるかと言うと「関数呼び出し」です。

ほとんどのプログラミング言語では関数呼び出しがあります。
呼び出された関数の中で更に関数を呼び出し、そこから更に関数を呼び出し、更に関数、、、、
と言った具合にプログラムしていると思います。
視点を変えると、
ある関数を処理していたら関数呼び出しがあるのでその関数にジャンプして、その関数内で更にジャンプして、、、、
と言う事になります。
そして、関数の最後やreturn命令まで辿り着くと呼び出し元へ戻っていきます。
このような動作を繰り返してプログラムが動いています。

さて、関数をどんどん渡り歩いていくわけですが、戻り先を憶えておかないと迷子になってしまいますよね。ふらふら
そこで登場するのが「スタック」です。
関数にジャンプする時に戻り先をスタックに積みます。
どんどんジャンプしてもどんどん積んでいきます。
戻る時はスタックから取り出せば戻り先がわかります。
どこまで深く潜っても出たり入ったりしてもスタックを頼りに元の場所に戻ってくる事が出来ます。
イメージできますか?

スタックには戻り先と一緒に様々な情報を積んでいきます。
CPUのレジスタ(CPUで使用する変数のようなモノ)は有限なので
今の関数で使用しているレジスタの状態をスタックに保存しておいて、ジャンプして戻ってきた時に復元しています。

ローカル変数もスタックから確保します。
情報を積み上げるモノだと説明したので少し変な感じがするかもしれません。
もう少し詳しく説明しましょう。

ジャンプする時にスタックに戻り先を積むと説明しましたが、関数にジャンプしてきてすぐにローカル変数をスタックに積みます。
その領域を変数のメモリとして使用します。
配列なども、そのメモリサイズ分スタックに積みます。(スタックから確保します)
モチロン、関数を抜ける時にはスタックから取り出します(領域を破棄します)

場合によりますが、関数の引数もスタックを経由して受け渡される事もあります。

ちっ(怒った顔)
イロイロいっぱい書いてきたので難しくなってきましたね。
細かい事はともかく、スタックには戻り先やローカル変数が積まれるという事が重要です。
このローカル変数には配列も含まれます。
配列外にアクセスしたらどうなりますか?がく〜(落胆した顔)
関数の呼び出し元や少し前に呼び出した関数でスタックした情報の残骸が今のスタックの前後にあります。
変数や配列を未初期化の状態で使用したり、配列外の情報を読み出した場合にはスタックの状態に依存した情報にアクセスする事になります。
読み出しはともかく、書き込みをするとどうなるか、、、、がく〜(落胆した顔)
戻り先を書き換えた時には何が起こっても不思議ではないです。

関数の呼び出し順番や、途中に無意味な関数を追加しただけで動作が変わるようなバグは
このような状態で作りだされる事がよくあります。
何も表示しない print を追加すると動作が変わったりするバグに遭遇した事ないですか?

ローカル変数のアドレスを憶えておいてその内容を後で参照したらどうなるでしょう?
ローカル変数の内容やアドレスが有効な期間もイメージできたと思います。
関数を再帰呼び出しした時のローカル変数はどのようにして確保されているかなど
スタックの仕組みとメモリを理解する事で動作のイメージがわかってくると思います。

思わぬ動作をするバグに遭遇したらスタックも疑ってみてください。
風が吹けば桶屋が儲かるように、ソースコードからは想像できない仕組みでバグが産み出されている事があります。

今回は少しややこしい話をしました。
基本的な事でありながらあまり知られていない事だと思います。
スタックの知識があるだけでプログラミングやデバッグのスキルがワンランクアップしますよ!ぴかぴか(新しい)


posted by 管理人 at 23:17 | プログラミング

2012年06月19日

C言語のあいまいさ

もうすぐ台風台風4号が上陸してきそうな中、このブログを書いているコンドウです。
ご無沙汰しております。

台風台風が間もなく近づいてくるという事で会社も早めの電車帰宅を促しておりますが、
そろそろ撤退しなければと考えていますダッシュ(走り出すさま)

今日はいいネタが思い浮かばなかったのでC言語のあいまいさについて
お話しようかと思います。

C言語(C++含む)を何年も実務や趣味でやっていると「あれexclamation&question」って思う挙動に
出くわす事ってないですか? 私はよくあります。
例えば、前の開発の事例で説明しますと、


unsigned int getBit(unsigned int& data,unsigned int shift)
{
unsigned int result = data & ((1<<shift)-1);
data>>=shift;
return result;
}


上の関数は引数dataから指定したbit分の数値を返すbit圧縮の展開などで
使われる関数ですが、これまずいところがあります。お判りでしょうか?

もう1つの例です。以前ブログでも紹介しました浮動小数点で紹介したプログラムです。


#define FRAC_LEN 23

union FLOATING_VALUE{
float FloatValue;
struct {
unsigned int Fraction:FRAC_LEN;
unsigned int Exp:31-FRAC_LEN;
unsigned int Sign:1;
}s;
};


これもよく見るとまずい使い方をしています。


ではまずい箇所を説明します。最初の関数は

data>>=shift;

がまずい部分です。int型の幅は処理系依存になるのですがここでは32bitとして考えます。
もし、shiftが32以上だった場合、dataの値が処理系によって不定になるのです。
なぜかというとC言語の定義に無いコーディングとなるからです。C言語で保障されている
シフトはその変数の幅未満までで、幅以上のシフトは言語的に動作不定となります。
実際、上記のコードはPowerPCやMIPS系のプロセッサでは問題無かったのですが、x86系は
異なった結果になりました。x86の場合はシフト命令はカウンタ値が5bitでマスクされてから
処理されるので例えばshift=32だったら、shift=0になって処理してしまうので期待した結果
になりませんでした。(data>>=shiftより、1行上の処理も当然まずいですが。。)
シフト処理はかなり未定義なところが多く、右シフトの動作は
算術シフト(空いたbitは最上位bitで埋まる)論理シフト(空いたbitは0で埋まる)どちらになる
かはC言語の規格には明確に定義されていません。処理系に依存するという事です。


もう1つの例のまずい箇所は色々あります。1番まずいところは「ビットフィールドの値は
何か変数と共有してはいけない」
というところです。では何がいけないというと

・float FloatValueはどのようにメモリに格納されるのか(ビッグエンディアン/リトルエンディアン)
・ビットフィールドが上位bitから割り当てられるのか、下位bitから割り当てられるのか

ビットフィールドのビットが上位か下位かどちらか割り当てるのかは処理系依存しています。
私の経験上からはビッグエンディアンの処理系では上位から、リトルエンディアンの処理系では
下位から割り当てられているようですが、これも確実ではありません。
よって浮動小数点のブログでは注意書きも入れていたかと思いますが、Windows上(x86系)での
動作に限られます。ビットの順序を重要視するようなコードの場合は面倒でもシフト演算子を
使って自作する事が賢明でしょう。

他にもネットでC言語の未定義動作を検索してみるといくつか知る事ができます。

その点、後発のJavaは未定義部分がほぼ無いといわれています。即ち、処理系に依存するような
コードにはならないという事ですね。どちらがいいか結論付けるのは難しいですがプログラマ
としては処理系によって挙動が変わるのは移植の観点からもあまり好ましくは無いでしょう。

ただゲーム開発は未だC系が主流なので今回の話を頭の片隅にでも置いておければと思います。


posted by 管理人 at 15:34 | プログラミング