JCardente

A Busy Summer

2011-07-22T08:30:00.001-04:00

The summer is proving busier than expected. In June, I started taking remote classes at Stanford in pursuit of a Graduate Certificate in Data Mining and Applications through the Stanford Center for Professional Development (SCPD). So far, I am enjoying my first class, stats202. As I suspected, I really like working with data to find hidden patterns, trends, etc.

At the same time, I have a project at work with an aggressive mid-August deadline. So I've been putting in extra hours. The good news is that the project is going well and I'm doing lots of R programming to analyze performance data. More fun working with data. I like R and am gaining a lot of experience with it through work and school projects.

Any spare time not spent with family is being use to work on a few hobby projects. I'm building a Zen Toolworks desktop CNC machine so that my son and I can make cool things. I bought an Arduino and Ultimate Microcontoller Pack from the MakerShed that I'm having fun with. If that wasn't enough, I'm slowly putting together a plan to build a tricopter.

A busy summer indeed.

TomTom Foolery

2011-05-06T19:39:00.006-04:00

Three years ago I bought a TomTom ONE XL for a family trip. It worked great but I haven't used it much since then. We took another family trip a couple of weeks ago and I again wanted to take the TomTom. I decided to update its maps and thus ensued an unexpected adventure.

I bought an updated (and overpriced) map via the TomTom Home desktop application. Part way through copying the map to the device, it complained that it was out of space. A little digging revealed that there wasn't room for both the old and new maps. I looked for a way to uninstall the original map via the desktop but couldn't find one. Luckily, OSX mounted the TomTom as a FAT formatted disk so I just deleted the old map files. No more out-of-space problem.

I confidently re-started copying the map to the TomTom but ran into another problem. The TomTom suddenly disconnected. Repeated attempts all ended with the same error message that the USB device had unexpectedly disconnected. I tried different USB cables and ports but nothing worked. With the trip looming, it was time for some hacking.

I opened an OSX Terminal and used dd to write files with increasing sizes to the TomTom. It consistently disconnected when writing files larger than 100MB. Writing smaller files with intervening pauses seemed to work OK. Now that I knew what I could do, I turned my attention to what I needed to do.

I figured out that TomTom Home put the new map files at the path,

~/Documents/TomTom/HOME/Download/complete/map/USA_and_Canada/

The directory contained the files,

$ls -lh 
total 1790632
-rw-r--r--  jcardent  staff   7.7K Apr 13 16:25 USA_and_Canada-1.gif
-rw-r--r--  jcardent  staff   1.6K Apr 13 17:22 USA_and_Canada.gif
-rw-r--r--  jcardent  staff   2.6K Apr 13 17:30 USA_and_Canada.toc
-rw-r--r--  jcardent  staff   874M Apr 13 17:30 USA_and_Canada.zip
-rw-r--r--  jcardent  staff   305B Apr 13 17:22 activation.zip

Clearly, the file USA_and_Canada.zip contained the majority of the data. So I unzipped it and found,

$ls -lh
total 1790504
-rw-r--r--  jcardent  staff   252K Jan 10 11:05 USA_and_Canada-308.meta
-rwxr-xr-x  jcardent  staff    60B Jan 10 11:05 USA_and_Canada.pna
drwxr-xr-x  jcardent  staff   3.1K Jan 10 11:04 brand
-rwxr-xr-x  jcardent  staff   446M Jan 10 11:04 cline.dat
-rwxr-xr-x  jcardent  staff   113M Jan 10 11:05 cname.dat
-rwxr-xr-x  jcardent  staff   123M Jan 10 11:05 cnode.dat
-rwxr-xr-x  jcardent  staff    23M Jan 10 11:05 cphoneme.dat
-rwxr-xr-x  jcardent  staff    56M Jan 10 11:05 faces.dat
-rwxr-xr-x  jcardent  staff    30B Jan 10 11:05 mapinfo.dat
-rwxr-xr-x  jcardent  staff    92M Jan 10 11:05 poi.dat
-rwxr-xr-x  jcardent  staff    15M Feb 18 10:53 tables.dat
-rwxr-xr-x  jcardent  staff   4.9M Jan 10 11:05 tmccodes.dat
-rwxr-xr-x  jcardent  staff   129B Jan 10 11:05 traffic.dat

Three files over 100MB, oh bother. But there was no need to fear for I was armed with dd. I proceeded to use a command like the following to copy the large files to the TomTom in 50MB chunks,

dd if=./<map file> of=/<TomTom path> bs=1024 count=52428800 \
  iseek=<offset> oseek=<offset>

After an hour or so, all the data was on the TomTom. I disconnected and rebooted it only to get a "map not authorized" error. After a some curses, I recalled the other downloaded file, activation.zip. I unzipped the file, copied the contents to a couple of places on the TomTom - I wasn't sure where it belonged - and rebooted. Woot! The updated map worked!

I'm happy to report that the TomTom worked flawlessly for our vacation.

Moral of the lesson, know and use your UNIX command line tools.

Diving into R

2011-04-29T06:20:00.001-04:00

I've wanted to learn R for a long time. A new project at work is providing an ideal opportunity to finally use it. So far, it's been a great experience. R is an incredibly powerful tool for data analysis. It's allowed to me dive deep into the project's data and automate much of the analysis process.

Programming in R has been easier than expected. I've previously programmed in Matlab which has helped greatly. Some of the concepts are still foreign but I'm confident that they will become less so with time.

The greatest joy has been getting "lost" for hours writing R functions to analyze the data and produce reports. R's interactive interface has made it easy to build up code in an exploratory manner. This is my preferred programming methodology that, I find, allows me to stay in a flow state for long periods of time. The experience has been very similar to programming in Lisp dialects which I also deeply enjoy.

Although there is a lot of good information about R available for free on the web, I've found the following O'Reilly books the best resource for coming up to speed quickly,

A particularly powerful library is ggplot2 by Hadley Wickham. With it, I've been able to create very complex graphs and charts with minimal code. ggplot2 uses a grammar to create graphics in layers that, at first, can be challenging to learn. The website is informative but the book has been the best resource and well worth the money.

ggplot2: Elegant Graphics for Data Analysis (Use R)

Another useful library is brew which I am using to auto-generate pleasant looking reports in PDF via LaTex.

I look forward to working more with R. Data science is a growing interest of mine and this opportunity to use R is adding to the momentum.

Book Review: Final Jeopardy

2011-04-11T19:39:00.001-04:00

Final Jeopardy: Man vs Machine and the Quest to Know Everything by Stephen Baker

I found the Watson exhibition very exciting. I was therefore eager to read Baker's new book, Final Jeopardy, that accounts the inception of IBM's Jeopardy Grand Challenge and the software team that completed it by creating Watson. Although light on technical details, the book provides a good overview of the primary challenges. It also discusses the non-technical issues that the Watson and Jeopardy teams struggled with in staging the man-machine competition. Overall, a very good and enjoyable book. If you enjoyed Baker's Numerati, you'll probably enjoy this book too.

The next challenge is to create a computer that can write Jeopardy questions rather than just answering them.

Seymour Cray Videos

2011-04-04T18:35:00.001-04:00

I've long admired Seymour Cray as the genius behind early super computers such as the CDC6600, Cray-1, and later Cray systems. However, I know little about Cray himself. So, I was happy to discover two YouTube videos of Cray speaking about his career and systems.

In this 1976 talk, Cray describes the design of the Cray-1. Among other topics, he describes the factors that gave rise to the Cray-1's iconic shape.

Thirteen years later, Cray discusses the design of the Cray-3 and Cray-4 systems in this talk and his decision to use Gallium Arsenide, then a leading edge material. I wasn't aware of the three dimensional modules used in the Cray-3. Cool stuff.

I enjoyed both talks. Cray was much more personable than I expected. He was very humble and claimed ignorance in a number of areas related to computing. It was refreshing to see someone of Cray's caliber display these characteristics.

It was amusing to see that the fundamental problems of building computing systems have remained the same for decades: speed, size, and power. The more things change, the more they stay the same.

Quants: The Alchemists of Wall Street

2011-03-06T09:14:00.001-05:00

Last week, I stumbled across a good documentary by VPRO on quantitative analysts. It features a couple of famous "quants", Paul Wilmott and Emanuel Derman, as well as Michael Osinki who wrote the software used by many banks to securitize mortgages.

The documentary discusses the challenges associated with financial modeling. For example,

Many models were based on limited historical data that was insufficient to represent macro-economic swings.
Many executives did not understand the technical aspects of financial modeling and were therefore unable to recognize the associated risks that led to the subprime crisis.

I strongly agree with Paul Wilmott on the following (paraphrased) point,

People that take risk should be compensated. But they should not be compensated for taking risk with other people's money.

Here here. Wilmott is extremely impressive. When the subprime crisis hit, I was surprised to find out that he had been warning against model related risks. Given his high regard in quant circles, I'm surprised his warnings were not better heeded.

Commemorating Discovery's Last Launch

2011-02-26T19:14:00.003-05:00

In commemoration of the Space Shuttle Discovery's last flight, I decided to post a link to the YouTube videos of MIT's Fall 2005 session of Aircraft Systems Engineering (16.885J). The course was co-taught by ex-shuttle astronaut Jeffrey Hoffman and ex-NASA official Aaron Cohen. It featured many guest speakers from the Shuttle program who went into a lot of technical detail about the system's design and operations.

All of the videos are good but my favorites are,

Lecture 6: Space Shuttle Main Engines.
Lecture 15: Space Shuttle Accidents. An excellent guest lecture by Sheila Widnall describing the investigation of the Columbia accident.
Lecture 16: Guidance, Navigation, and Control. Great overview of the Shuttle's computer systems.
Lecture 17: Mission Control. Guest lecture by Chris Kraft who held prominent positions in Mission Control during the Mercury, Gemini, and Apollo programs.

Whenever I need a hard-core technical fix, I watch one of these videos. Works every time. These were real engineers.

Other materials from this course are available on MIT's OCW website.

Thank you Discovery for twenty seven years of service. It's disappointing that the space program is returning to rockets. It's just so 20th century.

Rickards on Global Sovereign Debt

2011-02-26T05:48:00.002-05:00

It's one thing to read tin-foil hat blog posts about the impending collapse of the global economy. It's another to watch the same message from James G. Rickards, a (seemingly) intelligent and credible source.

I liked Rickard's approach of using dynamic systems theory to analyze global markets and economies. The technique changes the conversation from a philosophical one (i.e. Keynesian vs. Monetarists vs. Austrian) to a scientific, empirical one.

To summarize, Rickards says we're screwed. Decades of deficit spending and the bailout have led to the accumulation of an unsustainable amount of debt - no combination of growth and taxes that can satisfy the liability. Rickard's makes the point that this debt can't magically disappear, it has to be flushed from the system either through default, inflating currency, or debtors and creditors going to war. This sounds sensational until Rickards explains how this happened multiple times in the 20th century alone.

Scary stuff but worth watching. Wishful thinking isn't going to fix the current economic situation. I much prefer a data based approach to understanding and solving the problem. I hope Rickard's is wrong but, if not, I hope someone is listening.

Shared Keyboard Madness

2011-02-25T06:40:00.000-05:00

I'm not alone in my mechanical keyboard madness. Arstechnica posted a good video about ergonomic keyboards. Their recommendation? Mechanical switches and a split layout.

I'm really enjoying the Kinesis Contoured keyboard. The wrist pain I was experiencing has disappeared. I only wish I had a second one for home as it is now uncomfortable to go back to using the MS Natural Ergonomic - the rubber dome keys require a lot more force.

More Watson

2011-02-20T19:49:00.001-05:00

There is a lot of good information available online about Watson. Many of my friends have wondered about Watson's wagering algorithms so I was happy to find this blogpost and video by IBM research. I find Watson's avatar endearing, this video on its creation was fun to watch.

Part of me wonders if (read hopes that) Watson will inspire a whole new generation of AI researchers.

Watson Wins!

2011-02-17T19:41:00.001-05:00

Well, Watson won Jeopardy!. It's an amazing feat. I look forward to seeing where IBM takes the technology.

NOVA has made their episode on Watson's creation free to watch online. IBM has posted a YouTube video of a talk by Dr. David Ferrucci on the overarching DeepQA project. Ken Jennings, one of the human contestants, gave an entertaining live Q&A.

I would love to write software for a system like Watson. As a kid, I was fascinated by fictional super-intelligent computers like HAL, WOPR, and MCP. Over the past year, I've rediscovered a strong interest in data mining and machine learning. While I've helped develop server and storage systems capable of hosting such applications, I have not yet worked with these technologies directly. This is something I'm considering as part of my annual career planning.

Andrew Lo, Kill the Quants

2011-02-11T06:18:00.001-05:00

A good talk by Andrew Lo, Director of the MIT Laboratory of Financial Engineering, on the merit of blaming quantitative methods for the subprime crisis.

Lo main assertion is that,

"blaming quantitative methods for the financial crisis is like blaming accounting and the real number system for accounting fraud"

Instead, he suggests blaming the people that used the methods inappropriately rather than the methods themselves. From what I've read of the subprime crisis, I agree.

Lo partially demystifies the subprime crisis by using a simple example to explain collateralized debt obligations. He demonstrates how pooling loans and securitizing them into new bonds in multiple traunches can produce both higher and lower quality investments. He explains that it was securitization that allowed subprime loans to find their way into low risk funds like pensions and money markets. He also demonstrates how the method fails when the underlying loans are highly correlated.

Lo then discusses the crisis preconditions that Charles Perrow puts forth in his book "Normal Accidents",

Complexity
Tight Coupling

To this Lo adds an additional precondition,

The lack of (frequent) negative feedback

Lo asserts that under these conditions, human behavior naturally leads to crises like the one in 2008. His points greatly reminded of those made by Richard Bookstaber in his book "A Demon of Our Own Design". I found Lo's argument compelling. Without frequent negative feedback, conditions build to a point where proactively unwinding them becomes impossible - the cost is too great to actively decide to incur. The cost inevitably comes but without conscious action.

In closing, a great talk worth watching.

More Keyboard Madness

2011-01-15T18:36:00.001-05:00

Last March, I posted about a growing keyboard obsession and decision to buy a Filco Majestouch mechanical keyboard. Well, the madness continues. I am now the proud owner of a Kinesis Contoured Advantage.

The Filco is a high quality keyboard. The Cherry Blue switches feel great but are indeed noisy - not ideal for late night hacking at home. Actually, even day time hacking was frowned upon by my family. Luckily, I got a closed door office at work which allowed me to use the Filco all day without driving others crazy.

Unfortunately, I started experiencing wrist pain and the evidence pointed to using the Filco. The ergonomic people at work set me up with a keyboard tray to promote better hand positioning. That helped but I felt "trapped" in the "correct" position. Not only did I still have wrist pain, I was even more uncomfortable.

Frustrated, I switched back to using a Microsoft Natural keyboard. The pain subsided but the rubber dome keys felt awful after typing on the Cherry switches. The extra force required to press the keys was noticeable and tiring.

I considered pre-ordering a Truly Ergonomic keyboard but I didn't want to be an early adopter. I'd rather wait until there are many reviews.

I mentioned in the March post that I've long wanted a Kinesis Contoured Advantage keyboard. They look really cool but, more importantly, have many positive reviews online. I decided that it was finally time to try one.

I've been using the Kinesis for a couple of weeks and really like it. The Cherry brown switches feel as good as the Filco's blue switches but without the noise. I really like the thumb keys and use my pinky fingers much less. I remapped the CTRL and ALT keys to the same positions on both thumb pads. Using Emacs and org-mode is now easier and faster. Most importantly, the wrist pain is fading.

It didn't take as long to adjust to the Kinesis layout as I feared. After a couple of hours, I was typing at my usual rate. Switching back and forth between the Kinesis and regular keyboards does take some adjustment but it appears to be getting easier.

The Kinesis may well be my ideal keyboard. Now I'm wondering when I should consider switching to a Dvorak layout. A challenge for another day.

Where's Johnny?

2011-01-02T19:35:00.002-05:00

I've been neglecting this blog lately. Instead of posting, I've been spending my rare spare time exploring multiple interests. Specifically, clojure, data science, and quantitative investing.

I'm hoping to combine these interests and post about them in the near future.

Book Review: The Cuckoo's Egg

2010-11-11T19:06:00.001-05:00

The Cuckoo's Egg Tracking: a Spy Through the Maze of Computer Espionage by Cliff Stoll

In 1986, Cliff Stoll's boss asked him to investigate a $0.75 accounting error for the use of their lab's computer. He quickly discovered that a hacker had penetrated their computer system and was attempting to do the same to the Milnet computers it was connected to. The situation quickly cascaded into a multi-national search for a malicious hacker-spy involving multiple "three letter" government agencies. At the center of it all was Cliff, an astronomer turned system administrator turned digital sleuth. In The Cuckoo's Egg, Cliff provides a detailed account of his adventure and eventual success.

I really enjoyed The Cuckoo's Egg. Although I was vaguely aware of the story, I only recently learned of the book. I was immediately hooked and struggled to put it down.

The Cuckoo's Egg provides a detailed description of 1980's computing, a subject for which I have an irrational fondness. It's a great reminder of how innocent a time that was and how far technology has come.

Timeless, though, were Cliff's creativity and persistence. I wish more people today put as much effort into solving problems, even apparently small ones. Cliff's story remains an inspiration.

Cliffs political retrospection added an unexpected dimension to the story. His initial mental model of government agents was comic book-esque. During the pursuit, he gradually realized that they were just normal people with similar values. Cliff's willingness to alter his political views was also encouraging.

PDF versions of the book are available online. The book was also summarized in the NOVA episode The KGB, The Computer, and Me albeit without much of the detail that made the story interesting.

If you like computer history, cyber-security, and mystery stories then you will likely enjoy The Cuckoo's Egg.

Book Review: Fermat's Enigma

2010-11-05T18:50:00.000-04:00

Fermat's Enigma by Simon Singh

In 1637, Pierre de Fermat, a renown amateur-but-genius mathematician, was reading Diophantus's Arithmetica and wrote the following margin note:

I have discovered a truly marvelous proof that it is impossible to separate a cube into two cubes, or a fourth power into two fourth powers, or in general, any power higher than the second into two like powers. This margin is too narrow to contain it.

In other words, although there are many three integer solutions to Pythagoras's Theorem,

X^2+Y^2=Z^2

There are no three integer solutions for higher powers,

 X^3+Y^3=Z^3
 X^4+Y^4=Z^4
....

Unfortunately, no written record of Fermat's proof has ever been found. Worse, Fermat had a reputation for pranking his fellow mathematicians by claiming to have secretly solved impossible problems. For 350 years, it was uncertain if a proof ever existed. But that didn't stop a lot of people from trying, including some of the best mathematicians in history.

In this book, Simon Singh provides a thorough account of the many efforts to prove Fermat's Last Theorem. Particular attention is given to Andrew Wiles's successful solution in 1994, the result of a seven year solitary effort that shocked the mathematics world.

The book is structured very well. Singh expertly interweaves the history and mathematics behind Fermat's conjecture in an easy to understand and engaging manner. Singh describes the complicated mathematics involved just enough to appreciate Wiles's solution without going into too much detail. The narrative flows evenly and holds the reader's attention well.

Wiles's story is incredible. He was first fascinated by Fermat's Last Theorem as an adolescent. After earning a PhD in mathematics, Wiles found himself uniquely positioned to pursue a proof. He made the bold decision to both work in secret and devote all of his time to developing a proof. For seven years, Wiles worked night and day in isolation until he finally succeeded. After a fatal flaw was found during peer review, he spent an additional year fixing the proof. Wiles's focus, dedication, and determination are truly inspiring.

Fermat's Last Theorem is great book if your into math, history, and solitary geniuses overcoming the odds.

Saving weblinks to org-mode from Safari

2010-09-26T20:10:00.004-04:00

Each day, I come across numerous web articles, blog posts, newsgroup posts, etc, that appear interesting. Often, I discover them while working on another task. To avoid distraction, I typically save their links for later review. Sometimes I drag the links to my desktop. Sometimes I bookmark them in my browser. Sometimes I send them to myself via email. Sometimes, I post them to my delicious account. It's time to admit that I need a better process.

In a prior post, I mentioned that I use Emacs's org-mode to organize my notes and tasks. I recently setup org-mode's Capture capability to easily record the deluge of thoughts that come at random throughout the day. While reading the documentation, I discovered the solution to my link saving woes, org-protocol. In particular, the ability to capture links to an org file directly from a web browser as demonstrated in this screencast.

Imitating the screencast on OS X turned out to be harder than I expected. So, I thought it worth wile to post my approach.

To begin, it's worthwhile to understand how org-protocol captures work. org-protocol is based on Emacs server which allows applications to use Emacs for text editing. A common practice is to have shells use an already running Emacs instance rather than starting a new one. This is accomplished by a helper program, emacsclient, that communicates with the primary Emacs instance. For org-protocol captures, emacsclient is launched with a specially formatted argument.

emacsclient org-protocol:/capture:/tname/http://foo.com

By advising the server-visit-files function, org-protocol detects such arguments and creates org-mode entries from them. A powerful template facility is provided to specify how the argument information is transformed into an org entry. Multiple templates are supported and selected by the argument's tname field. The remainder of the argument specifies the URL, in this case http://foo.com, and an optional note (not shown in the example).

Templates are specified by elisp code like the following,

(setq org-capture-templates
      '(("tname" "Link" entry 
        (file+headline org-default-notes-file "Links to Read")
        "* %a\n %?\n %i")))

This template, called tname, tells org to save the entry in the default notes file under the header "Links to Read" with the url as a sub-heading. This results in something like,

* Links to Read
** http://foo.com

See the Emacs documentation for all of the template facility's capabilities and options.

In the screencast, two "tricks" are used to have FireFox call emacsclient with the argument needed to capture the present page. The first is a bookmarklet that creates the appropriate emacsclient argument,

javascript:location.href='org-protocol://capture://tname/'+
      encodeURIComponent(location.href)+'/'+
      encodeURIComponent(document.title)+'/'+
      encodeURIComponent(window.getSelection())

The second trick takes advantage of the fact that the emacsclient argument is formatted as a URI. The topmost component of a URI is called the URI scheme. The standard scheme, http, represents HTTP hyperlinks and is handled directly by the browser. Many other URI schemes exist and most browsers support launching separate programs, sometimes called URI handlers, to process them. In the screencast, FireFox is configured to launch emacsclient when links with the org-protocol scheme are "clicked".

Duplicating this functionality with Safari on OSX turned out to be harder than expected. In an effort to make things easy, OSX provides the Launch Services API to automate the registration of URI schemes and their handlers. Unfortunately, a manual method isn't provided to specify new URI schemes and handlers. This means Safari can't simply be told to launch emacsclient when org-protocol links are "clicked".

While searching for a solution, The worg website led me to the org-mac-protocol project. Although promising, org-mac-protocol uses AppleScripts executed via a drop down menu. Call me lazy but I really like the bookmarklet approach. org-mac-protocol also provides far more functionality than I was interested in. I like to keep things simple.

A second look at the Launch Services documentation revealed that two mechanisms are provided to register URI schemes and handlers. Using a programmatic API, applications can, at execution time, register themselves as the handler for new URI schemes. Alternatively, applications can include the URI scheme and handler information in their application bundle property list. Of the two approaches, the property list approach looked like the best to pursue.

Property lists are used by OSX to store application and user settings. They're essentially Objective-C objects serialized to XML. Every OSX application contains a default property list in its application bundle that the Finder reads after certain events. While processing property lists, the Finder will register any URI schemes and handlers it finds with Launch Services. With this approach, all that is necessary to register a new URI scheme and handler is to edit an XML text file.

Unfortunately, modifying Emacs's application bundle plist didn't seem to be an option. I didn't see a way to specify the helper program emacsclient as the URI handler.

I knew from prior experience that AppleScripts can be packaged as application bundles. I reasoned that I could write an AppleScript to launch emacsclient, save it as an application bundle, and modify its property list to register the script as a handler for org-protocol URIs. I suspected that this had been done before and a quick google search led me to this stackoverflow thread.

Using AppleScript Editor and the stackoverflow thread as an example, I wrote the following script and saved it as an application bundle called EmacsClientCapture.app.

on open location this_URL
   do shell script 
      "/Applications/Emacs.app/Contents/MacOS/bin/emacsclient " 
      & this_URL
end open location

Next, I edited the script's plist at the path,

EmacsClientCapture.app/Contents/Info.plist

And added the following XML elements just before the final </dict></plist> tags.

<key>CFBundleIdentifier</key>
<string>com.mycompany.AppleScript.EmacsClientCapture</string>
<key>CFBundleURLTypes</key>
<array>
  <dict>
    <key>CFBundleURLName</key>
    <string>EmacsClientCapture</string>
    <key>CFBundleURLSchemes</key>
    <array>
      <string>org-protocol</string>
    </array>
  </dict>
</array>

I then moved the application bundle to the /Applications directory. This caused the Finder to read the property list and register EmacsClientCapture with Launch Services as the handler for the org-protocol URI scheme.

I added the bookmarket described above to Safari and viola! I can now click on the bookmarklet and save a link to the current page in an org-mode file. No more disorganization. Of course, it's now easier to collect distractions but that is a problem for a future post.

Book Review: On Writing Well

2010-09-21T18:54:00.001-04:00

On Writing Well by William Zinsser

Clarity. Simplicity. Brevity. Humanity. Those are the four attributes of good writing that Zinsser promotes and teaches in this classic book on writing.

The book is structured into four parts. Part one, Principles, covers fundamental topics like simplicity, clutter, style, words, and usage. In part two, Methods, Zinsser teaches how to structure a coherent story. Part three, Forms, provides advice on writing interviews, travel stories, technical articles, business communications, and other types of writing. Part four, Attitudes, discusses common feelings and decisions during the writing process. Throughout the book, Zinsser uses examples to illustrate and reinforce his points.

I really liked this book and agree strongly with Zinsser's values. A lot of modern writing is long-winded, complex, and content-free. Simple and clear writing is not only more effective but also more enjoyable. I've always tried to use a simple, direct writing style. I'm eager to apply the book's advice to further improve my writing.

I was greatly encouraged by many of Zinsser's comments on the writing process itself. For example, I consider myself a slow writer. I often spend a lot of time revising my writing to get it "just right". Even simple things like emails and blog posts seem to take an excessive amount of time. I frequently feel insecure about this so I was glad to read the following,

Writing is hard work. A clear sentence is no accident. Very few sentences come out right the first time, or even the third time. Remember this in moments of despair. If you find that writing is hard, it's because it is hard.

Similarly, I was inspired by the following comment in the chapter "Enjoyment, Fear, and Confidence",

Living is the trick. Writers who write interestingly tend to be men and women who keep themselves interested. That's almost the whole point of becoming a writer. I've used writing to give myself an interesting life and a continuing education. If you write about subjects you think you would enjoy knowing about, your enjoyment will show in what you write. Learning is a tonic.

I started this blog to learn by writing about my many interests. I find that explaining a topic often leads to deeper insights. I hope that writing and blogging will help me to continue learning and leading an interesting life.

Brain fitness videos

2010-09-07T18:58:00.001-04:00

The "Thoughts about thinking" post motivated me to improve my brain fitness. To that end, I found the following three talks very informative.

I really appreciate Google posting internal guest lectures to YouTube and GoogleVideo. I have watched many of the computer science talks and learned a lot. It's nice to know that talks on many other valuable topics are also available.

Doing less than your best

2010-08-22T14:42:00.001-04:00

I once learned a valuable lesson - never do well a task that you don't want to do again.

The situation started out innocently. A task for the project I was working on needed to get done. I disliked the task but grudgingly did it for the benefit of the team. I did my best to do the task well with the expectation that I would be rewarded with more enjoyable work. Instead, I was asked to keep doing it. I protested unsuccessfully and was soon miserable. I couldn't understand how acting selflessly and doing a good job led to such "punishment".

I discovered that when you do any job well the benefiters want you to keep doing it. If they're confident you'll produce good results, they would rather encourage you than find a replacement (who may not do as well). I eventually realized that I shouldn't have done a good job in the first place.

Initially, I found this insight disturbing. As a child, I was taught to always do my best at everything. As I grew up, I tried to do my best at school, sports, hobbies, and part-time jobs. Gradually, "always doing my best" became a core attribute of my self-image. Therefore, the notion of consciously doing less than my best just seemed wrong.

Then I made a discovery - some of my role models consciously do or did less than their best to avoid undesirable work.

For example, the legendary physicist Richard Feynman discusses "actively acting irresponsible" in this BBC interview. He also cautioned against administrative roles in this letter to Stephen Wolfram. Donald Knuth and Neal Stephenson are well known for being "bad" at correspondence. On a somewhat related note, Paul Graham warns in this essay against distracting thoughts and activities. More personally, some of my mentors have privately admitted to performing badly at tasks that they don't want to do.

From these examples I've formulated the following three guidelines:

Say "no" to any undesirable tasks.
If unavoidable, only do an adequate job.
Focus all remaining time on excelling at the work you most want to do.

