$l1m
$44(Graphics interpreter)
$b2
$18[Introduction]
$p1
This document is a report of an experiment which defines and implements
a simple universal interface
between the applications programs, system utilities and user interface
modules on one side and the graphics support component of the system
on the other.
Such structured hierarchical graphics interface should fit easily into a 
variety of applications through supporting structured hierarchical dependencies
of objects both between and within the applications. 
It which attempts to provide flexible workspaces for the
individual applications while presenting a manageable and uniform
front to the graphics support subsystem. 
Several similar approaches have been suggested e.g. in [Foley 82] and 
[Lantz 84] but with a limited number of practical implementation
examples and less emphasis on their application to general interactive
computing environment. Recently work has been started on defining a standard
for such an interface: Programmer's Hierarchical Interactive Graphics
Standard (PHIGS).
$p1
The interface is a directed graph, residing in the main system memory
where client processes in the system can manipulate their own allocated
sections on one side and a separate evaluation process caters
for the creation of the resulting images on the other as shown in a
paraphrase of a windowing system below. 
In other words, the evaluation process
can be viewed as a function taking the graph as an argument and producing
the image as a value. 
$b0
#
$p1
The top part of the graph is usually under the supervision of the system window
manager, while its exit edges provide linkage to applications subgraphs
running within their allocated subwindows. Such hierarchy may reoccur 
recursively
where an application may have its own subwindow manager maintaining its
menu, workspace and other areas of activity.
$p1
The image is computed through a depth-first scan of the descriptor structure,
where for each of the nodes, its local evaluation environment is saved,
prior to following any of the downwards edges and subsequently restored 
on return. The ordering of the exit edges defines the eventual overlap of
the graphical objects created by their execution.
Evaluation is terminated after the execution along the last vertical
edge of the node, at which it was invoked, thus allowing nested invokation
of selected substructures.
$p1
The speed of generating new images is strongly
dependent on the complexity of the graph and
on whether the evaluation process has to share the processor with other
processes, or it can have its own customised evaluation engine.
Depending on certain properties of the graph, like being acyclic or even
a tree, various optimisation techniques allow for only parts of the
graph to be scanned, still yielding a valid picture.
$b2
$18(Graph construction)
$p1
The graph is constructed out of fixed-format nodes with two exit edges:
a $32(vertical) and a $32(horizontal) one. The vertical
edge is used to represent image hierarchy and the horizontal edge
supports linkage of multiple image components at the same level of
hierarchy.
$p1
Leaf nodes in such a directed binary graph i.e. those with no vertical 
exit edges are generally
responsible for the final drawing operations, and they can invoke 
operations like filling a polygon, drawing a stright line, drawing a
string of characters etc. These are executed with the necessary current
environmental attributes like: colour, font, scaling, clip boundaries etc. 
Some of the drawing
operations can have impact on the environment, like deposition of
character strings moves the working coordinates along the string baseline.
Non-leaf nodes are generally responsible for the composition of the picture
out of subordinate ones as well as for the necessary modifications of the
environment, like coordinate manipulations, colour and font selection etc.
Some of these operations, like moving or scaling are cummulative
along the vertical paths in the graph; others like font or colour selection
are nested.
There are also some general control nodes, which allow the user
to exercise control over the evaluation process.
$b0
#
$b1
$22(Format of the node)
$p1
Each binary node consists of 11 consecutive 16-bit half-words, where
the first two bytes contain the instruction code and the execution flags
of the node. They are followed by a long-word of argument field, and
then two long-words, where on exit, the evaluation process deposits the 
relative
dimensions of the bounding box for the image subordinate to the node.
These dimensions are relative to the environmental working
$32[(workX,workY)] coordinates on the entry to the node. 
The argument field can contain
a 32-bit pointer, two 16-bit geometrical or indexing arguments, or
for some single-argument operations only the first half-word is taken into
account.
The last two long-words contain downwards and rightwards pointers of
the exit edges, with execution flags $32[Down] and $32[Right] indicating their
validity. Flag $32[Pointer] when 1 represents indirection in fetching
of arguments.
$p1
We will describe further details of the nodes while presenting a number of
example applications. 
In all illustrations, nodes will be denoted with their associated opcodes
and those of the flags, which are set to 1. Values of 1 for the
$32[Down] and $32[Right] flags are indicated by the presence of the 
corresponding exit edges.
$b2
$22(Arguments and data structures)
$b2
$a indent=1
$item All pointers are 32-bit integers, interpreted as absolute 
byte addresses in the machine address space.
$b1
$item Additive/subtractive arguments are represented as 16-bit 2's 
complement integers.
$b1
$item Scaling factors are signed 16-bit numbers with
binary point between bits 7 and 8 of the word.
$a indent=0  
$p1
There are a number of data structures that can appear as arguments in the
instructions.
$b1
$a indent=4        
$i0 pixelmap $t4 is represented by 2 16-bit words specifying the width and the
height of the map, followed by the map itelf, stored as width-long
sequence of 1 pixel-wide vertical lines; one byte per pixel.
Following the increasing addresses
of the representation pixels will be drawn on the screen from bottom upwards, 
with consecutive vertical lines appearing to the right of their predecessors.
$b1
$i0 template $t4 consists of a 4 half-words header followed by
the bitmap of the template.
The half-words 0 and 1 contain template offsets in X and Y from the current 
working coordinates and half-words 2 and 3 specify width and height
of the template. 
Offsets are primarily used for positioning templates of the
characters relatively to the baseline and the in-line horizontal positioning
coordinate. They will be usually 0 for non-character type templates.
The template itself is stored as 
(width/16 + 1)-long sequence of height-long vertical strips. Following the
increasing addresses in the representation, individual strips will be drawn
on the screen from bottom upwards, with most significant bits on the left.
Consecutive strips are placed to the right of their predecessors.
$b1
$i0 font $t4 is stored as a list of templates for individual characters.
Such list of templates is preceeded by an
array indexed by the codes of characters and containing pairs of short
integers.
The first integer in each pair
contains offset from the base of array to the template of the corresponding
character and the second contains the formatting width of the character.
Entries of 0 in the first element of the pair indicate characters for which
templates have not been defined in that particular font and their
occurence is used by the protocol as one of termination conditions 
when drawing character strings.
Width of the character represents the distance to the base of the
next character to the right.
$b1
$i0 arrays $t4 are always 1-dimensional short-integer arrays, with the
lowest element having index 0.
$a indent=0      
$b2
$22(Evaluation environment)
$p1
Each node is executed within the environment inherited from the previous node,
and it may modify this environment prior to passing it to the next nodes: down, to
the right or up.
$p1
The environment consists of:
$a indent=5
$b1 $i0 ink $t5 current colour for the subordinate drawing nodes
$b1 $i0 planes $t5 a mask of planes with enabled write operation for the 
subordinate drawing nodes
$b1 $i0 (workX,workY) $t5 a pair of current working coordinates
$b1 $i0 (bblX,bbbY) $t5 left-hand bottom corner of the image bounding box
$b1 $i0 (bbrX,bbtY) $t5 right-hand top corner of the image bounding box
$b1 $i0 (cblX,cbbY) $t5 left-hand bottom corner of the environmental clipping
box
$b1 $i0 (cbrX,cbtY) $t5 right-hand top corner of the environmental clipping box.
Clip boundaries are the intersection of all the clipping boundaries set by
the clipping nodes above the current position. Deferred scaling node
maps them (division) into the virtual coordinates of the subordinate image.
$b1 $i0 (dscaleX,dscaleY) $t5 A deferred scaling 
factor provided to support virtual to physical coordinate transformation. 
Deferred factor is applied to the coordinates and arguments in drawing
nodes, thus alowing the construction of the image above them to be expressed
in the virtual design coordinates.
Deferred scaling factor applies immediately only to the inherited
clipping coordinates, where reverse scaling of environmental coordinate 
information allows to implement physical clipping of images expressed in virtual
coordinates. Clipping in virtual coordinates is achieved through
positioning deferred scaling node above the clipping nodes.
$b1 $i0 iteration $t5 factor which must be greater then 0 for the interpreter
to follow the vertical exit edge from the node.
$b1 $i0 fontbase $t5 pointer indicates the base of the current font to be
used in all the subordinate string drawing operations.
$b1 $i0 argument array $t5 points to a one-dimensional array of shortwords
which can be used as arguments in the subordinate graph.
Entering the same subgraph with different array of arguments, is similar
to the passing of arguments to a drawing procedure.
Such subgraph should contain appropriate index flags set
for the nodes to which such arguments are
to be passed and appropriate array indexing information in its argument fields.
$b1 $i0 cursor $t5 points to a graph
currently responsible for drawing of cursors. Nodes of such graph
will be usually designed to pick up arguments from the environment
which invoked the graph.
$a indent=0
$b2
12: |                   right pointer MS half                       |
    +---------------------------------------------------------------+ if Rgt=1
