Nov 95 Challenge
- Jan 95 Challenge
- Feb 95 Challenge
- Mar 95 Challenge
- Apr 95 Challenge
- May 95 Challenge
- Jun 95 Challenge
- Jul 95 Challenge
- Aug 95 Challenge
- Sep 95 Challenge
- Oct 95 Challenge
- Dec 95 Challenge
Volume Number: 11
Issue Number: 11
Column Tag: Programmer’s Challenge
Programmer’s Challenge 
By Bob Boonstra, Westford, Massachusetts
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
Enclosing Bounds
The Challenge this month is based on a suggestion by Mike Scanlin, who remains a fan
of the column. (We’re still waiting for Mike’s first Challenge entry, however.) The
problem is to write a routine that will return a rectangle enclosing all non-white
pixels in a selected area of an image. This code might be useful in a drawing or
painting program, where the user would be allowed to select a subset of the image by
clicking and dragging, and the software would select all of the elements of the image
contained within that selection. The prototype of the code you will write is:
void EnclosingBounds(
PixMapHandle pm, /* handle to PixMap containing image */
Rect selection, /* subset of image to enclose */
Rect *enclosingRect /* enclosing rect return value */
);
Your code should examine all of the pixels within the selection rectangle of the
PixMap and return the smallest rectangle containing all of the non-white pixels.
Pixels outside the selection rectangle should be ignored. The bounds rectangle of the
PixMap will be no larger than 2048 pixels in each dimension, the baseAddr pointer
pixelSize values of 1, 8, or 32, with values of 8 and 32 being weighted most heavily
in measuring performance. For PixMaps with indexed pixels (cmpCount==1), the
color table will contain white as the first table entry (as all good color tables are
supposed to). For PixMaps with direct pixels, the unused (alpha) bits of each pixel
will be zero.
You may use either the Metrowerks or the Symantec compilers for this native
PowerPC Challenge. If you have any questions, or would like some test data for your
code, please send me e-mail at one of the Programmer’s Challenge addresses, or
directly to boonstra@ultranet.com.
Two Months Ago Winner
Congratulations to Eric Lengyel (Blacksburg, VA) for submitting the fastest and
smallest entry to the Reversible Scrambling Algorithm Challenge. Despite an
unfortunate delay in publication of the magazine that left participants with less time
than usual to complete the Challenge, three of the four entries I received by the
extended deadline worked correctly, at least in part.
You might recall that the Challenge was to write code that would raise a large
integer message to a power and compute the remainder modulo another large integer.
The name of the Challenge comes from the fact that this technique is reversible, given
properly chosen integers. Eric is a graduate student in Mathematics at Virginia Tech,
and he took advantage of a highly optimized multiple precision integer arithmetic
library that he had written as part of a number theory project involving the
factorization of very large numbers.
Each of the working entries converted the BigNum representation provided in the
problem into one that right-justified numbers into a fixed-length data structure.
While this imposes a restriction on the maximum size integer that the code can handle,
this assumption was permitted by the problem statement. In Eric’s code, the
restriction is controlled by a single #define statement.
Eric uses a binary exponentiation algorithm to raise the message to the specified
power, and takes advantage of facts from number theory that allow the remainder to be
computed at each step of the exponentiation. The time to perform the exponentiation is
therefore proportional to the logarithm of the exponent. Eric’s multiplication and
division routines use the 68020’s capability to compute the 64-bit product of two
longwords and to divide a 64-bit dividend by a longword. The multiplication, division,
exponentiation, and compare routines in Eric’s code are general purpose and could be
used in any 68K application that needs large integers.