QuickDrawが素早く楕円を描く手順を追う
2010年7月20日、QuickDrawのソースコードがダウンロード可能になったらしい。
QuickDrawは、Lisaや初代MacintoshからOS9の時代まで、Macの画面に見えるもの（ほとんど）すべてを描いていたGUIなOSの核となる描画プログラムだ。25年以上も昔から、角の丸い四角形を当然のように高速に描画していた。そのQuickDrawがどのように円を描いていたのか？以前の日記で思いを馳せたことがある。
奇数の数列の和が、二乗の数列になる（1 + 3 = 2^2、1 + 3 + 5 = 3^2、1 + 3 + 5 + 7 = 4^2、... ）ことを利用していることは分かっていたのだが、実際にどのように実装されていたのかは、想像するしかなかった...。それが今や、ソースコードをダウンロードして確かめることが可能になったのだ！これはもう確かめてみるしかない。早速、ソーコードをダウンロードしてみるが、さてどうなることやら...。
ソースコード
- ダウンロードしたソースコードはzip形式で圧縮されていた。
- 102658076_quickdraw_acc.zip
- 解凍すると、QuickDraw Sourceというフォルダに37に分かれたソースファイルが現れた。
- 事前の情報どおり、その内容はすべてアセンブラで書かれていた。*1
- つまり、CPUが直接実行するバイトコードを1対1で理解しやすい英単語に置き換えた、もっともCPU寄りな言語である。
- 逆に言えば、人間には最も理解し難い言語とも言える。
- その代わりに、CPUでは最も効率よく処理できるのだ。（但し、上手に書けば）
- まず、今の自分には、QuickDrawのアセンブラコード全体を正確に理解する能力は全くない。
- 但し、機能限定で特定の部分がどのような仕組みで実装されているかを探ることぐらいはできるかもしれない。
- 例えば、円・楕円を描画する仕組みを探ることぐらいは...。
目的のコードを探す
- 目的は、円・楕円を素早く描く仕組みを探ることである。
- その処理が、数あるソースファイルのどこに記載されているのか？特定する必要がある。
- その前に、QuickDrawをどのように利用するのか知る必要がある。
- QuickDrawで円・楕円を描くには、以下のように呼び出すようだ。
SetRect(tempRect,510,264,570,294); FrameOval(tempRect);
- これで、(y=510, x=264)と(y=570, x=294)を結んだ対角線を持つ、四角形に内接する楕円が描画されるようだ。
- ちょうど幅30px、高さ60pxの縦長の四角形に内接する楕円になる。
- もし、四角形が正方形なら円が描画されることになる。
- ちなみに、描画する時のペンサイズや色、パターン等も指定することもできる。
BackColor(whiteColor); ForeColor(redColor); PenSize(3,2); PaintOval(tempRect); FillOval(tempRect,myPattern);
- しかし、円・楕円を素早く描く手順とは関係ないので、その部分は追わないことにする。
- まず、Finderで「frameoval」を検索してみると、関係しそうな「Ovals.a」というファイルがヒットした。
- さらに「oval」でも検索してみると、関係しそうな「DrawArc.a」「PutOval.a」というファイルがヒットした。
- 3つのソースファイルをざっと眺めてみると...（サブルーチン呼び出しのJSRに注目して眺めてみた）
- FrameOval(tempRect);の呼び出しによって、Ovals.aのコードが実行され、
- Ovals.aの中で、PutOval.aとDrawArc.aが呼び出されている。
- そして、PutOval.aとDrawArc.aの中では、DrawArc.aに含まれるサブルーチンBUMPOVALも呼び出されている。
- どうもこのBUMPOVALが、円・楕円の座標を計算する核の部分となっているようだ。
CPUの基礎知識
- アセンブラを知るには、まずCPUの仕組みを理解する必要がある。
Motorola MC68000
- 演算とは...
- AND・OR・NOT等の論理演算
- ビット列を左右に動かすshift操作
- 加減剰余の計算
- CPUは、演算を行うためにメモリから値を読み取って、
- 演算結果を再びメモリに書き込んでいると言える。
- あるいは、レジスタにそのまま残して、次の演算に利用している。
- レジスタD0〜D7は、まさにその演算を実行する目的のレジスタである。（C言語の変数のような役割）
- レジスタA0〜A7は、メモリのアドレス番地を示す目的のレジスタである。（C言語のポインタのような役割）
- D0からD7レジスタは4バイトのサイズだが、2バイト、あるいは1バイトに制限して扱うことができる。
- A0からA7レジスタも4バイトのサイズだが、2バイトに制限して扱うことができる。（1バイトは扱えない）
- その中でもA7レジスタは特別で、CPUが利用するスタックポインタとしての役割が与えられている。
- メモリは先頭から1バイト（8ビット）ごとに区切られて、0から順にアドレスが付番されている。
- CPUは基本的にメモリにある実行コードを順番に読み取って実行する。
- 現在実行中のアドレスは、プログラムカウンタ（レジスタPC）が指し示している。
- 通常、プログラムカウンタは、メモリから実行コードを1バイト読み込む度に1加算され、次に実行するアドレスを指し示す。
- このプログラムカウンタに任意の値を書き込むと、CPUの処理の流れを変更できる。（分岐）
- 二つの値の比較によって、条件分岐することもできる。（等しい・小さい・大きい時に分岐する）
- また、分岐する前にプログラムカウンタの値をスタック（スタックポインタが指し示すアドレスのメモリ）に保存して分岐することもある。
- つまり、CPUは時々処理の流れを変えながら、メモリから値を読んで、レジスタで演算して、メモリに書き戻す。
- CPUが処理できることは以上である。非常にシンプルだ。
- マルチタスクといっても、CPUにとっては常に一つの処理を超高速で実行しているだけ。
- オブジェクト指向なプログラムも、CPUにとっては単なるサブルーチン呼び出し。
- あくまで、人間から見るとマルチタスクやオブジェクト指向に見えるだけなのだ。
- 今この瞬間もブログを書きながら、日本語変換という高度な処理もこなしている。
- 裏ではMail.appが稼働し、メールが届けばGrowlが通知してくれる。
- もはや奇蹟のように感じてしまう...。
- このような高度で複雑な処理がいくつも、裏で並列処理されていることが。
- 実体はレジスタ同士の演算でしかないはずなのに。
CPUの外側の世界とのやり取り
- では、CPUの世界はレジスタとメモリだけなのに、なぜ画面にウィンドウが表示され、文字や図形まで表示されるのか？
- それは、VRAM（ビデオRAM）と呼ばれる、画面上のピクセルと連動した特別なメモリが割り当てられていて、
- そのメモリに値を書き込むことで、画面上のピクセルの点灯・消灯がコントロールされる仕組みのようだ。
ちなみに...
- ハードディスクなら、特定のメモリに値を書き込むことで、ヘッドの位置が移動して、目指す場所に磁気データが記録される。
- キーボードなら、特定のメモリの値を読み取ることで、タイプされたキーコードが確認できる。
- CPUにとっては、あくまでも単なるメモリアクセスである。
- それが、外部機器と連動したメモリ領域においては、外部機器がコントロールされたり、外部機器からの入力値を受け取ることができるのだ。
アセンブラの基礎知識
MOVE.L #$1000,A3 ;16進数の値$1000を、A3レジスタに代入する MOVE.W A3,D1 ;A3レジスタの値$1000を、D1レジスタに代入する MOVE.W (A3),D1 ;A3レジスタの値をアドレスと解釈し、メモリ$1000番地の値を、D1レジスタに代入する MOVE.B $F(A3),D2 ;A3レジスタの値をアドレスと解釈し、メモリ$100F番地の値を、D2レジスタに代入する MOVEM.L D1-D5/A0-A2,(A3) ;レジスタD1〜D7とA0〜A2の値を、メモリ$1000番地から書き込む MOVEM.L (A3),D1-D5/A0-A2 ;メモリ$1000番地から読み出し、レジスタD1〜D7とA0〜A2に代入する MOVE A3,-(SP) ;A3レジスタの値を、SPの値を-4したアドレスに書き込む
- MOVE.L、MOVE.W、MOVE.Bの違いは、読み込むデータのサイズが違ってくる。
- .Lが付くと、4バイトのデータサイズ。（ロングワード）
- .Wが付くと、2バイトのデータサイズ。（ワード）
- .Bが付くと、1バイトのデータサイズ。（バイト）
- 「;」セミコロンより右側はコメント扱い。生成される実行コードには影響しない。
- 「.」で始まるのは疑似命令。CPUが実行する命令ではなく、アセンブラがコンパイルする時に利用する。
- アセンブラ未定義の英字で始まる単語はラベルである。
例：ラベル
CLR D0 MOVE.B #100,D1 LOOP ADD.L D1,D0 DBRA D1,LOOP ;D0を1減らし、0以上ならLOOPを続ける
- ラベルは、アセンブラが実行コードを生成する時に、分岐先のアドレスを計算する目印として利用される。
- 上記では、カウンタとしてD1レジスタに100を設定して、-1しながら0になるまでLOOP間を100回繰り返す。
- つまり、LOOPを抜けた時に、1から100までの数列の和「5050」がD0に代入されているはず。
例：.EQU
OVALTOP .EQU 0 ;INTEGER OVALBOT .EQU OVALTOP+2 ;INTEGER
- また、.EQUを利用して、ラベルに任意の値を設定することもできる。
- まず、疑似命令.EQUによって、OVALTOPというラベルに「0」が設定される。
- すると、以降のコードにOVALTOPを見つけると、その部分を「0」と解釈する。
- つまり、次の行は「OVALBOT .EQU 0+2」と同義である。
- さらに、数式は計算されるので「OVALBOT .EQU 2」と同義である。
- よって、OVALBOTというラベルに「2」が設定される。
以上、かなりいい加減な理解だが、基礎知識を身に付けた。実際、CPUやコンピュータの仕組みは、詳細に見るともっと複雑なはず。アセンブラの言語仕様は、全く違っているかもしれない。しかし、QuickDrawのソースコードを読む目的においては、上記の知識でそれなりに役立ちそうである。
追跡 Ovals.a
それでは、CPU・アセンブラに関する若干の知識を仕入れて、より具体的に見ていくことにする。
- 以下のコードは、点(x=200, y=100)と(x=210, y=110)を対角線に持つ四角形に内接する円を描く。
- 四角形の幅は10、高さ10になるので、正方形ということになる。
- また、中心座標(x=205, y=105)、半径5の円ということになる。
SetRect(tempRect,100,200,110,210); FrameOval(tempRect);
- このようにしてQuicDrawのFrameOvalを呼び出した時に、処理がどのように進んでいくか、実際に追ってみた。
入り口
- Finderで「frameoval」を検索すると、アセンブラコードのファイル「Ovals.a」がヒットする。
- Ovals.aをCotEditorで開いて、さらに検索すると、84行目の行にジャンプした。
;---------- Ovals.a 84行目 ---------- .PROC FrameOval,1 .DEF CallOval,PaintOval,EraseOval,InvertOval,FillOval .REF StdOval ;----------------------------------------------------- ; ; PROCEDURE FrameOval(* r: Rect *); ; MOVEQ #FRAME,D0 ;VERB = FRAME BRA.S CallOval ;SHARE COMMON CODE
- どうやら「.PROC FrameOval,1」が入り口を示すラベルになっているようだ。（.PROCの意味は分からない）
- カンマ「,」に続く1は、1個の引数をとることを表現しているようだ。
- 実際の処理は、ラベルであるFRAMEの値を、D0レジスタに代入して、CallOvalにジャンプしている。
- では、FRAMEの値は何だろう？と思って検索してみると、その定義は「GrafType.a」の14行目にあった。
;---------- GrafType.a 10行目 ---------- ;----------------------------------------------- ; ; QuickDraw VERBS: ; FRAME .EQU 0 PAINT .EQU 1 ERASE .EQU 2 INVERT .EQU 3 FILL .EQU 4
処理の振り分け
- 上記のコードが一体何を意味するのかは、「Ovals.a」のFrameOvalに続くコードを見てみると想像がついた。
;---------- Ovals.a 95行目 ---------- ;----------------------------------------------------- ; ; PROCEDURE PaintOval(* r: Rect *); ; PaintOval MOVEQ #PAINT,D0 ;VERB = PAINT BRA.S CallOval ;SHARE COMMON CODE ;-------------------------------------------------------- ; ; PROCEDURE EraseOval(* r: Rect *); ; EraseOval MOVEQ #ERASE,D0 ;VERB = ERASE BRA.S CallOval ;SHARE COMMON CODE ;-------------------------------------------------------- ; ; PROCEDURE InvertOval(* r: Rect *); ; InvertOval MOVEQ #INVERT,D0 ;VERB = INVERT BRA.S CallOval ;SHARE COMMON CODE ;-------------------------------------------------------- ; ; PROCEDURE FillOval(* r: Rect; pat: Pattern *); ; FillOval MOVE.L (SP)+,A0 ;POP RETURN ADDR MOVE.L (SP)+,A1 ;POP ADDR OF PATTERN MOVE.L A0,-(SP) ;PUT RETURN ADDR BACK MOVE.L GRAFGLOBALS(A5),A0 ;POINT TO LISAGRAF GLOBALS MOVE.L THEPORT(A0),A0 ;GET CURRENT GRAFPORT LEA FILLPAT(A0),A0 ;POINT TO FILLPAT MOVE.L (A1)+,(A0)+ ;COPY PAT INTO FILLPAT MOVE.L (A1)+,(A0)+ ;ALL EIGHT BYTES MOVEQ #FILL,D0 ;VERB = FILL BRA.S CallOval ;SHARE COMMON CODE
- 似たような処理が、PaintOval、EraseOval、InvertOval、FillOvalというラベルに続いている。
- これらはすべてQuickDrawの楕円を描くコマンド名と一致している。
- FrameOval.....楕円の境界線を描く。（ペンの色・パターンで描く）
- PaintOval......楕円を塗りつぶす。（ペンの色・パターンで塗りつぶす）
- EraseOval......楕円を消す。（ペンの背景色・パターンで塗りつぶす）
- InvertOval......楕円内部のピクセル値を反転する。
- FillOval......楕円を塗りつぶす。（指定したパターンで塗りつぶす）
- おのおの楕円をどう描くかという「動詞」の違いを、0〜4の値としてD0レジスタに代入して、CallOvalに分岐している。
- おそらく、楕円に対する似たような処理なので、コードの重複を抑えるために、このように処理していると考えられる。
CallOval
- 共通の処理CallOvalでは、以下のコードが実行される。
;---------- Ovals.a 140行目 ---------- ;--------------------------------------------------------------- ; ; PROCEDURE CallOval(r: Rect); ; ; code shared by FrameOval, PaintOval, EraseOval, InvertOval, and FillOval. ; enter with verb in D0. ; CallOval MOVE.L (SP)+,A0 ;POP RETURN ADDR MOVE.L (SP)+,A1 ;POP ADDR OF RECT MOVE.B D0,-(SP) ;PUSH VERB MOVE.L A1,-(SP) ;PUSH ADDR OF RECT MOVE.L A0,-(SP) ;RESTORE RETURN ADDR MOVE.L GRAFGLOBALS(A5),A0 ;POINT TO LISAGRAF GLOBALS MOVE.L THEPORT(A0),A0 ;GET CURRENT GRAFPORT MOVE.L GRAFPROCS(A0),D0 ;IS GRAFPROCS NIL ? LEA STDOVAL,A0 BEQ.S USESTD ;YES, USE STD PROC MOVE.L D0,A0 MOVE.L OVALPROC(A0),A0 ;NO, GET PROC PTR USESTD JMP (A0) ;GO TO IT
- まず、スタックに「動詞の区分値0〜4」を追加している。
- このルーチンでは、「LEA STDOVAL,A0」「BEQ.S USESTD」を経過して、最終的に「JMP (A0)」される。
- つまり、A0レジスタにはSTDOVALのアドレスが代入されるので、処理はSTDOVALに分岐するのである。
- 分岐する前の何回かのMOVE操作は、GRAFPROCSがnilかどうかを調べるための処理のようだ。
- おそらく、GRAFPROCSがnilという状態が一般的なのだと想像する。
- もし、GRAFPROCSがnilでなければ、A0レジスタの値を書き換えて、OVALPROCのアドレスへ分岐する。
- OVALPROCの処理がどこに分岐して、どのような意味があるのかまでは分からなかった...。
- しかし、円・楕円を描画する仕組みを探る、という目的においては、STDOVALの処理を調べるだけで十分だと考え、
- OVALPROCの処理の処理については、これ以上追跡しなかった。
StdOval（引数の受け渡し・ローカル変数領域の確保）
- StdOvalのコードは「LINK A6,#VARSIZE」で始まる。
- LINK命令は複合命令で、以下の処理と同等である。
- これらの処理によって、A6レジスタで参照可能な変数領域が4バイト確保される。（VERSIZE=-4なので）
- 利用する時は「MOVE D0,OVWD(A6)」「MOVE D0,OVHT(A6)」のように使う。
;---------- Ovals.a 18行目 ---------- ;--------------------------------------------------------------- ; ; PROCEDURE StdOval(verb: GrafVerb; r: Rect); ; ; A6 OFFSETS OF PARAMS AFTER LINK: ; PARAMSIZE .EQU 6 VERB .EQU PARAMSIZE+8-2 ;12 GRAFVERB RECT .EQU VERB-4 ; 8 LONG, ADDR OF RECT OVWD .EQU -2 ;-2 WORD OVHT .EQU OVWD-2 ;-4 WORD VARSIZE .EQU OVHT ;-4 TOTAL BYTES OF LOCALS LINK A6,#VARSIZE ;ALLOCATE STACK FRAME MOVEM.L D7/A3-A4,-(SP) ;SAVE REGS MOVE.B VERB(A6),D7 ;GET VERB JSR CHECKPIC ;SET UP A4,A3 AND CHECK PICSAVE BLE.S NOTPIC ;BRANCH IF NOT PICSAVE
- 「MOVEM.L D7/A3-A4,-(SP)」D7、A3〜A4レジスタの値をメモリのスタック領域に保存する。
- 「MOVE.B VERB(A6),D7」描き方の動詞の区分の値をD7レジスタに代入する。
- ところで、VERB(A6)によって何故、描き方の動詞の区分にアクセスできるのか？考えてみた。
- 事前のCallOvalの処理で、すでにスタックには以下の値が保存されている。
- 「描き方の動詞の区分」=VERB
- 「楕円に外接する四角領域へのアドレス」=RECT
- 「戻りアドレス」
- そして、現在までの処理を考えてスタック領域の区分を想像すると、以下のようになる。
$00000000側 ┌──────────────┐← -4 │ＯＶＨＴ （２）│ ├──────────────┤← -2 │ＯＶＷＤ （２）│ Ａ６→├──────────────┤← 0 │古いＡ６の値（４）│ ├──────────────┤← +4 │戻りアドレス（４）│ ├──────────────┤← +8 │ＲＥＣＴ （４）│ ├──────────────┤←+12 │ＶＥＲＢ （２）│ └──────────────┘ $FFFFFFFF側
- .EQUのラベル定義と関連づけて考えると、理解できた。（右側コメントの先頭に、数式の計算結果を追記した）
;---------- Ovals.a 24行目 ---------- PARAMSIZE .EQU 6 VERB .EQU PARAMSIZE+8-2 ;12 GRAFVERB RECT .EQU VERB-4 ; 8 LONG, ADDR OF RECT OVWD .EQU -2 ;-2 WORD OVHT .EQU OVWD-2 ;-4 WORD VARSIZE .EQU OVHT ;-4 TOTAL BYTES OF LOCALS
- VERB(A6)は、A6レジスタの指し示すアドレスに+12したアドレスになる。
- そこには、事前にCallOvalで保存した「描き方の動詞区分」が存在するのだ。
- このように、スタックは、A6レジスタの指し示すアドレスを中心に、ローカル変数・引数の受け渡し領域として活用されることが多い。
StdOval（PutOvalとDrawArcの呼び出し）
- 続く処理は、NOTPICに分岐すると決め打して、処理を追い続ける。
- Pictures.a 1556行目のCHECKPICの処理は追わなかった。
;---------- Ovals.a 47行目 ---------- NOTPIC MOVE.L RECT(A6),A0 ;POINT TO RECT（47行目） MOVE RIGHT(A0),D0 SUB LEFT(A0),D0 MOVE D0,OVWD(A6) ;OVWD := R.RIGHT - R.LEFT MOVE BOTTOM(A0),D0 SUB TOP(A0),D0 MOVE D0,OVHT(A6) ;OVHT := R.BOTTOM - R.TOP MOVE.L A0,-(SP) ;PUSH ADDR OF RECT（55行目） TST.B D7 ;IS VERB FRAME ? BNE.S NOTFR ;NO, CONTINUE TST.L RGNSAVE(A3) ;YES, IS RGNSAVE TRUE ? BEQ.S NOTRGN ;NO, CONTINUE MOVE.L A0,-(SP) ;YES, PUSH ADDR OF RECT（61行目） MOVE.L OVHT(A6),-(SP) ;PUSH OVWD, OVHT MOVE.L RGNBUF(A4),-(SP) ;PUSH RGNBUF PEA RGNINDEX(A4) ;PUSH VAR RGNINDEX PEA RGNMAX(A4) ;PUSH VAR RGNMAX JSR PutOval ;ADD AN OVAL TO THERGN NOTRGN MOVE.B #1,-(SP) ;PUSH HOLLOW = TRUE（68行目） BRA.S DOIT NOTFR CLR.B -(SP) ;PUSH HOLLOW = FALSE DOIT MOVE.L OVHT(A6),-(SP) ;PUSH OVWD,OVHT JSR PushVerb ;PUSH MODE AND PATTERN CLR -(SP) ;PUSH STARTANGLE = 0 MOVE #360,-(SP) ;PUSH ARCANGLE = 360 ; DrawArc(r,hollow,ovWd,ovHt,mode,pat,startAng,arcAng); JSR DrawArc ;（78行目） MOVEM.L (SP)+,D7/A3-A4 ;RESTORE REGS UNLINK PARAMSIZE,'STDOVAL '
- 最初のブロックで、RECTの座標を元に、OVWD（楕円の幅）とOVHT（楕円の高さ）を求めている。（47行目〜）
- 次のブロックでは、描画方法がFrameOvalかどうかを判定している。（55行目〜）
- FrameOvalであれば、スタックに引数を設定して、PutOvalをサブルーチン呼び出ししている。（61行目〜）
- 続く処理は、DrawArcをサブルーチン呼び出しする前の引数設定。（68行目〜）
- 楕円描画においては、最終的にすべての描画方法でDrawArcを呼び出して描画しているようだ。（78行目〜）
追跡 DrawArc.a
- 楕円を描く仕組みはDrawArc.aにあるはずなのだが、コードのボリュームが1000行以上あり、かなり長い。
- 角が丸い長方形や円弧を描く時にも呼び出されるので、それに対応するために多機能になっているようだ。
- すべてのコードを詳細に追うと時間がかかり過ぎてしまう...。
- そこで、全体のコードの流れを確認して、楕円描画の核の部分だけ詳細に追ってみることにした。
- 0001行目〜0100行目、.EQUによるラベル定義
- 0103行目〜0588行目、変数領域の確保、引数へのアクセス、変数領域やレジスタの初期設定などをしている。
- 383行目（OUTEROVAL用）・432行目（INNEROVAL用）と分けて、INITOVALを2回呼び出している。
- 0597行目〜0837行目、楕円描画ループ（NEXTROW）
- 604行目（OUTEROVAL用）・607行目（INNEROVAL用）と分けて、BUMPOVALを2回呼び出している。
- 0898行目〜0998行目、INITOVAL（楕円の描画状態を記録する領域を初期化する）
- 1003行目〜1081行目、BUMPOVAL（水平方向にスキャンして、楕円の境界座標を計算する）
なぜ、OUTEROVAL（外側の楕円）用・INNEROVAL（内側の楕円）用と分けているのか？
- QuickDrawでは、幅と高さを持った四角形のペンサイズを指定できる。
- FrameOvalの場合、外接四角形の内側に、ペンサイズの太さで楕円の境界ラインを描くことになる。
- ペンサイズの太さの境界ラインを描く方法として、最初に外側の楕円の座標を求める。（OUTEROVAL）
- その後、ペンサイズ分縮小した外接四角形に接する楕円の座標を求めている。（INNEROVAL）
- 以上の流れを見て、BUMPOVALが楕円の境界座標を計算する核となる部分。
- 但し、BUMPOVALで利用する変数は、INITOVALで初期化されているので、詳細に追うにはINITOVALも見ておく必要がある。
INITOVAL
INITOVALが設定する値を調べてみた。
- 以下のQuickDraw呼び出しの場合で考えてみる。
SetRect(tempRect,100,200,110,210); FrameOval(tempRect);
- INITOVALが呼ばれた時点のレジスタの状態は以下のようになると思う。
.PROC INITOVAL,4 ;------------------------------------------------------------ ; ; PROCEDURE InitOval(dstRect: Rect; VAR oval: OvalRec; ; ovalWidth,ovalHeight: INTEGER); ; ; initialize an oval state record to fit the given rectangle. ; ; INPUTS: A0: dstRect = (100,200,110,210) ; A1: ovalRec = OVAL STATE RECORDの先頭アドレス ; D1: ovalHeight = 10 ; D2: ovalWidth = 10 ; ; CLOBBERS D0,D1,D2 ;
- OVAL STATE RECORDの初期値は、以下のように設定されるのだ。
; OVAL STATE RECORD: （919行目 ）OVALTOP = dstRect.top = 100 （920行目 ）OVALBOT = dstRect.bottom = 110 （961行目〜）OVALY = 1 - ovalHeight = -9 （967行目〜）RSQYSQ = 2*ovalHeight - 1 = 19 （975行目〜）SQUARE = 0.0 （980行目〜）ODDNUM = 1*(ovalHeight/ovalWidth)^2 = 1 （990行目〜）ODDBUMP =2*(ovalHeight/ovalWidth)^2 = 2 （945行目〜）LEFTEDGE = 205.0 （945行目〜）RIGHTEDGE = 205.5 （957行目 ）ONEHALF = 0.5 （...行目 ）OVALSIZE = 未定義
; A6 で参照できる楕円描画ループからの引数: PARAMSIZE DSTRECT = (110,200,100,210) HOLLOW = 1（Frameの場合1が設定されている） OVALWIDTH = 10 OVALHEIGHT = 10 MODE = ?（Ovals.a 72行目 JSR PushVerb → Rects.a 69行目〜 PushVerbによって設定されるようだが、未追跡） PAT = ? （Ovals.a 72行目 JSR PushVerb → Rects.a 69行目〜 PushVerbによって設定されるようだが、未追跡） STARTANGLE = 0（円弧の描画開始位置、単位:度、12時位置が0、時計回りに進む） ARCANGLE = 360（円弧の描画範囲、単位:度、12時位置が0、時計回りに進む）
BUMPOVAL
以上の設定値を考慮して、いよいよ楕円描画の核の部分、BUMPOVALのコードを詳細に追ってみる。
.PROC BUMPOVAL,2 ;------------------------------------------------------------ ; ; LOCAL PROCEDURE BumpOval(VAR oval: OvalRec; vert: INTEGER); ; ; bump an oval state record to the next scanline down. ; ; INPUTS: A3 POINTS TO OVAL STATE RECORD ; D0 CONTAINS CURRENT VERT ; ; CLOBBERS D0-D7,A0-A3 ; ;
- BUMPOVALに分岐した時点で、レジスタの状態は上記のようになっているらしい。
;------------------------------------------------------- ; ; ONLY BUMP IF VERT IS BETWEEN OVALTOP AND OVALBOT ; CMP (A3)+,D0 ;IS VERT < OVAL TOP ? BLT.S GOHOME ;YES, IGNORE CMP (A3)+,D0 ;IS VERT >= OVAL BOTTOM ? BGE.S GOHOME ;YES, IGNORE MOVE (A3),D0 ;GET OVALY ADD #2,(A3)+ ;ADD 2 TO OVALY FOR NEXT TIME MOVEM.L (A3),D1-D7/A0-A2 ;GET REST OF THE OVAL RECORD BRA.S WHILE1 ;GO TO LOOP START
- A3レジスタを利用して、OVAL STATE RECORDにアクセス。
- 現在のスキャン位置VERTが、OVAL BOTTOM <= VERT < OVAL TOPの範囲であるかチェック。
- 範囲外なら何もしないで戻る。
- OVALY（=-9）をD0レジスタに代入。
- 次回のためにOVALYに2を加算する。（=-7）
- 現在、A3レジスタの示すアドレスは、OVAL STATE RECORDのRSQYSQまで進んでいる。
- 「MOVEM.L (A3),D1-D7/A0-A2」を実行して、OVAL STATE RECORDのRSQYSQ以降の値をD1〜D7とA0〜A2レジスタに読み込む。
- 実行後の各レジスタの利用状態は、以下のコメントに解説されるとおりとなる。（値を追記した）
;------------------------------------------ ; ; register usage: ; ; D0: vert = -9 ; D1: RSQYSQ = 19 ; D2,D3: SQUARE = 0.0 ; D4,D5: ODDNUM = 1 ; D6,D7: ODDBUMP = 2 ; A0: LEFTEDGE = 205.0 ; A1: RIGHTEDGE = 205.5 ; A2: #$00008000 = 下位4バイトを小数として扱う固定小数点と考えると0.5 ; A3: modified oval ptr = OVAL STATE RECORDのRSQYSQのアドレス
- この状態でWHILE1に分岐して、Y座標に対する楕円境界のX座標を求めるループがいよいよ始まるのだ。
;----------------------------------------------- ; ; WHILE SQUARE < RSQYSQ DO MAKE OVAL BIGGER ; MORE1 ADD.L A2,A1 ;RIGHTEDGE := RIGHTEDGE + 1/2 SUB.L A2,A0 ;LEFTEDGE := LEFTEDGE - 1/2 ADD.L D5,D3 ;SQUARE := SQUARE + ODDNUM ADDX.L D4,D2 ;ALL 64 BITS OF IT ADD.L D7,D5 ;ODDNUM := ODDNUM + ODDBUMP ADDX.L D6,D4 ;ALL 64 BITS OF IT WHILE1 CMP.L D1,D2 ;IS SQUARE < RSQYSQ ? BLT MORE1 ;YES, LOOP BRA.S WHILE2 ;NO, GO TO NEXT LOOP START
- まずは、ループを継続するかどうかの条件判定。
- SQUARE < RSQYSQならループは継続する。（MORE1に分岐）
- 1回目、0 < 19なのでループは継続する。
- RIGHTEDGE := RIGHTEDGE + 1/2 = 206.0
- LEFTEDGE := LEFTEDGE - 1/2 = 204.5
- SQUARE := SQUARE + ODDNUM = 1
- ODDNUM := ODDNUM + ODDBUMP = 3
- 2回目、1 < 19なのでループは継続する。
- RIGHTEDGE := RIGHTEDGE + 1/2 = 206.5
- LEFTEDGE := LEFTEDGE - 1/2 = 204.0
- SQUARE := SQUARE + ODDNUM = 4
- ODDNUM := ODDNUM + ODDBUMP = 5
- 3回目、4 < 19なのでループは継続する。
- RIGHTEDGE := RIGHTEDGE + 1/2 = 207.0
- LEFTEDGE := LEFTEDGE - 1/2 = 203.5
- SQUARE := SQUARE + ODDNUM = 9
- ODDNUM := ODDNUM + ODDBUMP = 7
- 4回目、9 < 19なのでループは継続する。
- RIGHTEDGE := RIGHTEDGE + 1/2 = 207.5
- LEFTEDGE := LEFTEDGE - 1/2 = 203.0
- SQUARE := SQUARE + ODDNUM = 16
- ODDNUM := ODDNUM + ODDBUMP = 9
- 5回目、16 < 19なのでループは継続する。
- RIGHTEDGE := RIGHTEDGE + 1/2 = 208.0
- LEFTEDGE := LEFTEDGE - 1/2 = 202.5
- SQUARE := SQUARE + ODDNUM = 25
- ODDNUM := ODDNUM + ODDBUMP = 11
- 6回目、25 > 19なのでループを抜けてWHILE2へ分岐。
;----------------------------------------------- ; ; WHILE SQUARE > RSQYSQ DO MAKE OVAL SMALLER ; MORE2 SUB.L A2,A1 ;RIGHTEDGE := RIGHTEDGE - 1/2 ADD.L A2,A0 ;LEFTEDGE := LEFTEDGE + 1/2 SUB.L D7,D5 ;ODDNUM := ODDNUM - ODDBUMP SUBX.L D6,D4 ;ALL 64 BITS OF IT SUB.L D5,D3 ;SQUARE := SQUARE + ODDNUM SUBX.L D4,D2 ;ALL 64 BITS OF IT WHILE2 CMP.L D1,D2 ;IS SQUARE > RSQYSQ ? BGT MORE2 ;YES, LOOP
- やはり最初は、ループを継続するかどうかの条件判定。
- 今度は逆に、SQUARE > RSQYSQならループは継続する。（MORE2に分岐）
- 1回目、25 > 19なのでループは継続する。
- RIGHTEDGE := RIGHTEDGE - 1/2 = 207.5
- LEFTEDGE := LEFTEDGE + 1/2 = 203.0
- ODDNUM := ODDNUM - ODDBUMP = 9
- SQUARE := SQUARE - ODDNUM = 16
- 5回目、16 < 19なのでループを抜ける。
ADD #1,D0 ;CALC OVALY+1 EXT.L D0 ;SIGN EXTEND TO A LONG ASL.L #2,D0 ;CALC 4*(OVALY+1) SUB.L D0,D1 ;RSQYSQ := RSQYSQ-4*(OVALY+1) MOVEM.L D1-D7/A0-A2,(A3) ;UPDATE OVAL RECORD GOHOME RTS
- ループを抜けた後は、不思議な計算をしている。
- RSQYSQ := RSQYSQ-4*(vert+1)
- 最後は、現在のレジスタの値で、OVAL STATE RECORDを更新して、戻る。
BUMPOVALは一体何をやっているのか？
まず、RSQYSQがどのように変化するか追ってみた。
- Y=-9をスキャン
- RSQYSQ = 2*ovalHeight - 1 = 19
- Y=-7をスキャン、vert=-9
- RSQYSQ = RSQYSQ - 4*(vert+1) = 51
- Y=-5をスキャン、vert=-7
- RSQYSQ = RSQYSQ - 4*(vert+1) = 75
- Y=-3をスキャン、vert=-5
- RSQYSQ = RSQYSQ - 4*(vert+1) = 91
- Y=-1をスキャン、vert=-3
- RSQYSQ = RSQYSQ - 4*(vert+1) = 99
次に、半径10の円の座標がどのように変化するのか？
- 円の公式を変形して利用してみる。
X^2 + Y^2 = 10^2
X^2 = 100 - Y^2
- Y=-9
- X^2 = 100 - Y^2 = 100 - 81 = 19
- Y=-7
- X^2 = 100 - Y^2 = 100 - 49 = 51
- Y=-5
- X^2 = 100 - Y^2 = 100 - 25 = 75
- Y=-3
- X^2 = 100 - Y^2 = 100 - 9 = 91
- Y=-1
- X^2 = 100 - Y^2 = 100 - 1 = 99
- つまり、RSQYSQとは、円周上のY座標に対応するX座標の2乗を計算していたのである！
- RSQYSQとは、半径RのSQUARE（2乗）− Y座標のSQUARE（2乗）を省略したラベル名だったのである。
- X座標の2乗が求められれば、後はその平方根（ルート）を計算すれば良い。
- しかし、平方根の計算は、当時の68000CPUにとって負荷が大き過ぎる。
- そこで、奇数列の和が二乗の数列になることを利用して、平方根（ルート）を概算しているのだ。
- 1 = 1^2、1＋3 = 2^2、1＋3＋5 = 3^2、1+3+5+7 = 4^2
- 整数座標しか扱わないQuickDrawにとっては、概算で十分だったのである。
- ODDBUMP中で唯一の掛算は、次のRSQYSQを求める部分。
- RSQYSQ = RSQYSQ - 4*(vert+1)
- ところが、4倍は、CPUにとって左に2ビットシフトする単純操作になるので、加算・減算と同等のスピードで処理できる。
- その他の命令は、加算・減算・条件分岐のみ。
だから、浮動小数点計算ユニットを持たない68000CPUであっても、QuickDrawは素早く円を描画してくれたのだ！
RSQYSQ = 2*ovalHeight - 1、RSQYSQ = RSQYSQ - 4*(vert+1)の証明
- ところで、 R^2 - Y^2は、なぜ上記の数式で求められるのだろうか？考えてみた。
円周上にあるY座標に対するX座標をX0とおく。 X0 = R^2 - Y^2 上記のY座標が1減少した場合のX座標をX1とおく。 X1 = R^2 - (Y - 1)^2 = R^2 - Y^2 + 2Y - 1 Yが1減少した時のXの変化値は、X1 - X0である。 = R^2 - Y^2 + 2Y - 1 - (R^2 - Y^2) = 2Y - 1 同様に、Yが2減少した時のXの変化値も求めてみる。 = R^2 - (Y - 2)^2 - (R^2 - Y^2) = R^2 - Y^2 + 4Y - 4 - (R^2 - Y^2) = 4Y - 4 = -4(-Y + 1)
- つまり、Y=Rの場合X=0は明白なので、そこからYが1減少した場合
- RSQYSQ = 2*ovalHeight - 1
- さらに、上記の位置からYが2減少した場合
- RSQYSQ = RSQYSQ - 4*(vert+1)
- vertは負の整数
- RSQYSQ = RSQYSQ - 4*(vert+1)
なるほど。
楕円の境界
- 円の描画方法は分かった。しかし、楕円の場合はどうなるのだろう？
- その仕組みは、ODDNUM・ODDBUMPを求める計算式にあった。（DrawArc.a 980行目〜）
; ODDNUM:= 1 TIMES ASPECT RATIO SQUARED CLR.L -(SP) ;GET READY FOR FUNCTION RESULT MOVE D1,-(SP) ;PUSH NUMERATOR=HEIGHT MOVE D2,-(SP) ;PUSH DENOMINATOR=WIDTH _FixRatio ;CALC FIXED POINT HEIGHT/WIDTH MOVE.L (SP),-(SP) ;DUPLICATE RESULT PEA ODDNUM(A1) ;PUSH ADDR FOR RESULT _LongMul ;CALC 64BIT (HEIGHT/WIDTH) SQUARED ; ODDBUMP:= 2 TIMES ASPECT RATIO SQUARED MOVE.L ODDNUM+4(A1),D0 ;GET LO LONG OF RESULT ADD.L D0,D0 ;DOUBLE IT MOVE.L D0,ODDBUMP+4(A1) ;STORE INTO LO LONG OF ODDBUMP MOVE.L ODDNUM(A1),D0 ADDX.L D0,D0 ;DOUBLE HI LONG WITH CARRY MOVE.L D0,ODDBUMP(A1) RTS
- つまり、以下の式で求めているということになる。
- ODDNUM = 1*(HEIGHT/WIDTH)^2
- ODDBUMP = 2*(HEIGHT/WIDTH)^2
- もし、円の場合なら、(HEIGHT/WIDTH)^2の部分は1になるはずである。
- だから、BUMPOVALの中ではシンプルな整数の奇数列が発生する。
- 1、1＋3 = 4、1＋3＋5 = 9、1+3+5+7 = 16、1+3+5+7+9 = 25、1+3+5+7+9+11 = 36
- では、横長の楕円ではどうなるだろう？
- X軸半径が10、Y軸の半径が5の楕円で考えてみた。
- (HEIGHT/WIDTH)^2 = (5/10)^2 = (1/2)^2 = 1/4
- ODDNUM = 1/4
- ODDBUMP = 2/4
- ここで、BUMPOVALで発生する数列を考えてみると、(HEIGHT/WIDTH)^2、つまりアスペクト比の2乗で割り算した奇数列の和になる。
- 1/4、1/4+3/4=4/4、1/4+3/4+5/4=9/4、1/4+3/4+5/4+7/4=16/4、1/4+3/4+5/4+7/4+9/4=25/4、1/4+3/4+5/4+7/4+9/4+11/4=36/4
- 実際に上記図形を見ながら、円の座標(3,4)と楕円の座標(6,4)に注目してみる。
- BUMPOVALの中では、楕円であっても円と同じ境界値3^2=9を利用する。*2
- 但し、1/4された奇数列の和が利用されるので、境界値に達するのは36/4の時である。
- この時、X座標は6と計算される。実際に上記楕円もそうなっている。
つまり、QuickDrawは円のアスペクト比を変更して楕円を描いていたのである！
- この方法なら複雑な楕円の公式を使わず、シンプルな円の公式で素早く計算できる。
その他
- QuicDrawでは、半径R = 5の円を、2倍の半径R = 10の円として計算している。（なぜだろう？）
- 誤差を最小にするため？
- あるいは、直径が奇数・偶数どちらにも対応するため？
- 2倍の半径Rの円としているので、
- 求めるX座標はループ回数に応じて、1/2ずつ変化させている。
- また、Y座標の変化は、初期値だけ1、ループ中は2ずつ変化させている。
- QuickDrawの座標系は、数学座標とはちょっと違う。
- 左上が原点。
- Xは右に行くほど増加。
- Yは下に行くほど増加。
追跡 PutOval.a
- ちょっと力尽きたので、詳細には追跡しなかった。
- おそらく、重ね合わせのためのマスク処理をしているのではないだろうか？
ポイント
所感
- 正直、自分はコードの美しさを実感できるレベルにはない。
- しかし、1行ごとの詳細なコメントには相当助けられた。
- コメントのおかげで、拙い自分の知識でも読めたと思う。
- 円・楕円の描画方法にねらいを絞って、その他の部分は大雑把に見て途中で追跡をやめてしまった...。
- よって、間違った解釈も多々あると思う。
- QuickDrawには、パターン描画、画像・ウィンドウの重ね合わせ、必要最小限の再描画など、興味深い技が多々眠っている。
参考ページ
以下のページが参考になりました。感謝です！