14: |                   right pointer LS half                       |
    +===============================================================+
$b2
$16
Byte 0 of half-word 0 contains the instruction code.
$b1
Byte 1 contains flags, part of which parameterize the execution of
the instruction or of its subordinate subgraph.
$b0
Flags (Optimise,Wait,Pointer,IndexA,IndexB,Cursor,Down,Right) correspond to
 bits 
$14(<7:0>) of the byte.
$b1
$a indent=3
$i0 Optimise $t3 flag invokes optimised evaluation of the subordinate graph,
where the interpreter will follow only those vertical edges, where
the bounding box of the image is expected to intersect with the current 
clipping box.
Such evaluation, although fairly simple to maintain at the top level nodes
e.g. with multiwindow textual displays becomes more complicated for
more sophisticated structures and may require significant monitoring of
differential changes in the graph.
$b1
$i0 Wait $t3 when 1 forces the interpreter to execute a partial completion
sequence and halt immediately after executing the return phase of the node.
$b1
$i0 Pointer $t3 flag when 0 indicates that arguments are stored immediately
in the instruction starting with halfwords 2 and 3.
For Pointer=1 halfwords 2 and 3 form a 32-bit argument pointer.
This interpretation applies to nodes requiring 1 or 2 arguments. For nodes
requiring argument lists Pointer=1 and half-words 2 and 3 point to the
head of the list.
$b1
$i0 IndexA $t3 flag when 0 indicates that argument A is directly accessible
immediately or through a pointer, depending on the Pointer flag.
IndexA=1 signals that the value obtained through such access
is the argument index in the current argument array 
(See the description of individual nodes for
the declaration of the current argument array). 
$b1
$i0 IndexB $t3 has the same function as IndexA but applies to argument B.
$b1
$i0 Cursor $t3 flag set to 1 results in temporary replacement of the
current argument array pointer with a pointer to the bounding box
coordinates of the node, followed by a call to the
current cursor drawing graph.
All this happens immediately after the execution of the return phase of the
node.
$b1
$i0 Down $t3 flag indicates that half-words 7 and 8 contain a valid pointer
to the first instruction of a chain in the subordinate subgraph.
For Down=0 the interpreter will execute return phase of the instruction
without entering the evaluation of the subordinate graph.
Down=1 will be ignored for the iteration index in the current environment
being 0.
$b1
$i0 Right $t3 indicates that half-words 9 and 10 contain a valid pointer
to the next of horizontally linked chain of instructions. 
Upon encountering Right=0
the interpreter will execute the "return" part of the instruction
which invoked the currently terminated chain. Right=0 encountered at
the level at which the evaluation was invoked will terminate the evaluation.
              
