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

VOX 3.4.1 - Music player that supports m...
VOX just sounds better! The beauty is in its simplicity, yet behind the minimal exterior lies a powerful music player with a ton of features and support for all audio formats you should ever need.... Read more
Quicken 6.2.2 - Complete personal financ...
Quicken makes managing your money easier than ever. Whether paying bills, upgrading from Windows, enjoying more reliable downloads, or getting expert product help, Quicken's new and improved features... Read more
QuickBooks 19.0.8.938 - Financial manage...
QuickBooks helps you manage your business easily and efficiently. Organize your finances all in one place, track money going in and out of your business, and spot areas where you can save. Built for... Read more
Microsoft Office 365, 2019 16.50 - Popul...
Microsoft Office 365. The essentials to get it all done. Unmistakably Office, designed for Mac Get started quickly with new, modern versions of Word, Excel, PowerPoint, Outlook and OneNote-... Read more
Xcode 12.5.1 - Integrated development en...
Xcode includes everything developers need to create great applications for Mac, iPhone, iPad, and Apple Watch. Xcode provides developers a unified workflow for user interface design, coding, testing... Read more
Tidy Up (Three Computers) 5.4.3 - Find d...
Tidy Up is a full-featured duplicate finder and disk-tidiness utility. Features Supports Lightroom: it is now possible to search and collect duplicates directly in the Lightroom library. Multiple... Read more
Tidy Up 5.4.3 - Find duplicate files and...
Tidy Up is a full-featured duplicate finder and disk-tidiness utility. Features: Supports Lightroom: it is now possible to search and collect duplicates directly in the Lightroom library. Multiple... Read more
DiskCatalogMaker 8.3.7 - Catalog your di...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast Finder-like intuitive look and feel Super-fast search algorithm Can compress catalog data for... Read more
Meteorologist 3.4.4 - Popular weather ap...
Meteorologist is a simple interface to weather provided by weather.com. It provides the ability to show the weather in the main menu bar, displaying more detail in a pop-up menu, whose contents are... Read more
iShowU Instant 1.4.5 - Full-featured scr...
iShowU Instant gives you real-time screen recording like you've never seen before! It is the fastest, most feature-filled real-time screen capture tool from shinywhitebox yet. All of the features you... Read more

Latest Forum Discussions

See All

