,
Dr. Dobbs J O U R N A L
#364 SEPTEMBER 2004
SOFTWARE TOOLS FOR THE PROFESSIONAL PROGRAMMER
http://www.ddj.com
DISTRIBUTED COMPUTING Grid Computing & The Linda Programming Model
Debugging Distributed Systems SCTP: The Next-Generation TCP?
Bonus Eclipse Coverage
Continuous Integration & .NET
Eclipse & General Purpose Applications Writing Plug-Ins In C/C++ for Eclipse CDT
Version Control, Builds, & Testing
RFID: You Make the Call Al Stevens on
Band-In-A-Box, Finale, & MusicXML Michael Abrash on
Performance Optimization The New Qt Designer IDE Bluetooth & Remote UIs Improving .NET Events Building MFC Dialogs at Runtime
Erich Gamma & Kent Beck on
Contributing To Eclipse
FEATURES
C O N T E N T S
SEPTEMBER 2004 VOLUME 29, ISSUE 9
Grid Computing & the Linda Programming Model 16 by Rob Bjornson and Andrew Sherman
Compared to web services, the Linda programming model provides a number of advantages for building grid apps.
Debugging, Message-Oriented Middleware, & Distributed Systems 26 by Paul Pazandak and Steve Ford
If you’ve built distributed messaging systems, you know about problems with tracking down and isolating bugs.
Stream-Control Transmission Protocol 32 by Ian Barile
The Stream Control Transmission Protocol is a new transport layer protocol that offers an alternative to TCP.
Continuous Integration & .NET: Part II 37 by Thomas Beck
Thomas introduces a complete Continuous Integration solution.
RFID Blocker Tags 42 by Burt Kaliski
Blocker tags let you choose when, where, and what RFID devices are tracking you.
Optimizing Pixomatic for x86 Processors: Part II 46 by Michael Abrash
Michael discusses his greatest performance challenge ever— optimizing an x86 3D software rasterizer.
Band-In-A-Box, Finale, & MusicXML 52 by Al Stevens
Al converts Band-In-A-Box file formats into Finale notation files using MusicXML as a porting medium.
C#, COM Objects, & Interop Services S1 by Shehrzad Qureshi
Shehrzad implements an ActiveX control in both C++ and C#.
Improving .NET Events S6 by Richard Grimes
.NET provides facilities for writing your own event mechanisms — if you know how.
Building MFC Dialogs at Runtime S11 by Adrian Hill
Adrian presents a class for defining MFC-based dialogs.
The Qt Designer IDE 57 by Dave Berton
With Qt Designer 3.3.1, you have a feature-rich IDE for designing and coding GUI applications.
Eclipse & General-Purpose Applications 66
by Todd E. Williams and Marc R. Erickson
Eclipse provides the framework for combining disparate tools into a single integrated application.
Writing Plug-Ins in C/C++ for Eclipse CDT 70
by Doug Schaefer and Sebastien Marineau-Mes
The Eclipse CDT Project delivers a fully functional C/C++ IDE for the Eclipse platform.
Contributing to Eclipse 74
by Kent Beck and Erich Gamma
Eclipse’s plug-in architecture means that every programmer is potentially a toolsmith.
Tools for Domain-Specific Modeling 79 by Steven Kelly
The Eclipse Modeling Framework and Graphical Editor Framework provide a domain-specific modeling solution.
EMBEDDED SYSTEMS Bluetooth & Remote Device User Interfaces 61 by Richard Hoptroff
The FlexiPanel Bluetooth Protocol is a remote UI service for computers, electrical appliances, and other devices.
FORUM EDITORIAL 8 by Jonathan Erickson LETTERS 10 by you DR. ECCO’S OMNIHEURIST CORNER 12 by Dennis E. Shasha NEWS & VIEWS 14 by Shannon Cochran OF INTEREST 94 by Shannon Cochran SWAINE’S FLAMES 96 by Michael Swaine
RESOURCE CENTER As a service to our readers, source code, related files, and author guidelines are available at http:// www.ddj.com/. Letters to the editor, article proposals and submissions, and inquiries can be sent to
[email protected], faxed to 650-513-4618, or mailed to Dr. Dobb’s Journal, 2800 Campus Drive, San Mateo CA 94403. For subscription questions, call 800-456-1215 (U.S. or Canada). For all other countries, call 902-563-4753 or fax 902-563-4807. E-mail subscription questions to ddj@neodata .com or write to Dr. Dobb’s Journal, P.O. Box 56188, Boulder, CO 803226188. If you want to change the information you receive from CMP and others about products and services, go to http://www.cmp .com/feedback/permission.html or contact Customer Service at the address/number noted on this page. Back issues may be purchased for $9.00 per copy (which includes shipping and handling). For issue availability, send e-mail to
[email protected], fax to 785838-7566, or call 800-444-4881 (U.S. and Canada) or 785-8387500 (all other countries). Back issue orders must be prepaid. Please send payment to Dr. Dobb’s Journal, 4601 West 6th Street, Suite B, Lawrence, KS 66049-4189. Individual back articles may be purchased electronically at http://www.ddj.com/.
COLUMNS Programming Paradigms 83
Chaos Manor 89
by Michael Swaine
by Jerry Pournelle
Embedded Space 86
Programmer’s Bookshelf 92
by Ed Nisley
by Lynne Greer Jolitz
NEXT MONTH: Intelligent systems are our focus in October.
DR. DOBB’S JOURNAL (ISSN 1044-789X) is published monthly by CMP Media LLC., 600 Harrison Street, San Francisco, CA 94017; 415-905-2200. Periodicals Postage Paid at San Francisco and at additional mailing offices. SUBSCRIPTION: $34.95 for 1 year; $69.90 for 2 years. International orders must be prepaid. Payment may be made via Mastercard, Visa, or American Express; or via U.S. funds drawn on a U.S. bank. Canada and Mexico: $45.00 per year. All other foreign: $70.00 per year. U.K. subscribers contact Jill Sutcliffe at Parkway Gordon 01-49-1875-386. POSTMASTER: Send address changes to Dr. Dobb’s Journal, P.O. Box 56188, Boulder, CO 80328-6188. Registered for GST as CMP Media LLC, GST #13288078, Customer #2116057, Agreement #40011901. INTERNATIONAL NEWSSTAND DISTRIBUTOR: Worldwide Media Service Inc., 30 Montgomery St., Jersey City, NJ 07302; 212-332-7100. Entire contents © 2004 CMP Media LLC. Dr. Dobb’s Journal is a registered trademark of CMP Media LLC. All rights reserved.
http://www.ddj.com
Dr. Dobb’s Journal, September 2004
5
,
Dr.Dobbs J O U R N A L
PUBLISHER Timothy Trickett
SOFTWARE TOOLS FOR THE PROFESSIONAL PROGRAMMER
EDITOR-IN-CHIEF Jonathan Erickson
EDITORIAL MANAGING EDITOR Deirdre Blake MANAGING EDITOR, DIGITAL MEDIA Kevin Carlson SENIOR PRODUCTION EDITOR Monica E. Berg NEWS EDITOR Shannon Cochran ASSOCIATE EDITOR Della Song ART DIRECTOR Margaret A. Anderson SENIOR CONTRIBUTING EDITOR Al Stevens CONTRIBUTING EDITORS Bruce Schneier, Ray Duncan, Jack Woehr, Jon Bentley, Tim Kientzle, Gregory V. Wilson, Mark Nelson, Ed Nisley, Jerry Pournelle, Dennis E. Shasha EDITOR-AT-LARGE Michael Swaine PRODUCTION MANAGER Douglas Ausejo INTERNET OPERATIONS DIRECTOR Michael Calderon SENIOR WEB DEVELOPER Steve Goyette WEBMASTERS Sean Coady, Joe Lucca CIRCULATION SENIOR CIRCULATION MANAGER Cherilyn Olmsted ASSISTANT CIRCULATION MANAGER Shannon Weaver MARKETING/ADVERTISING ASSOCIATE PUBLISHER Brenner Fuller MARKETING DIRECTOR Jessica Hamilton AUDIENCE DEVELOPMENT DIRECTOR Ron Cordek ACCOUNT MANAGERS see page 95 Michael Beasley, Randy Byers, Andrew Mintz, Kristy Mittelholtz SENIOR ART DIRECTOR OF MARKETING Carey Perez DR. DOBB’S JOURNAL 2800 Campus Drive, San Mateo, CA 94403 650-513-4300. http://www.ddj.com/ CMP MEDIA LLC Gary Marshall President and CEO John Day Executive Vice President and CFO Steve Weitzner Executive Vice President and COO Jeff Patterson Executive Vice President, Corporate Sales & Marketing Mike Mikos Chief Information Officer William Amstutz Senior Vice President, Operations Leah Landro Senior Vice President, Human Resources Sandra Grayson Vice President & General Counsel Robert Faletra President, Group Publisher Technology Solutions Vicki Masseria President, Group Publisher Healthcare Media Philip Chapnick Vice President, Group Publisher Applied Technologies Michael Friedenberg Vice President, Group Publisher Information Technology Paul Miller Vice President, Group Publisher Electronics Fritz Nelson Vice President, Group Publisher Network Technology Peter Westerman Vice President, Group Publisher Software Development Media Shannon Aronson Corporate Director, Audience Development Michael Zane Corporate Director, Audience Development Marie Myers Corporate Director, Publishing Services
American Buisness Press
6
Dr. Dobb’s Journal, September 2004
Printed in the USA
http://www.ddj.com
EDITORIAL
A Special Kind of Platform
T
o my way of thinking, every issue of Dr. Dobb’s Journal is something special. But in fact, this issue really is special in its look, feel, and content. As you can tell just by thumbing through the magazine, we’ve changed the paper stock to one that’s softer and less glossy, but easier to read. That’s what we were promised anyway. While a trial press run wasn’t possible, we did pour over other magazines that publish source code on similar paper and felt good about it. We hope you do. too. That’s the “feel” part of the look-and-feel. As for the look part, you’ll also notice that DDJ Art Director Margaret Anderson has been tinkering with the page design, in an effort to make DDJ easier to read. She’s cleaned up the headlines, punched up the pullquotes, and generally cleared the decks. In all likelihood, she’s not yet done, which means you may see more changes in the coming months. In terms of the content, we’re starting something special this month that, to my recollection, DDJ hasn’t done before — launching a multiissue, multiarticle, in-depth examination of a specific topic. In this issue, our special Eclipse coverage includes four articles on various aspects of the platform — a general background by Todd Williams and Marc Erickson (no relation) examining what Eclipse is, an article by Erich Gamma and Kent Beck on how you can participate in the Eclipse Project, one by Doug Schaefer and Sebastien Marineau-Mes on the Eclipse CDT, which delivers a C/C++ IDE for Eclipse, and another by Steven Kelly on the Eclipse Modeling Framework. We’ll continue the series in the October issue with articles on the Eclipse Visual Editor for Java, a plug-in that modifies the Eclipse development environment for ease of use, and refactoring with Eclipse. We’ll then wrap up the series in November by looking at how Eclipse is being used in embedded-systems development, how it is being used as a Rich-Client Platform, and what’s what with EMF, the Eclipse modeling framework. That said, DDJ’s coverage of Eclipse won’t go away with the November issue, however. We will continue covering the platform in subsequent months. So what’s the attraction? Simply put, Eclipse is a powerful open-source IDE built on top of a plug-in architecture. Moreover, Eclipse projects and subprojects are available under the Common Public License, which has been approved by the Open Source Initiative. This royalty-free license lets you use and redistribute Eclipse for both commercial or noncommercial purposes (for licensing details, see http://www.eclipse.org/legal/cpl-v10.html). Finally, with the recent release of Version 3.0, coverage of Eclipse is timely. The 3.0 release is a significant step forward with its focus on the development of a Rich-Client Platform, UI responsiveness, an improved user experience, and tools that go beyond Java source file manipulation. As our Eclipse series rolls out over the coming months, I’ll be curious to know what you think both in terms of the content itself and this broad, in-depth approach. If you’d like more series such as this, let us know— and don’t be afraid to suggest topics you think are worth investigating. Shifting gears, it is interesting how the definition of the term “platform” has, well, shifted. It used to be that “platform” referred to the CPU and/or operating system, as in “a computing platform is the combination of computer hardware and operating-system software that defines a particular computing environment” (http://www.geodyssey.com/tutorial/tapp.html). Along the way, the definition was stretched to include stuff such as an “infrastructure…that gives people and businesses value” (http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=57675). The first thing we knew, Java was categorized as a platform, followed by web browsers, and then IDEs such as Eclipse. More recently, applications and APIs have moved from the realm of “interfaces” to that of “platforms.” eBay, Amazon.com, PayPal, Google, and Yahoo!, among others, are referring to themselves as web-services-based “platforms” that make liberal use of the usual suspects —XML, SOAP, Java, XSLT, HTTP, and the like. In short, it seems the best way to define the word “platform” is simplest — it’s anything that you build on top of. When it’s all said and done, I suppose DDJ is in this sense a special kind of development platform, too. We present algorithms, source code, and the like, and you build systems using that information. Jeez, that sounds too much like marketing. If you don’t mind, I’ll just continue calling DDJ what it is — a magazine, albeit a special one.
Jonathan Erickson editor-in-chief
[email protected] 8
Dr. Dobb’s Journal, September 2004
http://www.ddj.com
LETTERS
, PO S S O BB
are: Cloque, 52,265 secs; FacePerm, 72,204 secs. German Gonzalez-Morris
[email protected]
T
D
2
C
T EN
S
2
Backtracking Algorithms Dear DDJ, In regard to Timothy Rolfe’s article “Backtracking Algorithms” (DDJ, May 2004), I found another discard rule to insert in the algorithm, doing the first algorithm (Cloque.java) as good (or better) than the second one (FacePerm.java). This new rule sums the complement of the numbers used, then divides by 3 (to get the triplets) the numbers left, then this result divides the sum, thus if the last result is bigger than the allowed value, it discards the rest. For instance, assume we are calculating 12 numbers and 21 as boundary if we are beginning our search having 1, 2, and 3 at the first positions face[0,1,2], we can sum and the complement will be 72 then divide the numbers left 9 by 3 (always three because it is a triplet —>9/3=3) then this new result divides 72 —>72/3=24. If this number is bigger than the allowed (21 in this example) we can discard the rest of permutations because we’ll always get an over number. The following code was inserted in the check method making the program more effective: // true/false only to enter or not to this // new check (optimization) if ( true ) { total = 0; for(idx=0; idx<=posn; idx++) total += face[idx]; total = size*(size+1)/2 - total; if ( total/((size-posn)/3D) > maxTot ) return false; }
The new performance is: Numbers 12 13 13 14 15
Limit Calls-Original 21 2,168,123 22 8,092,606 23 18,990,336 24 77,374,157 25 308,576,798
Calls-New 637,269 549,160 5,486,228 8,199,708 4,829,667
The new Cloque is similar to FacePerm in performance with the examples shown, but if you try 16 and 27 as numbers and limit, respectively, on my computer (PIII 500-MHz, 256 MB), the results 10
Dear DDJ, Regarding my article “Backtracking Algorithms” (DDJ, May 2004), Paul Purdom of Indiana University, Bloomington made the following observation clock face permutation backtracking: There is one simple test you can add to your code that should make it much faster yet. Suppose you have assigned numbers to the clock face for positions 1 to k, but have not yet assigned numbers for positions k+1 to N. You have the following situation: X[k–1] X[k] X[k+1] … X[N]
X[1]
X[2]
known known unknown … unknown known known
You also know that the sum of each three numbers should be no more than MaxSum, and you have Nk+2 groups of unknown sums-of-three. Let R be the sum of the numbers not yet assigned. Then X[k–1] appears in one group-of-three, X[k] appears in two groups, each X contributing to R appears in three groups, X [1] appears in two groups, and X[2] appears in one group. Thus, we need: (N– k+2)MaxSum>=X[k–1]+2X[k]+3R+2X[1]+X[2].
This, indeed, massively reduces the number of function calls and the time required to solve the problem. For instance, using the straight backtracking implementation in Java took 19.44 hours to discover that a clock face of 20 entries has 506 cyclic permutations with a maximum sum of 33. Doing the same thing after adding the bound that Professor Purdom provided, the program required was only 13.85 seconds. 5.3E+11 function calls got trimmed down to 7.0E+04. Timothy Rolfe
[email protected] C, as in Duct Tape Dear DDJ, I’ve been writing code (mostly in C) for the past 20 years and I’d like to comment on some of the points in Jerry Pournelle’s February 2004 column. • Strong type/range checking can prevent buffer overflows. This is true, and wonderful when a program runs in a veritable vacuum, like a spreadsheet that takes user input directly and read/writes its own files. It is also nearly true when a program communicates with a known partner for known purposes. Unfortunately, in the world of the Internet, one can rarely be assured that the program on the other end will always be the correct one or even the correct version of the correct program. That means programs must be Dr. Dobb’s Journal, September 2004
able to handle unexpected buffer lengths and sometimes must be able to determine the data type of incoming data after it is read—very, very difficult in strongly typed languages. Yes, better hardware can speed up the necessary hoop jumping, but a loosely typed language can easily adjust on the fly to new data types, at least when coded correctly. • Shooting feet. I once heard (from a fellow at DEC) this comment about programming in C: “We provide the gun and bullets, you provide the foot.” However, as most sane people know, just because you can do a thing, doesn’t mean you should do that thing! • C’s “near unreadability.” When I was learning C, the guys in my shop called it a “write-only language” because it was so hard to guess what another person meant by reading their code. However, that was just an excuse for writing poorly commented code that made use of every possible syntactical shortcut combined with lousy formatting. When I was given the opportunity (at my next job) to set the coding-style guidelines, things were much better… For the past 10 years, I’ve been coercing the other programmers to follow my style guidelines and none of us ever have trouble following each other’s code. Even customers who have purchased source licenses use our source as self training because it is easier to understand than many samples on the MSDN CD! • Other languages. You missed good old Ada in your list! I had to learn that while I was in the U.S. Air Force (in 1986, when the first validated compilers were becoming available) and I think it would’ve been a very good choice, too. Based on tests at the time, it was almost always true that a program developed in Ada was done once it would compile. Very few bugs were ever found after a compile completed successfully. On the other hand, there’s an old joke that may bear repeating here: “REAL PROGRAMMER’s can write Fortran in any language!” And my personal corollary: “Most programmers (or at least, people who call themselves programmers) write bad code in every language (even English or their native tongue).” I think of C as kind of like Duct tape — very flexible, easy to get something small done very quickly, great for a very wide number of jobs. But would anyone want to fly in an airplane made entirely out of Duct tape? Steve Valliere
[email protected] DDJ http://www.ddj.com
DR. ECCO’S OMNIHEURIST CORNER
Occam’s Ringleaders Dennis E. Shasha
A
s I entered Ecco’s apartment, I could see that he and his 10-year- old nephew Tyler were engaged in a heated discussion. “This makes no sense uncle,” Tyler said. “The rule in checkers that forces me to jump prevents a whole world of strategies. I don’t think it’s necessary.” Ecco chuckled. “You would have gotten along well with William of Occam young Tyler.” “Occam’s razor?” asked Liane. “Right,” Ecco responded, “the 13th century Franciscan theologian.” “I have his quote on my bedroom wall,” Liane interjected. ‘Plurality should not be assumed without necessity.’ he wrote. He used the principle to fight beliefs in witchcraft. At the time, people accused witches of every possible mishap. He thought that the mishaps could come from completely natural causes. I figure that they would have heard me argue about mathematics or cosmology and convicted me forthwith. So he would have been my natural defender and ally.” “I agree,” Ecco said smiling at his 16year-old niece who somehow managed to look quite stylish in her lacrosse uniform. “He wanted explanations to be much simpler. Justice is often simple. But we’ll come back to witchcraft and checkers another day, I promise. Today, I want to talk about using the Occam principles to find the ringleaders of a gang of 11 thieves. “Here is the data we have. There have been several stock-trading events on 11 stocks that the authorities believe are collusions in purchases and sales of stock. Represent a purchase by a 1 and a sale by a 0. The 11 conspirators are smart enough not to communicate by phone or e-mail. We believe they collude by their actions. There are a few ringleaders who perform actions and then their subordinate conspirators compute a particularly simple logical/arithmetic function to decide on their action. Dennis is a professor of computer science at New York University. His latest books include Dr. Ecco’s Cyberpuzzles: 36 Puzzles for Hackers and Other Mathematical Detectives (W.W. Norton, 2002) and Database Tuning: Principles, Experiments, and Troubleshooting Techniques (Morgan Kaufman, 2002). He can be contacted at
[email protected]. 12
“Our informant tells us that they use just two circuit elements: AND takes some collection of 1s and 0s as inputs and outputs a 1 if all the inputs are 1; otherwise, it ouputs a 0. ODD returns a 1 if the number of 1s in its input collection is odd and otherwise it returns 0. (Note that if there are no 1s in its input collection, ODD returns 0.) Just those two circuit elements. No more. “One or both of these circuit elements are used by each subordinate conspirator we believe. Here’s a warmup. There were 12 events and 6 conspirators who did the following (on six different stocks): conspirator conspirator conspirator conspirator conspirator conspirator
1: 2: 3: 4: 5: 6:
1 0 1 1 0 0
1 1 1 1 0 1
0 0 0 0 0 0
1 1 1 0 0 0
0 1 0 1 1 0
0 1 0 1 1 0
0 1 0 1 1 0
1 0 1 0 1 1
0 0 0 1 1 1
1 1 1 0 0 0
1 1 1 0 0 0
1 1 1 0 0 0
Which ones are the ringleaders? Try before you read on.” Solution to the Warm-Up Puzzle Conspirators 2, 4, and 6 are, or at least could be, the ringleaders. Conspirators 1 and 3 simply take the ODD function on the buy/sell values of the ringleaders. For example, in the first column, the values of conspirators 2, 4, and 6 are 0, 1, 0, respectively, so there are an odd number of 1s. In the second, 2, 4, 6 have the values 1, 1, 1, so again there are an odd number of 1s. Conspirator 5 computes the function: AND the results of 2 and 4, then take the ODD function on that result and the input from 6 (see Figure 1). .Algebraically, C5=ODD(C6, AND(C2, C4)). So, the first column produce a 0 from the AND and the input from 6 is also 0 so the result is 0. In the second column, the AND produces a 1, but the input from 6 is also a 1, so the number of 1s is even; hence, we get a 0 result. C2
C4
C6
AND
ODD
1. Ok, now it’s your turn. Here are the conspirators’ buy/sell decisions on 11 different stocks. conspirator 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 conspirator 2: 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0 conspirator 3: 0 0 1 1 1 1 1 0 1 1 0 1 1 0 1 0 conspirator 4: 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 conspirator 5: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 conspirator 6: 1 0 0 0 1 1 0 1 1 1 1 1 0 1 0 1 conspirator 7: 1 1 0 1 0 0 1 1 0 0 1 0 1 0 0 1 conspirator 8: 1 0 1 0 0 1 0 0 0 1 1 1 0 1 1 1 conspirator 9: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 conspirator 10: 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 1 conspirator 11: 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0
Reader: Try to find the ringleaders and how each of the subordinate conspirators make his or her decision. You may be able to do this on your kitchen table. Hint: Tyler and Liane were able to do this assuming only four ringleaders. It’s open whether fewer could be the ringleaders, assuming each subordinate computes a function using only at most one AND and one ODD circuit. 2. There is a new group of trades. Liane and Tyler believe there are only 3 ringleaders this time. They also think the conspirators have grown careless. Can you see why? conspirator 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 conspirator 2: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 conspirator 3: 0 1 0 0 0 0 1 1 0 0 0 1 1 0 1 1 conspirator 4: 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 conspirator 5: 0 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 conspirator 6: 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 conspirator 7: 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 conspirator 8: 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 conspirator 9: 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 conspirator 10: 0 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 conspirator 11: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
One thing that worries Ecco is that perhaps any random set of buy/sell decisions among 11 traders over a time scale of 16 could lead to the conclusion that four ringleaders and possibly even three were responsible. That would mean innocent people would be falsely accused. Do you think this would be a common occurrence for the simple AND/ODD circuits presented here? Perhaps you can find an elegant counting argument. For the solution to last month’s puzzle, see page 88.
C5
Figure 1: Warm up. Dr. Dobb’s Journal, September 2004
DDJ http://www.ddj.com
SECTION
A
MAIN NEWS
Dr. Dobb’s
News & Views
DARPA Prepares Next Robot Race A million dollar prize went unclaimed in last year’s DARPA Grand Challenge (http:// www.darpa.mil/grandchallenge/), as none of the autonomous robot racers managed to travel more than eight miles of the 142 mile off-road course. DARPA, however, has decided to make a yearly event of the race. The next Grand Challenge has been scheduled for October 8, 2005, and the prize money has been doubled. This year, DARPA is also holding a Participants Conference “intended for participants, interested sponsors, and groups looking for others to help complete their teams.” The conference will take place on August 14 in Anaheim, California. Fifteen teams from a field of 106 applicants managed to qualify for the race in 2004. The best showing was made by “Sandstorm,” a robotic Humvee built by a team at Carnegie-Mellon, which managed to complete 7.4 miles with an average speed of 15 mph (http://www.redteamracing .org/index.html). The Carnegie-Mellon team is already preparing for next year’s race, and DARPA expects overall participation to rise significantly this year.
Largest Prime Number Yet The Great Internet Mersenne Prime Search (GIMPS), a distributed computing effort that uses the spare computing cycles of volunteers to search for as-yet-unknown prime numbers, has discovered a 7,235,733-digit prime number. The new number, which can be concisely expressed as 2 to the 24,036,583th power minus 1, is the largest known prime and only the 41st known Mersenne prime. The discov-
14
ery was made by Josh Findley, a consultant to the National Oceanic and Atmospheric Administration in La Jolla, California. He has been part of the GIMPS project (http://www.mersenne.org/) for five years; the specific calculation that led to the new discovery took two weeks to perform on his 2.4-GHz Pentium 4 PC. Mersenne primes are named for Marin Mersenne, a French monk who published a sequence of these numbers in 1644, although he was not the first to study the relationship between prime numbers and numbers of the form 2n–1. For example, these numbers are prime when n equals 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, and 127. This is the seventh Mersenne prime discovered by the GIMPS project over the last eight years. The Electronic Frontier Foundation offers a $100,000 prize for the discovery of the first 10-million-digit prime: “An award-winning prime could be mere weeks or as much as few years away— that’s the fun of math discoveries,” said GIMPS founder George Woltman in a prepared statement.
New Algorithm for 3D Compression A team of researchers from the University of Southern California says their Variational Shape Approximation scheme lets 3D images be compressed with much more efficiency than existing methods (http:// www-grail.usc.edu/pubs.html). Assistant professor Mathieu Desbrun worked with two postdoctoral researchers — Pierre Alliez, now with France’s National Institute for Research in Information and Automation, and David Cohen-Steiner, now of Duke University — to produce the “Variational
Dr. Dobb’s Journal, September 2004
DR. DOBB’S JOURNAL September 1, 2004
Shape Approximation” scheme, which represents 3D images as simplified meshes. It uses a technique called “Lloyd Clustering,” from the field of machine learning, to dissect 3D objects into nonoverlapping connected regions that can then be separately optimized.
Microsoft Revises Shared Source License Microsoft is eliminating many of the restrictions on the use of its “shared source” license for Windows CE 5.0. The revised shared source license increases the source code that Microsoft is making available to more than 2.5 million lines of code, including the GUI, operating-system kernel, and the like. Among other revisions, the license for CE 5.0 lets developers customize the OS code in their software without having to sublicense the modified code back to Microsoft. For more information, see http://msdn.microsoft.com/embedded/.
Java 3D & Project Looking Glass Open Sourced Sun has announced the open-source availability of the Java 3D API and Project Looking Glass. The Java 3D API provides a set of object-oriented interfaces that support a high-level programming model you can use to build, render, and control 3D objects and visual environments. With the Java 3D API (http://www.java.sun.com/products/javamedia/3D/), you can incorporate highquality, platform-independent 3D graphics into Java-based applications and applets. Project Looking Glass (http://www.sun .com/software/project-looking-glass/) is an interface that offers an intuitive, 3D environment to interact with desktop apps.
http://www.ddj.com
Grid Computing & the Linda Programming Model An alternative to web-service interfaces ROB BJORNSON AND ANDREW SHERMAN
W
ith all the current interest in Grid computing, it is surprising that there is still a lack of agreement on exactly what it is. Our definition is a pragmatic one. Grid computing is an approach to computing that lets you:
• Organize widespread, diverse collections of CPU resources into a virtual supercomputer. • Organize widespread, diverse collections of data resources into a virtual file system. • Organize widespread, diverse collections of applications into standardized, reusable libraries of components (virtual applications). • Collect and organize disparate, valuable, but hard-to-use resources into a more uniform, manageable, visual whole. • Make this virtual grid of resources accessible to multiple users simultaneously. Much of the current mainstream thrust in grid computing has grown out of the web-services community, which naturally envisions the grid as a large collection of machines that offer resources via web-service-like interfaces accessed directly by clients that speak primarily in XML. This view of grid computing is appropriate in some contexts, such as loosely coupled service architectures. However, this abstraction level is too low for most users, and XML requires far too much data translation and parsing for efficient communication. Furthermore, direct RPC-style communication is too restrictive in the dynamic, even disorganized, environment in which grid applications have to exist. Alternatively, “Linda” is a communication style abstraction (called a “tuplespace”) based on a bulletin board rather than direct messaging. Linda Linda is not a full programming language. Rather, it is a set of coordination operations that can be added to any existing language, providing a way to communicate among and synchronize different processes. Linda has been added to languages as diverse as C, Java, Prolog, Fortran, and Smalltalk. Moreover, there Rob is chief architect at TurboWorx. He received a Ph.D. from Yale University, where he focused on massive parallel computing. He can be contacted at
[email protected]. Andy is CTO at TurboWorx. He also received a Ph.D. from Yale and has 30 years of experience in high-performance computing. He can be reached at
[email protected]. 16
are at least three robust, commercially supported versions of Linda for Java. Although their APIs differ somewhat, all offer largely similar capabilities. All support the basic Linda operations, multiple tuplespaces, and transactions on tuplespaces (for consistency and fault tolerance):
“Scheduling is a decentralized, cooperative process between clients and workers” • Paradise, from Scientific Computing Associates (http://www .lindaspaces.com/) emphasizes speed and interlanguage connectivity. It has APIs for Fortran, C, and Java, letting tuples serve as a bridge between languages as well as between processors. (Rob was one of the designer/implementers of Paradise.) • JavaSpaces, from Sun Microsystems (http://java.sun.com/ developer/products/ jini/index.jsp), is part of the Jini project. Not surprisingly, JavaSpaces is confined to operating within Java, and leverages Java in its API. In particular, Linda operations are performed directly on a single object; its public fields become the fields of the tuple. It is integrated with other Java technologies, most notably transactions. (An excellent book on the subject is JavaSpaces Principles, Patterns, and Practice by Freeman, Hupfer, and Arnold; http://java.sun.com/docs/ books/jini/javaspaces/.) • Tspaces from IBM (http://www.almaden.ibm.com/cs/TSpaces/) is also supported only in Java, but has a focus on extensibility, database-like functionality, and fault tolerance. Tspaces supports more complex queries against tuplespace by creating custom matches( ) methods in tuples. In Linda, data is created and communicated via tuples. Tuples are simply ordered collections of data. For example, the tuple: ("task", taskid, arguments[4], taskdesc)
could describe a task to be performed, its inputs, and a unique task identifier. Tuples are produced by writing them to tuplespace:
Dr. Dobb’s Journal, September 2004
http://www.ddj.com
ts.out("task", taskid, arguments[4], taskdesc)
Not surprisingly, the exact syntax for Linda operations varies among different host languages and even among implementations of Linda. (In this article, we use a generic Java syntax.) Tuples are read by performing read( ) or in( ) operations, using a template to search for matching tuples. Some values in a template are filled in, in which case they must match exactly; others are wildcards and must simply be type compatible. Wildcards are denoted by a “?”; for example: ts.in("task", ? taskid, ? arguments[], ? taskdesc)
searches for a tuple that matches; if one is found, it consumes it. As a side effect, taskid, arguments, and taskdesc are set to the values found in the tuple. If several matches are available, one is chosen, typically at random. If no matching tuple is found, the operation blocks until one appears. Using the bulletin-board metaphor, tuplespaces are boards and tuples are the notes posted on them. At first blush, this might appear an odd way to communicate. If you want to send a message to Bob, why would you write a message on a board when you could just call him (message passing being equivalent to directly calling someone)? There are several reasons: • Bob might not be available right now to take a call. • You might not know Bob’s number. • More importantly, you may not know Bob’s identity. Just as you might post a note on a board looking for a ride to Seattle, you can post a tuple requesting a certain type of service. You don’t need to know who will provide the service, where they are located, or if they are currently available. Linda provides a communication mechanism that is both associative (using qualities of the data itself to find it) and anonymous (producers and consumers of data communicate without directly addressing one another). This is in sharp contrast to traditional message-passing approaches (of which web/grid services are simply the latest incarnation), where messages are always directed to a particular recipient. Traditionally, Linda has been considered a parallel programming tool for improving the performance of a single application, analogous to the Message-Passing Interface Standard (http://www-unix.mcs.anl.gov/mpi/). However, Linda is even better suited to distributed or grid computing, where individual components of the system are less well known to one another. A common Linda idiom is the client/worker model in which clients submit tuples that represent tasks to a particular tuplespace. Included in the tuples is all the information required for scheduling and executing a particular task. Workers, which represent compute nodes, use in( ) to withdraw tuples for compatible tasks. They execute the tasks and put a result tuples back into tuplespace.
Figure 1: A protein classification workflow. http://www.ddj.com
This idiom is simple, yet powerful, because of the properties of Linda communication. Scheduling is a decentralized, cooperative process between clients and workers. Workers can dynamically come and go as they please because tasks are not being directed at any particular worker. Achieving fault tolerance is greatly simplified because tuples are manipulated under transactions; if a worker fails holding a task tuple, it is automatically regenerated. Example 1 shows simplified code for the tuple client and worker. Visual Programming, Workflows, & Grids Figure 1 shows a workflow that implements a compute-intensive application. The workflow is built using TurboWorx Builder, a component and development environment from TurboWorx (the company we work for; http://www.turboworx.com/). Figure 1 shows a life-science application for classification of protein domains. In the figure, the boxes represent components performing computations, while the (directed) lines represent the flow of data and dependencies. The visual workflow created by the user is automatically transformed by the GUI into an XML representation that guides the runtime system as it carries out workflow execution. Components in workflows perform computations by invoking applications or other workflows. Applications may be compiled executables, scripts written in languages such as Perl, Python, or Java classes. Before use in workflows, each application is “componentized” using a wizard that creates an XML wrapper file describing the application’s inputs and outputs and how it should be invoked. Typically, no modifications are made in the underlying program or script. For a command-line invocation, the XML would describe the invocation command, including input and output files, environment variables, switches, and the like. For a Java method, the wrapper would describe the accessor and execution methods, much as with JavaBeans. Workflows are themselves components and they may be nested to arbitrary depth as components in other workflows. At runtime, components may execute as soon as all of their required input dependencies are satisfied, and the runtime system normally tries to schedule them on appropriate compute (continued on page 20) (a) worker() { RESULT r; TASK t; while (1) { transaction(ts); ts.in("task", ?t); r = compute_task(t); ts.out("result", r); commit(ts); } } (b) master() { int i; RESULT r; TASK t; for (i=0; create_task(&t);i++) ts.out("task",t); for (;i;--i){ ts.in("result",?r); update_result(r); } output_result(r); }
Example 1: Master/worker paradigm: (a) worker; (b) master. Dr. Dobb’s Journal, September 2004
17
(continued from page 17) nodes (that is, workers) as soon as possible after they become ready to run. After executing, components normally provide data for each of their outputs that must be delivered eventually to one or more downstream components in the workflow. Figure 1 also illustrates one of the advanced TurboWorx programming features for exploiting parallelism. The components joined by parallel lines (beginning with “Fasta Splitter” and ending with “Concatenation Joiner”) actually constitute a parallel loop. Multiple independent data elements flow through this subgraph, possibly causing multiple instances of the components to run on independent nodes. Such advanced programming features make it easy for users to apply workflow systems to a wide variety of computational problems. Runtime System The runtime system required for executing workflows in a grid environment poses a number of challenges: • Tasks must be scheduled to run when their required inputs are present. • Results must be propagated to downstream tasks. • Tasks should be efficiently assigned to worker machines on the grid, even as the workers come and go dynamically. • Workers failing while executing a task should not interrupt the overall computation. The Linda communication model supports these requirements quite naturally, using a more advanced form of the client/worker model, in which tasks express interdependencies and can generate subtasks. The runtime system transforms the XML describing the workflow into a partially ordered collection of tasks and executes them on a set of worker nodes, using tuples to represent the tasks. Figure 2 portrays the overall architecture of the TurboWorx runtime system. The system contains three major elements — a single Master, one or more Clients, and one or more Workers. Master. The Master refers to a collection of services, often colocated on a central server, that coordinate the overall runtime system. These services include a Linda server for storing tasks and other metadata, a web server and a data server. Each of these services is backed by nonvolatile storage so that, in the event of failure, the services can be restarted without losing vital state. The Linda server is used to store information about tasks and to communicate metadata or small quantities of real data between tasks. Each task is represented by a task tuple that contains information required to execute the underlying computational program; data or metadata about the inputs available thus far (that is, satisfied dependencies for the task); the number of remaining inputs required; information about the user submitting the task; and a reference to the component definition (to be described shortly). One field of the tuple indicates task status. When all the inputs for a task are available (all dependencies are satisfied), that field of the task tuple is changed to indicate that the task is ready to run. Workers take tasks by selecting from among the readyto-run task tuples. All tuple manipulations occur under transactions, so that a recovery mechanism can be invoked should failures occur. Recovery is accomplished by rolling back the workflow’s execution state to the most recent consistent state. Thus, the Linda server acts as the “short-term” state memory of our system. In concert with a database, the web server is used to manage the collection of users and the library of defined components. It also provides the service side of a browser-based user interface to the system, letting users execute components from a portallike web interface, forwarding execution requests to the master’s Linda server, and holding completed results until users request 20
Dr. Dobb’s Journal, September 2004
http://www.ddj.com
(continued from page 20) them. Thus, the web server serves as the “long-term” memory of our system. The data server is used to store and stream large data objects among the clients and the workers performing component execution. For large data objects, the metadata passed via the Linda server only includes reference-counted pointers to the data. The data itself is only transmitted when the component requiring it has been scheduled on a specific worker. The system currently supports a variety of data server implementations, including NSF, FTP, and WebDav. Clients. Clients represent the users of our system. Clients submit execution requests by naming a component (typically, a workflow) to be executed and providing a set of input values to be passed to the executing instance of that component. The client then waits for the results to be returned. Currently, a client may use a SOAP or Java API to interact with our system, and we provide users with a Java Swing GUI that invokes a servlet-based web API. Workers. The workers are the actual loci of computation for the runtime system. They are responsible for selecting ready-to-run task tuples from the Linda server, collecting required data and executables, carrying out the actual computations, and delivering output data for use by downstream components. Task scheduling is completely decentralized in the sense that each worker makes its own decisions about task selection based on locally configurable selection/scheduling criteria. (This is a major advantage in the grid setting.) Task selection may be based on a variety of criteria, including task metadata (for example, task priority, user identity, application name, characteristics of the inputs) as well as local information about the worker’s state (resource availability, current load, prior local availability of input data, and so on). Once a worker has selected a task, it requests the component definition from the component library, examines the XML wrapper, and invokes an appropriate component interpreter. A component interpreter is a program that understands how to interpret the component metadata to set up and execute a particular type of component (for example, command-line executable, script, or Java method). The interpreter collects required input data, sets up the necessary runtime environment, and invokes the underlying application executable or scripting system. Fault Tolerance The runtime system as a whole is fault tolerant in that any element (Client, Master, or Worker) can fail without causing the system to lose the states of currently executing workflows. Fundamentally, fault tolerance is accomplished via Linda but is handled somewhat differently for each of the three elements of the system. If a Client fails after submitting a workflow, the workflow execution will continue as usual. The master retains the results until such time as a new authorized Client requests them via an in( ) operation. If a Worker fails while executing a task, the Linda server automatically cancels the transaction under which the execution was proceeding, and the task returns to the list of pending tasks available for selection by another Worker. In general, the work performed on the partially completed, failed task is lost, but completed tasks in the workflow are safe. If the Master fails, the system ceases executing until a new Master is started from the saved state of the failed Master (the Linda server maintains its own checkpoint). Restarting the Master restores the state of the various services from their most recent consistent checkpoints, and workflow executions can proceed from that point. Scalability A possible objection to the aforementioned architecture concerns the scalability of the Linda server. Our current implementations employ a single server, primarily to simplify administration. 22
Dr. Dobb’s Journal, September 2004
http://www.ddj.com
N
e ativ
..
CompTask PirTask DFTB
TBTB
Jpiranhad TupleAPI
Na
FTP
NFS
WebDav
WebDav
FTP
Web Server tive
Client
Soap
Apache
Postgres ...
Ta s
ks
UsrSvc ComDir CompRep Tomcat
DataRepAPI NFS
Linda Server
DF Intp
Soap
CLI Intp
THubAPI
Builder
s
Task
TCP/IP ...
Data Server
Worker
Master
Figure 2: Runtime system architecture. (continued from page 22) However, multiple servers can be scattered around the grid, each serving as a local grid-access point. Tuplespaces could serve as directories listing available access points. Workers and Clients could wander from server to server, as their needs dictate. Conclusion The Linda programming model provides a number of advantages for building Grid applications, compared to more traditional approaches using web services: • Compute nodes (workers) can dynamically appear and disappear without any additional programming effort or architectural complexity.
• Scheduling is a distributed activity. Each worker makes its own decision about which tasks to take. No centralized, oracular scheduler is required. • The state of the system is open and available for inspection. The state of tasks can be determined by browsing the tuples in the Linda server via a variety of tools, including webbrowser interfaces. • Native data types, such as Java objects, can be easily passed among cooperating processes. This does not exclude the possibility of exchanging tuples containing XML in cases where that is appropriate, of course. DDJ
Debugging, Message-Oriented Middleware, & Distributed Systems Runtime software modification PAUL PAZANDAK AND STEVE FORD
I
f you are involved in designing and building distributed messaging systems, you are well aware of the problems in tracking down and isolating bugs. A common approach is to log into each of the remote hosts, start the application on each, then watch for exceptions or debug statements you inserted in the code. The problem with this approach is that it doesn’t scale well. For one thing, when the distributed system involves tens of computers and hundreds of processes, it is impossible to observe all of the console windows. Furthermore, when the distributed processes are sending hundreds or thousands of messages (and it’s your job to find out why a handful of messages out of those thousands aren’t making it to their destination), it is impossible to visually track every message through the system by monitoring the debug statements emitted to the screen. This is exactly what we were faced with in the Cougaar Agent System. Cougaar (short for “Cognitive Agent Architecture”) is a Java-based architecture for the construction of large-scale distributed agentDr. Paul Pazandak (
[email protected]) and Steve Ford (
[email protected]) are research scientists at Object Services and Consulting (http://www.objs.com/). Distribution Statement A Approved for public release; distribution is unlimited. 26
based applications and the product of a multiyear DARPA research project (UltraLog, http://www.ultralog.net/) into largescale agent systems. The Cougaar agent system is big. This year, the largest of the Cougaar test societies will have 50+ host computers running 1000+ agents; a small test society involves about six computers. Therefore, it should not be a surprise that debugging messaging problems in Cougaar is labor intensive. Given the quantity of messages being sent, we simply could not monitor console windows. Instead (in the beginning), we sent all of the debug statements to log files using Log4J (http://logging .apache.org/log4j/docs/), then inspected the files offline after the application had terminated. We improved on this by implementing a console tool to inspect the log files for us and identify what messages had been lost. This tool sorted all messages first by agent, and then by whether the message was sent or received by that agent. A second iteration through these files identified which messages were sent but not received. A problem with this approach was that it was not dynamic — we had to wait for the application to run to completion (for instance, generating a logistics plan, which might be an hour or more). However, an even bigger problem was that it allowed only coarse visibility — it would tell us if a message didn’t make it, but it would not tell us how far it had gotten. We would then have to hand inspect the log files to track down debug statements to see where the message was last seen. We should say that we are assuming that the underlying network is not the likely problem, rather we are debugging the multiprotocol sending and receiving message stacks that we wrote. What we did next was to Dr. Dobb’s Journal, September 2004
implement a tool that solved both of these problems. Solving Problem 1: Offline Debugging Instead of collecting data into files, we routed all of the message-related Log4J debug statements from every agent to our new centralized collection tool running on one machine. To do this, we defined a
“ProbeMeister supports both XML configuration-directed probe insertion and drag-and-drop insertion” Log4J SocketAppender in Cougaar, then passed in the host and port for the tool via each host’s command line. The Log4J debug statements were then modified to emit to an event router class that we implemented (in Cougaar), which simply sent them across the socket if it existed (if the command-line arguments were provided); otherwise, we sent them via the default Cougaar logging mechanism. The centralized tool at the other end collected, organized, and displayed all of the data as soon as it was received (Figure 1). The main window showed a summary of all known agents, how many messages they had sent, received, and were still outstanding. From here, you can drill-down and look at all of the messages sent by any http://www.ddj.com
(continued from page 26) given agent, and quickly see which messages had made it or had not yet arrived. While this was a big improvement over the previous tool, we still wanted to pinpoint where a message was being lost. Solving Problem 2: Coarse Visibility Rather than just knowing whether a message was received, we wanted to know where it was last seen in the code for the sending/receiving protocol stacks so that we could track down the offending bug. To solve this, we needed the tool to recognize and process debug statements emitted at multiple points in the stacks. This would let us see how far each message traveled through the code. These points, or logpoints, were simply additional Log4J debug statements that we inserted in the protocol stacks (having debug statements at multiple layers in the message stack results in thousands of entries for each agent). With the logpoints in place, our tool lets us drill down further to see the logpoints each message made it to and when it arrived at each logpoint (Figure 2). The tool learned about logpoints via an XML-based configuration file (Exam-
Figure 1: Centralized collection tool.
ple 1). It defined the logpoints, which stack they belonged to (send or receive), supplied a user-friendly name, and the order they appeared in the stacks. The last receive stack logpoint defined defaults to be treated as the endpoint. Any message having reached this point was considered to have been successfully received. We also permitted the endpoint to be changed at runtime. Since the tool’s main window displays the number of messages sent and received, changing the endpoint could affect how many messages were considered to have been successfully received. This lets us quickly see how many messages had made it to a specific logpoint. Using our tool, we were then able to see (in near real time) the flow of messages through the system and quickly observe when messages were apparently lost in the ether. In the MessageDetail window (Figure 2), we could examine the logpoints for each individual message and the time it was seen. The send stack logpoints were color-coded in black, receive logpoints in blue, and the final logpoint in red. When we identified messages disappearing (not making it past some logpoint), the next step was to insert one or more logpoints after the last logpoint the message was seen at. This, of course, required us to stop the application, modify the code, and then restart it. For small applications, or when reaching new debug statements occurs relatively quickly, the run-observe-stop-add_more_logpointsrestart debug cycle might be tolerable. In our situation, testing the various message protocols might take an hour. So, while the tool reduced the time to identify lost messages substantially, we were still left with an expensive debug cycle to track down where the messages were being lost. Fortunately, we had another tool to bring to bear.
TRUE" ID="B TRUE" ID="B TRUE" ID="B FALSE" ID="A 1" SEND_STACK="F FALSE" ID="A
Example 1: Logpoint configuration file. 28
Dr. Dobb’s Journal, September 2004
http://www.ddj.com
Inserting Logpoints at Runtime The last major hurdle to efficiently debugging our code was to terminate the application to insert new logpoints (Log4J debug statements). What we really needed was to be able to insert (and remove) logpoints into the agents while Cougaar was running. For this feature we turned to ProbeMeister, another tool we had developed (available electronically; see “Resource Center,” page 3). ProbeMeister (Figure 3) is a runtime software instrumentation tool (it was the first tool of its kind to use the advanced distributed debugging facilities introduced in JDK 1.4). ProbeMeister’s key strength is that it is capable of inserting Java bytecode into any local or remotely running Java application without stopping it. We developed ProbeMeister a few years ago to support ad hoc insertion of software probes into multiple remotely running Java applications. To insert probes into an application, users can either connect to the remote application at will from ProbeMeister or configure the remote application (using additional Java Virtual Machine directed command-line arguments) to connect to ProbeMeister when it starts up. No specialized JVM or modification of the application itself is required. ProbeMeister supports XML configurationdirected probe insertion as well as dragand-drop insertion. Using XML-based configuration files, you can specify exactly where to insert a given set of probes into a Java process (the probes can be inserted into application classes as well as core JVM classes). The custom configurations can then be automatically applied when ProbeMeister first attaches to the application or at any point after. While configuration files could be defined by hand, in general, you build up a configuration simply by deploying probes — ProbeMeister records all deployments that can then be exported to a configuration file (the file can then be edited if desired). Custom configurations could be used to focus on specific problems such as networking or file I/O, or to define application patches. Probes can be just about any code you might want to write; they are certainly not limited to debugging statements. Ad hoc deployment of probes involves simply dragging a selected probe to a source-code window and dropping it in between two lines of code. The sourcecode window displays the decompiled bytecode of the selected class and method, and labeled icons indicate where other probes currently exist in the code. Because ProbeMeister decompiles the current in-memory version of a class’s bytecode, no source code files are used by ProbeMeister. Once a probe has been dropped into the source-code window, it http://www.ddj.com
is immediately deployed to the remote JVM. Specifically, a copy of the method’s code is modified in the remote JVM and it is swapped in as soon as no process is executing the method. Once a probe is deployed, it remains in existence for the application’s execution lifetime (until the application is terminated), or until it is removed. Probe removal is just as simple as insertion — you
“To support this capability, our tool would need to understand how messages flow through the application” simply drag a probe out of the sourcecode window. While currently unimplemented, it would also be possible to support modification of the class files so that probes persisted across executions. Recall that the purpose of ProbeMeister was to insert probes into remotely running applications. Thus, if you insert debug statements into a remote application, they will by default emit their output to the remote machine’s console. However, it won’t do much good if you cannot see the output! To solve this, ProbeMeister includes a probe that forwards debug statements to a remote collection facility. We first implemented a basic web server that collected and displayed the data from all probed processes in a web page. We later extended ProbeMeister to act as a collector itself and to display the data within an easily accessible window. Data from multiple processes can be interwoven (the text from each process is color coded) or displayed in separate windows.
Figure 2: Message detail window. Dr. Dobb’s Journal, September 2004
ProbeMeister comes with a variety of probes built-in (for instance, one to call a specified method in the remote application, another to emit strings, one to emit a method’s arguments, and so on). Other basic probes can be written without excessive trouble using high-level probe-building library calls. More sophisticated probes are implemented in the target application as probe plugs. Using probe plugs, which are written in Java (not in bytecode like the other probes), you can easily and quickly write code capable of accessing and manipulating specific application objects and state. Then, in ProbeMeister, one drags and drops a probe stub onto the source code that is then customized by the user to call one of the predefined probe plugs (ProbeMeister displays a list of all compatible registered probe plugs that could be invoked). The most verbose probe stub passes several items to a probe plug for its use — the name of the remote JVM, the probe stub name, the name of the instrumented method, a user-supplied message, the current thread, an array containing all of the method’s arguments, and the current object (if the instrumented method is not a static method). Recall that the probe stub is executing within the remote application, so it has access to all of this information. Its job is simply to collect it all up and pass it to another method (the probe plug) to do something with it. This might include simply emitting the information, though the method could easily modify the data or object to affect application behavior. Using ProbeMeister To Solve Our Problem Using ProbeMeister, we developed a custom probe plug that would emit new logpoints by calling our event router in Cougaar. Specifically, we used a ProbeMeistersupplied probe stub to make a method call to a custom probe plug that we defined in Cougaar. We could use this plug in any method where a message was accessible.
Figure 3: Main ProbeMeister window showing a probe stub that was just deployed into the source-code window via drag-and-drop. 29
This gave us the ability to inspect the message and to identify the sending and receiving agents, message sequence number, message type, and so on. The probe plug then composed a debug statement containing this information and emitted it to the SocketAppender via our event router. Thus, using ProbeMeister, new logpoints could be added anywhere in the message stack. Our collection tool (see Figure 4) then automatically identified the new logpoints and correctly organized them. New logpoints appeared as NEW entries in our LogPoint Configuration window. From here, we could identify which ones to pay attention to, essentially indicating whether we cared about them or not. As they appeared in this window, we could redefine the endpoint and immediately see if any new messages were making it past the new logpoints (Figure 5). This significantly shortened the coding cycle by reducing the need for application restarts required after the insertion of new debug statements. You might ask why we needed to use ProbeMeister when we could simply place debug statements everywhere. Given the timing sensitivity of Cougaar, and likely most messaging middleware, the main problem with this approach is that it perturbs the behavior of the application such that it behaves differently than it would without all of the debug statements. A secondary problem with this approach, in general, is that of information overload because you may have 50 to 100 or more debug statements emitting data per message. Future Enhancements While we found ProbeMeister to suit our needs in some respects, it was never designed to scale to instrument hundreds of processes. It was also not designed with the specific intent to connect to several identical remote processes and to deploy identical probes to each. When we used it with Cougaar, we watched for where specific messages were being lost, and then attached to the host machine(s) that the message was lost on and deployed a probe. Ideally, and potentially in some future version of ProbeMeister, we could instruct a probe to be deployed simultaneously to several or all running JVMs in the agent society. A second enhancement that we could envision would be to automate the deployment of probes. This would come into play when a message didn’t arrive: Our message auditing tool would identify the last logpoint a message was seen at, select a point in the code between that logpoint and the next existing logpoint, and insert a new logpoint via ProbeMeister (via ProbeMeister’s existing RMI interface). If a message still didn’t make it to the new logpoint, another would be chosen between 30
Dr. Dobb’s Journal, September 2004
Figure 4: LogPoint display configuration window.
Figure 5: Agent message list. the last one it made it to and the one that was just inserted. Logpoints not of interest could be removed from the application via ProbeMeister to minimize perturbations. To support this capability, our tool would need to understand how messages flow through the application. Automated tools, and potentially user assistance, could be used to analyze the code to construct a data flow description that could then be used to identify logpoint locations. ProbeMeister is looking for a home. While it is fairly robust, it could use a good home where it could become a widely useful and available debugging tool. Acknowledgments Thanks to Dr. John Salasin for funding the development of ProbeMeister (funded under the DARPA DASADA program), as well as Dr. Mark Greaves for funding the tool development under UltraLog. We would also like to thank Tom Bannon for his contributions on this effort. This research is sponsored by the Defense Advanced Research Projects Agency and managed by the Department of the Interior/National Business Center under contract NBCHC010011. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency, Department of the Interior/National Business Center, or the United States Government. DDJ http://www.ddj.com
Stream-Control Transmission Protocol An alternative protocol to TCP IAN BARILE
T
he Stream Control Transmission Protocol (SCTP) is a new transport layer protocol proposed in RFC 2960 (http://www.faqs.org/rfcs/rfc2960 .html). Like TCP and UDP, SCTP uses the network layer protocol for intersystem communication. SCTP is a connectionoriented protocol, similar to TCP that provides reliable communication between two endpoints. Unlike the byte stream TCP uses for data transport, SCTP sends data in message chunks similar to UDP packets. SCTP was originally developed for telephony signaling networks. Integrated Services Digital Networks (ISDN) is one SS7 protocol implemented on SCTP. SCTP has many features that make it a beneficial protocol for use outside of the telecom industry. SCTP’s unique features such as native virtual streams and multihomed support make SCTP an attractive alternative to TCP. Over the next several years, SCTP will start to play a role in Internet applications. SCTP stacks are available for almost every operating system. To find an implementation for a particular OS, visit http:// www.sctp.org/implementations.html. In this article, I use the LKSCTP implemen-
Ian currently works as a development consultant for Marimba and his interests are in computer security and networking. He can be contacted at ian_barile@ yahoo.com. 32
tation (LKSCTP is integrated into the 2.6 Linux kernel; http://www.kernel.org/). Types of Socket Communication Several types of socket communication are available for use in developing network applications. Developers must choose the transport layer protocol and technique that transmits data efficiently for applications. Transport layer protocols transmit data between two endpoints on IPv4 networks using the following methods: • Unicast. One endpoint to one endpoint. • Broadcast. One endpoint to all endpoints on a subnet. • Multicast. One endpoint to many. TCP and SCTP are connection-oriented protocols that only support unicast data transmission. UDP is a connectionless protocol that supports unicast, broadcast, and multicast data transmission. Connectionless protocols send data to endpoints regardless of the endpoint ability to receive and process the data. Connection-oriented protocols ensure reliable data transmission, flow control, and error control. Unicast Data Transmission When developing applications that require unicast data transmission, you must choose the correct transport layer protocol. SCTP, TCP, and UDP have unique features that can benefit your application. SCTP is a connection-oriented protocol similar to TCP. SCTP provides error and flow control for data packets such as TCP. SCTP also gives you the ability to tag data through the use of virtual streams and protocol payload identifiers. SCTP sends data in messages similar to UDP packets — unlike the TCP byte stream. TCP uses a full-duplex byte stream to transmit data between endpoints. TCP enDr. Dobb’s Journal, September 2004
sures reliable, sequenced data transmission between two endpoints by using flow- and error-control algorithms. Like IP, UDP transmits data using unreliable, unordered datagram packets. Any packet reordering and validation occurs
“SCTP is a connection-oriented protocol similar to TCP” in the application layer. UDP is the fastest transport layer protocol due to the lack of error or flow control. Virtualized Streams SCTP’s virtual streams and the protocol payload identifier let you reduce application complexity and simplify application layer protocols by making it easy to identify data types. Virtual streams benefit you by letting data types be tagged by the stream identifier, reducing the need to parse data types out of the TCP byte stream. When implementing the application protocols HTTP and SMTP over TCP, different data types are identified by text headers (MIME headers). Parsing a TCP byte stream for text headers is a complex, costly process, compared to using the SCTP stream identifier (a WORD value) in the SCTP [DATA] packet header. To set up the number of inbound and outbound virtual streams for an SCTP association, two setsockopt( ) calls must be http://www.ddj.com
(continued from page 32) made with the option name SCTP_INITMSG and SUBSCRIBE_EVENT (see Example 1). SCTP-specific setsockopt( ) calls must pass SOL_SCTP for the level parameter. When an SCTP endpoint receives a mes-
sage from an associated endpoint via the sctp_recvmsg( ) API, the sctp_sndrcvinfo structure specifies the virtual stream via the sinfo_stream member (Example 2). Other application layer protocols such as FTP require multiple connections to com-
int SCTPSock = socket(PF_INET, SOCK_SEQPACKET, IPPROTO_SCTP); //set sctp initial options sctp_initmsg tSCTPInitMsg; memset(&tSCTPInitMsg, 0, sizeof(tSCTPInitMsg)); tSCTPInitMsg.sinit_num_ostreams = 10; tSCTPInitMsg.sinit_max_instreams = 20; int nRet = setsockopt(SCTPSock, SOL_SCTP, SCTP_INITMSG, &tSCTPInitMsg, sizeof(tSCTPInitMsg)); //tell SCTP to provide information about the data messages //being sent across the SCTP association sctp_event_subscribe tSCTPSubscribe; memset(&tSCTPSubscribe, 0, sizeof(tSCTPSubscribe)); tSCTPSubscribe.sctp_data_io_event = 1; tSCTPSubscribe.sctp_send_failure_event = 1; nRet = setsockopt(SCTPSock, SOL_SCTP, SCTP_EVENTS, &tSCTPSubscribe, sizeof(tSCTPSubscribe));
Example 1: SCTP_INITMSG and SUBSCRIBE_EVENT. This figure demonstrates how to set the number of virtual streams for an SCTP association. nRet = sctp_recvmsg(SCTPSock, szBuf, &buflen, (sockaddr*)&msgname, &msgname_len, &tSCTPSndRcvInfo, &msg_flags); if( nRet == -1 ){ perror(NULL); return -1; } switch(tSCTPSndRcvInfo.sinfo_stream){ ... }
Example 2: Using sctp_recvmsg() to get the virtual stream associated with the data message. TCP and SCTP Server (LISTEN)
∗ int server = socket(PF_INET, SOCK_STREAM, IPPROTO_SCTP). The last parameter can be 0 or IPPROTO_SCTP for a TCP socket.
∗ bind(server, SockAddr, sizeof(sockaddr_in) ∗ listen(server, 10) ∗ accept(server, NULL, NULL)
municate between a client and server. FTP servers and clients could be reimplemented with the “data connection” and the “control connection” being sent over one SCTP association. The multiple “connections” would be on separate virtual streams or have unique protocol payload identifiers. Multihomed Support SCTP native multihomed support enables an endpoint to send data transparently over multiple networks by binding an endpoint to multiple IP addresses. SCTP determines the IP address it will transmit data on by analyzing the routes between the addresses associated with an endpoint. When multiple addresses are available to an association, SCTP uses a default address. If the default route fails, the SCTP endpoint switches to another address in the transport address list. This enables clients to connect to servers over completely different networks reducing dropped connections due to connectivity issues and latency on a network; see Figure 1. When using SCTP to support multiple interfaces on a single SCTP socket, the sctp_bindx( ) call is used to bind the socket to more than one interface. sctp_ bindx( ) (Example 3) differs from the regular socket bind in that it allows addresses to be bound and removed from the socket dynamically. There is an optional call, sctp_connectx( ), which enables an endpoint to connect to multiple addresses on a remote endpoint. At this writing, the LKSCTP implementation hasn’t used the sctp_connectx( ) call. Security Security is an ever- increasing concern when developing applications. When developing a network application, you must understand the security issues associated with the transport layer protocol used. SCTP has been designed to mitigate certain types of security threats.
TCP and SCTP Client (CONNECTING)
∗ int client = socket(PF_INET, SOCK_STREAM, IPPROTO_SCTP) ∗ connect(client, NULL, NULL) SCTP Server (RECEIVING MESSAGE)
Endpoint 'A'
∗ int server = socket(PF_INET, SOCK_SEQPACKET, IPPROTO_SCTP) Network 1
∗ bind(server, SockAddr, sizeof(sockaddr_in))
Network 2
Network 3
∗ sctp_recvmsg(...). The SCTP association isn't established until the first message is received.
SCTP Client (SENDING MESSAGE)
∗ int client = socket(PF_INET,SOCK_SEQPACKET, IPPROTO_SCTP) ∗ sctp_sendmsg(...). The SCTP association is established when the message is
Endpoint 'Z'
successfully sent.
Figure 1: SCTP multihomed connection between two endpoints.
Table 1: Network APIs. 34
Dr. Dobb’s Journal, September 2004
http://www.ddj.com
A common transport layer attack, Denial of Service (DoS), tries to reduce the number of new inbound connections a system can create by tying up resources through a [SYN] flood. SCTP mitigates DoS attacks by using a cookie to maintain state information during the initialization handshake. The SCTP cookie contains data, like the Transmission Control Block, used in system resources once an endpoint enters the established state. An established SCTP socket protects against random and malicious packets through validation tags. If a packet is received with an invalid validation tag, the packet is discarded. SCTP relies on other technologies to provide protection against data corruption (IP Authentication Header RFC 2402) and protecting confidentiality (IP Encapsulating Security Payload RFC 2406). If your application requires a connectionoriented protocol to communicate between endpoints, you can choose between SCTP and TCP. When developing the applications, knowledge of how the connections are initialized, terminated, and data is transferred leads to better application design and faster debugging. Initialization Establishing an association between two endpoints requires the use of network APIs in the client and server to negotiate the association and allocate system resources. The socket APIs used for establishing TCP associations are used in establishing an SCTP association. SCTP also provides an implicit association to be created between endpoints. The socket APIs have been extended to to support SCTP-specific functionality. Table 1 lists the network APIs. When client and server applications establish an association between endpoints, the endpoints enter the protocols initialization sequences. The SCTP initialization sequence has a four-way handshake where TCP has a three-way handshake. The TCP initialization sequence in Figure 2 illustrates the [SYN]/[ACK] packet ex-
change required to establish communication between the endpoints. The endpoints use the sequence numbers established in the [SYN] packets to allow TCP stacks deliver sequenced data to the application. SCTP’s initialization sequence uses a fourway handshake. The extra step in SCTP’s handshake is used to pass a cookie that maintains state and validate the endpoints; see Figure 3. The initialization steps for two SCTP endpoints A and Z is as follows: 1. Association [INIT] is sent. The Init contains endpoint A maximum inbound virtual streams, number of outbound virtual requested, and the address list of the host. 2. Endpoint Z sends an [INIT ACK]. The [INIT ACK] contains endpoint Z’s [COOKIE] packet, Cookie_Z, number of virtual outbound streams, maximum number of inbound streams, and the address list. 3. Endpoint A sends the [COOKIE ECHO] packet. 4. Endpoint Z receives the [COOKIE ECHO] and sends the [COOKIE ACK]. Endpoint Z is now in an established state waiting to receive data. 5. Endpoint A receives the [COOKIE ACK] and the association enters an established state. User data is now allowed to be sent. During the initialization sequence, the number of inbound and outbound virtual streams, along with the address lists for the endpoints are exchanged. Each endpoint specifies its maximum number of inbound streams (MIS) and requests the number of outbound streams (OS). If the number of outbound streams is greater than the MIS, the OS must be adjusted to match the MIS stream count or the association must be aborted. If an SCTP endpoint needs multihomed support, an address list must be present in the initialization sequence. There are three possibilities for how addresses are listed in the [INIT] and [INIT-ACK] datagrams:
• No IP addresses list and no hostname. SCTP will use the IP address specified in the datagram header and no multihomed support is provided. • IP address list. SCTP will use the IP addresses for its transport address list and provide multihomed support. • A hostname. SCTP resolves the hostname to IP addresses; these addresses are used in the transport address list. TCP and SCTP Bulk Data Flow Once an association has been established, data can be sent between the endpoints. Both TCP and SCTP provide reliable data transmission through similar error- and flow-control algorithms. SCTP can send data using the same APIs as TCP and UDP as well as a new SCTP-specific APIs: • send( ) and recv( ) (TCP and SCTP only). • sendto( ) and recvfrom( ). • sendmsg( ) and recvmsg( ). • sctp_sendmsg( ) and sctp_recvmsg( ) (SCTP only). The following client-server source files (available electronically; see “Resource Center,” page 5) illustrate how to use the APIs with the SCTP protocol to communicate between two applications: • server_recv.cpp and client_send.cpp illustrate how SCTP can be used like a TCP to communicate between a client and a server. • tcpserver_recv.cpp and tcpclient_send.cpp are a simple TCP client and server to illustrate that SCTP and TCP can overlap when compared to server_recv.cpp and client_send.cpp. • server_recvmsg.cpp and client_sendmsg.cpp illustrate how SCTP can send data using scatter/gather I/O APIs. sctp_ sendmsg( ) API is implemented using the recvmsg( ) and sendmsg( ) APIs. • server_sctprecvmsg.cpp and client_ sctpsendmsg.cpp demonstrate how TCP Initialization
int SCTPSock = socket(PF_INET, SOCK_SEQ_PACKET, IPPROTO_SCTP); void* pvSockAddrs; int nAddrCount = 2; pvSockAddrs = malloc( nAddrCount*sizeof(sockaddr_in)); //create addrs struct sockaddr_in* sa; sa = (sockaddr_in*)pvSockAddrs; sa->sin_family = AF_INET; ...
SYN S Create TCB SYN T / ACK S+1
sa = (sockaddr_in*)(pvSockAddrs + sizeof(sockaddr_in)); ... int nRet = sctp_bindx(SCTPSock, pvSockAddrs, nAddrCount, SCTP_BINDX_ADD_ADDR);
Example 3: Using sctp_bindx() to bind to multiple IP addresses. http://www.ddj.com
Create TCB
Dr. Dobb’s Journal, September 2004
ACK T+1
Figure 2: TCP initialization. 35
Endpoint A Start T1-init Timer
Cancel T1-init Timer
Endpoint Z
Init, Enter COOKIE-WAIT & Other Info
INIT ACK, cookie_z, & Other Info
Endpoint A
Destroy temp TCB
Start T1-init Timer, Enter COOKIE ECHO[cookie_z] Cookie Echo Build State TCB Enter Established COOKIE-ACK State Cancel T1-init Timer, Enter Established State
[SHUTDOWN] Check Outstanding Data Chunks
FIN Y
Create temp TCB and cookie_z
To understand the differences between how SCTP and TCP manage data transmission, you need to look at the protocol headers and control messages. TCP designates data being sent to an application by using the [PSH] flag in the TCP header. To ensure that data sent from an endpoint has been received, TCP uses an [ACK] that specifies which [PSH] packets have been received. [ACK]s are sent in response to [PSH] datagrams in two different circumstances: • When data has been received. • The ACK delay has been reached. TCP provides flow control and error control through the use of a receiving window. The receiving window informs the sender of the size of the buffer that is available to receive data. If the sender hasn’t received an [ACK] after filling the receiving window: • The sender must wait for an [ACK] to send new data. • Wait on the retransmission timeout to retransmit unacknowledged data. • A TCP endpoint will also retransmit data if an [ACK] for a specific data packet is continuously sent. This situation occurs if a packet is dropped or damaged. If packets are lost or damaged, an exponential back off is applied to the retransmission timer. The retransmission 36
SHUTDOWN
ACK Y+1 Destroy TCB
FIN WAIT-2 ACK Z+1
Check For Data Chunks
[SHUTDOWN PENDING] No More SHUTDOWN ACK No Data Can More Be Received Data Can Be Received SHUTDOWN COMPLETE
FIN Z Destroy TCB
Figure 4: TCP termination. timeouts are not readjusted until a packet that isn’t being requested for retransmissions [ACK] is received.
Figure 3: SCTP initialization. SCTP APIs allow communication between a client and server using multiple virtual streams.
Endpoint Z
SCTP’s model for bulk data flow uses many of the techniques that TCP has for sending data and flow control. SCTP handles dropped and delayed packets differently than TCP’s ability to manage virtual streams. If data is dropped then the [SACK] sent will contain the transition sequence number (TSN) for the last packet received. The [SACK] packet contains Gap ACK blocks specifying which packets need to be retransmitted. SCTP also uses Gap ACK blocks to report that packets where dropped because buffers filled up and the data can’t be forwarded to the application. When packet loss occurs for one virtual stream, SCTP continues to deliver data on other virtual streams while delaying the affected virtual stream. SCTP supports the ability to deliver data on a virtualized stream in an ordered or unordered fashion to an application. SCTP supports message bundling and fragmentation. SCTP fragments a message if it is larger than the smallest maximum transfer unit (MTU). SCTP doesn’t support refragmenting data chunks. If SCTP messages are smaller than the smallest MTU value, SCTP will bundle packets into a single data chunk to improve performance. When SCTP bundles packets, all control chunks are packed at the beginning of the SCTP packet. Termination Once an association has been established, data can be sent between the endpoints until the association is terminated or severed. The two network APIs that allow for the termination of an open association are Dr. Dobb’s Journal, September 2004
Figure 5: SCTP termination. shutdown(socket,how) and close(socket). The close( ) terminates the SCTP association. shutdown( ) terminates an association differently for SCTP than TCP because SCTP doesn’t have to have closed semantics. See draft-ietf-tsvwg-sctpsocket08.txt for the semantics of shutdown( ). A connection-oriented protocol uses the termination sequence to notify endpoints that data can no longer be received and that system resources should be released. The TCP termination sequence is a fourway handshake. Each endpoint sends a [FIN] and receives an [ACK] from its corresponding endpoint (see Figure 4). TCP allows for one endpoint to terminate its association and the other to still transmit data, resulting in a half open socket. SCTP’s association-termination sequence is a three-way handshake. SCTP doesn’t require a fourth step because it doesn’t support half-open socket communications. When an endpoint is entering the shutdown pending state, it will send all remaining data chunks and the [SHUTDOWN] chunk. When an endpoint receives a [SHUTDOWN], it sends the remaining data chunks and ACKS before the [SHUTDOWN ACK], refusing any new data and enters the shutdown-received state. The endpoint originating the [SHUTDOWN] datagram upon receipt of the [SHUTDOWN ACK] will send a [SHUTDOWN COMPLETE] finishing the shutdown sequence (see Figure 5). Conclusion SCTP is an exciting new transport layer protocol that offers an alternative to TCP. SCTP’s virtual streams and multihomed support can reduce application complexity and increase reliability. The similarities between TCP and SCTP APIs will ease porting and creating new applications using SCTP. DDJ http://www.ddj.com
Continuous Integration & .NET: Part II Continuous Integration and beyond… THOMAS BECK A common practice at Microsoft and some other shrink-wrap software companies is the “daily build and smoke test” process. Every file is compiled, linked, and combined into an executable program every day, and the program is then put through a “smoke test,” a relatively simple check to see whether the product “smokes” when it runs. — Steve McConnell “Best Practices: Daily Build and Smoke Test” IEEE Software, July 1996
W
hile unfamiliar to many developers, Continuous Integration is not a new concept at Microsoft, as is evident by Steve McConnell’s observation. Consequently, in this second installment of a two-part article (see DDJ, August 2004 for Part I), I examine the setup of a version-control system and configuration of a Continuous Integration tool that runs off of the version-control system in the .NET environment. I then integrate these tools into the build process to test for conformance with the Microsoft .NET Framework Design Guidelines, and finally address the issue of code-coverage testing.
CVSNT: Team Builds & Source-Code Control A source-code control system should be in place for all team development efforts. Thomas is a manager with Deloitte. He is currently working on the firm’s Commonwealth of Pennsylvania account and is located in Harrisburg, PA. Thomas can be reached at
[email protected]. http://www.ddj.com
As a matter of fact, this should be one of the first things that is put in place as part of an organized development effort. The reason I’ve waited until now to introduce version-control mechanisms in this article is twofold: • Version control is not critical to understanding the NAnt, NUnit, and NDoc examples in the first part of this two-part article. • Version control is a prerequisite for the next topic of this article — Continuous Integration with CruiseConrol.NET. Both NAnt and CruiseControl.NET integrate well with a variety of version-control systems. However, I use Concurrent Versions Systems (CVS), an open-source version-control system that runs on Linux and Windows. CVSNT is the Windows port of CVS (http://www.cvsnt.org/wiki/). CVS can be accessed from the command line using your IDE (both #Develop and Eclipse support CVS) or one of several popular open-source tools. For example, TortoiseCVS (http://www.tortoisecvs.org/) is a Windows plug-in that lets you access CVS capabilities from within the Windows File Explorer. Likewise, WinCVS (http:// www.wincvs.org/) is similar in appearance to Visual Source Safe’s user interface. When you have completed CVSNT setup, follow these steps to enter your code into version control: 1. Use the CVSNT Control Panel to add a repository named “Testing” underneath the default CVS directory. 2. Make a new module (/5-CVS, in this case) using the Password Server (:pserver) protocol within the repository that you created above. This creates a corresponding /5-CVS folder underneath your module folder. Figure 2 illustrates what this step would look like using TortoiseCVS (Figure 1 appeared in Part I). Dr. Dobb’s Journal, September 2004
3. Add all the contents of the root build directory to the CVS repository. This creates a number of additional CVS directories in your file structure. You should only be checking in source code, not the results of your build.
“You need a tool that produces code-coverage metrics” 4. When you have added the files, you need to do an initial commit of all of the files to CVS. Your code is now in version control and you can proceed to automatically check it in/out using the build program I present here. The changes to the build file to accommodate CVS are relatively minor; see Listing Six (Listings One through Five were presented in Part I). The goal of the changes is to make sure that the most current code is available prior to the build. The build-file changes amount to the addition of the update_source target, which contains the cvs-update NAnt task to update the build folder with the most current versions of our source code from CVS. When your build runs, notice that check-ins are occurring from CVS. You can test this by deleting some of the source files from your local directory and confirming that they are replaced with the versions from CVS prior to the build. The next step is to automate source control access with a continuous integration tool. CruiseControl.NET & Continuous Integration CruiseControl.NET is an open- source tool from SourceForge designed to meld 37
Figure 3: CruiseControl.NET Continuous Integration. Figure 2: Creating a new module with TortoiseCVS. several other open-source building and testing tools and completely automate the build process (http://sourceforge.net/ projects/ccnet/ and http://confluence.pulic .thoughtworks.org/display/CCNet/Download/). In fact, the goal of Continuous Integration tools such as CruiseControl.NET is to automate the reaction to build events (such as source-code modifications). In Figure 3, changes to the project’s source code trigger a build. This build causes the build site to be updated and, if necessary, results in e-mail notification of parties responsible for correcting unit testing errors. Coordination of these activities is the responsibility of CruiseControl. The source code for this section of the article is set up similarly to the source code to the previous example with one exception, namely that you are using two build files instead of one. The first build file (bootstrap) is responsible for updating the code on the build server from CVS, then invoking the main build file (CCNet). The main build file performs all the functionality of the build file from the previous section, with the exception of the CVS access now performed by bootstrap. Perform the initial addition and commit of the necessary files to a new CVS module, 6-CCNet, then perform an initial build by invoking the bootstrap build file. The first step in getting CruiseControl.NET up and running is to create a ccnet.config XML file that drives CruiseControl. This file controls the frequency of the integration cycles, defines the location of the version-control system and NAnt, details what 38
type of (if any) e-mail notifications should be associated with the build, and controls the XML logging that is used as the basis for the build web site. An example ccnet.config file is available electronically; see “Resource Center,” page 5. The file most likely needs to be tailored to accommodate the locations of specific files and programs on your filesystem. When you have the ccnet.config file in place, you can kick off CruiseControl by running the StartCCNet.bat job from the command line. The job should initiate an initial build and then continuously poll CVS until a change is made to the source code, at which point a new build will be started. Setting up the CruiseControl.NET web site is as simple as mapping an IIS virtual directory to the \web subfolder of your CCNet folder. Your continuous integration process is set up and ready to go. FxCop and .NET Framework Design Guidelines With the Continuous Integration process up and ready to go, it’s worth introducing a valuable tool that plugs right into CruiseControl. FxCop (http://www.gotdotnet .com/team/fxcop/) is an application that checks .NET managed code assemblies for conformance with the Microsoft .NET Framework Design Guidelines (http:// msdn.microsoft.com/library/default .asp?url=/library/en-us/cpgenref/html/ cpconnetframeworkdesignguidelines.asp). The FxCop tool tests for conformance in: • Library design. • Localization. • Naming conventions. • Performance. • Security. Dr. Dobb’s Journal, September 2004
Once FxCop is installed, you need to perform two steps: 1. Set up an FxCop task in the NAnt build file (see Listing Seven). 2. Merge the XML output produced by FxCop with the other input for CruiseControl (Listing Eight). Step 1 invokes the FxCop commandline utility using the exec task. A custom NAnt task for FxCop is not yet available. The second step, preparing the FxCop XML output for consumption by CruiseControl is done in the ccnet.config file. In this case, the xmllogger’s merging node (Step 2) is changed as in Listing Eight. After making these changes, create a separate CVS folder for this build and redeploy the modified ccnet.config file. Once you’ve done this and kicked off your build with CruiseControl, you should be able to use the FxCop link on CruiseControl to view your conformance with the .NET Framework Design Guidelines as in Figure 4. You can then correct your code to comply with the guidelines. It is also possible to add custom rules to FxCop to accommodate any special guidelines in place in your particular organization. Clover: How Thorough is Your Testing? With the entire testing and integration process automated, you must consider how well all those unit tests that you’re running are covering the different paths of execution within your code. To determine this, you need a tool that produces code-coverage metrics. Previously, such tools were usually only available as a part of large, usually fairly expensive, http://www.ddj.com
testing suites. Within the last few years, Clover, an inexpensive (though not open source) tool, has emerged that performs Java code-coverage testing, produces detailed reports and integrates with Ant (http://www.thecortex.net/clover/index.html). Originally developed as an internal tool at Cortex to support J2EE development, Clover is currently being ported to .NET and promises to be as powerful a tool for Continuous Integration in the .NET environment as it is in Java. A special limited 30-day licensed version of Clover is available electronically with the source code of this article. This Alpha release version of Clover has some limitations; for instance, only C# is currently supported. If the Java version is any indication, expect significant enhancements to this tool, its reporting functionality, and its integration with standard open-source tools as it moves towards a production- ready product. The process of testing your code coverage using Clover.NET can be best explained using the example of the new Clover target added to our build file; see Listing Nine. This target contains many familiar elements from previous sections and certain elements specific to Clover. Enumerated, the Clover target proceeds as follows:
ough testing is across the different modules of a project. This type of feedback, combined with the unit test results, allows for the most effective refactoring of the code and unit tests.
Figure 4: FxCop .NET guideline compliance report.
Conclusion Establishing a Continuous Integration environment using standard tools was a task that, just a few short years ago, was out of reach on a Microsoft development project. In the past several years, the number
Figure 5: Clover code-coverage report.
1. Execute the program CloverInstr to create an instrumented version of the C# file and a Clover Coverage Database (.cdb). The instrumented C# file contains special “tracers” to facilitate linking back to the coverage database. 2. Compile the instrumented C# program making sure to include a reference to the Clover and CloverRuntime DLLs. 3. Compile and run the NUnit tests against the business object DLL created from the instrumented C# file. 4. Execute the Clover HtmlReporter program to produce the HTML code-coverage report. Figure 5 is a sample report. It is worth paying attention to some of the Clover coverage features in Figure 5. The results include the code coverage for our class (BusObjCS.cs) as a percentage. If you had more than one class in your project, code-coverage results would also be summarized at the project level. The detailed coverage results for our class are below the coverage summary. Simple code highlighting indicates what was covered (line 23, six times in our tests), what wasn’t covered (lines 18 and 24), and what need not be covered (lines 1– 9). This type of visual detail lets you see exactly what is being tested, what’s not being tested, and to achieve a quick overview of how thorhttp://www.ddj.com
Dr. Dobb’s Journal, September 2004
39
and quality of open-source build, testing, documentation, and integration tools supporting the .NET environment has increased drastically. Using the examples in
this article, you should be able to weave together a Continuous Integration environment for your project that pays a hefty return on the comparatively minimal
Listing Six
Listing Seven
<exec program="${fxcop.exe}" commandline="/f:${fxcop.src} /o:${fxcop.out} /s" failonerror="false"/>
Listing Eight <mergeFiles>
c:\NETArticle\07FxCop\cs_build\BusObjTstCS.dllresults.xml c:\NETArticle\07FxCop\cs_build\BusObjCS.ccnetfxcop.xml
Listing Nine
<mkdir dir="${clover.dir}"/> <exec program="c:\program files\cenqua\clover.net\CloverInstr.exe" commandline="src\BusObjCS.cs -d ${clover.dir} -i ${clover.dir}\BusObjCS.cdb"/>
40
amount of time and resources that you need to invest. DDJ
imports="System,System.Data,System.Data.SQLClient, System.Collections.Specialized,System.XML"> <sources> <sources> <exec program="c:\program files\cenqua\clover.net\ HtmlReporter.exe" commandline="-i ${clover.dir} \BusObjCS.cdb -o report -t Test"/>
Dr. Dobb’s Journal, September 2004
DDJ
http://www.ddj.com
RFID Blocker Tags Protecting personal privacy BURT KALISKI
R
adio frequency identification (RFID) tags can be used as an advanced electronic version of the UPC barcodes that identify just about everything we purchase — from groceries to laptops. An RFID tag consists of a small integrated circuit attached to a small antenna and is capable of transmitting a unique serial number a distance of several meters to a reading device in response to a query. Most RFID tags are passive, meaning they do not contain batteries, relying instead on power obtained from the query signal itself. RFID tags are already quite common. Some popular examples include proximity cards used as replacements for metal door keys, theft-detection tags attached to consumer goods such as clothing, and the small dashboard devices for automating highway toll payments. Improvements in cost and size will encourage the rapid proliferation of RFID tags into many new areas of use. For example, a U.S. consumer goods manufacturer has recently ordered half a billion tags for use in retail environments. Over the next few years, manufacturers and retailers plan to embed or attach RFID tags to all types of products, theoretically reducing theft and making automated checkout, product returns, and inventory audits remarkably fast. Burt is chief scientist at RSA Security and director of RSA Laboratories. He can be contacted at
[email protected]. 42
While the many benefits of RFID are attractive, the technology rightfully has some consumers concerned about privacy. The expected surge in use of RFID tags in all aspects of our lives introduces serious threats. The simplest RFID tag broadcasts its ID serial number— that is, its electronic product code (EPC) — to any nearby reader. This presents a clear potential for privacy violations. What happens when a consumer wears his expensive new sneakers with a still functioning RFID tag to the store where he purchased them? Will the store read the tag again and correlate it with his previous purchase? Who’s to stop a retailer (or anyone else) from reading RFID tags on any purchased item, tracking consumer behavior or movements? What’s to protect anyone from secretly being given tags so they can be tracked or spied on by a private detective, spouse, parent, or even by an employer? Privacy has been recognized as a potential barrier in the widespread adoption of RFID technology for some time. Along with other researchers, RSA Laboratories (where I work) is developing RFID designs that promote adoption, while protecting the privacy rights of individual consumers. In this article, I explore a “blocker tag” technique that can make significant strides in the fight for privacy protection in relation to RFID tags. Protecting Privacy The most straightforward approach to privacy protection is to “kill” RFID tags before they are placed in the hands of consumers. A killed tag can never be reactivated. While the “kill tag on purchase” or deactivation approach may address many or even most instances of potential concern for privacy, it is unlikely to fit the bill in all scenarios. There are many applications for which such simple measures would be undesirable despite Dr. Dobb’s Journal, September 2004
the privacy assurances. For example, consumers may wish RFID tags to remain operative while in their possession to facilitate merchandise returns or perhaps to enable a future “electronic medicine cabinet” to verify that they have the correct prescriptions.
“An RFID reader is really only able to communicate with a single RFID tag at a time” With another approach, an RFID tag may be shielded from scrutiny using what is known as a “Faraday Cage”— a container made of metal mesh or foil that is impenetrable by certain frequencies of radio signals. Small-time thieves are already using foil-lined bags in retail shops to avoid detection when shoplifting. In the same spirit, currency notes of the future with active RFID tags could be protected with foil-lined wallets. However, RFID tags will inevitably be deployed in a vast range of applications that cannot be placed conveniently in metal containers. Faraday cages thus represent, at best, a partial solution to consumer privacy. Active jamming, a low-tech means of shielding RFID tags from “view,” is another http://www.ddj.com
High-Tech Privacy Protection A more high-tech approach would involve the use of cryptographic methods. These techniques are exceptionally challenging to design, given the cost constraints associated with the basic RFID tag. Protocols based on public-key cryptography can readily address privacy concerns, but are likely to be too expensive to implement universally in RFID
method of protecting privacy. In this scenario, consumers carry a device that actively broadcasts radio signals to effectively block and/or disrupt the operation of any nearby RFID readers. This approach may be illegal — at least if the broadcast power is too high — and is a most assuredly crude approach, possibly causing severe disruption of all nearby RFID systems (even legitimate applications).
tags in the foreseeable future. Protocols based on symmetric cryptography may become practical to implement sooner, but they must be carefully designed to preserve privacy. Consider that for a reader to determine which symmetric key to use when communicating with an RFID tag, the tag must somehow identify the key to the reader. This process itself might still enable the RFID tag to be tracked.
Blocker Tag Details ARI JUELS
T
he blocker tag devised by Ron Rivest, Michael Szydlo, and myself is itself meant to be a simple, passive RFID device, similar in cost and form to an ordinary RFID tag. However, a blocker tag performs a special function. When a reader attempts to scan RFID tags that are marked as “private” (in a manner to be discussed below), a blocker tag jams the reader. More precisely, the blocker tag cheats the tag-to-reader communications protocol in such a way that the reader sees many billions of nonexistent tags and, therefore, stalls! One of the chief design challenges in RFID systems is the prevention of radio collisions among messages transmitted by tags. If all tags were to broadcast their serial numbers simultaneously, the result would effectively be noise. That is, it would be hard for the reader to disentangle the many overlapping signals. To resolve this problem, reader-to-tag RFID communication protocols impose a careful scheduling on tag messages. One such protocol is tree walking. In this protocol, the space of n-bit tag serial numbers is viewed in terms of a binary tree of depth n. If you imagine each left branch as being labeled “0” and each right branch labeled “1,” then a path from the root to a given node at depth k specifies a k-bit serial-number prefix. Hence, each leaf of the tree corresponds to a unique tag serial number. Tags generally carry identifiers of at least 96 bits in length. The tree representing serial numbers, therefore, has a depth of at least 96. To determine which tags are present, a reader performs a kind of depth-first search on the tree. It starts at the root of the tree, asking all tags to broadcast the
Ari is Principal Research Scientist at RSA Laboratories and can be contacted at
[email protected].
http://www.ddj.com
first bit in their serial numbers. If the reader receives only a “0” transmission, it knows that all tag serial numbers begin with a “0,” and recurses on the left subtree; likewise, if the reader receives only a “1,” it recurses on the right subtree. If the reader detects a broadcast collision (that is, both a 0 and a 1), it recurses on both subtrees for the node (see Figure 1). At any given internal node of the tree, the reader performs this same operation; first, though, it transmits a command that causes only tags in the corresponding subtree to respond to its query. Once the reader has completed the process of traversing the tree and determined which tags are present, the process can communicate individually with tags by addressing them using their serial numbers. (This process of identifying individual tags is often called “singulation.”) In brief, then, to determine tag identities, the reader repeatedly asks subsets of tags to broadcast the bit value of their serial numbers in a particular position. The way that the blocker jams the reader is simple: When the reader asks a subset of tags to transmit their next bit, the blocker transmits both a 0 and a 1, simulating a broadcast collision. The result is that the reader believes that all possible tags are present. Since serial numbers are generally at least 96 bits in length, this means that a blocker can
cause a reader to perceive more than an octillion (1027 ) tags — in other words, far too many to count! For a blocking system to work productively, the blocking process must be selective. A blocker tag should only jam a reader if the reader tries to scan tags marked “private.” To achieve this, you can employ a system of zoning, in which half of the serial-number tree is regarded as “public” and the other is marked as “private.” For example, the left half of the tree, consisting of all serial numbers starting with a 0, might be treated as a private zone, while the other half is treated as a public zone. The first bit of any serial number in this case would indicate the public or private status of a tag. A blocker would naturally simulate collisions only in the “private” portion of the tree. In other words, a blocker tag would never prevent scanning of “public” tags in the left half of the tree, but would always do so in the right half of the tree. To change the zone of a tag from public to private in, say, a supermarket, it would suffice to flip the first bit of the serial number. (Like the “kill” command, this operation would require PIN protection to defend against malicious rezoning.) Many variant ideas are possible here. For instance, it is possible to introduce multiple zones with different privacy policies. DDJ
0 00
000
001
1
01
010
10
011
100
101
11
110
111
Figure 1: Tree-walking example: Solid circles at leaves represent tags. Subtrees with tags are searched recursively; the dark line shows the path of depth-first search to the leftmost tag, denoted 001. Open circles indicate collisions, where tags occur in both left and right subtrees.
Dr. Dobb’s Journal, September 2004
43
Conventional cryptography thus does not immediately suggest a generalpurpose, practical solution to the privacy concerns with RFID tags, but research into new approaches is showing promise. One approach is to go beyond protecting the data — the traditional province of cryptography — and instead look directly at the tag-to-reader interactions itself. Blocker Tags An RFID reader is really only able to communicate with a single RFID tag at a time. If more than one tag responds to a query by the reader, the reader detects a “collision” and cannot accurately read the information transmitted by the tags. The reader and RFID tags then need to engage in some sort of protocol so the reader can communicate with the conflicting tags one at a time. Such a protocol is called a “singulation protocol.” This is the premise behind RSA Laboratories simple “blocker tag” scheme for RFID tag privacy protection (for more information, see the accompanying text box entitled “Blocker Tag Details”). Blocker tags selectively exploit the standard tree-walking singulation protocol. The blocker tag does not actively engage in jamming. Rather, by participating in the tag-reading process in a noncompliant
44
manner, the blocker initiates passive jamming. When carried by consumers, blocker tags thus “block” RFID readers. To avoid
“The soft blocker is a low-cost method for honest merchants to add privacy protection to their systems” interfering with the legitimate business uses of RFID tags, a blocker tag blocks selectively by jamming only selected subsets of ID codes, such as those in a designated “privacy zone.” We believe that this approach, when used with appropriate care, provides an attractive alternative
Dr. Dobb’s Journal, September 2004
for addressing privacy concerns raised by the widespread use of RFID tags in consumer products. It is possible that the blocker tag concept be used for malicious purposes, for instance, as a tool for mounting denial-ofservice attacks. Such a blocker tag might shield either the full spectrum of serial numbers from reading or might target a particular range; for example, the set of serial numbers assigned to a particular manufacturer. A blocker tag of this form might be used to disrupt business operations or to help perpetrate petty theft by shielding merchandise from inventory control mechanisms. However, mechanisms — such as detecting blocker tags by monitoring for reports of unusually high numbers of tags — can be put in place to protect against fraudsters. Moreover, by design and intent, the blocker tag solutions that RSA Laboratories is developing are limited to privacy protection and do not facilitate such malicious uses. Our blocker tag approach to RFID privacy protection is particularly attractive because of the low cost associated with the implementation of such an effective privacy solution. • Ordinary consumer-product RFID tags may not need to be modified at all,
http://www.ddj.com
other than to have the ability to indicate whether they have been purchased or not (that is, whether they are in a privacy zone). The RFID tags don’t need any expensive cryptography. • Blocker tags themselves can be very affordable because they consist essentially of just one or two standard RFID tags, with minimal circuit modifications. If a standard RFID tag can be made for five cents, a blocker tag can probably be manufactured for roughly 10 cents in quantity. • The infrastructure behind such an implementation is manageable — limited to a PIN for each standard RFID tag that authorizes changes to privacy zones. Already, such PIN management is needed for the default remedy to privacy concerns, which is tag deactivation, to ensure that it is difficult for an unauthorized party to deactivate a tag. Blocker tags build on the same infrastructure, while leaving the option of continuing to use a tag after the point of sale, rather than killing it.
like the Platform for Privacy Preferences protocol (P3P) for privacy on the Web. The soft blocker is a low-cost method for honest merchants to add privacy protection to their systems. Also, because it is in software, it supports a flexible set of privacy policies. Conclusion The use of selective blocking by blocker tags lets consumers choose when to hide certain RFID tags from scanning, and when to reveal those same tags for scanning. By allowing RFID prefixes to be rewritten, tags can be moved in or out of privacy zones protected by various blocker tags. The scientists at RSA Laboratories believe that blocker tags are a potent and useful tool for protecting con-
sumer privacy, and recommend their incorporation into the portfolio of tools for building confidence into the promising new RFID infrastructure. For More Reading A. Juels, R.L. Rivest, and M. Szydlo. “The Blocker Tag: Selective Blocking of RFID Tags for Consumer Privacy” in 8th ACM Conference on Computer and Communications Security: ACM Press, 2003 (http:// www.rsasecurity.com/go/rfid/). A. Juels. “Soft Blocking: Flexible Blocker Tags on the Cheap.” Unpublished Manuscript. 2003. (http://www .rsasecurity.com/go/rfid/). DDJ
The RxA Pharmacy Demo At the 2004 RSA Conference, RSA Laboratories publicly demonstrated the use of blocker tags as a method for protecting consumer privacy. The demonstration took the form of a mock pharmacy, whose visitors received RFID-tagged prescription bottles filled with jelly beans offering “tranquility,” “wisdom,” and “happiness.” (“Wisdom” was the most popular, favored by about 40 percent of visitors.) After explaining the initial tradeoff between convenience and privacy engendered by RFID tags, the mock “pharmacists” then showed how technologies such as blocker tags can help, by enclosing the RFID-tag bottle in a paper prescription bag, affixed to which was a demonstration version of the blocker tag. When a purchased bottle was scanned apart from the bag, the “checkout” display indicated the bottle’s identifier (and if the prescription had been purchased, the visitor’s name or pseudonym). But when the bottle and bag were scanned together, the display read “blocked.” The demonstration offered the same “customer experience” as with the “full” blocker tag described earlier, but used another type of tag that RSA Laboratories is working on — the “soft” blocker. Although it should be possible to implement the full blocker tag in fairly straightforward fashion, the soft blocker is even easier to implement because it is a standard RFID tag. Rather than interfering with the tagto-reader protocol, though, the soft blocker relies on the reader or the application to enforce a privacy policy — somewhat http://www.ddj.com
Dr. Dobb’s Journal, September 2004
45
Optimizing Pixomatic For Modern x86 Processors: Part II Challenging assumptions about optimization MICHAEL ABRASH
I
n the first installment of this three-part article, I introduced the optimization challenges we faced with Pixomatic, the 3D software rasterizer that Mike Sartain and I developed for RAD Games Tools. This month, I start by examining the “welder”— a streamlined compiler custom designed to compile code very quickly— and look at issues such as pixel pipeline code. That said, the welder doesn’t exactly compile code. It might be better described as splicing together prewritten, hand-tuned segments of assembly language, performing fixups (like branch targeting), and conditional code generation (like selecting between texture wrapping and clamping) according to pseudocode commands embedded directly in the code stream. The bulk of the code is simply copied directly from the code stream to the execution buffer and no sophisticated analysis is performed — at worst, a few pseudocode conditionals are executed — so the process is very fast.
Michael is a developer at RAD Games Tools and the author of several legendary programming books, including Graphics Programming Black Book. He can be contacted at
[email protected]. 46
In the end, the overhead of welding proved not to be a problem at all; we have yet to see a profile where it reaches even 1 percent of the total time. Once again, it turned out that we had overanalyzed and overoptimized up front, instead of just trying it out and seeing how it worked. We also use welding in some other key places, such as handling arbitrary vertex formats, but by far the biggest application of it is in the pixel pipeline. The welded pixel pipeline code is a good example of circumstances in which good assembly code can still beat highlevel compiled code by a wide margin. In general, high-level compilers are quite good at general-purpose x86 code, especially given CPUs that can do out-oforder processing, such as the Pentium III and Pentium 4. For general-purpose code, it’s hard to beat a high-level compiler by a significant amount, and I have had the experience a couple of times recently of rewriting C code in assembly and not getting any faster at all. I should mention, however, that we recently did a pass through the C code for the Miles Sound System for the PlayStation 2, hoisting invariants out of loops and otherwise compensating for relatively poor compiler optimization to the tune of a 30 percent speedup. When we propagated the changes back to Windows, we found we had gotten nearly a 10 percent speedup. Since there were a lot of changes, I’m not sure what the key was, but I suspect it was a combination of turning multidimensional array accesses into pointer accesses and using local pointers so the compiler could tell there was no potential for aliasing. Where assembly can win big — by two to four times — is with code that’s Dr. Dobb’s Journal, September 2004
amenable to MMX and SSE because of the four-way parallelism they support and because of the extra registers they make available. True, MMX and SSE can be accessed via compiler intrinsics, but in my experience, those intrinsics rarely generate good code and often actually result in
“The welded pixel pipeline code uses MMX but not SSE registers” worse performance than normal compiled code. All those complications go away with assembly, and the full power of MMX and SSE can be tapped. On top of four-way parallelism, SSE and MMX also triple the number of available registers, and each of the new registers can contain multiple values; that’s a huge win for a processor as register constrained as the x86. In fact, the MMX register set is large enough so that no dynamic register allocation is needed in the Pixomatic pixel pipeline, and no spilling to memory is required, except in a few cases involving bilinear filtering or 24-bit z buffers with stencil. The ability to have a static register allocation not only improved performance but also greatly simplified the welder because all features can be http://www.ddj.com
(continued from page 46) turned on/off independently of one another with no register-allocation complications. The welded pixel pipeline code uses MMX but not SSE registers. This is partly because the pixel pipeline is entirely fixed point for performance reasons, and partly because integer SSE2 instructions are currently half the speed of MMX instructions. (In exchange, integer SSE2 can do twice as much work as MMX per instruction, but we couldn’t figure out any way to take advantage of that in the pixel pipeline.) Mostly, though, we didn’t use SSE registers in the pixel pipeline because we were able to do almost everything we wanted to without them, and it simplified things considerably to not have to support two different pipelines, one with SSE registers and one without. (We do, however, weld enhanced MMX instructions that were added as part of SSE— especially pshufw — into the pixel pipeline when they’re supported, by using processor feature conditionals in the welder.) We would have liked to have supported three or more textures, which SSE2 integer registers would have helped with, but then we would have had the problem of how to support that feature on nonSSE2 platforms. Table 1 shows the pixel pipeline register allocation. All scratch registers are used for various purposes. Not only are all eight MMX registers in use, but so too are all eight general-purpose registers — including ESP, since the code requires no stack. Many people don’t realize that under Windows it’s safe to use ESP as a general-purpose register because the OS switches to a system stack when fielding interrupts and context switching. A
R
G
B
63
0
Figure 1: MMX pixel format. Each field has 8 integral bits; the number of fractional bits varies throughout the pipeline. EAX EBX ECX EDX ESI EDI EBP ESP MM0 MM1 MM2 MM3 MM4-MM7
Scratch register Z-buffer pixel address Loop counter Texture 0 pointer Span-list pointer Pixel-buffer pixel address Texture 1 pointer 1/z Texture 0 coordinates (u0, v0) Texture 1 coordinates (u1, v1) Gouraud color Specular color Scratch registers
Table 1: Pixel pipeline register allocation. 48
(Note, though, that the code is no longer multithread-safe unless thread-local storage is used because ESP must be stored somewhere other than the stack so it can be restored at the end of the routine.) Register allocation is one reason why we ended up supporting only two textures; as you can see, there were no more registers to hold additional U and V coordinates and texture pointers. I’m going to digress for a minute and move up one level to show even more intensive register use. The welded pixel processing code rasterizes a set of horizontal spans, each between 1 and 16 pixels in length. That set of spans comes from the span-generation code, which calculates all the parameters for each span, including the perspective-correct texture coordinates at each end. (The pixel pipeline itself just interpolates U and V linearly; while this introduces some error, in practice it’s indistinguishable from perfect perspective correction, and, because it avoids having to do a divide per pixel, is much faster.) As I mentioned earlier, there are three versions of the span-generation code. The most interesting by far is the SSE version, which uses not 16 but 23 registers plus the stack pointer, as in Table 2. And, while the span generation code isn’t terribly register constrained, it could still have used a few more registers had they existed. Pixel Pipeline Performance Challenges There were two key performance areas that we had to address in the pixel pipeline: pixel processing and texture mapping. Once we’d decided to use MMX, pixel processing fell out nicely because there aren’t too many possible ways to use MMX to work with pixels. Figure 1 shows the pixel format Pixomatic uses. Each color component is stored as a 16-bit fixed-point value; the placement of the fixed point varies, depending on what the last and next operations are. (The variation is due to the alignment requirements of multiplication, which returns only the high or low 16 bits of the result, and also the need at times to perform saturating operations and to clamp results.) At all times, however, color values contain eight integral bits, so processing is always of 8-bit color components or better. MMX mapped quite well to pixel processing. It would have been nice to not have had to fiddle with bit placement to get multiplication to work, and it would have been even nicer to have been able to protect certain fields on any operation so that RGB could be modified without affecting alpha and vice versa. Still, those were minor inconveniences, and between Dr. Dobb’s Journal, September 2004
the parallelism, clamping, faster multiplies, and additional, larger registers, I’d estimate that MMX enabled us to perform pixel processing something like five times faster than would have been possible otherwise. In fact, the pixel pipeline is the one part of Pixomatic for which there is no fallback C code. MMX, driven by welded code, is required because performance would otherwise be so poor as to make Pixomatic useless. The other big performance aspect of the pixel pipeline is texture mapping, and this was the toughest challenge. In texture mapping, U and V (the horizontal and vertical texture coordinates) each have to be linearly interpolated, with sufficient fractional bits to allow for subtexel precision, and then the integral parts of U and V (after scaling up to the texture dimensions), have to be butted together and gotten into a general-purpose register so they can be used to address the texture. The desire to process U and V in parallel makes texture mapping a natural for MMX, but the part about butting the integral parts together is not a good fit. MMX is good at doing parallel processing of independent components, but poor at shuffling data around. This is particularly true with any granularity less than 16 bits, and the granularity for texture mapping varies from 0 to 12 bits, depending on the texture size. I beat my head against this for a while, but wasn’t able to come up with anything I was happy with. Finally, Jeff Roberts said that in cases like this on other chips, he’d found various generalized pack/shift/shuffle instructions to be the way to go, and he tended to think of the MMX pack, unpack, and especially pshufw instructions as limited versions of those. I’m not exactly sure why, but that immediately broke the logjam; Listing One shows the entire sequence used to handle texture mapping, from start to finish, in just six instructions. The first instruction causes the texture coordinates to wrap. The second, third, and fourth instructions store the combined U and V in eax. The fifth instruction loads the texel into mm7, and the last instruction advances U and V to the next texel. The key here is storing U and V so that they have enough fractional bits for subtexel accuracy, yet can be butted together with just one instruction, then right justified with a shift. Figure 2 shows how that works. In Figure 2, the code is working with a 256×256 texture, so the texture is addressed with 8-bit integer U and V values. V is stored so that its integral part is right justified to bit 48, and U is stored so that its integral part is left justified to bit 31. This allows a pshufw to butt the two integral parts together at bits 15 and 16, after which the combined VU can be right http://www.ddj.com
(continued from page 48) justified at bit 0 with a psrld; then it’s a simple matter to copy the result out to a general-purpose register and use it to address the texture. This is using MMX as it was not intended to be used. In the past, I’ve written about the importance of having a flexible mind when optimizing, and this is an excellent example of that. It’s also a good example of how you need to step back from your work and think about different approaches every so often — or get someone else to do it for you, as Jeff did for me. Remember, the best optimizer is between your ears — but you can’t weigh it down with preconceptions if you want it to do its best work. Pixel Pipeline Code Keeping all that background in mind, Listing Two shows the welded pixel pipeline for the case of one point-sampled texture modulated with Gouraud shading, with z buffering. The top part is the stepping of the interpolators; we jump into the middle of the loop for the initial iteration, to save doing a wasted stepping at the end of the last time through the loop. (This also
63
00VV.vvvv UU.uuuuuu 48 47 32 31 16 15 0 PSHUFW
63
48 47
00VV UU.uu 32 31 16 15 0 PSRLD
63
48 47
0000VVUU 32 31 16 15 0
Figure 2: Conversion from fixed-point (U,V) coordinates to a texture address. EAX EBX ECX EDX ESI EBP EDI ESP MM0 MM1 MM2 MM3 MM4 MM5-MM7 XMM0 XMM1 XMM2 XMM3 XMM4 XMM5 XMM6-XMM7
Scratch register Scanline length 1/z Scratch register Pixel-buffer pixel address Span list pointer Z-buffer pixel address Stack pointer Previous span (u0, v0) Previous span (u1, v1) Gouraud GB components Gouraud AR components Specular GB components Scratch registers 1/w u0,v0,u1,v1 1/w2 Left edge 1/w2 Left edge 1/w Left edge u0, v0, u1, v1 Scratch registers
Table 2: Span generation register allocation. 50
makes it possible to align the top of the loop without executing any nop instructions.) This is followed by the z compare, then the texture mapping code, the Gouraud code, the packing and writing of the final pixel value, and the loop control. At 20 instructions per pixel, it’s pretty compact for all it does, reflecting the good correspondence between MMX and this particular scenario. Next, Listing Three shows the welded pixel pipeline for the case of one bilinear filtered texture, plus Gouraud shading. And here we see what happens when MMX doesn’t correspond so well to a scenario. It would sure be nice to have a hardware module that did bilinear filtering because there’s just no elegant way to do it in software, despite heavy optimization and some fairly clever tricks. That reminds me of an important lesson we learned while doing Pixomatic: It’s almost impossible to know exactly what’s going on with the performance of your code nowadays. The out-of-order processing of the Pentium 4 is so complex and the tools available for analyzing performance are so inadequate (alas, VTune has regressed in this respect), that to a large extent all you can do is try a lot of approaches and keep the one that runs fastest. I mention this in the context of the bilinear filter because that was where that lesson was driven home. You see, I came up with a way to remove a multiply from the filter code — and the filter got slower. Given that multiplication is slower than other MMX instructions, especially in a long dependency chain such as the bilinear filter, and that I had flat-out reduced the instruction count by one multiply, I was completely baffled. In desperation, I contacted Dean Macri at Intel, and he ran processor-level traces on Intel’s simulator and sent them to me. I can’t show you those traces, which contain NDA information, but I wish I could because their complexity beautifully illustrates exactly how difficult it is to fully understand the performance of Pentium 4 code under the best of circumstances. Basically, the answer turned out to be that the sequence in which instructions got processed in the reduced multiply case caused a longer critical dependency path — but there’s no way you could have known that without having a processor-level simulator, which you can’t get unless you work at Intel. Regardless, the simulator wouldn’t usually help you anyway because this level of performance is very sensitive to the exact sequence in which instructions are assigned to execution units and executed, and that’s highly dependent on the initial state (including caching and memory access) in which the code is entered, which can easily be Dr. Dobb’s Journal, September 2004
altered by preceding code and usually varies over time. Back in the days of the Pentium, you could pretty much know exactly how your code would execute, down to the cycle. Nowadays, all you can do is try to reduce the instruction count, try to use MMX and SSE, use the cache wisely and try to minimize the effects of memory latency, then throw stuff at the wall and see what sticks. Speedboy We did come up with an interesting tool for dealing with the uncertainties of Pentium 4 optimization, which we nicknamed “Speedboy.” You insert a segment of assembly code that you want to optimize into Speedboy’s timing loop, add additional information to indicate which instructions are directly dependent on the results of which other instructions, and kick off the run. Speedboy then times all valid permutations of the code and lets you know which arrangement is fastest. Speedboy does in fact work as advertised but is not as useful as we’d hoped, particularly for our welded pixel processing code. The first problem is that it’s tedious and error prone to manually determine and enter the dependencies. Often, it would turn out that Speedboy’s choice for fastest code didn’t actually work properly because we’d missed a dependency. That could be fixed by writing a code analyzer to determine dependencies, but that didn’t seem worth doing once we came to understand the second and third problems. By way of introducing the second problem, let me tell you the story of the first BSP compiler I ever wrote. I got it working and then I thought, heck, computer time is free, why not have it optimize the BSP tree while I’m at it? So I added code to have it try all possible configurations and started a new compiler run. My polygon set was nothing like a real game level; it contained only 20 polygons, so I figured the run would finish in a few seconds at most. After half a minute, however, I started to wonder, and after half an hour or so, I decided to do a few calculations. It turns out that the order of a bruteforce BSP optimizer is roughly N!. Even with only 20 polygons, that works out to about 2 times 10 to the 18th. If we assume that each tree takes one microsecond to analyze (in fact it took a good bit longer than that), then it would take more than 70,000 years to optimize my little toy level. Bump it up to a big level — say, one with 30 polygons (real levels, of course, have thousands or even millions of polygons) — and I’d have been waiting for my answer well into the heat death of the universe. And I mean that http://www.ddj.com
literally; we’re talking 8 billion billion years here. I’d imagine you can guess where I’m going with this. Speedboy’s order is somewhat less than N! — but, unless there are a lot of dependencies, not all that much less. Sequences of 10–20 instructions work great; sequences of 40 or more tend to make you wish that either computers were a lot faster or that reincarnation was a viable option, depending on the number of dependencies in the code. Some of our critical code segments are short enough to run through Speedboy, but a lot of them aren’t; for example, the code for one bilinear filtered texture with Gouraud shading would probably take longer to finish than my BSP optimizer running on a 30-polygon level.
Worse still was the third problem. If you’ll recall, I mentioned earlier that the performance of code on the Pentium 4 is highly sensitive to the exact sequence of instruction execution. Well, in welded code, the exact instruction sequence is different for every one of many trillions of pipeline configurations. Furthermore, because the loops iterate only 1 to 16 times, performance can be greatly affected by the exact state of the processor when the code is entered, which varies depending on the render state and the shape and size of the triangle. Consequently, the results reported by Speedboy tended to be extremely case specific. Often, Speedboy would find an optimization that would speed up a specific case by as much as 10 percent in the test bed, but when we
Listing One pand pshufw psrld movd movd padd
mm0,[WrapUV0Mask] mm5,mm0,0Dh mm5,[WrapUV0RightShift] eax,mm5 mm7,[edx+eax] mm0,[UV0Step]
Listing Two LoopTop: add adc paddsw paddd cmp ja mov pand pshufw psrld movd movd movq punpcklbw psllw pmulhw packuswb movd LoopBottom: inc jne
esp,dword ptr [_RotatedFixed16ZXStep] ; stepping esp,0 mm2,mmword ptr [_argb7x_GouraudXStep] mm0,mmword ptr _Spans+20h[esi] sp,word ptr [ebx+ecx*2] ; z buffering LoopBottom word ptr [ebx+ecx*2],sp mm0,mmword ptr [_TexMap] ; texture mapping mm5,mm0,0Dh mm5,mmword ptr [_TexMap+28h] eax,mm5 mm7,dword ptr [edx+eax*4] mm6,mm2 ; Gouraud shading mm7,dword ptr [_MMX_0] mm7,1 mm7,mm6 mm7,mm7 ; pixel pack/write dword ptr [edi+ecx*4],mm7 ecx LoopTop
paddw pshufw psrlw psllw pmulhw pmulhw paddw paddw packuswb movq punpcklbw psllw pmulhw packuswb movd LoopBottom: inc jne
put it into Pixomatic, the benefit would vanish completely or would show up in that one case, but not in similar cases. So, in the end, Speedboy wasn’t much help with the welded pixel pipeline code. On the other hand, it was useful in nonwelded, high-repetition cases like the 2D blit code. On balance, Speedboy was a cool idea and modestly useful, but not a big win for Pixomatic. Next Month I’ll wrap up in next month’s installment with an examination of out-of-order processing, branch prediction, and how HyperThreading technology fits into the mix. DDJ
mm6,mm7 mm7,mm0,0AAh mm7,6 mm5,6 mm4,mm7 mm7,mm5 mm6,mm4 mm7,mm6 mm7,mm7 mm6,mm2 mm7,dword ptr [_MMX_0] mm7,1 mm7,mm6 mm7,mm7 dword ptr [edi+ecx*4],mm7 ecx LoopTop
DDJ
; loop control
Listing Three LoopTop: add adc paddsw paddd cmp ja mov pand pshufw psrld movd movd pslld add and paddw psrld movq psrld pand movd movd punpcklbw movd punpcklbw pshufw add and punpcklbw movq movd punpcklbw psubw psubw psubw psubw pmullw psraw pmullw
esp,dword ptr [_RotatedFixed16ZXStep] esp,0 mm2,mmword ptr [_argb7x_GouraudXStep] mm0,mmword ptr _Spans+20h[esi] sp,word ptr [ebx+ecx*2] LoopBottom word ptr [ebx+ecx*2],sp mm0,mmword ptr [_TexMap] mm6,mm0,0Dh mm6,mmword ptr [_TexMap+28h] eax,mm6 mm7,dword ptr [edx+eax*4] mm6,mmword ptr [_TexMap+28h] eax,dword ptr [_TexMap+0F4h] eax,dword ptr [_TexMap+0F8h] mm6,mmword ptr [_TexMap+40h] mm6,mmword ptr [_TexMap+28h] mm4,mm0 mm4,mmword ptr [_TexMap+48h] mm4,mmword ptr [_MMX_0x003F003F003F003F] mm5,dword ptr [edx+eax*4] eax,mm6 mm7,dword ptr [_MMX_0] mm6,dword ptr [edx+eax*4] mm5,dword ptr [_MMX_0] mm4,mm4,0 eax,dword ptr [_TexMap+0F4h] eax,dword ptr [_TexMap+0F8h] mm6,dword ptr [_MMX_0] mmword ptr [_MMX_UFrac],mm4 mm4,dword ptr [edx+eax*4] mm4,dword ptr [_MMX_0] mm6,mm7 mm4,mm5 mm5,mm7 mm4,mm6 mm6,mmword ptr [_MMX_UFrac] mm6,6 mm4,mmword ptr [_MMX_UFrac]
http://www.ddj.com
Dr. Dobb’s Journal, September 2004
51
Band-In-A-Box, Finale, & MusicXML Converting file formats using an XML dialect AL STEVENS
W
hen I retired the DDJ “C Programming” column in 2003, I thought my coding days were just about over and I would be a fulltime jazz musician and teacher. Computers would be only for music applications and, whenever possible, I would use existing software. I wouldn’t write a program unless I couldn’t find one to do what I needed. Given all the music applications for Windows and Linux, I figured I’d never have to write code again. My web site (http://www.alstevens.com/) contains little to indicate that I made my living as a programmer. Not that I didn’t enjoy programming. But I have other things to do now and all you dot-netters, see-sharpers, and ex-em-ellers can carry the banner while I pursue a different muse. I didn’t realize, however, that as I got into using my computer only for music applications, I’d find more problems waiting to be solved. This article is about one such solution — how to convert Band-In-A-Box song files into Finale notation files by using MusicXML as a porting medium. XML & MusicXML Most programmers know what XML is. If you program Internet applications, you
Al is DDJ’s senior contributing editor and a professional musician. He can be contacted at
[email protected]. 52
can’t escape it. XML is becoming the language of the Internet. A text-based markup language to describe document content and structure, XML is, among other things, the next-generation HTML, but its capabilities go far beyond describing web pages. XML can describe the architecture of virtually any kind of structured information to be exchanged between platform-independent applications. XML has been used, for example, to define the structure and control the content of relational databases. The World Wide Web Consortium (http://www.w3.org/) maintains XML and its standardization, and you can read all about XML at http://www .w3.org/TR/2004/REC-xml-20040204/. MusicXML (http://www.musicxml.org/) is a dialect of XML that describes music notation. All those cryptic lines and symbols that musicians read are implemented in XML Document Type Definition (DTD) files. The complete MusicXML DTD is at http://www.musicxml.org/dtds/. MusicXML could and should become a universal language for music applications to exchange data — if only application developers would buy into the concept of interchangeable data files. But most music notation applications — and there are many — use proprietary file formats and closed architectures. Developers do not open their file architectures lest they facilitate the porting of scores to competing notation applications. That would never do. Composers, arrangers, and musicians have other priorities, however, and we need a way to exchange data between music applications. If the Internet is to become the computing platform of the 21st century, it needs common data formats for every kind of document, and applications that aim to be Internet aware are goDr. Dobb’s Journal, September 2004
ing to have to abandon the closed architecture mentality to achieve that goal. Eventually, browser plug-ins will render MusicXML files as music notation. Until then, you need a MusicXML-friendly notation application to view the files in other than text format, and music notation on web pages continues to be portrayed only with graphical image files.
“MusicXML is a dialect of XML that describes music notation” MIDI for Notation Import/Export Rendering scores is one thing. Exchanging score data is another. Prior to MusicXML, the main way to move scores between music notation programs was to export them as Musical Instrument Digital Interface (MIDI) packets in Standard MIDI Format (SMF) files from one application and import those SMF files into the other. Most notation programs support SMF import/export. You can order the MIDI specification from http://www.midi.org/. Many books about MIDI describe the specification, too. SMF is the file format for storing MIDI data. You can find the SMF specification at http://help-site.com/local/midi.txt. http://www.ddj.com
Using MIDI to exchange notation gives less than perfect results. Much music notation has no standard representation in MIDI, a protocol that encodes music performances as event packets. MIDI packets encode what notes to play, how loud to play them, when to play them, what instruments to play them on, and what devices play those instruments’ sounds. Music notation does some of that, too, but notation was designed centuries ago for people to read and write. MIDI was designed decades ago for machines to read and write. Notation includes symbols and text meant to be interpreted by people in the context of rehearsals and performances, and these data include rehearsal numbers, chord symbols, endings, repeats, codas, cues, slurs, dynamics, expression, who’s soloing and who’s tacit, and so on. Many of these symbols are notational conveniences not represented in the typical MIDI sequence. Of the items on the list I just cited, the ability to move chord symbols between music notation applications is the one most relevant to the problem I address here. Because of these notational requirements, when you use an SMF file to export a score from one notation application to another, you must apply a lot of manual fix-up to restore the imported score to its original configuration. MusicXML addresses this problem. It contains markup tags for everything imaginable in a musical score. A score exported to MusicXML from one application retains virtually all its information when imported into another application. The only thing that might differ is how the two applications render the score with respect to music fonts, page layout, and so on. If you want to convert an SMF file into music notation, the best program for the job is MidiNotate (http://www.notation .com/). MidiNotate, however, is not a music notation editor. It doesn’t let you do much in the way of correcting the notation, and it does not export to MusicXML, so you can’t easily move MidiNotate’s notation data into a notation editor program. Scanning for Notation Import/Export Some notation programs let you scan printed music and convert the scanned bitmap into the application’s notational format. Likewise, programs such as PhotoScore (http://www.neuratron.com/photoscore .htm) and SharpEye (http://www.visiv.co .uk/) convert scanned scores into MusicXML, which you can then import into some notation editors. Any program that can print music notation can indirectly generate a graphical bitmap. I do it by printing to a file in http://www.ddj.com
PostScript format and using GSView (http:// www.ghostgum.com.au/) to convert the file to a TIF. I convert the TIF by using SharpEye, which treats the TIF as a scanned image and converts it to MusicXML. These programs work well, but they do not convert one item of notational information that I require in my work. They do not convert chord symbols. Band-In-A-Box I regularly use a program called Band-InA-Box for Windows (http://www.pgmusic .com/). If you are a musician, you’ve probably heard of it. Band-In-A-Box generates automatic musical accompaniments. It uses MIDI technology to produce accompaniments with drums, bass, piano, and strings. You enter a sequence of chord symbols and select a playback style, and Band-InA-Box does the rest. Figure 1 shows the Band-In-A-Box screen with the old swing tune “Back Home Again In Indiana” loaded and ready to play in the ZZJAZZ style. Band-In-A-Box is notorious for its nonstandard user interface and disorganized options procedures. But it’s the only program that does what it does, and it does it well. Until recently, Band-In-A-Box was available on the PC platform only as a 16bit application. The latest version, BandIn-A-Box 2004 is a Win32 application, but it still has that quaint UI that its loyal user base has come to love. I use Band-In-A-Box to practice in my studio and as a teaching tool. It provides a ready-made rhythm section for students learning to play jazz. Many musicians use Band-In-A-Box on the bandstand, others use it for practicing, and some use it in the studio to build backing tracks. The piano/bass/drums trio MP3s on my web site use Band-In-A-Box bass lines, which, in its jazz styles, can sound realistic after some tweaking with the Sonar sequencer program (http://www.cakewalk.com/ Products/SONAR/). Musicians find a wealth of standardtune files in Band-In-A-Box format available for download all over the Internet. Almost any popular tune from the early part of the previous century until the present time is available somewhere in BandIn-A-Box format. These files usually include the melodies of the tunes and often the lyrics. This enormous online resource is a boon to working musicians because BandIn-A-Box lets you transpose a tune to any key on either clef and print its music notation in lead sheet format. (See the accompanying text box entitled “Lead Sheets and Fake Books.”) I won’t say where you can find such files lest I alert those dedicated RIAA lawyers and divert them from their untiring quest to lock up impoverished stuDr. Dobb’s Journal, September 2004
dents who use university computers to share online punk/rap/hip hop/rock/crap MP3s, but a word to the wise is “Google.” Bear in mind that the software in this article is intended for personal use only or to help people publish lead sheets for which the publisher fully intends to pay the required royalties. Playing the Charts As any club date musician knows, when a band reads a tune in the concert key of B-flat (the “concert” key is the original key the tune was written in and is usually pitched to suit the average male vocal range), the piano player reads the tune in B-flat, trumpet and tenor sax players read it in C, alto and baritone saxes in G, and trombone and bass in C but from the bass rather than the treble clef. Reading a tune can require as many as four different lead sheets depending on what instruments are in the band. Then there are the chick singers who, because of their vocal range, must sing tunes in nonoriginal keys. They need even more lead sheets for each of the musicians to read. A working musician who prepares for a gig needs a way to rapidly print out readable lead sheets in multiple keys and clefs. Unless you want to carry a trunk full of fake books to the gig. Assuming the fake books are available. Which they aren’t. We used to have thick fake books with a lot of tunes, most of which nobody would ever play. When is the last time you heard a request for “The Naughty Lady of Shady Lane?” The tunes in those old fake books were in the concert key on the treble clef. Most were notated by hand, printed illegibly, distributed underground, and had lots of mistakes. All players read the same notation, and horn players transposed in real time. We shouldn’t need those books now because music notation software abounds. All we need is to get every known tune in the Western world into lead sheet format with a music notation program. Then we can print it in any key on any clef for any musician. Notation Editing Every known tune in the Western world is somewhere in a Band-In-A-Box file. And Band-In-A-Box has a notation editor feature. You enter the melody lines of a tune by using the notation editor or by playing the melody on a digital piano. Almost everybody uses the digital piano because the Band-In-A-Box notation editor is lacking, to put it mildly. Consequently, the melody notation in most of those thousands of freebie tune files reflects playing errors, player interpretations, and quantizing variations. You’d think someone who was about to release such a file for public consumption would use the notation editor 53
Figure 1: Band-In-A-Box. to fix up the notation, but they don’t because the notation editor itself discourages people from using it. But, given a melody line and the chord changes, Band-In-A-Box can print a lead sheet. Figure 2 shows the first of several measures of Band-In-A-Box’s notation for “Back Home Again In Indiana.” There’s not much wrong with the notation in Figure 2, but few of the tunes you find online are anywhere nearly as clean. And the Band-In-A-Box editor has some annoying conventions that discourages one from trying to clean up the notation. It improperly decides that a note should have a particular sharp or flat accidental, using an A-flat where the harmonic context of the tune calls for G#, for example. Worse, it will make that decision in a key where A-flat is part of the key signature and needs no accidental notation whatsoever. Or it will decide that an F ought to be an E-sharp or something silly like that. It assigns double barlines where you don’t want them. I could go on and on. These are only some of its contrary, arbitrary notational decisions that you cannot change. When you mention such deficiencies to Band-In-A-Box fans, they say, “Band-InA-Box is not supposed to be a notation editor. Use if for what it is best at.” Well,
duh. If it’s not supposed to be one, why even put the feature in? Oh, well, another problem to solve. With a MusicXML export of Band-In-ABox notation, I could import a tune’s notation into Finale and correct it to my heart’s content. But Band-In-A-Box does not support MusicXML.
Figure 2: Band-In-A-Box notation.
Finale What to do? I have all these songs with notation that cannot be easily corrected. They can, however, be exported to SMF files. I have the full-featured Finale notation editor program that supports both MusicXML import/export and SMF import/export. How do I bring the two applications together to get that large catalog of lead sheets into a manageable format? Remember as you look at these examples that my objective is to have lead sheets with melody lines and chord symbols that can be edited with a real music notation editor. And I want to do it a lot of times with a lot of tunes. Reaching that goal ought to involve as little manual effort as possible. Band-In-A-Box plays tunes based on programmed styles. These styles represent the kind of music that fits the tune. They define lines of notes for the bass to play, chords for the piano to play, rhythmic patterns for both, and, of course, drum patterns for the drums to pound out. There are hundreds of styles available in .STY files, and you can even take a tune intended to be played as a country ballad, for example, and play it as a hip hop tune. You can. I won’t. I exported an SMF file of “Back Home Again In Indiana” with the ZZJAZZ style in effect from Band-In-A-Box and im-
Figure 3: Band-In-A-Box’s MIDI output.
Figure 4: Band-In-A-Box’s MIDI output with the Export Style Imported into Finale.
54
Dr. Dobb’s Journal, September 2004
ported it into Finale to see what it looks like and how easy it would be to convert to a lead sheet. The imported notation shows some Band-In-A-Box stylemaker’s notion of what to play for each chord, not necessarily enough information to infer the actual chord symbol. Figure 3 shows the imported SMF data in notation format. As you can see, the bass line is all over the place; it does not always convey the chord’s root value, which you need to infer a lead sheet chord symbol. The piano part has altered and substitution chords and inversions selected by the style. Those piano chords are, of course, generated in a comping style with voicings, embellishments, and rhythmic interpretations that real piano players use when improvising accompaniments. Because they simulate piano accompaniments, the piano chords rarely unambiguously state the chord itself and rarely occur in a measure precisely where the chord symbol ought to be on a lead sheet. Obviously, a stylistic rendering of a tune such as Figure 3 shows is information overload on the one hand and yet insufficient information for my purposes on the other. Exporting with Style To get an SMF file with the melody and sufficient harmonic information to represent the current chord symbol at the proper place, I developed a Band-In-A-Box export style by using Band-In-A-Box’s Stylemaker process. Building the style took less than five minutes because the export style plays only one bass note, the root, in the bass part and only one chord in the piano accompaniment part for each chord change. The style plays a very simple version of the tune. Kind of like when you learned “Heart and Soul” on the piano when you were a kid. When you load the style to play with a tune that you want to export, you must allow Band-In-A-Box to reconfigure the melody to eliminate Band-In-A-Box’s socalled “swing” feeling. A lead sheet should have a plain, unadorned melody line. Musicians apply their own interpretations during performances. Figure 4 shows “Back Home Again In Indiana” with the export style exported by Band-In-A-Box to an SMF file and imported into Finale. If you used that style for playback in Band-In-A-Box, you would hear a rather boring rendition of the tune. The style is only for exporting information; it is not meant to be used for playback. Unless, of course, you really enjoy listening to boring music, in which case I can recommend some of the hip hop styles for your listening pleasure. You must apply some manual effort to get Band-In-A-Box to render the exported http://www.ddj.com
SMF file correctly and to tell Finale how to import it. You have to mute all BandIn-A-Box tracks other than piano, bass, and melody, tell Band-In-A-Box not to embellish chords during playback, tell it to delete all melody choruses other than the first one, and to export only one chorus. Then you have to tell Finale to import the SMF file by quantizing to the sixteenth note resolution and to space notes evenly in every beat to neutralize some of the tune’s original input interpretation. Because of the simplicity of the export style, the SMF file that Band-In-A-Box renders as shown in Figure 4 has the complete melody but only sufficient harmonic information (a bass note for the root and a piano chord for the chord’s other notes) to describe the chord and only when a chord changes. This is enough information to build a Finale lead sheet. If I had only a few such tunes to convert, I could use Finale’s Chord/Two-staff Analysis command to click on each chord and create a chord symbol, move the chord symbols to the melody staff, and delete the bass and piano staves. That’s simple enough, but it takes enough time for each tune that you wouldn’t want to do it for a large catalog of tunes. The melody track is important for this project. The Band-In-A-Box file needs a melody track. You can’t build a lead sheet without a melody for the lead instrument to play. If all you want is a chord sheet, Band-In-A-Box’s lead sheet notation is sufficient. Converting SMF to MusicXML This problem cries for a software solution to convert such SMF files into a MusicXML file. The solution would parse the bass and piano staves to infer chord symbols, which it adds to the remaining melody staff, and it would eliminate those staves in the converted MusicXML file. With that capability you have your choice of several notation editors that support MusicXML. At the present, music notation applications that support MusicXML are mostly those that support a software plug-in architecture, and their MusicXML plug-ins are typically developed by third parties. Most notable of those applications is Finale (http://www.finalemusic.com/), and recent versions of Finale include a light version of the MusicXML Dolet plug-in (http://store.recordare.com/doletfin1.html). Finale is the leading music notation program. and versions 2000 through 2004 support the MusicXML format. Sibelius (http://www.sibelius.com/) is another full-featured notation editor that supports MusicXML with a Dolet plug-in (http://store.recordare.com/doletsib1.html). http://www.ddj.com
Alternative Solutions My first plan was to write a Finale plugin that would process the imported score of Figure 4 and create a lead sheet. I abandoned that plan after a careful reading of the Finale plug- in API documentation. I found no way in that API to add chord symbols to a score. That doesn’t mean the API doesn’t support it; I just couldn’t find it. I did find an overly complex, underdocumented API so typical of the contemporary programming environments that nudged me into an early retirement last year.
My second plan was to write a script by using the new FinaleScript feature introduced with the latest version of Finale. I upgraded specifically to get that feature. The script would step through the score and apply the Chord/Two-staff Analysis command I mentioned earlier. I abandoned plan two when I could not find commands in the script language for working with chord symbols. My third plan was to write the program I just mentioned. I considered the knurly problems of converting MIDI data to notation, figuring out based on MIDI delta clock values and NOTE ON/NOTE OFF
Figure 5: ChordBuilder data flow diagram.
Lead Sheets and Fake Books
A
“lead sheet” is a sheet of music that includes a tune’s melody in music notation, chord symbols above the melody line, and, sometimes, the song’s lyrics below the melody line. Root around in your grandma’s piano bench and find some old sheet music for a popular song of years gone by. Sheet music has all that information plus a simple piano arrangement in bass and treble clef staves below the melody line. Many lead sheets from the old days were made by cutting and pasting sheet music to eliminate the piano arrangement staves. Professional musicians use lead sheets to play improvised interpretations of songs in their own performance styles. The melody line tells them what the melody is. The chord symbols tell a piano player what chords to play along with the tune. Chord symbols also tell lead instrument players the harmonic context to apply to improvised solos. Whereas most sheet music arrangements are three or more pages of musical notation, the typical song
Dr. Dobb’s Journal, September 2004
can be represented on a lead sheet with only one page. Lead sheets are essential tools for professional musicians who do not always play from fully scored arrangements. A “fake book” is simply a bound volume of lead sheets, usually in alphabetical order by song title. Fake books are usually published as collection of tunes that fit a theme. Jazz tunes, Latin tunes, old standards, and so on. The name reflects the old idea that musicians who read lead sheets or who play “by ear” are “faking” it rather than reading formally arranged parts. The phrase is thought to have originated as a putdown by classically trained musicians but, with popular usage, has become a respectable reference to the ability to play without needing full notation. A popular fake book compiled by a Berkeley teacher for jazz students is called the “Real Book,” a whimsical nod to the old idiom. —A.S.
55
Figure 6: Song imported from ChordBuilder’s MusicXML output. Step 1 2 3 4 5 6 7 8
Procedure Band-In-A-Box loads the song file and associates it with the export style. Band-In-A-Box exports the tune as a Standard Midi Format (SMF) file. Finale imports the SMF file and converts it to notation. Finale exports the notation in MusicXML format. ChordBuilder reads the MusicXML file that Finale exported. ChordBuilder converts the data to lead sheet format and writes a new MusicXML file. Finale imports the MusicXML file that ChordBuilder created and converts it to notation. Finale saves the notation in its own file format.
Table 1: ChordBuilder procedures. events what duration to assign a note, whether it is tied to another note, whether it ought to be dotted, and so on. It isn’t as easy as it looks, and all the notation programs have already done it. Why not leverage their work? ChordBuilder And so I arrived at plan four, the program that this article describes. The program, with the unimaginative name, ChordBuilder, converts to MusicXML. I am pretty good at writing text-parsing programs, having written several programming language and script interpreters, which is why I figured I could get this plan working before any of the others. To use ChordBuilder, follow Figure 5, a data flow diagram. You begin with a Band-In-A-Box file that contains the chords and melody of a tune you wish to export to a music notation program. That file is represented by the icon in the upper left corner of Figure 5. You wish to end with a lead sheet notation file in Finale’s notation file format. That file is represented by the icon in the lower right corner of Figure 5. Table 1 lists the steps in Figure 5. Indiana.xml (available electronically; see “Resource Center,” page 5) is built from the first five measures of “Back Home Again In Indiana.” As you can see, MusicXML is a verbose language because it uses XML markup tags to define even the smallest entity of music notation. ChordBuilder reads the exported score, parses the chord data from the bass and piano parts, inserts chord symbol markup into the melody part, and writes a new version of the score in MusicXML format with only the melody part and its new chord symbols. Indiana[1].xml (available 56
electronically) is the output from ChordBuilder. You import the output from ChordBuilder into Finale to view, edit, and print a lead sheet. Figure 6 shows “Back Home Again In Indiana” in its lead sheet format in Finale. The MusicXML Library I built ChordBuilder from the ground up by designing and coding all its MusicXML classes. I did not have to do it that way. The MusicXML Library (http://libmusicxml .sourceforge.net/) is an open-source project that supports a C++ class library for processing MusicXML data. If I was writing a complex MusicXML program, I might get on board with the MusicXML Library project, and I’d have to ensure that everything complied with the GNU Library or Lesser General Public License. ChordBuilder, however, is a relatively simple text parsing program, and it just seemed less trouble to design a few simple classes than to climb someone else’s learning curve and buy into their rules. Most of my code in the DDJ “C Programming” column was open source, but it wasn’t Open Source, and I’m not ready to jump into that fray from the comforts of a mostly noncoding retirement. About the Program ChordBuilder is a command-line program with only one command-line parameter. You must specify the name and not the extension of the MusicXML file that ChordBuilder reads. The extension has to be .XMl. ChordBuilder builds a file with the same name and a [1] suffix. So indiana.xml becomes indiana[1].xml. ChordBuilder also reads the SMF file that Band-In-A-Box exported. ChordBuilder exDr. Dobb’s Journal, September 2004
pects that file to have the same filename. In this example, that would be indiana.mid. ChordBuilder has to read that file to extract the tune’s title. For some reason, although virtually all SMF-processing programs reserve the META_SEQTRKNAME event in track 1 for the song title, the Finale SMF import feature does not import that title, so it does not get exported to the first MusicXML file. I wrote the program in Standard C++ with no platform dependencies. There is a version of Band-In-A-Box for the Mac and, if music notation programs for the Mac support MusicXML import/export, perhaps you can port ChordBuilder to the Mac. I compiled and tested ChordBuilder with Microsoft Visual C++ 6.0 and MinGW GCC 3.2.1 running under the Quincy 2002 IDE (http://www.alstevens .com/quincy.html). ChordBuilder’s source code is available electronically. The download includes the export.sty file that implements the export style for Band-In-A-Box and a Quincy project file. You can download an executable version of the program along with the style file and instructions for using the package with Band-In-A-Box and Finale on the Windows platform. The download file is found at http://www.alstevens.com/midifitz/. The program’s organization is a straightforward C++ class design. Two classes, musicXMLin and musicXMLout handle reading and writing the MusicXML files. Several structures defined in the musicdata.h source file organize music notation data for internal processing. The ChordBuilder class encapsulates the parsing of MusicXML input data and the generation of MusicXML output data. To extract the song title from an SMF file, I used a MIDIFile class that I developed several years ago and published in the “C Programming” column. All console output is isolated in a chordbuildermessage function in main.cpp. If someone wants to port ChordBuilder to a GUI, this function is where you would capture exception and warning messages from the program. The messages themselves have sufficient unique text data that a program can determine what to do with them. Although the program is reasonably portable among Standard C++-compliant compilers, portability was not my motivation for writing ChordBuilder as a command-line program in Standard C++. I did it because that’s how I like to write programs. I never much liked writing GUI programs for any platform, especially with MFC, and I’m retired now and can write programs any way I want. DDJ http://www.ddj.com
WINDOWS/.NET DEVELOPER
C#, COM Objects, & Interop Services Developing ActiveX controls and COM objects in C# SHEHRZAD QURESHI
T
he company I work for sells microfluidic instrumentation intended for use in pharmaceutical and biotechnology laboratories. Typically, there are a large number of machines and instruments that reside in these labs, with differing models from various companies, each performing a different set of functions. Integrating these disparate functionalities into a cohesive process and methodology falls under the banner of what is known as “lab automation.” As you’d expect, each machine or instrument runs some form of control software, and the industry has gradually settled on ActiveX controls as the preferred component technology that serves as the glue that connects all the pieces together. The dominant software architecture is a master scheduling application that is in control of the entire process, which invokes methods and gets/sets properties on the individual ActiveX “driver” components. This master application more often than not takes the form of a Visual Basic 6 (VB6) executable, as in Figure 1. As the industry has settled on the VB6/ActiveX paradigm of distributed lab automation, it is simply not feasible from a business point of view to completely jettison the COM- centric paradigm of component-oriented development and embrace .NET controls lock, stock, and barrel. Since many of our customers use VB6, Shehrzad is an engineer at Labcyte Inc. and author of the forthcoming book Embedded Image Processing on the C6000 DSP (Kluwer Academic Publishing, 2005). He can be contacted at shehrzad_q @hotmail.com. http://www.ddj.com
we must componentize our control software such that a VB6 client can talk to it. After all, the marketing department isn’t going to be pleased if they find out a potential sale is lost because engineering has completely transitioned to .NET and, thus, a potential VB6 customer has no means of integrating our instrumentation software into their production line. Fortunately, Microsoft has given some thought to backwards compatibility, and through the machinations of a .NET technology called “.NET Interop,” it is indeed possible — and even advantageous — to develop COM objects in .NET’s paradigmatic language, C#. Much of our control software requires unimpeded access to the underlying hardware. As such, our existing ActiveX controls are implemented using (unmanaged) C++. As anyone who has coded ActiveX controls using the Active Template Library (ATL) knows, developing these controls using the wizards provided by Visual Studio can be a laborious and arduous task, involving the modification of a multitude of source files, such as .cpp, .h, and Interface Description Language (IDL) files just to implement simple controls, like the one that I describe here. I wanted to leverage the power of .NET in our software development strategy, but until recently lacked the expertise (and, more importantly, the impetus) to make that jump. That impetus was handed to me when I was faced with the daunting prospect of developing several lab instrumentation ActiveX controls, on an extremely tight deadline, for a line of products my company had acquired through a merger. I then explored the possibility of using .NET interop to implement ActiveX controls in C# as a means of expediting this development. What I found was somewhat of a revelation to me — that, in fact, developing ActiveX controls and COM objects in general is straightforward in C#, and by properly utilizing .NET Interop, you can develop ActiveX controls that can be used by a VB6 client or any other COM-compatible language, provided the .NET Framework is available on the client machine. Moreover, in my estimation, the removal of ATL style “wizard-driven” coding (because hand coding such an implementation in C++ with-
out the wizard is extremely time consuming to say the least), leads to an advantage when developing ActiveX controls in C#. The code is far more concise and easier to digest and maintain. In this article, I first present an ActiveX control and VB6 client application, then examine the process of implementing this control using both C++ (ATL7) and C# in Visual Studio .NET 2003.
“C# lets you leverage the power of the .NET Framework and provides a bridge to the future” The ActiveX Control and Sample Client Application The COM object I use here is about as simple as I could conceive. It publishes a single method, Add( ), which accepts two double input parameters and returns the sum of those two inputs. The sample client application is a VB6 executable and is equally simple (Figure 2). The form has text edit boxes corresponding to the two input parameters and the result of the Add( ) method is placed in another edit box when the button in the form is clicked. ActiveX Implementation in C++ This particular implementation uses Unmanaged C++ and ATL Version 7. An alternative method of crafting ActiveX controls is to utilize the Microsoft Foundation Classes (MFC) framework, but Microsoft recommends ATL if size and speed are the main criteria. The ActiveX controls discussed here are of the in-process variety (as opposed to out-of-process), meaning that they reside within DLLs. The first step in creating the ActiveX control is to create a new ATL project in
Dr. Dobb’s Journal Windows/.NET Supplement, September 2004
S1
Visual Studio (Figure 3). The next step is to use the wizard to provide the skeleton for the control. Switch to the class view of the project (View|Class View), and add an “ATL Simple Object” class to the project (Project|Add Class); see Figure 4. After selecting the option to add an ATL simple object to the project, the wizard VB6 Application
Instrument 1 ActiveX Instrument 1
Instrument 2 ActiveX Instrument 2
Instrument 3 ActiveX Instrument 3
Figure 1: Typical lab automation software architecture.
Figure 2: Sample VB6 client application.
S2
prompts for a variety of options. Provide a class name and use the default options. The act of adding this ATL object to the project inserts a rather copious amount of code into the numerous C++ source files and generates Globally Unique Identifiers (GUID) for the interface and object classes. At this point, the wizard has constructed a fully functional ActiveX control (admittedly a useless one that has neither methods nor properties). Now you can insert the Add( ) method into the control. Again from the class view of the solution, select the interface class whose name begins with a capital “I” and is followed by whatever object name you selected earlier when you inserted the ATL object. Bring up the Add Method Wizard via Project|Add Method, and you can configure the signature of the new method. Figure 5 shows the contents
Figure 3: Creating a new ATL project.
of the Add Method Wizard after creating the signature for the Add( ) method. The class method that implements Add( ) returns an HRESULT and C++ clients, when invoking any COM method, can expect an HRESULT return value and should use the FAILED macro to test for success or failure. Clients coded in higher level languages, like Visual Basic or C#, can expect the ActiveX methods to return the parameter decorated with the [out,retval ] attribute (which, in this case, is a double and is the summation of the two inputs). The act of using the Add Method Wizard hides much of the gory details of implementing ActiveX methods in C++ from you. In essence, what is happening is that the wizard adds the method signature to the IDL portion of the project, adds a method declaration to the interface class, adds a similar method declaration to the implementation class, and finally adds a shell of the new method to the implementation class’s .cpp file, which of course is left for you to fill in. When all is said and done, the C++ project for this trivial ActiveX control consists of 10 source files, not including transient source files that the MIDL compiler generates. Visual Basic 6 Client (C++) The VB6 client application has already been introduced. After creating the form
Dr. Dobb’s Journal Windows/.NET Supplement, September 2004
http://www.ddj.com
in the VB UI designer, a reference to the new component must be added to the Visual Basic project. Add a reference to the control from within the Visual Basic IDE via Project|Reference, then browse to the location of the DLL that contains the new ActiveX control. Double clicking on the ActiveX DLL inserts the reference into the Visual Basic project. Listing One implements this simple application. What you have done to this point is nothing new, rather it could easily have been accomplished in almost the same way using Visual Studio 6 in 1999. What is new is to implement this same control using C# and .NET Interop. ActiveX Implementation in C# Using a COM object from .NET is straightforward. Once you add a reference to the COM object, Visual Studio automatically generates a Runtime-Callable Wrapper (RCW), which provides a thin veneer around the COM object and performs data-specific marshaling to/from the legacy COM domain and new .NET domain. What I implement is the converse of this, and the task is made substantially easier as the ActiveX control described here does not have a GUI aspect to it. If that were the case, then you could not use the steps described here as the MSDN documenta-
http://www.ddj.com
tion emphatically states that you “cannot register Windows Forms controls as ActiveX controls or create them using CoCreateInstance.” In contrast to the C++ version, the C# ActiveX implementation is much less wizard-driven. However, the result is far more concise, and easier to read and understand. The initial step is to create a C# class library project by selecting File|New|Project, choosing Visual C# Projects and the Class Library Template (see Figure 6). There is no ActiveX template and you’ll be creating the control from scratch. Listing Two is the C# version of the control and is probably a tenth of the size
of the C++ version in terms of lines of code. The C++ ATL object was named SimpleActiveX, so the interface class is ISimpleActiveX. The corresponding C# interface class is named ICSharp_ActiveX and decorated with two attributes. .NET attributes let you extend the metadata that
Figure 5: Inserting the Add() method into the ATL object.
Figure 4: Adding an ATL object to a C++ project.
Figure 6: Creating a C# class library.
Dr. Dobb’s Journal Windows/.NET Supplement, September 2004
S3
accompanies an assembly by annotating the source code with relevant fields. In this case, the first attribute is the GUID associated with the interface object. .NET Interop and, of course, the COM runtime need these GUIDs to perform their magic. The ATL wizard took care of generating GUIDs (and sprinkling them throughout various source files), while here I manually generate a GUID and link it to the event class using an attribute. GUIDs can be generated using either the command-line tool guidgen.exe or via the Create GUID item under the Visual Studio .NET Tools menu. The second attribute decorates the Add( ) interface method and is reminiscent of the IDL code inserted into the C++ project by the ATL wizard. In fact, it is merely embedded IDL and the same syntax is followed (for example, a help string could be associated with the method via the IDL helpstring keyword). Likewise, the class object that implements this interface requires a GUID and is decorated with a GUID attribute. The ClassInterface attribute controls whether a separate class interface is generated for the attributed class (in this case CSharp_ ActiveX_Class). While this option can be useful for debugging, the recommended value for this attribute is ClassInterfaceType.None, as it mitigates versioning problems. The Add( ) method is implemented and, except for a few postbuild steps, the COM object has been fully implemented. All of the attributes used in this example reside in the System.Runtime.InteropServices namespace. By adding the using declaration at the top of the source file, you don’t need to use the fully qualified name for all of the attributes. Before this assembly can be used as a COM object into a pre-.NET language, the object must be registered for COM Interop (Project|Properties, select Build under the Configuration folder and set Register for COM Interop to True). What this does is generate a COM-callable wrapper (CCW), which wraps the .NET class library we
have just implemented. The COM client (in this case, the sample VB6 application) interacts with the CCW, which in turn forwards method invocations and performs data marshaling between itself and the underlying .NET class library. For the CCW to work correctly, the .NET assembly must be strongly named or the .NET runtime can’t identify it. To sign the assembly with a strong name, I use the sn.exe utility, which is in the .NET SDK. By adding a postbuild step to the C# project, you can seamlessly integrate this postprocessing into the build process. The steps required to accomplish this are: 1. Open the AssemblyInfo.cs file, which consists of a variety of attributes, and update the AssemblyKeyFile attribute with a name referencing a key file. In this case, the attribute was updated as: [assembly:AssemblyKeyFile("..\\..\\bin\\ Debug\\CSharp_ActiveX.snk")]. 2. Add a postbuild event by opening the project’s properties, selecting the Build Events item under the Common Properties folder. The command to run is the sn.exe utility and pass it the key file specified in Step 1: sn -k CSharp_ActiveX.snk. 3. The final build step is to register the .NET assembly so that it can be used with COM. The C++ ATL project uses the regsvr32.exe utility to manipulate the registry such that the COM runtime is able to instantiate the object at runtime by running regsvr32.exe as a postbuild step. In a similar fashion, I use the .NET SDK regasm.exe utility to perform the equivalent steps, which entails reading the metadata accompanying the assembly and making the necessary registry entries such that CoCreateInstance( ) and their ilk continue to function correctly. To add this to the project, the command “regasm CSharp_ActiveX.dll” is added as a postbuild step. This completes the C# implementation of the ActiveX control. Upon building the project, the assembly is compiled,
Listing One
Private Sub Form_Load() ' instantiate control Set CppControl = New Cpp_ActiveX.CSimpleActiveX End Sub
Listing Two
S4
Visual Basic 6 Client (C#) The VB6 client code (available electronically; see “Resource Center,” page 5) is virtually identical to the previous VB6 listing, sans the variable names pertaining to the COM object being changed. The only other change concerns how to import the reference to the COM object. Recall that with the C++ ActiveX control, we added a reference to the ActiveX control by pointing Visual Basic to the DLL that contained the control. For the C# ActiveX control, when adding the reference, import the type library (.tlb) file instead, which is one of the outputs of the C# build process. Conclusion The advantages of using C# to develop COM objects are two-fold. C# lets you leverage the power of the .NET Framework and provides a bridge between older technology and the future. For example, in C/C++, dealing with BSTRs and the like can be cumbersome, even though ATL helps alleviate some of the issues. Many of these issues melt away in the C# domain. Also, the source code is easier to read and digest than the corresponding C++ version. Wizard-generated code, with all of its mysterious macros, transient and temporary files, registration scripts and such lend an air of black magic to the code. The C# implementation is cleaner, and by extension easier to maintain. One downside to using .NET interop is the overhead involved with data marshaling between the managed and unmanaged domains. However, through careful design, this performance hit can be mitigated. In practice, I have found the benefits to the implementation strategy described in this article to be significant — as long as the component is not shuttling voluminous amounts of data, the gains in readability should offset any potential performance issues. DDJ
/// <summary> /// COM object Interface /// [Guid("3D6E75CD-C44F-46fd-9723-F833B366129F")] public interface ICSharp_ActiveX { [DispId(1)] double Add(double a, double b); } /// <summary> /// The object that implements the above COM interface /// [ Guid("1DBB9AEB-9333-408f-925C-4DE11599DEEF"), ClassInterface(ClassInterfaceType.None) ] public class CSharp_ActiveX_Class : ICSharp_ActiveX { public double Add(double a, double b) { return a+b; } }
‘Declaration of the ActiveX control Dim CppControl As Cpp_ActiveX.CSimpleActiveX Private Sub btnAdd_Click() ' grab data from input text boxes Dim a, b As Integer a = CDbl(txtA.Text) b = CDbl(txtB.Text) txtResult.Text = CStr(CppControl.Add(a, b)) End Sub
using System; using System.Runtime.InteropServices; // for DispId & Guid attributes namespace CSharp_ActiveX {
built, and registered such that it can now be used as a COM object.
}
DDJ
Dr. Dobb’s Journal Windows/.NET Supplement, September 2004
http://www.ddj.com
WINDOWS/.NET DEVELOPER
Improving .NET Events Strategies for generating events RICHARD GRIMES
E
vents are a useful paradigm: Objects can notify other objects when some event occurs — perhaps a change in state or maybe an error condition has occurred. Some other code — handler code — can register its interest to be notified that this condition has occurred. When the event is raised, the handler code is called. But while .NET provides mechanisms for event-based code, there are some shortcomings in this mechanism. Luckily, .NET provides the facilities for writing your own event mechanism, thereby making it possible to address these problems.
Delegates As an example of generating and handling events, consider the user-interface events provided by the Control class and derived classes for handling Windows messages. In essence, the Control class contains a method equivalent to a Win32 windows procedure that accepts messages sent to the Win32 window attached to the Control object and handles each message by raising an appropriate event. A method written to handle a Windows message adds itself to the list of handler code. When the Windows message is sent to the window, the event is raised by calling all of the methods added to the handler list for the event. To enable this, .NET provides two facilities: a mechanism to inRichard is the author of Programming with Managed Extensions for Microsoft Visual C++ .NET 2003 (Microsoft Press, 2003). He can be contacted at richard@ richardgrimes.com. S6
voke methods called “delegates,” and a formalized mechanism for a class to identify the events it can raise. Of all the .NET languages, only managed C++ lets you create C-style function pointers, but even C++ cannot create a function pointer to a .NET method. The reason is that .NET methods have a special calling convention called _ _clrcall that is not a supported calling convention. So managed C++, like all other .NET languages, must use a delegate to invoke a method. A delegate is a compiler-generated class that derives from the MulticastDelegate class. Listing One shows how to declare a delegate called OneParam that is used to call methods that take a single parameter, a 32-bit integer, and return no values. As you can see, the delegate instance is initialized with a pointer to a method that has the correct prototype. This is the only time that you can access a pointer to a managed method. The compiler performs type checking when it uses this pointer to initialize the delegate through its constructor and so it ensures that a delegate will only be used to invoke a method with the correct parameters. This method can be an instance method, static method, and it can be a member of any class. You can initialize a delegate with a private method of one class, in another method in that class, and pass the delegate to another class where it can still be invoked. Furthermore, you can pass the delegate to unmanaged code and .NET provides the thunking code to allow the unmanaged function to invoke the managed method. Clearly, delegates are clever objects. If you take a look at the IL generated for this, you see that the constructor of the delegate class looks like this: .method public hidebysig specialname rtspecialname instance void .ctor(object 'object', native int 'method') runtime managed { } // end of method Del::.ctor
The runtime-managed modifier indicates that no IL exists for the constructor and that the runtime provides the code. The parameters are interesting: The first parameter indicates the object that contains the method that will be invoked, and C# conveniently infers this from the parameter that you pass. The second parameter is typeless and is effectively a .NET equivalent of a void∗ pointer. But again,
“There is no concept of invoking the delegates in the MulticastDelegate object in parallel”
the compiler performs type checks to ensure that the method used to initialize a delegate is of the right type. This information is stored in the delegate object and can be accessed through the Target and Method properties. Each delegate is multicast, which means that you can combine two delegate objects to create a third object that contains the first two. To do this, the MulticastDelegate class has a linked list, and when you combine two delegates, their linked lists are chained. Delegates can be invoked synchronously (Invoke, which C# calls for you when you invoke the delegate as if it is a method, as in Listing One) or they can be invoked asynchronously. However, “asynchronously” means with respect
Dr. Dobb’s Journal Windows/.NET Supplement, September 2004
http://www.ddj.com
to the code that invokes the delegate and not with respect to the individual delegates within the multicast delegate. There is no concept of invoking the delegates in the MulticastDelegate object in parallel. The default invocation mechanism will walk the linked list and invoke each delegate in turn, synchronously, waiting for an invocation to complete before invoking the next delegate in the list. If you invoke a multicast delegate asynchronously, all that happens is that this invocation is performed on another thread. Also, note that if one delegate in a multicast throws an exception when it is invoked, then the entire invocation of the multicast delegate is aborted. This is a problem when you consider events (which I will do next) because an event invites anyone to add a delegate to provide a handler for the event. When the event delegate is invoked, rogue code provided by some third party could throw an exception. If this happens, no other handlers for the event will be called. If the exception is still left uncaught, then the object could be killed. This highlights the tight coupling between .NET classes that raise events and the classes that handle them. Events The support for events comes in two forms. First, there must be a delegate field for each event and these hold the delegates that will be invoked when the event is raised. Second, there must be a formalized mechanism to allow code outside of the class to add delegates initialized with handler methods to this event delegate. .NET compilers provide their own code to do this and, with C#, this is done with the event keyword as shown in Listing Two. In this code, I have used a framework-provided delegate called EventHandler, but events can be defined for any delegate type. The event keyword adds a private delegate field and it adds public methods to add a delegate and remove a delegate from this delegate field. In addition, so that other code can tell that this class can generate events, the compiler adds some .NET metadata to indicate methods that are used to add and remove delegates from the event. The C# compiler allows you to call these event methods using the += and -= operators. When the event is raised, the delegate is invoked, and the default mechanism in C#, and the other .NET languages, is to invoke the delegate synchronously on the thread where the event was raised. Again, it is important to point out that all of the delegates in the multicast delegate are invoked serially. For Windows Forms classes this is a useful side effect because GUI code should only be called on the process’s GUI thread and the event handlers http://www.ddj.com
for controls usually access the control or other controls on the form. However, for nonGUI code, you may find this a restriction, particularly if the delegates are for methods on remote objects or methods that take a long time to perform. The Control class defines 57 events, indicating that, by using the default event mechanism, a Control object would have 57 delegate fields even though you will use perhaps only a handful of these. This clearly represents a waste of memory, so the designers of the Control class override the default action of the event keyword and provide a more efficient mechanism to store event delegates. The Control class derives from the Component class, which has a property, Events. This property is a collection of delegates of type EventHandlerList. The entries in this collection are identified by “key” objects; each key identifies a delegate for a specific event, and each of these delegates can contain one or more event handler delegates. The keys are objects, not a simple integer index; indeed, the actual value of the object is immaterial because the collection uses the identity of the object as the key. On first sight, this does not appear to solve the space issue because it implies that the Control class will need to maintain a key object for each event type. However, the key object can be the same for each event of the same type for each Control object, so the Control class provides these key objects as static (noninstance) objects. The space expense is paid by the class rather than the individual Control objects. C# lets you provide your own event methods and Listing Three shows how you can use these methods with an EventHandlerList collection. Attempts to Overcome the Issues Tightly coupled events are useful, particularly when events are handled within the application domain because they are lightweight. However, even though the event-raising code and handler code are tightly coupled, the providers of each code are likely to be completely unconnected. This means that even if your code is completely error free, if you invoke a delegate provided by someone else, their code can kill your object. There are a couple of ways to mitigate this risk. The first is the simplest: Use the [OneWay] attribute on the method that a delegate will invoke. The [OneWay] attribute adds metadata to the method, which is read by the .NET runtime when it invokes the method. This attribute indicates that the method does not return any values, so invocation code does not make any effort to retrieve return values. An exception is treated as an extra return parameter of the method, so
Dr. Dobb’s Journal Windows/.NET Supplement, September 2004
S7
[OneWay] tells the runtime to ignore the exception. However, this attribute is not suitable in all situations. The attribute only works when a call is made across a context boundary; hence, .NET remoting is used and can intercept method calls. In many cases, your code will run in the default context, so no interception occurs and the [OneWay] attribute will be ignored. Another problem is that the attribute is attached to the handler method by the author of that method; in other words, the person who writes the code that you regard as being a suspect has to mark his code to tell the runtime to ignore any exceptions it may throw. This is unlikely to happen. Another way to protect your code from errant event handlers is to invoke the event delegate explicitly. To do this you need to get access to the linked list of delegates in a multicast delegate. The MultiCastDelegate class does this through the GetInvocationList method. This returns an array of Delegate references. Listing Four shows how to use this to invoke the delegates within a try block to catch any exceptions that are thrown. The example contains no code in the catch handler; hence, the exceptions are ignored. Ignoring exceptions is not necessarily the best action — the client code may want to report that one of the delegates has generated an exception; however, to do this there must be some mechanism to collect all the exceptions that have been thrown and return them back to the client. To do this, I define a new exception class (see Listing Five) that maintains a list of ExceptionData objects that contain information about the exception and the delegate that generated the exception. This exception class has a method to add new exception information to the MultiException object, and to determine if exception information has been added to the object. The class also overrides the ToString method to add information about each exception in the collection. Finally, I have also provided a property that gives access to this collection of ExceptionData objects. Listing Six shows how this exception class is used. When a delegate throws an ex-
ception, the exception and delegate are added to the MultiException object in the exception handler but the exception is not rethrown. I think that this action is reasonable because the delegates are not related to each other, so an exceptional condition in one handler does not necessarily reflect that all the handlers are invalid, and it certainly does not indicate that the code invoking the delegates has some invalid state. When all delegates have been invoked, the code checks the MultiException object to see if any exceptions had been thrown and, if so, the MultiException object that contains those exceptions is thrown. Note that this exception class works fine if the exception is rethrown within the same context. In a future article, I’ll explain why the exception cannot be thrown across a context boundary and how to fix this problem by providing serialization code. The client that called the event- generating method can catch the exception and use the information in it. For example, Listing Seven shows exception handler code that prints out information about the MultiException that was caught and the exceptions thrown by the delegates. This code then accesses the errant delegate via the Exceptions collection and removes this delegate from the event. In effect, this is selfhealing code because once an individual delegate has thrown, action is taken to ensure that the delegate is never called again. Finally, it is worth pointing out that you cannot use this technique with Control objects. The methods on the Control class have names beginning with “On” (for example, OnClick for the Click event). These methods are virtual so you can provide an override, which will be called by the Control object’s windows procedure. However, the static key objects, used to access the event handlers in the Events property, are private and hence unavailable to your derived class. AppEvent.cs (available electronically; see “Resource Center,” page 5) is an event mechanism that catches delegate-thrown events such as those described here. DDJ
More .NET on DDJ.com ASP.NET2theMax: Textbox AutoEncoding Improves Security The standard TextBox control does not verify input text by default, and this creates a security hole that a cross-site scripting attack can exploit. Here’s a custom TextBox control that will “autoencode” text input. Richard Grimes on .NET: Notification and Delegate Lifetimes COM and .NET use two different approaches to event handlers and object lifetime management. Not surprisingly, the .NET approach is simpler, but does it provide all of the features you need? Available online at http://www.ddj.com/topics/dotnet/.
S8
Dr. Dobb’s Journal Windows/.NET Supplement, September 2004
http://www.ddj.com
Listing One
{ EventSomethingHappened = new object(); } // Declare the event and the custom event methods public event EventHandler SomethingHappened { add { events.AddHandler( EventSomethingHappened, value); } remove { events.RemoveHandler( EventSomethingHappened, value); } } // Helper method to get the event delegate and // invoke it protected void RaiseSomethingHappened(EventArgs args) { EventHandler d; d = (EventHandler)events[EventSomethingHappened]; d(this, args); } public void DoSomething() { // Code... RaiseSomethingHappened(new EventArgs()); }
public class Test { // Tell the compiler to generate a delegate class delegate void OneParam(int x); void Proc(int x) {/* code */} public void InvokeCode() { // Create a delegate object and initialize with a method pointer OneParam d = new OneParam(Proc); // Invoke the delegate d(42); } }
Listing Two public class Test { // Indicate that the class can generate the event public event EventHandler SomethingHappened; public void DoSomething() { // Code here... // Now raise the event if (SomethingHappened != null) SomethingHappened(this, new EventArgs()); } } public class UseCode { void InformMe(object sender, EventArgs args) { /* handle event */ } public void UseTestObject() { Test t = new Test(); t.SomethingHappened += new EventHandler(InformMe); t.DoSomething(); } }
Listing Three public class Test { EventHandlerList events = new EventHandlerList(); // This is the 'key' object for our event static object EventSomethingHappened; static Test()
http://www.ddj.com
}
Listing Four protected void RaiseSomethingHappened(EventArgs args) { EventHandler d ; d = (EventHandler)events[EventSomethingHappened]; Delegate[] dels = d.GetInvocationList(); // Invoke each delegate individually foreach(Delegate del in dels) { EventHandler eh = del as EventHandler; try { eh(this, args); } catch(Exception){} } }
Dr. Dobb’s Journal Windows/.NET Supplement, September 2004
(continued on page S10)
S9
(continued from page S9) Listing Five class MultiException : Exception { // Helper class to hold info about the exception public struct ExceptionData { public Exception theException; public Delegate theDelegate; public ExceptionData(Exception e, Delegate d) { theException = e; theDelegate = d; } } // Field used to collate exception data ArrayList exceptions = new ArrayList(); public MultiException(string str) : base(str) {} public void Add(Exception e, Delegate d) { exceptions.Add(new ExceptionData(e, d)); } public bool HasExceptions { get {return (exceptions.Count != 0);} } public ExceptionData[] Exceptions { get { return (ExceptionData[])exceptions.ToArray( typeof(ExceptionData)); } } // Return information about all the exceptions public override string ToString() { if (exceptions == null) return base.ToString(); StringBuilder sb = new StringBuilder(); sb.Append(base.ToString()); sb.Append(Environment.NewLine); for (int idx = 0; idx < exceptions.Count; idx++) { ExceptionData ed; ed = (ExceptionData)exceptions[idx]; sb.Append(String.Format( "{0} on {1} threw an exception:", ed.theDelegate.Method.Name, ed.theDelegate.Target.GetType())); sb.Append(Environment.NewLine); sb.Append(ed.theException.ToString()); sb.Append(Environment.NewLine); } return sb.ToString(); } }
Listing Six protected void RaiseSomethingHappened(EventArgs args) { MultiException exceptions = new MultiException( "delegate(s) thrown exceptions"); EventHandler d; d = (EventHandler)events[EventSomethingHappened]; Delegate[] dels = d.GetInvocationList(); foreach(Delegate del in dels) { EventHandler eh = del as EventHandler; try { eh(this, args); } catch(Exception e) { exceptions.Add(e, eh); } } if (exceptions.HasExceptions) throw exceptions; }
Listing Seven try { RaiseSomethingHappened(new EventArgs()); } catch (MultiException me) { Console.WriteLine("\n{0}", me.ToString()); foreach(MultiException.ExceptionData ed in me.Exceptions) { this.SomethingHappened -= (EventHandler)ed.theDelegate; } }
DDJ S10
Dr. Dobb’s Journal Windows/.NET Supplement, September 2004
http://www.ddj.com
WINDOWS/.NET DEVELOPER
Building MFC Dialogs at Runtime Sharing classes leads to less clutter ADRIAN HILL
D
ialogs are generally defined for GUIbased applications using a visual tool to design the appearance of the dialog, and an automatic code generator to generate most of the source code associated with the dialog. Apple’s Macintosh and Windows-based PCs both use this approach. For MFC-based Windows applications, you can use Visual Studio’s resource editor to position the dialog elements, then use ClassWizard to generate the corresponding C++ class code. The resource editor saves the layout information for all the application’s dialogs in a single resource (.rc) file, and saves the corresponding resource ID symbol definitions in the resource.h file. ClassWizard generally writes the C++ class code for each dialog to a separate .cpp and .h file. While this process is fairly easy to learn and use, the resulting code has several limitations, including: • The class encapsulating the dialog cannot be reused in other applications by simply including the dialog’s .cpp and .h files in the new application’s build. The dialog resources (in the application’s .rc and resource.h files) must also be copied, either manually or using the resource editor, from one application to Adrian is a founder of InPhase Technologies, a Lucent Technologies/Bell Labs spinoff that is developing holographic data storage products. You can contact him at adrianhill@ inphase-tech.com, with subject “DDJ.” http://www.ddj.com
the other. This process is tedious, particularly if the class is to be reused in several applications. If the dialog is subsequently changed and the changes are required in all applications, the modifications have to be made to each application in turn. Overall, this procedure is more like the bad old days of C programming than an object- oriented method. • The process of copying and pasting resources from one application to another can lead to an insidious bug. Since the resource IDs are effectively at global scope (they are all #defined in resource.h), clashes are possible if resource IDs copied from one application already exist in the destination application. The application with the resource ID conflict may crash, with no obvious reason. (This has only bitten me once, but it hurt.) • Only one developer can edit an application’s resource (.rc) file at a time. This limitation exists because the resource editor updates several #defines in resource.h (for example, _APS_NEXT_RESOURCE_VALUE and _APS_NEXT_CONTROL_VALUE) each time new resources are added. If two developers try to check in updated .rc and resource.h files to a source-code version-control system (such as CVS), the process fails because of conflicts in the values of these symbols. By contrast, multiple developers can work on different parts of a .cpp file concurrently, without clashing. • MFC’s ClassWizard will generate a new class for each dialog, no matter how simple the dialog is, or how similar the dialog is to other dialogs in the application. This produces “class clutter” that, though not serious, serves to muddy the class view in a large project and adds to code bloat. In this article I provide a class for defining MFC-based dialogs, which overcomes
these limitations by not using resources in the application’s .rc and resource.h files. (The complete source code and related files for the class are available electronically; see “Resource Center,” page 5.) Instead, dialog box templates are built in memory at runtime. The details are encapsulated in class Dynamic_dialog, together with its helper class, Dialog_item.
“An MFC-based dialog is constructed by creating a dialog box template that describes the dialog and its controls” You define a dialog in C++ source code, either using an instance of Dynamic_dialog directly or using a class derived from it when the dialog requires additional message map functions. To leverage as much existing MFC functionality as possible, Dynamic_dialog is derived from MFC’s CDialog class. In particular, it was simple to make all the familiar data exchange and data validation (DDX/DDV) functionality available with very little additional code. Example 1 is the code for a simple dialog with two edit controls, and the OK and Cancel buttons (Figure 1). Even without seeing the class declaration, the intent of the code is clear. Inside the Dynamic_dialog Class In general, an MFC-based dialog is constructed by creating a dialog box template that describes the dialog and its controls, such as edit boxes and pushbuttons. The
Dr. Dobb’s Journal Windows/.NET Supplement, September 2004
S11
dialog box template is then used to construct an instance of a CDialog-derived class (MFC provides class CDialog to encapsulate the basic functionality of a dialog box). When you use the resource editor to define a dialog, the dialog box template is compiled from the contents of the .rc file as part of the build process. In the Dynamic_dialog class, rather than building the templates from the resource file at compile time, I generate the dialog box template in memory at runtime. This approach is mentioned, but not described, in Jeff Prosise’s Programming Windows with MFC, Second Edition (Microsoft Press, 1999) and Michael Blaszczak’s Professional MFC with Visual C++ 6, Fourth Edition (Wrox Press, 1999). Blaszczak notes that this method is “fraught with pointer arithmetic and alignment tomfoolery.” However, by encapsulating the template details in the Dynamic_dialog and Dialog _item classes, the apparent complexity is addressed once and presents no further disadvantages.
control definition typically consists of an instance of the DLGITEMTEMPLATE struct followed by a Unicode string specifying the control’s initial text (see “Templates in Memory,” Platform SDK: Windows User Interface, MSDN Library CD, July 2001). The dialog box template has to be constructed with particular word alignment in order to work correctly, which is probably why this approach is not widely used. There is an example of building dialog templates in memory in “DLGTEMPL: Creating Dialog Templates Dynamically” (MSDN Library CD, July 2001), but it is incomplete and somewhat unconvincing because it implements most of its dialogs using standard (.rc) resources. The Dynamic_dialog class has a CArray data member that contains one Dialog_item instance for each control in the dialog. The final dialog template is assembled by the Dynamic_dialog::Build_template_buffer and Dialog _item::Write_to_template_buffer functions (in Dyn_dialog.cpp and Dialog_item.cpp).
Dialog Templates in Memory A dialog box template in memory consists of a template header followed by control definitions for each control in the dialog. A standard template header consists of an instance of the Windows SDK DLGTEMPLATE struct, typically followed by a Unicode string for the dialog box title, the font size, and another Unicode string for the dialog box font name. Each
Using the Dynamic_dialog Class The Dynamic_dialog class supports the five most common dialog controls: buttons, combo boxes, list boxes, edit controls, and static text. The DDlgTest application in the code accompanying this article has examples illustrating the use of all these controls. Look for the Dynamic_dialog _test namespace functions in DynDlgTest.cpp. Listing One (available electronically) shows the interface to Dynamic_dialog. You build a dialog by constructing an instance of Dynamic_dialog, then adding controls to it. The tab order of controls is determined by the order in which controls are added to the dialog. Call DoModal to display the dialog, just as you would with a class generated by ClassWizard. The overall dialog appearance can be set using the functions with names having the “Set_dialog_” prefix. Functions to add controls to the dialog have names starting with “Add_.” Most of
Figure 1: Dialog generated by the code in Example 1.
int exposure_time_ms = 8; // Two different numeric types. double laser_power_mw = 40.0; Dynamic_dialog dlg("Camera Image Capture", 155, 100); dlg.Add_OK_button(20, 70, 50, 14); dlg.Add_Cancel_button(85, 70, 50, 14); dlg.Add_edit_control("Exposure time", 15, "ms.", 70, 20, 45, 12, &exposure_time_ms, 1, 100); dlg.Add_edit_control("Laser power", 15, "mW.", 70, 40, 45, 12, &laser_power_mw, 0.1, 200.0); if (dlg.DoModal() == IDOK) { // ... more code ...
Example 1: Code for a dialog with two edit controls and two buttons. S12
these functions have a pointer argument value to associate a variable with the control. All the “Add_” functions have parameters specifying the size and position of the controls. Edit controls, list boxes, and combo boxes often have associated static strings to tell the user what the control’s contents are for. For convenience, the “Add_” functions for these controls take a pointer to a string to be displayed to the left of the control, and a second pointer to another string to be displayed to the right of the control (see Figure 1 and Example 1). If a pointer is 0, then no string is displayed in the corresponding position. Static text strings can also be added to a dialog using the Add_static_text function, but supplying these strings in the same call as their edit control (or list box or combo box) is convenient and makes the intent of the code line self documenting. For numerical values, the Add_edit_control function is implemented as a template function. If you require range checking (data validation) on the variable, then supply the value limits as the parameters min and max. If not, set these two parameters to the same value. Rather obviously, checkboxes are added with the Add_checkbox function. The state of the checkbox is reflected in the value of the associated bool value passed to this function. As far as MFC is concerned, checkboxes are simply another form of button. You add a group of radio buttons with a call to Add_ first_radio_button for the first button in the group, followed by a call to Add_radio_button for each additional button in the group. Call Add_group_box to complete the set of radio buttons. The variable associated with a group of radio buttons is passed as a parameter to Add_ first_radio_button. Buttons and Message Maps MFC uses a message map to associate a call to a dialog member function with a dialog event, such as clicking on a button or updating an edit box. For example, for a dialog produced with the resource editor, ClassWizard would generate a message map like this (with comments removed): BEGIN_MESSAGE_MAP(File_dlg, CDialog) ON_BN_CLICKED(IDC_INPUT_BROWSE, OnInputBrowse) END_MESSAGE_MAP()
to associate function OnInputBrowse with a button click on the button with resource ID IDC_INPUT_BROWSE. The first line of the message map indicates that this message map is part of class File_dlg, (continued on page S15)
Dr. Dobb’s Journal Windows/.NET Supplement, September 2004
http://www.ddj.com
(continued from page S12) which is derived from CDialog. BEGIN_MESSAGE_MAP, ON_BN_CLICKED, and END_MESSAGE_MAP are all MFCdefined macros. There is no need to generate message map entries for the nearly ubiquitous OK and Cancel buttons because the CDialog base class already provides the necessary mapping. These buttons can be added to a Dynamic_dialog instance with the functions Add_OK_button and Add_Cancel_button. Typically, I make an Add_OK_button call immediately after constructing the dialog (see Example 1) so that the OK button has focus when the dialog is displayed. If users immediately press Enter, the dialog acts as if the OK button had been clicked. To add other buttons to a dynamic dialog, you derive a class from Dynamic_dialog and add the button with a call to Dynamic_dialog’s Add_ pushbutton function. You must also provide a message map for your derived class, with an entry for each button. The resource ID specified in the message map must match the value passed as a parameter to Add_pushbutton. As with resource-based dialogs, you provide the function associated with the button in your derived class. An example of adding a pushbutton in a Dynamic_dialog-derived class is in the Pushbutton_dialog class (Push_dlg.cpp and Push_dlg.h) in the DDlgTest application. Browse buttons that let users select a file or directory by popping up a second,
standard dialog for file or directory selection are common in many applications’ dialogs. When users click OK in the second dialog, the file or directory name is copied back to an edit control in the primary dialog. To avoid the need to derive a class from Dynamic_dialog and add a message map every time I wanted this functionality, I decided to implement it directly in the Dynamic_dialog class. The message map and associated functions in Dynamic_dialog are shown in Example 2. I implemented four message map entries; the number can easily be extended if you anticipate needing more than four Browse buttons in a single dialog. To add a Browse button to a dialog and associate the button with the filename contained in an edit control, call function Add_Browse_button immediately after the Add_edit_control call controlling the filename. The first parameter to Add_Browse_button determines whether the secondary dialog is a standard CFileDialog, or a dialog to allow a directory to be selected. An example of a dialog with three CString edit controls with associated Browse buttons is in function Dynamic_dialog _test::Browse_test in the DDlgTest application. Message map notifications are not limited to pushbuttons. The sample application also contains an example of a dialog with two combo boxes where the contents of the right-hand combo box (in this case, a choice of cities) depends on the
// ----- Message Map ----BEGIN_MESSAGE_MAP(Dynamic_dialog, CDialog) ON_BN_CLICKED(Dynamic_dialog::e_first_browse_idc, OnBrowse0) ON_BN_CLICKED(Dynamic_dialog::e_first_browse_idc + 1, OnBrowse1) ON_BN_CLICKED(Dynamic_dialog::e_first_browse_idc + 2, OnBrowse2) ON_BN_CLICKED(Dynamic_dialog::e_first_browse_idc + 3, OnBrowse3) END_MESSAGE_MAP() void Browse(int button); // ----- OnBrowse? functions ---void Dynamic_dialog::OnBrowse0() { void Dynamic_dialog::OnBrowse1() { void Dynamic_dialog::OnBrowse2() { void Dynamic_dialog::OnBrowse3() {
Browse(0); Browse(1); Browse(2); Browse(3);
} } } }
Example 2: Message map in Dynamic_dialog for implementing Browse buttons.
selection made by the user in the left combo box (in this example, a choice of states). The dialog code is in class Derived_dialog (Derived.cpp); the dialog is in Figure 2. The message map for this class is: BEGIN_MESSAGE_MAP (Derived_dialog, Dynamic_dialog) ON_CBN_SELCHANGE (Derived_dialog::e_box_id, OnSelchangeState) END_MESSAGE_MAP()
Conclusion My primary aim in writing the Dynamic_dialog class was to let classes that use dialogs be shared among various projects, without the need to cut-and-paste resources from project to project. To implement simple dialogs, create an instance of Dynamic_dialog and add the required controls with calls to the member functions. Call DoModal, as you would for a dialog generated with the resource editor and ClassWizard, to display the dialog. If users click OK (or presses Enter) to close the dialog, then the variables associated with the dialog controls are updated. When a message map is needed for a dialog, derive a class from Dynamic_dialog and add the controls for the dialog in the constructor of the derived class. As before, call DoModal to display the dialog. I chose the order of parameters passed to several of the Dynamic_dialog functions to allow common default values, and also to be close to the order of the corresponding values in the definition of dialog controls in a resource file. This makes it fairly simple to write a converter to generate C++ code from .rc dialog resources that already exist in a project. Another advantage of building dialogs at runtime is that the current state of the program can be used to decide what controls to display. This can result in dialogs that are less cluttered than resource-based dialogs by avoiding the need to gray out or hide dialog items, for example, which are not relevant to the current state of the application. An obvious extension of the Dynamic_dialog approach is a class to automatically size a dialog and position the controls in it, given a list of controls to be displayed. This, in turn, offers the prospect of dialogs that resize themselves depending on the differences in lengths of strings in different languages such as German and Spanish. Acknowledgements Thanks to Charles Stanhope and Martin Pane, both at InPhase Technologies, for their insightful comments.
Figure 2: Sample dialog with two combo boxes where selecting a state in the left combo box changes the contents of the right combo box. http://www.ddj.com
Dr. Dobb’s Journal Windows/.NET Supplement, September 2004
DDJ S15
PROGRAMMER’S TOOLCHEST
The Qt Designer IDE Everything but the compiler DAVE BERTON
A
mong the many GUI programming libraries available, both free and licensed, the Qt C++ Library from Trolltech (http://www.trolltech.com/) has a strong following. And with the advent of Qt Designer 3.3.1, Qt developers now have a feature-rich IDE with which to design and code GUI applications. The lack of compiler support is the only significant drawback in an otherwise polished and useful tool. The original Qt Designer that appeared in Qt 2.0 did one thing, and did it well — WYSIWYG interface design. This filled a void in the world of Qt development, which at the time, required most of this code be hand written. The Designer in Qt 3.3.1 goes beyond simple GUI building, supporting full project management, source-code editing, resource management for images and database connections, and a full suite of design controls. Designer produces tight, reliable code, and does so for all platforms supported by Qt —Windows, Linux and other UNIX platforms, and Mac OS X. Because Qt is a C++ library, all code produced by Designer is in C++. To support the advanced event handling of Qt, there are some additional preprocessing steps necessary when compiling applications based on Qt. This may seem like unwanted overhead but, in practice, these steps are integrated neatly into the compilation process, and you are rarely bothered by any of the details. Designer works with Qt project files (.pro) directly so that it can be used on an as-needed basis to design and implement the GUI portions of your applica-
Dave is a professional programmer responsible for the original design of the Qt SQL database layer. He can be contacted at
[email protected]. http://www.ddj.com
tion, and it does so in a straightforward and understandable way. Designer’s project management gives you control over application include paths, linking with other libraries, and platform-specific settings; see Figure 1. Designing The original method for designing user interfaces is still available in Designer 3.3.1, and is often the fastest and most straightforward way of using Designer in C++ GUI projects. To fully appreciate what is going on while designing interfaces, an understanding of the Qt object model is necessary. In Qt, all classes inherit from QObject and all visual classes inherit from QWidget. QObject provides the framework for interobject communication and also provides memory management for child objects. QWidget (which is derived from QObject) provides event handling, painting routines, and window functionality. Designer exploits the metainformation available in the Qt object system and, through limited introspection, can make the method names and parameters of Qt classes available to designers. Interfaces are saved in .ui files that are preprocessed by a User Interface Compiler (uic) during compilation. The uic generates regular C++ classes that correspond to the interface you designed. You can extend the behavior of these generated classes by inheriting from them normally. An Address Book application (Version 1 is available electronically; see “Resource Center,” page 5) uses this method of design. The Address Book application displays a list of contacts, and lets you alter and insert contact information using QLineEdit widgets. The latest Designer improves upon this basic method of design by now providing integrated source-code editing of your interfaces, which avoids the extra step of inheriting from Designer-generated classes and significantly speeds up development time. The actual process of building interfaces in Designer is what you would expect from a modern IDE, and Designer supports all widgets provided by Qt (Figure 2). One interesting feature is the automatic layout Dr. Dobb’s Journal, September 2004
tools that let you drop a bunch of controls onto a window, then be able to quickly organize and manage layouts with a minimum of fuss (Figure 3). In addition, widget properties can be edited in groups with the property editor after selecting them in Designer (Figure 4). If you’re familiar with modern GUI builders, you will be comfortable using Designer to build interfaces. You can select different widget types and place them on your windows, grouping and organizing them in any way. You can also set widget
“C++ GUI application development with Qt is fast, maintainable, and flexible” properties, define tool tips, adjust layouts, initialize list boxes, and so on. There are a few annoyances, including the lack of a default action when placing new widgets— pressing Enter usually does nothing, and occasionally double clicking a new widget also does nothing. While right clicking always gives you access to editing basic widget properties, it is annoying to constantly have to resort to this when a reasonable default action should be made available in the main design window. Signals and Slots At the heart of Qt is the signal/slot mechanism, which provides a clean abstraction of event handling. In Figure 5, Designer provides visual signal/slot editing that makes this mechanism intuitive while designing. Even if you have never programmed with Qt before, Designer exposes the most powerful parts of the Qt GUI library to you in an organized fashion. In Qt, signals (which loosely correspond to events) are generated by objects at runtime. These signals are regular class 57
methods that are marshaled by the Qt metaobject system and connected to other widgets via slots (which are also regular class methods). This is a flexible and powerful system for event handling, and it is used extensively throughout the Qt library. An extra precompilation step is necessary using the Meta Object Compiler (moc), which generates the metaobject code used internally by Qt when connecting signals to slots. There are advantages and disadvantages to implementing event handling in this way versus, for example, a template and function objectbased approach (see, for example, http:// libsigc.sourceforge.net/). However, the approach taken by Qt has proven itself over time to be flexible, portable, and fast enough, especially when it is considered
58
that the cost of emitting signals as implemented by Qt is minor when compared to the cost of other code within GUI programs. Creating new slots for your interface can be done in a number of different ways within Designer. While creating signal/slot connections, new slots can be defined for the window to handle them. Also, using the Signal Handler property editor, which displays all the signals generated by the selected widget, you can quickly define new slots that are automatically given reasonable names by Designer. In either case, empty virtual methods are automatically generated by Designer in the corresponding window’s source code. While previous versions of Designer stopped at that point, the latest Designer lets you edit
Dr. Dobb’s Journal, September 2004
the source code for these new slots while you are designing. For example, the bulk of the behavior in the Address Book example is handled by connecting various signals with slots implemented in the AddressBookImpl class, which is the topmost widget in the application. As a developer, you don’t need to worry about all of the internal plumbing implemented by Qt to support signals and slots. Once you understand the concept behind signals/slots, this abstraction speeds up development. The Integrated Editor Designer’s integrated source-code editor is pretty good. It provides syntax highlighting, automatic indentation, tab completion, and limited method name completion. Designer does its best to maintain synchronization between source code and GUI design by adding new methods in the Object Explorer when source code is edited, and automatically creating skeleton code when new methods are added via the IDE. There are a few situations where source code can fall out of sync with the visual design, most notably when you change the class name of a top-level widget. Because Designer cannot keep up with these types of changes, you get errors during compilation and must go back and figure out exactly where Designer lost track. It’s best to design new windows, name controls, and finish the layout before getting into source-code editing. Familiarity with Qt programming is helpful, but not necessary, when editing source code from within Designer. The Qt library is known for its intuitive class hierarchy and method names, so it’s usually easy to accomplish what you want even without a good working knowledge of the library. For example, in the Address Book application, automatically updating line edit controls whenever a new list item is selected is easy to do in the AddressBook::newItemSelected( ) slot (Example 1). The code you are editing for a window is actually a file included by the generated implementation of the widget. The window definition for the Address Book application is contained in addressbook.ui. At compile time, uic generates the corresponding .h and .cpp files that correspond to the design. The custom source code that was added to the AddressBook class is actually contained in addressbook.ui.h, which is included by the implementation of AddressBook in Figure 5. The name of the file containing the custom code for the AddressBook class is a bit of a misnomer, since this file is actually included directly in the implementation file, addressbook.cpp. It would have been more clear to name this file addressbook.ui.cpp. In any case, this included file relies on the http://www.ddj.com
class declaration generated by Designer; therefore, it is important to make sure that any methods added by hand into addressbook.ui.h are also recognized by Designer and added to the list of methods for the AddressBook class; otherwise, it will not compile. Normally, the sourcecode editor within Designer does a good job parsing the code and recognizing both new methods and changes to existing methods. Occasionally, though, the source code can get out of sync with Designer’s definition, so it pays to keep an eye on the Object Explorer while editing source code to make sure it stays up to date. Hopefully, the next version of Designer will address some of these synchronization issues, since editing the source code for slots directly within Designer is by far the most useful feature of this tool. The entire Address Book application, written completely within Designer instead of using inheritance (see Version 2), is available electronically. Resource Management Designer not only manages multiple window designs for a project, but also image and database resources. Consolidating all images from a project makes accessing image resources simple. Images are added to the project’s Image Collection, and behind the scenes Designer generates all the code necessary to include the images into the compiled application, as well as registering the names of the images into the application’s MIME factory so that they can be retrieved with a single function call: addButton->setPixmap ( QPixmap::fromMimeSource( "logo.xpm" ) );
Internally, this static method searches the internal list of registered MIME types until it finds the “logo.xpm” resource that Designer generated. This could all be done by hand, of course, but Designer relieves you of the burden and generates reasonable code. An important new feature in Qt 3.x is the SQL module. Designer has full support for not only adding database connection information to your projects, but also interactively allows you to design with data-aware controls, including data tables, browsers, and views. The Qt SQL module provides uniform access to a variety of databases by presenting a single API that is implemented by a variety of database-specific plug-ins for back ends such as Oracle, MySQL, PostgreSQL, and ODBC. The data-aware widgets in Qt (including QDataTable, QDataView, and QDataBrowser) give you access to efficient data displays as well as inline-editing of data directly from the database. Designer supports these widgets as fully as any other control, which makes development of http://www.ddj.com
Figure 1: Qt Designer 3.3.1.
Figure 2: Populating a window with widgets.
Figure 3: Using layouts to organize widgets.
Figure 4: Editing widgets in a group. Dr. Dobb’s Journal, September 2004
59
nontrivial database applications with Designer just as easy as those created with database RAD tools, such as Microsoft Visual Basic. The main difference being, with Qt, the generated applications run natively on a wide variety of platforms with a simple recompile. Custom Widgets and Templates Adding your own widgets to Designer is usually necessary in any nontrivial program. Designer supports this by maintaining a list of custom widgets that can be added to windows like any other control, although it appears in the design window as an anonymous gray box (Version
3, available electronically, is another implementation of the Address Book application using a custom widget). Just adding your widget’s class name and its relevant signals, slots, and properties to the Custom Widget dialog is enough to let you visually design with it. Designer generates the proper code to include your widget in the interface, and all you need to do is add your custom widget’s implementation to the project. Designer even supports custom widget plug-ins. This requires more coding on your part, but once completed, your custom widget will appear normally in the design window instead of as a gray box. This may be
void AddressBook::newItemSelected( QListViewItem * item ) { // update line edits if ( item ) { firstLineEdit->setText( item->text(0) ); lastLineEdit->setText( item->text(1) ); emailLineEdit->setText( item->text(2) ); } }
Example 1: Updating line-edit controls whenever a new list item is selected.
Figure 5: Editing signals and slots. GUI Design: addressbook.ui
Generated by uic
addressbook.h
Generated by uic
addressbook.cpp #include
addressbook.ui.h
Conclusion The environment in which C++ developers work has a big impact on productivity. Many are quite happy using emacs and a few terminals to develop their applications. Others prefer the bells and whistles of, for example, Microsoft Visual Studio. Between these two extremes lies Qt Designer. Using Designer, C++ GUI application development with Qt is fast, maintainable, and flexible. You have access to all that the Qt library offers including sophisticated widgets, intuitive event handling, and database support. Designer manages entire C++ projects, and it can be customized and extended with user-defined widgets and templates. Designer can even be used on larger projects in such a way that the GUI design is a separate and distinct task from developing application functionality, which may be useful in some development shops. The resulting code generated by Designer compiles and runs natively on almost any platform. Where Designer falls short is its lack of support for compilation. All other major IDEs support the compile/edit cycle extremely well, but Designer is remarkable in that it completely skirts this issue. If you are comfortable with compiling from the command line, you can appreciate this because Designer can essentially stay out of your way. However, it would be a major advantage to new developers if the option existed to launch a compile from within Designer, with the ability to track down compile errors and fix them from within the Designer IDE. Hardcore developers would still have the option to skip this step if they choose, but having the option to compile from within Designer would fill the last remaining hole in an otherwise useful and powerful GUI design tool. DDJ
Figure 6: Files generated by Designer. 60
helpful for those who have separate developers working on GUI design as opposed to nonGUI application functionality, since they will be able to work with custom controls just as if it were any other control within Designer. In practice, it is usually sufficient to give Designer the top-level description of your custom widgets and skip the whole plug-in process. Another helpful tool Designer supports are templates. These can be created for entire window designs, or can be created to provide base class functionality for entire groups of windows or other container widgets. As the name implies, templates provide preconfigured widget layouts that save you the trouble of recreating common layouts (Designer ships with some sample templates including Dialog and Main Window).
Dr. Dobb’s Journal, September 2004
http://www.ddj.com
EMBEDDED SYSTEMS
Bluetooth & Remote Device User Interfaces A protocol for building UIs for small devices RICHARD HOPTROFF
I
originally developed the FlexiPanel protocol in 2002 as an IrDA infrared protocol for engine tuning in hobbyist racing cars. The engine was controlled by a microcontroller that needed to be finetuned with a number of preset values. Incorporating an onboard user interface (such as an LCD display and keyboard) to enter the tuning parameters was impractical — it would be too expensive, heavy, bulky, and fragile. At the time, PDAs with infrared capability were becoming popular, so it seemed logical to use one for the user interface. The FlexiPanel protocol was thus conceived as a way to let embedded systems create UIs on any suitable device that users might have at hand. However, the protocol’s limitations, and its wider potential, soon became apparent. IrDA might be wireless but, in practice, the communicating devices must be held steady within a one-foot (30 cm) range of each other and within line of sight. On the other hand, emerging radio technologies, such as Wi-Fi, Bluetooth, and ZigBee (a low-power protocol), offered 330-foot (100 m) range. Nor did they need exterior real estate — a tremendous product design advantage in terms of cost, aesthetics, and reliability in hostile environments. Consequently, we decided to migrate the technology to Bluetooth, on the grounds that it was widely implemented on remote devices and suited the ad hoc nature of the connection between appliances and remote handhelds. In addition,
Richard is a development engineer at FlexiPanel Ltd and coauthor of Data Mining and Business Intelligence: A Guide to Productivity. He may be contacted at
[email protected]. http://www.ddj.com
Intel had just committed incorporating Bluetooth into its Centrino 2 chipset. While Wi-Fi and ZigBee remain viable transport layers, they currently are not implemented widely enough on handheld devices. At the same time, it became clear that the FlexiPanel protocol’s potential went far beyond engine tuning. It provides a Human Machine Interface for smart dust (intelligent devices comprised of a microcontroller and a few external components), thus far extending their range of application. It offers a UI for “headless” (no screen or keyboard) single-board computers. This promises cost reductions for point-of-sale systems, computer-operated machine tools, and the like, while freeing operators from control panels. In traditional Windows applications, the protocol offers the possibility of a supplementary, roaming UI. Though rarely vital to Windows applications, roaming capability is a liberating addition to any application that might have anything to say to users while away from their desk. In short, the FlexiPanel Bluetooth Protocol is a remote user-interface service for computers, electrical appliances, and other machinery. A FlexiPanel server resides on the application and holds a UI database that reflects the appliance’s human-machine interface needs. A FlexiPanel client can connect at any time, read the database, and display the UI. Users may then control the application from the client device. Using Bluetooth, clients can be up to 330 feet away without need for line-of-sight communication. FlexiPanel clients have been implemented on a range of PDAs and cellphones and are freely available (http:// www.flexipanel.com/DownloadsIndex.htm). Like many higher level protocols such as OBEX file exchange, FlexiPanel sits on top of the RFCOMM serial port emulation layer of the Bluetooth protocol stack (Figure 1). It is not part of the official Bluetooth Standard. However, the Standard is relatively open in that anyone is free to create FlexiPanel clients, and FlexiPanel server licenses are royalty free (http:// www.flexipanel.com/RemoteControlsAPI/ index.htm). As with all emerging technologies, early Bluetooth devices suffered from clunky Dr. Dobb’s Journal, September 2004
operation and compatibility problems. This was particularly true of service discovery— finding out what Bluetooth devices are in range and the services they provide. Many 2002-era devices were limited to preconnection over a virtual serial port, rather than providing service discovery APIs. In the last year, Microsoft’s support for Bluetooth in Windows Sockets has made service discovery a one-click process that even Amazon boss Jeff Bezos would be proud of.
“From the application’s perspective, FlexiPanel is a GUI service just like any other” A User Interface Service From the application’s perspective, FlexiPanel is a GUI service just like any other. It can create controls and subsequently change the properties of those controls. If users modify a control, the application is sent a notification message. The application doesn’t need to know that the UI is displayed remotely. Conversely, just like a web browser, the FlexiPanel client is generic and does not need to know anything about the server it is providing a UI for. (Client software is generally free, too.) Table 1 lists the types of control that may be created. Under the hood, the FlexiPanel protocol is based on just 12 basic types of message passed between client and server (Table 2). The main differences between the FlexiPanel protocol and regular UI services are: • The nature of the client’s UI may be unknown. The controls displayed will always be logically correct but appearances may vary between different client devices. Compare the same slideshow 61
controller UI on a PDA (Figure 2) and a cellphone (Figure 3). If the client device can be anticipated in advance, certain additional preferences can be requested, such as a particular control layout (Figure 2) or keyboard accelerators (Figure 3). • The connection might be broken at any time, for example, if the client’s batteries fail or the client goes out of range. The appliance must enter a failsafe state if connection is lost at a critical moment. • FlexiPanel servers might be small, lowcost devices, such as Parallax’s FlexiPanel peripheral for BASIC Stamps (http://www.parallax.com/), based on a low-end 8-bit microcontroller (Figure 4). Consequently, system requirements on the server side must be extremely lean and communication succinct (unlike XML). The remote client device takes over as many responsibilities as possible. For example, a server is not required to buffer any I/O, manipulate any float-
ing-point numbers, or make any conversions between single-byte characters and Unicode. Bluetooth is a multipoint communication protocol. It is possible for a FlexiPanel server to manage UIs on up to seven remote devices at once. This is only implemented on high-end systems such as Windows servers, but is useful for applications such as restaurant table service, where several wait-staff can connect to the same server at once. A quick disconnect mode is also available, where servers close the connection immediately after connection has been established and control panel information sent. This lets servers send UIs to a large number of clients connecting asynchronously, although the clients have no chance to send any messages back to the server. The FlexiPanel protocol plays no role in authentication, encryption, error detection, or power management. These
are expected to be managed by other layers of the Bluetooth library. Embedded Systems Example In the following example, I use the FlexiPanel server C library to create a remote control panel for a data-logging embedded system. The library is intended to work with the lowest level embedded controllers possible. Therefore, I make no assumptions within the library about serial port buffering or multithreading support. The data logger records the value of a proximity sensor. It has no UI of its own and relies on FlexiPanel to communicate
Application
Audio
SDP Service Discovery
Remote UI
FlexiPanel
OBEX
File Exchange
RFCOMM Serial Port Emulation
L2CAP Logical Link Control
Baseband Link Manager, Link Controller & Radio
Figure 1: FlexiPanel in the Bluetooth protocol stack.
Figure 2: Powerpoint presentation controller UI on a PocketPC.
Logical Control
Example Depiction on a Remote Client
Function/Value
Button Latch
Button Check Box Radio Button Static Text Edit text Progress Bar Slider Table Column Chart Line chart Date Time Picker List Box Popup Menu Client-Specific Dialogs Message Box Client-Specific Dialogs Client-Specific Dialogs
Single-press event. Binary value.
Text Number Matrix Date Time List Section Password Message Blob* Files*
Character string. Integer or fixed-point value. 2D array of numeric values. Seconds to years plus day of week One of n selection. Arranges controls in a hierarchy. Controls access UI. Alerts users. Exchanges binary data. Exchanges files.
Table 1: Controls provided by the FlexiPanel protocol. (∗Optional — a client device is not required to implement this control.) 62
Figure 3: Powerpoint presentation controller UI on a Smartphone.
Dr. Dobb’s Journal, September 2004
Figure 4: FlexiPanel server implemented on an 8-bit microcontroller. The Bluetooth radio is mounted on the reverse side of the board. http://www.ddj.com
with the outside world. The distance measured is displayed as a digital readout on a number control and as a historical log in a matrix control. The data logger (Figure 5) is based on an 80186-based FlashCore embedded controller from Tern (http://www.tern.com/). A GP2D12 analog proximity sensor (Sharp Electronics) is connected to an A/D input and serves as the data source. A BlueWAVE Bluetooth serial module from Wireless Futures (http://www.wirelessfutures .co.uk/products/) is connected to a serial port to enable connection to FlexiPanel remote clients. The data logger’s job is simple and few lines of code are required to implement it (Listing One). All calls to the FlexiPanel server library begin with the prefix FBVS. Like most FlexiPanel applications written for embedded controllers, it consists of fixed sections: initialization, user interface definition, main program loop, client message processing, and an ungraceful disconnect handler. • Initialization. The Bluetooth stack and FlexiPanel server are initialized. This includes giving the UI a name. This name appears in a client’s UI in the list of servers available for connection. • User Interface Definition. Sandwiched between calls to FBVSStartControlList and
http://www.ddj.com
FBVSPostControls, each control is defined by a call to an FBVSAdd… function. Each time FBVSPostControls is called, the previous UI definition is replaced; the UI can thus be changed at any time. FBVSSetOption lets an application request the way a control is depicted on a specific remote device. In Listing One, a pointplot chart is specified if the client is a PocketPC or a Windows computer.
• Main Program Loop. In the main program loop, the FlexiPanel library is polled for messages from client devices. Every second, the sensor is sampled and the sampled value is written to both the digital readout and historical log controls. In addition, every few seconds a ping test is made to check whether a client device is still in range. If a client was connected but
Figure 5: Data logging embedded system using the FlexiPanel protocol to create UIs on PocketPCs.
Dr. Dobb’s Journal, September 2004
63
example, the server clears the matrix control of old data. FBVSN_ClientData, where the remote device modified a control, users press a button, for instance. In this particular application, neither of the controls is modifiable by the client and so nothing needs to be done. Usually, however, the application would be expected to respond to any user interaction at this point. FBVSN_ClientDisconnected, where a remote device is disconnected from the server. In this example, the message is ignored. FBVSN_Abandon, an error occurred. This message has only ever been witnessed during application- device
contact was unexpectedly lost, control is passed to the ungraceful disconnect handler. • Client Message Processing. When clientrelated events occur, the FlexiPanel server library posts notification messages to the application (Table 3). The data logger uses the FBVSGetNotifyCode function to collect these messages. Most notifications are informational and useful only for providing a local indication of the connection status. The four messages that the developer should always consider are: FBVSN_ClientConnected, a remote device connected to the server. In this
Figure 6: Main order screen in the OrderMaster application.
Figure 7: An appetizers subscreen in the OrderMaster application.
Message
Originator (Client/Server)
Purpose
Greetings Goodbye New Control Panel Control Modified Ping Ping Reply Ack New Server Props Update Files Profile Request Profile Reply
Either Either Server Either Either Either Either Server Server Server Client Server
Establishes a connection. Closes a connection. Sends control descriptions to client. Modifies a control's value. Presence check request. Presence check confirmation. Acknowledge receipt of message. Server initializing. Modifies a control's properties. Downloads requested files. Requests device-specific layout advice. Downloads device-specific layout advice.
Table 2: FlexiPanel client-server message types. Notification
Meaning
No Notify Client Connected Client Data Client Disconnected Got Pinged Got Ping Reply Got Ack Got Profile Request
No notable events have happened. Client connected to server. Client modified a control. Client disconnected from server. Client pinged server and server pinged back. Server pinged client and client pinged server back. Client acknowledged receipt of message. Client asked how to lay out controls and server replied.
Table 3: Notification messages that a FlexiPanel server can send to an application. 64
Dr. Dobb’s Journal, September 2004
development due to a readily apparent programming error. In this example, as a precaution, control is passed to the ungraceful disconnect handler if this message is received. • Ungraceful Disconnect Handler. The application must provide for the possibility that the connection is lost unexpectedly. This might occur because the remote device has gone out of range or its batteries are worn out. In this example, no action is necessary. In applications that control machinery, an emergency stop procedure should be implemented. Windows .NET Example The OrderMaster console application uses the FlexiPanel .NET library to create a remote control panel for a restaurant ordertaking system. A Windows server computer with a printer is located near the kitchen and prints out the orders for the kitchen and the checks for the customers. It needs to be Bluetooth equipped and, therefore, will require a USB Bluetooth adapter (ideally a class 1 adapter with a 330-foot range). The wait-staff carry remote devices for taking orders. The application is targeted specifically for PocketPC clients. The UI has been designed using a fat thumbs approach, where the controls are large enough that no stylus is required. In keeping with the FlexiPanel philosophy, however, any FlexiPanel client would be able to connect. A waiter who lost his PocketPC could always use his cellphone to take orders. Indeed, it would be possible for customers to place orders and print out their checks themselves if they had an appropriate device. Figure 6 is the OrderMaster main screen. At the top is a text control for displaying a summary of the current order. Below it are section controls that drill down to specific sections of the menu. At the bottom is a list control to select the table being served and buttons to order the check, clear the order, and confirm the order. Figure 7 is an Appetizer subscreen. At the top is the section control that returns to the main screen. Below it are number controls for setting order quantities for individual items on the menu. The code required to implement OrderMaster is available electronically; see “Resource Center,” page 5. Since much of the code is repetitive and would in practice be replaced with loops working from a menu database, code for subscreens other than the appetizers has not been implemented. The FlexiPanel .NET namespace is called RCapiM. It consists of static function calls for management of the user interface service and classes for each of the 12 control types. Like the data logger, this http://www.ddj.com
application consists of the same five sections: initialization, UI definition, main program loop, client message processing, and ungraceful disconnect handler. • Initialization. The _tmain( ) entry point in midway through OrderMaster (available electronically) begins by initializing the FlexiPanel library, setting up the Bluetooth port, giving the UI a name, and setting up a timer to ping the remote device regularly. Since a PocketPC client is anticipated, several options are requested specifically for it. It should hide its usual navigation buttons and it should regularly ping the server (the computer, that is, not the waiter!). • User Interface Definition. The UI is defined by creating controls and attaching them to an ArrayList called RemoteForm. The RemoteForm is then sent to the FlexiPanel::PostControls static function in order to display the control panel. If the application needs to respond when the user modifies a control, a delegate is added to the OnClientModify event for that control. Since the delegate will be called from a dif-
ferent thread to the main thread, the delegate contains static pointers to controls it needs to access. A delegate is also added to the static OnClientNotify event so that the order can be cleared if a Client Disconnected notification is received (see Table 3). • Main Program Loop. In the main program loop, nothing happens except for waiting for the instruction to quit. All further activities are in response to events. • Client Message Processing. The following delegates respond to events and are managed within the EvtHandler struct: OnClientNotify— if the client notifies it is disconnecting, the order is cleared; OnButCheck— if the Check button is pressed, the check is printed; OnButClear— if the Clear button is pressed, all order quantities are set to zero; OnButConfirm— if the Confirm button is pressed, the order is printed for the kitchen, then all order quantities are set to zero; OnCtlModify — if the Table list box is modified or one of the menu section controls is opened or closed, the status text box is updated; OnPingTimer— the client is pinged. If contact is lost, an Un-
Listing One }
// Bluetooth module is connected to serial port SER1 extern COM ser1_com; #define BTH_BAUD 12 // 115,200 baud for SER1 #define BTH_INBUFF 1024 // SER1 Input buffer size #define BTH_OUTBUFF 1024 // SER1 Output buffer size unsigned char ser1_in_buf[BTH_INBUFF]; // SER1 Input buffer unsigned char ser1_out_buf[BTH_OUTBUFF]; // SER1 Output buffer // UI constants #define CID_ATOD 1 #define CID_CHART_TY 2 #define NUM_CTRL 2 #define NUM_OPTION 2 // function prototypes void ProcessFlexiPanelMessages(void); void HaltProcesses(void); }
void main(void) { int16 loopcount; // initialize serial port (calls serial I/O library) s1_init( BTH_BAUD, ser1_in_buf, BTH_INBUFF, ser1_out_buf, BTH_OUTBUFF, &ser1_com ); // initialize FlexiPanel library and give the UI a name FBVSInit( NULL, NULL, 1, &ser1_com, NUM_OPTION ); FBVSSetDevNameAndCharSet( "Tern Demo" ); // initiate control panel description FBVSStartControlList( NUM_CTRL ); // numeric display of distance FBVSAddNumber( CID_ATOD, CTL_NUM_FIXEDPOINT, "Range", 0, 0, 0, 2, -2, "%% m", NULL); // graphical display of distance log FBVSAddMatrix(CID_CHART_TY, CTL_MTX_DATA_TY | CTL_MTX_Y_FIXEDPOINT | CTL_MTX_Y_2BYTE, "Data Log", 30, 0, NULL, 1, NULL, "Range", "Time", "%% m", "%HH%:%mm%:%ss%", 2, -2, 0, 0, NULL); // suggest how chart might be displayed FBVSSetOption( PPC_DEV_ID, CID_CHART_TY, PPC_ATT_STYLE, PPC_CST_MATRIX_POINTS ); FBVSSetOption( WIN_DEV_ID, CID_CHART_TY, WIN_ATT_STYLE, WIN_CST_MATRIX_POINTS ); // complete control panel description FBVSPostControls( ); // start control panel service FBVSConnect(); // main program loop loopcount = 0; while (1) { // ensure each loop takes around 10ms delay_ms(10); // discover whether client has sent any messages ProcessFlexiPanelMessages(); // every 3 seconds, ping loopcount ++; if (loopcount == 300) { loopcount = 0; // ping if ( FBVSIsClientConnected() && FBVSIsPingSupported() && FBVSPing() ) {
http://www.ddj.com
}
graceful Disconnect Handler procedure is followed. • Ungraceful Disconnect Handler. The application clears the order and waits for the client to reconnect. Future Developments Born almost by accident while trying to optimize engine performance, the FlexiPanel Protocol has evolved into a patented userinterface service for a range of devices from tiny microcontrollers to .NET applications. Future development plans include: • Embedding the protocol directly inside Bluetooth chipsets. This will lower the cost sufficiently so that even basic electrical appliances such as light switches can create remote user interfaces. • Provision of a local Bluetooth to an HTTP bridge so that a web browser anywhere in the world might connect to a FlexiPanel server. • Provision of a local Bluetooth to telecoms bridge so that a FlexiPanel server can be accessed by anyone dialingin using a touch-tone phone. DDJ
// lost contact with remote device; continue cautiously HaltProcesses();
} // every second, log proximity sensor if (loopcount%100==0) { int16 range; DateTimeU dt; // read A/D (calls A/D library) range = fb_ad16( 0xc6 ); // update numeric display FBVSSetNumberControlData( CID_ATOD, range ); // update chart SetToCurrentTime( &dt ); FBVSAddMatrixControlData( CID_CHART_TY, &range, &dt ); // send updated time to client FBVSUpdateControlsOnClient( ); }
void ProcessFlexiPanelMessages(void) { // check for message switch (FBVSGetNotifyCode()) { // nothing has happened case FBVSN_NoNotify: break; // Client has connected; clear the contents of the matrix control case FBVSN_ClientConnected: FBVSSetMatrixControlData( CID_CHART_TY, 0, NULL, NULL ); break; // Client has modified a control. in this app, no controls are // modifiable by the client, so nothing to do case FBVSN_ClientData: break; // Client has disconnected case FBVSN_ClientDisconnected: break; // following messages are informational only and will be ignored case FBVSN_GotProfileRequest: case FBVSN_GotPinged: case FBVSN_GotPingReply: case FBVSN_GotAck: case FBVSN_IncompatibleVersion: break; case FBVSN_Abandon: // Error; generally only gets here during development HaltProcesses(); Reset(); break; } } void HaltProcesses(void) { // In this function, anything controlled by the embedded // controller is put in a fail-safe state. // nothing being controlled in this app, so nothing to do }
Dr. Dobb’s Journal, September 2004
DDJ 65
ECLIPSE
Eclipse & General-Purpose Applications A universal platform, Java IDE, integration tool, and more TODD E. WILLIAMS AND MARC R. ERICKSON
W
hen building desktop applications, you need to start with good design and architecture. Because there is no universally accepted desktop-application framework, most developers design their own architecture, then build it into a framework themselves. However, the costs of this approach are a considerable expense, time, debug effort, support, and aggravation expended on solving a problem that is peripheral to building the business functionality of the application. Another approach is to find a framework that accommodates your needs to simplify and accelerate project development. A “wish list” for such a framework would (among other things): • Implement a clear, consistent, and cohesive architecture. • Support development and execution on all the major desktop platforms (Windows, Mac OS X, Linux, QNX Photon, Pocket PC, HP-UX, AIX, Solaris). • Have UI response that is “snappy,” while maintaining the platform’s native lookand-feel. • Provide a variety of widgets, both standard (buttons and checkboxes) and extended (toolbars, tree views, progress meters). • Provide extensive text processing that include editors, position/change manTodd is vice president of technology at Genuitec and Marc is a principle at Communications & Media Arts. They can be contacted at
[email protected] and
[email protected], respectively. 66
agement, rule-based styling, content completion, formatting, searching, and hover help. • Support the use of platform-specific features (ActiveX, for instance) and legacy software (if necessary). • Enable product branding for the application. • Contain an integrated help system.