LOC #3000000000000000 % Section 2.2.3, Exo.2 % Author Chan Vinh VONG % Draft Version 2012 March 20th % % We are dealing with an AVAIL Chain and a Node Chain. % The exercise specifies that the INFO is to be stored in a new node, % this implies that the allocation process should be taken care of. % % The structure for one Node is: % % OCTA % +----------------+ % (BA+0) | INFO | % +----------------+ % (BA+8) | LINK | % +----------------+ % % The size of a Node (or the distance between 2 consecutive allocated % nodes) is thus +16 bytes. % % A noticeable change between MIX and MMIX for this exercise is about % how to make the calling sequence. % % In MIX, we have (V1e3/p.269): % % JMP INSERT % NOP T % % This technique writes a data in what is now considered in MMIX as the % Text Segment. The closest equivalent in MMIX is (V1F1/p.54): % % JMP INSERT % TETRA T % % However, as the TETRA keyword indicates, this limits the size of T to % half the size of an address (OCTA), i.e the location pointed to % should be in between 0 and 2^32-1. There was no problem in MIX since % the range of +AA goes from 0 to 4096 which covers the 4000 words of % memory.But in MMIX, this may be a major constraint. We thus have to % put the link variable T in the Text Segment and not in the Data % Segment, nor in a GREG (for the sake of this exercise). % % In order to test the INSERT method, we set up: % - an area for allocating Nodes in the Data Segment % - a helper subroutine for allocation of the Nodes using the POOLMAX % technique (V1e3/p.257) % - a basic OVERFLOW method which only prints the error and exits the % program % POOLTOP GREG @ % top Node of the pool of Nodes (none at init) LIMIT GREG @+88 % limit the stack (5 Nodes max) LOC Data_Segment GREG @ AVAIL GREG 0 % pointer to the AVAIL chain temp GREG 0 test GREG 0 ERR_OF BYTE "Overflow",#A,0 dINFO IS 0 % d stands for delta, to be used for relative addressing dLINK IS 8 dNODE IS 16 LOC #100 GREG @ T OCTA 0 % pointer to the stack of live Nodes % technically it is always #100 but another routine % may use another chain of live nodes T' stored in % another location % Deal with the Overflow gracefully OVERFLOW LDA $255,ERR_OF TRAP 0,Fputs,StdOut JMP Exit % Helper subroutine for Node allocation using the POOLMAX technique, % with possible overflow in which case no node is allocated. This % leaves the OVERFLOW dispatching to the INSERT method, which is done % in the MIX version of this exercise. As the AVAIL Chain depletes, % AVAIL will point to 0 eventually. The newly allocated node is added % to the AVAIL Chain. % % Calling Sequence: GO $0,ALLOC % Entry Conditions: none % Exit Conditions : AVAIL points to a newly allocated Node % ALLOC LDA $2,POOLTOP % will we overflow if we go on? ADD $2,$2,dNODE CMP test,$2,LIMIT BNN test,9F % yes, don't allocate LDA $1,AVAIL % no, allocate LDA AVAIL,POOLTOP STO $1,AVAIL,dLINK SETL $3,#2A STO $3,AVAIL,dINFO LDA POOLTOP,$2 9H GO $0,$0,0 % This is the answer to exercice 2.2.3-2. % % Calling Sequence: JMP INSERT; TETRA T % Entry Conditions: $1 = information to be put into the INFO field of a % new node % Exit Conditions : The stack whose pointer is the link variable T has % the new node on top; $1, $2 altered % Exceptions : Overflow if there is no more AVAILable node % allocated (see ALLOC) % INSERT LDA temp,AVAIL CMP test,temp,0 BZ test,OVERFLOW STO $1,AVAIL,dINFO LDO $1,AVAIL,dLINK LDA AVAIL,$1 LDT $1,$0 % $1 <- LOC(T), here's the tricky part LDO $2,$1 % $2 <- T, it was just a pointer to a pointer STO $2,temp,dLINK STO temp,$1 9H GO $0,$0,4 % don't forget to skip the TETRA after $0 % Testing routine counter GREG 0 Main SETL counter,5 % Produce 5 Nodes max (>5 => no more nodes) 1H CMP test,counter,0 % BP here to monitor the allocations BZ test,2F GO $0,ALLOC SUB counter,counter,1 JMP 1B 2H LDA $4,T % self-modify text segment LDA $3,@+7*4 STT $4,$3 SETL counter,5 % Consume the Nodes (over 5 => Overflow) 3H CMP test,counter,0 % BP here to monitor the chains change BZ test,Exit LDA $1,counter % we just store the value of the counter GO $0,INSERT TETRA SUB counter,counter,1 JMP 3B Exit TRAP 0,Halt,0 % script for interactive mode (don't forget to double-check your BPs): % % M100# % g251 % M3000000000000000# % M3000000000000008# % M3000000000000010# % M3000000000000018# % M3000000000000020# % M3000000000000028# % M3000000000000030# % M3000000000000038# % M3000000000000040# % M3000000000000048# % M3000000000000050# % M3000000000000058# % % REM: % - M100# is T, the address in memory of the top of the live Nodes % - g251 is AVAIL (4th GREG) % % END OF DRAFT