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

ffWorks 1.0.6 - Convert multimedia files...
ffWorks (was iFFmpeg), focused on simplicity, brings a fresh approach to the use of FFmpeg, allowing you to create ultra-high-quality movies without the need to write a single line of code on the... Read more
Adobe Acrobat 18.011.20035 - Powerful PD...
Acrobat DC is available only as a part of Adobe Creative Cloud, and can only be installed and/or updated through Adobe's Creative Cloud app. Adobe Acrobat DC with Adobe Document Cloud services is... Read more
Adobe Acrobat Reader 18.011.20035 - View...
Adobe Acrobat Reader allows users to view PDF documents. You may not know what a PDF file is, but you've probably come across one at some point. PDF files are used by companies and even the IRS to... Read more
EtreCheck 4.0.3 - For troubleshooting yo...
EtreCheck is an app that displays the important details of your system configuration and allow you to copy that information to the Clipboard. It is meant to be used with Apple Support Communities to... Read more
Yummy FTP Pro 2.0 - $29.99
Yummy FTP Pro is an advanced Mac file transfer app which provides a full-featured professional toolkit combined with blazing speeds and impeccable reliability, so whether you want to transfer a few... Read more
Opera 51.0.2830.34 - High-performance We...
Opera is a fast and secure browser trusted by millions of users. With the intuitive interface, Speed Dial and visual bookmarks for organizing favorite sites, news feature with fresh, relevant content... Read more
Apple iOS 11.2.6 - The latest version of...
iOS 11 sets a new standard for what is already the world’s most advanced mobile operating system. It makes iPhone better than before. It makes iPad more capable than ever. And now it opens up both to... Read more
Google Chrome 64.0.3282.167 - Modern and...
Google Chrome is a Web browser by Google, created to be a modern platform for Web pages and applications. It utilizes very fast loading of Web pages and has a V8 engine, which is a custom built... Read more
Adobe Photoshop CC 2018 19.1.1 - Profess...
Photoshop CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Photoshop customer). Adobe Photoshop CC 2018, the industry standard... Read more
Apple iOS 11.2.6 - The latest version of...
iOS 11 sets a new standard for what is already the world’s most advanced mobile operating system. It makes iPhone better than before. It makes iPad more capable than ever. And now it opens up both to... Read more

Latest Forum Discussions

See All

Check out these 5 games that are a lot l...
So you're in love with Minecraft, but you're looking for something else to play as well? You've come to the right place then, because this list is all about games that are a bit like Minecraft. Some of them, more than others. [Read more] | Read more »
Our top 5 characters from casual RPG Cre...
Creature Quest definitely lives up to its name with a host of collectible creatures based on fantasy tales and world mythologies. To celebrate Creature Quest’s first birthday, we’re going to lay out what we think are the five best characters in the... | Read more »
Around the Empire: What have you missed...
Did you know that Steel Media has a whole swathe of other sites dedicated to all aspects of mobile gaming? Sure you'll get the very best iPhone news, reviews, and opinions right here at 148Apps, but we don't want you missing out on a single piece... | Read more »
All the best games on sale for iPhone an...
Oh hi there, and welcome to our round-up of the best games that are currently on sale for iPhone and iPad. You thought I didn't see you there, did you, skulking behind the bushes? Trust me though, the bushes aren't where the best deals are. The... | Read more »
The Battle of Polytopia Guide - How to H...
A new update just released for The Battle of Polytopia (formerly Super Tribes), which introduces online multiplayer. For all the fans of Midjiwan’s lite take on Civilization, this is certainly welcome news, but playing online isn’t as easy and... | Read more »
Here are the very best mobile games to p...
It's Valentine's Day! Did you get loads of cards and chocolates and other tacky, simple expressions of human affection? Did you send out tat because you find it almost impossible to express emotion unless there's a section dedicated to it at your... | Read more »
Florence (Games)
Florence 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Florence is an interactive storybook from the award-winning lead designer of Monument Valley about the heart-racing highs and... | Read more »
Purrfect Date (Games)
Purrfect Date 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Cats are a lil’ like marmite. Either you absolutely head-over-heels love’ em, or… nahhh, who are we kidding?! Everyone... | Read more »
More monsters to collect and evolve in C...
A laid-back mix of RPG and TCG, Creature Quest is all about building your deck, evolving your creatures and winning in battle. It’s the creation of VC Mobile, set up by Might and Magic producer Jon Van Caneghem. There are elements of that classic... | Read more »
Check out this awesome hands-on with the...
Well, PlayerUnknown's Battlegrounds has come out on mobile. This isn't a clone, this isn't a riff on the battleroyale mechanics of the game, it's the official mobile port by Tencent. But there's a little bit of a hitch. [Read more] | Read more »

