The “Atkinson” circle algorithm

After the groundwork done for rectangle drawing, the rest of geometric shapes were pretty easy to add. To make sure the results of drawing operations would look exactly like on a real Mac, the Midpoint circle algorithm was implemented as closely to what Atkinson used as possible

https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

More information about the Midpoint (“Atkinson”) circle algorithm

The fun thing is, that a bunch of QuickDraw primitives actually share this method, so not only did this allow drawing Circles, it also enabled drawing ovals (basically stretched circles, thus this is why overly long framed ovals on Mac tend to have holes on their silhouette), and the infamous round rectangles. Also drawing arcs benefits from this, but we won’t be needing them at least for some time so we won’t touch them at this point.

Here’s also a neat video of round rectangle clipping:

What are regions exactly?

Short answer: The most important part which made Mac user interface possible.

Long answer: The regions, in the form as they are used in the original Mac, were invented by Bill Atkinson as solution to solving the problem of creating effective algorithms for masking drawing commands with arbitrary bitmap shapes, and performing geometric logical operations with them. There is a good article on macGUI, which gives a better backstory and technical explanation about what regions are from the user’s (or programmer’s) point of view:

http://basalgangster.macgui.com/RetroMacComputing/The_Long_View/Entries/2010/8/29_Regions.html

Regions in the QuickDraw

One interesting feature of regions is, that when a region is rectangular, it will always have fixed size (10 bytes), and its bounding box can be used as in rectangular clipping. This helps reducing sometimes drawing in complex regions to trivial rectangular blitting operations, which are much faster than ones requiring region masking for each scanline:

However, the need for actual region operations comes up very quickly, when wanting to do anything that ends up being non-rectangular. For example, the test case we used at this point, was just to get union of two rectangles into region, and fill that with a solid pattern.

Region decompression and re-compression

In memory, regions are stored in sort of compressed format, with each scanline containing horizontal indices of the inversion points on that scanline. However, during operations, they need to be manipulated as points, with horizontal and vertical coordinate. To achieve this, the region is decompressed during the actual operations into a point buffer, where points from both source regions are added as needed by the actual operation. The resulting points from these operations are then sorted, and re-compressed into a new region. At this point, we do the sorting with slow bubble sort, which will be replaced by a more efficient Quicksort later.

Funny thing about InsetRgn is, that it takes a bit more complex way of performing the operation: For insetting, the region is actually getting inset twice, once for both axis, but the horizontal and vertical coordinates are flipped for the second inset, so the horizontal inset is actually ran *twice*.

Drawing the regions

After the complexity of geometric operations on regions, doing the actual drawing with them is pretty straightforward. The region image blitter is pretty similar to the rectangular blitter, but it takes up to three regions as arguments, which get expanded into horizontal scanline buffers during the drawing. Each of these buffers is updated on each vertical coordinate, and together they form a bitmask, which can be simply ANDed together and used to mask the transfer of source bits to the destination.

After a few missteps, we finally got the region clipping to work nicely:

Now that work on Memory Manager and Resource Managers has started, it’s time to focus on the next important part of Mac: The graphical user experience.

A5 World and InitGraf

As all QuickDraw operations depend on existence of QuickDraw globals, and they are addressed with the A5 register in an application’s “A5 world”, we needed to have a way to simulate this at boot time. It appears that real Macs use part of the boot-time stack space for temporary A5 world, so we decided to follow this path. At this point in boot process, we don’t have a 68K needing a stack, but we decided to simulate this anyway. At this point, system zone resides near the beginning of RAM (after low memory globals and trap tables), and the stack pointer is located somewhere just below the screen memory, a perfect place to stick QD globals and a mini A5 world into.

The InitGraf was pretty simple, and also OpenPort following it. With necessary QD globals set up, and a full-screen GrafPort available, next step was of course to fill the screen with the familiar gray pattern. It’s funny, how just filling a rectangle has a lot of dependencies to other quickdraw APIs, such as regions, and a common blitter routine which will be shared by a large number of future QuickDraw routines. For now, we just skipped the unused cases with “TODO” comments, and after a few days a hard work got this:

Move to SDL2

Until now, the testbed was running inside a Cocoa application, but the need for a platform-agnostic implementation was already putting pressure on adding an abstraction layer between the host and the emulated environment. At this point, we took this as a possibility to switch to SDL2, changing the test environment at the same to the SDL2 library but also at the same time adding the abstraction layer on top of it.

This was accomplished by adding “Platform” layer, which abstracts the creation of sound devices, graphics context and input handling into a set of calls which the Toolbox emulator uses. In future, this layer can be extended to support other platforms, so someday we can add again Cocoa layer to handle platform-specific stuff like, like seamless desktop integration.

At this point, we added page switching support to the VIA memory page handler, which is the “Classic Video” hardware abstraction layer to choose active video buffer. The above video demonstrates results of the page-switching test.

The “Fake” ROM

An interesting feature of the original Macintosh system is how the onboard ROM was able to contain majority of features of the operating system, reducing the unpatched code loaded from disk to a minimum. As we attempt to replicate system startup as closely as possible with our architecture, an interesting point came up: On real Mac, the boot process is kicked off by ROM doing a POST hardware check, initializing a bunch of stuff in the memory, and loading a stage 1 boot loader from the disk using the disk and file system drivers in ROM. As our goal is to actually use a virtual file system, we need to have a way to kick-start this filesystem. What we decided to do, is to actually simulate ROM resources, and add our native filesystem driver as a DRVR resource which will be loaded by the device manager, and which file manager will use to actually mount the virtualized disk.

Another benefit of the “Fake” ROM is, that it provides us with neat place to store the UPP records for our trap handlers. As trap dispatch tables contain only 32-bit pointers to the handlers, which for native calls only point to the UPP records, we could now install these dynamically into the “ROM” address space, with additional benefit that if any curious applications would snoop for the address of trap handlers, they would to be above ROMBase, like on a real Mac.

The “Fake” ROM format follows closely the one used by Apple, with the exception that we only use the ROM resources, and preallocate a certain size of image for the UPP records. Thanks to this, we were able to start implementation of first parts of Resource Manager support, starting with creation of ROZ (ROM resource zone), which is created inside system zone to hold the master pointers and resource map which are “mapped” to the ROM space using a very weird and clever hack like on real Mac

A fun fact: A Mac can have multiple types (24 vs 32 bits) of zones active at once – The ROM has resources formatted either to 24 or 32 bits, but as the ROM cannot be changed when the 32-bit mode is toggled on real Mac using the Memory control panel, the ROZ will always be in the format for which ROM resources were created for.

For now, we just use the “fake” ROM to hold fonts and cursors, adding more stuff there as needed.