% Package to format MMIX programs with TeX
% (and some useful commands to document them)
% Author: Udo Wermuth
% %%%
% before the macro package is loaded the
%      following must be \def'ed
%      required: \date, \author, \source
% the program name is taken from the mms-file
%      but it can be overwritten
%      optional: \pgmname
% start a programm with all \def's in one line
% (n is the \mmixtype explained elsewhere):
%  \def\date{<date>}\def\author{<name>}
%  \def\source{<volume, page>}\input mmix =n
% use \eop in the comment of the last
%    source line
% end the input file with a line that
%    contains either (! is the commchar) 
%    ``!\endprogram\bye'' (even \mmixtype)
%    or ``!!\endprogram\bye'' (odd \mmixtype)
%    or use \endwAoA instead of \endprogram
%       to input a file with an analysis
% %%%
% don't load the file several times
% but reset variables, fonts etc.
\def\ifundef #1 {% see \TeX book, ex. 7.7
  \expandafter\ifx\csname #1\endcsname\relax}
\ifundef mmixisloaded \def\mmixisloaded{true}%
\else\getmmixtype\endinput\fi
% %%%
% Header and Footer
\headline={\sevenrm Author: \authorH\hfill
           Program: \pgmnameH.mms (\sourceH)}%
\footline={\sevenrm Date: \dateF\hfill
           \sevenbf\folio}%
% file name for the ``Analysis of Algorithm''
\def\AoAfile{\pgmnameH_aoa.tex}
\def\checkextdata{%
  \ifundef pgmname \def\pgmnameH{\jobname}%
  \else\let\pgmnameH=\pgmname
    \let\pgmname=\undefined
  \fi
  \ifundef author \def\authorH{Unknown}%
  \else\let\authorH=\author
    \let\author=\undefined
  \fi
  \ifundef source \def\sourceH{TAOCP}%
  \else\let\sourceH=\source
    \let\source=\undefined
  \fi
  \ifundef date \def\dateF{\number\year}%
  \else\let\dateF=\date
    \let\date=\undefined
  \fi}
% %%% Definitions
% count registers
\newcount\lnocnt % counter for line numbers
\newcount\mmixtype % a value between -5 and 5
% -1,0,1: no line numbers, no space reserved
% absolute value 2,3: add column for 2 digits
% absolute value 4,5: add column for 3 digits
% > 1: start line numbering directly
% <-1: a user command starts numbering
% write a line (`!' is the commchar) with
%   even value: label op expr ! comment
%   odd value:  label op expr ! time ! comment
% dimen registers
\newdimen\lnotwodigitswidth   % 2 digits col
\newdimen\lnothreedigitswidth % or 3 digits
\newdimen\timecolumnwidth % column for time 
% if flags
\newif\ifcolforlno     % true: add col for lno
\newif\ifnumberlines   % true: number the lines
\newif\ifthreedigitlno % true: use 001..999
\newif\ifeopused % true: ``\eop'' was used
\newif\iftimeinfostated % true: add time col
% name 9pt and 6pt fonts
\font\ninerm=cmr9  \font\sixrm=cmr6
\font\ninesy=cmsy9 \font\sixsy=cmsy6
\font\ninei=cmmi9  \font\sixi=cmmi6
\font\nineit=cmti9 \font\ninesl=cmsl9
\font\ninett=cmtt9
\font\ninebf=cmbx9 \font\sixbf=cmbx6
% special in TeX but common in MMIX
\def\mmixdospecials{\do\ \do\$\do\&\do\#%
                    \do\^\do\_\do\%\do\~}
% remaining special characters in TeX
\def\texdospecials{\do\\\do\{\do\}}
\def\uncatcodespecials{% redef special chars
  \def\do##1{\catcode`##1=12 }%
  \mmixdospecials\texdospecials}
