プログラム・アルゴリズム

CDのピットの数
2021年03月05日 23:32

700MiB=58.7億bitだから58.7億個?
違う。
内容によって変わるが、たぶん平均的に20億個くらいだと思う。

まずセクタ数とセクタあたりバイト。Wikipediaを見る。

コンパクトディスクは650MiBでは約333,000セクタ、700MiBでは約360,000セクタからなる。1セクタは2,352バイト

セクタはとりあえず360000の方を取ることにする。この2352バイトというのが誤り訂正符号を含むのかどうか分からなかった。
英語版Wikipediaを見ると、

Each of these structures contains 98 channel-data frames, totaling 98 × 24 = 2,352 bytes of music.

誤り訂正符号を含まないデータだけの値のようだ。
なので誤り訂正符号を含めて1セクタあたり2352/24*33=3234バイト、360000セクタを掛けて11.6億バイト。
これにEight-to-fourteen modulation(EFM)を掛ける。
符号表はここにある。出現するデータに偏りがある可能性はあるが、よく知らないのですべて同様に出ると仮定すると、平均した1の数は3.07個くらいだった。
この14bitごとに3bitのmerging bitが付く。付き方についてはStandard ECMA-130「Data interchange on read-only120 mm optical data disks(CD-ROM)」という資料のAnnex Eにあった。
4種類(000, 001, 010, 100)のうち0の数2個以上10個以下の条件を満たす中でdigital sum value (DSV)が最小になるものという。DSVの説明がよく分からないが、たぶんHighとLowの割合を等しく保つやつだと思う。
とりあえず256個のパターンの先頭と末尾の組み合わせ65536通りを調べてみると、0の数が合計2個未満、つまりmarging bitが000に確定するものが16211通り、0が合計7個超、つまりmarging bitが1を含むことが確定するものが7529通りあった。
残りの41796通りが問題だ。考えてもよく分からなかったので、単純に4種類が均等に出ると考えて3/4の確率で1が入ると仮定する。すべて合わせて1の入る確率は0.59ほどとなった。
そうすると3.07個くらいと合わせて1バイトあたりの1の数は3.66個くらいになる。
データの1ごとにピットの有無が切り替わる(つまりピットの縁がデータの1に対応する)ので、ピットの数は1の数の半分、11.6億バイト×3.66[個/バイト]/2=21.3億個。
というわけでピットの個数は20億個くらいと推測できた。

Post time : 2021年03月05日 23:32 │Comments(0) │プログラム・アルゴリズム

6段のカレンダーが好きだ
2020年11月15日 04:06

月ごとのカレンダーは、多くが5段で収まるが、次のようなパターンで6段になる月もある。

1 | 1 2 | 1
2 3 4 5 6 7 8 | 3 4 5 6 7 8 9 | 2 3 4 5 6 7 8
9 10 11 12 13 14 15 | 10 11 12 13 14 15 16 | 9 10 11 12 13 14 15
16 17 18 19 20 21 22 | 17 18 19 20 21 22 23 | 16 17 18 19 20 21 22
23 24 25 26 27 28 29 | 24 25 26 27 28 29 30 | 23 24 25 26 27 28 29
30 | 31 | 30 31

ここで、市販のカレンダーには6段の月を素直に6段で描くものと、5段に収めるために下部の30,31日を23,24日と統合しているものがある。
6段の月の下部の統合

統合しているものが嫌いだ。
マスの余白に予定など書きづらいとか月の日の配置を図形として捉えられないといった不便があるし、一部分だけ数字が小さい不均一さが美しくなくて嫌だ。

とはいえ統合しないとなると、単純に作ると5段の月と6段の月で必要な幅が異なり、そのままでは5段の月の方に無駄な余白が多く出てしまう。
6段の月と5段の月

これを嫌って統合する気持ちも分からなくはない。(もっとも中には余白が大量にあるのに統合しているものもあるが、これは何を考えているのかわからない)

これをいかにして無駄無く自然に収めるか、様々なレイアウトの工夫が考えられる。

・5段の月は前月次月の薄い文字のマスで埋める

別にこれでも構わないと思う。5段に比べて多少狭くはなるが。

・6段の月では縦幅が狭いもの
6段は狭い

一番素直な解決策。スペースの有効活用の点で悪くないが、6段の月は他の月よりスペースが少し狭く少し不便であるので不公平感が出る。統合式の下の方にあった大きな不便を月全体の小さな不便に分割したとも言える。

・全て6段の月と同じ幅があるが、前月次月の小さいカレンダーや今月の行事・格言などの入ったマスの配置で余白を吸収するもの
追加マス

大昔に見て上手いなと思った記憶があるのだが、再現しようとするとどうにも記憶のように上手く決まらない。

・6段の月は上部の月表示に食い込むもの

数年前見たもの。好き。曜日表示の位置がずれるが、特に端の方など見なくても分かるので特に問題はない。曜日表示を無くしてもいいくらいだ。

・下に大きな社名があるやつを見ると、そこ削れよと思う。

常に下に社名があったらそこだけ切り取ったり隠したりもできるがたまに日付があればそうできないので社名を見せるためにもいいかもしれない。

・1日だけ飛び出す段は数字だけの幅にする案。
飛び出しは数字だけ

1マス完全に飛び出すよりスペースを節約できる(マスの半分くらいがメモスペースになっているカレンダーを想定している)。メモは数字の横の余白に書ける。
下側は問題ないが上側だと曜日表示がちょっと面倒なことになりそうだ。「1」は幅が狭いので枠内にもそこそこのメモスペースを確保できるかもしれない。
前月次月の薄い表記のマスにも予定を書きたい時には困る。もっともこの場合の薄いマスは統合式5段ではそもそも無かったところなので統合式に劣るわけではないが。
また、不均一で美しくない。

・数字を斜めに順に下げて配置して同じ日数なら縦幅が同じになるカレンダーを考案した。

見づらい。

・噂では海外では5段に収めるためにはみ出した日を上の隙間に配置することがあるらしい。
回り込み

なかなか不思議な見た目だが、実に無駄なくスペースが使えている。慣れれば一番よいかもしれない。
辞書にたまにある1行をやや超える内容が直前の行の末尾の余白にはみ出す表記にちょっと似た印象を受ける。
辞書の逆改行

ところで統合されるのはみな下の23/30,24/31なのはなぜだろう。
上の方、つまり1/8,2/9とすれば桁が少なくて済んで数字も大きくできるのに…
上の方で統合

…とここまで考えて気づいたが、1月8日や2月9日といった月日に見えてしまうというというのはかなり重大な欠点かもしれない。

その後面白い1日/8日統合の例を発見した。模式的に再現したものがこれだ。
1日/8日統合_ゴミ収集カレンダー

どこにあったかというと、某自治体のゴミ収集日表示。
ゴミ収集は平日に行われているため、平日のマスは広く取りたい一方で土日の列は重要ではない。ここで、どんな月でも平日のある段は5段に収まるので、常に統合せず5段で表示することができる。そしてその割を食って土曜の1日/8日統合という珍しいパターンが出現するわけだ。

Post time : 2020年11月15日 04:06 │Comments(0) │プログラム・アルゴリズム│日常

PIC16のDhrystone MIPSを測ろうとしてみた
2020年04月29日 02:23

PIC、中でも昔ながらのミッドレンジは演算性能が低いことで有名だ。
ベンチマークでどれほど低い値が出るか気になる。マイコンの性能比較に広く使われているDhrystoneは整数演算だけなので低性能なCPUでも走りそうだ。

そう思ってDhrystoneのソースコードを見てみると…

int Arr_2_Glob [50] [50];

ミッドレンジPICに5000バイトもメモリは無い。最大でも368バイトだ。

－完－

…とここで諦めてしまうのはつまらない。
よく見てみれば2500個の要素を全て使っているわけではない。アクセスするのはわずか4箇所。これならなんとかなるのではないか。
なんとかなるというのはつまり、Dhrystoneをそのまま走らせることはできないにせよ、なるべく結果に影響の出ない範囲でコードをいじったり、もし本来のコードが走ったらどの程度の速度が出るかを推測することで、それなりに意味のある値を出せるのではないか。

というわけでやってみた。
使うコンパイラはMPLABの標準のCコンパイラ、XC8(v1.44)。無償版なのできっと最適化とかに制限があるだろうが気にしない。

まずは何はともあれコンパイルが通るようにしなければならない。適当に配列要素の数を減らそう。50×50要素を7×6要素に。

int Arr_2_Glob [7] [6]; //Arr_2_Glob [50] [50];

typedef int Arr_2_Dim [7][6]; //[50] [50];

これが妥当かどうかは後で見ていく。
ついでにもう1つこっちも減らさないといけない。50要素を25要素に。

int Arr_1_Glob [25]; //Arr_1_Glob [50];

typedef int Arr_1_Dim [25]; //[50];

int 50個=100バイトはあるんではないかと思うかもしれないが、コンパイラの仕様上1つのオブジェクトは1バンクに収まっていないとならない。
また総メモリ量もわりときつく、ちょっと増やすとすぐ割り付けに失敗する。

配列の読み書きのコードは変えていない。
範囲外を読み書きすることになるがそこは自分の足を撃てるC言語。何の問題もない。

他数箇所変更した。
・エラーが出るたび適当にそれっぽいヘッダファイルをinclude
よく分からないまま追加しているがまあ多い分には問題ないだろう。

・NOSTRUCTASSIGN
structassignで「can't generate code for this expression」が出たので、それ用に用意されたコードが使われるよう

#define NOSTRUCTASSIGN

したら動くようになった。
これにともないmemcpyがコードに書かれたものが使われるようになったが、ライブラリ側のものと衝突したのでコメントアウトした。

・時間計測のためのTIMEだのなんだのを削除
結果に影響の無い部分なのでバッサリと。
このへんをPICで動くように変更するのは手間なので時間計測はシミュレータで行うことにする。
PICは実行クロック数が確定的なので問題ない。

・mallocができない
のでユーザーズガイドを見ると、

Dynamic memory allocation, (heap-based allocation using malloc, etc.) is not supported on any 8-bit device.

とある。
幸いmallocが使われているのは初期化の部分、ベンチマーク本体のループの外だ。直接宣言してしまおう。
ポインタが指す先のメモリがどう用意されたものかはプログラムを走らせる上で違いはないだろう。
おそらく最適化を防ぐために持ってまわった定義をしているのだろうと思われ、そこまでの最適化はきっとされていないだろうと判断する。少なくともポインタ参照はされている。

/*
Next_Ptr_Glob = (Rec_Pointer) malloc (sizeof (Rec_Type));
Ptr_Glob = (Rec_Pointer) malloc (sizeof (Rec_Type));
*/
Rec_Type temp1;
Rec_Type temp2;
Next_Ptr_Glob = &temp1;
Ptr_Glob = &temp2;

なお、これで測り終えた後見つけたのだが、別の対処法として、呼び出されると事前に用意したポインタを返す疑似mallocを使っている人がいた。(後述のAVRのコード)
こちらの方がより安全そうなので真似してみたのだが、後述のポインタ幅違いがまた出てどうしてもうまくいかなかった。
諦めて直接宣言のままにした。

・よく分からないエラーが出た

*Ptr_Ref_Par = Ptr_Glob->Ptr_Comp;

の部分で、「error: (1466) registers unavailable for code generation of this expression」というエラーが出た。
PICでレジスタってなんだろう。RAMとは違うのか。
なんだかよく分からないが2分割したらエラーが消えたのでこれでよしとする。

struct record *temp;

temp = Ptr_Glob->Ptr_Comp;
*Ptr_Ref_Par = temp;

…が、後にこれは必要なくなる。後述。

これで先へ進むようになり、コンパイルが通るか…と思いきや意外なことにプログラムメモリが足りない。結構食うんだなあ。
RAMがミッドレンジ最大の368バイトあるものとして手持ちからPIC16F88を選んだのだが、こいつのプログラムメモリは4kワード。
どうせシミュレータで動かすのだし最大の8kワードある石を適当に選ぶか…と思ったが、コードを見ると大量のprintfがあって容量を食っていそうだ。
状況説明のための出力は不要なので開始と終了を1文字だけ残して消す。
結果出力部分に未使用の変数が消されることを防ぐためのprintfがあるがこちらも極力切り詰める。
例えばこれを

printf ("Int_Glob: %d\n", Int_Glob);
printf (" should be: %d\n", 5);
printf ("Bool_Glob: %d\n", Bool_Glob);
printf (" should be: %d\n", 1);

こうする感じで。

printf ("a:%d\n", Int_Glob);
printf ("b:%d\n", Bool_Glob);

こうして切り詰めたら余裕で入った。3kワード弱にまでなった。
なおprintfから呼ばれるputchの実装は、意味のある出力をするものではなく、シミュレータで適宜止めて出力内容を見るための、引数が消されない最低限のコードにした。

これでビルドが通り、(内容はともかく)動作をするようになった。

出力を確かめると、配列の部分の値が違うのは想定通りだが、他に構造体のポインタ演算あたりの部分も違っている。
調べてみるとおかしいのは例の2分割で代入したところで、16bitのポインタに8bitのポインタを代入している。
この際データが不可解な変化を見せており、その影響でそのあとif文で通らないはずの方を通っている。

XC8ではポインタが8bitと16bitの2種類あるのだが、使い分けは手動ではできず、コード中の全ての代入を認識して自動で最適なものを使い分けてくれるという。
これが判定に失敗して間違った代入をしてしまっているように見える。つまりコンパイラのバグではないか。

ループ外に適当に代入文を書いてみたところ今まで8bitだったところに16bitのポインタが使われるようになり、出力が正しくなった。
そして例の2分割代入部分も元のコードでコンパイルが通るようになった。

配列部分も正しく動作しているか調べよう。
配列のアクセスの部分の数値を書き換えて配列内をアクセスするようにし、正しい結果が出るかを見る。
出た。
また、ここで時間計測し、配列アクセス部以外にかかる時間が変化していないことを確認した。
よって、不正なアドレスをアクセスすることで他の実行結果に影響を与えていることは無いと考えられる。

これで多分配列部分以外は本来のDhrystoneの想定通り動いているだろう。

さて配列の量をいじった事によりベンチマーク結果にどれほどの影響が出ているか考えてみよう。

1次元配列の方の要素数は、(2次元配列を[2][3]にしてメモリを空けた上で)[25][30][35][40][48]を試し、実行時間は一切変化しなかった。
こちらの影響は無いものとみて良いだろう。

2次元配列の要素数を[7][6]から変えて変化を見てみる。
配列の宣言の部分と、typedefの部分。

宣＼def	[50][50]	[50][6]	[7][50]	[7][6]	[2][2]
[7][6]	5800	5693	5800	5693	5571
[4][6]	5800	5693	5800	5693	5571
[8][3]	5800	5693	5800	5693	5571
[2][3]	5800	5800	5800	5800	5571

これを見ると、typedefの方の2次元めを変えると実行時間にやや変化が見られるのに対し、
配列の宣言の方は[2][3]でのみ値が変わるが他は要素数によらず一定である。

本来の[50][50]に近づけられないのが気がかりだが、現状の判断として、配列宣言の要素数を大きくしてもベンチマークの実行時間には影響を与えないと考えることにする。
typedefの方は折角なので本来の[50][50]にしておく。

なおこの要素数だが、変えるとコンパイルに失敗することがかなり多い。
要素数の積が48(メモリ量が96バイト)を越えるとメモリ不足でコンパイルできないのは分かるのだが、次表のようにそれ以下でも値に応じて不規則に失敗する。

	[*][2]	[*][3]	[*][4]	[*][5]	[*][6]	[*][7]	[*][8]	[*][9]
[2][*]	×	○	○	○	×	×	×	×
[3][*]	×	○	×	×	○	×	×	×
[4][*]	×	○	×	○	○	×	×	×
[5][*]	×	○	○	○	○	×	×	×
[6][*]	○	○	○	○	○	×	×
[7][*]	○	○	○	○	○
[8][*]	○	○	○	○	○
[9][*]	?	?	○	○
[10][*]	?	?	○
[11][*]	?	?	○
[12][*]	?	?	○

(○: コンパイル成功／ ×: コンパイルエラー／ ?および表範囲外: 未チェック／空欄: 96バイト超)

この時のエラーは次のようなもので、調べるとメモリのバンクへの割り付けに失敗しているエラーで、PICにはよくあることのようだ。有料版だと出なくなることもあるらしい。

D:\P\xc8\v1.44\sources\common\lwdiv.c:30: error: (1357) fixup overflow storing 0x8E in 1 byte at 0x950/0x2 -> 0x4A8 (dist/default/debug\Dhrystone88.X.debug.obj 120/0x26)

配列の宣言の方はこれでいいとして、実際にアクセスする部分はどうか。この分をどう考えるかは難しい。

何らかの計算をしてアドレスを求め、配列の範囲外とはいえどこかしらをアクセスしてはいる。
しかし、ここで生成されているコードはどうあっても2500の全ての要素にアクセスすることはできない。
そのような不完全なコードで時間を計ってよいものか。

とはいえ2500要素5000バイト分のアドレスというものはミッドレンジではそもそも存在し得ないのだから、それを計算するコードとしてどのようなものを想定するのかの正解は無い。

考えた末、以下2点を補正することにした。

・乗算
まず、アドレスの生成部分を見ると、1バイト×1バイト=1バイトの乗算ルーチンが呼ばれている。実行時間は100サイクル程度。
これはまずい。50×50要素の配列にアクセスするには積を2バイトで持たなければならない。
試しに2つのchar型の変数を乗算してみると実行時間は値によって変わり、124や178サイクル。

char temp01 = 8;
char temp02 = 100;
int temp03 = temp01*temp02;

→124

char temp01 = 38;
char temp02 = 100;
int temp03 = temp01*temp02;

→178
この分を適当に補正することにする。1回あたり50サイクル、配列アクセスは4回あるので計200サイクル追加することにする。

