Deep Pockets

In the tech industry, how often do we hear this?

• "Great technology, they just didn't market it well."
• "Its a shame to see that product die.
• "They need somebody with deep pockets to see it through."

Of course this brings us to Palm, acquired by HP for $1.2 billion. Brian Humphries, an HP executive in business development, reportedly said: "Our intent is to double down on webOS." Palm managed to find their deep pocketed benefactor. Now we get to watch what happens.

This is the second time a savior has swooped in for Palm. In the early 1990s before the PDA had really established itself as a category, Palm nearly ran out of money. Its VCs were unwilling to put in more, but Palm was not generating enough revenue to operate. The company was purchased by US Robotics, which was later purchased by 3Com. Palm operated successfully for many years after that first brush with death.

We'll see what happens from here. HP likely believes that by owning the complete system, from hardware to OS to applications, they will be able to deliver compelling products and compete successfully with the iPhone. Time will tell.

HTML5 is Hard, Lets Go Shopping!

I just wanted to embed two short audio clips in a web page. Just two little "play" buttons. Thats all. I started with a Flash player, "borrowing" one used by Google Reader:

<embed
  type="application/x-shockwave-flash"
  src="audio-player.swf?audioUrl=myfile.mp3">
</embed>
 

This worked fine, but its a brave new world. I decided to use HTML5's <audio> tag, falling back to the Flash player if <audio> is not supported. This results in:

<audio src="myfile.mp3" controls autobuffer>
  <embed type="application/x-shockwave-flash"
    src="audio-player.swf?audioUrl=myfile.mp3">
  </embed>
</audio>
 

Loaded it into Chrome, it looks nice and plays fine. Life is good. I feel like a real web-enabled kindof guy. Before posting I try it in Firefox... whoops, it doesn't play. Firefox 3.6 doesn't handle MP3 files, most likely due to patent issues. So Firefox has an empty gray box with a little "X" through it.

In fact there is no single audio format supported by all common browsers. Supplying both MP3 and Ogg Vorbis is recommended for maximum compatibility. Next step: re-encode the audio and supply multiple formats. Ogg has to be first, because apparently if Firefox cannot play the first format it does not try subsequent ones.

<audio controls autobuffer>
  <source src="myfile.ogg"/>
  <source src="myfile.mp3"/>
  <embed type="application/x-shockwave-flash"
    src="audio-player.swf?audioUrl=myfile.mp3">
  </embed>
</audio>
 

This sortof works. Not really, but sortof. Chrome doesn't seem to like the Ogg file and plays static for the last half second instead. It probably doesn't play in Opera, which considers the src attribute of the audio tag to be mandatory. I have no idea what IE will do. At least Firefox is happy.

To get an audio tag which will work in all browsers, it appears I have to use JavaScript. Detect the capabilities of the browser, assemble an audio object in the DOM which meets their various requirements and bogosities, and hope for the best.

It shouldn't be this hard. Really, it shouldn't. It appears that as with nearly everything else in the modern web, the HTML5 media tags will be buried behind APIs in our Javascript frameworks to work around browser differences.

Another Long Hidden Easter Egg

The Colony is an early 3d first person shooter. David Alan Smith began development in 1984 using an original 128k Macintosh. The game shipped in 1988. The version I played was black and white, though apparently a later update colorized it for the Macintosh II and Amiga.

The Colony is a fascinating game, for the daunting effort required to get good 3D performance on such early systems. For example the game engine does not use radians or degrees to compute angles. It settles for 256 discrete pseudo-degrees, allowing sin() to be implemented as a lookup table. cos() uses the same table by adding 64 to the desired angle, shifting sin by 1/4 wavelength. David A. Smith wrote about the development experience several years ago, and posted two videos of the game in action.

The game is also notable for its almost sadistic sense of humor. One of the puzzles is the Monolith: two connected rooms, painstakingly modeled after the small apartment at the end of 2001: A Space Odyssey. There is no exit. Once you find yourself in the room, there is no way to leave it. I saved a game in that room lo these many years ago, but unfortunately cannot load it due to a copy protection system of looking up a code in the long-lost manual. This screenshot comes from the second of the aforementioned Youtube videos instead.