% help messages
\newlinechar=`\^^J
\newhelp\mmixtypeerror{%
 mmixtype is the number
   stated after \string\input\space mmix.^^J%
 It must be between -5 and 5.
 Three aspects are coded into it:^^J%
 if it is odd
   time information is given (use two !);^^J%
 if it is -1, 0, 1
   no line numbers are present;^^J%
 if it is -3, -2, 2, 3
   line numbers have two digits;^^J%
 if it is -5, -4, 4, 5
   line numbers have three digits;^^J%
 if it is >1
  immediate numbering of lines is started.}%
% %%% Useful commands
\def\MIX{{\ninett MIX}}
\def\MMIX{{\ninett MMIX}}
\def\MMIXAL{{\ninett MMIXAL}}
\let\NULL\Lambda % the null link
\def\AVAIL{\hbox{\ninett AVAIL}}% free space
\let\Gets\Leftarrow % get space from AVAIL
\let\implies\Rightarrow % more ``logical''
% units for the analysis: oops and mems
\def\oops{\hbox{$\upsilon$}}\let\oop=\oops
\def\mems{\hbox{$\mu$}}     \let\mem=\mems
% reference to equation numbers of TAOCP
\def\numeq(#1){\hbox{$({\oldstyle#1})$}}
\def\eq(#1){% outputs Eq. (...)
   \hbox{Eq.\thinspace\numeq(#1)}}
\def\Eq(#1){% outputs Equation (...)
   \hbox{Equation \numeq(#1)}}
% steps in algorithms
\def\algidphrase#1#2#3.#4.{% #1 #arguments;
  % #2 phrase delimiter; #3 step id; #4 phrase
  $\underline{\hbox{\sl
      \vphantom{y}#3.%
      \ifnum #1>1 \enspace #4#2\fi}}%
  $\space}
\def\step#1. #2.{\algidphrase2.#1.#2.}
\def\steq#1. #2?{\algidphrase2?#1.#2.}
\def\stepid#1.{\algidphrase1-#1.-.}
% place the command in (odd number) or
% just above (even number) the middle
\def\mlsc#1:#2{% #1 #lines; #2 comment
  \smash{\ifodd#1\else\lower.45\baselineskip\fi
    \hbox{$% next line: see \TeX book, p.194
      \openup-1\jot % cancel for \eqalign
      % compute height of brace:
      \dimen255=\baselineskip
      \advance\dimen255 by 3pt
      \multiply\dimen255 by #1\relax
      \advance\dimen255 by -8pt
      \left.\kern-.5em % empty left brace
      \eqalign{\vrule height\dimen255
                  width 0pt depth 0pt }%
      \right\}% visible right brace
      $\thinspace#2}}}
% special operations
\def\dm{% dot minus: saturating subtraction
  \mathbin{\mathop{\kern0pt \smash{-}}%
    \limits^{\raise.55ex\hbox{$\textstyle.$}}}}
\def\ite(#1?#2:#3){% if-then-else; Vol.4a, p.96
  (#1\,{\rm?\ }#2{\rm:}\enspace#3)}
% symbols of \TeX
\def\vs{{\tt\char32 }}% visible space
\def\bs{{\tt\char92 }}% backslash
\def\bo{{\tt\char123 }}% open brace
\def\bc{{\tt\char125 }}% close brace
\let\lstroke\l
\def\l\_{{\tt\char95 }}% long underline
\def\h\#{\hbox{${}^\#$}}% high # (hex no.)
% %%% my shortcuts
% output rm or tt in math with 1 to 3 chars
\def\r#1{{\rm #1}}
\def\rr#1#2{{\rm #1#2}}
\def\rrr#1#2#3{{\rm #1#2#3}}
\def\m#1{{\tt #1}}
\def\mm#1#2{{\tt #1#2}}
\def\mmm#1#2#3{{\tt #1#2#3}}
% output of rm or tt text in boxes or arrays
\def\rb#1{\hbox{\rm #1}}% rm box
\def\mb#1{\hbox{\tt #1}}
\def\ra#1[#2]{\hbox{\rm #1[$#2$]}}% rm array
\def\ma#1[#2]{\hbox{\tt #1[$#2$]}}
\def\gts{% align `g' with the op-code col
  \iftimeinfostated
    {% omit time column if \mmixtype is odd
     \ninerm\hskip-\timecolumnwidth
     {\tentt\ }}% add space for 2nd commchar
  \fi
  {\tentt>\space }}
