Mar 95 Dialog Box
- Jan 95 Challenge
- Jan 95 Dialog Box
- Feb 95 Dialog Box
- Apr 95 Dialog Box
- May 95 Dialog Box
- Jun 95 Dialog Box
- Jul 95 Dialog Box
- Aug 95 Dialog Box
- Sep 95 Dialog Box
- Nov 95 Dialog Box
Volume Number: 11
Issue Number: 3
Column Tag: Dialog Box
Dialog Box 
By Scott T Boyd, Editor
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
Challenging Challenge Challenged
One of the Huffman challenge entrants, Allen Stenger, found a bug in Bob Boonstra’s
winning published Huffman code. It’s minor (ushort should be ulong) but it’s a real
bug. Fixing it doesn’t change Bob’s speed. Here’s some background on the problem.
- Mike Scanlin
progchallenge@xplain.com
Allen writes:
Subj: Huffman solution error?
I believe I’ve found an error in Bob Boonstra’s published solution to the Huffman
challenge (MacTech, January 1995 issue). Look at p. 72, the definition of macro
ProcessBitSlow. Observe that temp is declared as register ushort; contrast this
with the immediately preceding macros ProcessBit and ProcessBitFast, where it is
defined as register ulong. Actually all three should be ulong. The reason is that
temp is the offset to the child node; since the node table could be as large as 256K
bytes (64K nodes), temp can hold the offset in units of nodes but when
ProcessBitSlow does the multiplication temp *= sizeof(DecodeNode), temp may
overflow.
I was able to provoke this failure using the following example: The decoded
numbers are either 3-bit numbers 0-7 or 16 bits numbers 8000-FFFF. The 3-bit
numbers are encoded in 4 bits as 0-7 (i.e., a leading 0 bit followed by the number).
The 16 bit numbers are encoded as themselves (they already have a leading 1 bit).
Under this scheme A000 is decoded incorrectly.
- Allen Stenger.
Bob replies:
Allen Stenger is correct in pointing out an error in the published solution for the
HuffmanDecode challenge. As Allen points out, the declaration of the variable temp in
macro ProcessBitSlow should be register ulong.
The bug shows up when both of the following are true: (1) the private storage
available exceeds 64K, AND (2) numSymElems is large, greater than ~8K to ~32K,
depending on maxMemoryUsage.
The bug does not occur if maxMemoryUsage is <=64K. Condition (2) for the bug
is really when the size of the decode table exceeds the available storage. Since each
node in the decode table is 4 bytes, and since there are (roughly) 2 nodes in the decode
table for each element of the symbol table, the bug shows up under the following
conditions:
numSymElems maxMemoryUsage
> ~8K > 64K
>~16K >128K
>~32K >256K (beyond Challenge limits)
max (2**16-1) >512K (beyond Challenge limits)
(The relationship to numSymElems is approximate because it depends on the degree of
balance in the tree representing the Huffman encoding.)
In these cases, some symbols will be decoded incorrectly. In the case cited by
Allen, numSymElems is >32K, and the error shows up if maxMemoryUsage is >64K.
Correcting the bug changes a few xxx.W instructions to xxx.L, but shortens the
code generated by the macro in question by one instruction, and actually improves the
run time by an almost imperceptible amount.
It just goes to show you can’t do enough testing. My testing used Huffman
encodings that were generated from large text files, so I got encodings with a few
thousand elements. Still, I should have caught this one by inspection. Congratulations
to Allen for detecting the error, and good luck to him in future Challenges.
- Bob Boonstra
Anonymously Yours
I’ve heard that it’s possible to anonymously send e-mail to someone. I’ve also heard
that in order for this to be really anonymous you need to send it through three or four
anonymous re-mailers. Could you publish the addresses of these remailers and give an
example of how to send e-mail that has a very high chance of remaining anonymous?
[name and address withheld]
Great Prograph Coverage
Your January ’95 issue looks like one of the best ever. Two CD-ROMs, who could ask
for more? I was also very excited to see Kurt Schmucker’s article on Prograph
Commands. I hope that these articles on Prograph become a regular feature. As a
former member of the Software Frameworks Association, I’m glad to see MacTech
really taking up the slack where Frameworks left off. I have been working with
Prograph CPX for several months now and find it to be a great tool.
Please keep up your coverage of it, and other new OOP technologies.
- Steve Wilson , Emergent Behavior
emergent@aol.com
Do the Cobbler’s Children Always Go Barefoot?
I am inspired to write after reading the letter by Steve Weller, "A Trail of Good
Intentions", printed in the December Dialog Box. Like Steve, I always thought that "C
stood for cryptic but C++ is much worse.
I can best describe myself as a classic Mac hacker, that is one who programs the
Mac for the sheer joy of it and not
to make a living. As a programmer, my user interface is the editor I use. I have
made a few dollars on shareware but mostly I program the Mac just because I love the
Mac’s user interface.
You can judge the low quality of the editors that come with most C++ compilers
by the number of third party editors being sold. I personally can’t stand to use any of
the popular C++ environments (with or without third party editors) because they
don’t just compare to the editor in THINK Pascal.
THINK Pascal’s editor automatically formats my source code. It finds syntax
errors before I waste time trying to compile. Most of the Mac user interface is in the
Runtime and Interface libraries so I seldom have to include other libraries or
interfaces. The stops are easier and quicker to use than the ones in C++. Best of all, the
compiler and linker are very fast for reasonable sized programs.
The only thing I have found that really slows THINK Pascal is when I play with
MacApp, TCL or one of the other bloated object libraries. For my serious programs I
use THINK Pascal with a non-object shell generated by Marksman. In spite of the fact
that THINK Pascal hasn’t been updated for several years, I am still more productive
using it than C++.
I wish the technical support engineers who write the Symantec Top Ten would
answer these two questions.
#1 When is Symantec going to produce a new version of THINK Pascal that will
generate both 680x0 and PowerPC code?
#2 Why don’t they transplant the advanced editor, compiler and linker technologies
found in THINK Pascal to their slow user hostile C++?
- Fred Johnson
70651.3171@compuserve.com