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

Capto 1.2.9 - $29.99
Capto (was Voila) is an easy-to-use app that takes capturing, recording, video and image editing to the next level. With an intelligent file manager and quick sharing options, Capto is perfect for... Read more
Opera 51.0.2830.40 - 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
GarageSale 7.0.13 - Create outstanding e...
GarageSale is a slick, full-featured client application for the eBay online auction system. Create and manage your auctions with ease. With GarageSale, you can create, edit, track, and manage... Read more
1Password 6.8.7 - Powerful password mana...
1Password is a password manager that uniquely brings you both security and convenience. It is the only program that provides anti-phishing protection and goes beyond password management by adding Web... Read more
Evernote 7.0.1 - Create searchable notes...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
MacUpdate Desktop 6.2.0 - $20.00
MacUpdate Desktop brings seamless 1-click app installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on... Read more
HoudahSpot 4.3.5 - Advanced file-search...
HoudahSpot is a versatile desktop search tool. Use HoudahSpot to locate hard-to-find files and keep frequently used files within reach. HoudahSpot will immediately feel familiar. It works just the... Read more
EtreCheck 4.0.4 - 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
WhatsApp 0.2.8361 - Desktop client for W...
WhatsApp is the desktop client for WhatsApp Messenger, a cross-platform mobile messaging app which allows you to exchange messages without having to pay for SMS. WhatsApp Messenger is available for... Read more
iClock 4.2 - Customize your menubar cloc...
iClock is a menu-bar replacement for Apple's default clock but with 100x features. Have your Apple or Google calendar in the menubar. Have the day, date, and time in different fonts and colors in the... Read more

Latest Forum Discussions

See All

The best games like Florence
Florence is a great little game about relationships that we absolutely adored. The only problem with it is it's over a little too soon. If you want some other games with some emotional range like Florence, check out these suggestions: [Read more] | Read more »
Angry Birds Champions adds cash prizes t...
Collaborating with developer Rovio Entertainment, GSN Games has released a twist on the Angry Birds formula. Angry Birds Champions features the same bird-flinging gameplay, but now you can catapult Red and co for cash. | Read more »
Around the Empire: What have you missed...
148Apps is part of a family. A big family of sites that make sure you're always up to date with all the portable gaming news. Just like a real family, I guess. I don't know, my mum never told me anything about Candy Crush to be fair. [Read more] | Read more »
The Battle of Polytopia Guide - Tips for...
The addition of multiplayer to The Battle of Polytopia has catapulted the game from a fun enough time waster to a fully-fledged 4X experience on your phone. We've been playing quite a few matches over the past week or so, and we've put together a... | Read more »
All the best games on sale for iPhone an...
Hi there, and welcome to our round up of all the best games that are on sale for iOS at the moment. It's not a vintage week in terms of numbers, but I'm pretty sure that every single one of these is worth picking up if you haven't already played... | Read more »
Disc Drivin' 2 Guide - Tips for the...
We're all still playing quite a bit of Disc Drivin' 2 over here at 148Apps, and we've gotten pretty good at it. Now that we've spent some more time with the game and unlocked more powerups, check out some of these more advanced tips: | Read more »
Alto's Odyssey Guide - How to Tackl...
Alto’s Odyssey is a completely stunning and serene runner, but it can also be a bit tricky. Check out these to try and keep your cool while playing this endless runner: Don’t focus too much on tasks [Read more] | Read more »
Here's everything you need to know...
Alto's Odyssey is a really, really good game. If you don't believe me, you should definitely check out our review by clicking this link right here. It takes the ideas from the original Alto's Adventure, then subtly builds on them, creating... | Read more »
Alto's Odyssey (Games)
Alto's Odyssey 1.0.1 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.1 (iTunes) Description: Just beyond the horizon sits a majestic desert, vast and unexplored. Join Alto and his friends and set off on an endless... | Read more »
Vainglory 5v5: Everything you need to kn...
Vainglory just got bigger. [Read more] | Read more »

Price Scanner via MacPrices.net

Use your Apple Education discount and save up...
Purchase a new Mac using Apple’s Education discount, and take up to $400 off MSRP. All teachers, students, and staff of any educational institution with a .edu email address qualify for the discount... Read more
Apple Canada offers 2017 21″ and 27″ iMacs fo...
 Canadian shoppers can save up to $470 on the purchase of a 2017 current-generation 21″ or 27″ iMac with Certified Refurbished models at Apple Canada. Apple’s refurbished prices are the lowest... Read more
9″ iPads available online at Walmart for $50...
Walmart has 9.7″ Apple iPads on sale for $50 off MSRP for a limited time. Sale prices are for online orders only, in-store prices may vary: – 9″ 32GB iPad: $279.99 $50 off – 9″ 128GB iPad: $379.99 $... Read more
15″ Apple MacBook Pros, Certified Refurbished...
Save $360-$420 on the purchase of a 2017 15″ MacBook Pro with Certified Refurbished models at Apple. Apple’s refurbished prices are the lowest available for each model from any reseller. An standard... Read more
Amazon restocks MacBook Pros with models avai...
Amazon has restocked 15″ and 13″ Apple MacBook Pros with models on sale for up to $251 off MSRP. Shipping is free. Note that stock of some Macs may come and go (and some sell out quickly), so check... Read more
Lowest price of the year: 15″ 2.8GHz Apple Ma...
Amazon has the 2017 Space Gray 15″ 2.8GHz MacBook Pro on sale today for $251 off MSRP. Shipping is free: – 15″ 2.8GHz Touch Bar MacBook Pro Space Gray (MPTR2LL/A): $2148, $251 off MSRP Their price is... Read more
Apple restocks full line of Certified Refurbi...
Apple has restocked a full line of Apple Certified Refurbished 2017 13″ MacBook Pros for $200-$300 off MSRP. A standard Apple one-year warranty is included with each MacBook, and shipping is free.... Read more
Lowest sale price available for 13″ 1.8GHz Ma...
Focus Camera has the 2017 13″ 1.8GHz/128GB Apple MacBook Air on sale today for $829 including free shipping. Their price is $170 off MSRP, and it’s the lowest price available for a current 13″... Read more
21-inch 2.3GHz iMac on sale for $999, $100 of...
B&H Photo has the 2017 21″ 2.3GHz iMac (MMQA2LL/A) in stock and on sale for $999 including free shipping plus NY & NJ tax only. Their price is $100 off MSRP. Read more
Apple refurbished Mac minis in stock again st...
Apple has restocked Certified Refurbished Mac minis starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: – 1.4GHz Mac mini: $419 $80 off MSRP – 2.6GHz Mac... Read more

Jobs Board

*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
*Apple* Solutions Consultant - Apple (United...
# Apple Solutions Consultant Job Number: 113523441 Orange, CA, California, United States Posted: 21-Feb-2018 Weekly Hours: 40.00 **Job Summary** Are you passionate 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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.