Apr 94 Challenge
Volume Number: 10
Issue Number: 4
Column Tag: Programmers’ Challenge
Related Info: Memory Manager
Programmers’ Challenge 
By Mike Scanlin, MacTech Magazine Regular Contributing Author
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
The rules
Here’s how it works: Each month there will be a different programming challenge
presented here. First, you must write some code that solves the challenge. Second, you
must optimize your code (a lot). Then, submit your solution to MacTech Magazine
(formerly MacTutor). A winner will be chosen based on code correctness, speed, size
and elegance (in that order of importance) as well as the postmark of the answer. In
the event of multiple equally desirable solutions, one winner will be chosen at random
(with honorable mention, but no prize, given to the runners up). The prize for the
best solution each month is $50 and a limited edition “The Winner! MacTech Magazine
Programming Challenge” T-shirt (not to be found in stores).
In order to make fair comparisons between solutions, all solutions must be in
ANSI compatible C (i.e., don’t use Think’s Object extensions). Only pure C code can be
used. Any entries with any assembly in them will be disqualified (except for those
challenges specifically stated to be in assembly). However, you may call any routine
in the Macintosh toolbox you want (i.e., it doesn’t matter if you use NewPtr instead of
malloc). All entries will be tested with the FPU and 68020 flags turned off in THINK C.
When timing routines, the latest version of THINK C will be used (with ANSI Settings
plus “Honor ‘register’ first” and “Use Global Optimizer” turned on) so beware if you
optimize for a different C compiler. All code should be limited to 60 characters wide.
This will aid us in dealing with e-mail gateways and page layout.
The solution and winners for this month’s Programmers’ Challenge will be
published in the issue two months later. All submissions must be received by the 10th
day of the month printed on the front of this issue.
All solutions should be marked “Attn: Programmers’ Challenge Solution” and
sent to Xplain Corporation (the publishers of MacTech Magazine) via “snail mail” or
preferably, e-mail - AppleLink: MT.PROGCHAL, Internet: progchallenge@xplain.com,
CompuServe: 71552,174 and America Online: MT PRGCHAL. If you send via snail
mail, please include a disk with the solution and all related files (including contact
information). See page 2 for information on “How to Contact Xplain Corporation.”
MacTech Magazine reserves the right to publish any solution entered in the
Programming Challenge of the Month and all entries are the property of MacTech
Magazine upon submission. The submission falls under all the same conventions of an
article submission.
SWAP BLOCKS
This month’s challenge is to swap two adjacent blocks of memory using a finite
amount of temporary swap space. This is something the Memory Manager has to do
quite often as it shuffles blocks around in the heap.
The prototype of the function you write is:
/* 1 */
void SwapBlocks(p1, p2, swapPtr size1,
size2, swapSize)
void *p1;
void *p2;
void *swapPtr;
unsigned long size1;
unsigned long size2;
unsigned long swapSize;
p1 and p2 point to the beginnings of the two blocks to swap. size1 and size2 are
their respective sizes (in bytes). Both blocks begin on addresses divisible by 4 and
have sizes that are divisible by 4. swapPtr points to the scratch area you can use (if
you need to) and swapSize is the size of that area (between 256 and 4096 bytes,
inclusive). swapPtr and swapSize are also each divisible by 4. If the two blocks look
like this on entry:
/* 2 */
12345678ABCDEFGHIJKL
^ ^
p1 p2 size1 = 8 size2 = 12
then the same memory locations will look like this on exit:
/* 3 */
ABCDEFGHIJKL12345678
When measuring performance I will be calling your routine many times. The
distribution of the sizes of the blocks is as follows:
4 to 16 bytes 20% of the time
20 to 32 bytes 20% of the time
36 to 64 bytes 20% of the time
68 to 256 bytes 20% of the time
260 to 4096 bytes 10% of the time
4100 or more bytes 10% of the time
You would normally write this kind of routine in assembly, but let’s see how well
you can do in pure C (remember, everyone has the same handicap). If you want to
submit a pure assembly solution along with your pure C solution then please do so (but
the assembly version will NOT be counted as an entry in the challenge and it will not
win anything other than a mention in this column).
TWO MONTHS AGO WINNER
Of the 11 entries I received for the We Pry Any Heap (Happy New Year) anagram
challenge, only 5 worked correctly. Congrats to Larry Landry (Rochester, NY) for the
dual honor of coming in 1st both in terms of speed and smallest code size.
The times for anagramming “programmer” (462 anagrams) and “mactech
magazine” (3365 anagrams) with a 19,335 word English dictionary are given here
(more weight was given to longer inputs (15-30 characters) when ranking
contestants). Numbers in parens after a person’s name indicate how many times that
person has finished in the top 5 places of all previous Programmer Challenges, not
including this one:
Name code time 1 time 2
Larry Landry (1) 830 20 1048
Stepan Riha (5) 2352 45 1166
Bob Boonstra (6) 1370 52 1688
Allen Stenger (3) 1044 23 1701
Mark Nagel 1134 81 51407
Most of the entrants figured out that the key to speeding up the anagram process
was to pare down the size of the dictionary first. Once you have the input characters