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

 
AAPL
$102.50
Apple Inc.
+0.25
MSFT
$45.43
Microsoft Corpora
+0.55
GOOG
$571.60
Google Inc.
+2.40

MacTech Search:
Community Search:

Software Updates via MacUpdate

VueScan 9.4.41 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
Cloud 3.0.0 - File sharing from your men...
Cloud is simple file sharing for the Mac. Drag a file from your Mac to the CloudApp icon in the menubar and we take care of the rest. A link to the file will automatically be copied to your clipboard... Read more
LibreOffice 4.3.1.2 - Free Open Source o...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
SlingPlayer Plugin 3.3.20.505 - Browser...
SlingPlayer is the screen interface software that works hand-in-hand with the hardware inside the Slingbox to make your TV viewing experience just like that at home. It features an array of... Read more
Get Lyrical 3.8 - Auto-magically adds ly...
Get Lyrical auto-magically add lyrics to songs in iTunes. You can choose either a selection of tracks, or the current track. Or turn on "Active Tagging" to get lyrics for songs as you play them.... Read more
Viber 4.2.2 - Send messages and make cal...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device,... Read more
Cocktail 7.6 - General maintenance and o...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
LaunchBar 6.1 - Powerful file/URL/email...
LaunchBar is an award-winning productivity utility that offers an amazingly intuitive and efficient way to search and access any kind of information stored on your computer or on the Web. It provides... Read more
Maya 2015 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more
BBEdit 10.5.12 - Powerful text and HTML...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more

Latest Forum Discussions

See All

Qube Kingdom – Tips, Tricks, Strategies,...
Qube Kingdom is a tower defense game from DeNA. You rally your troops – magicians, archers, knights, barbarians, and others – and fight against an evil menace looking to dominate your kingdom of tiny squares. Planning a war isn’t easy, so here are a... | Read more »
Qube Kingdom Review
Qube Kingdom Review By Nadia Oxford on August 29th, 2014 Our Rating: :: KIND OF A SQUARE KINGDOMUniversal App - Designed for iPhone and iPad Qube Kingdom has cute visuals, but it’s a pretty basic tower defense game at heart.   | Read more »
Fire in the Hole Review
Fire in the Hole Review By Rob Thomas on August 29th, 2014 Our Rating: :: WALK THE PLANKUniversal App - Designed for iPhone and iPad Seafoam’s Fire in the Hole looks like a bright, 8-bit throwback, but there’s not enough booty to... | Read more »
Alien Creeps TD is Now Available Worldwi...
Alien Creeps TD is Now Available Worldwide Posted by Ellis Spice on August 29th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Dodo Master Review
Dodo Master Review By Jordan Minor on August 29th, 2014 Our Rating: :: NEST EGGiPad Only App - Designed for the iPad Dodo Master is tough but fair, and that’s what makes it a joy to play.   | Read more »
Motorsport Manager Review
Motorsport Manager Review By Lee Hamlet on August 29th, 2014 Our Rating: :: MARVELOUS MANAGEMENTUniversal App - Designed for iPhone and iPad Despite its depth and sense of tactical freedom, Motorsport Manager is one of the most... | Read more »
Motorsport Manager – Beginner Tips, Tric...
The world of Motorsport management can be an unforgiving and merciless one, so to help with some of the stress that comes with running a successful race team, here are a few hints and tips to leave your opponents in the dust. | Read more »
CalPal Update Brings the App to 2.0, Add...
CalPal Update Brings the App to 2.0, Adds Lots of New Stuff Posted by Ellis Spice on August 29th, 2014 [ permalink ] | Read more »
Baseball Battle Review
Baseball Battle Review By Jennifer Allen on August 29th, 2014 Our Rating: :: SIMPLE HITTINGUniversal App - Designed for iPhone and iPad Simple and cute, Baseball Battle is a fairly fun baseball game for those looking for something... | Read more »
Checkmark 2.1 Update Released, and it’s...
Checkmark 2.1 Update Released, and it’s on Sale for a Limited Time Posted by Jessica Fisher on August 29th, 2014 [ permalink ] | Read more »

Price Scanner via MacPrices.net

Labor Day Weekend iPad mini sale; $50 to $100...
Best Buy has the iPad mini with Retina Display (WiFi models) on sale for $50 off MSRP on their online store for Labor Day Weekend. Choose free shipping or free local store pick up. Price is for... Read more
13-inch 1.4GHz MacBook Air on sale for $899,...
Adorama has the new 2014 13″ 1.4GHz/128GB MacBook Air on sale for $899.99 including free shipping plus NY & NJ tax only. Their price is $100 off MSRP. Read more
It’s Official: Apple Issues Invitations To Se...
Apple has issued one of its characteristically cryptic press invitations for a special event to be held at the Flint Center for the Performing Arts in hometown Cupertino on Sept. 9, 2014 at 10:00 am... Read more
Tablet Shipments To See First On-year Decline...
TrendForce analyst Caroline Chen notes that when the iPad launched in 2010, it was an instant hit and spurred a tablet PC revolution, with tablets so popular that that notebook PC sales stagnated and... Read more
SOBERLINK Releases Apple iOS Compatible Handh...
Cypress, California based SOBERLINK, Inc., creator of the first handheld Breathalyzer designed to improve recovery outcomes, continues to show prominence in the mobile alcohol monitoring space with... Read more
New 21″ 1.4GHz iMac on sale again for $999, s...
Best Buy has the new 21″ 1.4GHz iMac on sale for $999.99 on their online store. Their price is $100 off MSRP. Choose free shipping or free local store pick up. Price is for online orders only, in-... Read more
Smartphone Outlook Remains Strong for 2014, U...
According to a new mobile phone forecast from the International Data Corporation (IDC) Worldwide Quarterly Mobile Phone Tracker, more than 1.25 billion smartphones will be shipped worldwide in 2014,... Read more
Save up to $60 with Apple refurbished iPod to...
The Apple Store has Apple Certified Refurbished 5th generation iPod touches available starting at $149. Apple’s one-year warranty is included with each model, and shipping is free. Many, but not all... Read more
12-Inch MacBook Air Coming in 4Q14 or 2015 –...
Digitimes’ Aaron Lee and Joseph Tsai report that according to Taiwan-based upstream supply chain insiders, Apple plans to launch a thinner MacBook model either at year end 2014 or in 2015, and that... Read more
Sapphire Screen “Most Wanted” iPhone 6 New Fe...
According to the ‘uSell.com iPhone Most Wanted Survey’ — a representative survey of 1,000 U.S. smartphone users conducted by used iPhone marketplace uSell.com — close to half of all smartphone users... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.