Following guidelines 1 and 2 will hopefully provide more time for pursuing guideline 3. The ideal result is to be so highly valued for doing work you enjoy that you won't get asked to do anything else - the opportunity cost for distracting you will be too high.

For myself, I expect a lot of time and practice will be required to put these guidelines into consistent application. After all, a self-image can be hard to change. Thankfully, I have role models to encourage me.

Thoughts about thinking

2010-07-19T18:51:00.003-04:00

Challenging work assignments, family matters, and home maintenance projects have kept me very busy lately. Hence, the significant drop-off in blog posts over the past couple of months. I'm hoping to correct that soon.

Not surprisingly, I've been thinking a lot about leisure time - in particular its benefits for creative thinking. My reflections are guided by two lectures on the topic.

The first is a GoogleTechTalk by Dr. David M. Levy, No Time to Think. In the talk, Dr. Levy asserts that deep contemplation not only promotes creativity but also provides a sense of calmness and satisfaction. He further argues that deep thinking cannot be forced directly - instead we must make ourselves available to it by seeking out silence, and sanctuary. Dr Levy observes that this requirement for sanctuary conflicts with modern social pressures to multi-task, remain in constant communication, and solve issues through repetitive searches of existing information.

The second is a lecture, Solitude and Leadership, by William Deresiewicz at West Point in 2009. The talk is deeply insightful and worth reading in its entirety but, for this post, can be fairly summarized by the following three points:

Original thinking is a core attribute of leadership.
Formulating original thoughts requires long periods of concentration and distance from the thoughts of others.
Quiet solitude is necessary to do both.

Like Dr. Levy, Mr. Deresiewicz laments social pressures to multi-task, remain in constant communication, and rely on existing information to solve problems. To quote,

Multitasking, in short, is not only not thinking, it impairs your ability to think. Thinking means concentrating on one thing long enough to develop an idea about it. Not learning other people’s ideas, or memorizing a body of information, however much those may sometimes be useful. Developing your own ideas. In short, thinking for yourself. You simply cannot do that in bursts of 20 seconds at a time, constantly interrupted by Facebook messages or Twitter tweets, or fiddling with your iPod, or watching something on YouTube.

and,

Here’s the other problem with Facebook and Twitter and even The New York Times. When you expose yourself to those things, especially in the constant way that people do now—older people as well as younger people—you are continuously bombarding yourself with a stream of other people’s thoughts. You are marinating yourself in the conventional wisdom. In other people’s reality: for others, not for yourself. You are creating a cacophony in which it is impossible to hear your own voice, whether it’s yourself you’re thinking about or anything else.

Thinking originally about difficult problems is an activity that I deeply enjoy and find satisfying. Like Dr. Levy and Mr. Deresiewicz, I reached similar conclusions about distracting activities years ago and have since guarded my time and attention vigorously. I've often been teased for my resistance to social media. At times I've felt self-conscious about this choice, even deficient or outdated. These talks give me renewed confidence in my choices.

The challenge, as indicated at the outset of this post, is finding the time to think. A hard task given the pace of modern society and the high-tech industry in particular.

Org-mode hack: tasks done last month

2010-06-23T20:11:00.003-04:00

I'm a big fan of Emacs's org-mode. Over the past year, I've started using it for everything - tracking tasks, taking notes, and drafting all my reports, papers, and blog posts. Org-mode is the only task-tracking software that I've used for more then a week.

At work, I am required to produce a monthly status report. To automate part of the process, I figured out a way to have org-mode produce a list of the tasks completed during a specific month. Since I couldn't find a similar example through a Google search, I thought I would post my approach for the benefit of others (and as a reminder to myself!).

Below is an example org file containing completed tasks that I'll use to illustrate the approach. The tracking closed items feature has been configured to add a time-stamp when each task is transitioned to the DONE state. The header specifies a category, Foo, that org will associate with all of the tasks in the file.

#+Category: Foo

* DONE Feed the dog
   CLOSED: [2010-04-30 ]

* DONE Mow the lawn
   CLOSED: [2010-05-01 ]

* DONE Take out the trash
   CLOSED: [2010-05-20 ]

* DONE Pay the bills
   CLOSED: [2010-06-01 ]

First, configure org-mode's agenda feature and use the C-c [ command to add the example file to the agenda files list.

At this point, a list of the tasks completed in May can be produced by issuing the agenda tag matching command, C-c a m, and giving it the following match string:

CATEGORY="Foo"+TODO="DONE"+CLOSED>="[2010-05-01]"+CLOSED<="[2010-05-31]"

This should produce the following list (slightly reformatted to fit blog width):

Headlines with TAGS match: CATEGORY="Foo"+TODO="DONE"\
+CLOSED>="[2010-05-01]"+CLOSED<="[2010-05-31]"
Press `C-u r' to search again with new search string
  Foo:        DONE Mow the lawn
  Foo:        DONE Take out the trash

Although this works, entering the search string is a cumbersome task. A better solution would avoid this step.

Agenda provides a way to define custom commands that can perform searches using pre-defined match strings. The following elisp code defines a custom command that performs the above tag search automatically.

(setq org-agenda-custom-commands
  `(("F" "Closed Last Month" 
     tags (concat "CATEGORY=\"Foo\""
                  "+TODO=\"DONE\""
                  "+CLOSED>=\"[2010-05-01]\""
                  "+CLOSED<=\"[2010-05-30]\"")))

After eval-ing this command, typing C-c a F will produce the same list as above without having to enter the match string. This approach is indeed better but uses a hard-coded match string. An even better solution would generate the match string based on the current date.

Although the call to concat in the example above programatically generates the match string, it does so only when the setq is evaluated. If the setq is in an initialization file (e.g. ~/.emacs) the match string will get generated based on the date emacs was started and not the date on which the search is performed. This could produce erroneous searches when using an Emacs instance started before the turn of the month. In such cases, the setq could be manually re-evaluated to generate the correct match string but an automatic solution would be best.

Unfortunately, org doesn't currently support providing a lambda to generate the match string at search time. For instance, this example:

