たまりば

  パソコン・インターネット パソコン・インターネット  三鷹市 三鷹市

ゲームボーイの吸い出し機を作った (後編)
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.マリオが読めた。
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ポケモンSilver_データ抜け2
このような分かりやすいバグった表示になるものなんだなあ。
なお部屋に出口がないので進めなかった。その後もう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の動作を再現する特殊なコントローラを積んでおり、普通のバンク切り換えとは異なるコマンドを入れる必要があるらしい。
色々試しているのだがまだ一切反応がない。一番つらい時期だ。
読み取りができたら、どうも書き込みも出来るらしいのでやりたい。自作ソフトを実機で動かすのは夢である。

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

  • ファミコンで全画面に任意の画像(ただしモノクロ)を表示
    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つの絵を表示することができる。
    00011011

    0111111111111100
    1111111111111111
    1111000000001111
    1111010101011110
    1111111111111111
    1111101010101111
    1111010101011111
    1111010101011110
    00011011

    0111111111111100
    1111111111111111
    1111000000001111
    1111010101011110
    1111111111111111
    1111101010101111
    1111010101011111
    1111010101011110
    00011011

    0111111111111100
    1111111111111111
    1111000000001111
    1111010101011110
    1111111111111111
    1111101010101111
    1111010101011111
    1111010101011110
    比較のために単一のパレットで表示したものがこちらだ。
    単一パレット表示

    次にキャラクタテーブル。
    「一度に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書き込み
    setChrRom:
        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

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

        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

    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

    waitInt:
        jmp waitInt

    ;色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

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

    ; 画像データ(BMP)
    ;    .bank 1
    ;    .org $A0C2
    ;    .incbin "bitmap.bmp" ; 画像。MSペイントなどで作成したモノクロビットマップ
    ;    .org $A100
    ;chr:
      

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

    MSゴシックのようなウェイト(太さ)が1種類しかないビットマップフォントをテキストエディタやHTMLなどで太字指定すると、自動生成された太字が表示される。
    単純な太字化アルゴリズムとして古くから用いられているのが横方向に1px太らせる手法で、WindowsでもXPまで長らく使われていた。
    単純な太字
    この手法の問題点は、1pxの隙間を開けて縦線が並んでいる箇所で隙間がつぶれてしまうことだ。
    「棚」「鵬」などの縦線の多い字を小サイズで表示すると黒い塊になってしまう。
    隙間が潰れる

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

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

    しかしこのアルゴリズムは思った以上に複雑で色々とわからない点がある。
    Windows太字の不明点
    ・黒にするか灰色にするかの判断
    単純に太らせると別の点に接触する場合は灰色なのかと思いきや、そうでない場合がある。例えば「棚」の赤で示した木偏の縦線は下2pxが隣の月に接触しているが構わず黒で太らせている。

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

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

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

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

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

    多倍長整数で1の位まで計算すれば明らかに正しい出力を出せるが、2進1024桁(10進308桁)だか何かそのレベルの桁数が必要になる。
    最終的に17桁しか必要でないのに途中に308桁もの計算をするのはコストが大きく無駄に思える。他に方法が無いものだろうか。
    log210nだかlog102nだかの表を(浮動小数点数で)持っておけば多数桁を保持すること無く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年の時点では)。
    ということになろう。
    自分の直感はいい線をいっていたが、「正確だが最適でない」表記という考えが不足していた。  

  • 【訂正・加筆】
    2016年12月06日 00:00

    2016/12/06 漢点字一覧表で、別の元データとの間で不一致があったので追記。
    2016/09/10 ネット契約を1Mbpsにしてみたの読み込み時間の記述が間違っていたので訂正。
    2016/09/04 ファミコンの縦解像度224px説の考察 左8pxを隠す機能の用途が思っていたのと違ったので追記。
    2016/06/06 Windows7でのペイントの劣化具合に新しく気づいたバグ情報を追加。
    2015/08/29 ベースラインPICの注意点で、型番の間違いを訂正、OPTION2の書き込み方法の間違いを訂正。
    2015/08/28 Windows7でのペイントの劣化具合に新しく気づいたバグ情報を追加。
    2013/09/26 5×5 ひらがなフォント5×5フォント改 / JavaScriptフォント表示機から5×5ドットフォント完成版に、思えばリンクを貼っていなかったのでリンク。
    2013/05/05 最弱のPICマイコンで電子オルガン_前編の単純ミスを1ヶ所修正。
    2013/04/27 文字コード表示機が特定の環境で動かない問題を修正、RTL文字での表示崩れを修正。
    2013/03/03 5×5ドットフォント完成版が紹介されていたので少々加筆しました。
    2012/11/18 ハロウィー?ンの正規表現に訂正・加筆があります。

    【このエントリについて】
    (2012/11/18)
    今まで、記事の内容にミスを見つけた場合はその記事だけ修正していたのですが、最新の記事はともかく古い記事にミスを見つけた場合は直しても気づかれないだろうと思って直すのが億劫になっていました。
    これではいけないと、どうするべきか考えた結果、訂正を知らせるエントリを1つ作ることにしました。
    記事を訂正した際にはこのエントリを更新して最上位に持ってくるように運用しようと思います。
    (2013/03/03)
    訂正だけに限らなかったので、エントリ名を【訂正】から【訂正・加筆】に変更しました。  
    タグ :お知らせ