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

A Better Finder Rename 10.00b1 - File, p...
A Better Finder Rename is the most complete renaming solution available on the market today. That's why, since 1996, tens of thousands of hobbyists, professionals and businesses depend on A Better... Read more
CrossOver 14.1.6 - Run Windows apps on y...
CrossOver can get your Windows productivity applications and PC games up and running on your Mac quickly and easily. CrossOver runs the Windows software that you need on Mac at home, in the office,... Read more
Printopia 2.1.14 - Share Mac printers wi...
Run Printopia on your Mac to share its printers to any capable iPhone, iPad or iPod Touch. Printopia will also add virtual printers, allowing you to save print-outs to your Mac and send to apps.... Read more
Google Drive 1.24 - File backup and shar...
Google Drive is a place where you can create, share, collaborate, and keep all of your stuff. Whether you're working with a friend on a joint research project, planning a wedding with your fiancé, or... Read more
Chromium 45.0.2454.85 - Fast and stable...
Chromium is an open-source browser project that aims to build a safer, faster, and more stable way for all Internet users to experience the web. Version 45.0.2454.85: Note: Does not contain the "... Read more
OmniFocus 2.2.5 - GTD task manager with...
OmniFocus helps you manage your tasks the way that you want, freeing you to focus your attention on the things that matter to you most. Capturing tasks and ideas is always a keyboard shortcut away in... Read more
iFFmpeg 5.7.1 - Convert multimedia files...
iFFmpeg is a graphical front-end for FFmpeg, a command-line tool used to convert multimedia files between formats. The command line instructions can be very hard to master/understand, so iFFmpeg does... Read more
VOX 2.6 - Music player that supports man...
VOX is a beautiful music player that supports many filetypes. 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... Read more
Box Sync 4.0.6567 - Online synchronizati...
Box Sync gives you a hard-drive in the Cloud for online storage. Note: You must first sign up to use Box. What if the files you need are on your laptop -- but you're on the road with your iPhone? No... Read more
Carbon Copy Cloner 4.1.4 - Easy-to-use b...
Carbon Copy Cloner backups are better than ordinary backups. Suppose the unthinkable happens while you're under deadline to finish a project: your Mac is unresponsive and all you hear is an ominous,... Read more

