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

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

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


Community Search:
MacTech Search:

Software Updates via MacUpdate

Markly 1.5.3 - Create measurement and de...
Markly is a measurement and design-spec plugin/extension for Photoshop and Sketch. It is made for modern Web designers and app front-end developers. You can add specification marks simply by clicking... Read more
Suitcase Fusion 6 17.3.0 - Font manageme...
Suitcase Fusion 6 is the creative professional's font manager. Every professional font manager should deliver the basics: spectacular previews, powerful search tools, and efficient font organization... Read more
Nisus Writer Pro 2.1.2 - Multilingual wo...
Nisus Writer Pro is a powerful multilingual word processor, similar to its entry level products, but brings new features such as table of contents, indexing, bookmarks, widow and orphan control,... Read more
calibre 2.40.0 - Complete e-book library...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital librarian... Read more
Vivaldi - An advanced browser...
Vivaldi is a browser for our friends. In 1994, two programmers started working on a web browser. Our idea was to make a really fast browser, capable of running on limited hardware, keeping in mind... Read more
OmniPlan 3.0 - Robust project management...
With OmniPlan, you can create logical, manageable project plans with Gantt charts, schedules, summaries, milestones, and critical paths. Break down the tasks needed to make your project a success,... Read more
Yummy FTP 1.11 - FTP/SFTP/FTPS client fo...
Yummy FTP is an FTP + SFTP + FTPS file transfer client which focuses on speed, reliability and productivity. Whether you need to transfer a few files or a few thousand, schedule automatic backups, or... Read more
Tweetbot 2.1 - Popular Twitter client. (...
Tweetbot is a full-featured OS X Twitter client with a lot of personality. Whether it's the meticulously-crafted interface, sounds and animation, or features like multiple timelines and column views... Read more
MacPilot 8.0 - Enable over 1,200 hidden...
MacPilot gives you the power of UNIX and the simplicity of Macintosh, which means a phenomenal amount of untapped power in your hands! Use MacPilot to unlock over 1,200 features, and access them all... Read more
Typinator 6.7 - Speedy and reliable text...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more

Balloony Land offers a fresh twist on th...
Balloony Land by Palringo offers a fresh twist on the match three genre and is out now on iOS and Android. First-off, you'll be popping balloons instead of crushing candy and the balloons will float up and fill the empty spaces instead of dropping... | Read more »
Graphic - vector illustration and design...
Graphic - vector illustration and design 1.0 Device: iOS iPhone Category: Productivity Price: $2.99, Version: 1.0 (iTunes) Description: Autodesk Graphic is a powerful full-featured vector drawing and illustration application right in... | Read more »
Sago Mini Babies (Education)
Sago Mini Babies 1.0 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0 (iTunes) Description: Introducing the Sago Mini babies. Boys and girls love caring for these adorable characters. Feed Robin her favorite mush... | Read more »
PAUSE - Relaxation at your fingertip (H...
PAUSE - Relaxation at your fingertip 1.1 Device: iOS iPhone Category: Healthcare & Fitness Price: $1.99, Version: 1.1 (iTunes) Description: | Read more »
Super Sharp (Games)
Super Sharp 1.1 Device: iOS Universal Category: Games Price: $1.99, Version: 1.1 (iTunes) Description: Your finger has never been so sharp! Cut with skill to complete the 120 ingenious physics levels of Super Sharp and become a cut... | Read more »
Assembly - Graphic design for everyone...
Assembly - Graphic design for everyone 1.0 Device: iOS Universal Category: Photography Price: $2.99, Version: 1.0 (iTunes) Description: Assembly is the easiest most powerful design tool on the App Store. Create anything you can... | Read more »
Dub Dash (Games)
Dub Dash 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: ARE YOU READY FOR THE ULTIMATE CHALLENGE? UNIQUE SYMBIOSIS OF MUSIC AND GRAPHICS | Read more »
Leave Me Alone (Games)
Leave Me Alone 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: 33% off launch sale!!! Somewhere between the 1980s and 1990s there exists a world that never was. A world of skatepunks,... | Read more »
YAMGUN (Games)
YAMGUN 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: The invasion has begun! Protect the walls of the citadel against waves of enemies! But watch out, you will soon run out of ammo...... | Read more »
Chesh (Games)
Chesh 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: It’s like chess, only not at all. ***40% off for a limited time to celebrate our launch!*** Chesh is a game of skill, strategy, luck,... | Read more »

Price Scanner via

TP-LINK Next-Gen Routers Support a Large Numb...
TP-LINK, specialists in consumer and business networking products, have announced the availability of Archer C2600, the company’s next-generation router featuring wireless AC, multi-user MIMO, and 4-... Read more
Apple’s Education discount saves up to $300 o...
Purchase a new Mac or iPad using Apple’s Education Store and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free, and... Read more
Save up to $350 with Apple refurbished iMacs
Apple has Certified Refurbished iMacs available for up to $350 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 27″ 3.5GHz 5K iMac – $1949 $350 off MSRP - 27... Read more
Mac Pros on sale for up to $300 off MSRP
B&H Photo has Mac Pros on sale for up to $300 off MSRP. Shipping is free, and B&H charges sales tax in NY only: - 3.7GHz 4-core Mac Pro: $2818.99, $181 off MSRP - 3.5GHz 6-core Mac Pro: $3699... Read more
5K iMacs on sale for up to $150 off MSRP, fre...
B&H Photo has the 27″ 3.3GHz 5K iMac on sale for $1899.99 including free shipping plus NY tax only. Their price is $100 off MSRP. They have the 27″ 3.5GHz 5K iMac on sale for $2149, $150 off MSRP... Read more
Twelve South Redesigns BookArc For Today’s Sm...
Twelve South has announced a redesigned version of their very first product, BookArc for MacBook. Tailored specifically for the newest generation of MacBooks, BookArc holds the new, smaller Apple... Read more
Phone 6s Tips & Tricks – Tips Book For iP...
Poole, United Kingdom based Tap Guides Ltd. has announced the release and immediate availability of iPhone 6s Tips & Tricks, an in-depth eBook available in the iBookstore that’s priced just $2.99... Read more
Apple refurbished 2014 13-inch Retina MacBook...
Apple has Certified Refurbished 2014 13″ Retina MacBook Pros available for up to $400 off original MSRP, starting at $979. An Apple one-year warranty is included with each model, and shipping is free... Read more
13-inch 2.5GHz MacBook Pro on sale for $994,...
Best Buy has the 13″ 2.5GHz MacBook Pro available for $994.99 on their online store. Choose free shipping or free instant local store pickup (if available). Their price is $105 off MSRP. Price valid... Read more
Is The iPad Pro Really A Serious Laptop Repla...
Probably not, at least for productive professionals and other power users. Steve Jobs declared that we’d entered the “post-PC Era” with the advent of the original iPad in 2010, a phrase we don’t hear... Read more

Jobs Board

*Apple* Desktop Analyst - KDS Staffing (Unit...
…work with some of the brightest engineers. Job Description Title: Apple Desktop AnalystPosition Type: Full-time PermanentLocation: White Plains, NYHot Points:Depth of Read more
*Apple* Retail Online, Customer Experience R...
**Job Summary** Apple Retail's Online Store sells Apple products to customers around the world. In addition to selling Apple products with unique services such Read more
Frameworks Engineer, *Apple* Watch - Apple...
**Job Summary** Join the team that is shaping the future of software development for Apple Watch! As a software engineer on the Apple Watch Frameworks team you will Read more
Senior Manager, Global Direct Marketing *App...
**Job Summary** Apple Retail is looking for an experienced Direct Marketing Leader to join its Marketing team. This position will take a leadership role in creating Read more
*Apple* Online Store Expansion - Apple (Unit...
**Job Summary** The Online Apple Store is seeking a person to lead its expansion into new countries. Based in Cupertino, CA, this person will develop and maintain an Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.