The Magic Internals Primer

Introduction
Configure/Compile/Install
Execution
Database
Commands and Command-Line Parsing
Files and File I/O
Undo/Redo Mechanism
Graphics
Technology
Extraction
"Background" DRC
CIF and GDS output
Miscellaneous

Introduction

Configure/Compile/Install

File structure
Scripts that help with the compile and install process are all in the "scripts" subdirectory. This includes:

scripts/config:
The original interactive configuration script.
scripts/configure.in:
Source for GNU "autoconf".
scripts/defs.mak.in:
Source for "defs.mak" when generated by GNU autoconf.
GNU autoconf
The "make" process used to be done with "make config", with "config" being a script in the "scripts" directory. This is no longer officially supported. Now, GNU autoconf is used. Note that GNU "automake" is NOT used, and "autoconf" is used in an unconventional manner. The original "make config" would generate a file "defs.mak" from scratch, as defined by lots of "cat - << CAT_EOF" statements.
Note that "configure" in the main directory is a separate script which forces the command "cd scripts" followed by "./configure" that allows GNU configure to be run from the top level without requiring "cd scripts; ./configure; cd ..; make". This is a useful convenience, and avoids the necessity of having all the GNU autoconf support routines (missing, install-sh, config.guess, etc.) sitting in the main directory.
The "unconventional" part is defined by AC_OUTPUT(defs.mak) in "configure.in". This forces the output created by the "configure" script to be dropped into file "defs.mak" according to the format of the file "defs.mak.in" (instead of the usual Makefile created from Makefile.in). This allows the retention of the original format in magic of a fixed "Makefile" that includes the "defs.mak" file for specific compile-time information. It allows both the GNU autoconf and the original "make config" methods to co-exist with a minimal amount of pain.
Compile-time options
Tcl/Tk version
Machine-dependent stuff
Most machine-dependent definitions are in misc/magic.h. Checks on size of types was added for compatibility with 64-bit architectures (originally, Alpha; now, AMD Opteron and Intel Itanium).
The main porting issue with 64-bit architectures is the ubiquitous use of type "ClientData" (generic pointer) to pass untyped data to general-purpose callback functions (see section 4. Database). Usually structures are passed through ClientData, but occasionally it is used to carry a single value. To deal with this, all such references are recast as "pointertype" (defined in misc/ magic.h), an integer type having the same number of bits as a pointer for the given hardware architecture.
Endian type (big-endian, little-endian) is ONLY used by the "utils/doubleint.c" routines, and probably predates the universal acceptance of C type "long long". It should be replaced.
Compiling
Installing

Execution

File structure
The top-level source is "magic/magicTop.c". This ONLY contains the main() routine definition. When compiled with Tcl/Tk, it is not used at all. It calls the internal routine magicMain().
All of the essential startup routines are in main/main.c. This includes the shell procedure magicMain(), which calls, in turn, the four major startup functions:
mainInitBeforeArgs():
This function initializes the input methods and determines what graphics displays are available.
mainDoArgs():
Processes command-line arguments and sets variables accordingly.
mainInitAfterArgs():
In order:
1. sets up the search paths
2. sets up the graphics display and methods
3. reads in the technology file, and
4. calls all remaining initialization routines.
mainInitFinal():
In order:
1. reads in the system startup file
2. reads in the user's startup file
3. read in a .mag file if specified on the command line, and
4. make the cursor box.
and the shutdown function,