・バンク
5000バイトのメモリは存在しないが、せめて複数バンクにわたるメモリのアドレスを算出するコードは考慮しておきたい。
1バンクあたり96バイトという中途半端な値を使うのはさすがに大変すぎる。
仮に大量のメモリを積むならもっとまともなアクセスができるようにするだろう(というか、実際にPIC18やEnhancedミッドレンジでされている)
悩んだ末、「80バイトや96バイトの容量があるバンクが十分に大量にあり、バンクごとに切りの良い64バイトだけを使う」「バンク選択にかかる時間は考えない」ことを仮定し、以下のコードを書いた。

int address = 0x1234
char addrh = address >> 6;
char addrl = address & 0x3F;

これに50サイクル掛かった。2次元配列のアクセスは4箇所あるので200サイクルを追加する。

以上より、実測値5800サイクルに2次元配列アクセスの分を想定した補正値400サイクルを加えた6200サイクルを、ミッドレンジPICにおけるDhrystone1回分の実行時間に相当する値と考える。

これをクロック数に直して24800クロック、1MHz・1秒あたりDhrystone相当値は40.3、1757で割りDMIPS/MHzの推定値は、
0.0229 DMIPSっぽい値/MHz
と得られた。

比較しよう。

16bitや32bitのマイコンの宣伝にはよく公式にDMIPSが書かれている。見ると、比較的性能の低い(インオーダー・シングルコア)のものでも1DMIPS/MHz程度はある。

CPU	DMIPS/MHz	情報ソース
PIC32MM	1.53	http://ww1.microchip.com/downloads/en/DeviceDoc/60001324b.pdf
RL78	1.39	https://www.renesas.com/ja-jp/products/microcontrollers-microprocessors/rl78/rl78-features.html
ARM Cortex-M0	0.89 (最適化条件を変えれば1.02や1.27)	https://developer.arm.com/products/processors/cortex-m/cortex-m0

何十倍も違うとあまり比較にならない。
もっと性能の低い、8bitCPUの値を探そう。
探してみるとそれなりに見つかる。

http://oneweekwonder.blogspot.jp/2013/12/z80-dhrystones.html
Z80。定番だ。
3.5MHzで0.142DMIPSというので、0.04DMIPS/MHz。

http://www.homebrewcpu.com/new_stuff.htm
65(C)02とZ80。6502はファミコンで有名だ。
6502 - 1.02MHz: 37Dhrystone
Z80 - 2.5MHz: 91Dhrystone
というので、
37/1757/1.02 = 0.02DMIPS/MHz
91/1757/2.5 = 0.02DMIPS/MHz
Z80の値が上の半分だ。まあ環境やコンパイラでこの程度の誤差は出るものだろう。

http://ww2.tiki.ne.jp/~maro/AVR/project/bench1/index.html
AVR。PICとよく比較されるマイコンだ。
at90s8515・8MHzで、最速の結果で1.938MIPSとある。0.24DMIPS/MHzだ。
ただしこの人、律儀に2500バイト(?)のために読み書きに3クロックかかる外部RAMを接続している。
(*2500バイトと書いてあるのはたぶん間違いだと思う。C言語的にIntは16bit以上のはず。)
自分のやったように必要な分のメモリだけにするなら外部RAMは要らずもっと速くなる。
4クロックから3クロックに変えるだけで1.659MIPSから1.933MIPSに上がったというのだから、同じ割合で1クロックになれば2.920MIPS・0.365MIPS/MHzに上がる計算になる。

http://www.ecrostech.com/Other/Resources/Dhrystone.htm
AVRもうひとつ。
こちらは内蔵メモリに収まるよう配列要素を半分にするなどしているようだ。先述の疑似mallocはここの記述だ。
ATmega64で、0.328DMIPS/MHz。
上の0.24DMIPS/MHzより速く、推定0.365MIPS/MHzよりは遅い。
調べてみるとat90には乗算命令がなくATmegaにはあるようなので、at90より速いはずだ。してみると上の推定0.365MIPS/MHzは少々怪しいか。

これらの値と今回のPICの推定値を比較してみる。

Z80: 0.02～0.04DMIPS/MHz
Z80はゲームボーイのCPUしか扱ったことがないが、1命令のクロック数は4の倍数で、概ねメモリアクセスの回数×4クロックに一致する。これはPICと似た性能である。
本来のZ80は多少クロック数が異なり、またレジスタが多かったりループ命令があったりするが、大勢に影響は無いだろう。
クロックあたりに行う動作がPICと同程度で、命令がZ80の方が豊富であることから、DMIPS値が1倍～2倍というのはだいたい感覚と合っている。

6502: 0.02DMIPS/MHz
6502はメモリアクセスあたり1クロック+α(内部処理分)といった趣で、Z80よりクロックあたりの性能は高い印象がある。
Z80と同等か低い値というのはちょっと感覚と合わない。まあZ80も2つで2倍の差があるくらいだし、この程度は誤差なのかもしれない。

AVR: 0.24～0.365DMIPS/MHz
Z80や6502と1桁違う。PICの10.5～16倍。感覚的にちょっと多すぎな気もするが、よく考えてみよう。
まずAVRは大半の命令が1命令1クロックで動く。PICは基本的に1命令4クロックなので、命令数では2.6～4倍となる。
ミッドレンジPICとAVRのアーキテクチャを比較すると、
・PICは汎用レジスタが1つのみであり何をやるにもメモリに値を置く必要がある
・PICはプログラムメモリのページ・RAMのバンク切り替えで時間を食う
・PICには乗算命令が無い
・PICは間接アドレッシング用のレジスタが1本しか無いことやメモリのバンク分けのため、C言語に向いていない
・一方AVRは間接アドレッシング用のレジスタが16bit×3本もあり、大変C言語向きである
といったあたりの要因からして、2.6倍くらいは妥当だし4倍もまあありうるのかなと思えてくる。

Conclusion

独自の仮定のもとにそれなりにDMIPSに近いと信じる値を算出し、いくつかの8bit CPUの値と比較して感覚とそれなりに合う結果となったので満足である。

結論に問題があるとすれば、まず一番怪しいのが2次元配列アクセスの補正が正当かどうか。
そしてmalloc除去を始め各所で加えた変更が正当かどうか。
あとはPICでまともにC言語を使ったのは初めてなのでなにか手順にとんでもない間違いがあるかもしれない。
有料版で最適化をかけて別次元の速さになったりしないかも少し心配だ。(「(PRO版なら)最大で60%小さく400%速いコードができていたんだぜ」ってコンパイルするたびに言われるのだ)
コードはgithubに上げたので、何か疑問があれば色々試してみるとよいだろう。
https://github.com/Ikadzuchi/Dhrystone88.X

なお、本稿をほぼ書き終えた段階で公開用にコードを整形したところ、ループ外の不要部を削っただけなのだが、ループの実行時間は5800サイクルから5824サイクルに増えた。面倒なので文中の数値は直さない。
コードの位置が変わることによりページをまたいだりして実行時間がこの程度変化することは十分考えられる。
他にもループ外にテスト用の乗算コードを書いたら7016→6996に短縮したこともあった。(不正な場所を実行していた時なので実行時間は大きく違う)

Post time : 2020年04月29日 02:23 │Comments(0) │マイコン│プログラム・アルゴリズム

Twitterの画像の扱いがやっとまともになって嬉しい
2019年06月23日 00:23

大昔、TwitterにJPEG画像を上げればJPEGのまま、PNG画像を上げればPNGのままだった。まあこれはこれで最高ではあった。

それが2016年1月、基本的にPNGはJPEGに変換されるようになった。
ただし、1pxでも透過部分のあるPNGはPNGを維持する。(容量の上限もあり。3MB?)

この仕様の問題点は
・PNGの方が容量が少ないようなファイルは、容量が増える。
・PNGの方が望ましいような画像をPNGで上げたい場合、目立たないよう隅などを透過する面倒な作業が発生する。
・PNGをPNGで上げる操作は本来意図していないであろう裏技であり、知っている者と知らない者に不公平がある。
・JPEGの方が望ましい画像(JPEGの劣化はさほど目立たない一方、PNGでは容量が非常に大きくなるもの)もPNGで上げられる。ダウンロードに時間が掛かったり、ギガが減る。

それが先日、2019年2月11日の新しい仕様で、透過PNGの裏技が使えなくなったとともに、一定の条件でPNGを維持するようになった。
具体的には、「900×900以下」または「256色」または「JPEGに変換した場合よりPNGのままの方がデータ量が少ない」場合にPNGを保つようになった。
(なおJPEGも、TwitterのJPEGよりデータ量が少ない場合に上げたままのJPEGを保つようになったようだ)

これは上記の問題点の解決を意図したものだろう。
・PNGの方が容量が少ないようなファイルは、PNGのまま容量は増えない。
・PNGの方が望ましいような画像をPNGで上げたい場合、PNGで上げるだけで済む。
・裏技は無く、公平に処理される。
・PNGでは容量がかさむ画像はJPEGでしか上げられないので、適切な容量で閲覧できる。900×900制限は、小サイズなら容量も少ないので許容ということだろう。

新仕様に問題が無いわけではない。

イラストなど劣化の無い最高の画質で見せたい/見たいような画像については、新仕様では無劣化は不可能になった。
これ自体はサーバーのコストとの兼ね合いであり、仕方ないことだ。
だが、それにしてもPNGとJPEGで落差が激しすぎるのは問題だと思う。
Twitterで使われるJPEGは85%・サンプリング4:1:1という画質のだいぶ低めな設定なので、色がくすむなどものによって劣化がかなり目立つ。
そしてPNGを保つ条件はこの低画質のJPEGより容量が少ないことなので、かなり厳しい条件となってしまっている。

一方、900×900の上限はかなり緩すぎると感じる。このサイズの無駄PNGはかなりの大容量だ。
風景写真などJPEGの方が望ましい画像も、このサイズ以内ならPNGで上げられてしまう。
わざわざ写真をPNGで上げる人もそういないと思うだろうが、フォトリアルなゲームのスクリーンショットはよくPNGで上げられる。
また実写写真でもたまに見かける。MSペイントのデフォルト保存形式がPNGなことや、ファイルでなく画像データをそのまま投稿画面にペーストすることができることを考えると、意図せずPNGで上げられることもあるのだろう。

総合して、問題はあるものの、基本的には今回の仕様変更は改善だと思っている。
以前あった無駄や不公平は無くなり、新たな制限もコストとのトレードオフで納得のできるものだ。

一応改善案も示しておこう。
PNGとJPEGの落差が激しい問題に対して、現状のPNG・低画質JPEGの間に例えば90%・4:4:4程度の「それなりに高画質のJPEG」を挟めば大分印象は変わる。
単純に判定するなら、「PNGは高画質JPEGより容量が少ない場合PNGを保ち、そうでなければ高画質JPEGにする。JPEGは低画質JPEGにする。」という判定が考えられる。
JPEGをPNGとして上げると高画質で上げられてしまう欠点はある。
もっと適切な判定をするなら、何らかの指標(単純なPSNRで十分だろう)でJPEG化した時の劣化度合いを測り、劣化が激しいようなら高画質にするという判断が考えられる。
サーバーコストとのトレードオフだが、まず900×900の小サイズ許容は無くしても問題ないだろう。
また、現状PNGを保つ場合はタイムラインに表示される縮小版もクリックして表示される拡大版もPNGとなっているが、縮小版はサイズがかさむ場合JPEGでも構わない(むしろ望ましい)だろう。
拡大して見る画像は少ないから、これだけでかなり通信量は抑えられるのではないだろうか。それでも足りなければ縮小版を更に低画質にするのもよいだろう。

Post time : 2019年06月23日 00:23 │Comments(0) │プログラム・アルゴリズム

ファミコンで9×9ドット文字表示(ほか)
2019年04月08日 02:02

ファミコンあたりのゲーム機は画面を8×8ドットのタイルを並べて構成している。よって文字表示は8×8ドット(空白含む)にするとプログラムが簡単だ。
このサイズだとひらがなカタカナ(濁点・半濁点なし)にちょうどいいサイズである。英数字にはやや大きいがさほど不自然でもない。

問題は漢字表示である。
8×8ドットに漢字を描くのはかなりの無理がある。16×16ドットにすれば何不自由なく描けるが、このサイズの文字は大きすぎて画面内に書ける文章量が減る。
そこでその中間あたりのサイズの文字表示をやってみようと思い立った。

まず考えたのが12×12ドット(空白含む)だ。1.5マスで比較的扱いが楽そうだ。
ゲームボーイでプログラムを組んでみて、まあうまくいった。
12×12ドット文字_ゲームボーイ

なお後に知ったのだがゲームボーイで12×12ドットのフォントはいくつか例がある。その1つの「合格ボーイ」シリーズの「常識の書」がこちらだ。
常識の書_横書き

さて、12ドット文字プログラムだが、意外と面倒な面が多かった。
1文字を18バイトで持っていたのだが、18は切りが悪い。縦横に空白をとると11×11ドットであり、11×11=121ビットというのは16バイトに収まる。せっかくだから収めたくなるがなかなか上手くいかない。
半角文字も用意したくなるが、横6ドットとなるとせっかくの1.5マスの切りの良さが無くなってしまう。
12×12ドットはわりと面積が広く、書き込みに意外と時間がかかる。
(なお先述の「常識の書」だが、英数字は全角の半分ではなく横8ドットにして切りの良さを保ち、フォントデータは中央4ドットを重複して持つことで表示を楽にしている。勉強になる)

12ドットでも面倒なら別のサイズでも似たようなものではないかという思いにいたり、別のサイズを模索してみることにした。
すると9×9ドット(空白含まず)がかなり楽そうだと分かった。
一見中途半端だが、9×9ドットはどのように配置しても8×8ドットのマス目の4マスにかかるという重要な性質がある。場合分けが不要というのは楽だ。
8bitCPUのレジスタは8bitだが、キャリーフラグをうまく使えば9bitを保持しておくことができる。
文字を9×9ドットとして1ドットの空白を設ければ10ドット。偶数なので奇数より多少楽だ。

そんなわけでゲームボーイで組んだ。
9×9ドット文字_ゲームボーイ

見ての通り表示できる文字数が増えるのも利点だ。漢字の読みやすさは12ドットには劣るものの、十分だろう。

その後ファミコンに移植してみた。
ファミコンでもカートリッジにメモリを積めばゲームボーイと同様にキャラクタを書き換えることができる。(CHR-RAMと呼ばれる)
(以前はあまりカートリッジ側に複雑なものを載せるのはレトロゲームプログラミングとして反則な気がして敬遠していたのだが、CHR-RAMを使っているソフトは普通にある感じなのでいいかと思い直した)
9×9ドット文字_ファミコン

ゲームボーイでは1文字出力のコードしか書いていなかったのだが(上の画像は1文字出力関数を文字数分呼んでいるのだ)、ファミコン版でやっとテキストデータを呼んで文字列を表示するコードを書いた。
(もっとも現状文字コードが1バイトで文字を256種しか使えないのだが)

これの製作中に1つ思いついて実装したのが、フォントデータの一部をテキストデータに持たせる手法だ。
フォントデータは普通には9×9で81bit、10バイトと余り1bitになる。これを11バイトで持つのは無駄が多く気に食わない。
そこで、例えば文字コードの最上位bitを文字の右上のドットに対応するようにする。するとフォントデータとして持つのは残りの10バイトのみでよくなる。
文字コードの並びは不規則になってしまうが、文字列を表示するだけなら問題は無い。
問題が起こるのは、まず外部とのやり取りで既存の文字コードを使う場合。これはゲームではあまり考えなくてよいだろう。
それと、文字列をソートしたい場合。これはやや問題になるかもしれない。漢字はソートできなくてよいと考えて、仮名のみならテーブルを作るか、文字コードを上手く作れば仮名の順は取れるようにできるかもしれない。

あと文字の送り幅を変えるコードもやっつけで書いた。やっつけなので1文字あたり1バイトを余計に使う無駄なコードだが。文字データも10バイト使って無駄だ。

NESファイルは[こちら]。
コードは汚いので(まだ)公開しない。そのうち整えてCC-BY-NCあたりで公開するつもり。ゲームボーイからファミコンへの移植で変わったとことかも文章にまとめたい。

(2019/07/17追記)
実機動作していただいた!

実機(NEWファミコン)で動かしてみたところ。
御覧の通り、画面後半の文字表示外の領域が化けている。
(不定パターンデータが不定ネームテーブルを元に表示されている) pic.twitter.com/dwv6F1yVH8
— レゲ活Lab (@LabRegekatsu) 2019年5月2日

…そして初期化忘れに気付かされる。
エミュレータはふつう初期状態のメモリは全ゼロになっているので初期化しなくても動いてしまい、実機で動作させて初めて気づくことが多い。PICマイコンでもしょっちゅうやらかした。
これをエミュレータでテストするのはなかなか面倒である。今回はテスト用に乱数生成(Xorshift)のコードを書いてまず最初にRAMをランダム値で埋めることにした。
それでできたのがこちらである。見事に再現できた。
初期化忘れ再現

さらに調べているとスタックが3バイト単位の繰り返しで全部埋まっていることにも気づいた。スタックオーバーフローだ。
コードを確認すると、初期化からVBlank割り込みルーチンに流れ込むわ、VBlank割り込みルーチンは最後リターンせずにVBlank待ちに入るわのめちゃくちゃなコードだった。よく動いていたな。

そんなわけで割り込みルーチンを直しメモリのゼロクリア処理を追加して、
確認してみると目的のノイズは消えたのだが、起動時に一瞬別のノイズが見えるようになったのが治らない。
起動時一瞬のノイズ