Poking around the game's implementation reveals another little joke from its developer. Sound effects are stored as sfil resources in a file named Zounds. One of the resources, "test," is nowhere used in the game.

(MP3) (Ogg)

Sounds vaguely human, doesn't it? Played backwards and slowed by 2x, it is:

(MP3) (Ogg)

I first stumbled upon this sound effect in college. I wish to note that I was living in a dorm 800 miles removed from my parent's basement at the time.

Note: the sound effect is copyrighted, by Mindscape and David A. Smith. It is two seconds long and clearly not material to the game, since it doesn't ever play. I believe this blog post constitutes fair use, as commentary.

eWhere? eWorld!

Did anybody else have an eWorld account, or just me?

It never really took off as a place for those-of-us-who-drink-the-Apple-coolaid to congregate. Mostly it turned into a way to download System Updates before anyone else, so as to lord it over them later. "Oh, you're still running MacOS 7.6.1? 7.6.2 is waaaaaaayyy better."

Code Snippet: hash_map

hash_map is not part of the current C++ STL, but is universally adopted as an extension. Using hash_map is simple when using built-in primitives like int or char*. Attempting to use user-defined classes as a key is somewhat more difficult, as the following example demonstrates:

class example1 {
 public:
  example1() {};
  ~example1() {};

  uint8_t name_[8];
};

typedef __gnu_cxx::hash_map<example1,int> Example1HashType;
Example1HashType hash_map1;

int main(int argc, char **argv) {
  example1 e1;
  hash_map1.insert(std::make_pair(e1, 1));
}

When compiled with gcc 4.2 this results in:

/usr/include/c++/4.2/bits/stl_function.h:200: error: no match for ‘operator==’ in ‘__x == __y’

/usr/include/c++/4.2/ext/hashtable.h:595: error: no match for call to ‘(const __gnu_cxx::hash<example1>) (const example1&)’

hash_map requires two things: a hash function, and an ability to compare equality. To use a class as a key you need to provide a hash<> template specialized for the class in question. You also need to implement an equality operator.

class example1 {
 public:
  example1() {};
  ~example1() {};

  bool operator==(const example1 &other) const {
    return (memcmp(name_, other.name_, sizeof(name_)) == 0);
  };

  uint8_t name_[8];
};

namespace __gnu_cxx {
template<> struct hash<example1> {
  size_t operator()(const example1& k) const {
    size_t hashval = 0;
    for (int i = 0; i < sizeof(k.name_); ++i) {
      hashval = 5 * hashval + k.name_[i];
    }
    return hashval;
  }
};
}  // namespace __gnu_cxx

typedef __gnu_cxx::hash_map<example1,int> Example1HashType;

int main(int argc, char **argv) {
  example1 e1;
  Example1HashType hash_map1;

  hash_map1.insert(std::make_pair(e1, 1));
}

This works, but what if we cannot add an operator method? For example, perhaps the class is in a library which we cannot modify, or is created by a code generator. Consider this case where key is a simple struct with no member functions. This code fails to compile, due to lack of "__x == __y"

struct example2 {
  uint8_t name_[8];
};

namespace __gnu_cxx {
template<> struct hash<example2> {
  size_t operator()(const example2& k) const {
    size_t hashval = 0;
    for (int i = 0; i < sizeof(k.name_); ++i) {
      hashval = 5 * hashval + k.name_[i];
    }
    return hashval;
  }
};
}  // namespace __gnu_cxx

typedef __gnu_cxx::hash_map<example2,int> Example2HashType;
Example2HashType hash_map2;

int main(int argc, char **argv) {
  example2 e2;
  hash_map2.insert(std::make_pair(e2, 1));
}

As this is C++, the solution will of course involve more templates. hash_map does not directly invoke "x == y," it uses an equal_to<> template. The "__x == __y" compiler error is from the template. We can provide an equal_to<> specialization instead.

struct example2 {
  uint8_t name_[8];
};

namespace std {
template<> struct equal_to<example2> {
  bool operator()(const example2& x, const example2& y) const {
    return (memcmp(x.name_, y.name_, sizeof(x.name_)) == 0);
  }
};
}  // namespace std

