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

Macs Fan Control 1.5.14 - Monitor and co...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more
VueScan 9.7.96 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
FileMaker Pro 19.6.1 - Quickly build cus...
FileMaker Pro is the tool you use to create a custom app. You also use FileMaker Pro to access your app on a computer. Start by importing data from a spreadsheet or using a built-in Starter app to... Read more
Duet 3.1.0.0 - Use your iPad as an exter...
Duet is the first app that allows you to use your iDevice as an extra display for your Mac using the Lightning or 30-pin cable. Note: This app requires a iOS companion app. Release notes were... Read more
Firefox 107.0.1 - Fast, safe Web browser...
Firefox offers a fast, safe Web browsing experience. Browse quickly, securely, and effortlessly. With its industry-leading features, Firefox is the choice of Web development professionals and casual... Read more
War Thunder 2.21.1.91 - Multiplayer war...
In War Thunder, aircraft, attack helicopters, ground forces and naval ships collaborate in realistic competitive battles. You can choose from over 1,500 vehicles and an extensive variety of combat... Read more
Numbers 12.2.1 - Apple's spreadshee...
With Apple Numbers, sophisticated spreadsheets are just the start. The whole sheet is your canvas. Just add dramatic interactive charts, tables, and images that paint a revealing picture of your data... Read more
DEVONthink Pro 3.8.7 - Knowledge base, i...
DEVONthink is DEVONtechnologies' document and information management solution. It supports a large variety of file formats and stores them in a database enhanced by artificial intelligence (AI). Many... Read more
Drive Genius 6.2.3 - $79.00
Drive Genius features a comprehensive Malware Scan. Automate your malware protection. Protect your investment from any threat. The Malware Scan is part of the automated DrivePulse utility. DrivePulse... Read more
VLC Media Player 3.0.18 - Popular multim...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more

Latest Forum Discussions

See All

