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

Corel Painter 20.1.0.285 - Digital art s...
Corel Painter lets you advance your digital art style with painted textures, subtle glazing brushwork, interactive gradients, and realistic Natural-Media. Easily transition from traditional to... Read more
iTubeDownloader 6.5.19 - Easily download...
iTubeDownloader is a powerful-yet-simple YouTube downloader for the masses. Because it contains a proprietary browser, you can browse YouTube like you normally would. When you see something you want... Read more
OmniFocus 3.8 - GTD task manager with iO...
OmniFocus is an organizer app. It uses projects to organize tasks naturally, and then add tags to organize across projects. Easily enter tasks when you’re on the go, and process them when you have... Read more
Hazel 4.4.5 - Create rules for organizin...
Hazel is your personal housekeeper, organizing and cleaning folders based on rules you define. Hazel can also manage your trash and uninstall your applications. Organize your files using a familiar... Read more
Macs Fan Control 1.5.7 - Monitor and con...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more
Acorn 6.6 - Bitmap image editor.
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
OnyX 3.8.2 - Maintenance and optimizatio...
OnyX is a multifunction utility that you can use to verify the startup disk and the structure of its system files, to run miscellaneous maintenance and cleaning tasks, to configure parameters in the... Read more
macOS Catalina 10.15.5 - An Operating Sy...
macOS Catalina gives you more of everything you love about Mac. Experience three all-new media apps: Apple Music, Apple TV, and Apple Podcasts. Locate a missing Mac with the new Find My app. And now... Read more
macOS High Sierra Security Updates 10.13...
macOS High Sierra introduces new core technologies that improve the most important functions of your Mac. From rearchitecting how it stores your data to improving the efficiency of video streaming to... Read more
Numi 3.28 - Menu-bar calculator supports...
Numi is a calculator that magically combines calculations with text, and allows you to freely share your computations. Numi combines text editor and calculator Support plain English. For example, '5... Read more

Latest Forum Discussions

See All