Game Dev Story+ is a new business manage...
Kairosoft has launched a new version of its classic business management sim Game Dev Story for iOS devices. It is available to play on either iPhone or iPad if you have an active Apple Arcade subscription. [Read more] | Read more »
Horizon Chase Mobile gets new Walker-X D...
Brazilian developer Aquiris has released a new Walker-X DLC for its mobile racing game Horizon Chase Mobile. The DLC is available now for iOS and Android devices. [Read more] | Read more »
Apple Arcade: Ranked - Top 25 [Updated 6...
In case you missed it, I am on a quest to rank every Apple Arcade game there is. [Read more] | Read more »
2112TD, Refinery Productions' sci-f...
Refinery Productions has announced the release of the second major update for their tower defence title 2112TD. It is available for both the iOS and Android versions of the game and is completely free if you already own the game. [Read more] | Read more »
Divinity - Original Sin 2 - Gameplay Jou...
Now that I have my quest legs, Divinity - Original Sin 2 is feeling more and more like an epic quest than a curiously rich playground. It also seems like a good sign that I'm ready to break free of the chains keeping me in this starting area to... | Read more »
Much-awaited Alchemy Stars strategy RPG...
The classic RPG genre comes in various forms, but Alchemy Stars have managed to produce an entirely new spin. This exciting game is set to release for both iOS and Android on June 17, escalating the excitement that precedes its pre-registration... | Read more »
Armed Emeth is the latest JRPG from KEMC...
KEMCO has announced the release of yet another RPG to their ever-growing library of games. The latest is called Armed Emeth and is available now for both iOS and Android. It has both premium and freemium version, with the latter featuring ads. [... | Read more »
Square Enix is remastering the first six...
Square Enix is going to be releasing remasters of the first six Final Fantasy games for both Steam and mobile storefronts. [Read more] | Read more »
Divinity - Original Sin 2 - Gameplay Jou...
It only took me four entries in this journal to finally advance some quests instead of just pick them up! Fort Joy has been an entertainingly complex starting area, but it always just seemed I was spinning my tires trying to find the key to moving... | Read more »
Distract Yourself With These Great Mobil...
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 »

Price Scanner via MacPrices.net

Apple has a wide range of M1-powered Macs in...
Prime Day 2021 may be over, but you can still realize significant savings on an Apple Mac powered by an Apple M1 processor. Apple has several models available today in their Certified Refurbished... Read more
Amazon Prime Day Sale: Apple’s 11″ M1 128GB i...
Amazon has the new 2021 11″ 128GB WiFi iPad Pro in stock today and on sale for $699 as part of their Prime Day 2021 sales. Shipping is free. Their price is $100 off Apple’s MSRP, and it’s the lowest... Read more
Amazon Prime Day 2021 Sale: Get an 8-Core CPU...
Amazon has new 13″ Apple M1 MacBook Airs with 8-Core M1 Silicon CPUs & 8-Core GPUs on sale today for $150 off MSRP as part of their Prime Day 2021 sales, each including free shipping: – 13″ M1... Read more
Amazon Prime Day Sale: Get Apple’s M1 13″ Mac...
Amazon has Apple’s 13″ MacBook Pros with M1 Apple Silicon CPUs on sale for $200 off MSRP today as part of their Prime Day 2021 sales, starting at $1099. Shipping is free: – 2020 13″ MacBook Pro Space... Read more
Amazon discounts Apple’s popular new M1 Mac m...
Amazon has new Apple M1 Mac minis in stock today and on sale for $100-$120 off Apple’s MSRP, with prices starting at only $599, as part of their Prime Day 2021 sales. Their prices are the lowest... Read more
Amazon Prime Day 2021 Deal: Apple’s 13″ 2GHz...
Amazon has 2020 13″ MacBook Pros with 10th generation Intel CPUs on sale for $200-$350 off Apple’s MSRP as part of their Prime Day 2021 sales. Shipping is free. Be sure to purchase the MacBook Pro... Read more
Amazon Prime Day 2021 Sale: Get an Apple M1 M...
Amazon is offering a $100 discount on Apple’s 13″ M1 MacBook Airs with 7-Core GPUs and 8-Core CPU as part of their Prime Day 2021 sales. With Amazon’s discount, their price drops to only $899 with... Read more
Amazon Prime Day Sale: 27″ 5K 6-Core Apple iM...
Amazon has Apple’s 2020 27″ 5K 6-Core iMacs on sale for $200-$300 off MSRP as part of their Prime Day 2021 sales. Their prices are the lowest available for these 27″ iMacs from any Apple reseller.... Read more
Amazon Prime Day 2021 Deal: Get one of Apple’...
Amazon has Apple 10.9″ iPad Airs on sale for up to $90 off MSRP as part of their Prime Day 2021 deals, each including free shipping. Sale price varies by color, as indicated below: – 10.9″ 64GB WiFi... Read more
Apple launches 2021 Back to School promotion:...
Apple has launched their Back to School promotion for 2021. As part of this promotion, Apple will include one free pair AirPods (with charging case) with the purchase of a MacBook Air, MacBook Pro,... Read more

Jobs Board

*Apple* iOS Administrator - Leidos (United S...
Description Job Description: Leidos has an immediate need for an Apple iOS Administrator. The selected candidate will assist SSA with providing Apple iOS Read more
Geek Squad *Apple* Consultation Professiona...
**811980BR** **Job Title:** Geek Squad Apple Consultation Professional **Job Category:** Store Associates **Store Number or Department:** 002516-Southpark Read more
Relationship Banker - *Apple* Valley Financ...
Relationship Banker - Apple Valley Financial Center - Minnesota Market - Apple Valley, MN APPLE VALLEY, Minnesota **Job Description:** At Bank of America, we Read more
Senior Software Developer - *Apple* (iOS/tv...
**SUMMARY** Hulu's Apple team is seeking an experienced Senior Software Engineer with a passion for mobile applications to join our team in Seattle. Our highly Read more
Geek Squad Advanced Repair *Apple* Professi...
**811751BR** **Job Title:** Geek Squad Advanced Repair Apple Professional **Job Category:** Store Associates **Store Number or Department:** 000449-Auburn Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.