TweetFollow Us on Twitter

Mar 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 or source 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

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Latest Forum Discussions

See All

Bid farewell to Penacony as Honkai: Star...
Penacony has been a story of twists, exciting new characters, and strong allies, and soon Honkai: Star Rail will be finishing it with a bang. Version 2.3, fittingly titled Farewell Penacony, will be launching June 19th and will feature updates to... | Read more »
HoYoverse roll out their plans for Anime...
For those who are looking to book a getaway in July, you might give some thought to Los Angeles between the 4th and 7th, which just so happens to coincide with the Anime Expo 2024. Amongst all the storied attendees is HoYoverse, who will be... | Read more »
The first rule of Brok the InvestiGator...
Mobile gamers were recently able to get their hands on BROK the InvestiGator, a point-and-click following the adventures of the titular reptile, a detective who can solve crimes through wit or brawn. If you were one that chose the latter then... | Read more »
Diablo Immortal celebrates second annive...
It has been two years since Diablo Immortal launched and despite some very valid criticism of its business model, it has done pretty well for itself. The Tempest class also gives it a lot of grace. To celebrate this anniversary, the March of the... | Read more »
Pokemon GO pulls on its jersey for a foo...
There have been a lot of jokes about this, some by me, but Pokemon Go has genuinely done a lot of good by getting people out and about.Pokemon GO Fest 2024: Madrid is fast approaching, and Niantic has set up a new area in a bit to get people to... | Read more »
Stumble Guys dials up the calamity 1000%...
Credit where it is due, Stumble Guys has had a few top-class crossovers in its’ life; Dungeons and Dragons, Rabbids and SpongeBob Squarepants to name but a few. It is such a shame, though, that all of these have now been well and truly trounced... | Read more »
You’re going to need a bigger boat as wa...
I am sure we all know that Finding Nemo quote of fish being friends and not food, however, Play Together is going in a completely opposite direction with their latest update. Introducing the Monstrous Fish, these behemoths are proving themselves... | Read more »
Supercell's hotly anticipated Squad...
If you've ever picked up a mobile, even without looking at an App storefront, you will have heard of Supercell, the massive company behind Clash of Clans, Brawl Stars, and Clash Royale. Now, the catalogue grows as Squad Busters prepares to take... | Read more »
Top Mobile Game Discounts
Every day, we pick out a curated list of the best mobile discounts on the App Store and post them here. This list won't be comprehensive, but it every game on it is recommended. Feel free to check out the coverage we did on them in the links below... | Read more »
Osseous has a bone to pick with you as t...
We recently quelled the immense threat brought about by Zemouregal and the giant dragon Vorkath in Runescape, and you might think that earnt adventurers a little break, but no. Instead, Jagex has decided it is time to face off against an equally... | Read more »

Price Scanner via MacPrices.net

Could A Smarter Siri Infused With AI (‘Apple...
FEATURE – The iPhone is already smart, but it’s about to become more intelligent. AI — short for artificial intelligence — is widely expected to be the main topic of discussion at this year’s WWDC (... Read more
Update: For WWDC, Amazon has lowered prices o...
Amazon has every configuration and color of Apple’s M3 MacBook Airs now on sale for $170-$210 off MSRP, starting at only $899 shipped, as Apple holds their annual WWDC conference this week. Their... Read more
Deal Alert! 2nd-generation Apple AirPods on s...
Amazon has 2nd generation Apple AirPods on sale right now for only $79.99 shipped. That’s $50 (38%) off Apple’s MSRP. Their price is the lowest currently available for a new set of AirPods from any... Read more
13-inch M3 MacBook Airs on sale for $150-$200...
Amazon has every configuration and color of Apple’s 13″ M3 MacBook Air on sale for $150-$200 off MSRP, now starting at only $899 shipped. Their prices are the lowest available for these Airs among... Read more
Apple is now selling 13-inch M3 MacBook Airs...
Apple has Certified Refurbished 13″ M3 MacBook Airs now in stock for $170-$230 off MSRP, Certified Refurbished. Prices start at $929. These are the cheapest M3-powered MacBooks for sale at Apple and... Read more
Amazon is offering $150-$200 discounts on 15-...
Amazon is offering a $150-$200 discount on every configuration and color of Apple’s M3-powered 15″ MacBook Airs. Prices start at $1149 for models with 8GB of RAM and 256GB of storage: – 15″ M3... Read more
Apple is now selling 15-inch M3 MacBook Airs...
Apple has Certified Refurbished 15″ M3 MacBook Airs in stock today starting at only $1099 and ranging up to $260 off MSRP. These are the cheapest M3-powered 15″ MacBook Airs for sale today at Apple.... Read more
13-inch M3 MacBook Air prices drop to record...
B&H Photo is offering discounts on new 13-inch M3 MacBook Airs ranging up to $200 off MSRP ahead of Apple’s WWDC conference next week. Prices start at only $899! These are the lowest prices... Read more
Apple HomePods on rare sale for $20-$30 off M...
Best Buy is offering a $20-$30 discount on Apple HomePods this weekend on their online store. The HomePod mini is on sale for $79.99, $20 off MSRP, while Best Buy has the full-size HomePod on sale... Read more
Base 14-inch M3 MacBook Pro on sale for $1399...
Amazon and B&H Photo both have the base 14″ M3 MacBook Pro on sale for $200 off Apple’s MSRP, only $1399. Shipping is free at both retailers (free 1-2 day shipping at B&H): – 14″ M3 MacBook... Read more

Jobs Board

*Apple* Systems Administrator - JAMF - Activ...
…**Public Trust/Other Required:** None **Job Family:** Systems Administration **Skills:** Apple Platforms,Computer Servers,Jamf Pro **Experience:** 3 + years of Read more
*Apple* Systems Administrator - JAMF - Activ...
…**Public Trust/Other Required:** None **Job Family:** Systems Administration **Skills:** Apple Platforms,Computer Servers,Jamf Pro **Experience:** 3 + years of Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Armed Security Officer - *Apple* Store - NA...
…provide services in which the client's health, safety, and security is our #1 priority. The Apple Store is located on the 2 nd floor of the 5 th Avenue Mall. Read more
Liquor Stock Clerk - S. *Apple* St. - Idaho...
Liquor Stock Clerk - S. Apple St. Boise Posting Begin Date: 2023/10/10 Posting End Date: 2024/10/14 Category: Retail Sub Category: Customer Service Work Type: Part Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.