Steam Link Spotlight - Signs of the Sojo...
Steam Link Spotlight is a feature where we look at PC games that play exceptionally well using the Steam Link app. Our last entry was XCOM: Chimera Squad. Read about how it plays using Steam Link's new mouse and keyboard support over here. | Read more »
Steampunk Tower 2, DreamGate's sequ...
Steampunk Tower 2 is a DreamGate's follow up to their previous tower defence game. It's available now for both iOS and Android as a free-to-play title and will see players defending their lone base by kitting it out with a variety of turrets. [... | Read more »
Clash Royale: The Road to Legendary Aren...
Supercell recently celebrated its 10th anniversary and their best title, Clash Royale, is as good as it's ever been. Even for lapsed players, returning to the game is as easy as can be. If you want to join us in picking the game back up, we've put... | Read more »
Pokemon Go Fest 2020 will be a virtual e...
Niantic has announced that Pokemon Go Fest will still take place this year although understandably it won't be a physical event. Instead, it will become a virtual celebration and is set to be held on 25th and 26th July. [Read more] | Read more »
Marvel Future Fight's major May upd...
Marvel Future Fight's latest update has now landed, and it sounds like a big one. The focus this time around is on Marvel's Guardians of the Galaxy, and it introduces all-new characters, quests, and uniforms for players to collect. [Read more] | Read more »
SINoALICE, Yoko Taro and Pokelabo's...
Yoko Taro and developer Pokelabo's SINoALICE has now opened for pre-registration over on the App Store. It's already amassed 1.5 million Android pre-registrations, and it's currently slated to launch on July 1st. [Read more] | Read more »
Masketeers: Idle Has Fallen's lates...
Masketeers: Idle Has Fallen is the latest endeavour from Appxplore, the folks behind Crab War, Thor: War of Tapnarok and Light A Way. It's an idle RPG that's currently available for Android in Early Access and will head to iOS at a later date. [... | Read more »
Evil Hunter Tycoon celebrates 2 million...
Evil Hunter Tycoon has proved to be quite the hit since launching back in March, with its most recent milestone being 2 million downloads. To celebrate the achievement, developer Super Planet has released a new updated called Darkness' Front Yard... | Read more »
Peak's Edge is an intriguing roguel...
Peak's Edge is an upcoming roguelike puzzle game from developer Kenny Sun that's heading for both iOS and Android on June 4th as a free-to-play title. It will see players rolling a pyramid shape through a variety of different levels. [Read more] | Read more »
Clash Royale: The Road to Legendary Aren...
Supercell recently celebrated its 10th anniversary and their best title, Clash Royale, is as good as it's ever been. Even for lapsed players, returning to the game is as easy as can be. If you want to join us in picking the game back up, we've put... | Read more »

Price Scanner via MacPrices.net

New 16″ MacBook Pros now on sale for up to $2...
Apple reseller DataVision is now offering new 16″ Apple MacBook Pros for up to $255 off MSRP, each including free shipping. Prices start at $2194. DataVision charges sales tax for NY, NJ, PA, and CA... Read more
Apple now offering Certified Refurbished iPho...
Apple is now offering Certified Refurbished iPhone Xr models in the refurbished section of their online store starting at $499. Each iPhone comes with Apple’s standard one-year warranty, ships free,... Read more
Sale! Get a 10.2″ 32GB WiFi iPad for only $27...
Walmart has new 10.2″ 32GB WiFi iPads on sale for $50 off Apple’s MSRP, only $279. These are the same iPads sold by Apple in their retail and online stores. Be sure to select Walmart as the seller... Read more
Apple resellers offer new 2020 Mac minis for...
Apple resellers are offering new 2020 Mac minis for up to $50 off Apple’s MSRP with prices available starting at $759. Shipping is free: (1) B&H Photo: – 2020 4-Core Mac mini: $759 $40 off MSRP... Read more
Sprint is offering the Apple iPhone 11 free t...
Did you miss out on Sprint’s recent free iPhone SE promotion? No worries. Sprint has the 64GB iPhone 11 available for $0 per month for new lines when you trade-in a qualifying phone in any condition... Read more
Apple has clearance 2019 13″ 1.4GHz MacBook P...
Apple has Certified Refurbished 2019 13″ 1.4GHz 4-Core Touch Bar MacBook Pros available today starting at $979 and up to $440 off original MSRP. Apple’s one-year warranty is included, shipping is... Read more
Apple restocks 2019 MacBook Airs starting at...
Apple has clearance, Certified Refurbished, 2019 13″ MacBook Airs available again starting at $779. Each MacBook features a new outer case, comes with a standard Apple one-year warranty, and is... Read more
Apple restocks clearance Mac minis for only $...
Apple has restocked Certified Refurbished 2018 4-Core Mac minis for only $599. Each mini comes with a new outer case plus a standard Apple one-year warranty. Shipping is free: – 3.6GHz Quad-Core... Read more
Apple’s new 2020 13″ MacBook Airs on sale for...
B&H Photo has Apple’s new 2020 13″ 4-Core and 6-Core MacBook Airs on sale today for $50-$100 off Apple’s MSRP, starting at $949. Expedited shipping is free to many addresses in the US. The... Read more
B&H continues to offer clearance 2019 13″...
B&H Photo has clearance 2019 13″ 4-Core MacBook Pros available for up to $300 off Apple’s original MSRP, with prices starting at $1149. Expedited shipping is free to many addresses in the US. B... Read more

Jobs Board

Security Officer - *Apple* Store - NANA (Un...
**Security Officer \- Apple Store** **Description** About NMS Built on a culture of safety and integrity, NMSdelivers award\-winning, integrated support services to Read more
Transition Into Practice Program (TIP) - Sept...
…Academy-Transition into Practice (TIP) Residency program at St Mary Medical Center in Apple Valley, CA. **We are seekingRegistered Nurses who are:** + New graduate Read more
Essbase Developer - *Apple* - Theorem, LLC...
Job Summary Apple is seeking an experienced, detail-minded Essbase developer to join our worldwide business development and strategy team. If you are someone who Read more
Senior Software Engineer @ *Apple* - Theore...
Job Summary Apple is looking for a seasoned senior software engineer to join our worldwide business development and strategy team. This is an opportunity to lead a Read more
Cub Foods - *Apple* Valley - Now Hiring Par...
Cub Foods - Apple Valley - Now Hiring Part Time! United States of America, Minnesota, Apple Valley Retail Operations Post Date May 18, 2020 Requisition # 119230 Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.