## Computer Science 237 |

**Lab 5: Red-Blue Hackenbush****Due: Monday, October 16, 2006 at 9:00 AM**

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.

Hackenbush, at start of play

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

you will find the support code you need. To untar this, type:
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

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:

- 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.
- The
`int`on the palm is a word. Use the`ext.l`instruction if you need to sign extend a word to a longword. - The
`mulu`operation takes two words and produces a longword. - 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. - 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. - 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.
- 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:

- Every segment must be directly or indirectly attached to either the sky or the ground.
- 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.
- 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*.