TrueType命令でビット演算

TrueType命令で遊ぶシリーズ。

ビット演算

TrueType命令にはビット演算がない。ヒンティングには重要でないからだろう。
それでも、~~変なことしようとすると~~あると便利なのがビット演算である。

それっぽい名前の命令としてNEG, AND, ORなどがあるが、それぞれ数値の符号反転 (-a), 論理AND (a&&b), 論理OR (a||b)である。
仕方がないので自分で実装してしまおうというのがこの記事の目的である。

bitwise NOT

符号反転して-1を足すだけ。(別に1を引くのでもいい)

NEG
PUSHW_1 -1
ADD

2の補数の定義より、符号の反転(-x)はビット反転+1 (~x +1)と等価
即ち
-x == ~x + 1
1を移項して
-x - 1 == ~x
したがって、符号反転して1引いた数はビット反転に等しい。
— にせねこ (@nixeneko) 2017年5月25日

左シフト

1ビット左シフト

要するに2を掛ければよいのだけれど、掛け算命令使うとF26DOT6との折り合いを付けないといけなくて面倒なのとオーバーフロー時の動作が心配なので、同じものを複製して足し合わせて計算することにする。

DUP
ADD

多ビット左シフト

1ビット左シフトをシフトしたいだけ繰り返せばよい。

右1ビット算術シフト

2.0 (つまり、F26DOT6の6ビット分だけ下駄を履かせて128)で割る。ただ、任意の数について適切に扱えるかはわからない。

PUSHB_1 128
DIV

多ビット(nビットとする)の場合は $2^n \times 64$ で割るといいと思う。

右1ビット論理シフト

最上位ビットに気を付けて2で割る。
まず数値が負かどうかを見て最上位ビット(MSB)によって場合分けする。

非負(MSB==0)ならそのまま2で割る。
負(MSB==1)なら0x80000000を足してMSBを0にした後、2で割り、もともとのMSBに相当する部分のビットを立てる(つまり、0x40000000を足す)。

             #x
DUP          #x|x|
PUSHB_1 0    #x|x|0|
LT           #x|x<0| #MSB
IF           #x| #when MSB==1
 PUSHW_3
  16384  #0x100*64
  16384  #0x100*64
  -32768 #0x8000
 MUL
 MUL         #x|0x80000000|
 ADD         #x+0x80000000|
 PUSHB_1 128 #x+0x80000000|2.0|
 DIV         #(x+0x80000000)/2|
 PUSHW_3
  16384 #0x100*64
  16384 #0x100*64
  16384 #0x4000
 MUL
 MUL         #(x+0x80000000)/2|0x40000000|
 ADD         #(x+0x80000000)/2+0x40000000|
ELSE         #x| #when MSB==0
 PUSHB_1 128 #x|2.0|
 DIV         #x/2|
EIF

これを一度計算すると最上位ビットが0であることが保証されるので、多ビット(nビット)シフトする場合はこれを実行した後に $2^{n-1} \times 64$ で割るといいと思う。

bitwise AND

AND, ORって命令はあるけれど、0をfalse, 0以外をtrueとしたlogical演算(演算結果がtrueの場合は1, falseの場合は0が返される)であって、bit演算ではない。

MSBは0だと非負整数、1だと負正数となる。そのため、値が0より小さければそのMSBが1だとわかる。また、左シフトもできるので、1ビットごと計算をしていけばよさそうだ。

演算対象の2つの数値についてMSBがわかるので、それらのMSBに対して(logical) ANDをとる。返す値を1ビット左シフトしながらその結果を加算する(LSBとなる)。
演算対象の2つの数値について1ビット左シフトして、この全体のプロセスを32回繰り返すと、bitwise ANDの結果が得られる。