mainFinished():
Calls MainExit(), which closes the graphics display and resets the terminal to its original state.
The distribution system startup file is "magic/proto.magic.m4" and is processed by the "m4" preprocessor (yuck.) to modify system startup based on choices made at compile-time.
Startup
The Tcl/Tk version startup is significantly different from the non-Tcl/Tk version startup. With Tcl/Tk, the "magic" executable is actually a shell script, found in "tcltk/magic.sh.in" (this is preprocessed by "m4" to replace variable names with compiled-in path names). Even with the Tcl/Tk version, there are two completely different methods of startup, "terminal startup" and "console startup". "Terminal startup" attempts to mimic, to the extent possible, the original terminal-based input method magic used prior to version 7.2. However, there is effectively NO WAY to emulate the character-based input in the terminal from the line-based Tcl interpreter. The kludgy method is to redirect keystrokes into the xterm terminal with the X11 "XSendEvent" procedure. But, the xterm must be explicitly set by the user to "accept send events" (in an xterm, use Control-Button 1 to get the popup "Main Options" window, and select "Allow SendEvents"). In a further kludge, to get Tcl to drop back into the terminal after processing the magic startup Tcl script, it is necessary to treat the script as a ".wishrc" file, requiring the environment variable $HOME to be set to the magic install destination directory, and the "magic.tcl" script to be symbolically linked from the name ".wishrc".
The cleaner startup method is to use the "tkcon" Tcl/Tk console window. In this case, the "magic" shell script runs "tkcon.tcl" and passes it an initial set of commands that 1) force it to read the Tk package into the slave interpreter, 2) copy the shell command-line arguments to Tcl arguments, and 3) source the "magic.tcl" script. In this arrangement, there are two interpreters in a master/slave arrangement, with the tkcon console being the master interpreter, and magic being the slave interpreter. Commands which affect the console directly, such as moving the cursor around or redirecting keystrokes into the console window, must be sent to the console interpreter, while magic commands or any commands affecting the magic window must be sent to the magic interpreter. Internally, these interpreters are accessed as global variables (type Tcl_Interp *) "consoleinterp" and "magicinterp", respectively.
The "magic.tcl" script loads magic as a shared-library object file (tclmagic.so) into the Tcl interpreter. Loading the file causes the "Tclmagic_init()" function to be automatically executed (see "tcltk/tclmagic.c"). The initialization routine does only a couple of things, which is to define, in the interpreter, commands "magic::initialize", "magic::startup", and "magic::tag", which will be invoked later in the script. This allows essentially all of the startup to be managed by the script and limiting the amount of startup code that must be compiled in.
The "magic.tcl" script goes on to call the "initialize" and "startup" functions. Note that these are split because it is necessary to do some command-line processing between the two routines. If the "wrapper" is specified on the command line, then the additional script "wrapper.tcl" is called between these two routines.
"magic::initialize" calls the routine _magic_intialize() defined in "tcltk/tclmagic.c". It is responsible for
1. calling mainInitBeforeArgs(), mainDoArgs(), and mainInitAfterArgs(), and
2. registering all of the magic commands as Tcl commands, so they are available from the Tcl command line.
"magic::startup" calls the routine _magic_startup() defined in "tcltk/tclmagic.c". It is responsible for:
1. calling mainInitFinal(), and
2. setting up the prompt and input method appropriately, depending on whether "terminal startup" or "console startup" has been selected.
The "magic.tcl" file, being a startup script, is read through, after which the Tcl interpreter sits and waits for command input.
Initial file reads
System ".magic" file: This defines all of the single-key macros used by magic. There are also some definitions for plot spooling, and loading some SCHEME definitions if the SCHEME interpreter is compiled in. Likewise, this would be the proper place to load Tcl procedures from script files.
User ".magic" file: This is read out of the current working directory, if it exists, and if not, it is read out of a user's home directory, if it exists there. It does NOT override the system ".magic" file. Since the system file only sets up the macros (which can be redefined), there is no point in allowing an override. This is most likely used when users have their own preferred key macros or extensions. In a specific directory, however, it can also be used to force the loading of a specific technology file, and commands "grid" and "snap" can be used to set an "effective lambda" for doing layout that is not the same as the magic internal units. It can also add specific directories to the search path for cells.
Search paths
Environment variables
Remote connections
Window manager interaction

Database