(setq org-agenda-custom-commands
  `(("F" "Closed Last Month" 
     tags
     (lambda ()   
       (concat "CATEGORY=\"Foo\""
               "+TODO=\"DONE\""
               "+CLOSED>=\"[2010-05-01]\""
               "+CLOSED<=\"[2010-05-30]\"")))))

produces the error message "Wrong type argument: stringp, …". Patching org-mode to support lambdas for match strings is an option but I prefer to maintain the stock org-mode code.

Thanks to the near infinite hackability of emacs, it's possible to extend the stock org mode functionality without modifying it directly. The below elisp code defines two new interactive functions that call into org-mode to perform a tag search for a specific month.

(require 'calendar)

(defun jtc-org-tasks-closed-in-month (&optional month year match-string)
  "Produces an org agenda tags view list of the tasks completed 
in the specified month and year. Month parameter expects a number 
from 1 to 12. Year parameter expects a four digit number. Defaults 
to the current month when arguments are not provided. Additional search
criteria can be provided via the optional match-string argument "
  (interactive)
  (let* ((today (calendar-current-date))
         (for-month (or month (calendar-extract-month today)))
         (for-year  (or year  (calendar-extract-year today))))
    (org-tags-view nil 
          (concat
           match-string
           (format "+CLOSED>=\"[%d-%02d-01]\"" 
                   for-year for-month)
           (format "+CLOSED<=\"[%d-%02d-%02d]\"" 
                   for-year for-month 
                   (calendar-last-day-of-month for-month for-year))))))

(defun jtc-foo-tasks-last-month ()
  "Produces an org agenda tags view list of all the tasks completed
last month with the Category Foo."
  (interactive)
  (let* ((today (calendar-current-date))
         (for-month (calendar-extract-month today))
         (for-year  (calendar-extract-year today)))
       (calendar-increment-month for-month for-year -1)
       (jtc-org-tasks-closed-in-month 
        for-month for-year "CATEGORY=\"Foo\"+TODO=\"DONE\"")))

The first function, jtc-org-tasks-closed-in-month, generates an appropriate query string and calls the internal org-mode agenda function org-tags-view. The function defaults to the current month but takes optional arguments for the desired month and year. The function also takes a match-string argument that can be used to provide additional match criteria.

The second function, jtc-foo-tasks-last-month, calculates the prior month and calls jtc-org-tasks-closed-in-month with an additional match string to limit the list to DONE tasks from the category Foo. Executing jtc-foo-tasks-last-month interactively automatically produces a list of the tasks closed in the prior month. For my purposes, this is close enough to the ideal solution. Using the optional match-string argument, I can re-use this solution to search for tasks completed in other categories or with specific tags.

My typical work flow is to archive the closed tasks after my status report is written. Org-mode's agenda makes this an easy task. First I mark all of the tasks for a bulk operation by typing m on each. Then I perform a bulk archive by typing the command B $. This will move the closed tasks to an archive file, typically a file of the same name with an added _archive suffix.

Org-mode is a great productivity tool. Combined with Emacs's hackability, it's possible to create tools optimized for your particular work flow.

Addendum

I found that searching on CLOSED date ranges didn't work in org-mode version 6.34a. The problem appears to be fixed in the 6.36c release so be sure to have the right version if you want to replicate this method.

Book Review: The Quants

2010-05-25T20:08:00.001-04:00

The Quants by Scott Patterson

In The Quants, Patterson provides an intriguing account of Wall Street's most successful quantitative analysts (aka quants) and the role they played in the subprime crisis.

The first few chapters introduce the main players and provide a brief introduction to quantitative finance. Patterson begins by describing how Ed Thorp applied his mathematics background and experience pioneering Black Jack card counting techniques to invent various hedging techniques and start the first arbitrage hedge fund. From there, Patterson lightly introduces other important concepts like Brownian Motion, Random Walk Theory, Efficient Market Hypothesis, and statistical arbitrage. The introduction winds down with the October, 1987 market crash which is used as the context to introduce the "fat tail" contrary point of view personified by Benoit Mandelbrot, and Nassim Nicholas Taleb - a not so subtle foreshadow.

The "middle" of the book discusses the background, career, and substantial success of primarily five high-profile quants: Pete Muller, Ken Griffin, Cliff Asness, Boaz Weinstein, and Jim Simmons. Other Wall Street personalities are also mentioned but to a lesser extent. This part of the book more or less establishes that the above quants are very smart, and very rich.

The last part of the book provides a blow-by-blow account of the sub-prime crisis. All of the quants appeared to be caught off guard, perplexed by the market's "irrational" behavior, and unshure of how to adjust their models to prevent further losses. Throughout the ordeal, many of the quants are forced to question the very foundations of their mathematical models and prior success - was it all just luck?

Over all, I thought this book was OK but felt it tried to cover too much ground as a quantitative finance primer, homage to quants, historical account of the sub-prime crisis, and financial mystery-thriller. Since my interest lies more in the technical details, I was a disappointed with those portions of the book and uninterested in the dramatized historical account. Perhaps I simply had the wrong expectations of the book.

It's also possible that my expectations were set artificially high by Poundstone's excellent book Fortune's Formula which provides a detailed historical and technical account of the events that gave rise to the quantitative finance industry. If you're interested in this topic, then I highly recommend Fortune's Formula.

While reviewing the book to write this review, one passage caught my eye on page 250 regarding a study performed by MIT Professor Andrew Lo and his student Amir Khandani:

There was also the worry about what happened if high-frequency quant funds, which had become a central cog of the market, helping transfer risk at lightning speeds, were forced to shut down by extreme volatility. "Hedge funds can decide to withdraw liquidity at a moment's notice," they wrote, "and while this may be benign if it occurs rarely and randomly, a coordinated withdrawal of liquidity among an entire sector of hedge funds could have a disastrous consequences for the viability of the financial system if it occurs at the wrong time and in the wrong sector."

There is some evidence indicating that the withdrawal of high-frequency liquidity was a contributing factor to the May 6, 2010 flash crash. I doubt the story of the quants is over just yet.

Book Review: Daemon & FreedomTM

2010-04-14T18:50:00.001-04:00

Daemon and FreedomTM by Daniel Suarez

I haven't enjoyed a science fiction, techno-thriller this much since reading Neal Stephenson's Cryptonomicon. I liked Daemon so much that I finished the sequel, FreedomTM, before I got the chance to write a review (or do anything else for that matter).

I tried a couple of times to summarize the basic plot without revealing too much but failed. So I think I'll just say that if you're into computers, AI, hacking, MMORPG's, augmented reality, sustainable technologies, and overthrowing corporate social control then you'll probably like these books. My only criticism is that they are a bit too graphic in places for my taste (mostly violence but some sex).

One of the most refreshing things about the book is that the author is an IT specialist so the technology stuff isn't too bogus. In fact, even the "far-fetched" technology in the book is actually just an exaggeration of the current state of the art.

Preview chapters are available online for both Daemon and FreedomTM if you would like to read a sample before buying. I actually listened to the audiobook version of both books via iTunes which worked out quite well - the reader's voices enhanced the overall experience, especially the Daemon's computer-generated, English-accented female voice.

One of my favorite quotes from the book was:

"Technology. It is the physical manifestation of the human will. It began with simple tools. Then came the wheel, and on it goes to this very day. Civilizations rise and fall based on technological innovation. Bronze falls to iron. Iron falls to steel. Steel falls to gunpowder. Gunpowder falls to circuitry."

I don't think there is any doubt that circuitry, more specifically digital information, is becoming the dominant source of power. Why destroy a nation when you can simply crash its infrastructure and delete its data? Daemon and FreedomTM certainly drive this point home.

The future suggested by Daemon and FreedomTM is both frightening and exciting. Although a work of fiction primarily intended to entertain, I think some valuable lessons and cautions can be drawn from the story. Good stuff.

StudyHack's Stretch Churn

2010-03-29T18:11:00.002-04:00

Although I am no longer a student, I really enjoy reading Cal Newport's StudyHacks blog. In particular, I like its focus on achieving success through good time management, hard focus, deliberate practice, and obtaining outstanding skill.

In this post on James McLurkin, Cal discusses an interesting concept called Stretch Churn. Paraphrased from Cal's post:

Stretch Project: A project that requires a skill you don't have at the outset. Importantly, a stretch project is hard enough to stretch your ability but reasonable enough to be completed.
Stretch Churn: The number of stretch projects you complete per unit time.

The premise is that the higher your stretch churn rate the more likely you are to obtain the kind of skill required to be a leader in your chosen field. As the interview with James demonstrates, highly successful people are adept at maintaining a high stretch churn rate. I suspect this is one of the underlying attributes of Outliers.

I think the stretch churn concept is an important insight because it clarifies how to apply the deliberate practice concept in engineering and research environments. Instead of working on a single problem over a long period of time - a common approach in research - the stretch churn concept suggests that it is better to work on a series of related, hard-but-achievable projects. In a way, this strikes me as the agile development model applied to becoming a domain expert.

On a personal level, I found the stretch churn concept interesting for two reasons. First, it explains why I highly value my advanced development experience - the very nature of the work has allowed me to maintain a high stretch churn rate for years. Second, it helped me realize that if I want to become a real domain expert that I'll have to more tightly focus my stretch projects so that they build upon each other. It's a vector math problem - stretch projects in many different directions result in little change when added together.

I suspect the stretch churn concept will be a valuable addition to my self-development toolbox.

Recovering Deleted JPEGs from a FAT File System - Part 9

2010-03-21T10:49:00.002-04:00

Part 9 in a series of posts on recovering deleted JPEG files from a FAT file system.

A month ago (!), in part 8, we looked at the JPEG file format specification to determine if there was sufficient determinism in the on-disk layout to allow the recovery of deleted files through analyzing the residual data in the file system. The answer was mixed:

GOOD: Uniquely valued markers, discoverable through data inspection, identify the beginning and type of the segments that constitute a JPEG file.
GOOD: the metadata segments have a pre-defined size
BAD: the length of the entropy encoded image data is, to the best of my knowledge, unspecified in the START-OF-SCAN segment header. Instead, an END-OF-IMAGE marker is used to identify the end of the entropy encoded data. The theory is that this is done to allow JPEG files to be written as the image is processed.

Essentially, this means that there is no way to determine through data inspection the length or location of the clusters containing the encoded image data. The only clue available is the END-OF-IMAGE marker at the end of the entropy encoded data.

One option is to discover and analyze latent directory entries in the data area - doing so could provide valuable clues to the start and length of erased JPEG files. The downsides to this approach are added complexity (recovering deleted directory entries) and incompleteness (directory entries for deleted JPEG files may not exist due to reuse).

A simpler approach is to inspect each cluster in the data area to see if it begins with a START-OF-IMAGE marker or contains an END-OF-IMAGE marker. Any extent of clusters bounded by START-OF-IMAGE and END-OF-IMAGE markers stands a good chance of being the data for a contiguous JPEG file - the very kind of file we've been trying to recover in this series. In this post, I'll implement this simple method and test the results. Follow the "Read more" think for the rest of the post.

I added the following code to the fatrecover program being developed alongside these posts to perform the marker scan (excerpted from a larger procedure).

#define JPEG_MARKER_COMMON (0xFF)
#define JPEG_MARKER_SOI    (0xD8)
#define JPEG_MARKER_EOI    (0xD9)

int firstCluster;
int lastCluster;
int clusterIndex;
int byteOffset;

unsigned char  lastMarkerType;
int            lastMarkerCluster;

printf("Scanning clusters:\n");
lastMarkerType    = 0;
lastMarkerCluster = 0;
for(clusterIndex = firstCluster; 
    clusterIndex < lastCluster; 
    clusterIndex++) {

  frClusterRead(pimageInfo, clusterIndex, 
                1, pimageInfo->tmpBuff);

  // N.B. - the following code does not cover the
  //        case of markers spanning cluster boundaries.
  //        Not sure if this is a legal condition for
  //        JPEG files. 
  for (byteOffset = 0; 
       byteOffset < (pimageInfo->clusterSizeBytes-1);
       byteOffset++) {

    // N.B. - SOI markers should be in the first two bytes of the
    //        cluster. This constraint can be relaxed to defeat
    //        attempts to hide images by adding a preamble.
    if ((byteOffset == 0) &&
        (JPEG_MARKER_COMMON == pimageInfo->tmpBuff[byteOffset]) &&
        (JPEG_MARKER_SOI    == pimageInfo->tmpBuff[byteOffset+1])) {
      printf("SOI cluster: %#08x\n",clusterIndex);

      lastMarkerType    = JPEG_MARKER_SOI;
      lastMarkerCluster = clusterIndex;
    }

    if ((JPEG_MARKER_COMMON == pimageInfo->tmpBuff[byteOffset]) &&
        (JPEG_MARKER_EOI    == pimageInfo->tmpBuff[byteOffset+1])) {
      printf("EOI cluster: %#08x  offset: %#x\n",
             clusterIndex, byteOffset);

      if (JPEG_MARKER_SOI == lastMarkerType) {
        printf("** CONTIG JPEG? start: %#08X  length: %d\n", 
               lastMarkerCluster,
               (clusterIndex-lastMarkerCluster+1));
      } 

      lastMarkerType    = JPEG_MARKER_EOI;
      lastMarkerCluster = clusterIndex;
    }
  }
}

Processing the post-deletion test disk image from post 7 with this new code via the shell command jpgscan results in:

$ sw_vers
ProductName:    Mac OS X
ProductVersion: 10.6.2
BuildVersion:   10C540

$ wc -l fatrecover.c 
    1431 fatrecover.c

$ make all
gcc -g -Wall fatrecover.c -o fatrecover

$ ./fatrecover frtest2.dmg 

=== FAT RECOVER v0.0 ===

Opening file frtest2.dmg................OK
Reading boot sector.....................OK
Processing boot sector..................OK
Reading root dir........................OK

AT YOUR COMMAND:

>> ls

LISTING DIR: ROOT
 ATTR     SIZE            NAME          1ST CLUSTER
------  --------  --------------------  -----------
.H..D.         0            .fseventsd  (0x000006)
.H..D.         0              .Trashes  (0x000002)
.H...A      4096            ._.Trashes  (0x000003)
...V.A         0              FRTEST2.  (00000000)

>> fat

FAT TABLE ( KEY: .=free  B=bad  -=used X=last R=reserved)

00000000-0000001F: RXX-XXX.........................
00000020-0000003F: ................................
00000040-0000005F: ................................
00000060-0000007F: ................................
00000080-0000009F: ................................
000000A0-000000BF: ................................
[output omitted for brevity]

>> jpgscan
Scanning clusters:
SOI cluster: 0x000007
EOI cluster: 0x00000c  offset: 0x7f4
** CONTIG JPEG? start: 0X000007  length: 6
SOI cluster: 0x00000d
EOI cluster: 0x000013  offset: 0x564
** CONTIG JPEG? start: 0X00000D  length: 7
SOI cluster: 0x000014
EOI cluster: 0x00001c  offset: 0x6f4
** CONTIG JPEG? start: 0X000014  length: 9
SOI cluster: 0x00001d
EOI cluster: 0x000027  offset: 0x47c
** CONTIG JPEG? start: 0X00001D  length: 11
SOI cluster: 0x000028
EOI cluster: 0x000032  offset: 0x7e6
** CONTIG JPEG? start: 0X000028  length: 11
SOI cluster: 0x000033
EOI cluster: 0x00003e  offset: 0x195
** CONTIG JPEG? start: 0X000033  length: 12
SOI cluster: 0x00003f
EOI cluster: 0x00004a  offset: 0x37d
** CONTIG JPEG? start: 0X00003F  length: 12
SOI cluster: 0x00004b
EOI cluster: 0x00005c  offset: 0x27e
** CONTIG JPEG? start: 0X00004B  length: 18
SOI cluster: 0x00005d
EOI cluster: 0x000082  offset: 0x6ac
** CONTIG JPEG? start: 0X00005D  length: 38
SOI cluster: 0x000083
EOI cluster: 0x0000ac  offset: 0x552
** CONTIG JPEG? start: 0X000083  length: 42

In part 7, we used the contig command to list the location and size of the contiguous JPEG files before they were deleted. For convenience, I copied the information from post 7 below:

>> contig

LAYOUT STATUS OF FILES IN DIR: ROOT

       NAME          1ST      LENGTH    CONTIGUOUS?
 ---------------  --------  --------  -------------
      4.2.05.jpg  0x000083       42     CONTIGUOUS
      4.2.01.jpg  0x00005d       38     CONTIGUOUS
      4.1.06.jpg  0x00004b       18     CONTIGUOUS
      4.1.01.jpg  0x00003f       12     CONTIGUOUS
      4.1.05.jpg  0x000033       12     CONTIGUOUS
      4.1.04.jpg  0x000028       11     CONTIGUOUS
      4.1.02.jpg  0x00001d       11     CONTIGUOUS
      4.1.08.jpg  0x000014        9     CONTIGUOUS
      4.1.07.jpg  0x00000d        7     CONTIGUOUS
      4.1.03.jpg  0x000007        6     CONTIGUOUS
      ._.Trashes  0x000003        2     CONTIGUOUS

Comparing the contig and jpgscan outputs confirms that the CONTIG JPEG? lines accurately reflect the location and size of the contiguous JPEG files before they were deleted - success, the simple marker scan method worked!

The contiguous files discovered by the scan can be recovered manually using the fatrecover utility's extract command that was implemented in part 7. With a little more effort, we can automate the recovery of such extents into files for further analysis. This is fairly straight forward and shouldn't require explanation.

In the next post, we'll take a look at what happens when there are non-contiguous files in the file system. After that, I'll try to fix the long file name code from post 5 and wrap up this part of series.

Wait a moment...

2010-03-19T08:35:00.001-04:00

The other day, I posted a lament about modern (popular) programming being mostly a matter of connecting pre-existing components or libraries with minimal work. In the post I stated that I didn't find such work satisfying.

The next day, however, I realized something - I've just spent nearly a decade in advanced development roles happily creating prototypes by modifying and combining pre-existing software components with the minimal possible work. Spot the inconsistency?

This perplexed me - why did I react this way to Mike Taylor's post when I have enjoyed such prototyping work so much?

After some thought, I concluded that my prototype work has involved modifying complex systems. This has required first understanding enough about each system's design and software to determine the minimal changes required to implement the desired functionality. So, although the eventual changes were relatively minor (100s to 10Ks LOC), along the way I had to obtain a deep understanding to complete the task. I think this is the material difference between the prototyping work I've enjoyed and the kind of "library gluing" that I dislike (and Mike of course!). If true, then there is no inconsistency after all.

Clearly the issue isn't black-and-white - the amount of work performed doesn't represent the amount of understanding required. To some degree this reminds me of the Simplicity Cycle - after a certain point, enough understanding is achieved to make the solution simpler, not more complex. From this perspective, I suspect that the satisfaction that I - and perhaps others - seek is the result of crossing that complexity-understanding threshold - this may be the "grokking" point that was easier to achieve in simpler times (e.g. 8bit programming).

Grokking and Modern Programming

2010-03-16T18:47:00.001-04:00

For this blog, I try not to repost popular links from high traffic aggregation sites - odds are you've already seen them. But Mike Taylor's comments in this post so resonated with me that I felt compelled to discuss it despite the attention it has received.

While reviewing a classic Commodore64 book, Mike segues into a follow-up discussion to his What Ever Happened to Programming post in which he says:

So I think this is part of what I was bemoaning in Whatever happened …: the loss of the total control that we had over our computers back when they were small enough that everything you needed to know would fit inside your head. It’s left me with a taste for grokking systems deeply and intimately, and that tendency is probably not a good fit for most modern programming, where you really don’t have time to go in an learn, say, Hibernate or Rails in detail: you just have to have the knack of skimming through a tutorial or two and picking up enough to get the current job done, more or less. I don’t mean to denigrate that: it’s an important and valuable skill. But it’s not one that moves my soul as Deep Knowing does.

I found this comment insightful as it made me realize that I have been possibly struggling with the same thing.

For as long as I can remember, I've felt compelled to Deeply Know the systems that I work on. Starting with my own adolescent experiments programming 8bit computers, I've enjoyed diving deep into the machine to understand its fundamental operation and then using that knowledge to grok whole-system behaviors. As Mike states in the post, this was possible to do in the 8bit days due to the simple machines and books providing all of the necessary information (my tome was Your Atari Computer which still sits on my bookshelf as a reminder of those happy times).

Unfortunately, two things have happened since then - machines have gotten more complicated and having a deep understanding seems to be less valued.

The first point is obvious, computers have gotten more complicated on every level - hardware architectures, operating systems, applications, and networking. Although the fundamentals can be learned, obtaining deep expertise in any of these areas requires specialization.

Having spent most of my career working on large-scale, enterprise computing and storage systems, I've experienced the leading edge of this expanding complexity first hand. In my first job, I think I did pretty well at understanding large portions of that machine but it's been a losing battle since then. The systems that I now work with are now so numerous and complex that it's impossible to deeply understand them all - but I try.

Lately, I've been trying to do more hobby projects to have fun, and expose myself to domains outside of work. But in doing so I find that I quickly run into the second point that Mike's What Ever Happened to Programming post captures well - the hero of modern programming is the person that can stitch together libraries in the shortest amount of time in the fewest lines of code. The greatest heroes are those that can create and launch a startup in less than 24 hours while on a bus. That's great but it's not for me - I just don't find this form of programming satisfying.

I've been overly nostalgic lately, hence recent posts on clicky keyboards, old computer books, and old computer commercials. At first, I thought a looming birthday was to blame but Mike's post has me thinking that it's really a reaction to the shift in programming. The kind of work I like to do doesn't seem to be where all the "action" (read capital investment) is.

It's unreasonable to expect the world to revert back to the way things were. Therefore, there are two possible reactions:

Deal with it and change with the times
Pick a niche were it is possible to "grok" the system and specialize. This doesn't mean building everything from scratch but rather picking a stable domain that allows an accumulated understanding of as much of the system as I care to know.

Traditionally I've been a generalist but I must admit that option 2 seems much more attractive than 1. I guess this is something to reflect on while planning out my future career.

Keyboard Madness

2010-03-12T19:50:00.001-05:00

Last year, I decided to finally become a competent touch-typist and better Emacs user. An unforeseen result of both decisions is that I am developing a mild keyboard obsession.

For the past couple of years I have been using a Microsoft Natural Ergonomic keyboard which has been good but lately I've felt the urge for a change - an irrational desire I'm sure.

Somewhere along the way in considering a new keyboard, I thought it would be cool to get a mechanical model. Probably due to nostalgia, the sound of a "clicky" keyboard is just one of those aesthetic things that makes me think of "real" programming and helps me enter a flow state.

Not knowing anything about mechanical keyboards, I thought it best to do some research. Through the power of Google, I found:

this blog post on mechanical keyboards with a video demonstration of various models.
this video summarizing the attributes of various mechanical switches.
many, many YouTube videos of people typing on various keyboards

After reviewing this material, I considered four options:

Kinesis Advantage Contoured: well known for its ergonomics and "cool factor". However, the high price (~$300) and unusual layout made me hesitant.
Unicomp Customizer 104: based on the same buckling spring technology as the renown IBM Model M and reasonably priced at $70. I decided against it mainly due to the greater key resistance.
Das Keyboard: a popular keyboard amongst geeks that uses Cherry Blue switches (tactile, and clicky) and priced at $130. Unfortunately the glossy case reportedly attracts an abnormal amount of dust.
Filco Majestouch Tenkeyless: an imported keyboard available with either Cherry Blue or Cherry Brown (tactile, no click) switches available from elitekeyboards.com for ~$120.

In the end, I went with the Filco after reading many positive reviews. While I came close to buying the brown switches, I decided that I really wanted that aesthetic "clicky" sound of the blues.

It's only been a couple of days but so far I really like the Filco. The keys feel smooth and solid - my MacBookPro keyboard just feels wimpy now. The switches are definitely clicky, this YouTube video provides a pretty good example. The only negative is that I miss the ergonomic design of the Microsoft keyboard.

I'm just using the Filco at home for now to avoid driving my cube neighbors nuts with all the clicking but if things go well perhaps I'll buy another Filco with the brown switches for work.

Join the mechanical keyboard retro-revolution!

The Kahn Academy

2010-03-03T19:24:00.001-05:00

About a month ago I discovered The Kahn Academy. Since then, I've found myself spending spare moments watching the video tutorials to refresh my memory on a number of topics including finance, banking, the credit crisis, statistics, linear algebra, and physics. Although short (~10 minutes), the tutorials are very well done and a great resource.

Evidently, the creator, Salman Kahn, started out making video tutorials for a geographically distant niece. Unexpectedly, other people around the world began watching the videos and sending positive feedback. This motivated Kahn to turn the effort into a non-profit venture dedicated to providing high-quality, free educational materials. An inspiring story.

Also impressive is Kahn's simple approach of drawing diagrams on a "black board" in real-time - very similar to back-of-the-napkin visual brainstorming. Like all good teachers, Kahn's deep understanding allows him to discuss complex topics in a readily understandable manner.

If you've got a spare moment, I encourage you to check out a video.

How the World Will Try to Stop You

2010-02-23T04:28:00.001-05:00

The other day, I watched a recorded lecture on Google Video by University of Waterloo Economics Professor Larry Smith entitled "How the World Will Try to Stop You and Your Idea". The lecture was given to students interested in entrepreneurship with the goal of advising them on how to overcome resistance.

The points that I took away from the lecture were:

Entrepreneurs, especially young ones, are often given mixed messages. They are encouraged to change the world but when they try to are told that they won't be successful.
The vast majority of people are busy beyond belief. While it may seem like most are incapable of substantive thought, the fact of the matter is that they are simply too busy to do so.
Because they are too busy, most people rarely listen closely. This means that their feedback is very superficial and shouldn't be taken seriously.
Common criticisms are "it's been tried before" and "it won't work". It's important to counter these comments with probative questions like "when was it tried?" and "why not?". A lack of response indicates a baseless criticism. The rare factual response may provide useful information to refine the idea.
Young entrepreneurs are often told to get more experience, earn their "spurs", wait their turn, and suffer a few failures before starting a venture. This implies that entrepreneurs should get more degrees, work in a big company for 15 years, and wait until their forties to start a company. This is nonsense, history is full of examples of young, inexperienced people changing the world.
Instead of fighting resistance, avoid it. Don't tell anyone what you are really up to. Keep your own counsel and only tell people what they need to know. The best way to change the world is to sneak up on it.
Ultimately, courage is needed to ignore negative feedback. Unfortunately, there is no easy way to acquire it.

Regrettably, one of the two cameras used to record the lecture had a faulty audio connection. As a result, parts of the recording are not understandable. It's a shame that the audio from the working camera wasn't dubbed into the recording to fix the problem. Regardless, the talk is still worth listening to for the audio that is understandable.

I found many of Professor Smith's comments insightful and in-line with my experiences. For example, I've spent the majority of my career in advanced development and have heard the "it won't work" and "it's been tried before" feedback almost daily. Professor Smith's talk helped me realize that I now reflexively ask the "why" and "when" follow up questions. As he indicated, the criticism is often either outdated or baseless.

I also often run into the too-busy-to-think dilemma and presently spend the majority of my time supporting long-running campaigns to gradually get people to recognize and embrace innovative opportunities. These campaigns can be a lengthy process but the alternative is rash decisions based on limited thought which I think causes more harm than good.

Although I don't like to admit it, I have allowed myself to fall victim to the "need more experience" feedback more than once - sometimes it was even self-generated after working alongside extremely talented colleagues. The result, I now have multiple degrees and 14 years experience working in a large company. The good news is that I am approaching my forties so perhaps "my time" is nearing! Humor aside, I now recognize that focus and persistence are often more important for success than experience. That said, I strongly believe in continuous self-development and am always eager to obtain new knowledge and experiences. I think it's a matter of keeping a healthy balance between humility and hubris.

In summary, I really enjoyed this lecture. Professor Smith is clearly very thoughtful about many topics and passionate about helping students - both were inspiring to watch. If you have the time, I recommend seeing it for yourself.

A few years ago, I had a similar experience with another of Professor Smith's recorded lectures on the potential of expert systems. That lecture made a significant impression on me and continues to factor into my long-term career goals. I'm presently reading Professor Smith's book on the topic, Beyond the Internet: how expert systems will truly transform business, and look forward to writing its review in a future post.

In the immortal words of Guy Kawasaki, don't let the bozos grind you down!

Recovering Deleted JPEGs from a FAT File System - Part 8

2010-02-18T08:46:00.004-05:00

Part 8 in a series of posts on recovering deleted JPEG files from a FAT file system.

In part 7, I demonstrated recovering deleted JPEG files through knowing their pre-deletion location in a FAT file system. In the real use-case of recovering accidentally deleted files, the locations are unknown making this approach impossible.

Recovering deleted files without knowing their location requires a method to find them within the unerased data. In this post, I'll show how the structure of a JPEG file can be used to do just that. Follow the read more link for the full discussion.

JPEG File Structure

Generally speaking, files meant to be processed programmatically employ some form of deterministic structure. Two common approaches are to partition the file into well defined segments or use an embedded catalog to record the file's contents (similar to a file system directory). Regardless of the approach, this deterministic structure can be used to reconstitute a file from its residual data.

In JPEG's case, the segmentation approach is used. The official JPEG format is specified in Annex B of the ISO/IEC International Standard 10918-1 - otherwise known as the JPEG Interchange Format (JIF). The specification defines:

a variety of segment types to store metadata, compressed image data, etc.
the combinations of segment types that form valid JPEG files.
unique two-byte markers used to demarcate segments and other key aspects of a JPEG file's structure.

For the purposes of this discussion, the markers are particularly important.

Every two-byte marker consists of the value 0xFF followed by a non-zero value representing the marker's type. In some cases, markers may be proceeded by a series of 0xFF "fill bytes" to meet alignment requirements - these fill bytes can be ignored. To avoid false markers in segment payloads (e.g. compressed image data), all non-marker related 0xFF values must be followed by x0x00 to escape them - the null bytes should be ignored during processing. This simple marker scheme allows a JPEG file to be parsed without having to interpret each constituent segment.

Apparently, the JIF format is rarely used in practice due to its complexity. Instead, two simplified variants - JFIF and EXIF - are commonly used instead. Both JFIF and EXIF utilize JIF's built-in extension mechanism and marker values. This means that a program that understands JIF markers can determine the structure of both JFIF and EXIF files.

An Example

To further understand the structure of a JPEG file, let's examine one of the test image files. Inspecting the first 128 bytes of the file 4.1.01.jpg using hexdump results in:

$ hexdump -n 128 -s 0 -C images/4.1.01.jpg
00000  ff d8 ff e0 00 10 4a 46  49 46 00 01 01 01 00 48  |......JFIF.....H|
00010  00 48 00 00 ff db 00 43  00 03 02 02 03 02 02 03  |.H.....C........|
00020  03 03 03 04 03 03 04 05  08 05 05 04 04 05 0a 07  |................|
00030  07 06 08 0c 0a 0c 0c 0b  0a 0b 0b 0d 0e 12 10 0d  |................|
00040  0e 11 0e 0b 0b 10 16 10  11 13 14 15 15 15 0c 0f  |................|
00050  17 18 16 14 18 12 14 15  14 ff db 00 43 01 03 04  |............C...|
00060  04 05 04 05 09 05 05 09  14 0d 0b 0d 14 14 14 14  |................|
00070  14 14 14 14 14 14 14 14  14 14 14 14 14 14 14 14  |................|

To make the output clearer, the markers have been bolded and color coded.

First, we see that the file starts off with the marker 0xFF_D8, this is the Start-of-Image marker (SOI) that must begin all JPEG files. SOI markers stand alone and do not have an associated segment.

Next comes the marker 0xFF_E0 which identifies an APP0 application specific segment. Application segments are JIF's built-in extension mechanism to allow application specific information to be embedded inside JPEG files. The JIF standard reserves 16 markers (0xFF_E0 to 0xFF_EF) for application segments which are available for general use - the JIF standard makes no attempt to assign application segments to specific applications. By convention, JFIF files use an APP0 segment while EXIF files use an APP1 segment. To guard against other applications using the same application segments, both JFIF and EXIF identify themselves by including the 'JFIF' or 'EXIF' ASCII string in the 4th through 7th bytes of the segment (from the marker's first byte). In this case, we see that the APP0 segment indeed contains the string 'JFIF' in bytes 6 through 9.

After the marker, each segment begins with a two-byte length parameter (excluding the marker). The output above indicates that the APP0 is 0x10 bytes long and sure enough the next marker is found at offset 0x14. This time the marker 0xFF_DB indicates the beginning of a quantization table segment (DQT) that is 0x43 bytes long. This is followed by another DQT segment at offset 0x59.

Similarly analyzing the remainder of the file reveals the following markers and segments.


OFFSET	MARKER	SEGMENT?	LENGTH(B)	DESCRIPTION
0X0000	0XFF_D8 (`SOI`)	N	-	Start of image
0X0002	0XFF_E0 (`APP0`)	Y	0X10	Application segment
0X0014	0XFF_DB (`DQT`)	Y	0X43	Quantization table
0X0059	0XFF_DB (`DQT`)	Y	0X43	Quantization table
0x009E	0xFF_C0 (`SOF0`)	Y	0x11	Start of frame
0x00B1	0xFF_C4 (`DHT`)	Y	0x1D	Huffman table
0x00D0	0xFF_C4 (`DHT`)	Y	0x3E	Huffman table
0x0110	0xFF_C4 (`DHT`)	Y	0x1B	Huffman table
0x012D	0xFF_C4 (`DHT`)	Y	0x37	Huffman table
0x0166	0xFF_DA (`SOS`)	Y	UNSPECIFIED	Start of scan
0x5B7D	0xFF_D9 (`EOI`)	N	-	End of image

Houston we have a problem

Notice in the table above that the SOS segment has an unspecified length. Based on my reading of the JIF specification and other references, the length of the entropy coded image data in the SOS segment is not explicitly specified. Instead, it is terminated by either an EOI or other marker. I suspect this was done to allow encoders to generate JPEG files as images are compressed - in this case the length of the compressed data is unknown when the SOS is started.

This presents a problem for recovering deleted JPEG files as it means their structure isn't completely deterministic. In the next post, I'll discuss the limitations this imposes and demonstrate how markers can be used to recover contiguous deleted files.

The Doctor's Computer

2010-02-11T18:33:00.000-05:00

Who knew, The Doctor prefers Prime Computers. I love these.

Book Review: The Tinkertoy Computer

2010-02-11T18:00:00.001-05:00

The Tinkertoy Computer by A.K. Dewdney.

After reading The Planiverse, I picked up a couple of Dewdney's other books. Published in 1993, this book is a compilation of some of his articles from the periodicals Scientific American and Algorithm.

The book contains 23 chapters organized into four themes. Of them, the following were my favorites:

Theme One: Matter Computes

Chapter 1: The Tinkertoy computer - an account of a tinkertoy computer built by Daniel Hillis and others at MIT designed to play Tic-Tac-Toe.
Chapter 2: The Rope-and-Pulley Wonder - methods for building boolean logic blocks out of ropes and pulleys.
Chapter 6: Dance of the Tur-mites - Turing machines and cellular automata.

Theme Two: Matter Misbehaves

Chapter 8: Star Trek Dynamics - implementation details of a 1970s era computer game.
Chapter 9: Weather in a Jar - the Lorenz attractor and simple models demonstrating the behavior.
Chapter 11: Designer Fractals - iterated function systems and their use for creating fractal patterns.

Theme Three: Mathematics Matters

Chapter 13: Mathematical Morsels - a summary of mathematical puzzles by Ross Honsberger.
Chapter 14: Golygon City - an introduction to golygons.
Chapter 15: Scanning the Cat - a simple algorithm for reconstructing 2-D images from 1-D shadows.
Chapter 16: Rigid Thinking - rigidity theory, and flexible nonconvex surfaces.
Chapter 17: Automated Math - an algorithm for determining the rules for numerical sequences.

Theme Four: Computers Create

Chapter 19: Chaos in A Major - the use of logistic maps to create chaotic music.
Chapter 23: Latticeworks by Hand - algorithms for creating lattices.

As you can tell, I more or less enjoyed the entire book. This wasn't surprising given that I bought the book because it touched upon a number of topics that I find very interesting: complexity theory, fractals, math puzzles, physics simulations, geometric patterns, and algorithms.

I was, however, pleasantly surprised by the nostalgia invoked by the simple programs presented in the book. The short, simple BASIC programs reminded me of the many, many hours I spent programming 8bit computers during my adolescence. I still recall the feeling of awe that resulted from seeing simple programs like these produce seemingly "magical" results. Computing was much simpler then but no less rewarding - hopefully short but powerful programs like these aren't becoming a lost art.

Dynabook reflections

2010-02-06T06:29:00.003-05:00

I'm sure like many others, the recent iPad excitement has led me to think more about Alan Kay's Dynabook concept.

Some think the Dynabook is just a highly portable computer such as a conventional laptop or tablet computer. Kay, however, had a much grander vision - the Dynabook was to be an easy to use and program "instrument" that would allow "children of all ages" to learn experientially through simulation.

Kay and Goldberg's 1977 article, Personal Dynamic Media, briefly discusses the Dynabook as a learning device and their successful results from letting children use the "Interim Dynabook" - otherwise known as the Xerox PARC Alto. Kay explores this topic in greater depth in his talk Doing With Images Makes Symbols. Howard Rheingold discusses the Dynabook's history and potential as a "fantasy amplifier" in greater depth in Chapter 11 of his book Tools for Thought (a great book, available for free online here).

Kay conceived of the Dynabook in 1968 based on a number of influences including:

Vannevar Bush's Memex
Ivan Sutherland's Sketchpad (video)
Douglas Engelbart's Augmenting Human Intellect research and ground breaking NLS project (video of the famous demo)
Seymour Papert's use of Logo to teach children mathematics (video)
The learning theories of Jerome Bruner and Jean Piaget

In his talk at the Computer History Museum's 40th Anniversary of the Dynabook event, Kay does a great job of describing how these works influenced his thinking.

Kay's pursuit of the Dynabook produced many significant innovations like Object Oriented Programming and the overlapping window graphical user interface. It has also been the motivation behind his support of efforts like the One Laptop Per Child program, Squeak project, and EToys learning environment.

Modern technology now makes it possible to build portable computers that strongly resemble the Dynabook's physical form - the iPad is a great example. However, I think little progress has been made towards creating software that realizes the fantasy amplifier vision.

Kay is famous for saying that the computer revolution hasn't happened yet. I tend to agree - current computing seems almost primitive compared to the work cited above. I suspect the vast majority of computers are used today as mechanistic productivity enhancers (office apps), communicators of trivialities (tweets?), and sensory overloading distractions (games, video, etc).

The iPad will certainly be used for the same purposes - in fact Job's specifically profiled these use-cases in his keynote speech. However I think the iPad has the greatest potential in the education space. Transforming textbooks into eBooks is only the first step - the next is to add interactive learning aids like simulations for exploratory experimentation. If (when?) this happens, the Dynabook will finally have come to life.

Perhaps it's time to download the iPad SDK, watch Stanford's iPhone Development class on iTunes, and lend a hand in making the revolution happen.

Recovering Deleted JPEGs from a FAT File System - Part 7

2010-01-28T18:18:00.000-05:00

Part 7 in a series of posts on recovering deleted JPEG files from a FAT file system.

After a hiatus due to the holidays, personal matters, and work-stuff I'm ready to continue the FAT Recover project. In this post I'll

finally demonstrate the two principal assumptions that this project is based on.
actually recover deleted files using a manual approach.

Follow the "read more" link for the detailed discussion.

But first a mea culpa - I've discovered that the code for long file name support in post 5 is utterly broken. The code works for files that only use a single long file name entry but does not correctly process file names spanning multiple entries. For now, I'll side-step the issue and post a fix at a later time. I'll also update post 5 to warn future readers. Apologies for the error - that's the danger of hacking in the wee hours and minimal unit testing.

By this point, it's likely apparent that this project is based on two assumptions:

Deleting a file from a FAT file system often does not erase the associated data.
In simple cases - like a digital camera saving pictures on a fresh memory card - files are stored contiguously in FAT file systems.

To test if these assumptions hold, let's create and analyze a new disk image with multiple JPEG files.

Expanding on the method from post 2, the following shell script creates a new disk image and copies to it ten images from the test corpus.

#!/bin/bash

IMAGENAME=frtest2
VOLNAME=FRTEST2
VOLSIZE='-megabytes 16'
MOUNTPATH=/Volumes/${VOLNAME}
TESTPATH=/Users/jcardent/projects/fatrecover2/test/images
TESTFILES=`ls -1Sr ${TESTPATH}/4*.jpg | head -10`

hdiutil create \
         -fs "MS-DOS FAT16" \
         ${VOLSIZE} \
         -layout NONE \
         -volname ${VOLNAME} ${IMAGENAME}

hdiutil attach ${IMAGENAME}.dmg

for file in $TESTFILES
do
    echo "Copying file " ${file}
    cp ${file} ${MOUNTPATH}
done  

hdiutil detach /Volumes/${VOLNAME}

Mounting the image and listing the root directory confirms that ten image files were copied to the encapsulated FAT file system.

$ hdiutil attach frtest2.dmg 
/dev/disk1                      /Volumes/FRTEST2

$ls -ao /Volumes/FRTEST2/
total 712
drwxrwxrwx  1 jcardent  16384 Jan 26 07:18 .
drwxrwxrwt@ 4 root        136 Jan 26 07:18 ..
drwxrwxrwx@ 1 jcardent   2048 Jan 26 07:18 .Trashes
-rwxrwxrwx  1 jcardent   4096 Jan 26 06:30 ._.Trashes
drwxrwxrwx  1 jcardent   2048 Jan 26 07:18 .fseventsd
-rwxrwxrwx  1 jcardent  23423 Jan 26 06:30 4.1.01.jpg
-rwxrwxrwx  1 jcardent  21630 Jan 26 06:30 4.1.02.jpg
-rwxrwxrwx  1 jcardent  12278 Jan 26 06:30 4.1.03.jpg
-rwxrwxrwx  1 jcardent  22504 Jan 26 06:30 4.1.04.jpg
-rwxrwxrwx  1 jcardent  22935 Jan 26 06:30 4.1.05.jpg
-rwxrwxrwx  1 jcardent  35456 Jan 26 06:30 4.1.06.jpg
-rwxrwxrwx  1 jcardent  13670 Jan 26 06:30 4.1.07.jpg
-rwxrwxrwx  1 jcardent  18166 Jan 26 06:30 4.1.08.jpg
-rwxrwxrwx  1 jcardent  77486 Jan 26 06:30 4.2.01.jpg
-rwxrwxrwx  1 jcardent  85332 Jan 26 06:30 4.2.05.jpg

Since the last post, I've made a number of enhancements to the fatrecover program that I am developing for this series. One new feature is a simple shell that allows interactively analyzing a disk image. Building and running the program results in:

$ sw_vers
ProductName:    Mac OS X
ProductVersion: 10.6.2
BuildVersion:   10C540

$ wc -l fatrecover.c 
    1348 fatrecover.c

$ make all
gcc -g -Wall fatrecover.c -o fatrecover

$./fatrecover frtest2.dmg 

=== FAT RECOVER v0.0 ===

Opening file frtest2.dmg................OK
Reading boot sector.....................OK
Processing boot sector..................OK
Reading root dir........................OK

AT YOUR COMMAND:

>> help
      quit     exits program
      help     displays commands
   bsector     prints boot sector
   fsareas     prints size and location of fs areas
       fat     prints file allocation table
        ls     prints current directory
     chain     prints cluster chain
    contig     prints file continuity status
  checksum     prints cluster checksums
   extract     extracts clusters to file

>>

Listing the root directory within fatrecover also shows the ten copied files (and the volume name entry which is usually hidden).

>> ls

LISTING DIR: ROOT
 ATTR     SIZE            NAME          1ST CLUSTER
------  --------  --------------------  -----------
.....A     85332            4.2.05.jpg  (0x000083)
.....A     77486            4.2.01.jpg  (0x00005d)
.....A     35456            4.1.06.jpg  (0x00004b)
.....A     23423            4.1.01.jpg  (0x00003f)
.....A     22935            4.1.05.jpg  (0x000033)
.....A     22504            4.1.04.jpg  (0x000028)
.....A     21630            4.1.02.jpg  (0x00001d)
.....A     18166            4.1.08.jpg  (0x000014)
.....A     13670            4.1.07.jpg  (0x00000d)
.....A     12278            4.1.03.jpg  (0x000007)
.H..D.         0            .fseventsd  (0x000006)
.H..D.         0              .Trashes  (0x000002)
.H...A      4096            ._.Trashes  (0x000003)
...V.A         0              FRTEST2.  (00000000)

Printing the FAT table suggests a well-ordered layout of the JPEG files in the data area.

>> fat

FAT TABLE ( KEY: .=free  B=bad  -=used X=last R=reserved)

00000000-0000001F: RXX-X..-----X------X--------X---
00000020-0000003F: -------X----------X-----------X-
00000040-0000005F: ----------X-----------------X---
00000060-0000007F: --------------------------------
00000080-0000009F: --X-----------------------------
000000A0-000000BF: ------------X...................
000000C0-000000DF: ................................

Inspecting the cluster chains of the first three files confirms their contiguous layout.

>> chain 0x7

0x0007 -> 0x0008 -> 0x0009 -> 0x000a -> 0x000b -> 
0x000c -> EOC
(6 clusters, check 6, Contiguous)

>> chain 0xd

0x000d -> 0x000e -> 0x000f -> 0x0010 -> 0x0011 -> 
0x0012 -> 0x0013 -> EOC
(7 clusters, check 7, Contiguous)

>> chain 0x14

0x0014 -> 0x0015 -> 0x0016 -> 0x0017 -> 0x0018 -> 
0x0019 -> 0x001a -> 0x001b -> 0x001c -> EOC
(9 clusters, check 9, Contiguous)

For convenience, I implemented the contig shell command which lists each file and reports if it is stored contiguously in the file system.

>> contig

LAYOUT STATUS OF FILES IN DIR: ROOT

       NAME          1ST      LENGTH    CONTIGUOUS?
 ---------------  --------  --------  -------------
      4.2.05.jpg  0x000083       42     CONTIGUOUS
      4.2.01.jpg  0x00005d       38     CONTIGUOUS
      4.1.06.jpg  0x00004b       18     CONTIGUOUS
      4.1.01.jpg  0x00003f       12     CONTIGUOUS
      4.1.05.jpg  0x000033       12     CONTIGUOUS
      4.1.04.jpg  0x000028       11     CONTIGUOUS
      4.1.02.jpg  0x00001d       11     CONTIGUOUS
      4.1.08.jpg  0x000014        9     CONTIGUOUS
      4.1.07.jpg  0x00000d        7     CONTIGUOUS
      4.1.03.jpg  0x000007        6     CONTIGUOUS
      ._.Trashes  0x000003        2     CONTIGUOUS

The contig command confirms that all of the copied files are indeed stored contiguously. This evidence supports the second assumption - contiguous storage - but what about the first assumption that file data doesn't get erased after deletion?

I've also enhanced fatrecover with the ability to checksum a series of clusters using the FNV hash algorithm. Hashing the clusters for the first three files yields:

>> checksum 0x7 6

0007-000A: 621102b1 5f618b21 d2855912 f5e1af11 
000B-000C: 5587dd40 8988110b 

>> checksum 0xd 7

000D-0010: e736c48d 2554ee35 e613f172 fe82cc2f 
0011-0013: de7bf92b 515eea02 acefd6c3 

>> checksum 0x14 9

0014-0017: 73e7cfea cdc2d024 5625892b 560cd9b1 
0018-001B: e5257e13 49fddb98 44610606 6011d7c7 
001C-001C: eadda707

To validate these checksums, I also implemented a standalone FNV hash utility to checksum the original image files in 2KB chunks (last chunk padded with 0s).

$ ./fnvtest 4.1.03.jpg

0000-0003: 621102b1 5f618b21 d2855912 f5e1af11 
0004-0007: 5587dd40 8988110b 

$ ./fnvtest 4.1.07.jpg 

0000-0003: e736c48d 2554ee35 e613f172 fe82cc2f 
0004-0007: de7bf92b 515eea02 acefd6c3 

$ ./fnvtest 4.1.08.jpg 

0000-0003: 73e7cfea cdc2d024 5625892b 560cd9b1 
0004-0007: e5257e13 49fddb98 44610606 6011d7c7 
0008-000B: eadda707

They match! This indicates that we have indeed located the data for these files in the disk image.

Now let's mount the disk image and delete the JPEG files.

$ hdiutil attach frtest2.dmg 
/dev/disk1                      /Volumes/FRTEST2

$ rm /Volumes/FRTEST2/4*.jpg

$ ls -ao /Volumes/FRTEST2/
total 48
drwxrwxrwx  1 jcardent  16384 Jan 28 06:59 .
drwxrwxrwt@ 4 root        136 Jan 28 06:59 ..
drwxrwxrwx@ 1 jcardent   2048 Jan 28 06:59 .Trashes
-rwxrwxrwx  1 jcardent   4096 Jan 26 06:30 ._.Trashes
drwxrwxrwx  1 jcardent   2048 Jan 28 06:59 .fseventsd

$ hdiutil detach /Volumes/FRTEST2/
"disk1" unmounted.
"disk1" ejected.

Re-examining the image in fatrecover confirms that the files are no longer listed in the root directory and that their associated clusters have been marked as unused in the FAT table.

>> ls

LISTING DIR: ROOT
 ATTR     SIZE            NAME          1ST CLUSTER
------  --------  --------------------  -----------
.H..D.         0            .fseventsd  (0x000006)
.H..D.         0              .Trashes  (0x000002)
.H...A      4096            ._.Trashes  (0x000003)
...V.A         0              FRTEST2.  (00000000)

>> fat

FAT TABLE ( KEY: .=free  B=bad  -=used X=last R=reserved)

00000000-0000001F: RXX-XXX.........................
00000020-0000003F: ................................
00000040-0000005F: ................................
00000060-0000007F: ................................
00000080-0000009F: ................................
000000A0-000000BF: ................................
000000C0-000000DF: ................................

Checksumming the same clusters as before results in:

>> checksum 0x7 6

0007-000A: 621102b1 5f618b21 d2855912 f5e1af11 
000B-000C: 5587dd40 8988110b 

>> checksum 0xd 7

000D-0010: e736c48d 2554ee35 e613f172 fe82cc2f 
0011-0013: de7bf92b 515eea02 acefd6c3 

>> checksum 0x14 9

0014-0017: 73e7cfea cdc2d024 5625892b 560cd9b1 
0018-001B: e5257e13 49fddb98 44610606 6011d7c7 
001C-001C: eadda707

The same checksums! Although the files were deleted the data remains unchanged in the file system! This supports the first assumption that deleting files does not erase their associated data.

To recover the deleted files, all that is needed is to extract the data from the disk image and write it to a new file. I added the extract command to do just that:

>> extract 0x7 6 recover1.jpg
Extracting clusters:
0x07 0x08 0x09 0x0a 0x0b 0x0c 

>> extract 0xd 7 recover2.jpg
Extracting clusters:
0x0d 0x0e 0x0f 0x10 0x11 0x12 0x13 

>> extract 0x14 9 recover3.jpg
Extracting clusters:
0x14 0x15 0x16 0x17 0x18 0x19 0x1a 0x1b 0x1c

The recovered files are slightly larger than the originals but this is due to extracting the entire last cluster even though it was only partially used.

$ ls -ao images/4.1.0[378].jpg 
-rw-r--r--  1 jcardent  12278 Dec  4 21:16 images/4.1.03.jpg
-rw-r--r--  1 jcardent  13670 Dec  4 21:16 images/4.1.07.jpg
-rw-r--r--  1 jcardent  18166 Dec  4 21:16 images/4.1.08.jpg

$ ls -ao recover*.jpg
-rw-r--r--  1 jcardent  12288 Jan 28 10:50 recover1.jpg
-rw-r--r--  1 jcardent  14336 Jan 28 10:50 recover2.jpg
-rw-r--r--  1 jcardent  18432 Jan 28 10:50 recover3.jpg

Comparing the original and recovered files with ImageMagik's identify, and compare utilities results in:

$ identify images/4.1.0[378].jpg
images/4.1.03.jpg JPEG 256x256 256x256+0+0 8-bit DirectClass 12kb 
images/4.1.07.jpg[1] JPEG 256x256 256x256+0+0 8-bit DirectClass 13.3kb 
images/4.1.08.jpg[2] JPEG 256x256 256x256+0+0 8-bit DirectClass 17.7kb 

$ identify recover[123].jpg
recover1.jpg JPEG 256x256 256x256+0+0 8-bit DirectClass 12kb 
recover2.jpg[1] JPEG 256x256 256x256+0+0 8-bit DirectClass 14kb 
recover3.jpg[2] JPEG 256x256 256x256+0+0 8-bit DirectClass 18kb 

$ compare -metric RMSE images/4.1.03.jpg recover1.jpg null:
0 (0)

$ compare -metric RMSE images/4.1.07.jpg recover2.jpg null:
0 (0)

$ compare -metric RMSE images/4.1.08.jpg recover3.jpg null:
0 (0)

Success, the recovered files are identical to the originals! For further confirmation, I opened these files with Apple's Preview application and visually compared the recovered images to the originals - they were indeed identical.

It's important to note that this manual recovery process worked because we knew where the files originally were in the file system. In the real use-case, the location of the original files is unknown so a method is needed to discover the beginning and ending of deleted files. In the next post, I'll begin developing such a method.

Book Review: The Simplicity Cycle

2010-01-20T05:06:00.001-05:00

A couple of weeks ago I came across a link to the book The Simplicity Cycle by Dan Ward. It's available as a free download so I grabbed a copy and finally got the chance to read it.

The book begins with the argument that projects follow a curve in the two-dimensional space formed by the qualities "goodness" and "complexity". Initially, all projects start off at the origin with no complexity or goodness. As they progress, complexity and goodness increase together as the initial problems are understood and suitable solutions created.

The book's primary thesis is that eventually all projects reach an inflection point where further increases in complexity yield less goodness, not more. To improve goodness beyond this point, the focus must switch from increasing complexity to reducing it. These transitions from simple, to complex, and back to simple again form the "simplicity cycle" which, when successful, results in "an elegant, graceful, and streamlined solution" capable of representing "tremendous complexity" while being "at once profound and breathtakingly simple". Inspiring stuff.

Not surprisingly, the author asserts that increasing complexity after the inflection point results in an undesirable outcome. For software, this could mean an application with too many features, options, or ways to accomplish tasks. For decision making, this could mean having too much information to draw an effective conclusion.

Unfortunately, the non-linear relationship between complexity and goodness can go unrecognized - from page 26:

One pitfall that designers, engineers, and academicians may fall prey to is the belief that continuing to increase complexity … will continue to produce increases in goodness. It just isn't the case.

In some cases, this mistaken belief can be due to a fascination with complexity itself - here goodness doesn't mean utility to the consumer but rather intellectual gratification to the producer. Also quoting from page 26:

This is genesis-gone-wild, cancerous growth. It is the product of “over-learning” and smugness, where people fall in love with complexity.

In other cases, the complexity is mastered but without achieving the deep insight needed to reduce the subject to its fundamental problems and solutions - to my mind a kind of mechanistic expertise. Quoting from page 30:

It generally means we are over-thinking a problem or over- engineering a solution. Think of it as achieving “the complexity on the other side of understanding,”

…

Here we find the learned academician who everyone assumes is brilliant because nobody can understand a word he says. In fact, his academics may simply be complicated and have very limited goodness. All those extra squiggles are not very useful, no matter how complex.

The book admits the difficulty of knowing when the inflection point has been reached. Guessing too late results in over complicatedness as has been discussed. However, guessing too soon results in premature optimization - an equally bad outcome as it fails to reach optimal goodness. Unfortunately, the author asserts that a method for reliably identifying the inflection point doesn't exist.

The book makes the important point that the complexity phase cannot simply be skipped. Quoting from on page 46:

However, the simplicity in this region is built upon an essential foundation of earlier complexity. We can’t just jump from simplistic to simple, skipping the complex entirely. The initial increase in complexity is as crucial to maximizing goodness as the later decrease in complexity.

The book concludes with examples of good and bath paths through the complexity vs. goodness space. I found these helpful for reflecting on how the simplicity cycle relates to past experiences.

This book was a pleasant surprise. Although short and free, I found it thought provoking and insightful. In particular, the "simplicity cycle" concept matches well with my experiences. When developing software, I often find that after writing a fair amount of code common patterns emerge that allow for a simpler design. Conversely, I've witnessed first hand the disastrous outcome of projects that fail to simplify after the inflection point. Although these experiences have given me a healthy fear of complexity, this book provided a context for that fear and a framework for managing it.

My only criticism of the simplicity cycle concept is that it may encourage the kind of over generalization that Joel Spolsky warns against in his essay "Don't Let Architecture Astronauts Scare You". Quoting from Joel's essay:

When you go too far up, abstraction-wise, you run out of oxygen. Sometimes smart thinkers just don't know when to stop, and they create these absurd, all-encompassing, high-level pictures of the universe that are all good and fine, but don't actually mean anything at all.

These are the people I call Architecture Astronauts. It's very hard to get them to write code or design programs, because they won't stop thinking about Architecture. They're astronauts because they are above the oxygen level, I don't know how they're breathing.

The point I take away from this is that simplification is not the same thing as abstraction - simplification remains focused and actionable while abstraction becomes vague and unactionable. Unfortunately, I think many mistake generalization for simplification but now that I'm consciously aware of the difference I'll be less likely to fall into the trap myself.

New Year, New Role

2010-01-16T08:00:00.000-05:00

With the New Year I took on a new position at work - same kind of role leading an advanced development team but with a much expanded sphere of responsibility. While exciting, this change plus some personal matters has left less time for blogging.

I expect to recover my blogging time this week and plan to finish up the FAT Recover series by the end of the month.

The bright side to this interruption is that it helped me realize how much I enjoy blogging. According to Google Analytics, this blog isn't setting the web on fire but regardless the personal benefits have more than justified the effort.

I have a lot of plans for this blog in 2010 and I intend to set aside the time required to remain active. That said, family and work take higher priority so such interruptions are probably inevitable - who knows what the year will bring.

Book Review: Organizing Genius

2010-01-06T06:15:00.000-05:00

Organizing Genius: The Secrets of Creative Collaboration by Warren Bennis & Patricia Ward Biederman

I first read this book a few of years ago and recently reviewed it in preparation for a new role at work. As before, I found it to be an extremely insightful resource on the attributes of great, innovative teams.

The majority of the book provides accounts of the following "great" groups:

The Walt Disney Studio
Xerox PARC
The Apple Macintosh Team
The 1992 Clinton Campaign Team
Lockheed's Skunk Works Group
Black Mountain College
The Manhattan Project

As stated in the introduction, the authors attempt to systematically examine these groups in the hope of identifying their "collective magic". In the final chapter they summarize their findings into the following 15 points.

Greatness starts with superb people.
Great Groups and great leaders create each other.
Every Great Group has a strong leader.
The leaders of Great Groups love talent and know where to find it.
Great Groups are full of talented people who can work together.
Great Groups think they are on a mission from God.
Every Great Group is an island - but an island with a bridge to the mainland.
Great Groups see themselves as underdogs.
Great Groups always have an enemy.
People in Great Groups have blinders on.
Great Groups are optimistic, not realistic.
In Great Groups the right person has the right job.
The Leaders of Great Groups give them what they need and free them from the rest.
Great Groups ship.
Great work is its own reward.

Generally speaking I agree with all of these points. The closest I've come to working in a Great Group was my first job building a big-iron ccNUMA machine. That group and experience had many of the elements listed above and a decade later I recognize how rare of an opportunity that was. I suspect others from the team feel the same way based on the reminiscing we do whenever any of us cross paths.

Clearly the leaders of Great Groups are responsible for creating an appropriate environment for the team to flourish. In my role as the leader of an advanced development engineering team I've tried my best to follow this guidance with I think moderate success. As my role and responsibility expands I need to place greater focus on creating the right environment - to that end this book will be a valuable resource.

Recovering Deleted JPEGs from a FAT File System - Part 6

2009-12-31T14:39:00.000-05:00

Part 6 in a series of posts on recovering deleted JPEG files from a FAT file system.

In this post we'll tackle the last major FAT file system data structure - the file allocation table. Compared to the previous post on the root directory, this post is much less complex. Follow the "read more" link for an overview of the file allocation table and the code required to process it.

As mentioned in previous posts, a FAT16 file allocation table consists of one 16 bit entry for each cluster in the data area. The value stored in each entry indicates the associated cluster's allocation state and, if needed, the next cluster containing data for the same file system object.

Although table entries exist for clusters 0 and 1, they are reserved for the system's use. The first byte of entry 0 is used to store a copy of the mediaType field from the common boot sector - the entry's remaining bits are set to 1. Entry 1 is sometimes used to record if the volume was unmounted cleanly. Because of these reservations, the data area cluster information beings with entry 2.

Initially, table entries 2 and higher are initialized to a value of 0x0000 indicating that the associated clusters are available for use. Bad clusters are signified by the value 0xFFF7 while reserved clusters have a value between 0xFFF0 and 0xFFF6 (inclusive).

Table entries for allocated clusters contain either:

The number of the next cluster containing additional data for the associated file system object (file or directory).
A value between 0xFFF8 and 0xFFFF (inclusive) indicating that this is the last cluster containing data for the associated file system object. Collectively, these values are known as end-of-chain (EOC) values.

Essentially, allocated table entries form a singly linked-list specifying the location and order of the clusters containing a file system object's data. To illustrate this, consider the following diagram:

          ROOT                        FAT
          DIR                        TABLE
  +--------+------+            +-------+-------+
  | FNMAME | 1ST C|            | ENTRY | VALUE |
  +========+======+            +=======+=======+
  | FILEA  | 0x02 +-------+    | 0X00  | RESVD |
  |        |      |       |    |       |       |
  +--------+------+       |    +-------+-------+
  | FILEB  | 0x03 +-----+ |    | 0X01  | RESVD |
  |        |      |     | |    |       |       |
  +--------+------+     | |    +-------+-------+
  |        |      |     | +--->| 0X02  | EOC   |
  |        |      |     |      |       |       |
                        |      +-------+-------+
                        +----->| 0X03  | 0X04  |
                               |       |       +----+
                               +-------+-------+    |
                               | 0X04  | 0X06  |<---+
                               |       |       +----+
                               +-------+-------+    |
                               | 0X05  | 0X00  |    |
                               |       |       |    |
                               +-------+-------+    |
                               | 0X06  | EOC   |<---+
                               |       |       |
                               +-------+-------+
                               |       |       |
                               |       |       |

The diagram depicts two examples, FILEA and FILEB, and their associated entries in the root directory and file allocation table.

FILEA's root directory entry states that cluster 0x02 contains the first portion of its data. To reflect this allocation, file allocation table entry 0x02 has a non-zero value. Furthermore, entry 0x02 contains an EOC value indicating that no other clusters contain data for FILEA - all of FILEA's data fits within the single cluster.

FILEB is a longer file requiring three clusters to store its data. Its root directory entry identifies cluster 0x03 as the first and, appropriately, file allocation table entry 0x03 contains a non-zero value. In this case, entry 0x03 contains the value 0x04 indicating that FILEB's second cluster of data resides in cluster 0x04. File allocation table entry 0x04 in turn contains the value of 0x06 identifying cluster 0x06 as the third holding FILEB's data. Finally, file allocation table 0x06 contains an EOC value indicating that it is the last cluster containing FILEB's data. Note that cluster 0x05, although between clusters holding FILEB's data, remains unallocated and is available for use.

The example illustrates how the file allocation table is used to both track cluster allocations and construct linked-lists describing the location of file system object data. In FAT parlance, these linked lists are called cluster chains.

The file allocation table forms the heart of the file system - a fact reflected by the file system's name, FAT. Before discussing the code required to process the on-disk table, it's worth noting a couple of things:

The smallest allocation unit is a cluster - 2KB in our test image's case. File system objects smaller than a cluster consume the whole thing. As a result, a large number of small files will result in severe internal fragmentation.
The file allocation table only contains forward pointers. There are are no back pointers to prior clusters or the directory entry for the file system object the chain belongs to.
The file allocation table alone describes the location of file system object data - erasing the table essentially erases the file system although the data remains unchanged.

Recall from the first post that the third point was the basis for the original project in 2004. File systems that erase files by only clearing their directory and file allocation table entries leave the data in place thus making it theoretically possible to recover them.

Compared to the root directory, processing the file allocation table is trivial. The following code fragment provides all of the required constants, macros, and type definitions:

#define FAT_FAT16ENT_FREESECTOR       (0x0000U)
#define FAT_FAT16ENT_RESERVED_START   (0xfff0U)
#define FAT_FAT16ENT_RESERVED_END     (0xfff6U)
#define FAT_FAT16ENT_BADSECTOR        (0xfff7U)
#define FAT_FAT16ENT_LASTSECTOR_START (0xfff8U)
#define FAT_FAT16ENT_LASTSECTOR_END   (0xffffU)

#define FAT_FAT16ENT_ISFREESECTOR(x) \
  ((x) == FAT_FAT16ENT_FREESECTOR)
#define FAT_FAT16ENT_ISBADSECTOR(x) \
  ((x) == FAT_FAT16ENT_BADSECTOR)
#define FAT_FAT16ENT_ISLASTSECTOR(x) \
  ((x) >= FAT_FAT16ENT_LASTSECTOR_START)
#define FAT_FAT16ENT_ISRESERVEDSECTOR(x)\
  (((x) >= FAT_FAT16ENT_RESERVED_START) && \
   ((x) <= FAT_FAT16ENT_RESERVED_END))

typedef uint16_t fatFAT16Entry_t;

Reading a cluster entry requires calculating the associated sector number and offset, loading the sector into memory, and extracting the correct two bytes.

fatTableOffset = clusterNum * sizeof(fatFAT16Entry_t); 
sectorNum      = (fatTableOffset / bytesPerSector)
                 + pimageInfo->fatFirstSector;
sectorOffset   = fatTableOffset % bytesPerSector;

frSectorRead(pimageInfo, sectorNum,
             1, pSectorBuff);

memcpy(pfatEntry, (pSectorBuff + sectorOffset),
       sizeof(fatFAT16Entry_t));

Alternatively, a portion of the table loaded into a memory buffer can be iterated over as an array.

 fatFAT16Entry_t *fatTable;
 fatFAT16Entry_t  entry;

  fatTable = (fatFAT16Entry_t *) pfatTableBuffer;
  for(entryIndex=0; entryIndex < numEntries; entryIndex++ ) {

    entry = fatTable[entryIndex];
    ....
  }

Using the code fragments above, I enhanced the program I am (re)developing alongside these posts to process and printout the file allocation table. Running it against the test disk image, frtest1.dmg, created in the second post and used to produce the examples in the prior two posts yielded:

$ sw_vers
ProductName:    Mac OS X
ProductVersion: 10.6.2
BuildVersion:   10C540

$ wc -l fatrecover.c 
     829 fatrecover.c

$ make clean all
rm -r fatrecover fatrecover.dSYM 
gcc -g -Wall fatrecover.c -o fatrecover

$ ./fatrecover frtest1.dmg 

=== FAT RECOVER v0.0 ===

Opening file frtest1.dmg................OK
Reading boot sector.....................OK
Processing boot sector..................OK
Reading root dir........................OK

BOOT SECTOR:
          OEMName: (BSD  4.4)
         volumeID: 63260cf5
     Volume Label: FRTEST1    
           FSType: FAT16   
     Bytes/Sector: 512
  Sectors/Cluster: 4
 Reserved Sectors: 1
   Hidden Sectors: 0
 Sectors/Vol (2B): 32768
 Sectors/Vol (4B): 0
      Sectors/FAT: 32
        # of FATs: 2
# RootDir Entries: 512

MAJOR STRUCTURES:
      AREA    OFFSET      SIZE
----------  --------  --------
 BOOT+RESV  00000000  0x000001 (sectors)
       FAT  0x000001  0x000040 (sectors)
   ROOTDIR  0x000041  0x000020 (sectors)
      DATA  0x000061  0x001fe7 (clusters)

LISTING DIR: ROOT
 ATTR     SIZE            NAME          1ST CLUSTER
------  --------  --------------------  -----------
.....A     92889            4.2.04.jpg  (0x00000a)
.H..D.         0              .Trashes  (0x000002)
.H...A      4096            ._.Trashes  (0x000003)
...V.A         0              FRTEST1.  (00000000)

FAT TABLE ( KEY: .=free  B=bad  -=used X=last R=reserved)

00000000-0000001F: RXX-X.....----------------------
00000020-0000003F: -----------------------X........
00000040-0000005F: ................................
00000060-0000007F: ................................
<OUTPUT FOR EMPTY ENTRIES OMITTED>

CLUSTER CHAIN FOR ENTRY 0xa:
0x000a->0x000b->0x000c->0x000d->0x000e->0x000f->0x0010->
0x0011->0x0012->0x0013->0x0014->0x0015->0x0016->0x0017->
0x0018->0x0019->0x001a->0x001b->0x001c->0x001d->0x001e->
0x001f->0x0020->0x0021->0x0022->0x0023->0x0024->0x0025->
0x0026->0x0027->0x0028->0x0029->0x002a->0x002b->0x002c->
0x002d->0x002e->0x002f->0x0030->0x0031->0x0032->0x0033->
0x0034->0x0035->0x0036->0x0037->EOC (46 clusters)

As discussed previously, file allocation table entries 0 and 1 are reserved by the system. The program output indeed shows that entry 0 contains a RESERVED value but entry 1 instead contains an EOC value. A little research¹ uncovered that EOC values are used to both prevent entry 1 from being used and to encode the volume's last unmount state - the output thus makes sense.

Table entry 2 is also allocated and the root directory listing tells us that it belongs to the .Trashes subdirectory. Furthermore, the EOC value indicates that the directory's contents fit within the single sector.

Entry 4 is allocated to the ._.Trashes file which requires two clusters to store its 4096 bytes of data. Presumably, entry 5 also belongs to this file and is the last in its cluster chain.

Finally, entries 0x0a to 0x37 are all allocated to the test JPG file 4.2.04.jpg. This is suggested by the root directory listing and allocation table summary and confirmed by the additional output showing the cluster chain starting at entry 0x0a. The cluster chain's length, 46, provides a sanity check as it is the smallest number of clusters required to store the file's 92889 bytes of data (46 * 2KB -> 94208B).

With that we now have all the code required to examine a FAT file system disk image. With a little work, the code fragments provided in this and prior posts can be used to create a program capable of inspecting file system images of varying size and complexity.

In the next post, we'll regroup by using the functionality developed thus far to inspect various file system images to determine the best approach for recovering deleted JPG files.

Footnotes:

¹ http://en.wikipedia.org/wiki/File_Allocation_Table#File_Allocation_Table

Book Review: The Planiverse

2009-12-29T06:45:00.001-05:00

The Planiverse: Computer Contact with a Two Dimensional World by A.K. Dewdney

Written in 1984, this is a fictional story of a computer science professor and his students making contact with a two-dimensional universe - The Planiverse - through a simulation program developed as a class project. More specifically, a telepathic connection is established with one of the universe's inhabitants called YNDRD otherwise known as "Yendred". The professor and students accompany Yendred on a journey and in the process discover the workings of the two-dimensional world.

Essentially, the book can be decomposed into two concurrent streams:

The story of Yendred's journey across his world in search of a mystic - Drabk - said to possess "knowledge of the beyond".
A series of expositions on the scientific, technological, and social aspects of Yendred's two-dimensional universe.

Basically, Yendred's journey provides the context and segues for the expositions. This structure reflects the book's derivation from two prior publications - the monograph Two-Dimensional Science and Technology and book Symposium on Two-Dimensional Science and Technology. Material from these prior works formed the basis for the expositions around which the fictional Yendred plot was wrapped to create a coherent, entertaining, and intellectually stimulating story.

Although I thought the Yendred story was only "OK", I really enjoyed the expositions - clearly a lot of thought was given to how a two dimensional world would work. For example, some of the scientific exposition topics were:

Thermodynamics and the extremely low melting point that two-dimensions lead to.
The mechanics of two-dimensional turbulence.
Electromagnetism and the lack of magnetic forces.
The "Global" weather patterns of a two-dimensional "planet"
Energy diminishing according to the inverse of distance (instead of the inverse-square as in three dimensions).
The biological structure of two-dimensional organisms.
Two-dimensional chemistry and the limited number of possible elements.

The technical expositions discussed the design of two-dimensional objects such as:

Buildings that avoided obstructing surface travel.
Doors that allowed privacy and structural integrity while remaining passable.
Functional steam engines, foundries, space rockets, and fishing boats.
Balloons for travel and the shipment of freight.
Gears capable of varying torque in the absence of axles.
Subterranean elevators.
Electronic circuits suitable for constructing rudimentary computers.
A wind powered generator for recharging batteries - the only viable source of electricity as wires create impassable obstacles.

The social expositions discussed topics such as:

How the world's inhabitants "passed" each other while traveling (they walk over each other according to social conventions).
How traveler's deal with surface events like a sports game (they wait until it's done).
Two dimensional warfare and its influence on politics.

In summary, if you enjoy thinking differently about science, and technology then I think you'll enjoy reading this book. The ability to think about problems from different perspectives is an important and powerful skill - I think reading books like The Planiverse is one way to help develop that skill.

Recovering Deleted JPEGs from a FAT File System - Part 5

2009-12-24T18:33:00.012-05:00

Part 5 in a series of posts on recovering deleted JPEG files from a FAT file system.

UPDATE: 2010/1/28: it's come to my attention that the long file name support code described in this post is broken - it only works for files that utilize a single LFN entry. For the time being I plan to work around this bug for the FATRecover series but I do intend to post a fix eventually. I'll be sure to add another update with a link to the fix when it is available.

The topic of this installment is the root directory and the code required to process it. Although strictly speaking the file allocation table is the next major on-disk area, I think covering the root directory first will make the overall discussion clearer.

Note that this is a watershed post as the "hack" level of the example code increases dramatically. This was unfortunate but necessary to accommodate certain FAT functionality while limiting the discussion's length. That said, readers with sufficient skill should be able to use the example code to create more robust implementations.

Follow the "read more" link for a detailed description of how to read and interpret the root directory.

As discussed in parts 3 and 4, the root directory area is located on-disk immediately after the FAT area and consumes a fixed amount of pre-allocated space. The root directory area is essentially an array of 32 byte entries with the following structure:

#define FAT_DIRENTS_FNSZ (8)
#define FAT_DIRENTS_EXTSZ (3)

typedef struct fatDirectoryEntrySFN_s {     
  uint8_t   filename[FAT_DIRENTS_FNSZ];   // 07-00
  uint8_t   extension[FAT_DIRENTS_EXTSZ]; // 10-08
  uint8_t   attributes;                   // 11-11
  uint8_t   reserved1;                    // 12-12
  uint8_t   createTimeDsec;               // 13-13
  uint16_t  createTimeHMS;                // 15-14
  uint16_t  createTimeDay;                // 17-16
  uint16_t  accessedDay;                  // 19-18
  uint16_t  firstClusterHigh;             // 21-20
  uint16_t  writeTimeHMS;                 // 23-22
  uint16_t  writeDay;                     // 25-24
  uint16_t  firstCluster;                 // 26-27
  uint32_t  fileSize;                     // 31-28
} __attribute__ ((packed)) fatDirectoryEntrySFN_t;

The the first byte of the filename field specifies an entry's allocation status. Initially, all directory table entries are in the UNUSED state (0x00). Entries that are allocated and then later deallocated (due to file system deletions) are moved to the DELETED state (0xE5). The first byte of valid directory entries contains the first file name character which must have a value other than 0x00 or 0xE5 (if necessary the value 0x05 is used to encode the character value 0xE5).

File systems are expected to allocate directory entries sequentially starting with the first. As a result, partially allocated directory tables should consist of an inter-mixture of allocated and DELETED entries followed by one or more UNUSED entries. Directory tables that have been fully utilized will consist of only allocated and DELETED entries. When allocating entries, file systems can either re-use DELETED entries or allocate the next UNUSED entry (if one exists) - the preference is implementation specific.

The following code fragment provides #defines and a macro that can be used to determine a directory entry's allocation status.

#define FAT_DIRENTS_FNUNUSED  (0x00)
#define FAT_DIRENTS_FNDELETED (0xE5)

#define FAT_DIRENTS_FNVALID(pfatDE) \
  ((FAT_DIRENTS_FNUNUSED  != (pfatDE)->filename[0]) &&  \
   (FAT_DIRENTS_FNDELETED != (pfatDE)->filename[0]))

Valid directory entries contain the associated file system object's name in 8.3 format. The filename field contains the base file name while the extension field may contain an optional 3 character extension. As with the boot sector's text fields, the filename and extension fields are padded with spaces and lack null termination.

The attributes field contains flags describing the entry's type and characteristics. The following code fragment defines the various flags and provides macros for testing them.

#define FAT_DIRATT_READONLY     (0x01)
#define FAT_DIRATT_HIDDEN       (0x02)
#define FAT_DIRATT_SYSTEM       (0x04)
#define FAT_DIRATT_VOLUMELABEL  (0x08)
#define FAT_DIRATT_LFN          (0x0f)
#define FAT_DIRATT_DIRECTORY    (0x10)
#define FAT_DIRATT_ARCHIVE      (0x20)
#define FAT_DIRATT_MASK         (0x3f);

#define FAT_DIRATT_ISREADONLY(x) \
  (((x) & FAT_DIRATT_READONLY) == FAT_DIRATT_READONLY)
#define FAT_DIRATT_ISHIDDEN(x) \
  (((x) & FAT_DIRATT_HIDDEN) == FAT_DIRATT_HIDDEN)
#define FAT_DIRATT_ISSYSTEM(x) \
  (((x) & FAT_DIRATT_SYSTEM) == FAT_DIRATT_SYSTEM)
#define FAT_DIRATT_ISVOLUMELABEL(x) \
  (((x) & FAT_DIRATT_VOLUMELABEL) == FAT_DIRATT_VOLUMELABEL)
#define FAT_DIRATT_ISLFN(x) \
  (((x) & FAT_DIRATT_LFN) == FAT_DIRATT_LFN)
#define FAT_DIRATT_ISDIRECTORY(x) \
  (((x) & FAT_DIRATT_DIRECTORY) == FAT_DIRATT_DIRECTORY)
#define FAT_DIRATT_ISARCHIVE(x) \
  (((x) & FAT_DIRATT_ARCHIVE) == FAT_DIRATT_ARCHIVE)

Most of the attributes should be self-explanatory. Later in the post we'll discuss the LFN attribute and its dire implications.

For this project, the only other fields of interest are firstCluster and fileSize. The firstCluster field specifies the data area cluster containing the associated file system object's first chunk of data - the next post on the file allocation table will discuss this in greater depth. The fileSize field indicates a file's size in bytes - non-file entries should have a value of 0 in this field.

For the program I am re-developing alongside these posts, I took the following approach to processing the root directory:

malloc a temporary buffer the same size as the root directory area.
Read the on-disk root directory area into the buffer.
Iterate over the directory table entries in the buffer and create an abstracted data structure for each valid entry.
free the temporary buffer

Below is a high-level code fragment that implements the above steps:

  pRootDirBuff = malloc(rootdirSizeBytes);
  memset(pRootDirBuff, 0, rootdirSizeBytes);
  
  frSectorRead(pimageInfo, 
               pimageInfo->rootdirFirstSector,
               pimageInfo->rootdirSizeSectors,   
               pRootDirBuff);

  frDirProcessEntries(&(pimageInfo->rootDir), 
                      pRootDirBuff,
                      rootdirSizeBytes);

  free(pRootDirBuff);

pimageInfo is a housekeeping data structure my program uses to pass around context information like the disk image's open file descriptor, copies of the boot sector structures, and the information calculated in part 4. frSectorRead() is a utility routine that reads the specified sector extent from the disk image file into the memory buffer provided. All of the real action occurs in frDirProcessEntries().

My first implementation of frDirProcessEntries() looked something like the following:

int frDirProcessEntries(frDirEntry_t *pParentDir, 
                        char *pdirBuff, 
                        size_t sizeBuff)
{
fatDirectoryEntrySFN_t *fatDirectoryTable;
size_t numFatDirTableEntries;

fatDirectoryTable = (fatDirectoryEntrySFN_t *) pdirBuff;
numFatDirTableEntries = sizeBuff / 
                        sizeof(fatDirectoryEntrySFN_t);

for (entryIndex = 0;
     entryIndex < numFatDirTableEntries;
     entryIndex++) {

  if (!(FAT_DIRENTS_FNVALID(&(fatDirectoryTable[entryIndex])))) {
    continue;
  }
  entryCount++;

  pDirEntry = (frDirEntry_t * )malloc(sizeof(frDirEntry_t));
  memset(pDirEntry, 0, sizeof(frDirEntry_t));

  ptmp  = (char *) &(pDirEntry->filename);
  ptmp += 
      utilCopyNameChars((char *)fatDirectoryTable[entryIndex].filename,
                        ptmp,
                        (int) FAT_DIRENTS_FNSZ,
                        1);

  if (FAT_DIRENTS_FNVALID(&(fatDirectoryTable[entryIndex]))) {
     *ptmp = '.';
      ptmp++;
      ptmp += 
         utilCopyNameChars((char *)fatDirectoryTable[entryIndex].extension, 
                           ptmp,
                           (int) FAT_DIRENTS_EXTSZ,
                           1);
  }
  *ptmp = '\0';

  pDirEntry->attributes   = fatDirectoryTable[entryIndex].attributes;
  pDirEntry->fileSize     = fatDirectoryTable[entryIndex].fileSize;
  pDirEntry->firstCluster = fatDirectoryTable[entryIndex].firstCluster;

  pDirEntry->pParentDir    = pParentDir;
  pDirEntry->pNextSibling  = pParentDir->pDirEntries;
  pParentDir->pDirEntries  = pDirEntry;
  pDirEntry = NULL;
}

return entryCount;
}

Basically, the routine:

Calculates the number of directory entries in the buffer provided.
Casts it as an array of directory entries.
Iterates over the entries via a for loop.
Checks the first byte of each entry to see if it is valid.
Allocates an abstracted data for each valid entry.
Copies the file name and other metadata to the abstract structure.
Adds the abstract structure to the parent directory's linked list of contents.

Technically speaking the for loop should terminate when a FAT_DIRENTS_FNUNUSED entry is encountered but the code above just skips over such entries and continues processing the table - this shouldn't be a problem so I didn't bother to fix it (this is a hobby endeavor after all).

As mentioned, frDirEntry_t is an abstracted data structure used to represent directory entries. Its structure can be inferred from the code above. The motivation for using a secondary structure is to avoid re-processing the raw entries for each listing (the importance of this will become clear later).

utilCopyNameChars() is a utility routine that copies characters from the raw directory entry text fields to a C string.

int utilCopyNameChars(char *srcString, 
                      char *destString, 
                      int maxChars, int srcSkip)
{
  // Copy characters from srcString to destString until 
  // a space character, null character, 0xff value, or 
  // maxChars is reached.
  //
  // Returns the number of characters copied

  char *psrcChar  = srcString;
  char *pdestChar = destString;
  int   count = 0;

  while ((*psrcChar != ' ')  &&
         (*psrcChar != '\0')  &&
         (((unsigned char)*psrcChar) != 0xff)  &&
         (count < maxChars)) {

    *pdestChar = *psrcChar;
    psrcChar += srcSkip;
    pdestChar++;
    count++; 
  }

  return count;
}

The while loop terminates upon reaching either a space character, NULL character, or the value 0xff (which will be explained later). The skip argument supports a hack that is explained below.

After adding a short routine to print the abstracted directory entry structures (which I won't show), I got the following output from running the improved fatrecover program against the test image, frtest1.dmg, from the prior two posts.

LISTING DIR: ROOT
 ATTR     SIZE            NAME          1ST CLUSTER
------  --------  --------------------  -----------
.....A     92889            4204~1.JPG  (0x00000a)
RHSV..        -1                   A4.  (00000000)
.H..D.         0             FSEVEN~1.  (0x000008)
RHSV..        -1                   A..  (00000000)
.H..D.         0             TRASHE~1.  (0x000002)
RHSV..        -1                   A..  (00000000)
.H...A      4096               _~1.TRA  (0x000003)
RHSV..        -1                   A..  (00000000)
...V.A         0              FRTEST1.  (00000000)

YUCK! The funky file names, -1 sizes, and simultaneous setting of the RHSV flags indicated that I had run into the dreaded (by me) long file name support.

When I first did this project in 2004 I punted on handling long file names. I considered doing the same for this re-implementation but the idea didn't sit well with me - I have a hard time avoiding the same problem twice. Besides, without long file name support I would have had to modify the test disk image to clean up the output and update the prior posts as needed. This felt too much like hiding dirty laundry so I decided to suck it up and hack together long file name support - this isn't going to be pretty.

Long file names are supported by using multiple directory entries with the following structure:

#define FAT_DIRENTL_FN1SZ (10)
#define FAT_DIRENTL_FN2SZ (12)
#define FAT_DIRENTL_FN3SZ (4)

typedef struct fatDirectoryEntryLFN_s {     
  uint8_t   sequenceNum;                  // 00-00
  uint8_t   filename1[FAT_DIRENTL_FN1SZ]; // 10-01
  uint8_t   attributes;                   // 11-11
  uint8_t   reserved;                     // 12-12
  uint8_t   checksum;                     // 13-13
  uint8_t   filename2[FAT_DIRENTL_FN2SZ]; // 25-14
  uint8_t   reserved2[2];                 // 27-26
  uint8_t   filename3[FAT_DIRENTL_FN3SZ]; // 31-28
}  __attribute__ ((packed)) fatDirectoryEntryLFN_t;

These long file name (LFN) structures are identified by the RHSV flags being simultaneously set and precede their associated 8.3 entry (SFN) in the directory table. The 8.3 directory entry includes a shortened version of the long file name and the object's associated metadata (i.e. size, starting cluster, etc).

Each LFN entry includes a sequence number indicating its order. The entries are stored in highest to lowest order in the directory table making it easier to determine their total number. The last LFN entry has a a sequence number of 1 bitwise OR'd with the value 0x40. Below is a macro that can be used to check for the 0x40 marker:

#define FAT_DIRENTL_LASTSEQ (0x40)
#define FAT_DIRENTL_ISLASTSEQ(x) \
  (((x) & FAT_DIRENTL_LASTSEQ) == FAT_DIRENTL_LASTSEQ)

The following is a simple example of an LFN and SFN directory table sequence:

| ENTRY# | TYPE | SEQ# |
|--------+------+------|
|      1 | LFN  | 0x04 |
|      2 | LFN  | 0x03 |
|      3 | LFN  | 0x02 |
|      4 | LFN  | 0x41 |
|      5 | SFN  |   -- |

Each LFN entry has three fields for storing file name characters. Some or all of an LFN entry's text fields may contain file name characters. Those that do will have a non-null value in the first byte. Below are macros that can be used to test each field for valid contents:

#define FAT_DIRENTL_FNUNUSED  (0x00)

#define FAT_DIRENTL_FN1VALID(pfatDEL) \
  (FAT_DIRENTL_FNUNUSED  != (pfatDEL)->filename1[0])
#define FAT_DIRENTL_FN2VALID(pfatDEL) \
  (FAT_DIRENTL_FNUNUSED  != (pfatDEL)->filename2[0])
#define FAT_DIRENTL_FN3VALID(pfatDEL) \
  (FAT_DIRENTL_FNUNUSED  != (pfatDEL)->filename3[0])

As with other FAT structures, these fields lack null termination so they must be handled similarly to other on-disk text fields.

Unfortunately, unlike the other on-disk structures, the LFN entry text fields use a UTF-16 UNICODE encoding. I prefer my tangents one at a time and since I don't have much experience in dealing with UTF-16 in C I decided to hack a shortcut (I warned you). Since I know my test images will only use UTF-8 characters I decided to only copy the low-order byte of the UTF-16 characters. I accomplished this by calling utilCopyNameChars() with a skip argument value of 2 and a maxChars argument value of the field length divided by 2. Not my proudest coding moment but it worked.

To handle LFN entries, I modified my original directory table processing for loop to include a sub while loop to iterate over the LFN entries. The code fragment below shows the modified loop along with comments documenting the (many) assumptions made (the remainder of frDirProcessEntries() remained the same):

fatDirectoryTable = (fatDirectoryEntrySFN_t *) pdirBuff;
numFatDirTableEntries = sizeBuff / 
                        sizeof(fatDirectoryEntrySFN_t);

for (entryIndex = 0;
     entryIndex < numFatDirTableEntries;
     entryIndex++) {

  if (!(FAT_DIRENTS_FNVALID(&(fatDirectoryTable[entryIndex])))) {
    continue;
  }
  entryCount++;

  pDirEntry = (frDirEntry_t * )malloc(sizeof(frDirEntry_t));
  memset(pDirEntry, 0, sizeof(frDirEntry_t));

  ptmp  = (char *) &(pDirEntry->filename);

  if (FAT_DIRATT_ISLFN(fatDirectoryTable[entryIndex].attributes)) {
    // N.B. - Hack alert. Rudimentary support for long file names.
    //        Assumes that LFN entries are valid (no checksum checking).
    //        Assumes that last LFN marked with end of sequence flag
    //        Assumes that file names are in UTF-16.
    //        Assumes that all LFN entries exist and are in proper order.
    //        Assumes that LFN and SFN entries are contiguous.
    //        Assumes that file name is less than 256 characters long.
    //
    //        Iterates over LFN entries, copies filename to pDirEntry.
    //        Leaves entryIndex at the associated SFN.

    fatDirectoryEntryLFN_t *pfatDirEntLFN = NULL;
    do {
      pfatDirEntLFN = 
        (fatDirectoryEntryLFN_t *)&(fatDirectoryTable[entryIndex]);

      assert(FAT_DIRATT_ISLFN(fatDirectoryTable[entryIndex].attributes));
      assert(entryIndex < numFatDirTableEntries);

      if (FAT_DIRENTL_FN1VALID(pfatDirEntLFN)) {      
        ptmp += 
               utilCopyNameChars((char *)pfatDirEntLFN->filename1,
                            ptmp,
                            (int) FAT_DIRENTL_FN1SZ/2,
                            2);
      }

      if (FAT_DIRENTL_FN2VALID(pfatDirEntLFN)) {      
        ptmp += 
              utilCopyNameChars((char *)pfatDirEntLFN->filename2,
                            ptmp,
                            (int) FAT_DIRENTL_FN2SZ/2,
                            2);
      }

      if (FAT_DIRENTL_FN3VALID(pfatDirEntLFN)) {      
        ptmp += 
              utilCopyNameChars((char *)pfatDirEntLFN->filename3,
                            ptmp,
                            (int) FAT_DIRENTL_FN3SZ/2,
                            2);
      }

      entryIndex++;

    } while (!(FAT_DIRENTL_ISLASTSEQ(pfatDirEntLFN->sequenceNum)));
  } else {

    // copy file name and extension   
    ptmp += 
       utilCopyNameChars((char *)fatDirectoryTable[entryIndex].filename,
                  ptmp,
                  (int) FAT_DIRENTS_FNSZ,
                  1);

    if (FAT_DIRENTS_FNVALID(&(fatDirectoryTable[entryIndex]))) {
      *ptmp = '.';
      ptmp++;
      ptmp += 
        utilCopyNameChars((char *)fatDirectoryTable[entryIndex].extension,
                          ptmp,
                          (int) FAT_DIRENTS_EXTSZ,
                          1);
    }
  }
  *ptmp = '\0';

  pDirEntry->attributes   = fatDirectoryTable[entryIndex].attributes;
  pDirEntry->fileSize     = fatDirectoryTable[entryIndex].fileSize;
  pDirEntry->firstCluster = fatDirectoryTable[entryIndex].firstCluster;

  pDirEntry->pParentDir    = pParentDir;
  pDirEntry->pNextSibling  = pParentDir->pDirEntries;
  pParentDir->pDirEntries  = pDirEntry;
  pDirEntry = NULL;
}

With this LFN hack in place, re-running the program against the test image produced:

$ sw_vers
ProductName:    Mac OS X
ProductVersion: 10.6.2
BuildVersion:   10C540

$ wc -l fatrecover.c 
     632 fatrecover.c

$ make clean all
rm -r fatrecover fatrecover.dSYM 
gcc -g -Wall fatrecover.c -o fatrecover

$ fatrecover frtest1.dmg 

=== FAT RECOVER v0.0 ===

Opening file frtest1.dmg................OK
Reading boot sector.....................OK
Processing boot sector..................OK
Reading root dir........................OK

<BOOT SECTOR INFO REMOVED FOR BREVITY>

LISTING DIR: ROOT
 ATTR     SIZE            NAME          1ST CLUSTER
------  --------  --------------------  -----------
.....A     92889            4.2.04.jpg  (0x00000a)
.H..D.         0            .fseventsd  (0x000008)
.H..D.         0              .Trashes  (0x000002)
.H...A      4096            ._.Trashes  (0x000003)
...V.A         0              FRTEST1.  (00000000)

Ah, much better. The first entry is the JPG image file which is 92889 bytes long and begins in cluster 0xa. The .fseventsd and .Trashes entries are artifacts from mounting the disk image on an OSX system - they can be ignored. The last entry (which actually appears first in the on-disk table) is a volume label as indicated by the V attribute flag.

As a sanity check, mounting the disk image and listing the root directory from OSX produces:

$ hdiutil attach frtest1.dmg 
/dev/disk1                      /Volumes/FRTEST1

$ls -ao /Volumes/FRTEST1/
total 232
drwxrwxrwx  1 jcardent  16384 Dec 24 10:52 .
drwxrwxrwt@ 4 root        136 Dec 24 10:52 ..
drwxrwxrwx@ 1 jcardent   2048 Dec 24 10:52 .Trashes
-rwxrwxrwx  1 jcardent   4096 Dec 14 05:28 ._.Trashes
drwxrwxrwx  1 jcardent   2048 Dec 24 10:52 .fseventsd
-rwxrwxrwx  1 jcardent  92889 Dec 14 05:28 4.2.04.jpg

Other than being in opposite orders the two listings match. Woot!

Before declaring total victory, there is one major shortcoming with the LFN hack shown above - it requires an entire directory table to be read into an in-memory buffer. My original intent was to process directory tables one sector or cluster at a time to minimize the memory footprint. However, the hack above can't handle LFN entries spanning a sector or cluster boundary as this would involve separate calls to frDirProcessEntries(). I thought of a couple of ways to achieve both goals but decided that they would unnecessarily complicate the discussion as we'll only be dealing with small disk images in this series. If you plan to use this code to handle arbitrarily large file systems you will probably want to consider solving this problem.

In the next post we'll tackle the last file system area, the file allocation table.

Oh Christmas Tree, Oh Christmas Tree

2009-12-21T18:17:00.001-05:00

The other day my son, age four, noticed that a string of lights were out on our Christmas tree. Last year, we switched to the new LED lights so I wasn't sure how long they should last or how to fix them.

I assumed that, like incandescent tree lights, a single failing LED would prevent the others from lighting. Unfortunately, we discarded the original box and therefore did not have any replacement bulbs (assuming that they came with some).

I picked up a new set of lights but apparently all "white" LEDs are not exactly the same - the new set had a bluer tint that didn't match the remaining sets on the tree. Oh bother, suddenly this became a "project". With the beauty of our tree at stake failure was not an option.

A Google search led me to this extremely informative web page. It turns out these LED lights use a much simpler circuit than I first imagined. No rectifiers, no smoothing capacitors - just 30 LEDs in series with a current limiting resistor. That explains the blinking that I sometimes find irritating.

My plan was to replace the faulting LED with one from the new set. First, however, I had to find it. I used a 9V battery and resistor to build a test rig, removed each LED, and tested it. Eventually, I found the broken one and of course it was the first one in the string that had the current limiting resistor soldered to it. So much for a quick replacement.

After a quick trip to the workshop to solder the resistor onto the new LED, we once again had a working set of really-white lights - except for one bluish one. Oh well, good enough is good enough.

An unexpected bonus from having one bluish LED is that my son now considers it a game to "find" the different one - it doesn't move but that doesn't appear to matter to a four year old :-).

Recovering Deleted JPEGs from a FAT File System - Part 4

2009-12-19T06:12:00.002-05:00

Part 4 in a series of posts on recovering deleted JPEG files from a FAT file system.

Now that we've created a test data set and covered the high-level structure of a FAT file system, it's time to get our hands dirty with some code. Enough talk, more action!!!

Follow the "read more" link for a detailed description of how to read and interpret a FAT file system boot sector.

The following C structure defines the first 36 bytes of the FAT boot sector which is common across all three variants - FAT12, FAT16, and FAT32.

// COMMON BOOT SECTOR
#define FAT_COMBS_OEMSZ (8)

typedef struct {
  uint8_t  jmpInstruction[3];            // 02-00
  uint8_t  oemName[FAT_COMBS_OEMSZ];     // 10-03
  uint16_t bytesPerSector;               // 12-11
  uint8_t  sectorsPerCluster;            // 13-13
  uint16_t reservedSectors;              // 15-14
  uint8_t  numberOfFATs;                 // 16-16
  uint16_t numberOfRootDirEntries;       // 18-17
  uint16_t numberOfSectorsShort;         // 20-19
  uint8_t  mediaType;                    // 21-21
  uint16_t sectorsPerFAT;                // 23-22
  uint16_t sectorsPerTrack;              // 25-24
  uint16_t numberOfHeads;                // 27-26
  uint32_t numberHiddenSectors;          // 31-28
  uint32_t numberOfSectorsLong;          // 35-32
} __attribute__ ((packed))  fatBootSectorCommon_t;

The packed attribute instructs the compiler to place the structure members adjacent to each other in memory. Without this, the compiler might insert padding between structure members to optimize their alignment. In this case such padding would cause a mismatch between the in-memory and on-disk structure layouts making reading the boot sector more cumbersome.

As might be expected, the common part of the boot sector provides the information needed to understand the file system's on-disk structure. Particular fields of interest are:

oemName ASCII description of the OS used to format the file system. OS dependent, no null termination.
bytesPerSector: sector size in bytes - see part 3 for a brief explanation.
sectorsPerCluster: data area cluster size in sectors - see part 3 for a brief explanation.
reservedSectors: number of sectors consumed by the boot sector and any additional reserved space.
numberOfFATs: multiple copies of the file allocation table may be kept to guard against disk errors, this field indicates the number of copies in the FAT area.
numberOfRootDirEntries: size of the root directory area in terms of the maximum number of directory entries. Recall that in both FAT12 and FAT16 space is reserved after the FAT area to store the root directory's contents. The size of a directory entry, 32 bytes, is needed to compute the size of the root directory area from this parameter.
numberOfSectorsShort: total number of sectors in the volume, only valid if the count is less than 64K. Otherwise the value of this field will be 0 and numberOfSectorsLong will contain the correct value.
sectorsPerFAT: size in sectors of a single copy of the file allocation table in the FAT area.
numberOfSectorsLong: total number of sectors in the volume, only valid if the count is greater than or equal to 64K. Otherwise the value of this field will be 0 and numberOfSectorsShort will contain the correct value.

The remainder of a FAT12 or FAT16 boot sector has the following format:

// FAT12 & FAT16 EXTENDED BOOT SECTOR
#define FAT_EXTBS_START (36)
#define FAT_EXTBS_VLSZ  (11)
#define FAT_EXTBS_FSSZ  (8)

typedef struct {
  uint8_t  driveNumber;                    // 36-36
  uint8_t  reserved;                       // 37-37
  uint8_t  bootSignature;                  // 38-38
  uint32_t volumeID;                       // 42-39
  uint8_t  volumeLabel[FAT_EXTBS_VLSZ];    // 53-43
  uint8_t  filesystemType[FAT_EXTBS_FSSZ]; // 61-54
  uint8_t  reserved2[448];                 // 509-62
  uint16_t signature;                      // 511-510
} __attribute__ ((packed))  fatBootSectorExt1216_t;

Much of the extended boot sector is reserved for the possible inclusion of boot code. For this project, only the following extended boot sector fields are of marginal interest:

volumeID: numerical ID - value dependent on the OS/tool used to create the file system.
volumeLabel: ASCII name for the file system, used by some OSs for the mount-point name. No null termination.
fileSystemType: ASCII description of file system type. No standard values, examples include "FAT", "FAT12", and "FAT16". No null termination.

The following C code fragment demonstrates the use of these structures to read the common and extended boot sectors from an image file opened with the descriptor fdImage.

fatBootSectorCommon_t  bootSectorCommon;
fatBootSectorExt1216_t bootSectorExt1216;

fseek(fdImage, 0, SEEK_SET);
fread(&(bootSectorCommon), 
      sizeof(fatBootSectorCommon_t), 1, fdImage);

fseek(fdImage, FAT_EXTBS_START, SEEK_SET);
fread(&(bootSectorExt1216), 
      sizeof(fatBootSectorExt1216_t), 1, fdImage);

Thanks to the use of the packed attribute, the on-disk structures can be read directly into their in-memory counterparts and accessed using the standard C structure idioms.

The following code fragment shows how to use the boot sector information to calculate the location and size of the major file system areas.

#define ALIGN(size, alignment) \
 (((size) + (alignment-1)) / (alignment))

size_t volSizeSectors;
size_t fatFirstSector;
size_t fatSizeSectors;
size_t rootdirFirstSector;
size_t rootdirSizeSectors;
size_t clustersFirstSector;
size_t clustersSizeClusters;

if (bootSectorCommon.numberOfSectorsShort > 0) {
  volSizeSectors = 
    bootSectorCommon.numberOfSectorsShort;
  
} else {
  volSizeSectors = 
    bootSectorCommon.numberOfSectorsLong;
}


fatFirstSector = 
  bootSectorCommon.reservedSectors;

fatSizeSectors = 
  bootSectorCommon.sectorsPerFAT * 
  bootSectorCommon.numberOfFATs;

  
rootdirFirstSector = 
  fatFirstSector + 
  fatSizeSectors;

rootdirSizeSectors = 
  ALIGN((bootSectorCommon.numberOfRootDirEntries * 32,
         bootSectorCommon.bytesPerSector);


clustersFirstSector = 
  rootdirFirstSector + 
  rootdirSizeSectors;

clustersSizeClusters = 
  (volSizeSectors - clustersFirstSector) /
  bootSectorCommon.sectorsPerCluster;

As mentioned above, calculating the size of the root directory area requires knowing the size of a directory entry. We'll discuss the root directory in a future post - for now it is sufficient to know that each entry is 32 bytes.

Printing the boot sector's contents to a console is a fairly simply matter with the only complication being that the ASCII information should first be copied to null-terminated strings.

char oemName[FAT_COMBS_OEMSZ+1];
char volumeLabel[FAT_EXTBS_VLSZ+1];
char filesystemType[FAT_EXTBS_FSSZ+1];

strncpy(oemName,        
        (char *)pBootSectorCommon->oemName, 
        FAT_COMBS_OEMSZ);
strncpy(volumeLabel,    
        (char *)pBootSectorExt1216->volumeLabel, 
        FAT_EXTBS_VLSZ);
strncpy(filesystemType, 
        (char *)pBootSectorExt1216->filesystemType, 
        FAT_EXTBS_FSSZ);

oemName[FAT_COMBS_OEMSZ]       = 0;
volumeLabel[FAT_EXTBS_VLSZ]    = 0;
filesystemType[FAT_EXTBS_FSSZ] = 0;

Voila! This should be enough information to write a simple program capable of reading a FAT file system boot sector, locating the major areas, and printing the information to a console.

As an example, below is the output of the program I am (re)developing alongside these posts from which the code fragments above were taken. The output was generated by running the program against the test disk image created in part 2 of this series. Recall that my development platform is an Apple MacBookPro running OS X Snow Leopard (10.6.2).

$ sw_vers
ProductName:    Mac OS X
ProductVersion: 10.6.2
BuildVersion:   10C540

$ wc -l fatrecover.c 
     306 fatrecover.c

$ make all
gcc -g -Wall fatrecover.c -o fatrecover

$ ./fatrecover frtest1.dmg 

=== FAT RECOVER v0.0 ===

Opening file frtest1.dmg................OK
Reading boot sector.....................OK
Processing boot sector..................OK

BOOT SECTOR:
          OEMName: (BSD  4.4)
         volumeID: 63260cf5
     Volume Label: FRTEST1    
           FSType: FAT16   
     Bytes/Sector: 512
  Sectors/Cluster: 4
 Reserved Sectors: 1
   Hidden Sectors: 0
 Sectors/Vol (2B): 32768
 Sectors/Vol (4B): 0
      Sectors/FAT: 32
        # of FATs: 2
  RootDir Entries: 512

MAJOR STRUCTURES:
      AREA    OFFSET      SIZE
----------  --------  --------
 BOOT+RESV  00000000  0x000001 (sectors)
       FAT  0x000001  0x000040 (sectors)
   ROOTDIR  0x000041  0x000020 (sectors)
      DATA  0x000061  0x001fe7 (clusters)

Note that the structure offsets are in units of sectors.

From the output we can see that the:

volume name is "FRTEST1", matches the name specified when the disk image was created.
sector and cluster sizes are 512 and 2048 bytes respectively.
FAT area starts at sector 1 and is 64 sectors long (2 * 32).
root directory can contain up to 512 entries.
data area contains 0x1fe7 or 8167 clusters.
volume contains a total of 32768 sectors - 16MB as expected.

To sanity check the output, let's validate the size of the data area.

Total Sectors	32768	0x8000
Less Boot Sector	32767	0x7FFF
Less FATs	32703	0x7FBF
Less RootDir	32671	0x7F9F
Divided by 4	8167	0x1FE7
(remaining sectors)	3

The check looks good. The remaining three sectors further validate the calculations. Only the boot sector consumed an odd number of sectors - one - which implies that there should be three or less unused sectors in the data area (since the cluster size is four sectors).

As a second sanity check, let's make sure the file allocation table's are an appropriate size. Since FAT entries are 16 bits (2 bytes), we know that each FAT contains (32*512)/2 = 8192 entries which is enough to represent the 8167 clusters in the data area.

The sanity checks appear to pass - it looks like the above code works. In the next post we'll skip ahead to processing the root directory before tacking the FAT.

Addendum

One important detail omitted from the main-line discussion above is that all FAT file system data structures are stored on-disk in little endian order. As I am using a little endian machine (Intel Core 2 Duo) the example code above uses the value of all multi-byte fields directly. A big endian machine, however, would have to convert all of the multi-byte field values from little to big endian before using them.

When I originally did this project in 2004, I used ah PowerPC Apple PowerBook which had a big endian architecture. As a result, my original program had to do the endian conversion. Below are the macros I wrote to do the necessary byte swapping.

//  Macros to byte swap to change endianess
//
#if BYTE_ORDER == BIG_ENDIAN


#define LEToHost16(_x)                          \
do {                                            \
    unsigned char *buff = (unsigned char *) _x; \
    unsigned char tmp;                          \
    tmp     = buff[1];                          \
    buff[1] = buff[0];                          \
    buff[0] = tmp;                              \
   } while(0)


#define LEToHost24(_x)                          \
do {                                            \
    unsigned char *buff = (unsigned char *) _x; \
    unsigned char tmp;                          \
    tmp     = buff[2];                          \
    buff[2] = buff[0];                          \
    buff[0] = tmp;                              \
   } while(0)


#define LEToHost32(_x)                          \
do {                                            \
    unsigned char *buff = (unsigned char *) _x; \
    unsigned char tmp;                          \
    tmp     = buff[0];                          \
    buff[0] = buff[3];                          \
    buff[3] = tmp;                              \
    tmp     = buff[1];                          \
    buff[1] = buff[2];                          \
    buff[2] = tmp;
   } while(0)

#else

#define LEToHost16(_x) 
#define LEToHost24(_x) 
#define LEToHost32(_x) 

#endif

An Incredible Library

2009-12-15T18:39:00.004-05:00

I have never been more jealous in my life than I am of Jay Walker's personal library.

If I had copious amounts of money, this is what I would do with it - books, interesting gadgets, and lots of wood. I don't know if I would ever leave the house :-).

Even just working in such an aesthetic environment would be wonderful.

Recovering Deleted JPEGs from a FAT File System - Part 3

2009-12-15T06:17:00.002-05:00

Part 3 in a series of posts on recovering deleted JPEG files from a FAT file system.

The FAT file system was invented in 1980 by Tim Paterson while developing 86-DOS, the precursor of MS-DOS. Since its creation, FAT has gone through a number of evolutions to accommodate growing disk sizes, and provide more capabilities. Although FAT is nearly 30 years old, it remains in common use due to its ubiquitous OS support and simplicity - both important factors for embedded consumer devices like digital cameras.

FAT's history is complex, a retelling could consume an entire series of posts itself. For this project, it is sufficient to know that there are three main variants - FAT12, FAT16, and FAT32 - each successively supporting larger maximum disk sizes. Generally speaking, the on-disk format of all three variants is very similar, so much so that code developed to grok one format can, with reasonable effort, be hacked to grok another¹. In this project, we'll be working with a FAT16 file system which hdiutil can be explicitly requested to create by using the argument -fs "MS-DOS FAT16"².

The following diagram depicts the high-level, on-disk structure of a FAT16 file system (not drawn to scale).

+---------+-------+--------+-------+---------------------+
|   BOOT  | RESV  |   FAT  | ROOT  |  DATA ............. |
|  SECTOR | (OPT) |        | DIR   |  AREA ............. |
+---------+-------+--------+-------+---------------------+
0                                                        N

In computer storage, capacity is divided into fixed sized units called sectors - typically 512 bytes long³. The sector is the fundamental unit for addressing storage and smallest amount of data that can be transferred to/from a disk drive. While older disk drives used an awkward addressing scheme based on physical geometry, newer drives use a linear series of sector addresses.

The first sector (offset 0) of a FAT16 file system contains the BOOT SECTOR which provides critical information about the file system's organization. Optionally, a number of sectors may be reserved after the boot sector (RESV).

The next major data structure is the File Allocation Table (FAT) from which the file system gets its name. The FAT is essentially an array of 16bit elements ⁴ each representing a fixed size portion of the DATA AREA. To minimize the FAT's relative size, each element represents a cluster⁵, a power-of-two multiple number of sectors. In addition to tracking the allocation status of each DATA AREA cluster, FAT elements are also used to store pointers forming linked-lists describing the on-disk location of files and sub-directories spanning multiple clusters.

After the FAT comes the root directory area (ROOT DIR) used to hold the information describing the files and sub-directories at the top of the file system namespace tree. In FAT12 and FAT16, the root directory area is a fixed size which limits the numbers of files and sub-directories that can be stored in it.

The remainder of the disk capacity (DATA AREA) is essentially a heap allocated as needed to store file and sub-directory data. As mentioned previously, use of the DATA AREA is managed by the FAT.

In the next few posts, I'll describe each of these major areas in greater detail and present the code needed to interpret them. By the end, we should essentially have a read-only FAT file system implementation that will serve as the basis for the remainder of the project.

Footnotes:

¹ Here I am ignoring many, many subtle differences and complications. A thorough discussion of the technical details for all of FAT's variants is outside the scope of this series. The curious reader is recommended to read the bountiful information available via a Google search. Brian Carrier's book, File System Forensic Analysis, is another valuable resource (which sadly wasn't available when I first did this project in 2004).

² Note that FAT16 file systems have a minimum supported size - usually 16MB but some tools may allow smaller sizes.

³ Some enterprise level disk drives use a 520 byte sector - the additional 8 bytes are often used to store error checking and recovery information for RAID systems.

⁴ The size of the FAT elements is one of the principal differences between the file system variants. FAT12 uses 12bit entries while FAT32 uses 32bit entries. The FAT element size is one of the factors that determines each variant's maximum supported disk size.

⁵ Other file systems may use the term block instead of cluster.

Recovering Deleted JPEGs from a FAT File System - Part 2

2009-12-14T05:39:00.002-05:00

Part 2 in a series of posts on recovering deleted JPEG files from a FAT file system.

Whenever I develop an analysis program I first create a dataset to test and experiment against. In part 1, I mentioned that I used my digital camera to create a test data set for the original project in 2004. For this series of posts, I thought it would be better to use a data set reproducible by others. Two things are required to accomplish this goal:

A collection of commonly available test images
A repeatable method for creating disk images of FAT file systems

A Google search for test images led me to this wikipedia page from which I selected the University of Southern California Signal & Image Processing Institute's data set - specifically the miscellaneous corpus. This collection consists of 44 TIFF images of various resolutions ranging in size from 64KB to 1MB (17MB in total). Since JPEG images are needed for this project, I used the following ImageMagick command to do the conversion.

mogrify -format jpg -quality 90 *.tiff

After the conversion, the file sizes ranged from 4.8KB to 350KB (3.4MB in total) - a conveniently sized collection for this project.

In the 2004 project, I used the UNIX dd command to make a disk image of my camera's memory card. However for this project, I wanted a way to create disk images without requiring a physical device. One option considered was to use Linux loop devices but I wanted to use my machine-of-choice, an Apple MacBookPro, for this project - an artificial but important constraint since this is for fun.

After some research, I discovered that Apple's hdiutil utility can create a suitable image using the following command:

hdiutil create \
        -fs "MS-DOS" \
        -megabytes <SIZE> \
        -layout NONE \
        -volname <VOLNAME> <IMAGENAME>

Executing this command creates the file <IMAGENAME>.dmg that is an image of a FAT file system called <VOLNAME> with a total capacity of <SIZE> megabytes. The remaining argument, -layout NONE, prevents a partition table from being added to the image - an unnecessary complication for this project.

The following example illustrates the OS X terminal commands needed to create a 16MB disk image with a single JPEG file on it¹

$ hdiutil create \
          -fs "MS-DOS" \
          -megabytes 16 \
          -layout NONE \
          -volname FRTEST1 frtest1
..................................................
created: /<PATH>/frtest1.dmg

$ hdiutil attach frtest1.dmg 
/dev/disk1             /Volumes/FRTEST1

$ cp images/4.2.04.jpg //Volumes/FRTEST1//

$ hdiutil detach //Volumes/FRTEST1//

Using the selected image corpus and above hdituil terminal commands, a wide variety of test disk images can be created programmatically via shell scripts - just what is needed for this project.

In the next post, we'll start down the path of grokking a FAT file system layout.

Footnotes:

¹ Minor changes were made to the example output to remove machine specific information (i.e. paths) and fit it within the limited size of the post area.

Recovering Deleted JPEGs from a FAT File System - Part 1

2009-12-11T06:28:00.007-05:00

Part 1 in a series of posts on recovering deleted JPEG files from a FAT file system.

In 2004, my in-laws returned from a vacation and had all of the pictures accidentally deleted from their digital camera. When I heard the news my first thought was that the data may still be there!

Often, deleting a file only erases its associated file system metadata (i.e. name, owner, etc) - the file's data is left unchanged. As a result, a deleted file can sometimes be recovered by finding the unchanged data fragments and recombining them in the correct order. I reasoned that if their camera took this metadata-only approach then there was a good chance that some of the pictures could be recovered.

Unfortunately, my in-laws lived in another state so I couldn't examine their camera's memory card right away. I suggested that they remove the card from the camera and bring it with them on their next visit so that I could analyze it then.

My initial plan was to try one of the many file recovery tools that already existed. However, I soon began to wonder how hard it would be to write a program to recover the pictures myself. Finding the challenge exciting, I immediately began spending all of my spare time coding up a recovery program.

After one week, and a lot of caffeine, I had a C program capable of recovering deleted JPEG files from a FAT file system - the typical file system used by digital cameras. Using my own camera as a test bed, the program could reliably recover pictures after performing an "erase all" operation. Cool!

Unfortunately, the story didn't end as well for my in-laws. When I finally received their memory card I found that all of the file system data blocks had the value 0xFF - a clear sign that the entire FLASH memory had been erased¹. The data was gone.

Despite the unfortunate ending, this project was one of my favorite spare-time hacks. So much so in fact that I thought it would be fun to recreate it as a series of blog posts. Over the next few weeks I plan to write a series of posts under the label "FATrecover" describing how to develop such a program. By the end of the series, hopefully anyone with sufficient coding experience will be able to write their own FAT file system recovery program.

Footnotes:

¹ FLASH memory, being a form of EEPROM, cannot be re-written directly. Instead, the FLASH memory cells must first be returned to an unwritten state - an operation typically called an "erase". After being erased, the affected memory cells have a value of 0xFF.

Behind the Code: Jim Gray

2009-12-01T05:46:00.001-05:00

One of my engineering role models is the late Jim Gray. I happened across a Microsoft Channel9 interview with him and decided to watch it.

I most appreciated Jim's comments on the following three points:

The importance of first principles
The "risk" that research presents to established products
The role writing played in his getting recognition for what was actually joint work with others

One of the most influential papers that I've read was Jim's (and Shenoy's) Rules of Thumb in Data Engineering. This relatively short paper is packed with insights derived from simple trend data and the application of first principles. Since that time I've tried to rely on first-principles while researching new technologies and communicating the results. I've found this approach to be both highly effective and differentiating as, unfortunately, the practice doesn't seem to be as common as it should be.

Although my current position doesn't compare to the one Jim held at Microsoft, I do run a small research team inside of a large company. As a result, I found his comments on this topic interesting. In particular, I was pleased to hear that I have come to a point-of-view in common with Jim's - research innovations represent increased risk to an established line of business that is trying to minimize risk. It's a classic example of the "change vs. control" conflict that Kotter describes in his seminal paper, What Leaders Really Do. In realizing this, I have come to the conclusion that it is my group's responsibility to reduce the risk of research innovations to a level that allows the main-line managers to predict with confidence the cost/time/effort required to bring the new product/feature to market. As a result, creating new technologies is not sufficient - my team must also make those technologies consumable to an existing line of business. This has been perhaps one of the most important realizations of my career and it was encouraging to hear Jim make similar comments.

Towards the end of the interview, Jim made it a point to say that much of "his" work was actually done in collaboration with others. However, much of the credit has been given to Jim because he took the additional effort to document the work in the form of papers, articles, books, etc. This statement matches my own observations of authors/presenters earning outsized credit and highlights the importance of communicating effectively in regards to career growth.

400 Years of the Telescope

2009-11-30T19:04:00.002-05:00

If you're interested in astronomy then you might enjoy this PBS documentary, 400 Years of the Telescope.

This beautifully filmed show summarizes the history of the telescope beginning with Galileo's first experiments with looking glasses up to the Hubble and radio astronomy. Along the way it (briefly) describes various recent technologies like adaptive optics and techniques for building very large mirrors.

While not a deeply technical resource, it is a nice way to spend an hour. In my case, I watched this on my iPhone while waiting for my son at a doctor's appointment and it was much better than reading out-of-date magazines - well worth the $1.99 cost.

Watching this made me want to work in an observatory someday, maybe I've seen the movie Contact too many times (if that is even possible) :-).

N is a Number

2009-11-29T18:16:00.000-05:00

Earlier this year I read the book "Linked: The New Science of Networks" which prominently featured the mathematician Paul Erdős. The book mentioned a documentary about Erdős entitled "N is a Number" that I was curious to see. Thanks to Netflix, I finally got the chance last weekend.

Most importantly, this movie is about Erdős "the person" and not his mathematics. While the film discusses his mathematical activities and accomplishments, it makes no material attempt to explain them.

With that focus in mind, I thought this was a nice documentary. The footage of Erdős was very entertaining and I suspect conveyed an accurate sense of his personality. I found the interviews of his various acquaintances equally entertaining - especially the elderly English women who recalled Erdős as a young man. Such focus on Erdős' human qualities really helped cast him as an "exceptional person" instead of an "un-relatable genius".

As is often the case with people of substance, Erdős suffered hardship and had a number of significant life experiences - especially during WWII. Perhaps this explains his generosity and thoughtfulness of others that was recounted a number of times in the documentary.

I was most surprised to learn of Erdős' nomadic lifestyle - for most of his life he had no permanent home or job. Instead, he followed his interests around the world attending conferences and staying with (very) supportive friends. If an acquaintance on a different continent came up with an interesting problem, Erdős would hop on a plane with all of his worldly possessions in two small suitcases and often only a small amount of money in his pockets. I found his nomadic and minimalistic lifestyle both impressive and foreign as I can't imagine being without a "home" to return to. I wonder if this is an insight into the personal sacrifice needed to achieve greatness beyond having raw-talent alone.

Clearly Erdős was a genius which I already understood from reading other references before watching this film. The depth and breadth of his work was unique and will likely be unmatched for a long time to come. But, putting his mathematical achievements aside, Erdős still seemed like an impressive, inspirational, and great man - definitely a role model worth reflecting on.

Bug Hunt Wrap-up

2009-11-24T15:48:00.002-05:00

To wrap up my "Bug Hunts" series, I thought it worthwhile to quickly reflect on what made these particular bugs so special.

In the series I posted about five bugs:

Since these five represent only a small subset of all the bugs that I have diagnosed during my career I have to ask myself - what makes these bugs so special?

To me, the common thread among them is that their resolution involved a leap of thought based on skill, imagination, concentration, and an intuitive understanding of the associated technologies. In each case the answer was not self-evident from the information available and became clear only after deep thought produced an incredibly rewarding "ah-ha" moment. The short-term elation from these "ah-ha" moments are one reason why these bugs hold a special place in my memories.

However, I think the deeper answer to my question is that these bugs were milestone events that, to varying degrees, demonstrated and validated the skills that I had worked hard to acquire. The longer-term feeling of "mastery" and confidence produced by these moments were the reward required to make my past efforts satisfying and motivate further developing my skills.

In many ways, this conclusion correlates well with Malcom Gladwell's comments on satisfying work in his book Outliers. From page 49:

Those three things - autonomy, complexity, and a connection between effort and reward - are, most people agree, the three qualities that work has to have if it is to be satisfying.

The lesson that I draw from this reflection is that it is important to periodically seek out validating experiences to demonstrate acquired skill, obtain satisfaction, and refuel a continuous self-development effort.

The Case of the Corrupted Cache Line

2009-11-21T05:50:00.002-05:00

To culminate (for now) my "Bug Hunts" series of posts I will attempt to describe the hardest problem that I have solved to date. This was a very complicated problem which I found challenging to describe without going into excessive detail but I think the discussion below does an adequate job.

In prior posts, I described the ccNUMA system that I worked on during my first industry job. After the (relative) success of the first system, a second generation system was developed that consisted of numerous incremental improvements - faster processors, better memory controllers, faster interconnect ASICs, a few coherency protocol optimizations, etc. In general, the pre-production testing went smoothly and the system started shipping with the fullest of confidence.

Shortly after going GA, however, a coherency protocol problem appeared in the field. The problem only seemed to occur on the largest (eight node) second generation systems and had a long mean time between failure even under very heavy workloads. After ruling out the obvious suspects (those coherency protocol optimizations I mentioned), we instrumented an eight node system in the lab and started the bug hunt.

To describe the failure, I need to further explain the SCI coherency protocol used in these systems. Like other distributed shared memory protocols, the SCI protocol segmented the system's memory into fixed sized chunks called "lines" (64 bytes in SCI's case). Being a ccNUMA machine, the lines were distributed across all of the nodes in the system. For each line of memory in the system there was a single "home-node" that contained the associated physical memory and served as the coordination point for all accesses to it. Mapping tables initialized at boot time identified the home-node for each line of memory which remained constant while the machine was running. "Remote-nodes" could access the lines from home-nodes and cache them via the SCI protocol and interconnect.

One big challenge in using the SCI protocol was that it assumed an architecture where the memory and processors were located on separate nodes. In this model, home-nodes were passive and simply responded to protocol requests from remote nodes - the protocol didn't provide a means for home-nodes to obtain access to their own lines cached elsewhere in the system. Unfortunately, our system used a different architecture with each node containing both processors and memory which put it at odds with the standard SCI model. As a result, a workaround was needed in our system to allow home-nodes to obtain access to their own memory lines.

The chosen workaround was to essentially allow home-nodes to temporarily adopt multiple personalities. In order to re-gain access to a local memory line cached elsewhere in the system, a home-node would:

Temporarily create a fictitious remote node persona
Participate in the coherency protocol as a remote node to obtain the desired access rights
Act as a remote-node performing an eviction to remove the fictitious-remote-persona from the coherency sharing-chain (SCI used a distributed linked list to identify the remote-nodes with cached copies of each line).

While this dual-personality solution worked, the need to simultaneously track both the home and fake-remote-persona protocol states significantly increased the complexity of our implementation (foreshadow alert!).

Another important aspect of the system was the way that the per-line access-rights information was maintained. The Coherency ASIC was responsible for maintaining the SCI state (which indicated the access rights) for each line of local memory and remote memory cached in the L3 cache. Because of the amount of main-memory (4GB per node) and L3 cache (512MB per node), the SCI state information was stored in an external DRAM attached to the Coherency ASIC. Storing the SCI information in this way presented a problem in that it would have taken too long to query it for each transaction on the processor bus (which was necessary to maintain coherency). To get around this problem, an SRAM attached to the FSB ASIC was used to cache the access-rights information for recently accessed lines (both local and remote). Using the SRAM, the FSB ASIC could quickly determine if a processor bus operation could be allowed to continue (node had sufficient access) or needed to be postponed (node didn't have sufficient access). Although the SRAM allowed the majority of processor bus operations to complete un-delayed, it burdened the Coherency ASIC with the additional task of keeping the access-rights cached in SRAM consistent with the SCI tags (another foreshadow alert!).

With those additional explanations out of the way…

Our initial investigation into the failure revealed that the primary symptom was an inconsistency between the SCI and SRAM states for a local memory line. Specifically:

The SCI state indicated that the line was not cached anywhere else in the system - the local node had full access rights to the line.
The SRAM state indicated that the line was cached in a modified state elsewhere in the system - the local node had no access rights to the line.

Oh bother. This inconsistency was obviously incorrect and the ASICs were designed to generate a panic when it occurred to prevent data corruption (which access-rights information was correct??).

At first, we couldn't think of how such an inconsistency could occur. After much effort we managed to get a synthetic workload running in the lab that could induce the failure approximately once per day. However, because of the system's size (eight nodes), large number of busses-of-interest (3 per node, 24 total), and a limitation of only having two logic analyzers it was extremely difficult to get a clear picture of the failure. At best, all we could get (if we were lucky) was a trace of a couple of bus operations being performed against the failing line. It was clear that we stood little chance of capturing a definitive, complete trace of the failure - it was time to put on our thinking caps.

As luck would have it, this failure emerged at the end of a financial quarter and there was a substantial order being prepared for shipment. Management was unwilling to ship the order until the problem was resolved which meant there was a large amount of revenue at risk. All of sudden this problem got upper-management's full attention - not good.

Given the problem's complexity, and the substantial amount of executive attention my mentor (the MicroKid) and I isolated ourselves in his office and began brainstorming how the state inconsistency could occur. After a while, we identified a couple of areas in the microcode that could lead to such a problem but neither of us could think of a sequence of events to manifest it. After a lot of joint discussion we decided to brainstorm separately to parallelize the effort.

For three days I sat in my cube listening to music, staring at trace fragments, and assembling in my mind all the possible interactions that could cause the state inconsistency we were observing. I don't think I have ever concentrated on a single thing as hard for that long at any other time in life. Finally, everything "clicked" and I knew how the state inconsistency was occurring.

The failure involved a complex interaction between three nodes with one being the associated memory-line's home node. The following is a (simplified!) description of the failure:

The initial condition was that the line was cached in a modified state in a remote node (Node1) and the home-node was attempting to get read access. To accomplish this task, the home-node created its fake-remote-persona and performed the necessary operations to obtain a read-copy of the line. Upon getting a copy of the line, the SRAM access rights were set to "read-only" and the local processor's request was completed.
In order to remove the fake-remote-persona from the SCI sharing chain, the home-node began an eviction operation to get rid of the now unneeded second personality by sending a request to Node1.
Just as the home-node began performing the eviction operation for its fake-remote-persona, Node1 also began an operation to evict the line from its L3 cache. According to the SCI protocol, such eviction races were resolved by allowing the "older" remote node (Node1) to proceed ahead of the "younger" remote node (which in this case was the home-node's fake-persona).
While the eviction race condition between the home-node and Node1 was being resolved, a third node (Node2) started an operation to obtain read access to the same line which completed successfully.
Upon completing the eviction operation with Node1, the home-node detected that Node2 had obtained read-access to the line (Step 4) which meant that it now had to perform an eviction operation with Node2 in order to finish removing the fake-remote-persona from the SCI sharing chain. This required the home-node to downgrade the SRAM access rights to "no-access" to guard against potential SCI operations that could invalidate the local copy. The home-node then resumed its eviction effort by informing Node2 that it was leaving the sharing chain.
Node2 received the home-node's fake-remote-persona's eviction request and sent a response.
Immediately after it sent the response in step 6, Node2 began an operation to evict the line from its L3 cache.
Due to an extremely unlikely sequence of events, Node2's eviction request from step 7 got received and processed by the home-node while Node2's response from step 6 was still in-fight. In order for this to have happened, a request had to bypass a response in the interconnect which was highly improbable due to the priority given to sending responses over requests.

At the end of this sequence, the SCI state was correct in indicating that the line was not cached anywhere else in the system. The problem was that the microcode didn't explicitly check for the request-bypassing-response order of events that occurred in step 8. As a result, the microcode failed to update the SRAM information with the correct access rights thus leading to the problem. Over a decade later, I still get a brain cramp from thinking about this sequence of events.

Once the microcode bug was identified it took less than five minutes to fix. Luckily, I figured out and fixed the problem on the Friday afternoon before the end of the quarter so the big order sitting on the docks was able to ship, the company got to recognize the revenue in the quarter, and the account's sales team got a hefty commission. For my efforts, my management compensated me with, wait for it, a cup of coffee. Seriously, after "saving" millions in revenue I got a $2.00 cup of coffee from my Director. Oh well, luckily I wasn't in the role for the money :-).

And that, to date, is the hardest problem that I have ever solved.

The following diagram summarizes the failure sequence described above. Note that to simplify the diagram I avoided using the actual SCI commands and states involved as their obscure nature would have required too much explanation. Recall that each lab trace contained, at-best, only one or two of the included operations. To solve the problem, I more or less had to imagine all of the possible interactions that could be occurring and then identify this sequence as a failing case.

The Case of the Deadlocked Queues

2009-11-12T06:06:00.002-05:00

Updated on 12.4.2009 with a diagram.

In a previous post I described my first industry job where I got to work on the coherency subsystem for an enterprise class ccNUMA server. For my "Bug Hunts" series of posts I thought I would describe a complex problem that I root-caused during pre-production testing.

During the alpha silicon testing, the systems started hanging under heavy load. Our initial investigations discovered that operations on the processor (FSB) and inter-ASIC (F2C_Bus) busses appeared to get stuck waiting for various pregrant signals to activate. The situation looked bad, it appeared that we had a multi-ASIC deadlock on our hands.

In simple terms, the coherency subsystem on each node had two responsibilities:

accept requests from the local processors, send requests to other nodes to perform the necessary coherency & memory operations on the remote processor busses, and return responses to the local processors.
accept requests from other nodes on behalf of remote processors, perform the necessary coherency & memory operations on the local processor bus, and return responses to the other nodes for the remote processors.

To guarantee forward progress, the coherency subsystem had one golden rule - requests shall never block responses. At the transport layer this rule was enforced through the use of two independent virtual channels with priority given to the response channel. Within the ASICs, the golden rule was maintained by carefully designed scheduling and priority logic. Theoretically the golden rule should have prevented deadlocks from occurring - so much for theory.

Since this was a real system, our view was limited to the activity observed on the busses - we had no visibility into what was happening inside the ASICs. To get around the visibility problem, I worked closely with a friend on the verification team to create a script that reproduced, in simulation, the activity observed in the lab. Through these simulation tests I gained an insight into what was happening inside the ASICs. In the meantime, I consulted with the ASIC designers to better understand some of the unexpected behaviors discovered during the investigation.

I can still remember well the meeting when everything suddenly "clicked" in my head. We had brought together both ASIC teams (which were geographically distributed) to discuss the problem and attempt an explanation. To focus the conversation, I asked a series of very specific "what if" questions that finally led to an "ah ha" moment.

As with most complex failures, a number of smaller problems combined to cause the deadlock. The diagram included in my prior post may provide more context for the explanation that follows.

The first problem was that the FSB ASIC violated the golden rule by strictly ordering, in a single queue, requests from remote processors and responses to local processors. During the investigation it was discovered that this design change was made to resolve a race condition between evicting modified data from the L3 cache (accomplished via a remote processor request) and installing the replacing data into the cache (accomplished via a local processor response). Oops.

The second problem was much more subtle, there was no ordering rule between local and remote responses! The microsequencer inside the Coherency ASIC was responsible for processing all coherency requests, both from this and other nodes, and generating the associated responses. The microsequencer treated all out-bound responses equally and used a common queue to buffer them for transmission. This single out-bound response queue essentially created a cycle in the path of queues between the Coherency and FSB ASICs - a response blocked at the head of this queue would prevent all other microsequencer responses from making forward progress.

The third problem was that the microsequencer could issue more requests than it had buffers to queue out-bound responses. This meant that the microsequencer relied completely on out-bound responses making forward progress for it to be able to receive responses for the requests it issued.

Together, these three problems resulted in a deadlock when:

The coherency microsequencer sent a burst of local processor responses to the FSB ASIC. These actions freed coherency engine resources but consumed FSB ASIC resources preventing it from accepting more responses.
The coherency engine's response queue got full with an FSB ASIC bound local processor response at the head of the queue. At this point, the resource consumption described in (1) prevented the response at the head of the queue from proceeding.
Shortly thereafter, the FSB ASIC completed a number of Coherency ASIC requests and sent responses to the microsequencer. Because the microsequencer's out-bound response queue was block by (2), it couldn't send the remote responses generated by the FSB ASIC responses. This condition prevented the microsequencer from accepting more responses and caused the FSB ASIC's single request/response queue to stall.
The local processor responses already in the FSB ASIC queue from (1) were unable to make progress due to the stall described in (3). As a result, the FSB ASIC could not accept more responses to alleviate the stall described in (2).

The result, neither ASIC could make progress until the other could - a classic deadlock.

In reality, the actual deadlock scenario was much more complicated than this - it required a complex sequence of events, specific event timings, and an interplay with non-coherent inter-node accesses (i.e. accesses to another node's PCI space). However, the simplified explanation above captures the salient points - in particular the need for an additional ordering rule between local and remote responses.

Once the problem was understood, the fix was relatively easy. Luckily we had programmatic control over the depth of various ASIC queues that allowed us to configure the system to avoid the deadlock condition without having to re-spin silicon - and then there was much rejoicing.

Although the deadlock had been solved the story didn't end there for me. I was so fascinated by this problem that I spent a significant amount of time over the next few months writing a program capable of analyzing a system of queues to discover such deadlocks. 10K lines of perl code later, I had a program that took as input a queuing model expressed in a domain specific language that I designed for the task. The model language was rich enough to represent such things as different kinds of tokens, tokens spawning new tokens, global token limits, conditional routing rules for tokens, and the sharing of limited resources. The program used this information to find patterns of tokens in queues that resulted in deadlock conditions. Although I didn't know it at the time, I essentially used a constraint propagation method to reduce the search space to a reasonable size. Using the program, I was able to "predict" the deadlock condition found in the lab and validate the configuration changes made to avoid it. Although the tool never got used again, the sense of personal accomplishment from developing it made the effort worthwhile.

My history with this deadlock finally came to an end when, for the third generation system, I redesigned the coherency engine to fix this and other troublesome bugs. The opportunity to fix this problem myself really brought a fulfilling sense of closure to the experience.

This deadlock bug is one of my favorite bug hunts of all time. It was a complex problem that required a deep understanding of the system, a holistic view of its behavior, and the ability to see how the many micro-behaviors interacted to cause the deadlock. Furthermore, it led to the simulation and ASIC re-design activities which were equally rewarding experiences.

This, however, wasn't the hardest bug that I ever root caused. That will be the topic of the next Bug Hunt post once I figure out how to describe it.

UPDATE

To clarify this post I decided to add a simple diagram of the deadlock condition. The actual failure was much more complex but hopefully this diagram captures the salient points from the description above - the impact of the shared queue for requests+responses and the need to route local and remote responses differently.

A Lucky Career Start

2009-11-06T19:06:00.004-05:00

Updated on 12.4.2009 with a better diagram of the system's architecure

I have two more bugs in mind for my "bug hunt" series but before I can post about them I need to provide a little background information about my first real industry job.

After graduate school, I had the rare opportunity to help build a large-scale, enterprise-class ccNUMA server. At the time, 1996, ccNUMA architectures were leading-edge technology and ours was one of the first to utilize the Intel platform.

The system's architecture was based on "building block" nodes each containing four PentiumPro processors, 4GB of main memory, and 12 PCI slots. Up to eight nodes could be connected together using a high-speed interconnect to create a system with 32 processors, 32GB of main memory, and 96 PCI slots. The system ran a proprietary version of UNIX carefully tuned to work efficiently on its specific architecture. At its maximum size the system consumed two 19 inch racks - big iron indeed.

The high-speed interconnect was based on the IEEE Scalable Coherent Interconnect (SCI) standard and responsible for creating a single, cache coherent memory space out of the combined node resources. Through the interconnect, any processor could access the memory on any of the nodes - albeit at variable latency based on their relative locations in the system. In addition to the processor caches, each node contained a large capacity "L3" cache to store data fetched from other nodes to avoid, as much as possible, the significantly greater "remote" access latency. The SCI interconnect inter-operated with the processor and "L3" caches to ensure that accesses to cached data were handled correctly. Together, these capabilities are what made the system a cache-coherent non-uniform memory (ccNUMA) architecture. SCI was a ring based protocol and our system used two counter rotating rings to halve the average node-to-node latency, double the bandwidth, and provide some measure of redundancy (not fault-tolerance, just reboot level redundancy if a ring failed).

The ccNUMA subsystem consisted of four custom ASICs, two designed in-house and the others jointly developed with a partner company. One of those ASICs was dedicated to maintaining the SCI coherency protocol and used a microsequencer and microcode combination to provide a programmable, high-performance coherency engine. The microsequencer utilized a VLIW-like instruction set to maximize parallel operation and minimize the control store's size.

I joined the project just after its start and my initial responsibilities were to become an SCI expert, be able to program the coherency microsequencer, and optimize the SCI coherency protocol implementation to match our machine's specific architecture. After completing those tasks ahead of schedule, I went on to do a wide variety of things including writing verification scripts for the coherency ASIC, implementing the BIOS responsible for initializing the SCI subsystem, serving as a systems engineer for the coherency subsystem, root-causing complicated bugs in all four ASICs, and writing a variety of programs to automatically identify failure root causes from simulation, emulation, and production logs. In the subsequent two follow on projects, my responsibilities continued to grow and culminated in an architect role for the third generation system.

As a computer-obsessed young engineer just starting a career this job was a dream come true. On a daily basis, I had direct interaction with ASICs, logic board design, exotic computer architectures, complicated caching protocols, low-level coding, and advanced operating systems. Stuff that I had only read about in text books was now literally at my finger tips to be studied, understood, and played with.

It was the people that I got to work with, though, that really made this job special. Everyone on the project shared an all-hands-on-deck, add-value-where-you-can, succeed-at-all-costs attitude that created an invigorating environment to work in. My principal mentor was a MicroKid from The Soul of a New Machine from whom I learned a great, great deal (and still do!). Thanks to his guidance and support I got to "touch" nearly every part of the system and felt encouraged to continuously take on new challenges. To this day I still recall the feeling of endless possibilities and excitement of knowing that my skills were improving daily.

Truly a lucky way to start my career.

UPDATE

To clarify this post, I decided to add a simplified diagram of the system's architecture. The actual architecture was more complicated, for example some of the ASICs depicted were actually multiple devices, but the diagram should sufficiently convey the overall design.

C Bitfields and HW Registers

2009-10-28T19:18:00.002-04:00

When I need a quick low-level programming "fix", I browse the archives at PageTable.com. Last week I read the post on Readable and Maintainable Bitfields in C which argued the merits of using bitfields over bitmasks+macros. Although I agree with the post's points I think it omitted one important detail - the danger of using bitfields with hardware registers.

Hardware registers can be mapped into a processor's memory space and accessed with standard memory read/write instructions. Therefore the temptation is to define a bitfield type representing a register's structure and set a pointer to its base memory address. For example, assuming register bar is four bytes wide, has five bit-fields, and is located at memory address 0xBAADF00D one might be tempted to do the following:

typedef struct {
    unsigned int f1:8;
    unsigned int f2:4;
    unsigned int f3:8;
    unsigned int f4:4;
    unsigned int f5:8;
  } registerBar_t;


// Set pointer to register's memory address
registerBar_t *pBar = 0xBAADF00D;

// Use pointer to access register
pBar->f1 = 0xFE;

One problem with this approach is that many registers are designed to be accessed only at their full size - all accesses must be aligned to the register's base address and read/write the whole thing. Unfortunately, the setting of f1 in the above example may produce a partial register write that can lead to unexpected and unintended results.

Another challenge when dealing with registers is that, unlike main memory, register accesses can have side effects. Even register reads can cause the hardware to initiate action or clear information. Consider the following example:

...
tmpf1 = pBar->f1;
tmpf2 = pBar->f2;
...

If reads of register bar are destructive causing its contents to be cleared then the read of f1 may clear the contents of f2 before it is read by the subsequent pointer dereference. The resulting loss of information could cause the driver, hardware, or both to behave unexpectedly.

Alternatively, if reads of register bar cause the hardware to initiate action then spurious activity may occur if the f1 and f2 accesses are done separately.

Because of these granularity and side effect issues, I was advised early in my career to avoid using bitfields with hardware registers. This is, I think, an important point that is captured in the PageTable.com post's comments but not in the post itself which is an unfortunate omission.

After reading the PageTable.com post, I realized that I always took this advice on faith and never looked at the instructions generated by bitfield accesses. So I decided to do a quick experiment, below is a short program that accesses a bitfield with fields of varying size and alignment.

#include <stdio.h>

typedef union {
  struct {
    unsigned int f1:8; // Bits 07:00
    unsigned int f2:4; // Bits 11:08
    unsigned int f3:8; // Bits 19:12
    unsigned int f4:4; // Bits 23:20
    unsigned int f5:8; // Bits 31:24
  };
  unsigned int raw;
} bitfield_t;


int main()
{
  bitfield_t bitfield;
  unsigned int tmp;

  bitfield.raw = 0x0;

  // Set bit field f1
  bitfield.f1 = 0xEF;
  tmp = bitfield.f1;
  printf(" After f1: F1(0x%02x) RAW(0x%08x)\n", 
         tmp,
         bitfield.raw);

  // Set bit field f2
  bitfield.f2 = 0xE;
  tmp = bitfield.f2;
  printf(" After f2: F2(0x%02x) RAW(0x%08x)\n", 
         tmp,
         bitfield.raw);

  // Set bit field f3
  bitfield.f3 = 0xDB;
  tmp = bitfield.f3;
  printf(" After f3: F3(0x%02x) RAW(0x%08x)\n", 
         tmp,
         bitfield.raw);

  // Set bit field f4
  bitfield.f4 = 0xA;
  tmp = bitfield.f4;
  printf(" After f4: F4(0x%02x) RAW(0x%08x)\n", 
         tmp,
         bitfield.raw);

  // Set bit field f5
  bitfield.f5 = 0xDE;
  tmp = bitfield.f5;
  printf(" After f5: F5(0x%02x) RAW(0x%08x)\n", 
         tmp,
         bitfield.raw);

  // Set with raw
  bitfield.raw = 0xDECAFBAD;
  tmp = bitfield.raw;
  printf("After raw: RAW(0x%08x)\n", 
         tmp);

  return 0;
}

Compiling and running this program on an Ubuntu system results in the expected output.

jcardent@ubuntu:~/tmp$ gcc -g -o foo foo.c 
jcardent@ubuntu:~/tmp$ ./foo 
 After f1: F1(0xef) RAW(0x000000ef)
 After f2: F2(0x0e) RAW(0x00000eef)
 After f3: F3(0xdb) RAW(0x000dbeef)
 After f4: F4(0x0a) RAW(0x00adbeef)
 After f5: F5(0xde) RAW(0xdeadbeef)
After raw: RAW(0xdecafbad)

Running the command

jcardent@ubuntu:~/tmp$ objdump -d -S foo

reveals the instructions generated to access the bit-fields. Looking at the f1 write and read sequence shows:

  // Set bit field f1
  bitfield.f1 = 0xEF;
 80483dc:       c6 45 f8 ef        movb   $0xef,-0x8(%ebp)
  tmp = bitfield.f1;
 80483e0:       0f b6 45 f8        movzbl -0x8(%ebp),%eax
 80483e4:       0f b6 c0           movzbl %al,%eax
 80483e7:       89 45 f4           mov    %eax,-0xc(%ebp)

The first thing to note from this disassembly fragment is that bitfield is located on the stack eight bytes below %ebp. Likewise, tmp is located at offset 0xC.

From this example it's clear that the write to f1 uses a single byte move instruction. If bitfield had been mapped to a hardware register, this would have resulted in an aligned but too short write access that could have produced unintended behavior.

The read of f1 is less clear until the movzbl instruction is understood to be a move from a single byte to a word, four bytes in this case. So here again, if bitfield had been mapped to a register the single-byte access may have resulted in unintended behavior like dataloss (top three bytes cleared) or spurious action (if subsequent reads are done to other fields for the same operation).

Looking at the f2 write and read sequence shows:

 // Set bit field f2
  bitfield.f2 = 0xE;
 8048404:       0f b6 45 f9        movzbl -0x7(%ebp),%eax
 8048408:       83 e0 f0           and    $0xfffffff0,%eax
 804840b:       83 c8 0e           or     $0xe,%eax
 804840e:       88 45 f9           mov    %al,-0x7(%ebp)
  tmp = bitfield.f2;
 8048411:       0f b6 45 f9        movzbl -0x7(%ebp),%eax
 8048415:       83 e0 0f           and    $0xf,%eax
 8048418:       0f b6 c0           movzbl %al,%eax
 804841b:       89 45 f4           mov    %eax,-0xc(%ebp)

In this case, setting the four bit-wide field f2 results in a byte-wide read-modify-write sequence aligned with the second byte of bitfield, evidenced by the offset of 0x7 instead of 0x8. Similarly, reading f2 results in a byte-wide read aligned with the second byte of bitfield. Both accesses are too short and misaligned.

Since f3 spans bytes 2 and 3 of bitfield, its access sequence results in aligned, four byte-wide mov instructions.

  bitfield.f3 = 0xDB;
 8048438:       8b 45 f8           mov    -0x8(%ebp),%eax
 804843b:       25 ff 0f f0 ff     and    $0xfff00fff,%eax
 8048440:       0d 00 b0 0d 00     or     $0xdb000,%eax
 8048445:       89 45 f8           mov    %eax,-0x8(%ebp)
  tmp = bitfield.f3;
 8048448:       8b 45 f8           mov    -0x8(%ebp),%eax
 804844b:       c1 e8 0c           shr    $0xc,%eax
 804844e:       80 e4 ff           and    $0xff,%ah
 8048451:       0f b6 c0           movzbl %al,%eax
 8048454:       89 45 f4           mov    %eax,-0xc(%ebp)

Although the accesses themselves are well-formed, unintended behaviors can still result if f3 is only one of multiple fields that must be set for a single operation.

Since the structure of bitfield is symmetrical, the accesses to fields f4 and f5 produce instructions similar to those for f2 and f1 respectively albeit with different offsets.

Finally, the accesses to raw produce aligned, full-width instructions as expected.

  // Set with raw
  bitfield.raw = 0xDECAFBAD;
 80484cd:       c7 45 f8 ad fb ca de movl   $0xdecafbad,-0x8(%ebp)
  tmp = bitfield.raw;
 80484d4:       8b 45 f8           mov    -0x8(%ebp),%eax
 80484d7:       89 45 f4           mov    %eax,-0xc(%ebp)

This last example illustrates a tempting workaround for "safely" using bitfields to manage register accesses. Consider:

registerBar_t *pBar = 0xBAADF00D;
registerBar_t tmpBar;

// Set field f1 to 0xff
tmpBar.raw = pBar->raw;
tmpBar.f1  = 0xff;
pBar->raw  = tmpBar.raw;

While this approach works, it suffers the risk of an uninformed future maintainer "optimizing out" the temporary variable and just using the bitfield method directly. In this regard, it may be more maintainable to use bitmasks and macros for register accesses.

Of course, problems can arise regardless of the method used if "uninformed" developers are allowed to change the code. The only prevention here is to make sure there is suitable training and disciplined code reviews.

Book Review: Coders At Work

2009-10-22T05:52:00.001-04:00

Coders At Work: Reflections on the Craft of Programming by Peter Seibel

I really enjoyed this book. Peter Seibel did an outstanding job in selecting a group of interviewees that are both legendary and represent a wide range of programming domains. In addition, Peter's questions were similar enough to allow comparisons between responses but maintained a conversational flow that prevented the interviews from feeling formulaic. Ehud Lamm's quote from the font cover perhaps says it best, "reading this book may be the next best thing to chatting with these illustrious programmers in person".

I read the interviews out of order based on my interests. All were good but my favorite ones were (in no particular order):

One striking observation was how many of the interviewees fit into Malcolm Gladwell's definition of an Outlier. Nearly all of them had opportunities to get a significant amount of programming experience at a young age and serendipitously found jobs that provided the right environment for them to succeed.

I also found interesting the "organic" approach most of the interviewees took to programming. None seemed to rely on formalized best practices but instead used their intuition to tailor their approach based on the task at hand. To me this suggests that you just can't codify great programming which matches my experiences with the great programmers that I have known.

Finally, it's notable how many of the people interviewed either starting out hacking Lisp or were heavily influenced by it. Of course this may be due to selection bias given that the author, Peter Seibel, is a a Lisp hacker himself and wrote the outstanding book Practical Common Lisp. As a Lisp fan, I don't mind the potential bias; it's a feature, not a bug!

Favorite Innovation Resources

2009-10-14T06:54:00.002-04:00

My company's annual innovation conference is today and I'll be participating in a panel of innovators. As a result, innovation is on my mind so I thought I would post my favorite innovation resources. Unfortunately, this is only a quick list of links as I don't have time to discuss in detail what I like about each resource. Perhaps this will be a theme for a future series of posts.

Innovation

The Innovator's Solution: sequel to The Innovator's Dilemma, I prefer this book as it discusses many secondary factors related to disruption and how to avoid it. Key points to me were transitions between tightly-integrated and modular architectures and avoiding products that are incremental innovations for incumbents.
Drucker's Innovation and Entrepreneurship: simply a great book that should be required reading for every innovator, entrepreneur, and executive manager. Based on my years of experience as an innovator within a large company I found Drucker's insights and advice to be relevant, pragmatic, and actionable. Given its publication date, it appears to me that this book served as the foundation for the "popular" innovation books of the 90's and beyond. Reading Drucker's book helped to provide more context for those later works. This book is well worth the time to read it.
The Doblin Group's Ten Types of Innovation: a great cheat-sheet summarizing the various forms of innovation. I have this hanging on my office wall at work.
Skate to Where the Money Will Be: perhaps one of the most important papers for any innovator to read, especially those involved in long term strategic planning for an established company.
Creating New Market Space: a great HBS article on systematic ways of identifying new market opportunities.
What is a Strategy: to some degree innovating is deeply tied to defining a strategy. As a result, it's important to understand what a strategy is and Porter is a leading thinker in this area.
The Myths of Innovation: a thought provoking book that dispels some of the myths surrounding innovation.
Serious Play: a decent book that makes the important point that sometimes a model or prototype is needed to serve as the catalyst and focal point for exploratory innovation. I've spent most of my engineering career building prototypes so I found this book to be a thoughtful resource.
The Power of Product Platforms: written by one of my MBA professors, this book introduces the concept of using modular architectures to build derivative products to serve different market segments. A powerful concept in my experience.
Eureka! It Really Takes Years of Hard Work: a nice New York Times article discussing the fact that innovation is often the result of a lot of hard work and not an instantaneous eureka moment.

Execution

Crossing the Chasm: Geoffrey Moore's classic book about making the transition from the early to mainstream markets. A lot of great advice for innovators.
Dealing with Darwin: another Moore classic, this one discusses how to structure an organization to maintain a pipeline of innovations and sustain corporate growth. A good read for anyone involved in maintaining an established business.
That Art of the Start: a great and inspiring book on starting a new venture. I particularly appreciated the no nonsense advice and strong focus on fundamentals. My bias towards the latter has always made me feel like a "pseudo-MBA" so Guy's advice increased my confidence in my own opinions in this area.

Creative Problem Solving

ThinkerToys: a great resource for creative thinking techniques.
Back of the Napkin: sometimes a whiteboard or pen+paper are the most powerful tools for communicating ideas and innovations. This book provides great tips on visual thinking and communication.
The Mind Map Book: I have found mind-mapping to be a very effective and powerful technique for creative thinking. Written by the one of the original proponents of mind-mapping, this is a good resource for learning how to create and use mind-maps.
How to think Like Einstein: despite the cheeky title this book contains useful tips on creative thinking.
How to Think Like Leonardo Da Vinci: same as the above, cheeky title but good advice.

As I mentioned, this is just a short list of the resources that I've found most useful. In future posts I may discuss these and other resources in more detail.

Book Review: Fortune's Formula

2009-10-09T05:41:00.001-04:00

Fortune's Formula: The Untold Story of the Scientific Betting System that Beat the Casinos and Wall Street by William Poundstone

[Read in August of 2009 but was delayed in writing the review.]

I absolutely loved this book, in fact I more or less devoured it as it involved three topics that I find very interesting:

Computing history
Information Theory
Investing & Quantitative Finance

How can a book involving these three topics be anything but good!

OK, enough gushing, the book is essentially about the following three people:

Claude Shannon: Bell Labs super-genius most famous for creating the field of Information Theory but who also invented the use of boolean binary logic in digital computers, and made material contributions to the fields of Mendelian genetics, cryptography, and computational logistics.
John L. Kelley: Bell Labs scientist famous amongst geeks for programming an IBM 704 to sing the song Daisy Bell which inspired HAL-9000's song at the end of the movie 2001: A Space Odyssey. Kelly is also famous for using Shannon's Information Theory to create the Kelly Criterion method for optimal betting or investing given inside information.
Edward O. Thorpe: M.I.T. professor famous for writing the book Beat the Dealer which proved card counting could be used to win at Black Jack. Thorpe is also famous for pioneering the use of computers in hedge fund investing (a.k.a quantitative finance). Thorpe's fund, Princeton Newport Partners, achieved an impressive annualized return of 15.1% over its 19 year duration.

The story more or less goes thusly:

Shannon invents Information Theory
With Shannon's help Kelley uses Information Theory to create the Kelly Criterion for determining an optimal betting strategy given inside information.
After meeting at M.I.T., Shannon and Thorpe research ways of using wearable computers to win at roulette. Thorpe goes on to use the Kelly Criteria to first make optimal bets while card counting and later make profitable investments for his hedge fund.

The book focuses on how the interaction between these three men gave rise to much wealth. Along the way Poundstone discusses related topics such as Efficient Market Theory, the Random Walk Hypothesis, and statistical arbitrage. Poundstone includes just enough mathematics to make the story interesting to technical readers without alienating other audiences.

It must be noted that the book offers a much richer story including the influences of organized crime at various stages of history.

All in all, a great book that I highly recommend to anyone interested in these topics.

Book Review: Labyrinths of Reason

2009-10-09T05:38:00.001-04:00

[Read in August of 2009 but was delayed in writing the review.]

Labyrinths of Reason: paradox, puzzles, and the frailty of knowledge by William Poundstone.

Ouch, my head hurts. How do we really know we're not just brains-in-vats living in a simulated reality?

This is more or less the central theme of the book which guides the reader through various thought experiments designed to probe the depths of meaning, understanding, and knowing. Along the way Poundstone discusses various topics such as:

Deductive and inductive reasoning
Counterfactuals
Poincare's universe doubling riddle
Complexity Theory and Satisfiability
Computability Theory and NP-Completeness

I could go on but doing so would still do the book an injustice. It's a great book that covers a lot of interesting topics. Well worth reading if you are interested in these kinds of things but be prepared to get a few headaches from excessive thinking. I'm planning to re-read it perhaps a year from now to try to better absorb the material.

Book Review: Prisoner's Dilemma

2009-10-09T05:06:00.000-04:00

[Read in August of 2009 but was delayed in writing the review.]

Prisoner's Dilemma: John Von Neumann, Game Theory, and the Puzzle of the Bomb by William Poundstone.

A book ostensibly about Game Theory, I felt that it was more of a montage of:

Game Theory
A biography of John Von Neumann
A history of the RAND Corporation and cold war

The Game Theory content was fascinating and informative covering various kinds of games, strategies, and complications stemming from repeated games. Good stuff.

I found the Von Neumann biography captivating as it provided a deeper insight into his personal nature than I had read before. Clearly he was an incredibly intelligent man but he also clearly had a number of personal challenges. While this material makes Von Neumann appear more "human", it's not particularly pleasant to read about. Also, I thought the account of his death from cancer was too detailed and grim.

Personally, I have no interest in the history of the RAND corporation or the cold war so I found these parts of the book difficult to get through. But others may find this material more interesting.

All in all, not a bad book if you're interested in these topics but I wouldn't recommend this for "feel good" reading.

Book Review: Complexity

2009-09-27T16:28:00.002-04:00

Complexity: A Guided Tour by Melanie Mitchell

[Read in July of 2009 but was delayed in writing the review.]

I came across this book during a bookstore trip and decided to purchase it as it included topics related to a couple of recent posts and previously read book, Linked: The New Science of Networks. I'm glad I did as it made me realize that many of the things that I am interested in fall under the domain of Complex Systems.

The book is structured as five parts and nineteen chapters as summarized below:

PART	CHAPTER	THEME
1		BACKGROUND AND HISTORY
	1	What is Complexity?
	2	Dynamics, Chaos, and Prediction
	3	Information
	4	Computation
	5	Evolution
	6	Genetics, Simplified
	7	Defining and Measuring Complexity
2		LIFE AND EVOLUTION IN COMPUTERS
	8	Self-Reproducing Computer Programs
	9	Genetic Algorithms
3		COMPUTATION WRIT LARGE
	10	Cellular Automata, Life, and the Universe
	11	Computing with Particles
	12	Information Processing in Living Systems
	13	How to Make Analogies (if You Are a Computer)
	14	Prospects of Computer Modeling
4		NETWORK THINKING
	15	The Science of Networks
	16	Applying Network Science to Real-World Networks
	17	The Mystery of Scaling
	18	Evolution, Complexified
5		CONCLUSION
	19	The Past and Future of the Sciences of Complexity

Part 1, nearly a third of the entire book, provides a thorough introduction to Complex Systems which are defined by the author as having the following properties:

Complex collective behavior (i.e. the whole is greater than the sum of the parts)
Signaling and information processing
Adaptation to environmental changes

Example complex systems cited were insect colonies, the brain, the immune system, economies, and the world wide web.

Chapter 2 was an enjoyable introduction to dynamical systems and chaos theory which I had only a cursory awareness of. The simple "rabbit population" example using logistic maps was a great aid in understanding the concepts of fixed/periodic/strange attractors, and a sensitive dependence on initial conditions (aka. the Butterfly Effect). New to me were the concepts of the period doubling route to chaos and Feigenbaum's Constant (which is just plain odd).

Chapters 3 and 4 covered concepts related to information and computation including: entropy, Maxwell's Demon, statistical mechanics, Shannon's information theory, Hilbert's problems, Godel's incompletness theorem, and Turing machines. Overall the treatment was good and a sufficient introduction for readers unfamiliar with these concepts.

Chapters 5 and 6 discussed the topics of evolution and genetics. I found the discussion on evolution interesting as I don't recall learning about the feud between the early Darwinians, who believed in continuous small variations, and Mendelians, who believed in discrete large variations. I also don't recall learning about the Modern Synthesis or the continued challenges in the form of punctuated equilibrium. Interesting stuff.

Chapter 7 discussed various ways of defining and measuring complexity as:

size
entropy
algorithmic information content
logical depth
thermodynamic depth
computatoinal capacity
statistical complexity
fractal dimension
degree of hierarchy

While no single measure was identified as the measure, all were interesting to consider.

Chapters 8 to 10 discussed cellular automata, genetic algorithms, and artificial life. While the treatment was good, it felt light-weight after having just read The Recursive Universe. That said, Chapter 10 did provide a nice overview of Wolfram's work on cellular automata that augmented the prior material I had read on this subject.

Chapter 11 discussed the use of cellular automata for majority classification tasks. The specific task discussed was the determination of the dominant color in a one-dimensional vector of white and black pixels. The authors used genetic algorithms to evolve a set of CA rules that reliably performed this task by creating diagonal vectors that carried local majority-voting decisions which eventually intersected to produce a majority-vote for the entire original vector. The authors seemed unable to at first understand how the evolved CA worked but I thought it obvious as clearly any solution must involve the horizontal communication of local-majority votes in order to reach a global decision. It seems obvious (to me) that such horizontal communication would manifest as diagonal vectors when the CA evolutions are graphed vertically. I thought the use of particle equations to explain the phenomina was overkill but still interesting.

I enjoyed the author's account in Chapter 13 of her work on the CopyCat program which was designed to process analogies. The problem appears hard and the program was quite clever. I must admit I am extermely jealous that she got to work so closely with Douglas Hofstadter.

Chapters 15 to 16 discussed real-world network theory which included topics such as small-world phenomina, scale-free networks, clustering, preferential association, and network resiliance. Overall the treatment was good but mostly a review after having just read (actually listened to) Barabasi's book Linked, which I highly recommend reading.

Chapters 17 and 18 discussed network theory in the contexts of metabolic scaling and evolution which was very interesting. Some of this material was a review of Stuart Kauffman's work documented in his book Origins of Order. I previously read another of Kauffman's books, At Home in the Universe, which touched on some of the same topics but perhaps I'll add Origins to the list of potential future readings.

Chapter 19 concluded the book with an overview of the state of complexity science and the need for a unifying theory. While the field has accomplished many great things, it appears that a lot of difficult work remains which is perhaps why this is such an appealing topic.

In summary, Complexity is a great book that covers a lot of interesting topics. On a personal level, I am thankful to have read this book because, as I mentioned, it helped me realize that complexity science is the meta-topic that unifies many of my long term interests and therefore serves a guide for future research.

The Case of the Bloated Firmware

2009-09-24T18:24:00.002-04:00

A few years ago, a co-worker of mine was working on an embedded micro-controller for a proprietary enterprise class motherboard. I don't recall the exact details but my recollection is that the micro-controller was responsible for monitoring a group of sensors and reporting any anomalies.

My friend used a commercial C compiler to develop the code for the micro-controller which compiled fine but resulted in a binary that was too large for the device's EPROM. He tried a number of things to reduce the binary's size but was unable to get the code to fit. During a serendipitous hallway conversation he asked if I could take a look at the problem and we returned to his cube on a mission to shrink the binary.

First, he walked me through the source code to explain the overall purpose and design. At the C level the code looked fine so we next took a look at the disassembled binary and found our first clue - one of the for loops seemed to generate an excessive amount of instructions. Strange.

Again, the exact details escape me but the code in question looked roughly as follows:

 1:  int value1[NUM_SENSORS];
 2:  int value2[NUM_SENSORS];
 3:  int value3[NUM_SENSORS];
 4:  
 5:  for(sensor_num= 0; sensor_num < NUM_SENSORS; sensor_num++) {
 6:  
 7:    value1[sensor_num] = readSensorValue1(sensor_num);
 8:    value2[sensor_num] = readSensorValue2(sensor_num);
 9:    value3[sensor_num] = readSensorValue3(sensor_num);
10:  }

What we observed was that each of the array references resulted in a lot of instructions to compute the specified element's memory address. Since the loop body included three references, it generated a lot of instructions. Matters were made worse by the fact that there were multiple loops of this kind in the code. We found our culprit.

To work around the problem, I suggested that he re-write the code as follows:

 1:  struct {
 2:    int value1;
 3:    int value2;
 4:    int value3;
 5:  } sensors[NUM_SENSORS];
 6:  
 7:  for(sensor_num= 0; sensor_num < NUM_SENSORS; sensor_num++) {
 8:  
 9:    sensors[sensor_num].value1 = readSensorValue1(sensor_num);
10:    sensors[sensor_num].value2 = readSensorValue2(sensor_num);
11:    sensors[sensor_num].value3 = readSensorValue3(sensor_num);
12:  }

We changed the loops, recompiled the code, and presto chango the binary was small enough to fit!

A quick look at the disassembly confirmed my hypothesis that writing the code as proposed would result in only a single array element address calculation in the loop body - the address of each structure member was just an offset from the array element's starting address. The array element address calculations were still inefficient but we had reduced their number enough for the binary to fit within the device's EPROM. Success!

Overall, this wasn't a particularly difficult problem and didn't take that much time to resolve. However, the necessity to imagine how the compiler would respond to restructuring the code made this a fun, and memorable "bug" to work on.

Dan Weinreb Talk at Google

2009-09-24T06:08:00.001-04:00

In August, Dan Weinreb gave an interesting talk at Google on ITA Software's high-performance transaction system for airline ticket searching and pricing. ITA's software serves as the foundation for more well known travel pricing services like Orbitz who is an ITA customer. The problem ITA attempts to solve is extremely complex as explained in this slideument by Carl de Marken.

Amongst the Lisp community, ITA is famous for the signficant use of Lisp in their system, hiring well-known Lisp hackers, and using programming puzzles to filter job applicants.

Given my deep interest in all things Lisp (programming, lisp-machines, A.I., etc), Dan's blog is one of my favorite websites and someday I hope to meet him at a Boston Lisp Users meeting (if I can ever make it to one again).

Nice talk and worth watching if you're interested in this kind of thing.

The Case of the Replayed Queue

2009-09-23T06:22:00.001-04:00

A number of years ago, I wrote a Linux device driver for a host bus adapter (HBA). The interface to the HBA consisted of two circular buffers, one to send information to the HBA (TxQ) and another to receive information from the HBA (RxQ). In this particular project, the HBAs were being used in a non-standard way to implement a bi-directional communication link between two Linux systems. As a result, the driver sent both commands and responses via the TxQ and received both commands and responses via the RxQ. In both cases, the driver communicated with the HBA using fixed-size data structures called IO control blocks (IOCBs).

Another aspect of this non-traditional use of the HBAs was that a proprietary upper layer protocol was used instead of the standard protocol used with the HBA. In this case, the protocol command packets did not fit within a single IOCB. As a result, two IOCBs were needed to send and receive command packets between the driver and HBA. These IOCB pairs were required to be adjacent in the circular buffers.

As the project reached the beta-testing phase, a perplexing driver bug began manifesting during QA testing. The failure was extremely rare happening only once a day while under heavy load. Unfortunately, the unit-test I had created to test the driver ex-situ continued to run without error so the problem was only occurring in-situ in QA'a full system configuration and under their heavy load. Oh bother.

Faced with a difficult bug and a nearing deadline I got straight to work on figuring out the problem. To start, I reviewed the QA logs to determine a pattern to the failures. The evidence suggested that the driver was re-processing protocol packets that had already been handled. To me this indicated a potential problem with the RxQ circular buffer but a code-review didn't reveal any obvious bugs.

I proceeded on to debugging the driver in-situ. Unfortunately, for reasons that I can't recall, I had little success using a kernel debugger. As a result, I initially tried to use print statements but the verbose system messages generated by the failure caused the information to immediately scroll off the screen. I tried sending debug information out a serial port but this slowed the system down enough to significantly increase the time between failures beyond practicality. Hmph.

After a week of frustration and an increasing pressure from the team to resolve the bug, I decided to take a fresh view of the problem. First, I considered what could cause the driver to replay the RxQ and quickly concluded that erroneously putting the tail-pointer past the head-pointer could cause the problem. A quick review of the head-tail pointer management code didn't reveal any mistakes. Hmph.

Next, I considered how the head-tail pointer code could be tricked into putting the tail pointer beyond the head. I reasoned that one way this could happen was if the driver thought the contents of the circular buffer were longer than its actual size. If this were the case, then when the driver updated the tail pointer it would put it past the head which would erroneously make the circular appear full when the driver re-examined it. But what could make the driver think that the buffer contents were longer than they actually were?

After some deep pondering the problem hit me, it must those multi-IOCB commands! My thought was that if for some reason the second of the two IOCBs wasn't posted to the queue when the driver processed it and if the driver didn't check for this condition, that the driver would adjust the tail pointer as if the second IOCB was present which would put it after the head pointer. The timing window for this seemed to be impossibly small but the failure was taking a day to manifest under heavy load so it had to be a rare sequence of events. If there is one thing that I have learned from my years working on large-scale parallel computer systems it's that highly improbably events occur far more frequently than one suspects.

I checked the code and confirmed that I had failed to account for incomplete multi-IOCBs. I added the necessary guards to the code, gave a new binary to QA, and crossed my fingers. A few days later success was declared and from then on the driver performed without error.

I never figured out why the HBA was delayed in posting the second half of the protocol command IOCBs to the RxQ. But you can be sure that I'll never forget to check for circular buffer fragments again!

The Case of the Errant DMA

2009-09-19T04:04:00.000-04:00

The C++ puzzle that I posted about the other day got me thinking of various bugs that I've helped root-cause in the past. I thought it would be fun to post about some of the most memorable ones as a series of posts tagged as BugHunts.

About a year ago, a programmer that I was mentoring ran into a problem with errant DMAs in a ATA device driver that he was writing for a proprietary operating system (mostly as a training exercise). Said programmer did his initial development in a virtualized environment (i.e. virtual machine running on a hypervisor) and the device driver worked just fine. However, when run on a real platform the second and subsequent DMA operations would access "random" memory locations instead of those specified in the supplied scatter-gather lists.

After confirming that the basic scatter-gather code was working properly, the developer asked if I could help identify the problem. I started off by asking him to walk me through how the DMA operations were supposed to occur. Next, we walked through the code to ensure that it matched his description. Not seeing any obvious bugs, we then proceeded on to running the code, breaking into the debugger, and inspecting the scatter-gather lists to make sure that they contained the correct source/destination addresses. We observed the first DMA operation, which always worked, and the subsequent operations, which always failed, but saw no differences between the two. Humph.

At this point, I suggested that we focus on the fact that the first operation always succeeded but the subsequent operations always failed. I asserted that there must be a difference between how the first and subsequent operations were set up. So again we inspected the code and watched the execution in the debugger but didn't see any differences. Double humph.

After some thought, I then hypothesized that perhaps the first DMA operation was unexpectedly altering settings that were setup during the device driver's initialization. Since these setup operations were performed outside of the DMA setup code, we wouldn't observe any execution differences between the first and subsequent operations. So again we walked through the DMA operation but this time considered the additional configuration settings that they depended on. Bingo.

The chipset in question used a memory resident scatter-gather list. Since only a single DMA operation was outstanding at any time (per ATA channel) the developer pre-allocated the memory region during the device driver's initialization and wrote the region's base address to the appropriate chipset register. Since the same memory region was re-used to hold the scatter-gather list for each operation, the developer didn't re-write the base address to the register for each operation.

It turned out that on the virtualized platform the emulated ATA chipset left this register unchanged between operations, hence the device driver worked fine. However, on the real platform the chipset modified the register to point to the active scatter-gather element as the DMA operation was performed. As a result, the first DMA operation completed OK while all subsequent DMA operations walked off the end of the scatter-gather table and misdirected the DMA accesses based on the random data present in memory above the scatter-gather table. Once the developer added the code to re-initialize the scatter-gather base address register for each operation everything worked fine.

After the bug was fixed, the developer stated that he found this behavior surprising. I explained that having worked on designing ASICs in the past, I wasn't at all surprised that the hardware reused the register to hold the address of each scatter-gather element as the operation progressed; all's fair in ASIC design when it means saving some gates!

He then wondered how he could find such bugs in the future without having similar low-level hardware experience. I told him that the important lesson from the exercise was that once the possible errors have been ruled out you need to suspend disbelief and begin considering the impossible errors. Often our understanding of complicated systems is incomplete or flawed, therefore things we assume to be impossible may in fact be possible and therefore must be considered. I explained that this is a skill that must be hard-won over time through solving progressively harder bugs. I encouraged him to seek out hard bugs, spend time trying to resolve them on his own, but if stuck to utilize the already hard-won experiences of his mentors to accelerate his own skill development. This is the advice that has worked for me during my career and I am confident that the developer in question will do just fine.

Anyway, this particular bug was fun because it required thinking about how the system affected the program rather than how the program affected the system. These kinds of puzzles are always fun… after you've figured out the problem that is.

Fun C++ Problem

2009-09-16T11:37:00.008-04:00

Today a co-worker of mine ran into an interesting C++ inheritance problem that perplexed the usual lunch crowd. Some might call this a character flaw, but when presented with puzzles like this I feel compelled to figure them out. So, when I got back to my desk I reduced the problem to the following minimal program and got to work on figuring out the root-cause.

 1:  class Superclass
 2:  {
 3:  public:
 4:    void  foo(int aParameter);
 5:    void  foo(int  oneParameter,
 6:              int  twoParameter);
 7:  };
 8:  
 9:  class Subclass : public Superclass
10:  {
11:    void  foo(int aParameter);
12:    // inherits foo(int, int)
13:  };
14:  
15:  void Superclass::foo(int aParameter)
16:  {}
17:  
18:  void Superclass::foo(int  oneParameter,
19:                       int  twoParameter)
20:  {}
21:  
22:  void Subclass::foo(int aParameter)
23:  {
24:    foo(aParameter, 2);
25:  }
26:  
27:  int main(int argc, char * argv[])
28:  {
29:    return (0);
30:  }

In words, there is a super-class, Superclass, with an overloaded method, foo(), that has two variants - foo(int) and foo(int,int). In addition, there is a sub-class, Subclass, derived from Superclass that redefines the foo(int) variant but inherits Superclass's foo(int,int) method.

Straight forward, right? Nope.

$g++ borked.cpp 
borked.cpp: In member function ‘void Subclass::foo(int)’:
borked.cpp:26: error: no matching function for call to ‘Subclass::foo(int&, int)’
borked.cpp:24: note: candidates are: void Subclass::foo(int)

For some reason the compiler isn't able to resolve the call to the inherited foo(int,int) when called from Subclass's foo(int) method. How strange.

Commenting out the offending call on line 24 allows the program to compile and dumping the symbol table yields the expected results:

$nm a.out
0000000100000ea4 s  stub helpers
0000000100001048 D _NXArgc
0000000100001050 D _NXArgv
0000000100000e60 T __ZN10Superclass3fooEi
0000000100000e6e T __ZN10Superclass3fooEii
0000000100000e7e T __ZN8Subclass3fooEi
                 U ___gxx_personality_v0
0000000100001060 D ___progname
0000000100000000 A __mh_execute_header
0000000100001058 D _environ
                 U _exit
0000000100000e8b T _main
0000000100001020 s _pvars
                 U dyld_stub_binder
0000000100000e24 T start

All the methods are present and have unique signatures. Recompiling with the -fdump-class-hierachy option also doesn't produce any suprises - there is no vtable magic going on.

$g++ -fdump-class-hierarchy borked.cpp
$cat borked.cpp.002t.class 
Class Superclass
   size=1 align=1
   base size=0 base align=1
Superclass (0x1407c18c0) 0 empty

Class Subclass
   size=1 align=1
   base size=1 base align=1
Subclass (0x1407c1930) 0 empty
  Superclass (0x1407c19a0) 0 empty

As a final piece of the puzzle, fully qualifying the call to foo(int,int) as follows resolves the problem.

void Subclass::foo(int aParameter)
{
  Superclass::foo(aParameter, 2);
}

Now, I am no C++ guru but I do have a fair amount of experience with it - mostly from writing system level code for a proprietary RTOS that was written in C++. In fact, I wrote a loadable module framework for that RTOS that included a runtime dynamic linker capable of handling C++ intermediate object files. So, I'd like to think I have a decent knowledge of the C++ object model and yet this problem made little sense to me.

As is often the case, I didn't know the anwser to the problem but I did know enough to determine the right keywords to Google for the answer. The solution is to add a using declaration to the Sublcass's definition.

class Subclass : public Superclass
{
  using Superclass::foo;

  void  foo(int aParameter);
  // inherits foo(int, int)
};

As I now understand the situation, when a set of overloaded methods span the base and derived classes, the using declaration is required to introduce the base class's methods into the scope of the derived class. Without the using declaration, the compiler can't resolve the reference to the base class's method without fully qualifying it. Good to know!

I had a lot of fun figuring this out despite the fact that it took 20 minutes of time out of an already busy day. But, sometimes you just have to let the inner-geek exercise itself!

As an aside, I recommend Stanley Lippman's book Inside the C++ Object Model to anyone interested in learning the inner workings of the C++ object model.

Nice Finance Video Collection

2009-09-15T18:53:00.002-04:00

While web-surfing I stumbled across a nice collection of YouTube videos by Bionic Turtle on statistics, finance, and quantitative finance.

The videos tend to be short (under ten minutes) which makes them convenient to watch. Also, the author effectively uses Excel to work through examples and highlight the key points.

So far, I've only watched a handful of these videos but I plan to work my way through them gradually with a priority towards the topics relevant for re-balancing and evaluating the performance of my portfolio.

An Algorithmic Trading Primer

2009-09-09T13:34:00.001-04:00

While I was getting my MBA I developed a strong interest in quantitative finance. I doubt I'll ever pursue a career in this field but I continue to enjoy reading about it in my spare time as part of a larger, general interest in applied mathematics (more about that in a future post).

Needless to say, I was eager to read the paper Algorithmic Trading: A Primer published in the summer 2009 issue of The Journal of Trading.

Unfortunately, I apparently misinterpreted the title as instead of discussing the algorithms themselves, the article covered the high-level points that clients of algorithmic trading firms should be aware of. To this end the article did cover some important points including:

The desire (nay need) for algorithms to increase trader productivity
The importance of Regulation NMS and why it favors electronic trading (which I must admit was new to me).
The basic framework of algorithmic trading systems such as performance benchmarks, assumptions, etc.
The rationale for and limitations of using log-normal models for price fluctuations.
The importance of avoiding trades that signal the market and may therefore invalidate the algorithm's model.
The importance of using the right algorithms at the right time to achieve the intended goals.

So, although the article didn't cover the topics I had initially hoped for I did find it a useful read anyway.

Book Review: Outliers

2009-09-05T07:46:00.000-04:00

Outliers by Malcolm Gladwell

An interesting book asserting that rather than just latent talent, an individual's success is do to:

timing: some people are born at just the right time to take advantage of historical watershed moments (e.g. the PC revolution) or age-based selections (e.g. birthday cut-offs for joining sports teams, schools, etc).
practice opportunities: Gladwell asserts that the "universal" requirement for achieving expertise is 10,000 hours of practice. Gladwell further asserts that successful individuals have often been given abnormal opportunities to obtain that amount of practice in a short period of time and at an early age.
environment: the amount of nurture and support that a person receives from his family and community has a significant effect on their success. This includes parents teaching their children how to be assertive, and actively guide their own lives.
culture: cultural values and behaviors can have a profound effect on an individual's level of success.

To some degree, Outliers reminded me of other recent readings:

In the Black Swan, Taleb asserted that individual success in "scalable" fields was due primarily to luck and a rich-get-richer effect. In Outliers I think Gladwell provides a compelling explanation for that phenomenon in his focus on lucky opportunities for obtaining expertise.
The StudyHacks blog ran a post on how one person successfully entered the music industry by selecting a single nightclub to perform at and then focused all their energy on becoming the best performer at that venue. To me this resonated strongly with Gladwell's assertion that opportunities for obtaining 10,000 hours of practice are one of the keys to success.

So, there appears to be supporting opinions for some of Gladwell's assertions. Personally, I suspect that he is on the right track.

I enjoyed the first half of the book but found the second halves multi-generational discussion weaker as I suspect a "lucky event" can be found in everyone's family history if you go back a few generations.

Being a computer geek, I enjoyed the brief biographies on both Bill Joy and Bill Gates. I had no idea that Gates had so much programming experience before going to college. By all appearances both Bills had rare opportunities to become expert programmers at just the right age to ride the PC technology wave.

Some of the excerpts that I dog-earned were:

Page 11: … the values of the world we inhabit and the people that we surround ourselves with have a profound effect on who we are.
Page 42: (regarding the assertion that 10,000 hours of practice are required to become an expert at any particular skill) … ten thousand hours is an enormous amount of time. It's all but impossible to reach that number all by yourself by the time you're a young adult. … In fact most people can only reach that number only if they get into some kind of special program … or if they get some kind of extraordinary opportunity that gives them the chance to put in those hours.
Page 149: Those three things - autonomy, complexity, and a connection between effort and reward - are, most people agree, the three qualities that work has to have if it is to be satisfying.
Page 267: … success follows a predictable course. It is not the brightest who succeed. … Nor is success simply the sum of decisions and efforts we make on our own behalf. It is, rather, a gift. Outliers are those who have been given opportunities - and who have had the strength and presence of mind to seize them.

Upon reflection, I reduced (perhaps too far?) the book's message down to the following three points:

Pick a meaningful skill and practice it as much as possible.
Maximize your exposure to opportunities that require the chosen skill to be successful and provide more practice.
Aggressively pursue the opportunities that you come across to extract the most value from them.

Over all a good book, and worth the time to read it.

The Netflix Culture

2009-08-29T18:19:00.001-04:00

The other day a co-worker sent me a link to a presentation from Netflix that describes their corporate culture. Well worth the twenty minutes required to read the slides.

I'm sure like many others, I found the described culture very attractive. I thought the desired values were so compelling that I printed out slide 19 and hung it up in my office as a reminder of my self-development goals. I think anyone in a creative profession, technical or otherwise, wants to work with "stunning" colleagues as a means for improving one's own skill. Too often I've seen loyalty appreciated more than performance so I liked the "adequate performance gets a generous severance package" rule. The guidelines designed to increase employee automaticity, decrease complexity, and minimize process strike me as recipes for success, provided that you have the suitable talent. Finally, I really liked the notion of always paying at the top-market rate. Frankly, the practice of reactively adjusting compensation to market rate when an employee tries to resign never made sense to me; why not pro-actively pay appropriately to avoid the employee from feeling unappreciated or being tempted by external opportunities?

Congratulations to Netflix for creating such a unique and outstanding corporate culture. It will be interesting to see if this culture persists as the company grows and the original staff moves on to other opportunities.

Crooked Crazy Eddie's

2009-08-25T08:45:00.006-04:00

One of my iconic memories from the 80's is the commercials for Crazy Eddie's, a NY-NJ-CN area consumer electronics store that claimed to offer "insane" prices. Since I grew up in RI, I had no direct experience with Crazy Eddie's and never knew what became of the company.

My ignorance came to an end upon listening to an interview of the company's former CFO in episode 82 of NPR's Planet Money podcast. Evidently, Crazy Eddie's was crooked!

The corruption began with skimming sales and tax revenues but progressed to full-fledged money laundering as the company's size grew and the amount of unreported money became considerable. As the CFO became more financially savy, he hit upon the clever and even more profitable idea of:

taking the company public
gradually bringing the skimmed monies back onto the books to artificially inflate revenues and profits which led Wall Street to overestimate the company's future growth and over-value the stock
selling the owner's majority equity position at the inflated market prices yielding over $100M of capital gains

What a story! In the end greed tore the family owned business apart which resulted in someone informing the authorities out of revenge thus bringing the whole operation to an end.

The podcast is very entertaining if you're interested in this kind of thing as the CFO seems to be proud of his cleverness despite its illegality. As it happens, he is now a consultant and instructor to various government agencies on the topic of corporate fraud. So much for the notion that crime doesn't pay.

Struggling with Book Reviews

2009-08-17T15:02:00.001-04:00

When I started this blog, I thought it would be a good idea to write book reviews as I finished readings. I've discovered two problems with this goal:

It takes a long time to write a worthwhile book review.
Due to the voracity of my reading appetite, I have been unable to delay starting a new book until I have finished writing a review for the previous book.

The result, I am now behind in writing two reviews and close to finishing a third book. So much for posting book reviews anywhere as frequently as Eli Bendersky.

I can think of five solutions:

Write shorter reviews.
Force myself to write reviews before starting a new book.
Only write reviews for selected books.
Don't worry about it and write reviews when the time permits.
Stop writing reviews.

Of these, only options 2 and 3 are acceptable. Part of my rational for writing reviews is to obtain a deeper understanding of the material through extended contemplation, review, and summarization. This motivation rules out options 1 and 5. Option 4 is more or less a formalization of the current situation which I already know isn't working; I'll just keep on reading and never get around to writing the reviews. This, again, leaves options 2 and 3.

So, going forward I will attempt a hybrid approach of:

Writing reviews before starting new books.
Only writing in-depth reviews of selected books which deserve the most reflection.

Hopefully this new approach will lead towards fulfilling my goal of getting more out of the books that I read.

Cool Commodore Hack

2009-08-05T16:22:00.002-04:00

Although I enjoy all of the content on the PageTable blog, I like the archeology stuff the most. This post about the hack used to do directory listings on the Commodore is a great example.

Essentially, the Commodore's disk drive acted as a co-processor handling all of the mass storage management and file system operations. The Commodore's kernel and BASIC shell used a file oriented API (i.e. open, close, read, write) to communicate with the floppy drive. Commands like list-directory were performed by an open() call to a special address and file name and reading the results from the open "file" until an EOF was received.

For reasons that are unclear from the post, it seems that the Commodore's kernel and BASIC shell were unable to natively perform the list-directory operation. As a result, a hack was needed to avoid users from having to write a BASIC program every time they wanted to list a directory.

The solution was for the floppy drive to return the directory listing in the format of a BASIC program. Thus, a list-directory operation consisted of:

opening the special file
reading the returned fake program into memory as a program
listing the fake program to display the directory contents

What a clever hack!

If I understood the post correctly, the returned fake program simply used the structural description of a BASIC program but wasn't a valid program itself. In other words you couldn't execute the program returned by the list-directory operation. Too bad because it would have been really cool if the floppy drive returned a lambda function!

Aesthetic environments

2009-07-29T05:56:00.002-04:00

One of the things that I've discovered about myself is that I have a sensitivity to my work environment. I find that I am most creative, and productive when I am in an aesthetically pleasing environment. This applies not only to my physical environment but also to my computing environment which is largely why I prefer to use OSX over other equally capable computing environments such as Linux.

A by product of this sensitivity is that I have a deep interest in the work environments of others as a means for further refining my own environment. I'm especially interested in the work spaces and habits of people that I admire.

In a general sense, I admire writers as I have a growing interest in doing more writing myself. So it was with pleasure that I came across whereiwrite.org, an effort to collect photographs of the work spaces of various science fiction and fantasy authors.

I also enjoy programming (which is really writing for machines instead of people) and therefore I am also drawn to images of aesthetically pleasing offices such as:

One of my greatest idols is the famous computer scientist Donald Knuth. As a result I enjoyed this picture of his home office from a Standford Alumni Magazine interview.

Unfortunately my current work environment is a standard corporate cube-farm. I often consider sending our facilities people a copy of the book PeopleWare but I suspect its suggestions would be deemed "cost inefficient". My home environment is still a work-in-progress and unfortunately I don't get to spend much time working in it. It's a life goal of mine to find a way to earn a living in an environment of my choosing. So far, I'm not banking on my blogging skills!

Library, uploaded

2009-07-28T18:51:00.002-04:00

After weeks of gradual effort I've finally completed entering my personal library into a LibraryThing account. If interested, you can view the contents of my library here. This is just the dead-tree stuff and doesn't include the many PDF books that I have collected over the years. Perhaps that will be the topic of a future post.

Until now I have used an OSX desktop application, Delicious Library, to catalog my books. It's a nice program that works fairly well but the eye-candy UI clearly takes priority over the needs of a serious book collector. LibraryThing, on the other hand, better suits my goals of:

Cataloging all my books, including the older ones that don't have an ISBN number
Providing online access to my library making it easier to recall references and send links to potentially interested colleagues
Getting book recommendations based on the contents of my existing library

Some friends of mine use GoodReads for similar purposes. I spent a little time comparing LibraryThing to GoodReads and it seems that the material differences between the two are:

GoodReads is free for an unlimited number of books, LibraryThing is free up to 200 books and requires a paid-for account for larger libraries.
GoodReads prioritizes social networking over cataloging. LibraryThing prioritizes cataloging over social networking.

I think both services are good and provide much value to avid readers.

While I was entering my catalog, I also tagged each book to make it easier to browse and track my library. One nice feature of LibraryThing is that it provides RSS links for each tag so that interested parties can track additions to my library for a specific tag. Now I don't have to nag friends whenever I buy a new book, they can just subscribe to my feeds!

Colossus: The Forbin Project

2009-07-16T20:10:00.002-04:00

While web surfing some time ago I came across a reference to a movie that I hadn't seen before, Colossus: The Forbin Project. I finally got a chance to watch it this weekend and it was fun.

Filmed in 1970, I understand this to be the first movie with the primary theme of a super-computer being given complete control of the nation's defenses, achieving sentience, and overtaking mankind for its own good. Given the period in which this was filmed, I was expecting much "cheeze" and nonsensical computer technology. Instead, it turned out to be a pretty good treatment of the concept based on sound principals. Of course there was some cheeze but this can only be expected from a forty year old movie.

The primary lesson to be drawn from the movie - don't build a super complicated mission-critical system, go straight into production, and then make it impossible to disable it. Advice that continues to hold value forty years later.

Worth watching if you're into this kind of movie.

First & Latest Computers

2009-07-15T17:06:00.002-04:00

On the right is my first computer, a Timex Sinclair 1000. On the left is my latest computer, a Dell Mini9 hacked to run OS X. Putting these two machines side-by-side really puts into context how much computing technology has progressed over the past 27 years (1982 to 2009). Unfortunately, it also serves as evidence that I am getting old!

Joking aside, I bought the Dell more or less for the fun of hacking it to run OS X. My expectations for using it as an actual computer were low. Although I still greatly prefer using my MacBook, I have to say that the Mini has proved far more useful than I initially hoped. OS X runs really well, the screen size and resolution is good, and the keyboard isn't terrible. The Mini's small size, and no moving parts makes it a great machine for taking everywhere which has saved me from boredom on a number of occasions. For light work such as web surfing, email, blogging, and play-programming the Mini is quite productive.

I look forward to posting 27 years from now with a similarly sized computer from that time.

Is an Entrepreneurial Bubble Next?

2009-07-15T05:28:00.002-04:00

Will the next bubble be the collapse of small businesses started during an entrepreneurial gold rush?

This thought has been brewing in my mind for a while now but it was brought to the fore by this Jack and Suzy Welch article in the July 13,2009 issue of BusinessWeek Magazine. The particular quotes that caught my eye were:

Look, this recession has really shocked people…. The result? Many people have come to the conclusion that they don't want to work for "the man" anymore. They want to work for themselves or someone they know and trust.

To be someone else's employee, people are telling us, is to be at someone else's whim.

If anything, starting a business puts you at the whim of more people rather than less. Investors, customers, employees, suppliers, service providers, and others all place demands on business owners that must be addressed. Abandonment by any of these groups could be disastrous.

Also starting or working for a small business involves a substantial amount of risk and provides little insulation from economic downturns. In fact, I suspect that the current downturn has had the greatest impact on small businesses.

Jay Goltz's New York Times blog post, The Dark Side of Entrepreneurship, captures both of these issues well.

To be clear, I am a proponent of entrepreneurship and think that starting a business can be liberating. But to be successful I don't think liberation can be the only goal and I fear that many people are going into small business without the right expectations.

If that is true then what will happen if many of those businesses begin to fail in a couple of years? Do they represent a new form of systemic risk to the economy?

Von Neumann's Universe

2009-07-12T19:46:00.005-04:00

In 2005, George Dyson gave a talk at the O'Reilly Media Emerging Technology Conference on John Von Neumann's work at the Institute for Advanced Study on building early computers. This talk has been a favorite of mine since it was posted to the IT Conversations website. It is informative, entertaining, and well worth listening to.

Related to the Recursive Universe post, much of Dyson's talk focuses on Von Neumann's work on cellular automata in collaboration with Stanislaw Ulam. If you liked that post then you will likely enjoy listening to Dyson's talk. The associated slides are available here (warning, they are 111MB).

Book Review: The Recursive Universe

2009-07-12T07:09:00.004-04:00

The Recursive Universe by William Poundstone

What a delightful book! I was made aware of it by Cosma Shalizi's commentary that I linked to in the A New Kind of Science post. It sounded interesting so I bought a used copy. I'm happy I did so!

The book takes the novel approach of using Conway's Game of Life to discuss complexity theory, specifically how simple rules can manifest into complex systems. Particular emphasis is placed on Von Neumann's interest in self-reproducing machines and cellular automata.

The book is structured in chapter pairs with the first discussing a particular aspect of complexity theory and the second showing how Conway's Life can provide deeper insight. A brief summary of the chapter pairs are:

Chapters	Theme
1 & 2	introduction to complexity, reductionism, information theory, and the Game of Life
3 & 4	entropy, Szilard's thesis on information and entropy, and the limits of empirical knowledge.
5 & 6	information, structure, meaning, and unlimited growth
7 & 8	recursion, the challenges of predicting complex systems using recursive calculations, and self-reproduction.
9 & 10	the evolution of the cosmos and random Life initial states
11 & 13	self-reproduction, the information theory of life, and Life computers.

Before reading this book I had a cursory knowledge of the Game of Life but I was unaware of the sophisticated constructs possible. The Life computers presented in Chapter 12 are fascinating and I can't imagine how much time was required to design them.

I was also unaware of how much attention Life received when it was first created; it seems that many of the bright minds of the time spent considerable time playing the game. I found the historical aspects of this interesting as well but then I have a fondness for computing of this era.

While discussing this book with others I was surprised to find out that an acquaintance of mine was on Gosper's team at MIT that discovered the first Glider Gun. I always enjoy it when I find a personal connection like this to a period of history before "my time".

While looking for additional materials to augment the book I found the following useful references:

Two excerpts (part 1 and part 2) of a BBC documentary featuring interviews with Conway.
A Game of Life news website
Golly, a feature rich cross platform Life implementation
Hashlife, an algorithm devised by Gosper that uses quadtrees to efficiently represent deterministic Life constructs.

All in all an entertaining book that is also very thought provoking. I only wish I had copious amounts of spare time to play the Game of Life myself!

Book Review: The Art of the Start

2009-06-22T16:39:00.003-04:00

The Art of The Start
by Guy Kawasaki

A great and inspiring book. I particularly appreciated the no nonsense advice and strong focus on fundamentals. My bias towards the latter has always made me feel like a "pseudo-MBA" so Guy's advice increased my confidence in holding similar opinions.

I particularly enjoyed the material on bootstrapping. I have always found exciting the kind of action-based, goal-oriented bootstrapping that Guy describes which likely explains why I have spent the majority of my career in small, advanced development teams building prototypes of new technologies and products.

In summary, a great book that I highly recommend to anyone involved in starting new ventures, internal or external.

Daily routines...

2009-06-15T19:45:00.001-04:00

By way of Hacker News, I discovered this delightful website, Daily Routines, that documents the daily routines of various people, many famous. Simply fascinating to read. For instance who knew that Winston Churchill didn't get out of bed until 11:00AM!

A daily routine is something that I've always desired but found difficult to maintain. Perhaps this website will inspire me to finally settle on a daily routine of my own.

A New Kind of Science

2009-06-03T16:40:00.001-04:00

I must admit that before all of the recent WolframAlpha excitement I didn't know much about Stephen Wolfram. By all accounts he is an impressive person so I decided to watch a talk he gave on his book A New Kind of Science.

In general, I find the kinds of cellular automata and computability theory that Wolfram discusses to be very interesting. However, I'm in no position to judge the quality or validity of his conclusions. To that end a quick google search uncovered this commentary by Cosma Shalizi which appears to question at least the originality of Wolfram's work. It sounds like an unfortunate situation for all involved.

Someday I may pick up a copy of A New Kind of Science but in the meantime I may read some of Wolfram's papers as the topic does interest me. Based on the commentary linked above, I ordered a copy of The Recursive Universe and look forward to reading it.