% Author: Wijtze de Boer <agricola@xs...>
% (no subject)  
% 2002-09-19 21:58
% 
% 
% 
% Dear all,
% 
% This is the first MMIX program that I have written and therefore I present 
% it to you humbly.
% 
% It is program C on page 76-77 of vol. 3. I have tested it and counted the 
% number of mems and oops required for the program. So far I have found no 
% problems. Please let me know if you agree or disagree.
% 
% Remarks I have to make:
% 
% 1) the original algorithm cleared the COUNT table. Since the MMIX data 
% segment is filled with zeroes except for data explicitly set differently I 
% have not incorporated this part of the algorithm.
% 
% 2) the comments show the number of times the instruction is executed in the 
% same terminology as prof. Knuth used. I added the weight in mems and oops.
% 
% The program needs (3N + 2B - 2) mems and (6N + 6A + 3B + 1) oops and (N + 
% B)x2 oops for wrong branches.
% 
% Suggestions and comments are greatly appreciated.
% 
% Regards,
% 
% Wijtze de Boer


% Program C pg 76-77 TAoCP Vol. 3, D.E. Knuth
% MMIX version
% email agricola@xs4all.nl
%
input  IS $0
count  IS $1
n      IS $2
t      IS $255
i      GREG
j      GREG
ti     GREG
tj     GREG
c      GREG

       LOC  Data_Segment
inputa GREG @
       OCTA 0			Dummy count[0]
       OCTA 503
       OCTA 087
       OCTA 512
       OCTA 061
       OCTA 908
       OCTA 170
       OCTA 897
       OCTA 275
       OCTA 653
       OCTA 426
       OCTA 154
       OCTA 509
       OCTA 612
       OCTA 677
       OCTA 765
       OCTA 703
counta GREG @
       LOC @+8*17
naddr  GREG @
       OCTA 16

newln  BYTE #a,0,0,0
blnks  BYTE " 000",0,0,0,0
buf    BYTE " 000",0,0,0,0


       LOC  #100
Main   LDA  input,inputa      1   v        get address of input
       LDA  count,counta      1   v        get address of count
       LDOU n,naddr,0         1   m+v      get n
       SL   i,n,3             1   v        C2. loop on i
       JMP  1F                1   v
2H     LDOU c,count,i        N-1  m+v          
       LDOU ti,input,i       N-1  m+v
3H     LDOU tj,input,j        A   m+v
       CMPU t,ti,tj           A   v        C4. Compare Ki : Kj
       BP   t,4F              A   v/3v(B)
       LDOU t,count,j         B   m+v      Count[j]
       ADDU t,t,1             B   v         + 1
       STOU t,count,j         B   m+v        -> Count[j] 
       JMP  5F                B   v
4H     ADDU c,c,1            A-B  v        Count[i] <- Count[i] + 1
5H     SUB  j,j,8             A   v        C3. Loop on j 
       PBP  j,3B              A   v/3v(N-1)
       STOU c,count,i        N-1  m+v
       SUB  i,i,8            N-1  v
1H     SUB  j,i,8             N   v        N >= i > j > 0
       PBP  j,2B              N   v/3v(1)
       TRAP 0,Halt,0