どうやらランダム値をVRAMに書き込む際に出ているようで、表示は切ってあるはずなのに不思議である。
ランダム化を消せば消えると思われたが、理由が分からないのは不安なので調べることにした。
結果、案の定仕様を勘違いしていたことが分かった。PPUADDRレジスタがパレットのあるアドレスを「表示中に」指しているとそのパレットの色が出るという仕様があるのだが、これを非表示中に起こるものと思っていた。
https://wiki.nesdev.com/w/index.php/PPU_palettes#The_background_palette_hack
更に、この仕様に関連して、ファミコンは起動時の一瞬、PPUが操作可能になる前に(条件によって異なる)とある1色を表示するということも知った。そういえばそんなだった気がするな。PPUが操作可能になる前なのでどうしようもないらしい。

理由が分かったので安心してゼロクリア処理を消す。今まで確認に使っていてNintendulatorではノイズが見えなくなったが、再現度の高いらしいMesenでは本来のパレットへの書き込みの分まだわずかに残っている。VBlank中へ持っていけば消せるのかもしれないが面倒なのでひとまずこれでよしとする。
画像を載せようかと思ったが上のと全く同じなのでやめる。
上のNESファイルは更新した…はず。エミュレータで見ても表示は同一なので確認が難しい。

あと全画面任意画像の方にも同じバグがあったので合わせて修正した。

Post time : 2019年04月08日 02:02 │Comments(0) │文字コード│プログラム・アルゴリズム│ゲーム機

謎の色名「honeydewtab」とlegacy color valueパース手順
2018年03月24日 12:45

HTMLやCSSで使うために140個の色名が定義されている。個人ホームページ全盛期のHowTo本にはよく載っていたものだが思えば最近あまり見ない気がする。
HTMLを書いていてなんでもいいからとりあえず色を付けたい時一々カラーコードを書くよりredとかblueとか書くと楽なので便利だ。(cyan・magenta・yellowもあるがgreenは罠だ。緑100%はlimeだ。)

ここで、謎の色名「honeydewtab」というものがある。
詳しくはこちらのページを読んでほしいが、かいつまんで言うと
・なぜか色名として「honeydewtab」が載っている本やサイトがあった
・何らかの色が出るが、ブラウザにより異なる
・著者から連絡があり間違いだったと確認された
ということだ。

ここで不思議なのが何らかの色は出ること。
存在しないのならなぜ無視されるのでなく何か出るのか。どういう解釈をされているのか。
調べていると別のサイトで様々な文字列が実験されているのを見つけた。
ここの「coffee」で見覚えのある色があって気づいた。これは#C0FFEE色だ。英単語として読める16進数は色々あり、中でもちょうど6文字でいい感じの色が出るC0FFEEは自サイトでもよく使うお気に入りだったのである。

すると#を付けなくとも16進数として解釈されるのか。試してみると6文字の時は16進数字以外を"0"として解釈した値と一致している。
謎はほぼ解けたもののhoneydewtabなど6文字以外の場合の規則は分からずじまいだった。

