% Section 2.3.5, Exo 4: Algorithm E (Marking)
% Author Chan Vinh VONG <chanvinh.vong@gmail.com>
% Draft Version 2012 April 8th
%
% The MIX version of the exercise requires a node to be stored in one
% word. For MMIX, we will use two OCTAs per node with the following
% structure:
%
%  >|<-------OCTA------>|<
%   +-------------------+
%   | ALINK/63 (MARK/1) | (BA+0)
%   +-------------------+
%   | BLINK/63 (ATOM/1) | (BA+8)
%   +-------------------+
%
% Notes:
% - {A|B}LINK targets other nodes and are thus octa-byte aligned
% - MARK=1 or ATOM=1 will make {A|B}LINK change their parity
% - when ATOM=1, {A|B}LINK may contain addresses of data stored
%   elsewhere in memory using any alignment except one-byte alignment
%   due to the existence of MARK|ATOM bit flags
%

dALINK  IS 8*0
dBLINK  IS 8*1
dNODE   IS 8*2

% Calling Sequence:
%     $1 <- PO
%     PUSHJ $0,MARK
%
        PREFIX MARK:
P       IS $0
T       IS $1
Q       IS $2
x       IS $3
m       IS $4
NULL    IS $5
:MARK   SET T,0     % E1. Subroutine call already did P <- P0
        SET m,1     % mask
        PUT :rM,m
        SET NULL,0
        
        % E2. Mark P
E2      LDOU x,P,:dALINK
        MUX  x,m,x
        STOU x,P,:dALINK % MARK(P) <- 1
        
        % E3. Go up if atom
E3      LDOU x,P,:dBLINK
        BOD  x,E6
        
        % move on ALINK
E4      LDOU Q,P,:dALINK
        SRU  x,Q,1        % avoid mark flag in ALINK
        BZ   x,E5         % Q = NULL?
        LDOU x,Q,:dALINK
        BOD  x,E5         % MARK(Q) = 1?
        LDOU x,P,:dBLINK
        MUX  x,m,x
        STOU x,P,:dBLINK % ATOM(P) <- 1
        LDOU x,P,:dALINK
        MUX  x,x,T
        STOU x,P,:dALINK % ALINK(P) <- T w/o changing flag in ALINK
        SET  T,P            % T <- P
        MUX  P,NULL,Q       % P <- Q w/o flag
        JMP  E2

        % move on BLINK
E5      LDOU Q,P,:dBLINK
        SRU  x,Q,1
        BZ   x,E6         % Q = NULL?
        LDOU x,Q,:dALINK
        BOD  x,E6         % MARK(Q) = 1?
        LDOU x,P,:dBLINK
        MUX  x,x,T
        STOU x,P,:dBLINK  % BLINK(P) <- T w/ flag
        SET  T,P          % T <- P
        MUX  P,NULL,Q     % P <- Q
        JMP E2
        
        % Rewire and go up
E6      BZ   T,9F        % T=0, DONE
        SET  Q,T         % Q <- T
        LDOU x,Q,:dBLINK
        BEV  x,1F        % ATOM(Q) = 0?
        MUX  x,NULL,x
        STOU x,Q,:dBLINK % ATOM(Q) <- 0
        LDOU x,Q,:dALINK
        MUX  T,NULL,x    % T <- ALINK(Q) w/o flag
        MUX  x,x,P
        STOU x,Q,:dALINK % ALINK(Q) <- P w/ flag
        SET  P,Q         % P <- Q
        JMP E5
1H      MUX  T,NULL,x    % T <- BLINK(Q) w/o flag
        MUX  x,x,P
        STOU x,Q,:dBLINK % BLINK(Q) <- P w/ flag
        SET  P,Q         % P <- Q    
        JMP E6

9H      POP 0,0
        PREFIX :