HP 35s でプログラミング - 4

HP 35s

前回 HP 35s 向けにそこそこ複雑なアルゴリズムを実装してみたが、なかなかパフォーマンス的に厳しい事実が垣間見えてしまった。ほかに何かネタが無いか考えあぐねいていたところ、出版されたのはだいぶ前だが「ハッカーの楽しみ」という本のことを思い出した。英語版では第二版が 2012年に出ている。

Hacker's Delight (English Edition)

Hacker's Delight (English Edition)

マニアックなビット演算の話が多い中で、とっつきやすそうなビットの数え上げを HP 35s で実装してみる。このアルゴリズムは 1 word = 32 bit のデータ中、1 の立っているビットの数を返すもので、ビットで状態を管理するシステムや信号処理には有用だろう。本では幾つもの手法が紹介されているが、冒頭に紹介されている分割統治法によるものを HP 35s で実装してみようと思う。
C 言語によるコードは以下（分割統治法といっても再帰は使わない）：

x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);

本の例を以下に拝借させてもらうと、入力に対して以下のステップで x が変化する：

10 11 11 00 01 10 00 11 01 11 11 10 11 11 11 11 0xBC637EFF
01 10 10 00 01 01 00 10 01 10 10 01 10 10 10 10 0x685269AA
0011 0010 0010 0010 0011 0011 0100 0100 0x32223344
00000101 00000100 00000110 00001000 0x05040608
0000000000001001 0000000000001110 0x0009000E
00000000000000000000000000010111 0x00000017

一番最後のステップがわかり易い。0x9 と 0xE の足し算は 0x17 である。コードとも直観的に一致するのではないだろうか。
前提として、このアルゴリズムは 32bit 向けで、かつシフト演算器が備わっていないと高速化が見込めない。HP 35s は内部的な演算器は 8bit、シフト命令キーは無しなので割り算で代用する。愚直に HP 35s で実装すると以下の通りになる：

E001 : LBL E
E002 : HEX
;
; x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
E003 : 55555555h
E004 : x<>y
E005 : AND
E006 : LAST x
E007 : 2h
E008 : /
E009 : 55555555h
E010 : AND
E011 : +
;
; x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
E012 : 33333333h
E013 : x<>y
E014 : AND
E015 : LAST x
E016 : 4h
E017 : /
E018 : 33333333h
E019 : AND
E020 : +
;
; x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
E021 : 0F0F0F0Fh
E022 : x<>y
E023 : AND
E024 : LAST x
E025 : 10h
E026 : /
E027 : 0F0F0F0Fh
E028 : AND
E029 : +
;
; x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
E030 : 00FF00FFh
E031 : x<>y
E032 : AND
E033 : LAST x
E034 : 100h
E035 : /
E036 : 00FF00FFh
E037 : AND
E038 : +
;
; x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
E039 : 0000FFFFh
E040 : x<>y
E041 : AND
E042 : LAST x
E043 : 10000h
E044 : /
E045 : 0000FFFFh
E046 : AND
E047 : +

HP 35s でのプログラミングもだいぶ慣れてきたのか、今回は最初から脳内アセンブル & 直接入力し、1発で動いてくれた。4行目でわざわざ x レジスタと y レジスタを交換しているのは、6行目でオリジナルの x を LAST x で取り出すためである。こうすると STO/RCL 命令を使わずに済む。21行目等、16進数のアルファベットを入れるには EQN キーを押し、RCL F とすれば良い。実行するには

BC637EFFh
XEQ E
ENTER

とすれば良い。ちゃんと 17h が出力された。

さて、気になるのは実行パフォーマンスである。この実行には4秒ほどかかった。HP 35s には HP 16C とは異なりシフト命令キーが無く、割り算をしているのも遅い要因と思ったが、プログラムを使わず普通の電卓として複雑な割り算をしても全く遅く感じない。
内部的にどのような処理になっているのか気になったので少し調べてみたところ、CPU は MOS 8502 というやつで、6510 と命令セットは同じらしい。6510 のデータシートを見てみた。
http://archive.6502.org/datasheets/mos_6510_mpu_nov_1982.pdf

HP 35s の第一回目の記事で「裸のコンピュータ」と書いたが、どうやらそれは誤りのようだ。データシートを見たところ、HP 35s で用意されている"命令"は 6510 のそれに比べると相当リッチである。一見低レベル風な命令が多いのでてっきりアセンブラだと思っていたが、HP 35s で動くプログラムは立派なインタプリタである。

命令セットは以下のほうがわかり易い。

http://www.e-tradition.net/bytes/6502/6502_instruction_set.html

各命令にサイクル数も載っており、例えば SP ( スタックポインタ) の更新には 2 サイクル、スタック領域への値書き込みに 3 サイクル、読み込みに 4 サイクル。スタックとは別に用意されているメモリアクセスはアドレッシング方式により最大 7 サイクルかかる。絶対ジャンプに必要なサイクル数は 3 で、パイプラインや命令キャッシュなんて無いのであろうから、少ないコストで動くのだろう。
HP 35s と 6510 の命令比較の一例を挙げると、HP 35s の ISG( インクリメント後にループ制御変数の値を評価し、条件により次の命令をスキップ） は 6510 には無い命令で、6510 には単純な INC( インクリメント ) のみが用意されている。ISG は INC の実行後に小数部を取り出して CPX/CPY ( 比較 ) 命令を追加実行し、フラグを評価後に「インタプリタ」プログラムの PC を変更するのであろう。尚、I/(I), J/(J) によるアドレッシングは 6510 の X, Y インデックスレジスタによるものだろうが、これらのレジスタは 8bit なので、どのように 35s のアドレス空間にマッピングしているのかは謎である。ページ毎にアクセスする命令を置いておいて、X-indexed で調整しているのだろうか。35s でアクセス可能なアドレス空間は「未初期化」状態というものが存在することから、何かしらの管理領域が存在することは確かと思われる。
RPN で利用する4段のスタックもハードウェア由来のものと思ったが、計算に使えるレジスタは 8bit のアキュムレータ 1 つで、ソフト的に実装されているものだ。6510 のスタック領域は 256 Byte で、RPN スタック領域はこの領域を使っているのかもしれない( 35s で表現可能な数値は 36bit で、3次元ベクトルを扱う場合を考えるとスタック1段あたり 108 bit、4段 + Last X の分で 68 Byte 使う計算となる。35s におけるサブルーチン呼び出しは最大 20 段と規定されており、RTN ( Return ) で戻るアドレスに 2 Byte 消費すると見積もると 40 Byte。残りの領域は、アルファベットの変数に割り当てているのか、または管理領域として使っているのであろうか )。

もはやプログラミングより内部構造のほうに興味が移りつつあるが、もう少しこの電卓で遊んでみようと思う。