%=====================================================================
% 秋田高専 3E 電子計算機用テキスト
%    シフト命令
%      last updated 2006.2.14
%        created by  Masashi Yamamoto
%        e-mail yamamoto@akita-nct.jp
%=====================================================================
\documentclass[10pt,a4paper]{jarticle}
\usepackage{graphicx,amsmath,amssymb,ascmac,float,float}
\oddsidemargin 0mm  %左の余白 25.4mm-0mm　奇数ページ
\evensidemargin 0mm %左の余白 25.4mm-0mm　偶数ページ
\textwidth 160mm
%
\newcommand{\tw}[1]{\texttt{#1}}
\newcommand{\vbt}[1]{\begin{verbatim} #1 \end{verbatim}}
\newcounter{linenum}
\newcommand{\wrtlinenum}{\multicolumn{1}{|r|}{\arabic{linenum}}
   \addtocounter{linenum}{1}}
%
\newcounter{toi_num}
\newcommand{\toi}{\textbf{\texttt [問\arabic{toi_num}]}
   \addtocounter{toi_num}{1}}
%
\begin{document}
\title{CASL IIのプログラム例(その2)}
\date{2006年2月14日}
\author{山本昌志\thanks{国立秋田工業高等専門学校　電気工学科}}
\maketitle
%
%
%=====================================================================
\section{前回の復習と本日の学習内容}
%=====================================================================
%---------------------------------------------------------------------
\subsection{復習}
%---------------------------------------------------------------------
前回の講義では，教科書~\cite{text_casl2}の第5章の{\bf CASL IIプログラム例}の[例
題1]〜[例題3]を学習した．
\begin{itemize}
 \item {\bf [例題1]加算}
 \begin{itemize}\setlength\itemsep{-5pt}
  \item 演算を行う場合，汎用レジスターを使用しなくてはならない．
  \item メモリーの操作が必要である．
 \end{itemize}
 \item {\bf [例題2]加算と条件分岐}
  \begin{itemize}\setlength\itemsep{-5pt}
   \item 条件により実行する文が異なる処理を分岐という．
   \item CASL IIの場合，ジャンプ命令を使って分岐を行う．フラグレジスターの値によ
				りジャンプ先が変わる．
   \item フラグレジスターの値は，比較命令または演算により設定される．
  \end{itemize}
 \item {\bf [例題3]マスク処理と条件分岐}
 \begin{itemize}\setlength\itemsep{-5pt}
  \item 特定のビットを取り出すためのビットパターンをマスクという．
  \item 以下のようにすれば，特定のビットパターンになっているか，否かを調べるこ
			       とができる．
  \begin{enumerate}\setlength\itemsep{-5pt}
   \item マスクと\tw{AND}演算を行い，調べたい場所ののビットパターンを取り出す．
   \item \tw{CPL}命令により，ビットパターンの比較を行う．結果は，フラグレジスター
				  の\tw{ZF}に設定される．
  \end{enumerate}
  \end{itemize}
\end{itemize}
%
%---------------------------------------------------------------------
\subsection{本日の内容}
%---------------------------------------------------------------------
本日は教科書のp93-101の以下の内容について学習する．
\begin{itemize}
   \item {\bf [例題4]論理演算とアドレス修飾}
   \begin{itemize}\setlength\itemsep{-5pt}
    \item 指標レジスターを用いたアドレス修飾の方法を学習する．
   \end{itemize}
 \item {\bf [例題5]シフト演算}
   \begin{itemize}\setlength\itemsep{-5pt}
    \item シフト演算を用いた効率の良いかけ算と割り算の方法を学習する．
   \end{itemize}
 \item {\bf [例題6]繰り返し処理}
   \begin{itemize}\setlength\itemsep{-5pt}
    \item 繰り返し処理(ループ文)のプログラム方法を学習する．
   \end{itemize}
 \item {\bf [例題7]繰り返し処理とサブルーチン}
   \begin{itemize}\setlength\itemsep{-5pt}
    \item サブルーチンのプログラム方法を学習する．
   \end{itemize}
\end{itemize}
%
%=====================================================================
\section{[例題4]論理演算とアドレス修飾}
%=====================================================================
教科書のList 5-4のプログラムを例にして，論理演算とアドレス修飾について説明する．
以下のことが，ここでの学習の重要なポイントである．
\begin{itemize}\setlength\itemsep{-5pt}
 \item アドレス修飾の使い方
 \item カウンターとインクリメントのプログラムの記述方法．
\end{itemize}
%
%---------------------------------------------------------------------
\subsection{論理演算}
%---------------------------------------------------------------------
%------------------------
\subsubsection{教科書の例}
%------------------------
教科書のプログラムは，
\begin{itemize}\setlength\itemsep{-3pt}
 \item ラベル\tw{A,B}に\tw{\#0030,\#009F}が格納されている．
 \item ラベル\tw{ANS}から，3語このプログラムで確保されている．
 \item \tw{ANS}から確保された3語の領域に，\tw{A AND B}と\tw{A OR B}，\tw{A XOR
       B}の演算結果を格納せよ．
\end{itemize}
と言う問題を解く，プログラムである．

このようなプログラムを作成するために必要なことは，
%
\begin{itemize}
 \item データ領域
       \begin{itemize}\setlength\itemsep{-3pt}
	\item 演算の対象データ(\tw{\#0030,\#009F})をラベル(\tw{A,B})を指定してメ
	      モリーに書き込む．
	\item 演算結果を書き込む領域をラベル(\tw{ANS})を指定して，確保する．
       \end{itemize}
 \item 命令領域
       \begin{itemize}\setlength\itemsep{-3pt}
	\item 演算対象データをレジスターにコピー
	\item 演算の実行
	\item 計算結果の格納
       \end{itemize}
\end{itemize}
%
である．
%---------------------------------------------
\subsubsection{アドレス修飾}
%---------------------------------------------
大まかなプログラムの流れは，分かった．また，論理演算も説明することもないだ
ろう．演算対象のデータのそれぞれのビット毎の論理和(OR)と論理積(AND)，排他的論理
和(XOR)を計算しているだけである．

プログラムの命令領域とデータ領域は，図\ref{fig:memory5_4}のようになるだろう．プ
ログラムの書き方によっては，こうならないこともあるが，通常はこのようになる．
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio, scale=0.8]{figure/memory5-4.eps}
  \caption{教科書のList5-4のプログラムを実行する場合のメモリ構造．図中の\tw{?}は
  値はあるが，不明を示している．}
  \label{fig:memory5_4}
 \end{center}
\end{figure}
%

この場合，プログラムのデータ領域にアクセスする事を考える．ラベル\tw{A}や\tw{B}は
簡単で，ラベル名を示せば良い．ラベル名はアドレスを示すからである．問題は，結果を
格納する領域である．このアドレスは，3つ続いて確保されているが，先頭だけ\tw{ANS}
とラベル名がある．残りの2つの表し方である．これらのアドレスは，\tw{ANS+1}と
\tw{ANS+2}である．\tw{ANS}のアドレスにオフセットの値を加算するのである．

プログラムで使うメモリーのアドレスは，\tw{ANS+オフセット}で，オフセットは，
\tw{0,1,2}とすれば良い．論理和の結果を\tw{ANS+0}，論理積の結果を\tw{ANS+1}，論理
和の結果を\tw{ANS+2}に格納する．プログラムでは，オフセットの\tw{0,1,2}を\tw{GR2}
に入れておき，
\begin{ttfamily}
 \begin{small}
  \begin{tabbing}
   \hspace{6mm} \= 
   \hspace{11mm} \= 
   \hspace{11mm} \= 
   \hspace{11mm} \kill
   \> ST \> GR1,ANS,GR2 \>
  \end{tabbing}
 \end{small}
\end{ttfamily}
と書く．演算の結果(\tw{GR1})の値が，\tw{ANS}にオフセット値(\tw{GR2})を加えたアド
レスに格納される．

ここで，使っている\tw{GR2}のように，1つずつ値が増加するものをカウンターと呼ぶこ
とがある．これを使うためには，
%
\begin{itemize}
 \item カウンターの初期化．ここでは，\tw{GR2}をゼロに設定する．
       \begin{itemize}
	\item CASLでは，\tw{LAD GR2,0}
       \end{itemize}
 \item カウンターのインクリメント．カウンターの値を1増加させる．
       \begin{itemize}
	\item CASLでは，\tw{LAD GR2,1,GR2}
       \end{itemize}
\end{itemize}
%
とする．このテクニックは，重要である．内容をよく理解する必要がある．
%
%---------------------------------------------------------------------
\subsection{プログラムの構造とフローチャート}
%---------------------------------------------------------------------
このプログラムのフローチャートを図\ref{fig:flow_chart_list5_4}に示す．．
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio, scale=0.8]{flow_chart/REI5-4.eps}
  \caption{教科書のList5-4のプログラムの構造とフローチャート}
  \label{fig:flow_chart_list5_4}
 \end{center}
\end{figure}
%
%=====================================================================
\section{[例題5]シフト演算}
%=====================================================================
教科書のList 5-5のプログラムを例にして，シフト演算を使ったかけ算と割り算の方法を学習する．
以下のことが，ここでの学習の重要なポイントである．
\begin{itemize}\setlength\itemsep{-5pt}
 \item データを$2^n$倍するためには，データのビットをシフトさせることにより可能で
       ある．
 \item これを上手に使うと任意のかけ算と割り算ができる．
\end{itemize}
%---------------------------------------------------------------------
\subsection{積の演算}
%---------------------------------------------------------------------
積(かけざん)の演算を行うとき，シフト命令を使えば効率の良いプログラムができる．ビッ
トシフトを用いると積の演算ができる理由は以前述べているが，忘れた人もいるので，も
う一度，説明する．

シフト命令を使った積の演算は，小学生のときに学習をした筆算の掛け算と同じである．
たとえば，$34\times24$を計算する場合，筆算は
$34\times(2\times10^{1}+4\times10^{0})$と分解したはずである．そうして，次の手順
でこの計算を行ったはずである．
%
\begin{enumerate}\setlength\itemsep{-3pt}
 \item{$34\times2$を計算し，1桁ずらす(10倍する)．}
 \item{$34\times4$を計算する．}
 \item{先の計算結果を合計する．この合計816が$34\times24$の計算結果である．}
\end{enumerate}
%

同じことを2進数で行う．これがコンピューターによる乗算である．先ほどと
同じ計算($32\times24$)を行う．これを2進数で表現すると，
%
\begin{align*}
 (100010)_2\times(11000)_2=(100010)_2\times(1\times2^4+1\times2^3)
\end{align*}
%
となる．これを先ほど同様の手順で計算する．
%
\begin{enumerate}\setlength\itemsep{-3pt}
 \item{掛け算は1倍なので計算する必要が無く，最初に$(100010)_2$を4桁左
      にずらす(ビットシフト)．すると，$(1000100000)_2$となる．}
 \item{次に$(100010)_2$を3桁左にずらす．すると，$(100010000)_2$となる．}
 \item{先の計算結果を合計すると，$(1100110000)_2$となる．これは，10進
      数の816である．}
\end{enumerate}
%
シフトと加算命令でかけ算ができることが分かったはずである．

今回の問題のように分数(少数)の場合でも，
\begin{align}
 0.75&=\frac{1}{2}+\frac{1}{4} \nonumber \\
 &=\left(2^{-1}\right)+\left(2^{-2}\right)
\end{align}
%
と分解する．右に1ビットシフトさせたものと，右に2ビットシフトさせたものを加算すれ
ば良い．

教科書のように
\begin{align}
 0.75=1-\left(2^{-2}\right)
\end{align}
%
と分解するのは一般的ではない．
%
%---------------------------------------------------------------------
\subsection{プログラムの構造とフローチャート}
%---------------------------------------------------------------------
このプログラムのフローチャートを図\ref{fig:flow_chart_list5_5}に示す．．
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio, scale=0.8]{flow_chart/REI5-5.eps}
  \caption{教科書のList5-5のプログラムの構造とフローチャート}
  \label{fig:flow_chart_list5_5}
 \end{center}
\end{figure}
%
%=====================================================================
\section{[例題6]繰り返し処理}
%=====================================================================
教科書のList5-6のプログラムを例にして，繰り返し処理(ループ)について説明する．以
下のことが，ここでの学習の重要なポイントである．
 \begin{itemize}\setlength\itemsep{-5pt}
  \item 比較とジャンプ命令を使うことにより，繰り返し処理が出きる．
 \end{itemize}
%
%---------------------------------------------------------------------
\subsection{プログラムの基本構造}
%---------------------------------------------------------------------
高級言語のプログラムは，
\begin{quote}
 \begin{description}
  \item[順次]プログラムの命令は上から下へ実行される．
  \item[選択]制御式により実行される分が選択される．これは，FORTRANやC言語のif文の
	     ことである．
  \item[繰り返し]ループあるいは反復とも呼ばれ，同じ命令を繰り返す．FORTRANではDO
	     文，C言語ではfor文などである．
 \end{description}
\end{quote}
の基本構造からなる．いままで，順次は気が付かないで使っていたが，なにも考えること
はない．例題[3]で示した条件分岐(比較+ジャンプ)が選択の構造である．本日の例題
[6]では，繰り返し文を学習する．
%---------------------------------------------------------------------
\subsection{教科書の例}
%---------------------------------------------------------------------
教科書のプログラムは，
\begin{itemize}\setlength\itemsep{-3pt}
 \item ラベル\tw{DATA}から，ラベル\tw{KOSUU}が示す語数の整数のデータが格納されて
       いる．
 \item このデータの最大値を探し出し，それをラベル\tw{MAX}が示す領域に格納する．
\end{itemize}
という問題を解く，プログラムである．このプログラムは，教科書のp.98のList5-6に示
されている．まず最初に，
%
\begin{itemize}
 \item このプログラムの命令とデータの領域の区別
\end{itemize}
%
を考える．これは，さんざんやったので理解できているものとする．

このプログラムの核となる部分は，最大値を探すアルゴリズムである．教科書の例では，
それは，次のようなアルゴリズムとなっている．
%
\begin{enumerate}
 \item 最初に読み込むデータ(アドレス[\tw{data}])を暫定最大値とする．
 \item それ以降は繰り返し処理．
       \begin{enumerate}
	\item 次のデータと最大値を比較する
	\item 個数分のデータの比較が済んでいなければ，元(次データ
	      処理)に戻る
       \end{enumerate}
\end{enumerate}
%
である．最大値を探すアルゴリズムには，次々にデータを最大値と比較する処理が必要で
ある．ここに繰り返し処理が使われる．
%
%---------------------------------------------------------------------
\subsection{繰り返し処理}
%---------------------------------------------------------------------
高級言語では繰り返し専用の命令が用意されているが，アセンブラ言語にはない．そのた
め，条件分岐を使い繰り返しを行うことにする．アセンブラ言語では，以前学習したよう
に，条件分岐は比較命令(\tw{CPA,CPL})とジャンプ命令
(\tw{JMI,JNZ,JZE,JUMP,JPL,JOV})を上手に使って，繰り返し処理を行うことになる．フ
ローチャートで書くと，図\ref{fig:loop_structure}の様な構造である．

このような繰り返し構造を実現するためには，一度実行した命令に戻る必要がある．その
ために，フローチャートの上へ分岐(ジャンプ)するのである．このままだと，無限ループ
に陥るので，そこから抜けるための機構も必要である．パラメーターの値に従いループを
続けるか，そこから抜けるかを決める．それは，分岐(比較とジャンプ命令)で実現できる．

今回の問題であれば，データの個数分だけ繰り返せばよい．そのために，カウンターを用
いて，データ数のカウントをしている．これはまた，指標レジスターにも使える．
%
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio, scale=1.0]{figure/loop_structure.eps}
  \caption{分岐命令を使った繰り返し構造}
  \label{fig:loop_structure}
 \end{center}
\end{figure}
%
%---------------------------------------------------------------------
\subsection{プログラムの構造とフローチャート}
%---------------------------------------------------------------------
このプログラムのフローチャートを図\ref{fig:flow_chart_list5_6}に示す．ループ構造
になっているのが分かるだろう．それについての説明の前に，データを取り扱うレジスター
やラベルの内容を表\ref{tab:list6_variable}に示しておく．
%
\begin{table}[H]
 \begin{center}
  \caption{汎用レジスターとメモリの内容}
  \label{tab:list6_variable}
  \begin{tabular}{ll}
   \hline
   GR0 & 読み込んだデータ(比較すべき対象)を入れる． \\
   GR1 & データ数から1引いた値．指標レジスタの最大値．\\
   GR2 & データのカウンタ．0から始まり，指標レジスタとしてつかう．\\
   DATA & 調べるデータの先頭アドレス．\\
   KOSUU & 調べるデータ数が書かれているアドレス．\\
   MAX & 調べたデータの最大値を入れるアドレス．\\
   \hline
  \end{tabular}
 \end{center}
\end{table}
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio, scale=0.8]{flow_chart/REI5-6.eps}
  \caption{教科書のList5-6のプログラムの構造とフローチャート}
  \label{fig:flow_chart_list5_6}
 \end{center}
\end{figure}
%
%=====================================================================
\section{[例題7]繰り返し処理とサブルーチン}
%=====================================================================
教科書のList5-7のプログラムを例にして，サブルーチンについて説明する．以
下のことが，ここでの学習の重要なポイントである．
 \begin{itemize}\setlength\itemsep{-5pt}
  \item サブルーチンの呼び出しと呼び出し元に戻る方法を理解する．
  \item サブルーチンを使うとプログラムが部品化でき，内容が分かりやすくなる．
 \end{itemize}
%---------------------------------------------------------------------
\subsection{サブルーチンが必要な理由}
%---------------------------------------------------------------------
長いプログラムを，先に示した基本構造だけで作成することは不可能である．技術的には
可能であるが，何が書いてあるか全く分からないプログラムになってしまい．メンテナン
スが不可能である．そのため，プログラムを機能毎に細かく分割して，分かりやすくする
方法がとられる．この機能毎に分割されたプログラムをサブルーチンという．FORTRANで
は，\tw{SUBROUTINE}とか\tw{FUNCTION}というものがそれに当たる．ここでは，このサブ
ルーチンをCASL IIで実装する方法をである．
%---------------------------------------------------------------------
\subsection{教科書の例}
%---------------------------------------------------------------------
教科書の[例題6]のプログラムの動作内容は，[例題5]と全く同じである．ただし，最大値
を探索する部分をサブルーチンにして，プログラムの内容を分かりやすくしている．
%---------------------------------------------------------------------
\subsection{サブルーチン}
%---------------------------------------------------------------------
プログラムは，分かりやすく書かなくてはならない．分かりにくいプログラムはメンテナ
ンスが大変である．ここでは，最大値を探す機能をサブルーチンとして分割している．

実際，サブルーチンを作成するとにもっとも気にかけることは，データの受け渡しである
\footnote{受け渡しのデータのことを引数と言う．呼び出し側が渡すデータを実引数，呼
び出された側が受け取るデータを仮引数と言う}．
メインルーチンからサブルーチンに，ある処理を依頼するのであるが，そのためにはデー
タが必要である．メイン$\rightarrow$サブ，メイン$\leftarrow$サブと2通りある．高級
言語ではいろいろな方法があるが，CASL IIでは汎用レジスターを使うのが一般的である．

例題のプログラムを例にすると，
%
\begin{itemize}\setlength\itemsep{-3pt}
 \item メインルーチンがサブルーチンに依頼している仕事の内容は，データの最大値を
       探すことである．
 \item そのために，メインルーチンはサブルーチンに，\tw{GR1}を用いて，データの個
       数を渡している．
\end{itemize}
%
%
%---------------------------------------------------------------------
\subsection{プログラムの構造とフローチャート}
%---------------------------------------------------------------------
データを取り扱うレジスターやラベルの内容を表\ref{tab:list6_variable}と同じである．
また，プログラムのフローチャートを図\ref{fig:flow_chart_list5_7}に示す．．
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio, scale=0.8]{flow_chart/REI5-7.eps}
  \caption{教科書のList5-7のプログラムの構造とフローチャート}
  \label{fig:flow_chart_list5_7}
 \end{center}