#func0 - calculates bitwise AND
#initial stack: ...|x|y|
#final stack:   ...|x & b| (bitwise and)
PUSHB_1 0
FDEF        #x|y|
PUSHB_1 0   #x|y|r=0| #initialize return value r by 0
ROLL        #y|r|x|
PUSHB_1 32  #y|r|x|c=32| #initialize counter c by 32
ROLL        #y|x|c|r|
ROLL        #y|c|r|x|
PUSHB_1 4
MINDEX      #c|r|x|y|
#ここからループする(32回実行) #c|r|x|y|   #基準の形*1
# jump_to_here:
PUSHB_1 4
MINDEX      #r|x|y|c|
PUSHB_1 1   #r|x|y|c|1|
SUB         #r|x|y|c-1|
PUSHB_1 4
MINDEX      #x|y|c-1|r|
PUSHB_1 4
MINDEX      #y|c-1|r|x|
PUSHB_1 4
MINDEX      #c-1|r|x|y|
DUP         #c-1|r|x|y|y| 
PUSHB_1 0   #c-1|r|x|y|y|0|
LT          #c-1|r|x|y|y<0|
PUSHB_1 3
CINDEX      #c-1|r|x|y|y<0|x|
PUSHB_1 0   #c-1|r|x|y|y<0|x|0|
LT          #c-1|r|x|y|y<0|x<0|
AND         #c-1|r|x|y|y<0 && x<0|
PUSHB_1 4
MINDEX      #c-1|x|y|y<0 && x<0|r|
DUP         #c-1|x|y|y<0 && x<0|r|r|
ADD         #c-1|x|y|y<0 && x<0|r<<1|
ADD         #c-1|x|y|r<<1 + (y<0 && x<0)|
ROLL        #c-1|y|r<<1 + (y<0 && x<0)|x|
DUP         #c-1|y|r<<1 + (y<0 && x<0)|x|x|
ADD         #c-1|y|r<<1 + (y<0 && x<0)|x<<1|
ROLL        #c-1|r<<1 + (y<0 && x<0)|x<<1|y|
DUP         #c-1|r<<1 + (y<0 && x<0)|x<<1|y|y|
ADD         #c-1|r<<1 + (y<0 && x<0)|x<<1|y<<1| #*1と同じ形
#ここまでループする
PUSHW_1 -44 #c-1|r<<1 + (y<0 && x<0)|x<<1|y<<1|jump_delta| #ジャンプ先
PUSHB_1 5
CINDEX      #c-1|r<<1 + (y<0 && x<0)|x<<1|y<<1|jump_delta|c-1|
JROT        #c-1|r<<1 + (y<0 && x<0)|x<<1|y<<1| #jump if c-1 != 0
POP         #c|r|x|
POP         #c|r|
SWAP        #r|c|
POP         #r|
ENDF

bitwise OR

bitwise ANDの場合と同様だが、ANDの代わりにORを使えばbitwise ORになる。一命令入れ替えただけ。

#func1 - calculates bitwise OR
#initial stack: ...|x|y|
#final stack:   ...|x | b| (bitwise or)
PUSHB_1 1
FDEF        #x|y|
PUSHB_1 0   #x|y|r=0| #initialize return value r by 0
ROLL        #y|r|x|
PUSHB_1 32  #y|r|x|c=32| #initialize counter c by 32
ROLL        #y|x|c|r|
ROLL        #y|c|r|x|
PUSHB_1 4
MINDEX      #c|r|x|y|
#ここからループする(32回実行) #c|r|x|y|  #基準の形*1
# jump_to_here:
PUSHB_1 4
MINDEX      #r|x|y|c|
PUSHB_1 1   #r|x|y|c|1|
SUB         #r|x|y|c-1|
PUSHB_1 4
MINDEX      #x|y|c-1|r|
PUSHB_1 4
MINDEX      #y|c-1|r|x|
PUSHB_1 4
MINDEX      #c-1|r|x|y|
DUP         #c-1|r|x|y|y| 
PUSHB_1 0   #c-1|r|x|y|y|0|
LT          #c-1|r|x|y|y<0|
PUSHB_1 3
CINDEX      #c-1|r|x|y|y<0|x|
PUSHB_1 0   #c-1|r|x|y|y<0|x|0|
LT          #c-1|r|x|y|y<0|x<0|
OR          #c-1|r|x|y|y<0 || x<0|
PUSHB_1 4
MINDEX      #c-1|x|y|y<0 || x<0|r|
DUP         #c-1|x|y|y<0 || x<0|r|r|
ADD         #c-1|x|y|y<0 || x<0|r<<1|
ADD         #c-1|x|y|r<<1 + (y<0 || x<0)|
ROLL        #c-1|y|r<<1 + (y<0 || x<0)|x|
DUP         #c-1|y|r<<1 + (y<0 || x<0)|x|x|
ADD         #c-1|y|r<<1 + (y<0 || x<0)|x<<1|
ROLL        #c-1|r<<1 + (y<0 || x<0)|x<<1|y|
DUP         #c-1|r<<1 + (y<0 || x<0)|x<<1|y|y|
ADD         #c-1|r<<1 + (y<0 || x<0)|x<<1|y<<1| #*1と同じ形
#ここまでループする
PUSHW_1 -44 #c-1|r<<1 + (y<0 || x<0)|x<<1|y<<1|jump_delta| #ジャンプ先
PUSHB_1 5
CINDEX      #c-1|r<<1 + (y<0 || x<0)|x<<1|y<<1|jump_delta|c-1|
JROT        #c-1|r<<1 + (y<0 || x<0)|x<<1|y<<1| #jump if c-1 != 0
POP         #c|r|x|
POP         #c|r|
SWAP        #r|c|
POP         #r|
ENDF