その後HTMLの仕様を見ていた所「legacy color value」としてパース方法が定義されているのを見つけた。
https://html.spec.whatwg.org/multipage/common-microsyntaxes.html#rules-for-parsing-a-legacy-colour-value
簡単に説明すると、
16進数字以外を'0'に置き換え、文字数が3の倍数になるよう末尾に'0'を足し、3分割。3つの要素それぞれの先頭から等しい数の'0'を、最低2桁は残して、除ける限り除く。各要素の先頭2桁を1バイトのRGBと解釈する。
というものだ。(簡単に説明できなかった。)
正式な簡略表記だと思っていた3桁表記(#369=#336699みたいなやつ)もlegacyだったのは意外だ。

honeydewtabを例にパースしてみよう。

honeydewtab
000e0de00ab 16進数字以外は"0"に置き換える
000e0de00ab0 3の倍数文字になるよう"0"を補う
000e,0de0,0ab0 3等分する
00e de0 ab0 各部分において先頭から同数の"0"を消す
00 de ab 各部分の先頭2文字を取る
#00deab できあがり

さて、この複雑なパース手順は何を意図したものだろうか。
桁数が多い場合を考慮している点と、先頭2文字を取るところは、将来的に各色要素が3桁以上になった場合でも対応できるようにしつつその場合に各色8bitの環境でも適切な色を出せるように考えられているように見える。
しかし、そう考えると3桁以上で頭が0の時は破綻する。
例えば(000,012,0AB)という3桁の色表現があったとして、2桁に変換するなら(00,01,0A)となってほしいところだが、この手順では(00,12,AB)になる。
してみるとこの仕様はまともに使えることを意図したものではなく、各ブラウザでまちまちだった挙動をなるべく保持しつつ矛盾のない1つの仕様にまとめたものなのではないだろうか。

Post time : 2018年03月24日 12:45 │Comments(0) │プログラム・アルゴリズム

JPEG圧縮を繰り返しても際限なく劣化するわけではない
2017年02月10日 01:47

ビデオテープのダビングやコピー機でのコピーは世代を重ねるごとに劣化が蓄積する。
同様にJPEG画像も、保存→開く→保存…と繰り返すと、

オリジナル

保存1回目

保存9回目

保存17回目

保存49回目

保存97回目

保存201回目

保存497回目

保存1001回目

保存2001回目

保存5001回目

保存10001回目

といった具合に劣化が蓄積して画質が際限なく落ちていき、最後には一面のノイズになってしまう…

…と誤った認識を持っている人が多い。

実際に試してみよう。使用するソフトは定番のImageMagick。

magick convert -sampling-factor 1x1 -quality 95 orig.png gen1.jpg
magick convert -sampling-factor 1x1 -quality 95 gen1.jpg gen2.jpg
magick convert -sampling-factor 1x1 -quality 95 gen2.jpg gen3.jpg
…

このようなバッチファイルをExcelとテキストエディタで作成し、実行する。
結果は次のとおり。

オリジナル

保存1回目

保存17回目

以上だ。
3000回くらい回していたのだが、確認してみると18回目で既に前回と同一の画像が出力されていた。だいぶ時間を無駄にした。
このように、繰り返し保存による劣化は早々に止まることが分かる。
なお今回は1種類に収束したが、以前試した時は3種類のローテーションになったこともあった。
また、見て分かる(分からない)とおり、1回目と17回目で差はほとんど無い。
念のため差分をとってみよう。
JPEG劣化_差分_1-17

全く見えないので64倍に強調したものも置いておく。
JPEG劣化_差分_1-17(×64)

そもそも非可逆圧縮の原理は、元データを少々変えて「圧縮しやすいデータ」を作り、それを可逆圧縮するものと解釈できる。
よって一度非可逆圧縮したデータを展開したデータは、既に「圧縮しやすいデータ」になっているため、同じ設定で圧縮すれば完全に可逆圧縮になってもおかしくない。
むしろ17回まで劣化が続くことの方が不思議といえる。
ではなぜかだが、JPEGの圧縮の根幹である離散コサイン変換(DCT)は本来は可逆なのだが、実際には有限の精度で計算するために丸め誤差が発生する。おそらくこれがJPEG再圧縮が不可逆な原因だと思う。
またどうもJPEGの仕様はあまり厳密でないようで、エンコードでは演算の精度をソフトの自由で選べたり、デコードもソフトによって結果が違ったりする。これも一因かもしれない。
(2/11追記)RGB→YUVの変換も丸め誤差が発生するので一因かもしれない。

さて次にパラメータを少し変えてみる。

オリジナル

1回目

10回目

20回目

50回目

103回目

今度は劣化が103回目まで続く。劣化の度合いも目に見えて分かる。色が褪せていて、特に赤が大幅にくすんでしまっている。
差分をとってみる。
JPEG劣化_サンプリング2×2_差分_1-103

少し見にくいので4倍に強調しておこう。
JPEG劣化_サンプリング2×2_差分_1-103(×4)

闇夜に光る眼のようで可愛い。

何を変えたかというと、カラーサブサンプリングだ。
カラーサブサンプリングは、クロマサブサンプリングや色成分間引きと呼ばれたり、単にサンプリングやサンプリング比という名の設定項目で設定したりする。名前が定まっておらず面倒な概念だ。
先の17回で劣化が止まったものは、カラーサブサンプリングがOff、別の言い方をするとサンプリングが1x1や4:4:4と呼ばれるものだ。この設定では輝度成分と色成分を元の解像度のまま処理する。この時、画像は8×8のブロックごとに処理され、隣のブロックとの間で影響を及ぼすことはない。
一方103回の方は、カラーサブサンプリングがOn、サンプリングが2x2や4:2:0と呼ばれる設定であり、輝度成分は元解像度で、色成分は縦横1/2に縮小してから処理をする。
この縮小で単純に2×2ピクセルを平均するのであれば16×16のブロック内に影響が留まるだろうが、どうもそうではなく線形補間か何かをされているようで、ドットの色が16×16pxの境界を越えてにじむ現象が見られる。これにより隣のブロックの色が圧縮に影響し、次回は隣の隣のブロックにまで波及し、と際限なく影響を与え合う。厳密なことは分からないがこれが劣化が長く続く理由ではないかと思う。

なので劣化が蓄積するというのは、カラーサブサンプリングOnの設定においてはある程度正しい。
ただしそれにしても際限なく劣化するということはないし、JPEGが全てそのように劣化するわけでもないことは上で示したとおりだ。

さてもうひとつ、冒頭の例のように完全なノイズにまで際限なく劣化させるにはどうすればよいだろう。劣化しそうな方法をいろいろ試してみた。
まず圧縮率を毎回変えたら量子化の閾値が変わることで劣化が続くのではないかと考えたのだが、駄目であった。1万回繰り返してもほぼ劣化が見えなかった。(同じ画像が続くことは無かったので何パターンかのローテーションになっていたようだ)
次に90度回転を試したがこれも同様であった。今回使ったJPEGの量子化行列は縦と横で対称でないのでそれによるゆらぎを期待したのだが…。
そこで毎回画像の位置をずらしてみることにした。7回右下へ1pxずらしたあと、1回左上に7pxずらして戻すの繰り返し。これは見事に成功、これでできたのが冒頭の画像だ。
なぜこれが上手くいくかは、正確なことは分からないが、特定のドットに注目するとそのドットは8×8のブロック内で位置が毎回変わるようになっており、これで誤差が波及し続けるのが一因だろう。
サンプリング2x2の時は止まってしまったのでそれ以外に何かあるのだろうが、よく分からない。何か誤差が発振するような機構があるのだろうか…。
なお90度回転も、画像サイズが8×8の倍数でない場合はずらすのと同じことになる。

以上、まとめると
・単純に同じ設定で圧縮を繰り返すだけでは際限なく劣化することはない。
・ただしサンプリングを落とした場合は少々劣化が続く。
・設定を変えても際限なく劣化はしてくれない。
・位置の移動を伴うと際限なく劣化した。

JPEGの劣化は奥が深い。

Post time : 2017年02月10日 01:47 │Comments(2) │プログラム・アルゴリズム

ゲームボーイの吸い出し機を作った (後編)
2017年01月16日 22:44

前編の続き。プログラム側について。

まずは単純に読むことを試みる。
手持ちの中でバンク切り替えなし(32kB)のソフトとしてDr.マリオを選択。

バンク切り替えが無ければアドレスを出してデータを読むだけ。
…とはいえCLKとかCSとかRDとかどう制御すればいいのか。
GBのカートリッジの仕様くらいいくらでも見つかると思っていたのだが、ROMの読み出し方法は常識なのか、細かい解説が意外と見つからない。
結局、分かってみると単純で、
/RDがLにアサートされている間、アドレスピンで指定されたアドレスのデータが、データピンに出る
というだけのことだった。
つまり読み出すには、/RDをLにアサートしたままアドレスを順次変え、データピンを読むだけでよい。
これが分かるまでに/RDをH/L切り替えてしていた。
あと/CSはSRAMを読む時アサートするものだった。

プログラミング自体もなんだかんだで苦労した。
やはり合っているか分からない操作を正しく組めているか分からない機械にプログラムするのは疑心暗鬼に陥ってだいぶ精神を消耗する。
まずシリアル通信するところからしてうまくいかない。
シリアルポートが全く反応しなくて焦った挙句Windows10へアップグレードした時にケーブル類全部抜いてたのを戻してなかっただけだったりもした。
何か出るようになったと思えば文字化けしている。これはどうもTeraTermのバグかWindows10との相性のようで、最新版を使ったら正常であった。
新しいPICを使う際には毎回のようにGPIO以外の機能を切っていなくて問題が起こるのだが、今回もまんまとその罠にはまった。
ADコンバータとコンパレータを切ったまでは良かったのだが、それで読もうとしても何も読めない(FFが読める)。
ポートのレジスタを直接インクリメントしてたのがまずかったかと思い、別の変数をインクリメントしてそれを出力するようにしたところ何かは読めるようになったが、全体にわたりほぼ確実に8バイトづつ同じ値が取れる。
つまりアドレスの下3bitが何かおかしい。そのピンを調べると、LCDドライバの電圧生成機能がデフォルトでONであった。
ということはポートのレジスタを直接インクリメントすること自体は問題なく、最下位bitの書き込みが無視されていたせいでインクリメントできていなかったんだな。

というわけでついにDr.マリオが読めた。

次はバンク切り替え…の前に色々なソフトをバンク0だけ読んでみることにした。
するとポケモンYellowやポケモンカードなど読めるものもあるが、ポケモンSilverが読めない。
読めないというのは、ほぼ全てFFが返ってくる。ごく稀にFF以外のものが返ってくることもあるのがまた不可解である。
FFでない箇所のパターンは規則的で、なにかありそうである。2進数で「xxxx xxx1 0000 000x」と「xx00 0110 0000 0001」、つまり0100, 0101, 0300, 0301,…と0601, 4601がFFでない。
不要なはずのクロックだがMBCを積んでいることもあり何か変わるのではないかと入れてみる。当然変わらず。
…散々悩んだ挙句、電圧不足であった。
いつもPICを動かす時はEneloop2本(2.6V程度)を使っていて、使いやすい5V電源を持っていないこともあり、とりあえずそれでやっていたのだが、GBの電圧は5Vなので動かなくてなんの不思議も無いのであった。
Dr.マリオを始めいくつかのソフトで(バンク0は)読めていたので発覚が遅れた。

改めてバンク切り換えだ。
バンクの少ない(最少の4バンク)ものとしてQIXを選択。
バンク切り換えの手順はMBCによって少々違うが、基本的に特定のアドレスにデータを書き込むだけである。
書き込むべきデータを入れていなかったり、PICのIOを入力のまま出力したつもりになっていたり、書き込むアドレスを間違ったりして手間取ったが、まあまあすんなりと読めた。
QIX

さて続いて本命のポケモンSilverだ。
128バンクあるが、バンク切り換えのやり方は同じなので、単純に数が多いだけ。難しいことは何もない。
しかしなぜか途中でデータが飛ぶ。読み取ったデータを見るとファイルサイズが想定より小さい。
今までこのような大量のデータをシリアルで受信したことは無かった。シリアル通信の信頼性はこの程度なのだろうか。
だがそれは想定の内。1バンクごとに目印を入れてあるのでどこで抜けたかは分かる。何度か読んで正常な部分を切り貼りすればよいだろう。
…と思っていたのだが、不思議な事に常にエラーが出ている場所がある。
バッファ切れを疑ってバッファ量を変えたりウェイトを入れたりしてもなんとなく変化はあるものの直らず。
データの問題かと思いXOR 0x55したデータを送ってみると抜けの量はほぼ変わらず、抜けの位置が変わった。特定のデータが来ると問題が起こるのだろうか。
速度を落としてみるとだいぶ改善した。抜けが6バンクまで減ったので試しに起動してみると、一応起動はした。
ポケモンSilver_データ抜け1

このような分かりやすいバグった表示になるものなんだなあ。
なお部屋に出口がないので進めなかった。その後もう1バンク正常に取れたのでそれと合わせると部屋から出られたがBGMが異常になったりする。
しかしここで何度とってもほぼ同じ場所でエラーを起こす。
やはり速度を落とすだけでは解決しない。特定のデータが問題という線で考えてみよう。
改行の処理に時間が掛かっている可能性を考えてCRの後にウェイトを入れてみる。むしろ悪化。
あとは…エスケープシーケンス。何らかのエスケープシーケンスが来るとそれの処理に時間がかかってデータを取りこぼすのではないか。
ここでTeraTermを調べて、受信した文字をすべて表示するデバッグモードがあることを知る。
デバッグモードで受信するようにしたところ、一切取りこぼさなくなった!
ポケモンSilver

後で調べたところ、制御シーケンスに「1B 63: 端末リセット」というものがあるらしい。
つまりこのバイト列が来るとTeraTermがリセット動作を起こし、その間に来たデータを取りこぼしていたようだ。
調べてみると「1B 63」は最後まで読めなかった5バンク中の3ヶ所にあった。残り2ヶ所やそれ以前のエラー箇所は分からないままだがたぶん他のエスケープシーケンスだろう。
デバッグモード以外にエスケープシーケンスを無視する方法がないか調べたのだが、見つからなかった。
人が読む文字列を出す時は改行は使いたいのだが、致し方ない。

次に困ったのがX(エックス)だ。バンク切り替えができない。
調べてみるとこれに使われているMBC2はバンク切り替え時に書き込むアドレスに制限があり、今まで使っていた0x2000では駄目だった。
と0x2100に変えてみたが、やはりバンクは切り替わらない。
そこで読み取れたバンク0のコードを見てみることにした。この中にバンク切り替えのコードがあるはずである。
するとやはり0x2100に書き込んでいる。
合っているのにおかしいなと思い更に調べると、バンク1に変更する時は0x2100だったのだが、バンク2では0x2101、バンク3では0x2102…と、バンクNに変更する時0x2100+(N-1)に書き込むようになっていた。
1少ないのは書き込み後のインクリメントの関係だろう。ということでバンクNに変更する時は0x2100+Nに書き込むようにコードを書き換えてみると、見事読み取りに成功した。
なんだろう。バスコンフリクトだろうか。ファミコンのMMCでバスコンフリクトを起こすものがあるという情報はあるが、GBで起こるというのは見たことがなかった。
X(エックス)

さて次はニンテンドウパワーのGBメモリの読み取りを試みている。
これは複数のMBCの動作を再現する特殊なコントローラを積んでおり、普通のバンク切り換えとは異なるコマンドを入れる必要があるらしい。
色々試しているのだがまだ一切反応がない。一番つらい時期だ。
読み取りができたら、どうも書き込みも出来るらしいのでやりたい。自作ソフトを実機で動かすのは夢である。

ただその前に、どうも読み取りが安定しないのでどうにかしたい。
今まで読めていたソフトでも読めなくなったりしている。
断線しかかっているとかだろうか…。

Post time : 2017年01月16日 22:44 │Comments(0) │マイコン│プログラム・アルゴリズム│ゲーム機

ファミコンで全画面に任意の画像(ただしモノクロ)を表示
2017年01月14日 00:00

ファミコンは普通には全画面に自由に画像を表示できないことはよく知られている。
でもモノクロ2値ならできることに気づいたのでやってみた。
ファミコン全画面_猫耳

とりあえず猫耳。

酉年らしく羽根っ娘。
ファミコン全画面_漢字

全画面任意なのが分かりやすい図柄も。

まず前提として、ファミコンのBG(背景)面は32×30=960個のキャラクタで構成されるが、BGの(スプライトも)キャラクタパターンの指定は1バイトなので、一度に256種類からしか選べない。
よって普通にはBGだけでは256キャラ、画面の1/4強しか埋められず、スプライトを8×16ドットモードで最大の64個使って128キャラ用意してやっと384/960=40%にしかならない。
何らかのマッパーを使えば描画中にバンク切り替えで全画面を別のキャラクタで埋められるが、マッパーを使ってできるのは面白くないので今回考えないことにする。

そこで今回の手法だが、パレットの色分けとキャラクタテーブルの描画中切り替えで実質キャラ数を4倍に増やしている。
まずパレット。
ファミコンのキャラごとの色数は4色だが、これを2色しか使わなければ例えば「白黒白黒」と「白白黒黒」の2種類のパレットを左右で使い分けることで1つのキャラで2つの絵を表示することができる。

01	11	11	11	11	11	11	00
11	11	11	11	11	11	11	11
11	11	00	00	00	00	11	11
11	11	01	01	01	01	11	10
11	11	11	11	11	11	11	11
11	11	10	10	10	10	11	11
11	11	01	01	01	01	11	11
11	11	01	01	01	01	11	10

01	11	11	11	11	11	11	00
11	11	11	11	11	11	11	11
11	11	00	00	00	00	11	11
11	11	01	01	01	01	11	10
11	11	11	11	11	11	11	11
11	11	10	10	10	10	11	11
11	11	01	01	01	01	11	11
11	11	01	01	01	01	11	10

01	11	11	11	11	11	11	00
11	11	11	11	11	11	11	11
11	11	00	00	00	00	11	11
11	11	01	01	01	01	11	10
11	11	11	11	11	11	11	11
11	11	10	10	10	10	11	11
11	11	01	01	01	01	11	11
11	11	01	01	01	01	11	10

比較のために単一のパレットで表示したものがこちらだ。
単一パレット表示

次にキャラクタテーブル。
「一度に256種類からしか選べない」と書いたが、この「一度に」の部分がポイントだ。
仕組みを詳しく言うと、定義できるキャラは256個の領域が2つあり、BGと8×8のスプライトはそれぞれその2つのどちらの領域からキャラを選ぶかを設定できる。同じ領域をBGとスプライトの両方で使うこともできる。
(なお今回関係ないが8×16のスプライトは一度に2キャラを使うので、どちらかの領域から選ぶのではなく、2つの領域を合わせた512キャラを2キャラづつの256組と見たものから選択する)
ここでこの「どちらの領域から選ぶか」の設定は画面の描画中にも切り替えることができる。これにより上半分と下半分で別のテーブルからキャラを選ぶことが可能なのだ。
比較のためにこの切り換えを行わなかったものがこちら。
切り換えを行わない表示

基本的なアルゴリズムは以上だ。
実際のコードは下に置いたが、少々細かい解説を加えておく。

今回CHR-ROMでなくCHR-RAMを使っている。
そのためまず最初にPRG-ROMに持っている画像データを元にCHR-RAM上にパターンテーブルのデータを生成している。
これは事前に適切な並びにしたデータをCHR-ROMに持っておけば必要ない操作だ。
ただ、この並べ替えのプログラムは、ファミコン自体で行うか外部で事前に行うかの違いでどうせ書かなければならない。
ならば1つにまとめた方が扱いが楽なのでこうした。
下に書いたコードと、任意のモノクロビットマップを用意するだけで、NESASMでビルドできる。

このパターンテーブル書き込みのコードは少々複雑だが、やっていることは単純に、256×240ドットの1bitビットマップを適切な順に並び替えているだけだ。
パターンテーブル前半0x0000～0x0FFFが画像の上128ドット、後半のうち0x1000～0x0DFFが画像の残り。0x1F00～0x1FFFには後述の通り0x0F00～0x0FFFと同じものを重複して配置している。

「どちらの領域から選ぶか」の設定、つまりパターンテーブルのベースの切り換えだが、このような描画中のタイミング合わせはファミコンではふつう0番スプライトヒットフラグをポーリングすることで行う。
だが今回別の方法をとった。
0番スプライトヒットはBGとスプライトが共に不透明な点でしか起こらない。つまり画像の当該箇所が透明なとき使えない。
今回任意の画像を表示できるようにしようとしているのでこれは困る。
代わりにあまり知られていないスプライトオーバーフローフラグを使った。
これはライン上にスプライトが9個以上並んで横並び数制限を越えたときに立つはずだったフラグだ。
このフラグはスプライトが透明でも変わらず立つので、BGの内容に関係なく使えて便利だ。
ただ重大な欠点があって、このフラグ、アドレスの桁上がりの誤りで別のデータを参照するせいでまともに動かないという、致命的かつしょうもないバグが存在する。
使い物にならないと思うかもしれないが、バグの条件は厳密に判明している。
詳しくはNesDevの「PPU sprite evaluation」のページを読むとよいが、
スプライト番号順にライン内に存在するかをチェックし、8つめが見つかった次のチェックまでは正しく、その次から誤ったアドレスを参照しだす。
ここから、
・スプライト数が7つ以下なら、必ずフラグは立たない
・スプライト数が9つ以上の時、8つめと9つめのスプライト番号が隣り合っていれば、必ずフラグが立つ
ということが言える。
なので今回はスプライト番号順に連続した9つを目的の場所に置くことで確実にスプライトオーバーフローフラグを立てることにした。
というか残りも面倒なので同じ位置に置いた。

切り換えタイミングだが、画像を単純に上下に分割した場合、きっちりHBlank中に切り換えを起こすようにしないとこのように画面が乱れてしまう。
ファミコン全画面_画面乱れ

そのレベルで合わせるには描画中のスプライトの判定処理の流れをきちんと理解してコードを書かねばならないが、今回面倒なのでそこまではしなかった。
その代わり、1列分(8ライン)のキャラをパターンテーブル前半と後半で重複させておいた。これでこの8ラインの中で切り替えれば画面を乱さないようにできる。

画像データのインクルード部分は「画像データ(生)」と「画像データ(BMP)」の2種類を用意した。(生)は256×240bitの生データを使う時用で、(BMP)はWindowsのMSペイントで出力したBMPファイルをそのまま使えるようにヘッダ分だけずらした位置に配置するものだ。
これを使う時は、まずペイントで適当に描いた絵を上下反転
ペイントで描いて上下反転

モノクロビットマップで保存して

できたファイル名をソースに書き込んでビルドするとできあがり。
ビルドした表示

ぜひ試してみてほしい。

; 全画面に任意のモノクロ2値のビットマップを表示する
; NESASM v3.1でビルド、NNNesterJとNintendulatorで動作確認している。

; INESヘッダー
.inesprg 1 ; PRG-ROM容量(0x4000=16KB単位)
.ineschr 0 ; CHR-ROM容量、CHR-RAMでは0
.inesmir 0 ; Don'tCare(水平ミラーリング)
.inesmap 0 ; マッパーなし

.bank 0

; レジスタ名定義(してたりしてなかったり、してるのに使ってなかったり)
PPUMASK = $2001
PPUADDR = $2006
PPUDATA = $2007

;(グローバル)変数定義
;RAMの連続したアドレスにラベルを付けたいだけなのだがどうもROMに値をとっている。
;どうせ上書きされる場所で実害ないからいいけど、もっとまともな方法があるのだろうか…。
;まあとりあえず今回はこのままでいいや。
.org $0000
chrptr .dw 0 ;CHR-RAM書き込み時のポインタ
cnt1 .db 0 ;カウンタ変数
sprpos .db 0 ;スプライト書き込み時のポインタ
posx2 .db 0 ;何だっけ

;割り込みベクタ
.bank 1 ; 0x2000(8KB)単位。ファイルが全16KBなのでbank3でなく1。
.org $FFFA ; BFFAだけど。

.dw intvb ; VBlank割り込み
.dw init ; リセット割り込み。起動時とリセット時
.dw 0 ; ハードウェア割り込みとソフトウェア割り込み

.bank 0
.org $8000

init:
; PPUレジスタに書き込みできるようになるまで時間がかかるらしいので待つ
ldy #25
.loop:
dex
bne .loop ;5*256=1280 ;30000　30000/1280=23.4375
dey
bne .loop

.loop2:
lda $2002 ; VBlank待ち
bpl .loop2

; VBlankのNMIを無効
lda #%00110000
; ^||||||| VBlank開始時にNMI発生
; ^|||||| PPUマスター/スレーブ
; ^||||| スプライトサイズ 0:8x8 1:8x16
; ^|||| BGパターンテーブル
; ^||| スプライトパターンテーブルアドレス
; ^|| VRAMアドレス増分 0:1 1:32
; ^^ ベースネームテーブルアドレス 0:2000 1:2400 2:2800 3:2C00
sta $2000
lda #%00000110 ; 初期化中はスプライトとBGを表示OFFにする
sta $2001

; パレットRAM=$3F00
lda #$3F
sta $2006
lda #$00
sta $2006

ldx #$00
loadPal:
lda pallet, x
sta $2007
inx
cpx #32
bne loadPal

lda #50
sta posx2

setBg: ;BGのネームテーブルを適宜セット
; 00,01,...0F,00,01,...0F
; 10,11,...1F,10,11,...1F
; ...
; F0,
; 00,
; ...
; D0,
; $2000: BG1 name table
lda #$20
sta $2006 ;PPU_ADDR
lda #$00
sta $2006
ldx $00
lda #30
sta cnt1
ldy #0
bgLoop0:
ldx #16
bgLoop1:
sty PPUDATA
iny
dex
bne bgLoop1
tya
sec
sbc #$10
tay
ldx #16
bgLoop2:
sty PPUDATA
iny
dex
bne bgLoop2
dec cnt1
bne bgLoop0

;CHR-RAM書き込み
setChrRam:
lda #0
sta chrptr
lda #high(chr)
sta chrptr+1
ldy #$00
sty PPUADDR
sty PPUADDR
ldx #30

.loop
lda [chrptr],Y
sta PPUDATA

; 8: タイル縦px数 000yxxxx ~ 111yxxxx
;Y+=20
tya
clc
adc #$20
tay
bcc .loop ; if no carry loop
; 2: 色bit 0000xxxx, 0001xxxx
;Y+=10
tya
eor #$10
tay
and #$10
bne .loop ;if !y&10 loop
; 16: 横タイル数 00000000 ~ 00001111
iny
tya
and #$0F
bne .loop; if neq loop
; 30: 縦タイル数
ldy #$00
inc (chrptr+1)
dex
bne .loop

clearChrRam: ;背景に使わない16キャラ(=256バイト)をゼロクリア (2個スプライトに使う)
; PPUADDR = #$1E00
lda #0
.loop:
sta PPUDATA
dey
bne .loop

setChrRamOverlap: ;BGのベースを変える境目でオーバーラップさせておく
; PPUADDR = $1F00
lda #high(chr)+$0F
sta chrptr+1
ldy #0
.loop
lda [chrptr],Y
sta PPUDATA

; 8:タイル縦 000yxxxx ~ 111yxxxx
;Y+=20
tya
clc
adc #$20
tay
bcc .loop ; if no carry loop
; 2:パレットbit 0000xxxx, 0001xxxx
;Y+=10
tya
eor #$10
tay
and #$10
bne .loop ;if !y&10 loop
; 16: 横タイル数 00000000 ~ 00001111
iny
tya
and #$0F
bne .loop; if neq loop

;属性テーブル (BGパレット)
ldy #$23
sty PPUADDR
ldy #$C0
sty PPUADDR
ldx #8
attrloop:
lda #$00 ; 左半分 00 00 00 00
sta PPUDATA
sta PPUDATA
sta PPUDATA
sta PPUDATA
lda #$55 ; 右半分 01 01 01 01
sta PPUDATA
sta PPUDATA
sta PPUDATA
sta PPUDATA
dex
bne attrloop

;scroll
lda #0
sta $2005
sta $2005

; スプライト配置
lda #$00
sta $2003 ; OAMADDR

; Byte 0-3: Y,TileNo,Attr,X
; Attr:
;76543210
;||||||||
;||||||++- Palette (4 to 7) of sprite
;|||+++--- Unimplemented
;||+------ Priority (0: in front of background; 1: behind background)
;|+------- Flip sprite horizontally
;+-------- Flip sprite vertically

ldx #64
sprLoop:
lda #$7B ; BGのベースの切り替わりあたり
sta $2004
lda #$E1 ; 1:E0 空スプライト
sta $2004
lda #$00
sta $2004
lda #$B0 ; 特に意味はない
sta $2004

dex
bne sprLoop

; 表示開始
lda #%00011110 ; スプライトとBGの表示をONにする
sta $2001

lda #%11110000 ;VBlank割り込みをON
sta $2000

waitInt:
jmp waitInt

intvb:
lda #%11100000 ;BGパターンテーブルベース=0
sta $2000

waitVBlankEnd: ;VBlank終了時点でスプライトオーバーフローフラグが消えるのを待つ
lda $2002
and #$20
bne waitVBlankEnd

waitSprOvr: ;スプライトオーバーフローフラグが立つのを待ってBGパターンを切り替える
lda $2002
and #$20
beq waitSprOvr

lda #%11110000 ;BGパターンテーブルベース=1
sta $2000

rti

;色0・色1
C0 = $0F
C1 = $30

pallet:
.db C0, C1, C0, C1, C0, C0, C1, C1, C0, C0, C0, C0, C0, C0, C0, C0
.db C0, C0, C0, C0, C0, C0, C0, C0, C0, C0, C0, C0, C0, C0, C0, C0
; .db 0x03, 0x11, 0x15, 0x30, 0x03, 0x11, 0x15, 0x30, 0x03, 0x11, 0x15, 0x30, 0x03, 0x11, 0x15, 0x30
; .db 0x03, 0x11, 0x15, 0x30, 0x03, 0x11, 0x15, 0x30, 0x03, 0x11, 0x15, 0x30, 0x03, 0x11, 0x15, 0x30

; 画像データ(生)
; .bank 1
; .org $A000
;chr:
; .incbin "image.bin" ; 画像。256×240/8=0x1E00バイト

; 画像データ(BMP)
.bank 1
.org $A0C2
.incbin "image.bmp"
.org $A100
chr:

(2019/07/17 追記)
CHR-RAMの初期化忘れで空白のつもりのスプライトがノイズとなって見えていたのを修正しました。
やはり実機で動作させないと初期化忘れは見逃しがちである。
最初に気づいたのは、これをベースに作った9×9ドットフォントの方で、こっちをまず修正した。
しかし全画面表示の方はVRAMのほぼ全域に書き込んでいたので同じ問題は起こらないと思いこんでしまった。
実のところ、スプライト用のメモリは初期化していなかったのだ。

こちらが最初にわざわざ乱数(Xorshift)で初期化するコードを入れて再現したもの。
初期化忘れ

再現したところで修正して、乱数初期化を消して出来上がり。(エミュレータでの見た目は前と変わりない)
初期化あり

修正箇所はここを

setChrRomOverlap: ;BGのベースを変える境目でオーバーラップさせておく
ldy #$1F
sty PPUADDR
ldy #$00
sty PPUADDR

こう。

clearChrRam: ;16キャラをゼロクリア
; PPUADDR = #$1E00
lda #0
.loop:
sta PPUDATA
dey
bne .loop

setChrRamOverlap: ;BGのベースを変える境目でオーバーラップさせておく
; PPUADDR = $1F00 ←アドレスが直前からの続きになったのでセット不要に
lda #high(chr)+$0F
sta chrptr+1
ldy #0
.loop
lda [chrptr],Y
sta PPUDATA

それで直して確認していたところスタックがオーバーフローしていることに気づき、調べてみると
・初期化部分のコードの終わりからVBlank割り込みルーチンに流れ込む
・VBlank割り込みルーチンは最後にリターンせずにVBlank待ちに入る
というめちゃくちゃなコードであった。他にスタックを使う関数呼び出しなどしていなかったので動いてしまっていた。
これも直し、あとついでにCHR-RAMに書き込むとこのラベルがsetChrRom:だったのも修正した。

上のコードは修正済み。
なお、基本的に修正前の文章は残すように心がけているのだが、処理が面倒で適当に編集していたので申し訳ないが今回旧コードは残っていない。

Post time : 2017年01月14日 00:00 │Comments(0) │プログラム・アルゴリズム│ゲーム機

最近のWindowsのビットマップフォントの太字
2017年01月09日 18:49

MSゴシックのようなウェイト(太さ)が1種類しかないビットマップフォントをテキストエディタやHTMLなどで太字指定すると、自動生成された太字が表示される。
単純な太字化アルゴリズムとして古くから用いられているのが横方向に1px太らせる手法で、WindowsでもXPまで長らく使われていた。

この手法の問題点は、1pxの隙間を開けて縦線が並んでいる箇所で隙間がつぶれてしまうことだ。
「棚」「鵬」などの縦線の多い字を小サイズで表示すると黒い塊になってしまう。
隙間が潰れる

このつぶれを避ける改良版のアルゴリズムとして、「横に1px太らせてつぶれるなら、太らせない」というものがある。

なお、右に太らすか左に太らすかで2種類存在する。
スーパーの商品の値札の文字や、Javaで作られたGUIの文字表示に使われているのをよく見かける。
最初にこれに気づいたのがスーパーの値札だったので、自分の中でこれは「スーパーの太字化アルゴリズム」と認識されている。
これを最初に見かけた時は画期的だと感心したものだが、これにも欠点はあって、元々連続的な線であったところが太くなるところとならないところが混在すると形状が乱れて文字が読みにくくなってしまう。
スーパーの太字_乱れ

図の赤で示したあたりが不自然な形状になっている。

そして本題の最近のWindowsの太字だ。これが更に画期的なのである。

これは最初に気づいたのがWindows7のインストール画面で、Windows7で始めて実装されたものと思っていたのだが、確認してみるとVistaでも使われていた。
Vistaにも最初からあったのに気づいていなかったのか、それともアップデートで実装されたのか分からない。ともかく、XPまでは無く、7からはある。
この手法の特徴は見て分かるように白黒2値でなく中間調の灰色を使っている点だ。
単純な太字化で問題ないところでは黒で横に1px太らせ、単純にはつぶれてしまうところでは灰色で太らせる。
ここでスーパーのアルゴリズムと異なり、縦に連続する黒ピクセルは常に同じ色で太らせる。これにより形状が乱れることを防げている。

しかしこのアルゴリズムは思った以上に複雑で色々とわからない点がある。
Windows太字の不明点

・黒にするか灰色にするかの判断
単純に太らせると別の点に接触する場合は灰色なのかと思いきや、そうでない場合がある。例えば「棚」の赤で示した木偏の縦線は下2pxが隣の月に接触しているが構わず黒で太らせている。

・灰色の濃さ
接触する点が多いほど薄くなっている傾向は分かるのだが、細かく見るとそう単純ではない。
「鵬」の月の中と、月と月の間は両方とも100%接触なのだが色が違う。率だけでなく、ドット数や分断の有無で変わるのだろうか。
「繭」の一番左の灰色は、5ドット中4ドット接触だが、100%接触の鵬のドットより色が薄い。

・ひとつづきに扱う範囲
「繭」の赤で示したドットは、真ん中と下は横線で隔てられているが同じ色で太っている。また上は白ドットで隔てられていて違う色で太っている。
白ドットで隔てられた時は別扱いかと思いきや、青で示したドットは同じ色で太っている。(ともに100%接触だが、ドット数が違えば色は変わるものと思われる)

そんなわけで詳しいアルゴリズムがずっと気になっているのだが、不思議な事にこのアルゴリズムについてネット上で情報を見かけない。Windows7当時から探しているのだが、本当に1つも見つからない。
何か情報があればぜひ教えて欲しい。

Post time : 2017年01月09日 18:49 │Comments(0) │文字│プログラム・アルゴリズム

浮動小数点数の10進指数表示のアルゴリズム
2016年12月28日 01:28

printfなどで浮動小数点数を10進指数表示するとき、倍精度では17桁の仮数で適切に出力すれば読み込んだ時元の値に戻ることが知られている。
この適切な出力アルゴリズムがどうなっているのか昔から気になっていた。

多倍長整数で1の位まで計算すれば明らかに正しい出力を出せるが、2進1024桁(10進308桁)だか何かそのレベルの桁数が必要になる。
最終的に17桁しか必要でないのに途中に308桁もの計算をするのはコストが大きく無駄に思える。他に方法が無いものだろうか。
log₂10ⁿだかlog₁₀2ⁿだかの表を(浮動小数点数で)持っておけば多数桁を保持すること無く10進指数表示ができそうだ。
しかしこれは表の値の精度に依存することになる。全ての値で正しい出力が出せるような気がしない。ちょうど丸めの境目あたりの数になった時に間違った出力にならないだろうか。

質問サイトに質問しても有用な回答が得られず悶々としていたのだが、先日偶然見つけたアルゴリズムの論文で疑問が氷解した。
「Printing Floating-Point Numbers Quickly and Accurately with Integers」
これによれば、
・1970年台～1980年台を通して多くのライブラリが誤った(wrong)表現を生成していた。
・Coonenが1980年と1984年の論文で拡張精度を使った正確(accurate)な手法を示したが広まらなかった。
　(拡張精度というとx87の80bit仮数のものが有名だ。8087の発売はちょうど1980年なのでこれを使ったのだろうか。)
・SteeleとWhiteの1990年の論文の多倍長整数を使うDragon4アルゴリズムが広まった。
という。

そしてこの論文で示されているアルゴリズムはGrisuという名で3種類あり、
・Grisu1は、入力の浮動小数点数の仮数の桁数より2bit以上多い整数を使い、正確な出力を返す。Coonenの手法の一般化。
・Grisu2は、正確かつGrisu1より短い出力を返す。
・Grisu3は、正確かつ最適(optimal)な出力を返すか、あるいはエラーを返す。

最適とはどういうことかというと、例えばGrisu1では、「0.3」(に相当するdouble)に対して「29999999999999998e-17」を出力する。(2.9999999999999998e-1って書き方のほうが馴染みがあるが本質に違いはない)
0.3と29999999999999998e-17はdoubleに変換した時同じ値になるので、どちらの表記も同じく正確である(accurate)。しかし、どうせなら短い「0.3」のほうで出してほしいと考えるのが自然だろう。
これはつまり、「同じ浮動小数点数に変換される10進表記が複数あるなら、仮数の桁数の少ない方を優先する」ということだ。加えて「同じ桁数なら、真の値に近い方を優先する」という条件も付けたものを最適(optimal)と呼んでいるようだ。

Grisu1のアルゴリズムだが、論文や実装「grisu.net」を見たところ特殊なことは何もやっていない。単純に、(入力より少し仮数の多い)自作の浮動小数点演算で適切な10の階乗を掛けてから10進変換しているだけのようだ。10の階乗の表を作るあたりの効率化に何かあるようだが、本質ではないので読んでいない。
これで正確な出力になる証明も、真面目に読んでいないが、たぶん地道に誤差の最大値を追っていっているだけだ。

Grisu3は、最適な出力を出せなければDragon4を使うというものだから、結局(あらゆる入力に対して)最適な出力を出すには多倍長整数演算を使わなければならないということになる。
テーブルメーカーのジレンマというやつだろうか。

以上より、冒頭の疑問に対する答えとしては、
・正確なだけでよければ仮数+2bitの精度の演算で単純なアルゴリズムで出力可能。1980年からある。
・最適も求めると多倍長整数を使うほかない(少なくとも2010年の時点では)。
ということになろう。
自分の直感はいい線をいっていたが、「正確だが最適でない」表記という考えが不足していた。

Post time : 2016年12月28日 01:28 │Comments(0) │プログラム・アルゴリズム

PCのキーボードのアーウが反応しなくなったあどうすえばよいか
2016年07月17日 04:34

PCのキーボードの「R」が反応しなくなったことをその「R」の使えないキーボードで打ったツイートが少し前に話題になっていた。

どーも　PCのキーボードのアーウが反応しなくないました
そう　Eの右どないのアーウです
Tのひだいどないのアーウです
ほあ
アーウが無いと全く文章になあない
偉大だったアーウ
あいがとうアーウ
サヨなあアーウ pic.twitter.com/frz3YY4jZm
— TAKE_FLOW (@TAKE_FLOW) 2016年6月13日

ここで反応しなくなったキーが「R」だというのが絶妙だ。
Rを使わないとアールと文字名を打つこともできず、アーウという間の抜けた字面になるのがよい味を出している。
これが
Aエー、Cシー、Eイー、Fエフ(EHU)、Gジー、Hエイチ(EITI)、Jジェー(ZYE-)、Lエル、Qキュー、Vブイ、Wダブリュー、Xエックス、Yワイ
　ではその文字を使わなくても文字名が打ててしまう。
Bイー、Pイー、Kエー
　ではE・Aに読めてしまい分かりづらい。
Dヒー、Tヒー
　は「ディー」や「ティー」の発音の中に存在しない「h」が出てきてしまい文字名に結びつきづらい。
Iア、Oー、Uｙ－
　この辺は情報が足りなすぎなんだか分からない。
Mエウ、Nエウ、Sエウ
　これらはなかなかよい。「Nのいぎどなりのエウ」などよい間の抜けぐあいだ。ただ3つのどれか分からないのは欠点か。
Zエット
　これもなかなか面白い響きだ。「Shiftの右隣のエット」「Xの左隣のエット」が打ててしまうのが多少残念。

さてそれはそうと、R(など英字キー)が打てなくなった時の対処法を考えてみよう。
なお当該ツイートの画像はMacっぽい気もするがMacはよく知らないので主にWindowsについて考える。

まずはRが打てなくなったことを伝えるために1回だけでいいから「R」の文字を入力する方法を考えよう。

色々あるが、面白いところからいくと、英単語をカナ表記から変換する方法がある。
MS-IMEでは例えば「かー」を変換すると「CAR」が出せるので、Rを打たなくてもRの文字を出せる。
他の文字も考えてみると例えば

B	…	らむ	→	LAMB
D	…	しゅみっと	→	SCHMIDT
I	…	らてん	→	LATIN
K	…	ないふ	→	KNIFE
M	…	あんばー	→	AMBER
N	…	こらむ	→	COLUMN
O	…	かむ	→	COME
P	…	れしーと	→	RECEIPT
S	…	きっず	→	KIDS
T	…	くりすます	→	CHRISTMAS
U	…	かっと	→	CUT
Z	…	ぴっつぁ	→	PIZZA

といった出し方があるだろう。
なおZは「じー」でも出たりする。

他に、どこかからコピペしてくる方法もある。
Webブラウザで「ASCIIコード表」など適当な語句で検索すれば見つかるだろう。

まともな方法では、IMEパッドの手書きや

文字一覧、

ソフトキーボードが使える。
IMEパッドのソフトキーボード

文字一覧と同様のもので、「文字コード表」もある。

名前を指定して実行から「charmap」…が打てないのでどうにかして探そう。

変わったところで、Alt+テンキーでの文字コード入力。
日本語WindowsではShift_JISの文字コードを入力する。Rなら0x52(=82)なので、Altを押しながらテンキーの8,2を順に押し、Altを離すとRが入力される。
またレジストリのHKEY_CURRENT_USER\Control Panel\Input Methodに文字列値「EnableHexNumpad」を作成し値を「1」にするとAltを押しながら「+」を頭につけた16進のUnicodeで入力できるようになる。Shift_JIS外の文字も打てるようになるし、文字コードはふつう16進で書かれるものなのでそのまま打てて便利である。

さてしかし「R」だけ打てても日本人は困る。「らりるれろ」を入力したい。
そんなときにはソフトウェアキーボードだ。
IMEパッドのソフトキーボードのかなモードを使って1文字づつ打つか、
IMEパッドのソフトキーボード(かな)

osk.exe「スクリーンキーボード」なら普通にR,Aと打って「ら」を入力することができる。

Windows+R…が使えないのでマウス操作で、名前を指定して実行から「osk」を実行。
O,S,Kが使えない時はマウス操作でなんとかしよう。
Windows8以降なら「タッチキーボード」も同様に使える。
タッチキーボードのアイコン

(それにしてもWindowsにはソフトウェアキーボードが多いな…)

さて何度も打ちたいときはこれではまどろっこしい。やはり物理キーボードを使いたい。
それならばMS-IMEのローマ字設定を変えよう。
使っていない例えばQやXあたりをラ行にあてればよいだろう。
(なおMacのことえりではデフォルトでLがラ行を打つのに使えたように思う。)
MS-IMEでローマ字の追加

ここでちょっとしたおまけで、例えば「QYA」で「りゃ」が打てる状態で、QYAで打った「りゃ」を1文字消して「り」になったものをF10で変換すると「RI」になってくれるので、Rキーを使わず「R」の文字を出すこともできる。

MS-IMEを使う方法は日本語入力時はよいが、IMEをオフの状態で入力しなければならない場合に困る。
面倒だがレジストリをいじってキー配置を変更するのが最終手段である。
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Keyboard Layoutにバイナリ値「Scancode Map」を作成し以下のようなフォーマットで書く。

dword 0;
dword 0;
dword length+1;
{
word scancode_out;
word scancode_in;
} * length
dword 0;

めったに使わない無変換やF1など適当なキーをRとして使うようにするとよいだろう。
例えばF1をRにするなら、F1のスキャンコードが0x3B、Rは0x13であるから、

00 00 00 00 00 00 00 00
02 00 00 00 13 00 3B 00
00 00 00 00

こうなる。
スキャンコードの表は検索すれば見つかるだろう。例えばここ。
なお注意点として、PS/2キーボードから送出されるスキャンコードとWindowsが内部的にScancode Mapに使っているスキャンコードは別物なので、「Scancode Mapに設定するための」スキャンコード表を探そう。
また、1ユーザーのみの設定がHKEY_CURRENT_USER\Keyboard Layout\Scancode Mapで昔はできたのだが7以降できなくなっただか環境によってできないだかという。実際Windows8.1で試してできなかった。
昔WindowsXPで1ユーザーのみの設定をした時の記事も参考になるかもしれない。
http://wentwayup.tamaliver.jp/e50134.html

以上、突然Rが反応しなくなった時にはぜひ試してみてほしい。

Post time : 2016年07月17日 04:34 │Comments(0) │文字コード│プログラム・アルゴリズム

ARMマイコンはじめました。
2016年05月28日 14:43

はじめました。2013年6月頃に。なぜ今頃書くかというと、9割書き上げて放置されていたのを今発掘したためだ。

その頃、LPC810というARMマイコンがでた。
8ピンDIPなのでブレッドボードに直接挿せるという。

これが秋葉原のマルツに入荷したというので早速買いに行った。

売り切れだった。

しかし上位種のLPC812は残っていたのでこれを買ってきた。
LPC812はピン数やメモリ容量、周辺機能といった全ての面でLPC810を上回っており、値段もあまり変わらない。今見ると25円差。当時もたぶんそれくらいだったと思う。
ただ1つだけ重大な欠点があり、パッケージがDIPではなくSOPで扱いづらい。
ハーフピッチのユニバーサル基板でピッチ変換してみたが、後悔した。めっちゃめんどい。
LPC812をハーフピッチ基盤にハンダ付け

秋月でちょうどいい変換基板が80円で売られているのでお勧めだ。

さてこの石はPICやAVRと違って専用の書き込み機が必要ないので出費が少なくて嬉しい。

書き込み用の接続は開発環境が無くても試せるのでまずこれを試す。

用意する物はシリアルポートと7404(NOT)か何かとあと抵抗。
自分はこんなこともあろうかとシリアルポート付きのPCを買っているが、きっとUSB-シリアル変換ケーブルでも大丈夫だと思う。
7404は要するに論理を反転できればいいので7400(NAND)とか7402(NOR)でもよい。自分が使ったのもNANDだ。
シリアルポートとの接続はこのページを参考に直結した。
軽く説明すると、シリアルポートの受信側インピーダンスは3kΩ～7kΩらしいのでそのための4.7kΩと、電圧が高いので電流を落とすための100kΩである。

この回路をLPC812のUSART0ポートに接続、そしてブートローダーを立ち上げるためにPIO0_1をGNDに落とす。
以上で準備は完了。
LPC812 をシリアルポート接続

電源を繋ぎ、適当なターミナルソフトからデータ8bit、パリティなし、ストップ1bit、速度任意の設定で「?」の1文字を送信する。
成功すれば「Synchronized<改行>」が表示されるはずだ。
LPC812_Symchronized

接続に成功したので次は開発環境のLPCXpressoIDEをいれる。登録とか要るのでまあ適宜なんとかする。
さらに書き込みソフトのFlashMagicをいれる。

IDEを立ち上げる
左下に「Quickstart Panel」があり、その中の「Start here」の中に「Import project(s)」
Examplesフォルダが開いてるのでその下から
\NXP\LPC800\NXP_LPC8xx_SampleCodeBundle.zip
のようなものを探してあとは適当に全部入れる。
Project Explorerを見ると色々入っている。BlinkyというモノがLEDを点滅させてくれそうだ。してみるとこれだけ入れればよかったか。まあいいや。
Blinkyを選んだ状態でメニューからProject→Build Projectを選択。
すると何やら動きだし、デバッグビルドができたようだ。リリースビルドの方が良かったかと切り替えてみたら何やらエラーが出た。まあデバッグで困ることもないしいいや。
さてビルドができたのでFlashMagicから書き込もうとしてみるが、できたファイルはaxfで書き込むためのファイルはhexのようだ。
調べてみるとどうやらaxfファイルはIDEから直接書き込んでデバッグとかするためのファイルのようで、hexファイルを出力するにはaxfから変換する必要があるようだ。めんどい。
http://support.code-red-tech.com/CodeRedWiki/OutputFormatsを参考に
下のバーの右手側にあるというプロジェクト名を探したら左側にあったが、気にせずCtrlクリック。
intel形式のhexファイルにしたいので
arm-none-eabi-objcopy -O ihex blinky.axf blinky.hex
を実行。失敗。ファイルが無いと言われる。
パスが違ってた。こうだな
arm-none-eabi-objcopy -O ihex debug/blinky.axf blinky.hex
今度は成功。思っていたところの1階層上に出力されたがまあいいや。

あとはFlashMagicで適に設定して書き込み。これは難なく成功した。
FlashMagicでLPC812に書き込み

ブートローダー設定用のGNDに落としたピンを外して電源を入れると
…動いた!
LPC812_blinky

3つのLEDが順番に消灯する。多分順番に点灯するべきなので、+-を間違っているようだがまあいいや。

その後TVにカラー出力など試していた
LPC812でNTSCカラー

が、命令プリフェッチの関係かクロック数がどう数えても合わないので力尽きた。
より困難な(プリフェッチ幅が広く、I/O命令が遅い)LPC1114でNTSCカラー出力を実現したPancake(IchigoJam周辺機器)はすごいと思う。尊敬する。

Post time : 2016年05月28日 14:43 │Comments(0) │マイコン│プログラム・アルゴリズム

SDカードから1セクタ読み取るまでの手順解説
2015年10月05日 01:09

数年前からマイコンでSDカードを読みたいと思い続けていたが、やっと実行に移した。(そしてそれをブログに書くまでに1ヶ月…)
使うマイコンはもちろん慣れ親しんだPIC。中でも最近一番のお気に入りの10F200…といきたかったのだが多少無理があったので12F510に。

	10F200	12F510
Flash	256ワード	1024ワード
RAM	16バイト	38バイト
I/Oピン	4本	6本

主に問題なのはI/Oピン数。SDの操作に4ピン使うので、10F200では他にピンが余らない。またFlash容量も心許ない。読み取りだけならなんとかなるにしてもデバッグ用に出力などする余裕が全くないだろう。

回路はこちら。単純につないだだけ。
回路写真

現在、第0セクタ512バイトを読んだところである。
SDカード_1セクタ読み出し

次はファイルシステムを解釈してファイルの読み書きをしようと思っているが、その前に今回得た知見をブログにまとめておくことにする。

まず参考資料。

1. https://www.sdcard.org/downloads/pls/simplified_specs/
数年前からSDカードの仕様は公開されている。完全な仕様書ではなく「Simplified」ではあるものの、れっきとした公式資料。
これが公開される前はマルチメディアカード(MMC)としてのコマンドで扱うしかなかった。SPIモード部分についてはMMCとSDは互換性があるのでそれでも扱えるのだが、4ピンを使う高速なSDカード本来のプロトコルは使えない。
この仕様書の公開によってついにSDカード本来のプロトコルが使えるように…なったかと思いきや実は足りない部分があってMMCの仕様書を見て埋めないといけないとも聞く。
まあとりあえず今のところSPIモードしか使うつもりはないので困らない。

2. MMC/SDCの使いかた
ChaNさんのサイト。日本語のサイトの中ではもっとも詳しく説明されていると思う。何度見たか分からない。

この2つの資料で分からない事はそのたびに適当に検索して調べていたのでどのサイトを見たかあまり覚えていない。
思い出せるところでこのへんか。
http://bluefish.orz.hm/sdoc/psoc_mmc.html
http://bitcraft.web.fc2.com/embedded/microchip/microchip.html

次にSDから1セクタ読むまでの手順…の前に色々解説。

SDのSPIモードでの操作は、(当たり前ではあるが)すべてSPIのプロトコルに則った通信で行われる。つまりすべての通信は1バイト単位で行われる。
そしてすべての通信は機器側がマスター、SDカードがスレーブで行われる。つまりSDカードが自発的にデータを送ってくることはなく、常にマスターがクロックを送ることでデータを読みだすことになる。
なおSPIは全二重の通信ができる規格だが、SDカードの操作では大抵どちらかがデータを出すときはもう一方はデータを出さない(0xFFを出す)。両方がデータを出しているのはデータパケットの受信を止める時くらいか。
SDモードでは1本のデータ線で半二重通信をするのでそれと合わせたのかもしれない。あるいはそもそも必要ないしそっちの方が楽ということかもしれない。
SPIモードに入ってからの通信はすべてコマンドを送信して返答を読み取るトランザクション単位で行われる。
そしてトランザクションはパケット単位で行われる。1つのトランザクションの流れは次のようになる。
・コマンド送信
・レスポンス受信
・(あれば)データ送信or受信
なおコマンド送信後すぐにレスポンスが読み取れるとは限らない。0xFFが読めた場合それを読み飛ばす必要がある。
1つのトランザクションが終わった後には1バイト以上のクロックを送信しなければならないという奇妙な仕様がある。
マスターはクロックをいつでも中断できる(ACMD41の最中を除く)。

コマンドは、6バイト固定で次のような構造をしている。
・1バイトのコマンド番号
　うち頭2bitはスタートビットと、通信方向を示すTransmission Bit
・4バイトの引数
・1バイトのCRC
　うち末尾1bitはEnd Bit(って書いてあるけどストップビットって名前のほうが馴染みがある)
1バイト単位なのにスタート・ストップビットがあるという奇妙な構造だが、1bit単位で通信を行うSDモードと共通化したためであろう。通信方向を示すのもSPIモードでは送受信に別の線が割り当てられているしCSもあるのだから不要である。
CRCはSPIモードでは基本的にはチェックされないため適当な値を入れればよいが、そうでないところもあり要注意だ。
レスポンスには以下の種類がある。
・R1: 1バイトで、単純な状態を返す。
・R1b: R1の後にビジー応答(連続したLowレベル)を返す。
・R2: 2バイトで、R1に加え詳細なエラー状態を返す。
・R3/R7: R1に加え4バイトの情報を返す。
・R4/R5: SDIOのための予約らしい。
・R6: どうやらSDモード専用のようだ。
データパケットは、任意バイト数のデータを1バイトのヘッダと2バイトのCRCで挟んだ構造である。
コマンドと異なりデータパケットのヘッダは先頭bitが0ではない。こちらはSPIモード専用なので1バイト単位で読む前提のようだ。

改めて、SDから1セクタ読むまでの手順。

・コマンド送信前の儀式
まずSDカードの電源を投入してから1ms待ち、74個以上のクロックを送ることでコマンドを受け付ける準備が完了する。
74とは中途半端だが、この時点ではSDモードなのでクロック数が8の倍数である必要がないためだ。もっともSPIで制御するなら切りよく80クロック送るのが楽だろう。

これ以下はSPIモードと考えて良い。

・CMD0 リセット
このコマンドは本来の機能の他にSPIモードへの切り替え機能を持っており、CSをLowにした状態で送ることでSDカードをSPIモードにすることができる。このコマンドを送信する時点ではSPIモードではないのだが、コマンド送信についてはSDモードとSPIモードでほぼ同じ形式なのでSPIモードのつもりで問題ない。
SDモードで使うときにはCSをHighでこのコマンドを送ることで、SPIモードのレスポンスとは違う何かが起こる(よく知らない)。
引数は任意と書かれているところと0固定と書かれているところがあってよく分からない。たぶん任意だと思うが、まああえて0以外を送る理由もない。
SPIモードでないためCRC必須。引数が0の場合CRCは0x95である(ストップビット含む)。
返答はidleフラグのみの立った「0x01」であるはずである。

・CMD8 インターフェースコンディション確認
引数は、0x000001XX。
XXは任意。0xAAが推奨されているが、私は0xABをおすすめする。これにすると、CRCの値をCMD0と同じにすることができる。
仕様書にはSPIモードでもCRC必須とある。
ネット上の情報では「CMD0のみCRC必須」と書かれているものがあるが、どうもCMD8はSDカードのver.2からできたコマンドのようで、それ以前はCMD0のみがCRC必須のコマンドだったせいで混乱しているように見える。
このコマンドは対応している電圧範囲を取得するコマンドであり、レスポンスはR7で引数に指定された電圧範囲に対応しているかと、上で「任意」と書いたチェックパターンがそのまま返ってくる。
ただ、これは全電圧範囲に対応しているか否かを調べるだけで、普通は対応しているし、対応していなかったらどうしようもないので、調べる意味はあまりない。
が、これを送ることでSDHC/SDXCはCMD58とCMD41を有効化するということなので、送信は必須のようだ。
なおこれはver2以降のカードの場合であり、それより前のカードでは不正コマンドとなり、返答はR1で「0x05」となる。つまりver2以降か否かを調べるという効果もある。
1バイトしか返答がないところ5バイト読むと、残りはデータ線がHighのままなので0xFFが読める(害はない)。

・CMD1またはACMD41 初期化
初期化コマンドは仕様書を読む限り、「CMD1を使うとMMCとSDの区別がつかないので非推奨」と読めるのだが、手元のいくつかのカードで試してみたところ、CMD1を受け付けないカードがいくつかあった。ACMD41を使わなければならないのだろうか。しかしそれではSDのSimplified仕様書が公開される前にMMCとして扱えていたという情報と矛盾するように思う。
なんにせよ今回使ったSDはCMD1に反応したので今回のコードではCMD1のままである。
CMD1は引数任意でレスポンスはR1。初期化が完了するまではidleを示す0x01、完了したらエラー無しの0x00が返る。
ACMD41の引数はホストのSDHC/XCサポートの有無を示すHCSの1bitのみ(他のbitは予約)、応答はR3でOCRレジスタの内容が返る。
idleでなくなるまでCMD1またはACMD41を送り続ける。

・CMD58 OCRレジスタ読み取り
レスポンスはR3で、32bitのOperation Conditions Registerの値を読み取る。内容は対応している電圧範囲、SDHC/SDXCか否かを示すbit、ビジーフラグ。電圧範囲はCMD8でも確認してこちらでも確認するのだろうか。よく分からない仕様だ。
なお今書いていて気づいたのだが、このコマンドはSDカードでは予約扱いになっており、OCR読み取りにはACMD41を使う前提のようだ。しかし使ったカードではきちんとレスポンスを返してくれた。よく分からない。

・CMD9 CSDレジスタ読み取り
Card-Specific Dataレジスタの値を読み取る。カードの容量など様々な情報が含まれている。
このレジスタはOCRレジスタと異なり16バイトあるためレスポンスの中身ではなくデータパケットとして送られてくる。
なお今回のコードではこの内容は読むだけで使っていない。

・CMD16 ブロックサイズ指定
SDHC/SDXCではこのコマンドは無視され512バイト固定だが、SDの一部でデフォルトが512バイトでない場合がありうるので必要らしい。
面倒なので今回のコードでは省略した。

・CMD17 1ブロック読み取り
このコマンドでカード本体の内容を読める。
引数は読み取り開始アドレス。
無印SDカードは1バイト単位、SDHCおよびSDXCはセクタ(512バイト)単位で指定する。
1ブロック分のデータパケットが得られる。

以下自分の悩んだ点をまとめておく

・CSの操作
1回のトランザクションごとにCSをHighに戻す。
つまり、CSをLowにアサート、コマンド送信、レスポンス受信、(データパケットがあれば送受信、)CSをHighに。
CSの動作として当たり前なのだろうが、これが確信が持てなくてだいぶ悩んだ。

・ダミークロック
トランザクションごとに1バイト分のダミークロックが必要。
ダミークロックについては仕様書の(SPIモードでなく)SDモードの部分に書いてある。
CSはHighでもLowでも構わないと書いてあるサイトがあった。とりあえずHighにしている。

・ACMDの処理
CMD55,CMDnのシークエンスをACMDnという。
それはいいのだが、CMD55と次のコマンドの間の処理がよくわからなかった。
CMD55を送って返答の1バイトが返ってくるまでで1トランザクション、ここでダミークロックまで送り、次のコマンド本体とその返答がまた1トランザクションということのようだ。

・クロック周波数
初期化中のクロック周波数は100kHz～400kHzと書かれているが、仕様書を読むともっと詳しく書かれている。
ACMD41を発行しカードの初期化が完了するまで、ホストは次の2つのうちどちらかを行わなければならない。
1) 周波数100kHz～400kHzの連続的なクロックを出力する
2) ホストがクロックを停止したいならば、50ms以内の間隔でACMD41によりビジービットをポーリングする
マイコンでSPIモードを使うならふつうクロックは断続的になるだろうから見るべきは2番の方である。
ところで50ms以内の間隔ならクロックは100kHzを下回ってもよいのだろうか。
よいならば最低クロックはACMD41とレスポンスで50msになる値、レスポンスが即時に返ってくるとして6+1+6+5=18バイト分なので、(18*8)/0.05=2880Hzということに…
なるかと思いきや、よく図を見るとトランザクション中の時間は50msに含まれていない。
SD仕様書_クロックの制限