\end{figure}
%
%=====================================================================
\section{課題}
%=====================================================================
課題を課すので，レポートとして提出すること．課題内容は，以下の通り．
%
%---------------------------------------------------------------------
\subsection{問題}
%---------------------------------------------------------------------
最初の3問はアドレス修飾とカウンターに関する問題である．次の3問はシフト演算，引き
続き繰り返しとサブルーチンに関する問いである．
\setcounter{toi_num}{1}
\begin{quote}
 \begin{itemize}
  \item[\toi] データの格納(I)
	      \begin{itemize}
	       \item データ領域を3ワード確保する．
	       \item 確保された領域に，アドレス修飾を利用して，1, 2, 3と
		     整数を格納する．
	      \end{itemize}	    
  \item[\toi] データの格納(II)
	      \begin{itemize}
	       \item データ領域を3ワード確保する．
	       \item 確保された領域に，アドレス修飾を利用して，2, 4, 6と
		     整数を格納する．
	      \end{itemize}
  \item[\toi] データの格納(III)
	      \begin{itemize}
	       \item データ領域を100ワード確保する．
	      \item 確保された領域に，アドレス修飾を利用して，2, 4,
		     6,$\cdots$,200と整数を格納する．ヒント：ジャンプ命令
		     を上手に使うこと．
	      \end{itemize}
  \item[\toi] データを8倍
	      \begin{itemize}
	       \item ラベル名\tw{DATA}が示すメモリーの領域に$(00FF)_{16}$の値
		     を格納する．
	       \item シフト命令を利用して，この値を8倍する．
	       \item 8倍された値は，ラベル名KEKKAが示す領域に格納する．
	      \end{itemize}
  \item[\toi] データを1/16倍
	      \begin{itemize}
	       \item ラベル名\tw{DATA}が示すメモリーの領域に$(30000)_{10}$の値
		     を格納する．
	       \item シフト命令を利用して，この値を1/16倍にする．
	       \item 1/16倍された値は，ラベル名KEKKAが示す領域に格納する．
	      \end{itemize}
  \item[\toi] データを5.75倍
	      \begin{itemize}
	       \item ラベル名DATAが示すメモリーの領域に$(100)_{10}$の値
		     を格納する．
	       \item シフト命令を利用して，この値を5.75倍にする．
	       \item 5.75倍された値は，ラベル名KEKKAが示す領域に格納する．
	      \end{itemize}
  \item[\toi] 1〜1000までの和を計算するプログラムの作成
	      \begin{itemize}
	       \item 1〜1000までの加算は，サブルーチンで実行すること．そして，繰り
		     返し構造を用いた加算であること．
	       \item 加算結果は，メモリーの適当な場所に格納すること．
	      \end{itemize}	    
 \end{itemize}
\end{quote}
%
%---------------------------------------------------------------------
\subsection{レポート提出要領}
%---------------------------------------------------------------------
提出方法は，次の通りとする．
% 
\begin{quote}
 \begin{tabular}{ll}
  期限 & 2月21日(火) PM 5:00 \\
  用紙 & A4 \\
  提出場所 & 山本研究室の入口のポスト \\
  表紙 & 表紙を1枚つけて，以下の項目を分かりやすく記述すること．\\
       & \qquad 授業科目名「電子計算機」\\
       & \qquad 課題名「課題　プログラム練習(その2)」\\
       & \qquad 3E\quad 学籍番号\quad 氏名\\
       & \qquad 提出日\\
  内容 & 2ページ以降に問いに対する答えを分かりやすく記述すること．
 \end{tabular}
\end{quote}
%
%=====================================================================
%　参考文献
%=====================================================================
\bibliographystyle{jplain}
\bibliography{reference}
%=====================================================================
%
%=====================================================================
\end{document}