File structure (database.h)
CellDef and CellUse structures
Corner stitched tile structures
The best reference for the corner-stitched tile structure is the original whitepaper by John Ousterhout. However, in a nutshell, the quick reference can be found in comments at the top of the source file tiles/tile.h. Corner-stitching works in the following manner:
Each tile has the structure
```
	typedef struct tile
	{
	    ClientData   ti_body;       /* Body of tile */
	    struct tile *ti_lb;         /* Left bottom corner stitch */
	    struct tile *ti_bl;         /* Bottom left corner stitch */
	    struct tile *ti_tr;         /* Top right corner stitch */
	    struct tile *ti_rt;         /* Right top corner stitch */
	    Point        ti_ll;         /* Lower left coordinate */
	    ClientData   ti_client;     /* This space for hire.  Warning: the default
	                                 * value for this field, to which all users
	                                 * should return it when done, is MINFINITY
	                                 * instead of NULL.
	                                 */
	} Tile;
	
```
This structure is the fundamental data structure in magic. "ClientData" is a general-purpose pointer, usually to a specific pointer type. However, both ti_body and ti_client use this block of memory as an integer type. This is somewhat dangerous, as the size of a pointer is not necessarily equal to the size of an integer! Because of this, porting to 64-bit architectures such as the AMD Opteron required creating an integer type called "pointertype" equal in size to the size of a pointer. Any datum can be recast from ClientData to pointertype and vice versa without fear of losing information in the process.
In a normal layout tile, the ti_body variable is an integer value typedef'd as "TileType". When debugging magic, the name of the layer represented by TileType ttype can be seen using DBTypeLongNameTbl[ttype].
Tiles representing cell boundaries rather than physical layers use the ti_body variable as a pointer to a structure. The use of the corner-stitched format for cells, which really aren't corner-stitched at all, is at best something of a contrivance.