するとクロックが50ms以上止まらなければよいのだろうか。であれば1/(50ms*2)=10Hz…?
これはちょっと実験してみたいところだ。
なお、ACMD41を除いてクロックは好きな時に停止してよいようだ。これは助かる。

・CRC
分からない。
色々な所を見たが、見る所ごとに書いてあることが違う(ように感じる)。
結局、ここのコードを中身を理解しないままJavaScriptに移植して使ったところ、思ったのと1bit違うところで答えが出たのでそのまま使った。
http://nabe.blog.abk.nu/0355

・自分のプログラムのバグ
他人の役に立つとは思えないが、面白いバグだったので書き留めておく。
起こった現象
初期化シーケンスに対する返答が順に以下のようであった。
CMD0に0x01が返る。idleフラグのみ立った状態であり、これは正しい。
CMD8に0x00FFFFFFFFが返る。つまり1バイト目はエラー無しを示しているのにその後に続くはずのデータが来ない。古いSDでCMD8に非対応だからだろうか。
CMD1に常に1回で0x00が返る。idle待ちがあるはずだが…まあきっと通信が遅いせいだろう。たぶんおかしくない。
CMD58に0x00FFFFFFFFが返る。つまりCMD8と同様エラー無しなのにデータが無い。

別のカードを使ってみると違う結果が返るものがあり、
CMD8に0x00000001AAが返るものがある。idleでないのが不可解だがデータは正しい。
CMD58に0x0080FF8000や0x0000FF80が返るものがある。これは正しい。

