Computer Science 237 Computer Organization Williams College Fall 2006

This week's task is to write an efficient assembly language function to draw a Bezier curve. If you have used drawing programs you probably have some familiarity with these curves. This week we will use them as part of the game Red-Blue Hackenbush, an invention of John Conway and others. The rules to Hackenbush are discussed at the end of this document.

    tar xvfz /usr/cs-local/share/cs237/labs/hack/hack.tar.gz

This will create a subdirectory, hack. You are to complete the construction of the assembly file bezier.s by adding the code to compute one coordinate of a point on a Bezier curve. Build your program by typing "make". The result is found in hack.prc. In the starter kit, the BezierPt subroutine returns zero, so nothing exciting will happen. A working version of Hackenbush is found in whack.prc.

All Bezier functions are described by the formula: a(1-t)^3+3b(1-t)^2t+3c(1-t)t^2+dt^3 where 0 <= t <= 1. Note that at time 0 (t=0), all of the terms disappear save the first, which evaluates to a. At time 1, only the last coefficient, d, remains. We can think of the curve as taking us from a to d over time. In fact, the curve leaves a heading toward b and arrives at d coming in from c. On the plane we can use two functions x(t) = a_x(1-t)^3+3b_x(1-t)^2t+3c_x(1-t)t^2+d_xt^3 y(t) = a_y(1-t)^3+3b_y(1-t)^2t+3c_y(1-t)t^2+d_yt^3 to compute the curve from a=(a_x,a_y), toward b, arriving at d from c. It is sometimes useful to know that the curve always resides in the interior of quadrilateral a-b-c-d.

The C function to perform this computation has the following prototype:

    int BezierPt(int a, int b, int c, int d, int st);

It is important to realize that the pixels on the display are nonnegative integers. Furthermore, the support for floating point computations is, effectively, nonexistent on the palm. For this reason, the st that is passed in is a scaled t value between 0 and 8 (inclusive). These represent times between 0 and 1 (0, (1)/(8), (2)/(8), ..., 1). Write a tight assembly implementation of BezierPt that accurately computes the Bezier function. You may find the following useful:

1. Everything is unsigned and no greater than 160. Because of the quadrilateral observation, we know that all the resulting values will be unsigned and small, as well. Intermediate values, however, could get large enough to exceed the capacity of a word, so you need to be able to identify when values are word or long. Be aware, however, you should not use division early in the computation to keep things small-you will lose accuracy.
2. The int on the palm is a word. Use the ext.l instruction if you need to sign extend a word to a longword.
3. The mulu operation takes two words and produces a longword.
4. The divu operation takes a longword and divides it by a word. The result is a longword that contains the quotient in the low 16 bits, and the remainder in the high 16 bits. The remainder is unimportant here. Better yet, if you're dividing by powers of 2, consider logical shifts instead.
5. If we compute everything in "scaled time" values, it useful to think of (1-t) as (8-st) and then factor out the 8 for removal at a later time. This means we can simply finish our computation by dividing by 512.
6. For this application, it is better to round values during a division rather than directly truncating them. This can be accomplished by adding half the divisor before the division. This will make straight lines straighter.
7. Think carefully about how you might make the computation run more quickly. If the computation is fast, it is easier to imagine using it in a tight loop that follows mouse movements.

When you are finished, submit your well-documented implementation of BezierPt in the file bezier.s.

While you will write only the BezierPt routine, you will use it in a program that plays the full red-blue hackenbush game. If you are having trouble getting started with the program (maybe can't even get to the point where BezierPt gets called), note that you must begin the drawing of a segment by clicking on the "sky" or the "ground". The four points that define the Bezier curve to be drawn are the points where you press down ("pen down" on the Palm) the first time, where you release ("pen up") the first time, where you press down the second time, and where you release the second time.

Here are the rules for game play:

1. Every segment must be directly or indirectly attached to either the sky or the ground.
2. The players remove their segments in turns. If the removal of a segment causes other segments to become detached from the sky or ground, they are removed as well.
3. The first player without a valid move loses.

The game is quite complex to analyze and appropriate play is often difficult to identify. In general, there is no simple technique, say, for a computer to approach playing a game of Hackenbush against an opponent. For more information on this topic one can read Winning Ways by Berlecamp, Conway, and Guy. Conway also addresses the evaluation of Hackenbush positions in his The Book of Numbers.