The corner-stitched representation, shown above, links each tile to four of its neighbors. The position of these neighbors is indicated in the figure. There may be more than one tile neighoring any side of tile "Tile". One enumerates all the tiles on one side by "walking" the side. This procedure is used throughout the magic source code. For instance, to "walk" the top side of tile "Tile" from right to left:
```
		Tile *bp;

		/* Enumerate all tiles along the top of "tile" */
		for (bp = RT(tile); RIGHT(bp) > LEFT(tile); bp = BL(bp))
		{
		    /* Do something here */
		}
	
```
Note the heavy use of macros. The essential macros operating on (Tile *)tile are:
- LEFT(tile)
- RIGHT(tile)
- TOP(tile)
- BOTTOM(tile)
- BL(tile)
- LB(tile)
- TR(tile)
- RT(tile)
The top four functions return a position in magic internal coordinates; the last four return a pointer to the appropriate neighboring tile. Use of these macros is always preferred over the equivalent direct reference to the Tile structure, both because the meaning is clearer, and because the macros themselves could change in the future depending on the implementation (see the "Developer's Note", below).
Thus, the "tile enumeration" function defined above first finds RT(tile), the rightmost tile connecting to the top of "tile", and then works leftward by finding BL() of the result. Each tile enumerated must attach to the top of "tile" as long as the x-coordinate of the right side of the enumerated tile is larger than the x-coordinate of the left side of "tile".
In summary, one "walks" the four sides of a tile in the following manner:
```
	for (bp = RT(tile); RIGHT(bp) > LEFT(tile); bp = BL(bp)) {} /* top */
	for (bp = TR(tile); TOP(bp) > BOTTOM(tile); bp = LB(bp)) {} /* right */
	for (bp = LB(tile); LEFT(bp) < RIGHT(tile); bp = TR(bp)) {} /* bottom */
	for (bp = BL(tile); BOTTOM(bp) < TOP(tile); bp = RT(bp)) {} /* left */
	
```
Developers' Note: It has been noted that for 64-bit architectures, the only variable to remain constant in size is ti_ll; all of the others take twice the memory of the equivalent 32-bit version. Thus, memory for layout is consumed nearly twice as fast on a 64-bit architecture for the same layout. The only reasonable way to get rid of this overhead problem requires a complete overhaul of the magic source. The proper method entails not referring to tiles by pointer. Instead, each plane structure should maintain a list of all the tiles in that plane. Each tile structure would then reference the four corner stitches by index into that list. Since some cells (like via structures arrayed for GDS output) contain very few tiles, it makes sense for the plane structure to declare the number of bytes required to hold the list. CellDefs with fewer than 256 tiles would then require only one byte for the index. When the number of tiles exceeded 256, the tile structures would be reallocated to 2 bytes per index. This method would reduce the amount of memory required for virtually all layouts, even on 32-bit systems, and would eliminate the memory hit for 64-bit systems. What are the drawbacks? One cannot determine anything about a tile without having a reference to the plane structure holding the tile. Most of the search procedures in magic make callbacks that give the tile as the first argument, with no plane information available. The good news is that in many cases, the stacked tile structures of magic version 7.3 already require knowing the plane, and so some of the routines have already been modified as needed for this method. The other drawback is a performance hit, as the Tile pointers are a direct reference, while the Tile indices would be an indirect reference. Theoretically, a good compiler should be able to turn the indirect reference into a single operation, but it is not known how well that works in practice. Finally, the handling of tiles is complicated by the requirement of having a "tile manager" function. The "tile manager" would operate much like internal system memory management routines. Just like "malloc", with a bit of sophistication, tile merging and splitting can be done with a low performance overhead.
Planes
All geometry in magic is split into partially-independent planes. In general, these planes correspond roughly to the mask layers from which an integrated circuit is built. Typically, one defines a new plane for each set of layer types that are largely non-interacting with other types. This works especially well for metal routing layers, since the metal layers are completely non-interacting (excluding capacitance extraction, which is separate from the database representation), and only interact where cuts (vias) are defined. This works much less well for layers close to the original wafer surface. Polysilicon, diffusion regions, and wells are all heavily interacting, and therefore tend to work best when they are defined all on a single plane.
Of course, it would be possible to define everything in the layout on a single plane. But, anywhere that types overlap in the same plane, the corner-stitched tile structure gets broken up into pieces. For example, if type1 overlaps type2 in a single plane, magic requires separate types type1, type2, and an additional type type1-plus-type2, and the corner-stitched structures will be subdivided until each tile can be represented by one of these three types. This is highly effective in some cases, such as when type1 is n-diffusion, type2 is polysilicon, and thus type1-plus-type2 works out "naturally" to be layer type n-transistor. Using multiple planes prevents the necessity of defining meaningless (and exponentially increasing) combinations of layers like "metal1-plus-metal2" or "metal1-plus-ndiffusion-plus-poly".
The plane structure is what holds a corner-stitched tile representation. In fact, this is all that it does. The structure looks like:
```
	typedef struct
	{
	    Tile        *pl_left;       /* Left pseudo-tile */
	    Tile        *pl_top;        /* Top pseudo-tile */
	    Tile        *pl_right;      /* Right pseudo-tile */
	    Tile        *pl_bottom;     /* Bottom pseudo-tile */
	    Tile        *pl_hint;       /* Pointer to a "hint" at which to
	                                 * begin searching.
	                                 */
	} Plane;
	
```
Note that the plane structure consists entirely of tile pointers. These are "special" tiles that define the boundary of the layout. Their lower-left coordinates as defined by ti_ll equal "INFINITY" or "MINFINITY" which, unlike the name suggests, are actually just Very Large Numbers, close to (but, significantly, not equal to) the maximum and minimum integers represented by a 32-bit number (architecture dependent). When new tiles, with physically realistic coordinates, get inserted into the plane structure, the leftmost, rightmost, topmost, and bottommost tiles get hooked to these predefined tiles. The "corner-stitched" representation does not actually require these boundary tiles, but they are convenient for allowing search routines to find all the tiles in a plane in a deterministic manner, sweeping in any direction.
The Tile pointer pl_hint is different from the others in that it is not allocated, and may point to any tile in the plane. It is sometimes useful to retain the last position searched in a plane, so that a routine may pick up from where it last left off, instead of having to find the position by searching inward from the plane boundary. The value of pl_hint may be NULL without causing any harm other than a performance hit for some functions.
Tile Types and Bitmasks
Magic uses bitmasks ubiquitously, and the most common use is to represent multiple tile types. The maximum number of types allowed is TT_MAXTYPES defined in database/database.h, and the default number is 256. Magic often needs to handle multiple types. For instance, to see what other tiles are electrically connected to a tile of type "metal2", magic needs to search for tiles of type "metal2", "via", and "via2", all of which represent an electrical contact to type "metal2". To simplify the representation of multiple layers, each layer has a unique bitmask that is (effectively) the number 1 left-shifted by the tile type number. That is, if "metal1" is type number 34, then the bitmask for "metal1" is (1 << 34). Because this bitmask is unique, it can be OR'd with bitmasks of other tile types to represent any combination of types.
The obvious thing to note is that (1 << 34) overruns the space of a 32-bit integer type. In fact, with TT_MAXTYPES being 256, it should be obvious that no single data type can represent the bitmask of all possible tile types. So, magic defines the bitmask as an array of integers of known size. If an integer is 32 bits, then 8 of them are needed to represent all tile types. So, the type "TileTypeBitMask" is defined as follows:
```
	typedef struct
	{ 
	    unsigned int tt_words[TT_MASKWORDS];
	} TileTypeBitMask;
	
```
where TT_MASKWORDS is derived from the value TT_MAXTYPES and is equal to 8 for TT_MAXTYPES=256 in a 32-bit architecture.
Dealing with array types in plain C is cumbersome, and so tile type bit masks are ALWAYS handled by macros. Given a pointer bmask to a TileTypeBitMask structure, and a TileType ttype, the useful macro operators are:
- TTMaskZero(bmask) /* Clear all types */
- TTMaskCom(bmask) /* Invert a mask */
- TTMaskSetType(bmask, ttype) /* Add a tile type bit */
- TTMaskClearType(bmask, ttype) /* Remove a tile type bit */
- TTMaskSetOnlyType(bmask, ttype) /* Combination of 1 and 3 */
- TTMaskHasType(bmask, ttype) /* Query a tile type */
Given bmask and additional mask TileTypeBitMask * bmask2, some useful macro operators are:
- TTMaskEqual(bmask, bmask2) /* Query equality */
- TTMaskSetMask(bmask, bmask2) /* OR the two masks */
- TTMaskAndMask(bmask, bmask2) /* AND the two masks */
There are other operators, including operations on three masks. These are defined in database/database.h along with the more common ones listed above.
Note that the file database/database.h is derived from the file database/database.h.in at compile time. This allows all the macro operators to be generated in accordance with the value of TT_MAXTYPES. It is important to know that if TT_MAXTYPES is changed, then the source should be recompiled from scratch (make clean ; make).
Other data structures (geometry)
A number of structures apart from the basic cell, plane, and tile definitions, are used frequently throughout the magic source. Most of these have to do with geometry and can be found in utils/geometry.h.
Point
A point in 2-dimensional integer space. Reference coordinates p_x and p_y.
Rect
A rectangular area, specified by lower-left and upper-right points. Reference Point structures r_ll and r_ur for the lower left-hand corner and upper right-hand corner, respectively. Note that while the four coordinates of a rectangle are, as defined, r_ll.p_x, r_ll.p_y, r_ur.p_x, and r_ur.p_y, the magic source code almost always refers to these points by macro shorthand, which is, respectively, r_xbot, r_ybot, r_xtop, and r_ytop. This can be perpetually confusing when debugging source code.
Transform
A simplified transformation matrix. The well-known two-dimensional geometric transformation performs any linear coordinate tranformation by extending the two-dimensional vector with an extra "1", multiplying by a 3-by-3 matrix, and taking the first two values of the result as the new X and Y coordinates. In this simple form, only 6 numbers in the 3-by-3 matrix are significant, the others being always 1 or 0, so magic defines its tranformation matrix as an array of these six significant values. There are further restrictions placed on these numbers by the fact that the only rotations allowed in magic are rotations by 90, 180, and 270 degrees; together with "flipping", there are only eight orientations represented by these matrices. These eight special orientations have their own fixed (statically allocated) values, the global variables (extern Tranform):
- GeoIdentityTransform
- GeoUpsideDownTransform
- GeoSidewaysTransform
- Geo90Transform
- Geo180Transform
- Geo270Transform
- GeoRef45Transform
- GeoRef135Transform
A common function is to transform a Tile structure into the equivalent rectangle. This function is:
```
	    Tile *tile;
	    Rect r;
	    TiToRect(tile, &r)
	
```
Another common function is to translate the coordinates of a Rect in a subcell into the coordinate system of the top-level cell. This is always done in routines that are passed a SearchContext structure, which contains the aggregate transform from the current cell back to the top level. So the coordinate transformation to turn Rect r1 in local coordinates into Rect r2 in top-level coordinates is:
```
	    SearchContext *scx;
	    Rect r1, r2;
	    GeoTransRect(&scx->scx_trans, &r1, &r2);
	
```
Search routines and callbacks
Selection mechanism