さて困った。正しいデータが返るものもあるのだから、SPIやシリアル通信のプログラムが間違っているとも思えない。

CMD58に返答が返るものを使えばとりあえず先に進めるのだからよく分からないがこれを使っておくか…
…と思ったが、色々考えてみるとやはりCMD8に0x00が返ってくるのはおかしい。非対応ならエラーフラグの立った0x05が返るはずである。
CMD1のidle待ちが無いのも不可解だ。いくら遅いとはいえ1ループ数ミリ秒で回しているのだが、このidle待ちは「数百msかかることがある」というもので、早くても数十msはかかるのではないか。

つまり、頭の1バイトだけなぜか0x00に化けているのではないか。しかしそんな都合のいいバグが…あった。
どういうバグかというと、
ダミークロックを送る関数でバンク0に用意したループカウンタを回すつもりだがバンクを変えておらず、
運良くシリアル送信との兼ね合いでバンク0にしていた1回目のCMD0を除き、みなバンク1の変数を回していた。
そしてそこにちょうど読んだデータの1バイト目があったため、カウントダウンしてループを抜けるときには常に0になっていたというわけだ。
ミッドレンジのPICならバンク切り替えの必要は無かったので、もっと余裕をもった石を使うべきだったかもしれない。(もっとも10F200でなく12F510にした時点で余裕をもったつもりだったのだが)

最後にコード
ページ0/1を両方使っているが、ページ1はメッセージだけなのでそれを除けば512バイトのPICにも収めることができる。まあそんなPICはほとんど無いのでできてどうするという話ではあるが。

・コード内訳
000-1FF メインコード・サブルーチン
200-2FF メッセージ
300-3FF 未使用
なおベースラインPICの仕様上ページの前半にしかCALLで飛べないため、サブルーチンの本体は後半に置きつつ前半に一度CALLしてからGOTOで本体に飛ばす構造になっている。

list p=12F510
#include p12F510.inc
radix dec

; 12F510
; Vdd+-v-+Vss
; GP5| |GP0 DAT
; GP4| |GP1 CLK
; (GP3)+---+GP2

;- /--
;CS |
;DI |
;Vss |
;Vcc | 表
;SCL |
;Vss |
;CO |
;- +---

variable env
env= _IOSCFS_ON
env&= _MCLRE_OFF
env&= _CP_OFF
env&= _WDT_OFF
env&= _IntRC_OSC
__config env

cblock 0x0A ;バンク共通
bitcnt, bytecnt, skipcnt
commdat, spioutbuf
;バンク0
flag
cnt0, cnt1, cnt2, cnt3
temp, temp2
arg0, arg1, arg2, arg3
msgptr
endc
;バンク1は読み取ったデータの保存領域

;ram alias

;bytecnt equ bytecnt

;flag bit
RXFLAG equ 0
TIMEOUT equ 1

MOSIPIN equ 0
MISOPIN equ 3
SCLKPIN equ 1
CSPIN equ 2
RXPIN equ 4
TXPIN equ 5
MORSEPIN equ 5
MOSIBIT equ 1<<MOSIPIN
MISOBIT equ 1<<MISOPIN
SCLKBIT equ 1<<SCLKPIN
CSBIT equ 1<<CSPIN
RXBIT equ 1<<RXPIN
TXBIT equ 1<<TXPIN

CMD equ 0x40
CRC_CMD08 equ 0x95
;CMD0: 40 00 00 00 00 と
;CMD8: 48 00 00 01 AB で兼用

#define flagWAIT STATUS,GPWUF
#define flagCMD8 STATUS,CWUF

;##### EntryPoint #####
org 0x00
goto init

