% Section 2.2.3, Exo.27: Subroutine Allocation
% Author Chan Vinh VONG <chanvinh.vong@gmail.com>
% Draft Version 2012 March 27th
% Refactored    2012 April  9th
%
% This MMIX program is an answer to the exercise 27 page 272 of TAoCP
% Volume 1.
%
% Data Structure Implementation: (Tape) Directory =====================
%
% In the MIX version of the program, the following structure was used:
%
% +--+--+--+--+--+--+
% |  B  |SPACE| LINK| 1x MIX Word
% +--+--+--+--+--+--+
% |  B  | SUB1| SUBn|
% +--+--+--+--+--+--+
%
% In this proposal, we make use of a fact mentioned in page 325 of V1:
% addressing with octa-byte aligment allows storage of extra flags in
% the address. More precisely, 8 values are available within an address
% using that technic. Thus, we can store B within an absolute address
% with octa-byte alignment!
%
% We will work on blocks of blocks of OCTAs, the embedded flag will
% indicate the end of a block. We thus use full 64-bit addressing.
%
%                   >|<-----OCTA----->|<
%                    +----------------+
%                    |     SPACE      | no flag possible (not a link)
%                    +----------------+
%                    |      LINK      | flag 2
%                    +----------------+
%                    |      SUB1      | flag 2
%                    +----------------+
%                    |      ....      | flag 2
%                    +----------------+
%                    |      SUBn      | flag 0
%                    +----------------+
% 
% In the MIX version, the markers had the following meaning:
%
%                   ======================
%      /marking +2  | unmarked | marked  |
%    =====================================
%    | Block        |     0    |    2    |
%    =====================================
%    | End of Block |    -1    |    1    | -> Phase 1: |B| = 1
%    =====================================
%                                   V
%                                Phase 2:
%                                 B > 0
%
% Here with MMIX, we will use:
%
%                   ======================
%      /marking +2  | unmarked | marked  |
%    =====================================
%    | Block        |     2    |    3    |
%    =====================================
%    | End of Block |     0    |    1    | -> Phase 1: B < 2   
%    =====================================
%                                   V
%                                Phase 2:
%                                 B odd
%
%
% Data Structure Implementation: X Table ==============================
%
% The choice for the directory constraints this one. So let's use the
% following layout:
%
%                   >|<-----OCTA----->|<
%                    +----------------+
%                    |   SUBROUTINE   |
%                    +----------------+
%                    |       --       |
%                    +----------------+
%
% Each X[k] is made of 2 OCTAs, the algorithm will fill in the first
% one and update the second:
%
%                   >|<-----OCTA----->|<
%                    +----------------+
%                    |   SUBROUTINE   |
%                    +----------------+
%                    |      MLOC      |
%                    +----------------+
%
% =====================================================================
%
% Notes: think about using a NULL octa at the end of each block, this
% may make things faster at the expense of one more octa per block
% (affordable?).
%

dSPACE  IS 8*0
dLINK   IS 8*1

        PREFIX ALLOC:
XTable  IS $0
N       IS $1
FIRST   IS $2
MLOC    IS $3
k       IS $4
P       IS $5
LINK    IS $6
t       IS $7
SUBROUT IS $8
LinkFlag IS $9
:ALLOC  SET t,#7     % covers possible flag in an octabyte address
        PUT :rM,t
        SLU k,N,4
A0      SUB k,k,16         % A0. Init
        LDOU P,XTable,k
        LDOU LINK,P,:dLINK
        BOD LINK,1F        % MIX: B(X[J]) <= 0, MMIX: P.LINK is even
        MUX t,LINK,0
        ADD t,t,1
        MUX LINK,t,LINK    % flag <- flag + 1
        STOU LINK,P,:dLINK
1H      BP  k,A0

A1      BZ  N,B1
        SUB N,N,1          % N <- N - 1
        16ADDU P,N,XTable
        LDOU P,P
        ADD  P,P,8
        
A2      LDOU LINK,P        % LINK <- LINK(P)
        MUX  t,LINK,0
        CMP  t,t,2
        BN   t,A1          % End Of Block? (flags 0 or 1)
A3      ADD  P,P,8
        LDOU SUBROUT,P
        LDOU LINK,SUBROUT,:dLINK
        BOD  LINK,A2
        MUX t,LINK,0
        ADD t,t,1
        MUX LINK,t,LINK
        STOU LINK,SUBROUT,:dLINK % marked
        16ADDU t,N,XTable
        STOU SUBROUT,t
        ADD N,N,1
        JMP A3
        
        
B1      SET P,FIRST
        SET k,0
B2      LDOU LinkFlag,P,8
        MUX LINK,k,LinkFlag
        BNZ LINK,B3
        16ADDU t,N,XTable
        STCO 0,t,0
        STOU MLOC,t,8
        JMP Exit
B3      BEV LinkFlag,B4
        16ADDU t,N,XTable
        STOU P,t,0
        STOU MLOC,t,8
        LDOU t,P,0
        ADDU MLOC,MLOC,t
        ADD  N,N,1
B4      SET P,LINK
        JMP B2

Exit    POP 0,0
        
        PREFIX :