The flag can be used for temporary disabling of manipulated parts of the 
picture. When modelling execution of a command stream
the Right=0 marks the last instruction of the stream.
$a indent=0
$p1
Half-words 1 and 2 contain information about the arguments for the node,
subject to interpretation under flags Pointer and Index.
$p1
The node contains also the information about the bounding box of the
subordinate picture.
This information, depending on the invoked mode of evaluation can be:
$b1
$a indent=1
$i0 - $t1 updated by the evaluation process through the evaluation of the
subgraph
$b1
$i0 - $t1 used by the evaluation process during the optimised evaluation
where subordinate images with bounding boxes outside the clipping 
coordinates are not evaluated.
$a indent=0
$b1
Bounding box coordinates relative to the current working (X,Y) coordinates
of the interpreter are stored in half-words 3-6. Half-words (3,4) and
(5,6) contain (X,Y) coordinates of left-hand bottom and right-hand top
corners of the box.
$n 
$22(Nodes of the graphics data structure)
$b1
In the following descriptions arguments
of operation are shown in $32(italics) and represent values
obtained from half-words 1 and 2 through appropriate interpretation of
flags Pointer and Index.
$b2
$22(Non-drawing, environment modification nodes)
$b1
$22(FONT)($32[fontbase])
$b0
The subordinate graph will use the font starting at $32[fontbase].
$b1
$22(COLOUR)($32[colour])
$b0
$32[colour] becomes the colour for all the subordinate drawing operations.
$b1
$22(PLANES)($32[mask])
$b0
Planes indicated by 1's in $32[mask] will be enabled for writing in the
subordinate graph.
$b1
$22(RASTER)($32[rasterpointer])
$b0
In the subordinate graph the raster at $32[rasterpointer] will be used as a 
raster by all the area-filling operations. The initialisation raster is:
(16,1,16_FFFF) resulting in complete fill of the area.
$b1
$22(CURSOR)($32[cursorpointer])
$b0
$32(cursorpointer) points the top node of the cursor drawing structure
for the subordinate nodes.
$b1
$22(ARGUMENT)($32[arraypointer])
$b0
$32(arraypointer) points to the first element of the argument array
for the subordinate nodes
$b1
$22(CLIP)($32[sizeX,sizeY])
$b0
Clipping in a rectangle of size ($32[sizeX,sizeY]), starting from the
current position. As an environmental attribute subject to retrospective
inverse scaling by the deferred scaling node.
$b1
$22(MOVE)($32[modX,modY])
$b0
Current X and Y coordinates are modified by $32[modX] and $32[modY] 
respectively. $32(modX,modY) may have to be prescaled by the current
immediate scaling factors.
$b1
$22(ISCALE)($32[factorX,factorY])
$b0
Cummulative immediate scaling of subordinate picture. Implies only 
immediate scaling nodes can be encountered in all the vertical paths of the
graph which contain this node.
$b1
$22(DSCALE)($32[factorX,factorY])
$b0
Declaration of deferred scaling. Excludes presence of any other scaling
nodes in any of the vertical paths containing this node.
$b1
$22(SETITERATION)($32[iteration])
$b0
Declares iteration index $32[iteration] for the subordinate picture.
During execution flag "Down" is ignored if iteration index in the
environment is 0.
$b1
$22(DECITERATION)
$b0
Decrements iteration index in the environment.
$b2
$22(Drawing nodes)
$p1
Drawing nodes are responsible for the final drawing operations.
Each node starting at given coordinates modifies these coordinates
to the oposite end of the diagonal of the bounding box of the
created picture. In most applications such instruction will be used
to represent a leaf node (flag Down=0) and
the evaluation will subsequently move to the next horizontally linked node or
to the return phase of the node above.
$b1
$22(BOX)($32[Xsize,Ysize])
$b0
Fills with current colour a box of size ($32[Xsize,Ysize]), starting at current 
evaluation coordinates. Evaluation coordinates for X and Y are modified
by $32[Xsize] and $32[Ysize] respectively.
($32[Xsize,Ysize]) are subject to scaling by the cummulated immediate or by
the deferred scaling factors.
$b1
$22(POLYGON)($32[argumentlist])
$b0
Fills with current colour a polygon starting at current evaluation
coordinates and outlined by consecutive relative movements specified in
in $32[argumentlist].
$b1
$22(LINE)($32[Xsize,Ysize])
$b0
Draws a straigh line from the current evaluation coordinates to a point
distant by ($32[Xsize,Ysize]).
$b1
$22(LINES)($32[argumentlist])
$b1
$22(TEMPLATE)($32[template])
$b0
A pattern defined by the template is filled with current colour at the
current evaluation coordinates. 
$b1
$22(PIXELMAP)($32[pixelmap])
$b1
$22(ASCII)($32[ASCIIpointer])
$b0
Draws in current colour and with current font a string of ASCII characters.
Interpretation continues up to a character defined as a terminator by
the selected font.
$b2
$22(Control nodes)
$b1
$22(FLYBACKY)
$b0
Withholds execution of the following instruction till the beginning of the
nearest framestore vertical flyback. Most of the following instructions 
require such synchronization.
$b1
$22(COLOURMAP)($32[colourmappointer])
$b0
Consecutive locations of the framestore colourmap are loaded with the
consecutive store values starting at $32(colourmappointer). 
8-bit intensities for  red, green and blue
are represented by bits $14[<7:0>], $14[<15:8>] and $14[<23:16>] of 
consecutive 32-bit words.
$b1
$22(SETXY)($32[Xoffset,Yoffset])
$b0
Explicitly sets $22(X) and $22(Y) evaluation coordinates.
Intended for support of dual-buffering scheme with two such nodes
used alternately as entry points to the structure.
$b1
$22(PAN)($32[Xoffset,Yoffset])
$b0
Left-hand bottom corner of the display will is placed at 
(($32(Xoffset)/16)*16,$12(Yoffset)) in the framestore. Can be used with
$22(SETXY) and $22(FLYBACKY) to implement dual-buffering.
$b1
$22(DEPOSITENV)($32[environmentpointer])
$b0
This node deposits at the location indicated by the [environmentpointer]
the contents of its current working environment.
$b1
$22(PICKUPENV)($32[environmentpointer])
$b0
Partial evaluation of the structure starting from a chosen node
may be invoked through setting up the working environment to that of
the current environment of the node from the previous full evaluation.
$32[environmentpointer] will be usually the same as in $22(DEPOSITENV)
node which should preceed the chosen entry node in the structure.
In dual-buffering scheme additional $22(MOVE) node may have to be
inserted into the evaluated substructure.
Such optimised evaluation can be invoked when activities are
concentrated within the topmost windows.
$b1
$22(CALLMICRO)($32[microaddress])
$b0
Sections of new microcode can be invoked,
through a call to a chosen microcode location. This would usually
refer to additional, loadable microcode memory.
In case of partial replacement (e.g. when trying out new instructions)
proper care should be taken of the consistency of the stacks (main
and microinstruction one).
$b1
$22(CLEAR)
$b0
Resets the evaluation stack pointer. Should be invoked after abnormal
completion.
$b1
$22(REPORT)($12[reportpointer])
$b0
Will deposit value 00FF at the location $32[reportpointer].
$n
$22(Interaction between the user processor and the interpreter)
$12
$p1
After initialisation, as well as after each completed evaluation the graphics
processor-interpreter puts itself into a wait state. 
$b1
The process requiring the evaluation should set up all the necessary
startup environment including the required action on completion 
(e.g. $22[REPORT] node) and then wake up the graphics processor through
a write into location E04000.
$b1
The processor picks up from the environment its starting execution pointer
and performs depth-first scan of the structure. It will halt upon completion,
upon encountering flag Wait=1 or upon invalid opcode.
$b2
$22(Startup environment)
$p1
The location of the local graphics processor memory in the address space
of the APM is set up to E0E000.
$b1
$a indent=9
$22($i0 address $t3 attribute $t9 description)
$b1
$i0 E0E000 $t3 Execution pointer $t9 Prior to evaluation should be loaded
with a pointer to the required entry node (or to the first command in stream
execution). During evaluation it contains the current execution pointer.
$b1
$i0 E0E004 $t3 Execution flags $t9
$b1
$i0 E0E006 $t3 Current colour $t9 Contains current colour.
$b1
$i0 E0E008 $t3 Current planes $t9 16-bit mask with 1's indicating planes
with enabled write operation
$b1
$i0 E0E00A $t3 Current X $t9 Current working X coordinate
$b1
$i0 E0E00C $t3 Current Y $t9 Current working Y coordinate
$b1
$i0 E0E00E $t3 Bounding box $t9 left X coordinate
$b0
$i0 E0E010 $t9 bottom Y coordinate
$b0
$i0 E0E012 $t9 right X coordinate
$b0
$i0 E0E014 $t9 top Y coordinate
$b1
$i0 E0E016 $t3 Clipping box $t9 left X coordinate
$b0
$i0 E0E018 $t9 bottom Y coordinate
$b0
$i0 E0E01A $t9 right X coordinate
$b0
$i0 E0E01C $t9 top Y coordinate
$b1
$i0 E0E01E $t3 immediate scaling $t9 X scaling factor
$b0
$i0 E0E020 $t9 Y scaling factor
$b1
$i0 E0E022 $t3 deferred scaling $t9 X scaling factor
$b0
$i0 E0E024 $t9 Y scaling factor
$b1
$i0 E0E026 $t3 Iteration index $t9 Iteration index can be explicitly set
or it can be decremented. When 0 it inhibits evaluation of the subgraph of
the node.
$b1
$i0 E0E028 $t3 current font $t9 Current font pointer contains the address
of the base of the current font definition.
$b1
$i0 E0E02C $t3 Argument array $t9 It is a pointer to the base of the current
argument array.
$b1
$i0 E0E030 $t3 Cursor $t9 Cursor pointer addresses a graph currently used
for drawing cursors. Such graph will usually contain indexed argument
references in the array defining the bounding box of the image.
$a indent=0
$n
$22[Examples of application]
$b1
$22[Instruction codes]
$e