namespace __gnu_cxx {
template<> struct hash<example2> {
  size_t operator()(const example2& k) const {
    size_t hashval = 0;
    for (int i = 0; i < sizeof(k.name_); ++i) {
      hashval = 5 * hashval + k.name_[i];
    }
    return hashval;
  }
};
}  // namespace __gnu_cxx

typedef __gnu_cxx::hash_map<example2,int> Example2HashType;
Example2HashType hash_map2;

int main(int argc, char **argv) {
  example2 e2;
  hash_map2.insert(std::make_pair(e2, 1));
}

Extending hash_map to custom key types makes it useful in far more situations.

Facebook Developer Humor

Facebook caps the maximum image size to conserve storage space, or bandwidth, or both. I attempted to upload an image substantially larger than this, and received this error.

I suspect the wording is a joke by Facebook developers, "You can never be too tall or too skinny."

Bending the Rules

As of yesterday the iPhone Developer Program License reads:

3.3.1 - Applications may only use Documented APIs in the manner prescribed by Apple and must not use or call any private APIs. Applications must be originally written in Objective-C, C, C++, or JavaScript as executed by the iPhone OS WebKit engine, and only code written in C, C++, and Objective-C may compile and directly link against the Documented APIs (e.g., Applications that link to Documented APIs through an intermediary translation or compatibility layer or tool are prohibited).

The way the new requirement is phrased is interesting. Adobe's Packager for iPhone compiles Flash code to native ARM instructions. Assuming the Adobe tool can produce position independent code, one might consider something sneaky.