% used to state number of bad decisions
\def\bad#1\bad{\ignorespaces}% no output
% %%% Macros for the last line(s)
% typeset the Analysis of the Algorithm
\def\Analysis{\medbreak
  \def\rm{\fam0\tenrm}% back to 10pt
  \textfont0=\tenrm \scriptfont0=\sevenrm
  \textfont1=\teni  \scriptfont1=\seveni
  \textfont2=\tensy \scriptfont2=\sevensy
  % fam3 was not changed
  \def\it{\fam\itfam\tenit}%
         \textfont\itfam=\tenit
  \def\sl{\fam\slfam\tensl}%
         \textfont\slfam=\tensl  
  \def\tt{\fam\ttfam\tentt}%
         \textfont\ttfam=\tentt  
  \def\bf{\fam\bffam\tenbf}%
         \textfont\bffam=\tenbf
         \scriptfont\bffam=\sevenbf
  \def\oldstyle{\mit\teni}%
  \rm % activate \tenrm
  \noindent{\tenbf Analysis}\par% the headline
  \nobreak\smallskip\noindent}
\def\eop{% end of program symbol
  \qquad\vrule height 7pt depth 1pt width 3pt
  \eopusedtrue\stopnumbering}
\def\clearline{% remove 0--2 empty hboxes
  {\setbox0=\lastbox \setbox0=\lastbox}}
\def\endprogram{\clearline
  \ifeopused\eopusedfalse
  \else\message{^^JWarning: end the program
                with \string\eop^^J}%
  \fi
  \endgroup% opened in \getmmixtype
  \resetTeXcomment}
\def\endwAoA{\endprogram\bigskip
  \Analysis \input\AoAfile}
\def\printlinenumber{% with leading 0s
  \ifthreedigitlno % how many digits?
    \hbox to \lnothreedigitswidth{\it
      \ifnum\lnocnt<100 0\fi
      \ifnum\lnocnt<10 0\fi \number\lnocnt
      \hss}%
  \else\hbox to \lnotwodigitswidth{\it
      \ifnum\lnocnt<10 0\fi \number\lnocnt
      \hss}%
  \fi}
\def\numbermmixline{% shall no. be printed?
  \ifcolforlno
    \ifnumberlines
      \global\advance\lnocnt by 1
      \printlinenumber             % yes
    \else\phantom{\printlinenumber}% no
  \fi\fi}
% make style of numbers available for others
\def\pgmline#1{% print #1 as line number
  \gdef\argpgmline{#1}% store #1 and look ahead
  \futurelet\next\pgmlinex}
\def\pgmlinex{% check if \next is . or ,
  \if.\next {\it\argpgmline}%      no \/
  \else\if,\next {\it\argpgmline}% no \/
  \else {\it\argpgmline\/}%       add \/
  \fi\fi}
% %%% Format
\def\setflagsformmixtype{% analyse \mmixtype
  \ifnum\mmixtype<0
    \mmixtype=-\mmixtype % wait with numbering
  \else
    \numberlinestrue % prep. to number 1st line
  \fi
  \ifnum\mmixtype>1 % activate numbering
    \colforlnotrue
    \ifnum\mmixtype>3 % use 3 digits
      \threedigitlnotrue
  \fi\fi
  \ifodd\mmixtype % timing info is present
    \timeinfostatedtrue
  \fi}