;##### Subroutine Entry #####
;関数のcall先。ベースラインではページの前半しかcallできないためここにまとめてある。
;関数の本体はメインコードの後に置いてある。
txmsg232:
goto txmsg232core
getmsgbyte: ;これのみページ1へ飛ばす
bsf STATUS,PA0
movwf PCL
skipandread1: ;Wに1を入れてskipandreadn。すなわち1バイト読む
movlw .1
skipandreadn: ;0xFFのバイトを読み飛ばした後にNバイト読む
bsf flagWAIT
readn: ;Nバイト読む
goto readncore
skip2np1:
goto skip2np1core
skip2n:
goto skip2ncore
tx232hex:
goto tx232hexcore
;readresponse1:
; bsf respcnt,0
;readresponse:
; goto readresponsecore
sendnibble:
goto sendnibblecore
sendsdcmdarg0:
goto sendsdcmdarg0core
sendsdcmd:
goto sendsdcmdcore
;morse8:
; movwf dat
; goto f1
;morse:
; goto morsecore
;morsespace:
; ;interword(7)-interchar(3) =4
; movlw .8
; goto waithalfdit

readspi: ;SPIで0xFFを送信する
movlw 0xFF
spi:
goto spicore
tx232:
bsf GPIO,TXPIN ;0
bcf flag,RXFLAG
movwf commdat
goto tx232core
rx232:
btfss GPIO,RXPIN ;[0,3)
goto rx232
goto rx232core
rx232withtimeout:
bcf flag,TIMEOUT
rx232waitloop:
btfsc GPIO,RXPIN ;[0,5)
goto rx232core
incfsz cnt0,F
goto rx232waitloop
incf cnt1,F ;待ち時間を正しくカウントするために必要
btfsc GPIO,RXPIN
goto rx232core
incfsz cnt1,F
goto rx232waitloop
incf cnt2,F ;
btfsc GPIO,RXPIN
goto rx232core
incfsz cnt2,F
goto rx232waitloop
bsf flag,TIMEOUT
retlw 0

;##### Main Code #####
init
movwf OSCCAL

movlw b'10001000'
; /GPWU
; /GPPU=0: PullUp ON
; T0CS=0: Fosc/4,
; T0SE Don'tCare
; PSA Don'tCare
; PS2:0 Don'tCare
option

clrf ADCON0
bcf CM1CON0,C1ON

movlw MOSIBIT|CSBIT
movwf GPIO
movlw MISOBIT|RXBIT
tris GPIO

movlw 0x2A
movwf FSR
b12:
clrf INDF
bcf FSR,5
clrf INDF
bsf FSR,5
incfsz FSR,F
goto b12

initsd: ;1ms待ってから74個以上のクロックを出力
;wait 1ms
clrf cnt0
b9:
goto $+1
goto $+1
nop
decfsz cnt0,F
goto b9

movlw .5 ;10byte>74
call skip2np1

test:

;メッセージ出力
movlw msg_cmd0
call txmsg232

bcf GPIO,CSPIN

;CMD0を引数0で送信
movlw CMD|.0
call sendsdcmdarg0
;受信しつつ応答が来るまでスキップし、応答を1バイト読む
call skipandread1
;応答が来るまでにスキップした回数と受信内容を出力
decf skipcnt,W
call tx232hex
movlw ','
call tx232

movlw 0x30
movwf FSR
movf INDF,W
bcf FSR,5
call tx232hex
;CSをHighに
bsf GPIO,CSPIN
;1バイトダミークロック出力
movlw .0
call skip2np1

;CMD8で同様
movlw msg_cmd8
call txmsg232

bcf GPIO,CSPIN

movlw 0x01
movwf arg2
movlw 0xAB
movwf arg3
movlw CMD|.8
call sendsdcmd
;CMD8の応答は5バイト
movlw .5
call skipandreadn

bsf GPIO,CSPIN

movlw .0
call skip2np1

decf skipcnt,W
call tx232hex
movlw ','
call tx232
;5バイト出力。もうちょっとまともにやりたい。
movlw 0x30
movwf FSR
movf INDF,W
bcf FSR,5
call tx232hex
incf FSR,F
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex
incf FSR,F
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex
incf FSR,F
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex
incf FSR,F
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex

;CMD1。ACMD41を試してた名残りがある。
movlw msg_cmd1
call txmsg232

b13:

; movlw CMD|.55
; call sendsdcmdarg0
;
; call skipandread1
; bsf GPIO,CSPIN
; movlw 0x30
; movwf FSR
; movf INDF,W
; bcf FSR,5
; call tx232hex

bcf GPIO,CSPIN
movlw CMD|.1
call sendsdcmdarg0

call skipandread1
bsf GPIO,CSPIN

movlw .0
call skip2np1

movlw '/'
call tx232

decf skipcnt,W
call tx232hex
movlw ','
call tx232

movlw 0x30
movwf FSR
movf INDF,W
bcf FSR,5
movwf temp2
call tx232hex

movf temp2,W
btfss STATUS,Z
goto b13
;CMD58
movlw msg_cmd58
call txmsg232

bcf GPIO,CSPIN
movlw CMD|.58
call sendsdcmdarg0

movlw .5
call skipandreadn

bsf GPIO,CSPIN

movlw .0
call skip2np1

decf skipcnt,W
call tx232hex
movlw ','
call tx232

movlw 0x30
movwf FSR
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex
incf FSR,F
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex
incf FSR,F
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex
incf FSR,F
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex
incf FSR,F
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex
;CMD9
movlw msg_cmd9
call txmsg232

bcf GPIO,CSPIN
movlw CMD|.9
call sendsdcmdarg0
call skipandread1

decf skipcnt,W
call tx232hex
movlw ','
call tx232

movlw 0x30
movwf FSR
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex

movlw .16
call skipandreadn

decf skipcnt,W
call tx232hex
movlw ','
call tx232

movlw 0x30
b18:
movwf FSR
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex
incf FSR,F
movf FSR,W
andlw 0x1F
btfss STATUS,Z
goto b18

movlw .3
call readn

movlw 0x30
movwf FSR
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex
incf FSR,F
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex
incf FSR,F
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex

bsf GPIO,CSPIN

movlw .0
call skip2np1

;---
;CMD17
movlw msg_cmd17
call txmsg232

bcf GPIO,CSPIN
movlw CMD|.17
call sendsdcmdarg0
call skipandread1

decf skipcnt,W
call tx232hex
movlw ','
call tx232

movlw 0x30
movwf FSR
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex

movlw '/'
call tx232

call skipandread1

decf skipcnt,W
call tx232hex
movlw ','
call tx232

movlw 0x30
movwf FSR
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex

;512バイトを16バイトごとに受信して表示
movlw .512/.16
movwf cnt0
b17:
movlw msg_nl
call txmsg232

movlw .16
call skipandreadn

movlw 0x30
b16:
movwf FSR
bsf FSR,5
movf INDF,W
bcf FSR,5
call tx232hex
incf FSR,F
movf FSR,W
andlw 0x1F
btfss STATUS,Z
goto b16

bcf FSR,5
decfsz cnt0,F
goto b17

goto $

busychk: ;あれ、なんでこんなところに置いてあるんだろう。ページ前半でないとcallできない。
goto busychkcore

;##### Subroutine Core #####
busychkcore: ;ビジーチェック…のはずだけどどうやら使っていない。
call readspi
movf commdat,W
btfsc STATUS,Z
goto busychkcore
retlw 0

readncore: ;Nバイト読み取り
movwf bytecnt
movlw 0x30
movwf FSR
clrf skipcnt
readloop:
call readspi
btfss flagWAIT
goto f2
incf skipcnt,F
incf commdat,W
btfsc STATUS,Z
goto readloop
bcf flagWAIT
f2:
movf commdat,W
movwf INDF
incf FSR,F
decfsz bytecnt,F
goto readloop
bcf FSR,5
retlw 0

sendsdcmdarg0core: ;SDのコマンドを引数を0にして送信
clrf arg0
clrf arg1
clrf arg2
clrf arg3
sendsdcmdcore: ;SDのコマンドを送信
call spi
movf arg0,W
call spi
movf arg1,W
call spi
movf arg2,W
call spi
movf arg3,W
call spi
movlw CRC_CMD08
call spi
retlw 0

skip2np1core: ;2N+1バイト分のダミークロックを出力
bsf bitcnt,3
b14:
bsf GPIO,SCLKPIN
goto $+1
bcf GPIO,SCLKPIN
decfsz bitcnt,F
goto b14
skip2ncore: ;2Nバイト分のダミークロックを出力
movwf bytecnt
movf bytecnt,W
btfsc STATUS,Z
retlw 0
b11:
bsf bitcnt,3
b10:
bsf GPIO,SCLKPIN
goto $+1
bcf GPIO,SCLKPIN
goto $+1
bsf GPIO,SCLKPIN
goto $+1
bcf GPIO,SCLKPIN
decfsz bitcnt,F
goto b10
decfsz bytecnt,F
goto b11
retlw 0

spicore: ;SPI 1バイト送受信
movwf commdat
rrf GPIO,W
andlw ~(0x80|SCLKBIT>>1|CSBIT>>1|MISOBIT>>1)
movwf spioutbuf
; bcf GPIO,CSPIN

bcf STATUS,C
bsf bitcnt,3
spiloop:
rlf commdat,F
rlf spioutbuf,W ;CS:L SCLK:L MOSI<-C / c0
movwf GPIO
goto $+1
bsf GPIO,SCLKPIN
btfsc GPIO,MISOPIN
bsf commdat,0
decfsz bitcnt,F
goto spiloop

bcf GPIO,SCLKPIN

retlw 0

;### RS232C
;RS232Cシリアル関連のコード。

txmsg232core: ;文字列を送信
movwf msgptr
msgloop:
call getmsgbyte
bcf STATUS,PA0
movwf temp
andlw 0x7F
call tx232
btfsc temp,7
retlw 0
incf msgptr,F
movf msgptr,W
goto msgloop
retlw 0

tx232hexcore: ;1バイトを16進表記で送信
movwf temp
swapf temp,W
call sendnibble
movf temp,W
call sendnibble
retlw 0

sendnibblecore: ;下位ニブルを送信
andlw 0x0F
movwf commdat
movlw .6
addwf commdat,F
movlw '0'-.6
btfsc STATUS,DC
movlw 'A'-.10-.6
bsf GPIO,TXPIN ;0
bcf flag,RXFLAG
addwf commdat,F
goto tx232core

rx232core: ;1バイト受信。使っていない。
bsf flag,RXFLAG ;[4,7) mean5.5
movlw 0xFF
movwf commdat
goto $+1
; btfsc flag,BAUD300
; goto wait0r5a
;waitend0r5a:
goto $+1
goto $+1
goto $+1
goto $+1
goto $+1

;tx232:
; bsf GPIO,TXPIN ;0
; bcf flag,RXFLAG
; movwf commdat
; goto tx232core
tx232core: ;1バイト送信
nop ;5
bsf bitcnt,3

loop232:
goto $+1
; btfsc flag,BAUD300 ;ボーレートを115200と300で選べるようにしようと思ったが結局115200固定に。
; goto wait1b
;waitend1b:
goto $+1
nop
bcf STATUS,C
btfss GPIO,RXPIN ;read 28.5 +17n
bsf STATUS,C
rrf commdat,F
movf GPIO,W
andlw ~TXBIT
btfss STATUS,C
iorlw TXBIT
movwf GPIO ;send 20 +17n

decfsz bitcnt,F
goto loop232

; btfsc flag,BAUD300
; goto wait1c
;waitend1c:
;連続受信を極力早くするためここでreturn(2命令挟んで次のcallでストップビット中央)
btfsc flag,RXFLAG
retlw 0

goto $+1
goto $+1
goto $+1
goto $+1
goto $+1
goto $+1

bcf GPIO,TXPIN ;send　stop +17
goto $+1
; btfsc flag,BAUD300
; goto wait1d
;waitend1d:
goto $+1
goto $+1
goto $+1
goto $+1
nop
;連続送信で安全な時間空ける(1命令挟んで次のcallでストップビットが17サイクル)
retlw 0

;### morse
;デバッグ出力用にモールス信号を出力するコードを書いたが結局使わなかった。

;morsecore:
; movwf dat
;b3:
; decf cnt0,F
; rlf dat,F
; btfss STATUS,C
; goto b3
;f1:
; movlw .8
; addwf cnt0,F
;
;b4:
; ;bcf GPIO,OUTPIN
; rlf dat,F
; movlw .6 ;dah
; btfss STATUS,C
; movlw .2 ;dit
; movwf cnt2
;
;b5: ;2MHz,4*256cyc: ~1kHz
; movlw 1<<MORSEPIN
; decfsz cnt3,F
; goto b5
; xorwf GPIO,F
; decfsz cnt1,F
; goto b5
; decfsz cnt2,F
; goto b5
;
;;bsf GPIO,OUTPIN
;
;;1点間隔
; movlw .2
; movwf cnt3
;b7:
; ;4cyc,2MHz: .13sec
; nop
; decfsz cnt1,F
; goto b7
; decfsz cnt2,F
; goto b7
; decfsz cnt3,F
; goto b7
;
; decfsz cnt0,F
; goto b4
;
;;interchar(3)-interelem(1) =2
; movlw .4
;; goto waithalfdit
;
;waithalfdit:
; movwf cnt3
;b6:
; ;4cyc,2MHz: .13sec
; nop
; decfsz cnt0,F
; goto b6
; decfsz cnt2,F
; goto b6
; decfsz cnt3,F
; goto b6
; retlw 0

;メッセージ。最上位bitを立てることで終端を示している。ASCIIしか使えないが、\0終端と比べ1メッセージあたり1バイト節約できるのが利点。
;GBのアセンブラにあった機能を真似してみた。
org 0x200
msg_cmd0:
dt "\r\nCMD0 reset&SPI mode\r", '\n'|0x80
msg_cmd8:
dt "\r\nCMD8 >ver.2?\r", '\n'|0x80
msg_cmd1:
dt "\r\nCMD1 initialize\r", '\n'|0x80
msg_cmd58:
dt "\r\nCMD58 read OCR register\r", '\n'|0x80
msg_cmd9:
dt "\r\nCMD9 read CSD register\r", '\n'|0x80
msg_cmd17:
dt "\r\nCMD17 read single block\r", '\n'|0x80
msg_nl:
dt "\r", '\n'|0x80
end

Post time : 2015年10月05日 01:09 │Comments(1) │マイコン│プログラム・アルゴリズム

JavaScriptで生成した波形をHTML5のaudioで再生
2015年09月30日 00:02

タイトルの通り。
前々からやりたいと思っていたがやっとできた。
FirefoxとChromeで動作確認。IEはwavに非対応らしい。なんでじゃ。

//ArrayBufferを生成
var arrbuf = new ArrayBuffer(44100*2*5+44); //44.1kHz、2チャンネル、5秒、8bit +ヘッダ分
//ArrayBufferをUint8で扱う。せっかくなのでクランプ。
var uint8arr = new Uint8ClampedArray(arrbuf);
//wavヘッダ。各種データは決め打ち。
var head = [
0x52, 0x49, 0x46, 0x46, 0xC8, 0xBA, 0x06, 0, 0x57, 0x41, 0x56, 0x45, 0x66, 0x6D, 0x74, 0x20,
0x10, 0, 0, 0, 0x01, 0, 0x02, 0, 0x44, 0xAC, 0x00, 0x00, 0x88, 0x58, 0x01, 0x00,
0x02, 0, 0x08, 0, 0x64, 0x61, 0x74, 0x61, 0xA8, 0xBA, 0x06, 0
];

var i=0;
for( ; i<head.length; i++)
{
uint8arr[i] = head[i]; //ヘッダをArrayBufferに入れる
}
for( ; i<uint8arr.length; i++)
{
uint8arr[i] =~~(i%256)/3+128~~ (i%256-128)/3+128; //波形データ生成。鋸歯波。3で割ってるのはボリューム100%だとうるさいから。~~修正: 直流分出ちゃってました。~~
}

var blob = new Blob([arrbuf]); //ArrayBufferをBlobに

var bloburl = window.URL.createObjectURL( blob ); //BlobのURLを生成

document.getElementById("aud").src = bloburl; //URLをaudioのsrcに入れる

参考文献:
ArrayBufferとBlob
http://hakuhin.jp/js/array_buffer.html
http://hakuhin.jp/js/blob_url_scheme.html
WAV
http://www.web-sky.org/program/other/wave.php

Post time : 2015年09月30日 00:02 │Comments(0) │プログラム・アルゴリズム

Excelで浮動小数点数のビットパターン表示
2015年06月07日 20:51

Excel関数で浮動小数点数のビットパターンと数値の相互変換を組んでみた。
とりあえず単精度だけ。
Excelで浮動小数点数変換

4b3c614e
=INT(HEX2DEC(LEFT(A1))/8)
=MOD(INT(HEX2DEC(LEFT(A1,3))/8),256)-127
=MOD(HEX2DEC(RIGHT(A1,6)),2^23)
=(A4+2^23)*2^(A3-23)*-1^A2
=A4*2^(-126-23)*(-1^A2)
=IF(A4=0,IF(A2=1,"-∞","∞"),"NaN")
=IF(A3=128,A7,IF(A3=-127,IF(AND(A2=1,A6=0),"-0",A6),A5))
12345678
=IF(A9<0,1,0)
=INT(LOG(ABS(A9),2))
=ABS(A9)/2^(A11-23)-2^23
=ABS(A9)/2^(-126-23)
=IF(A9=0,0,IF(A11>(-127),A12,A13)+(MAX(A11,-127)+127)*2^23+A10*2^31)
=DEC2HEX(A14,8)
=IF(A9="-0","80000000",IF(A9="∞","7F800000",IF(A9="-∞","FF800000",IF(A9="NaN","7F800001",A15))))

使い方

