In particular, for the required portion of the project, you will write an assembly language program that
generates a tree-recursive process for drawing a Sierpinski carpet on the bitmap display tool that is available within MARS.
An example Sierpinski carpet is shown below. Once you have replicated this image, you can
earn extra credit by exploring other fractals of your own choosing.
You are not required to submit a lab write up; instead, just email me your assembly language programs (one per fractal you choose to do). For any fractals other than the Sierpinski carpet, you might also want to include screen captures of the result. However, that isn't essential. You should be sure that your programs follow the conventions for such matters as which registers are used for arguments and which registers each procedure needs to leave as it found them. Use a comment block at the top of each procedure to describe how it would be used. Use other comments only when necessary to explain the higher-level purpose of a code block, as opposed to directly echoing the assembly language instructions.
The following is a Python version of the program you need to write.
Its main procedure contains the call
carpet(0, 0, 243, 4). Your main program in the MIPS assembly
language version should contain that procedure
call and then use syscall number 10 to exit. You will also translate the
carpet procedure itself into assembly language.
def main():
carpet(0, 0, 243, 4)
def carpet(x0, y0, size, level):
'''Draw a carpet with upper left corner at (x0,y0).
The coordinate system has y increasing downward, not like usual math.
The size specifies both the width and the height.
If the level is 0, nothing should be drawn (leave background alone).'''
if level != 0:
newSize = size // 3
newLevel = level - 1
x1 = x0 + newSize
x2 = x1 + newSize
y1 = y0 + newSize
y2 = y1 + newSize
carpet(x0, y0, newSize, newLevel)
carpet(x0, y1, newSize, newLevel)
carpet(x0, y2, newSize, newLevel)
carpet(x1, y0, newSize, newLevel)
rectangle(x1, newSize, y1, newSize) # fill middle block solidly
carpet(x1, y2, newSize, newLevel)
carpet(x2, y0, newSize, newLevel)
carpet(x2, y1, newSize, newLevel)
carpet(x2, y2, newSize, newLevel)
# Everything above this line you should translate into MIPS assembly language.
# I have provided assembly code that is functionally equivalent to what follows.
def rectangle(x, width, y, height):
'''Fill a rectangle with upper left corner at (x,y) and specified sizes.'''
display.create_rectangle(x, y, x + width, y + height, fill='white')
display.update()
import cImage
display = cImage.ImageWin('Bitmap Display', 512, 256)
display.create_rectangle(0, 0, 512, 256, fill='black')
display.update()
main()
You can copy the assembly language version of the rectangle procedure
out of the example program rectangle.asm that I have linked to this
lab assignment. This example program has a demonstration main portion that simply draws a single rectangle and then exits.
The following list provides some suggestions for extra-credit variations. Feel free to pick any that suit you. Or fee free to come up with something of your own.
The Sierpinski carpet fills a solid square into the middle block of a 3 by 3 grid. What happens if instead of the middle block, you pick one of the other 8 blocks as the solid one? Or what happens if you fill in more than one of the 9 blocks?
Instead of dividing the carpet into a 3 by 3 grid, what happens if you divide it into a 2 by 2 grid, with 1 of the 4 blocks filled solid?
Rather than sticking with white on black, you could change the color scheme. For more coloring flexibility, you might want to modify the
rectangle procedure into a coloredSquare procedure. Unlike rectangle, it would take a single size argument
rather than separate width and height. That would free up one argument register to pass in a color, rather than the procedure always using white.
There are also fractals based not on filled rectangles, but on drawn lines. For example, the C curve and the dragon curve can each be viewed as a path from a starting point (x0, y0) to an ending point (x2, y2). At level 0, either of these curves is just a straight line from the starting point to the ending point. But at any higher level, they take a detour by way of an intermediate point (x1, y1) that is off to one side. Specifically, a level n C curve consists of a level n − 1 C curve from point 0 to point 1 and another level n − 1 C curve from point 1 to point 2. Likewise, a level n dragon curve consists of level n − 1 dragon curves from point 0 to point 1 and from point 2 to point 1. The coordinates of the detour point, point 1, can be calculated as follows:
x1 = (x0+x2+y0-y2)//2 y1 = (y0+y2+x2-x0)//2
In order to draw any of these line-based fractals, you'll need a line procedure to use in the base case, analogously to how carpet uses the rectangle procedure I provided. This will need to be your first step, and if you get it to work, you should definitely submit it for extra credit whether or not you wind up drawing fractals using it. You can use Bresenham's line-drawing algorithm.