% start and stop line numbering
\let\startnumbering=\numberlinestrue
\let\stopnumbering=\numberlinesfalse
\def\setcommchar#1{% boundary for verbatim
  \vskip-\baselineskip% for first end of line
  \gdef\commchar{#1}%
  \def\par{\endgraf\verbatim#1}}
% Verbatim macros
\def\verbatim{\begingroup % ends in \doverbatim
  \setupverbatim
  \doverbatim}
\def\setupverbatim{%
  \def\par{\leavevmode\endgraf\noindent}%
  \catcode`\`=\active
  \obeylines
  \uncatcodespecials
  \obeyspaces}
% now make a blank a control space
{\obeyspaces\global\let =\ }% 
% and avoid ligatures of ? and ! with `
{\catcode`\`=\active \gdef`{\relax\lq}}%
\long\def\doverbatim#1{% #1 is the commchar
  \everypar{\numbermmixline}%
  \def\nextmmixline##1#1{\noindent
    \tentt##1%
    \endgroup % opened in \verbatim
    \printtimeinfo}%
  \iftimeinfostated
    \gdef\printtimeinfo##1#1{% #1<time>#1
      \hbox to \timecolumnwidth{%
        \hss$ ##1 $\hss}\resetpar}%
  \else\global\let\printtimeinfo\resetpar
  \fi
  \nextmmixline}
\def\resetpar{\everypar{}\let\par=\endgraf
  \ignorespaces}
\def\newcommchar#1{% change the commchar
  \gdef\commchar{#1}%
  \def\par{\endgraf\verbatim#1}% new \par
  \obeylines}% end-of-line is the new \par
% switch to 9pt fonts
\def\setupfonts{\def\rm{\fam0\ninerm}%
  \textfont0=\ninerm  \scriptfont0=\sixrm
  \textfont1=\ninei   \scriptfont1=\sixi
  \textfont2=\ninesy  \scriptfont2=\sixsy
  % no changes for fam3
  \def\it{\fam\itfam\nineit}%
         \textfont\itfam=\nineit
  \def\sl{\fam\slfam\ninesl}%
         \textfont\slfam=\ninesl
  \def\tt{\fam\ttfam\ninett}%
         \textfont\ttfam=\ninett
  \def\bf{\fam\bffam\ninebf}%
         \textfont\bffam=\ninebf
         \scriptfont\bffam=\sixbf
  \def\oldstyle{\mit\ninei}%
  \rm}
% set the variables to their default values
\def\setvariables{\mmixtype=0 \lnocnt=0
  {\setbox0=\hbox{\nineit 00\tentt\quad}%
   \global\lnotwodigitswidth=\wd0
   \global\lnothreedigitswidth=1.25\wd0 }%
  {\setbox0=\hbox{$2M+M$}% 10pt gives white space
   \global\timecolumnwidth=\wd0 }%
  \colforlnofalse     \numberlinesfalse 
  \threedigitlnofalse \timeinfostatedfalse}
\def\testvalueofmmixtype{% value must be < 6
  \ifnum\mmixtype>5
    \errhelp\mmixtypeerror
    \errmessage{The number \string\mmixtype
       \space must be between -5 and 5}%
  \fi}
% %%% Start
{\obeylines \catcode`\%=\active
 \gdef\handleTeXcomments{\catcode`\%=\active
   {\obeylines \gdef%##1
    {\endgraf\expandafter\verbatim\commchar}}}}%
\def\resetTeXcomment{\catcode`\%=14 }
\def\getmmixtype{% needs a ``right side''
  \checkextdata   \setupfonts
  \setvariables   \handleTeXcomments
  \afterassignment\egroup% an assignment ends
  \bgroup                        % this group
  \aftergroup\setflagsformmixtype
  \aftergroup\begingroup% closed in last line
  \aftergroup\setcommchar
  \aftergroup!% this is the default commchar
  \aftergroup\obeylines
  \aftergroup\testvalueofmmixtype
  \aftergroup\par
  \global\mmixtype}% now get \mmixtype
\getmmixtype