TouchArcade Game of the Week: ‘Sling Min...
The world of PC games has always blown my mind because there’s just SO MUCH stuff out there that it’s not uncommon at all for there to be a game that’s well-liked and well-reviewed, and seemingly quite popular with a solid fanbase, and have it be... | Read more »
SwitchArcade Round-Up: Reviews Featuring...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 2nd, 2022. So, today turned out a little quieter than the usual Friday. It was so quiet, in fact, that I decided to pen a few reviews. The Knight Witch, Railbound, and Donut... | Read more »
Blue Archive reveals its latest event st...
Nexon has announced the new update for Blue Archive, under the name of An Unconcealed Heart. Featuring a battle between two academies, the story will follow a group struggling to gain recognition, and will bring three new students to recruit. [... | Read more »
Dead Cells+ Is Out Now on Apple Arcade a...
Following the major update for Dead Cells on iOS and Android a few days ago, Playdigious has brought Dead Cells+ () to Apple Arcade. As an App Store Great, Dead Cells+ includes all prior paid DLC and content updates. It also has exclusive mobile... | Read more »
SwitchArcade Round-Up: ‘Romancing SaGa’,...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 1st, 2022. Wow, December. We’re already at the last month of the year? Phew. I have a lot of work to finish in the next few weeks. As for today, we’ve got a little news, a... | Read more »
‘Railbound’ Update Now Available Adding...
One of our favorite puzzlers released this year is Railbound from Afterburn Games, which hit in early September and earned our Game of the Week recognition for being an absolutely ace logic puzzler. The goal is to place rail pieces down in order to... | Read more »
The Seven Deadly Sins: Grand Cross celeb...
Netmarble Corporation has pulled out all the stops to celebrate the 3 and a half year anniversary of The Seven Deadly Sins: Grand Cross. The Grand Cross 3.5th Year Anniversary the Ultimate One, a rather wordy title, brings with it a brand new... | Read more »
‘Skullgirls Mobile’ Major Update 5.2 Out...
Developer Hidden Variable pushed out a major update for Skullgirls Mobile (Free) a few hours ago. The version 5.2 update brings in Black Dahlia (before the console and PC game), Retakes, XP Treats, free gifts, and more. Since launch, Skullgirls... | Read more »
Out Now: ‘Disgaea 4’, ‘Romancing SaGa: M...
Each and every day new mobile games are hitting the App Store, and so each week we put together a big old list of all the best new releases of the past seven days. Back in the day the App Store would showcase the same games for a week, and then... | Read more »
SwitchArcade Round-Up: ‘Elevator Action...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for November 30th, 2022. We’re finishing up the month on a quiet note, friends. There are five new releases to look at today, with a few notables amongst them. We’ve got summaries for... | Read more »

Price Scanner via MacPrices.net

Holiday Sale: Apple AirPods Pro for only $199...
Amazon has new 2022 AirPods Pro in stock and on sale for $199.99 shipped as part of their Holiday sale. Their price is $50 off Apple’s MSRP, equaling their Black Friday price, and it’s the lowest... Read more
New Holiday Sale: Apple retailers are offerin...
Several Apple retailers lowered prices on 10.9″ iPad Airs overnight to lows of $100 off MSRP starting at $499. Their prices are the lowest available for iPad Airs anywhere this Holiday season right... Read more
New Holiday sale at Amazon: Take $50 off Appl...
Amazon has Apple’s new 10th-generation iPads in stock and on sale, for the first time, for $50 off MSRP starting at only $399. Their discount applies to all models and all colors. With the discount,... Read more
Holiday Sale: Get an 8.3″ Apple iPad mini for...
Sams Club has 10.9″ 64GB iPad minis on Holiday sale for $80-$100 off MSRP through December 7, 2022. With their discount, prices start at $399 — the cheapest price for a new iPad mini from any of the... Read more
Sams Club Holiday December Event sale: Apple...
Apple AirPods Max headphones are on sale at Sams Club for $110 off MSRP ($439) as part of their December Event sale, ending on December 7, 2022, valid for all colors. Sale price for online orders... Read more
Apple’s 10.2″ 64GB 9th-generation iPads are o...
Sams Club has 9th-generation 64GB iPads on Holiday sale for $60 off MSRP through December 7, 2022. With their discount, prices start at $259 — the cheapest price for a new iPad from any of the Apple... Read more
11″ 128GB WiFi M2 iPad Pro on sale for $749,...
B&H Photo has the new 11″ 128GB WiFi M2-powered iPad Pro (in Space Gray or Silver) on Holiday sale for $749 including free 1-2 day shipping to most US addresses. Their price is $50 off MSRP and... Read more
Find the best Holiday sale price on an iPad u...
We’ve updated our iPad Price Trackers with the latest information on the new 10th-generation iPads, M2-powered iPad Pros, M1 iPad Airs, iPad minis, and 9th generation iPads from Apple’s authorized... Read more
Apple retailers are offering $100-$150 Holida...
Apple retailers have posted their most-recent Holiday sale prices on 13″ MacBook Airs. Take up to $150 off MSRP on M2-powered Airs with these sales with prices starting at only $1099. Free shipping... Read more
Holiday Sale: Apple’s 14″ MacBook Pros with M...
B&H Photo is offering $200-$300 discounts on Apple’s 14″ MacBook Pros with M1 Pro CPUs as part of their Holiday 2022 sale, with prices starting at $1799. Free 1-2 day shipping is available to... Read more

Jobs Board

Support Technician II - *Apple* Support - O...
…problems and acting as a liaison between customers and resolving groups. As an Apple Technical Specialist, you will be supporting many of our popular Apple Read more
*Apple* Electronic Repair Technician - PlanI...
…a highly motivated individual to join our Production Department as an Apple Electronic Repair Technician. The computer repair technician will diagnose, assemble, Read more
Lead Developer - *Apple* tvOS - Rumble (Uni...
…earnings, and positive sentiment About the role: We are looking for a Lead Apple tvOS Developer to join our application engineering team to expand our video centric Read more
Tier 1 Endpoint Engineer - *Apple* - Red Ri...
…Desk on site, at our Client's location, with a focus on support to Apple products. This position will handle technical support requests directly from customers and Read more
Product Manager II - *Apple* - DISH (United...
…you will be doing We seek an ambitious, data-driven thinker to assist the Apple Product Development team as our new Retail Wireless division continues to grow and Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.