Archive for Mai 2011

I am

Mai 15, 2011

I am Jack’s Raging Bile Duct.
I am Jack’s Cold Sweat.
I Am Jack’s Complete Lack of Surprise.
I Am Jack’s Smirking Revenge.
I Am Jack’s Broken Heart.


Mai 3, 2011

QuickDraw is the graphics library which was used to create the user interface of the early Apple Macintosh computer. It was written by Bill Atkinson who is also known for creating MacPaint and Hypercard. Quickdraw is mainly assembler code for the Motorola 68000 Microprocessor. The MC68000 and its successors are CISC (Complex Instruction Set Computer) machines. The processor instructions are realized with microcode which runs on the processor.

Quickdraw computes the graphics primitives like lines, rectangles, ovals and circles using fast integer computations. The early 68k processors had no floating point arithmetics. The QuickDraw code contains some fairly complex algorithms as well as simple ones. To give you an idea of the nature of this code, let’s start with a simple function.

The function EmptyRect takes a rectangle and decides if the area of the rectangle is zero. If so then the rectangle is empty. The area could be computed by multiplying the width and height of the rectangle and then checking if it is zero. However, there is an easier way to decide this. The result is zero if either the width or the height is zero (or both).

The rectangle is a data structure with the given form (top,left,bottom,right), which could be read as (y0,x0,y1,x1). Usually, the following is true: top < bottom, left < right, or y0 < y1, x0 < x1.

Here is the function:

        .FUNC EmptyRect,1
;  FUNCTION  EmptyRect(r: Rect): BOOLEAN;
;  CLOBBERS D0,D1,A0,A1.
        MOVE.L  (SP)+,A1                        ;POP RETURN ADDR
        MOVE.L  (SP)+,A0                        ;POP ADDR OF RECT
        MOVE    (A0)+,D0                        ;GET TOP
        MOVE    (A0)+,D1                        ;GET LEFT
        CMP     (A0)+,D0                        ;IS TOP >= BOTTOM ?
        BGE.S   EMPTY                           ;YES, RETURN TRUE
        CMP     (A0)+,D1                        ;IS LEFT >= RIGHT ?
        BGE.S   EMPTY                           ;YES, RETURN TRUE
        CLR.B   (SP)                            ;NOT EMPTY, RETURN FALSE
        BRA.S   DONE                            ;AND QUIT
EMPTY   MOVE.B  #1,(SP)                         ;RETURN TRUE
DONE    JMP     (A1)                            ;RETURN

The first line says this is a function called EmptyRect which takes one parameter.

The parameters of the function are all on the stack. The stack pointer SP points to the current top of the stack. The first thing we do is we pop the paramters from the stack into the address and data registers.

First we pop the return adress, which is the adress where the code is executed after the function returns. We save the return adress in the address register A1. Next, we pop the address of the rectangle from the stack into the address register A0. This is the address where the rectangle structure in memory starts. We want to get the top,left,right,bottom values of the rectangle. We take the address of the rectangle and treat the rectangle itself like a stack. First we pop the top value in the data register D0. Data registers contain values which can be used to compute other values in the ALU of the 68000. We pop the left value in the data register D1.

We need it later. In the next line we compare the value of top and bottom. Remember, we want to know if the height a of the rectangle is zero. We decide that the rectangle is empty if TOP >= BOTTOM. If top was actually larger than bottom then the height (bottom – top) would be negative. We assume that if the height (or width) is negative (or zero), then the rectangle is empty.

If (TOP >= BOTTOM) then we jump to the the EMPTY mark. The rectangle is empty so we must return true. We set the current stack pointer SP to the value 1 (which means true). In the next instruction (DONE) we jump to the return address, which we saved in A1 in the first instruction.

If (TOP >= BOTTOM) is not true then (top < bottom) must be true, which means that the rectangle might not be empty. We do not take the jump but instead the following instruction is executed. We compare left and right.

If (LEFT >= RIGHT) then the rect must be empty and we jump to the EMPTY mark. We load 1 in the current stack pointer and jump to the return address. If left < right then we know that the rectangle is not empty (remember: top < bottom). We clear the byte at the current stack pointer. This sets the byte to 0. Then we jump to DONE. The 0 means we return false, because the rect was not empty.

As you can see this function has only 12 instructions. We only need 12 instructions to decide if a given rectangle is empty. There are 3 possible branches in the program.

EmptyRect is one of the shortest and simplest functions in the QuickDraw source code (However, there are much more complex ones). It’s an interesting example to get an impression of the guts of QuickDraw.