You Can Play Madfinger Games' Unkil...
Madfinger Games - probably best known for the Dead Trigger series - has officially launched their newest zombie shooter (that isn't called Dead Trigger), named Unkilled. [Read more] | Read more »
KORG iELECTRIBE for iPhone (Music)
KORG iELECTRIBE for iPhone 1.0.1 Device: iOS iPhone Category: Music Price: $9.99, Version: 1.0.1 (iTunes) Description: ** 50% OFF Special Launch Sale - For a Limited Time **The ELECTRIBE reborn in an even smaller form A full-fledged... | Read more »
I am Bread (Games)
I am Bread 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: ‘I am Bread’ is the latest quirky adventure from the creators of 'Surgeon Simulator', Bossa Studios. This isn't the best thing... | Read more »
Rock(s) Rider - HD Edition (Games)
Rock(s) Rider - HD Edition 1.0.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.0 (iTunes) Description: *** PLEASE NOTE: Compatible with iPhone 4s, iPad 2, iPad mini, iPod touch (5th generation) or newer *** Do you... | Read more »
Rebuild 3: Gangs of Deadsville (Games)
Rebuild 3: Gangs of Deadsville 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: It's been a few years since the zombpocalypse turned the world's cities into graveyards and sent the few... | Read more »
Power Ping Pong (Games)
Power Ping Pong 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Do you wield your bat with zen-like focus or do your balls of fury give you a killer spin? Table tennis goes mobile with a... | Read more »
Z.O.N.A Project X (Games)
Z.O.N.A Project X 1.00 Device: iOS Universal Category: Games Price: $1.99, Version: 1.00 (iTunes) Description: Z.O.N.A Project X - shooter in the post-apocalyptic world. | Read more »
Trick Shot (Games)
Trick Shot 1.0.6 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0.6 (iTunes) Description: A game where all you have to do is throw a ball into a box, simple? Trick Shot is a minimalist physics puzzler with 90 levels... | Read more »
VoxelCity (Games)
VoxelCity 1.0.2 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0.2 (iTunes) Description: Looking for a new city builder? Tired of social media anti-games with no strategy? Look no further! NO IAP EVER! VoxelCity is a... | Read more »
Goat Simulator MMO Simulator (Games)
Goat Simulator MMO Simulator 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: ** IMPORTANT - SUPPORTED DEVICESiPhone 4S, iPad 2, iPod Touch 5 or better.** Coffee Stain Studios brings next-gen... | Read more »

Price Scanner via MacPrices.net

Near-Office Input Functionality Virtually Any...
Today Logitech introduced the Logitech K380 Multi-Device Bluetooth Keyboard and the Logitech M535 Bluetooth Mouse, giving users the freedom to work on any device, most anywhere. According to... Read more
College Student Deals: Additional $100 off Ma...
Take an additional $100 off all MacBooks and iMacs at Best Buy Online with their College Students Deals Savings, valid through September 4, 2015. Anyone with a valid .EDU email address can take... Read more
Will You Buy An iPad Pro? – The ‘Book Mystiqu...
It looks like we may not have to wait much longer to see what finally materializes as a new, larger-panel iPad (Pro/Plus?) Usually reliable Apple product prognosticator KGI Securities analyst Ming-... Read more
eFileCabinet Announces SMB Document Managemen...
Electronic document management (EDM) eFileCabinet, Inc., a hosted solutions provider for small to medium businesses, has announced that its SecureDrawer and eFileCabinet Online services will be... Read more
WaterField Designs Unveils American-Made, All...
San Francisco’s WaterField Designs today unveiled their all-leather Cozmo 2.0 — an elegant attach laptop bag with carefully-designed features to suit any business environment. The Cozmo 2.0 is... Read more
Apple’s 2015 Back to School promotion: Free B...
Purchase a new Mac or iPad at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free,... Read more
128GB MacBook Airs on sale for $100 off MSRP,...
B&H Photo has 11″ & 13″ MacBook Airs with 128GB SSDs on sale for $100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 11″ 1.6GHz/128GB MacBook Air: $799.99, $100 off MSRP... Read more
13-inch 2.5GHz MacBook Pro (refurbished) avai...
The Apple Store has Apple Certified Refurbished 13″ 2.5GHz MacBook Pros available for $829, or $270 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.... Read more
27-inch 3.2GHz iMac on sale for $1679, save $...
B&H Photo has the 27″ 3.2GHz iMac on sale for $1679.99 including free shipping plus NY sales tax only. Their price is $120 off MSRP. Read more
Apple and Cisco Partner to Deliver Fast-Lane...
Apple and Cisco have announced a partnership to create a “fast lane” for iOS business users by optimizing Cisco networks for iOS devices and apps. The alliance integrates iPhone with Cisco enterprise... Read more

Jobs Board

*Apple* Desktop Analyst - KDS Staffing (Unit...
…field and consistent professional recruiting achievement. Job Description: Title: Apple Desktop AnalystPosition Type: Full-time PermanentLocation: White Plains, NYHot Read more
Simply Mac *Apple* Specialist- Repair Techn...
Simply Mac is the greatest premier retailer of Apple products expertise in North America. We're looking for dedicated individuals to provide personalized service and Read more
Simply Mac *Apple* Specialist- Service Repa...
Simply Mac is the greatest premier retailer of Apple products expertise in North America. We're looking for dedicated individuals to provide personalized service and Read more
*Apple* Desktop Analyst - KDS Staffing (Unit...
…field and consistent professional recruiting achievement. Job Description: Title: Apple Desktop AnalystPosition Type: Full-time PermanentLocation: White Plains, NYHot Read more
Simply Mac- *Apple* Specialist- Store Manag...
Simply Mac is the largest premier retailer for Apple products and solutions. We're looking for dedicated individuals with a passion to simplify and enhance the Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.