上の式をコピーして、ExcelのA1セルに1行目が合うように貼り付ける。
Excelを持ってない人はLibreOfficeのCalcとかGoogleSpreadSheetとかGnumericとかお好きな表計算ソフトで。Excel固有の機能は特に使っていないのでどれでも動いた。
でもOpenOfficeのcalcは関数の区切りが","じゃなく";"だからそのままだと動かない。","を全部";"に置換すれば動いたけど面倒なのでおすすめしない。
あとGnumericもそのまま貼り付けたらテキスト扱いになっちゃっていちいち先頭の「'」を消さないといけなかったのでおすすめしない。
他に表計算ソフトって何かあったっけ。KingSoftOfficeは試していないけどMSOfficeとの互換性を売りにしてるし大丈夫だろう。
そういえばEeePC買った時にKingSoftOfficeのライセンスついてきたんだよな…。なんか結局使わずじまいだったなあ。
あとは…「ThinkFreeてがるOffice」ってなんか急に思い出したぞ。
…話がそれた。
貼り付けたら、A1セルに単精度浮動小数点数のビットパターンを16進8桁で入力するとA8セルに対応する数値が出る。
逆に、A9セルに数値を入れるとビットパターンがA16セルに出る。

入力は大文字小文字問わず。
出力はExcelで数値として扱えるものは数値で出力。
数値として扱えない-0、±無限大、NaNは文字で出力。
NaNのビットパターンは複数あるが、区別せず「NaN」と出力。

入力は数値として扱えるものは数値で、そうでないものは文字列で。
出力の16進数は大文字。NaNはどれが一般的なのか分からなかったので一番小さい7F800001にしてみた。

解説

それぞれの式で何をしているかを説明する。

=INT(HEX2DEC(LEFT(A1))/8)	符号部を取り出す
=MOD(INT(HEX2DEC(LEFT(A1,3))/8),256)-127	指数部を取り出し、ゲタ分を補正
=MOD(HEX2DEC(RIGHT(A1,6)),2^23)	仮数部を取り出す(ケチ表現はそのまま)
=(A4+2^23)2^(A3-23)-1^A2	正規化数だった場合の値を符号部と(ケチ表現を補正した)仮数部から計算 ※
=A42^(-126-23)(-1^A2)	非正規化数(および0)だった場合の値を符号部と仮数部から計算
=IF(A4=0,IF(A2=1,"-∞","∞"),"NaN")	無限大orNaNだった場合の値を符号部と仮数部から計算
=IF(A3=128,A7,IF(A3=-127,IF(AND(A2=1,A6=0),"-0",A6),A5))	指数部を見て上3つから適切なものを選択

※特殊値を扱わないなら4行目までだけでOK

=IF(A9<0,1,0)	符号部を生成
=INT(LOG(ABS(A9),2))	指数部を生成
=ABS(A9)/2^(A11-23)-2^23	正規化数だった場合の仮数部を生成
=ABS(A9)/2^(-126-23)	非正規化数(および0)だった場合の仮数部を生成
=IF(A9=0,0,IF(A11>(-127),A12,A13)+(MAX(A11,-127)+127)2^23+A102^31)	正規化数と非正規化数を場合分けしてまとめる
=DEC2HEX(A14,8)	16進数変換
=IF(A9="-0","80000000",IF(A9="∞","7F800000",IF(A9="-∞","FF800000",IF(A9="NaN","7F800001",A15))))	-0、±無限大、NaNの場合、直書きの文字列を出力。それ以外は上を出力

おまけ

JavaScriptで組んだら一瞬だった。TypedArrayって便利だね。
そもそもJavaScript自体便利。無限大("Infinity")もNaNも指数表記も扱ってくれる。扱えないのは-0だけかな。
なお動作確認はFirefox(38.0.5, Windows版)でしかしていない。おまけだし。

入力:

出力:

Post time : 2015年06月07日 20:51 │Comments(0) │プログラム・アルゴリズム

PICで浮動小数点ウェイトルーチン
2015年05月26日 00:00

ふと思いついたので書いてみた。
呼び出すと、Wレジスタの値を浮動小数点数として見た量だけウェイトを掛ける。
具体的には、指数部3bit、仮数部5bitで、
1.仮数×2^(指数+4)
または指数部が0の時
0.仮数×2^(1+4)
で表される値×80。
最小が1の時の80、最大が255の時の322560…かと思いきやちょうど上手く0の時に327680になっている。
グラフにするとこうだ。
PIC_浮動小数点ウェイト

さて、ふと思いついて面白そうだったので書いてみたのだが、使い道が思いつかない。
思いついたきっかけは液晶モジュールの初期化時に27μsと1msと200msのようなウェイト量を要求されたからなのだが、数回使うくらいなら固定値のウェイトルーチンで済むし、10回程度までは単純な2バイトのウェイトルーチンを作った方がよいだろう。
役立てるには数十回のダイナミックレンジの広いウェイトを要求される必要があるが、そのような状況が思いつかない。
まあ書いてて楽しかったので特に問題はない。

何か使い道を思いついた方はご自由に使ってください。

fwait:
;使用レジスタ:
;cnth, cntl, exp
;cnthは事前にゼロクリアのこと。

;浮動小数点数を分解して適切な場所に置いたりケチ表現解除
movwf cntl
andlw 0xE0
movwf exp
btfss STATUS,Z
bsf cnth,1
btfss cnth,1
bsf exp,5
btfsc cntl,4
bsf cnth,0
swapf cntl,F
movlw 0xF0
andwf cntl,F
bcf STATUS,C
;指数部が1xxなら4bit左シフト
btfss exp,7
goto f1x4
swapf cnth,F
swapf cntl,F
movf cntl,W
andlw 0x0F
iorwf cnth,F
movlw 0xF0
andwf cntl,F
f1:
;指数部がx1xなら2bit左シフト
btfss exp,6
goto f2x1
rlf cntl
rlf cnth
rlf cntl
rlf cnth
f2:
;指数部がxx1でなければ1bit右シフト
btfss exp,5
rrf cnth,F
btfss exp,5
rrf cntl,F
;素通りに掛かる時間分の調整
movlw .8 ;40/5
subwf cntl,F
btfsc STATUS,C
incf cnth,F ;繰り下がり処理しつつ+1
b0:
;時間待ち処理本体
;ここにウェイトを入れ、上の調整部分も合わせると、全体のウェイト量を定数倍できる
decf cntl,F
btfsc STATUS,Z
decfsz cnth,F
goto b0
nop ;時間調整
retlw 0
;分岐の時間合わせ
f2x1:
nop
goto f2
f1x4:
goto $+1
goto $+1
goto f1

Post time : 2015年05月26日 00:00 │Comments(0) │マイコン│プログラム・アルゴリズム

PICで平方根ルーチンができた気がする
2015年05月06日 23:32

なんとなく欲しくなったので作ってみたらできた気がする。

sqrt:
movlw 0x60
movwf diff
movlw 0x40
movwf subhnd
bsf count,3
sqrtloop:
movf subhnd,W
subwf valh,W
btfsc STATUS,C
movwf valh
movf diff,W
rlf vall,F
rlf valh,F
rrf diff,F
btfss vall,0
xorwf subhnd,F
btfsc vall,0
addwf subhnd,F
decfsz count,F
goto sqrtloop

19命令、固定124サイクル。
valh:vallに平方根を求める値を入れる。vallに答えが出る。
このルーチンに入る前にcountはゼロにしておく。

入力は16bitを受け付けてくれるかと思いきや、大きすぎると計算途中でオーバーフローするようである。
15bitなら多分大丈夫。もうちょっと大きくても大丈夫な気がする。0b1011...まで大丈夫な気がしたがそんなことはなかった。

アルゴリズム

平方根の求め方 - 魔法使いの森
こちらのタイガー計算器での開平計算のアルゴリズムを参考にした。
同じことを2進法で行うのだが、2進法なので引く数を増やしながら順に引いていくところは1回だけで終わりである。

具体的には、

・平方根を求める数をAとする
・B=1
{
・Aの2nビット目からBを引き、キャリーを答にシフト (そのまま使えるのでPICのボローは楽である)
・引けたなら、B++; B<<1; B++
・引けなかったなら、B--; B<<1; B++
・A<<2
}繰り返し

なお図形的に考えたものに合わせAとB両方シフトするように書いたが、実際にはAを1bitシフト、Bを右に伸ばしていくようなコードになっている。これはタイガー計算器でもそうである。
コードに落としこむにあたって、引けた時と引けなかった時の計算に使う値を1つにまとめたのと、キャリーを壊さずに後の方まで使いまわしているのが楽しいところ。
引く数は最後の方は下位bitを切り捨てているので答えが多少ずれるだろうと思っていたのだが、いくつか試したところずれていないような気がする。不思議だ。
(5/7追記: √0が1になった。やっぱりなー。この程度は想定の範囲内。)

Post time : 2015年05月06日 23:32 │Comments(0) │マイコン│プログラム・アルゴリズム

ゲームボーイ始めました。
2015年03月28日 13:04

ファミコン、Atari2600、GBAに続いて、ゲームボーイにも手を出してみた。

やっと最近の話になった。冒頭の画像ができたのが今年の2/11である。

GBは実機で動作させるのが簡単そうな気がするのが嬉しい点。
たぶんFlashROMを1個用意してカートリッジの線につなげばできると思う。
これがファミコンだと2個要るし、GBAだとなんだか特殊な回路が入ってるようなことを見た記憶がある。

CPUは80系ということで初めて触るCPUだった。
8080→8086→80x86なのでx86と同系統なのだが、x86は触ったことがあったがレジスタ名に多少面影を感じる程度であった。
新しいCPUのアセンブラを触るのは楽しいのでこれはこれでよい。

開発環境はググって見つけたGBDKというものを。
ルートに展開せよと書いてあるがどうせパスの日本語に非対応という事だろうといつもの場所に置いてみたが、どうもパスの指定の関係でルート直下でないと動かないようだ。
C言語コンパイラもついてるけど、やっぱりアセンブラだよねー。
アセンブラのサンプルコードも(1個だけ)ついてるので安心。

アセンブラの起動方法はなんだかんだで手間取ったが分かってみれば簡単だった。
..\bin\lcc -Wa-l -Wl-m -o temp.gb temp.s

ちょっと困ったことに、この開発環境でアセンブルすると先頭のヘッダあたりを自動で生成してくれるのだが、その中の割り込みハンドラ部分が使い方がよく分からない。
このようなことはよくある。
CPU自体の割り込みの扱いはそのCPUを使おうとしている時点で大抵理解しているし、分からなかったらいくらでも資料があるので調べればよいだけなのだが、ある特定の開発環境でだけ使われるコードなど知らないし、調べようにもその付属のドキュメントが不足していたらそれまでである。だいたい、CPUが使いたいのであって開発環境を使いたいわけでもないのに、それを調べなくてはいけないというのはなかなかやる気を殺がれるものである。
まあコードを追って一応使える程度には理解した。

GBの面白いところとして、全画面に任意の画像が「頑張れば」表示できるという点がある。
ファミコンのようにキャラクタ数が足りず明らかに不可能でもなく、
GBAのようにビットマップモードがあって容易に可能でもない。

GBの全画面を覆うには20*18=360キャラクタ必要。
しかしGBで背景面に一度に表示できるキャラクタ数は256個。普通には不可能。
だが、表示する256個のキャラクタは384個の内から2通りの選び方ができる。
これを、画面の中程で切り替えることで、全画面に任意の表示ができるのである。

それで全画面表示をしたのが冒頭の画像なのだが、ユニークタイル数を数えてみたら181。普通にも表示できた画像であった。
単純に減色した画像では芸がないと思って綺麗にベタ塗りにしたのが災いした。

なおGBカラーになると同時表示キャラクタ数が512個になるので全画面に別のキャラクタを表示することが容易に可能になる。その代わり色数の面で全画面任意とはいかなくなるのだが。

あと画像表示の前に試したハローワールド
ゲームボーイ_ハローワールド

と、7×7(8×8)ドットでは芸がないので5×7ドットのテキストを表示…してみようとしたが2文字で力尽きた。
ゲームボーイで5×7ドットフォント

あとエミュレータはGBAでも使っていたので何も考えずVisualBoyAdvanceを使ったが、どうもGBエミュレータではBGBなるものが再現度が高いようだ。

Post time : 2015年03月28日 13:04 │Comments(0) │プログラム・アルゴリズム│ゲーム機

Atari2600はじめました。
2015年03月24日 01:19

ファミコンとGBAに続き、Atari2600の開発を始めてみた。
…と思っていたのだが、Twitterのログやファイルの日付を見ると2011年5月あたり、GBAより前だった。やってすぐに書かないとこういうことになる。

Atari2600と聞いてもピンと来ない人もいるかもしれない、というか自分自身始める前はおぼろげに名前を聞いたことがあるかという程度だった。
日本では流行らなかったけれどアメリカの方ではファミコンの前世代機として一時代を築いた名機らしいのだが。

このAtari2600、当然(総合的な)性能はファミコンを大きく下回るわけだが、画面の描画方法が他のゲーム機には無い独特なもので、挑戦しがいのある機械である。
詳細な仕様については別に書こうかと思うが、ごく簡単にまとめると以下のようになる。 (4/13追記: 書いた→Atari2600詳細)
・画面解像度は横160ドット
・背景面は横4ドット単位でしか描けない
・スプライトは計5個
　横8ドットの絵が描けるものが2個
　横1ドットが3個
　(スプライトは複製or拡大できるが、詳細は割愛)

縦は? と思うだろうが、ここがAtari2600最大のポイント。なんとVRAMを走査線1本分しか持っていないため、何もしなければ縦縞しか描けない。絵を作るには1ラインごとにVRAMを書き換える必要がある。
さらに走査線の描画中でもお構い無しにVRAMを書き換えることができて、スプライトの3倍複製モードで描画するそばから書き換えることで6キャラクタ分48ドットの任意の画像を表示する高等テクニックがある。(実際にはそれだけでは書き換え速度が足りないので裏レジスタを使うというさらにひとひねり必要。詳細は割愛)

そのテクニックを使って描いたのが冒頭の画像。
Atari2600のCPUはファミコンと同じ6502(正確にはその機能削減版の6507)なのでプログラムは楽であった。
なお開発環境はdasm、エミュレータはz26。
dasmでアセンブルするとなぜか出力ファイルの頭に謎の2バイトが付いてそれを消さないとz26で動かなかった。なんだかよく分からないがとりあえず備忘録的に書いておく。

あとつい最近またAtari2600をやりたくなって描いた絵を2枚。
Atari2600で猫耳2

プログラムもちょこちょこ変えているが外見はただ絵が変わっただけ。下の数字はエミュレータの機能。
はちゅねミクの絵で分かる人には分かると思うが、次はアニメーションさせたい。

Post time : 2015年03月24日 01:19 │Comments(0) │プログラム・アルゴリズム│ゲーム機

このページの上へ▲

WentWayUp: WebLog

CDのピットの数2021年03月05日 23:32

6段のカレンダーが好きだ2020年11月15日 04:06

PIC16のDhrystone MIPSを測ろうとしてみた2020年04月29日 02:23

Conclusion

Twitterの画像の扱いがやっとまともになって嬉しい2019年06月23日 00:23

ファミコンで9×9ドット文字表示(ほか)2019年04月08日 02:02

謎の色名「honeydewtab」とlegacy color valueパース手順2018年03月24日 12:45

JPEG圧縮を繰り返しても際限なく劣化するわけではない2017年02月10日 01:47

ゲームボーイの吸い出し機を作った (後編)2017年01月16日 22:44

ファミコンで全画面に任意の画像(ただしモノクロ)を表示2017年01月14日 00:00

最近のWindowsのビットマップフォントの太字2017年01月09日 18:49

浮動小数点数の10進指数表示のアルゴリズム2016年12月28日 01:28

PCのキーボードのアーウが反応しなくなったあどうすえばよいか2016年07月17日 04:34

ARMマイコンはじめました。2016年05月28日 14:43

SDカードから1セクタ読み取るまでの手順解説2015年10月05日 01:09

JavaScriptで生成した波形をHTML5のaudioで再生2015年09月30日 00:02

Excelで浮動小数点数のビットパターン表示2015年06月07日 20:51

使い方

解説

おまけ

PICで浮動小数点ウェイトルーチン2015年05月26日 00:00

PICで平方根ルーチンができた気がする2015年05月06日 23:32

アルゴリズム

ゲームボーイ始めました。2015年03月28日 13:04

Atari2600はじめました。2015年03月24日 01:19

CDのピットの数
2021年03月05日 23:32

6段のカレンダーが好きだ
2020年11月15日 04:06

PIC16のDhrystone MIPSを測ろうとしてみた
2020年04月29日 02:23

Twitterの画像の扱いがやっとまともになって嬉しい
2019年06月23日 00:23

ファミコンで9×9ドット文字表示(ほか)
2019年04月08日 02:02

謎の色名「honeydewtab」とlegacy color valueパース手順
2018年03月24日 12:45

JPEG圧縮を繰り返しても際限なく劣化するわけではない
2017年02月10日 01:47

ゲームボーイの吸い出し機を作った (後編)
2017年01月16日 22:44

ファミコンで全画面に任意の画像(ただしモノクロ)を表示
2017年01月14日 00:00

最近のWindowsのビットマップフォントの太字
2017年01月09日 18:49

浮動小数点数の10進指数表示のアルゴリズム
2016年12月28日 01:28

PCのキーボードのアーウが反応しなくなったあどうすえばよいか
2016年07月17日 04:34

ARMマイコンはじめました。
2016年05月28日 14:43

SDカードから1セクタ読み取るまでの手順解説
2015年10月05日 01:09

JavaScriptで生成した波形をHTML5のaudioで再生
2015年09月30日 00:02

Excelで浮動小数点数のビットパターン表示
2015年06月07日 20:51

PICで浮動小数点ウェイトルーチン
2015年05月26日 00:00

PICで平方根ルーチンができた気がする
2015年05月06日 23:32

ゲームボーイ始めました。
2015年03月28日 13:04

Atari2600はじめました。
2015年03月24日 01:19