void run_disassembled_flash_binary()
{
  asm volatile("ldr r3, [pc, #192]\n\t"
               "mov r1, #3\n\t"
               "str r3, [sp, #32]\n\t"
               "mov r3, #0\n\t"
               "str r3, [sp, #4]\n\t"
               "str r3, [sp, #8]\n\t"
               "mov r2, #24\n\t"
               "mov r3, #48\n\t"
               "add r5, sp, #12\n\t"
               "str r0, [sp, #24]\n\t"
               "str r0, [sp, #0]\n\t"
               "add r0, sp, #12\n\t"
               ...

I make this suggestion in jest. Apple does allow embedded ARM assembly in iPhone apps, but an application consisting of nothing but opcodes produced by a foreign programming environment will not resemble an app compiled from more conventional source code. I very much doubt it would pass the App Store approval process. Though phrased as a technical requirement, section 3.3.1 of the iPhone Developer License is really a business imperative.

Simple Checksums Considered Harmful

Lets talk about iSCSI for a moment, as a launching point for a discussion about data integrity. iSCSI relies on CRC32 to catch data corruption. CRC32 is a good fit for this purpose, but most previous uses of it had been confined to very low levels of the system and implemented in hardware. iSCSI uses CRC32 way up in the protocol header, where it is generally computed in software. The overhead of computing the CRC is one reason why so many hardware offload adaptors were developed for iSCSI.

Intel recently released a whitepaper describing how they achieved 1 million iSCSI operations per second. One fascinating tidbit is that the CRC32 is no longer a bottleneck. The Nehalem architecture includes an instruction to compute it directly, as part of SSE 4.2. The new instruction is described in the Intel64 and IA-32 Architectures Software Developer's Manual Volume 2A: Instruction Set Reference, A-M. It is on page 3-221 of the December 2009 edition; search for CRC32 in later editions.

CRC32 r32, r/m8	Accumulate CRC32 on r/m8
CRC32 r32, r/m16	Accumulate CRC32 on r/m16
CRC32 r32, r/m32	Accumulate CRC32 on r/m32
CRC32 r64, r/m8	Accumulate CRC32 on r/m8
CRC32 r64, r/m64	Accumulate CRC32 on r/m64

Thats it. You load words from memory and hand them to the CRC32 instruction. If you were already making a pass over the data for any reason, the CRC calculation is free. Table-driven CRC generation implementations were already fast, but this is even faster.

What does this mean? I think it means weak checksums should no longer be used for anything. Applications which care about data integrity moved to MD5 or SHA1 years ago, but you still see specifications in other contexts written to use Adler-32 or even the venerable 16-bit TCP checksum. Its not appropriate to use these any more. Server CPUs can compute CRC32 for free, and embedded CPUs have long included CRC32 calculation in DMA engines.

Peepshi

Just before Easter weekend Serious Eats published an excellent recipe for Peepshi. I highly recommend it. Their presentation is much better, I am just an amateur at food pr0n.

Distribution Schmistribution

Electronics distribution giant Avnet recently announced it would acquire Bell Microproducts. The deal values Bell at $250 million after paying off debt. Bell's annual sales are north of $3 billion, but electronics distribution is not a high margin business.

Some of the commentary surrounding the announcement expresses a lack concern about consolidation amongst distributors, because the chip manufacturers have firm control of pricing. I'm not sure that faith is warranted: distributors lack the ability to control pricing because there is so much fragmentation in the market. Each manufacturer has multiple channels for distribution and can play them off against one another. As the number of strong distributors dwindles, that power shifts to the remaining middlemen.

Distributors regularly show they will take complete advantage of any leverage they get. For example, chip manufacturers give preferential terms to a distributor who wins the design-in at a particular customer: no other distributor will be allowed to offer better prices to that customer. This is reasonable... until the distie takes it to the next level. Distributors do a great deal more business with contract manufacturers than almost any individual customer. A distributor can legitimately win the design for a particular chip, then request the bill of materials from the CM. In almost all cases the CM will give it to them. The distributor then registers as winning the design for every component on the BOM, even those they had nothing to do with. As a customer you suddenly find yourself unable to obtain better pricing on anything in your product, based on a single deal for one component.

If consolidation amongst distributors gives those which remain significantly more power over pricing, does anyone think they won't abuse it?

This!Would!Be!So!Awesome!

The World Wide What?

Calling it the World Wide Web is in insult to spiders everywhere. From now on, I propose we call it the World Wide Hairball.

Player Piano Torpedoes

March 24, 2010 is Ada Lovelace day, an informal holiday to celebrate the achievements of women in technology and science. I'd like to share a fascinating technology story about Hedy Lamarr. Ms Lamarr was a contract star at MGM during the Golden Age of Hollywood, in the 1930s and 40s. She was also a creative and mathematically talented inventor. Today, we would proudly call her a geek.

From US Patent 2,292,387, by Hedy Kiesler Markey and George Antheil:

"This invention relates broadly to secret communication systems involving the use of carrier waves of different frequencies, and is especially useful in the remote control of dirigible craft, such as torpedoes.

Our system... employs a pair of synchronous records, one at the transmitting station and one at the receiving station, which change the tuning of the transmitting and receiving apparatus from time to time..."

Two signals are sent, labelled L and R and controlling the left and right rudders of the torpedo. L is indicated by sending a 100 Hz signal over a carrier, R by 500 Hz. Remotely controlled torpedoes had been used before the 1940s, but were often jammed by the target because the control frequency was relatively easy to detect. The innovation in this patent is the use of perforated rolls of paper to modulate the frequency rapidly enough that the enemy would not be able to predict it, making jamming difficult. The perforated rolls of paper were commonly used in player pianos of the time, requiring no special development.

In the patent application seven rows of perforations were used to control the frequency of the carrier. An eighth row of perforations lights a small lamp at the transmitting station. Three of the seven transmission frequencies were dummies which would not actually be received by the torpedo, while the lamp informed the torpedo operator when the weapon was out of contact. The intent of the dummy frequencies appears to be to mislead the enemy and make it more difficult to determine how the control system worked. Some seemingly valid transmission would not be acted upon by the torpedo, while others would.

Rows A-G tune the radio to one of 7 frequencies.
Row H controls a lamp for the operator when the dummy frequencies A-C are in use.

For the transmitter and receiver to frequency hop in sync, the tape reels must begin rolling at very close to the same time and the speed of the winding must have a reasonably tight tolerance. Machined springs available in the 1930s were sufficiently precise to maintain this for several minutes, long enough to guide a torpedo to its target.

All in all its a fascinating invention which repurposed existing technology for a new purpose, in fighting the Pacific War. Unfortunately the rest of the story is not a happy one, as the invention was not taken seriously by the War Department. By the time the communication industry reinvented spread spectrum communications in the 1950s, this patent had expired.

In 1997 the EFF recognized Ms Lamarr and Mr Antheil's achievement with a Pioneer award.

Somebody Has To Build Them

Hmm. Thats an interesting name for a company. I wonder what they make there?

My Name Is ...

Please search for your name in a search engine, whichever one you prefer. Put quotes around your name or not, use a nickname or not, whatever you like. Now: are you satisfied with what you see in the results? If someone else searches for your name, what are they likely to think?

You don't get a second chance to make a first impression, even when that impression comes from a web search.

This blog was born two years ago because I wasn't happy with the search results for my name. At that time the top Google results were IEEE presentations from years ago on Resilient Packet Ring and Ethernet OAM. So lets check how its going:

Within the top four is ok. The results on Bing are significantly different, this site appears on page three. Bing appears to not automatically treat the two words as a name, so it finds pages where both words appear separately. Enclosing the two words in quotes to enforce proximity refines the search considerably, to the first page.

 
Claim Your Name Online

In 2010, I think everyone should have a URL to use whenever a personal link is needed. It doesn't have to be a blog: it could be your Facebook or Twitter page, a flickr group you contribute to, LinkedIn, etc, just something to link to whenever the situation arises. This question will come up more and more often as the Internet becomes ever more embedded into our society.

Its worthwhile spending a bit of time on the selection. Once you start building up links to this URL it will be difficult to change them. If you point to a domain you don't own, like twitter/facebook/flickr/etc, you have no control over whether they remain reachable. Those services seem like they will last forever, but so did GeoCities and Compuserve in their day. Personally I recommend using a domain name which you own. You don't have to run your own server, for example Blogger, Posterous and Tumblr are all free hosted platforms which allow you to use your own domain name.

Once you've picked a URL which conveys the positive first impression you want, start using it. twitter, LinkedIn, stackoverflow, and many other services you might already use let you include a link in your profile. Comments on blogs (like this one) let you use a URL for your name. You can also sign up for a Google profile, which can link to all of the services you want and will appear on name-query search pages.

 
Strategy: Search Engine Optimization

Once you decide you want to control the search results for your name, it is helpful to understand the basics of Search Engine Optimization (SEO). There is an astonishing amount of information online about SEO, much of it seemingly written by people who consider it a kind of magic for which they exchange incantations and arcane formulae. Most of it makes no sense to me, but a couple things did sink in:

1. The number of links pointing to a page matters. Writing an astonishingly useful resource which lots of people will link to is a great strategy. I'm still working on that strategy. It turns out to be difficult. Who knew?
2. When it comes to keywords, DNS > URL > title > body. That is, a keyword occurring in the site's DNS name is weighted more than a keyword in the URL for a page. The URL is weighted more than the same keyword in the page <title>, which is itself weighted more than the body of the page.

 
Tactics: Kneecap the Competition

We're firmly in the web2.0 era, with numerous social web sites vying for our attention. They are also vying for our identity, encouraging people to sign up using their real name. As these are very popular services, they will have lots of inbound links and quickly achieve a higher search ranking for your name than something you create on your own. This is especially true if you use your full name: your profile will contain your name in the URL, which is weighted more heavily. You'll note that in the search results above, two of the top three hits use my name in the URL while the third has it in the <title>.

There used to be more, with StackOverflow and friendfeed rounding out the top five. Fortunately the username could be changed on both services, relegating them lower in the list. So if you aren't happy with the top results for your name, its often possible to do something about it. You can change your login to an abbreviation or pseudonym, or delete accounts which you no longer use.

 
Think Long Term

Nudging positive material into the search results for your name is one thing. Its equally important, perhaps even more important, to keep material which reflects poorly on you out of the results. Jeremy Toeman published a good article about things one should never do online. I think the common sense rule is not to publish things you would regret later, not even if you think you understand privacy settings or conceal the URL.

Thats all. Please let me know your experiences with the search results for your name.