bitwise XOR

$a,b\in \{0,1\}$ でXORしたければ、ANDやORの代わりに a-b != 0 をチェックすればよさそう。
なので、bitwise ANDの場合と同様であるが、ANDの代わりに a-b != 0 を計算する命令が入っている。

#func2 - calculates bitwise XOR
#initial stack: ...|x|y|
#final stack:   ...|x ^ b| (bitwise xor)
PUSHB_1 2
FDEF        #x|y|
PUSHB_1 0   #x|y|r=0| #initialize return value r by 0
ROLL        #y|r|x|
PUSHB_1 32  #y|r|x|c=32| #initialize counter c by 32
ROLL        #y|x|c|r|
ROLL        #y|c|r|x|
PUSHB_1 4
MINDEX      #c|r|x|y|
#ここからループする(32回実行) #c|r|x|y|  #基準の形*1
# jump_to_here:
PUSHB_1 4
MINDEX      #r|x|y|c|
PUSHB_1 1   #r|x|y|c|1|
SUB         #r|x|y|c-1|
PUSHB_1 4
MINDEX      #x|y|c-1|r|
PUSHB_1 4
MINDEX      #y|c-1|r|x|
PUSHB_1 4
MINDEX      #c-1|r|x|y| 
DUP         #c-1|r|x|y|y| 
PUSHB_1 0   #c-1|r|x|y|y|0|
LT          #c-1|r|x|y|y<0|
PUSHB_1 3
CINDEX      #c-1|r|x|y|y<0|x|
PUSHB_1 0   #c-1|r|x|y|y<0|x|0|
LT          #c-1|r|x|y|y<0|x<0|
SUB         #c-1|r|x|y|(y<0)-(x<0)|
PUSHB_1 0   #c-1|r|x|y|(y<0)-(x<0)|0|
NEQ         #c-1|r|x|y|(y<0)-(x<0)==0|
PUSHB_1 4
MINDEX      #c-1|x|y|(y<0)-(x<0)==0|r|
DUP         #c-1|x|y|(y<0)-(x<0)==0|r|r|
ADD         #c-1|x|y|(y<0)-(x<0)==0|r<<1|
ADD         #c-1|x|y|r<<1 + ((y<0)-(x<0)==0)|
ROLL        #c-1|y|r<<1 + ((y<0)-(x<0)==0)|x|
DUP         #c-1|y|r<<1 + ((y<0)-(x<0)==0)|x|x|
ADD         #c-1|y|r<<1 + ((y<0)-(x<0)==0)|x<<1|
ROLL        #c-1|r<<1 + ((y<0)-(x<0)==0)|x<<1|y|
DUP         #c-1|r<<1 + ((y<0)-(x<0)==0)|x<<1|y|y|
ADD         #c-1|r<<1 + ((y<0)-(x<0)==0)|x<<1|y<<1| #*1と同じ形
#ここまでループする
PUSHW_1 -47 #c-1|r<<1 + ((y<0)-(x<0)==0)|x<<1|y<<1|jump_delta| #ジャンプ先
PUSHB_1 5
CINDEX      #c-1|r<<1 + ((y<0)-(x<0)==0)|x<<1|y<<1|jump_delta|c-1|
JROT        #c-1|r<<1 + ((y<0)-(x<0)==0)|x<<1|y<<1| #jump if c-1 != 0
POP         #c|r|x|
POP         #c|r|
SWAP        #r|c|
POP         #r|
ENDF