Price Scanner via MacPrices.net

Save up to $350 with these Apple Certified Re...
Apple has a full line of Certified Refurbished iMacs available for up to $350 off original MSRP. Apple’s one-year warranty is standard, and shipping is free. The following models are available: – 27... Read more
B&H offers $200 discount on Silver 15″ Ma...
B&H Photo has Silver 15″ Apple MacBook Pros on sale for $200 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 15″ 2.8GHz Touch Bar MacBook Pro Silver (... Read more
12″ Apple iPad Pro Sale of the Year! Models u...
B&H Photo has 12″ #iPad Pros on sale for up to $150 off MSRP. Shipping is free, and B&H charges sales tax in NY & NJ only: – 12″ 64GB WiFi iPad Pro: $719 $80 off MSRP – 12″ 256GB WiFi... Read more
Deals on 32GB 9″ iPads: Up to $50 off MSRP, s...
B&H Photo has 2017 9.7″ 32GB iPads on sale for $299 including free shipping plus NY & NJ sales tax only. Their price is $30 off MSRP, and it’s currently the lowest price available for these... Read more
15″ 2.2GHz Retina MacBook Pro available for o...
Apple has Certified Refurbished 15″ 2.2GHz Retina MacBook Pros available for $1699. That’s $300 off MSRP for this model, and it’s the lowest price available for a 15″ MacBook Pro currently offered by... Read more
13″ 3.1GHz/256GB Silver Touch Bar MacBook Pro...
Amazon has the Silver 13″ 3.1GHz/256GB Touch Bar MacBook Pro (MPXX2LL/A) on sale for $1649.99 including free shipping. Their price is $150 off MSRP, and it’s the lowest price available for a new 13″... Read more
Saturday Sale: Amazon offers 13″ 1.8GHz/256GB...
Amazon has the 13″ 1.8GHz/256B Apple MacBook Air on sale today for $250 off MSRP including free shipping: – 13″ 1.8GHz/256GB MacBook Air (MQD42LL/A): $949.99, $250 off MSRP Their price is the lowest... Read more
Roundup of Apple Certified Refurbished 12″ Ma...
Apple has Certified Refurbished 2017 12″ Retina MacBooks available for $200-$240 off the cost of new models. Apple will include a standard one-year warranty with each MacBook, and shipping is free.... Read more
Apple offers Certified Refurbished 10″ and 12...
Apple is now offering Certified Refurbished 2017 10″ and 12″ iPad Pros for $100-$190 off MSRP, depending on the model. An Apple one-year warranty is included with each model, and shipping is free: –... Read more
Apple Canada offers Certified Refurbished Mac...
 Canadian shoppers can save up to $560 on the purchase of a 2017 current-generation MacBook Pro, MacBook, or MacBook Air with Certified Refurbished models at Apple Canada. Apple’s refurbished prices... Read more

Jobs Board

*Apple* Store Leader - Retail District Manag...
Job Description:Job SummaryAs more and more people discover Apple , they visit our retail stores seeking ways to incorporate our products into their lives. It's your Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.