SEHOP

Structured Exception Handler Overwrite Protection

A timely reminder from somewhere near the middle of the new Microsoft SDL Progress Report (1.8MB pdf, including lots of lovely graphs):

Certain types of vulnerabilities can allow an attacker to make use of an exploitation technique known as a Structured Exception Handler Overwrite (SEH overwrite). This technique involves corrupting a data structure that is used when handling exceptional conditions that may occur while a program is running. The act of corrupting this data structure can enable the attacker to execute code from anywhere in memory. This technique is mitigated by SEHOP, which checks to ensure that the integrity of the data structures used for handling exceptions is intact. This new invariant makes it possible to detect the corruption that occurs when an exploit uses the SEH overwrite technique and is ultimately what makes it possible to break exploits that make use of it. SEHOP is a relatively new mitigation technology and is expected to become a requirement in future versions of the SDL.

Windows Vista SP1, 7, Server 2008 and 2008 R2 introduced support for SEHOP as a runtime feature, helping protect applications regardless of whether they were compiled using previously available mitigations such as the /SAFESEH option.

By default this protection is enabled on Windows Server SKUs (Srv08/R2) and disabled on Client SKUs (Vista SP1/2, Windows 7). If you're running one of these clients, clicking on the Microsoft Fix it graphic above will enable SEHOP for all applications.

SEHOP per-process opt-in support in Windows 7

"If you cannot enable SEHOP for all applications we strongly recommend enabling SEHOP for all internet facing applications, such as your preferred browser and mail client."

- Matt Miller, MSEC Science

First Day O' Security Follow Up

Security Theater

The most cited criticism of the (first) Day O' Security material seems to have been lack of the expected real world examples of specific vulnerabilities, threats, mitigations and attacks:

• Better concrete examples – ideally from our own code base if possible!
• Not enough real world examples.
• No code related examples (I know it’s more about the broad topics, but some specifics would have been nice).
• Would have liked concrete, how-to examples on security, i.e. how-to do authentication, how-to techniques on securing the transport, how stuff works in our domain etc.
• No real life exploiting of security [stories], i.e. Gary McKinnon probably used X method or Google got hacked one time because of X.
• Would have been good to hear about real world examples of specific attacks.
  

Fear not gentle readers, we'll soon be getting to all that fascinating stuff. Meanwhile it's clear you deserve an explanation: why did we deviate from that more obviously crowd pleasing agenda?

In his book Beyond Fear: Thinking about Security in an Uncertain World, Bruce Schneier coined the term Security Theater, describing countermeasures intended to provide the feeling of improved security, while doing little or nothing to actually improve it - or even making matters worse. This often takes the form of trying to prevent the most recent successful attack. Political pressures, like media hype and misinformation operating on an invariably poorly informed electorate, cause the adoption of the bad syllogism:

• Something must be done!
• This is something!
• Therefore, this must be done!
  

The consequences of security theater can range from Internet banking services that time out after seconds of inactivity, preventing you from getting any business done; to huge and vulnerable lines of people waiting in airport security, nicely kettled and immeasurably easier to bomb than previously. Meanwhile the bad guys - with the possible exception of only the very best, most successful suicide bombers - rather than resting on the laurels of their most recent success, are concentrating on their next, least expected attack.

The First Thing About Security

Whether in the arena of terror or the field of data processing, the antidote to the populist security theater mentality is concentration on holistic core principles. Airport security is that service sector's very last line of defence against the dangerous and deranged, but successful detection and capture there signals little more than failure of the intelligence-led policing intended (required) to guard against public atrocities in general. Effort, money and resources are almost invariably better spent when targeted at the latter strategy.

So too with computer security. The great majority of past exploits, however ingenious and heroically evil, are solved and patched; at least in the sense that solutions and patches are available to potential targets. Hearing about these exploits is fun, much like reading a good detective or espionage novel.

Very shortly before our first Day O' Security, the schedule was changed from an all-day session to two half-day presentations of the same material (intended to allow more people access to the limited number of PCs, which in the event went unused). In excising the populist examples of black hat ingenuity in favour of the higher priority core concepts of vocabulary, taxonomy, data flows, trust boundaries, threat modelling and attack surfaces, I veered decidedly and deliberately away from the security theater approach of finding then papering over the cracks in the plaster. By way of compensation, other received comments appear to acknowledge that humorous content did not necessarily suffer as a result.

The Second Thing

I mentioned above that high profile examples still have their place, and their time is coming. Meanwhile if you want a sample of the kind of thing planned for Day 2, take a look at Part 2 of this Google Code University slide deck on Web Security:

http://code.google.com/edu/submissions/daswani/index.html

(Hat tip: Brum Brum)

An accompaniment to the book Foundations of Security: What Every Programmer Needs To Know, these ppt slides are CC licensed just like the Microsoft SDL materials used in Day 1, so they may be retained for use in Day 2. Or it might be completely different; you'll just have to come along to find out.

I Hate You All

Security Presenter Character Assassinated

Last Monday was our "Day O' Security", when I finally gave our design, development and test departments the first "Introduction to the SDL" presentation. Months in preparation, the material was revamped numerous times, evolving in the process from an extravaganza of clowns and dancing girls, into its final form: a very modest, half-day coverage (presented twice) of CIA and STRIDE.

The material presented included Adam Shostack's 10-minute CC-licensed video explaining his threat modelling card game Elevation of Privilege. Also included were individually wrapped chocolate chip muffins and Mr Kipling's French Fancies.

My beautiful assistant ScaleThis!, who handled all the scheduling aspects, also sent out requests for audience feedback - three questions - at the end of the day. I'd already received and reacted to some comments about the morning session, and the afternoon presentation proceeded quite a bit faster as a result. That might account for some of the variation in these replies.

Here are links to the PowerPoint presentation, both native and pdf (minus Adam's video, for which see above):

http://www.jmkerr.com/security/Day O' Security.pptx
http://www.jmkerr.com/security/Day O' Security.pdf

And in the spirit of Scalzi's treatment of negative reviews, here is the feedback. Anonymized, but otherwise uncensored. Overall, this level of comment is terrific; although in the interests of continuous improvement, I'd just like to restate that more complaints are always welcome. You can be damn sure that I'll be working through Guy Smith-Ferrier's Video Series: How To Give Great Presentations this weekend...

Did You Find It Useful?

• Yes, we need to follow up on this.
• I did, I think there are certainly a number of areas we should be building into our processes as we develop our new offerings.
• Yep. Although to be really useful I think we need a formal review process in place in order to threat assess our applications, especially now when moving towards cloud based solutions and potentially SOA.
• I think the day of security was informative but feel as if I never learned very much from it.
• Yes, very useful. I have a very basic knowledge of security. I found the discussions about [Project#1] and [Project#2] in connection with STRIDE very useful as this put it in a real life situation which I was finding hard to do when John asked. I think however an existing knowledge of how [Project#1] and [Project#2] processes data and how that data is stored was necessary to answer the card game but I liked hearing the comments from others.
• Yes it was useful as I didn’t know of STRIDE or CIA.
• Yes. It was a good introduction to security considerations and gave an indication of what factors you should be considering when building any application.
• I found it very informative. certainly planted a little seed in terms of getting us to start thinking about these things.
  

3 Things That Were Bad...

• I’m afraid [John's] presenting skills come top of the list. Too much detail and not enough practicality which reduced opportunities for interactivity. The setup, too many people for PCs and all forward facing.
• Lot of "dead air" and I was uncertain if JK was looking for input at times... He seemed to wander off on his notes.
• Too deep on process at the end when a summary of the model would have done.
• I think JK suffered from a lack of structure and intent at points (was he planning a break?)
• Pace. Could have been a bit quicker.
• Better concrete examples – ideally from our own code base if possible!
• Having very little knowledge with security designs and techniques I feel like the lecture was [too advanced] for me. Most of it did not make sense.
• There was very little interaction we just sat and listened which made me lose concentration very easily.
• A bit slow to get to the core information.
• Not enough real world examples.
• No code related examples (I know it’s more about the broad topics, but some specifics would have been nice).
• John was at times difficult to hear.
• Did you see the calorie count on those muffins!!
• Maybe a bit more interaction for the audience, it felt a little like a lecture. However I think he’ll be doing this in the next session. Working in pairs is always quite good in workshops/training, makes it more fun and less scary for those who don’t quite know what they are doing.
• A little quiet at times.
• I found the presentation style a difficult to follow (sorry John), I’d guess that is the reason we only got half way through the material.
• Assumed we already knew the terminology and exploits already.
• Would have liked concrete, how-to examples on security, i.e. how-to do authentication, how-to techniques on securing the transport, how stuff works in our domain etc.
• No real life exploiting of security [stories], i.e. Gary McKinnon probably used X method or Google got hacked one time because of X.
• Too much flicking off and on the presentation slides, no real flow.
• Could probably do with more slides, but using images to convey a message. He also zipped through these quite quickly.
• John spoke too quietly.
• Network rack in the room was too noisy.
• Only one muffin :-J
• John struggled to get all the material in due to the duration having been cut by half a day.
• Would have been good to hear about real world examples of specific attacks.
• Interactive part was a bit flat – should have possibly split us into groups to discuss to make sure that everyone was contributing.
  

3 Things That Were Good...

• The subject matter was good, it was good that we did it, umm
• Sharing experiences of our own product weaknesses ! Good interaction driven by the attendees.
• JK's sense of humour.
• Overall "Thought provoking" ( but needed to be delivered a bit more snappier than it was).
• Thinking about our own application vulnerabilities is good.
• Good explanations of terminology, general research by John I think was top notch and presented well.
• Everyone was involved. We need more awareness of these concerns in each of our disciplines from design through to test. Even a basic awareness is a good thing, but as per 1 I think we need people who can review and threat assess projects periodically and provide advice on mitigation techniques to other developers or at least highlight the risks and ensure it is acceptable to the stakeholders…..
• Muffins!!
• Brings security which is often an afterthought to the forefront for everyone.
• Good discussion around security relating to [Project#2].
• Finally found out what CIA and STRIDE mean!
  
• The card game was great and well presented, took his time going through definitions of each and provided examples together with the video. It all came across really clear and simple.
• It was light hearted; this made me feel relaxed, making it easier to learn things from it.
• John didn’t assume the audiences existing knowledge of security and thus covered all levels, starting with glossaries and definitions helped people like me understand the whole presentation. This was very helpful and refreshing.
• Got people thinking about, perhaps some obvious, and some not so, security concerns, by way of the playing card examples, that we simply don’t think about.
• Pointer to http://google-gruyere.appspot.com/
• Suggestion/Push/Nudge/whatever at getting earlier involvement from folks other than a high level design team on security concerns. Not design by committee, but not excluding those that might have valid input either. Not sure the card game (… really? Blackjack it ain’t) is the best approach, but interesting to try.
• He has a good relationship with everyone in the room.
• Some good humour worked in.
• Had a game for the audience (needed more work to engage people though).
• Developed an awareness of threat modelling.
• Learned that identifying weaknesses need not be a highly technical exercise.
• Developed an awareness of various attack vectors.
• Lively and interesting presentation with just the right amount of injected humour.
• Interesting discussions related to our products.
• The fact we are involved in something that potentially will have practical results.
• Card game aspect – interesting way of categorising the threats and makes it a bit more memorable than an unordered or ordered list.
• Mapping the threats and categories onto [our] applications clarified some of the terminology.
• John’s dry sense of humour in his presenting skills – I like it!
  

Other Comments

• But do you know what? It's a difficult thing to do, JK was nervous and he hasn't done it for a long, long time; I think most of the senior members of the team should be doing sessions like this to build up confidence and share the love!
• Kudos to John. Can’t wait for the next part.
  

Thanks To All Who Contributed

You deserve better.

C# String Format Run Time Field Width

Explanation As Promised

String formatting in C# is no small subject. With so many variations, its documentation can seem all over the place in MSDN, making it a bit of a pain to track down that one spec detail you need. And occasionally, a lot of a pain, when it transpires the feature you're chasing doesn't exist, never has, nor will :-( Example: what's the C# equivalent of this Delphi fragment, which formats a given string value into a field whose width is determined at run time:

ShowMessage(Format('%*s', [width, value]));

The key point here is that '*' character in the middle of the format string, consuming one numerical value from the input data, and assigning it to the field width expected in that position. Frustratingly, the answer is that the standard C# string formatting arrangements have no such feature. However, having said that, the following C# code does display any given value (not just strings), right justified, in a field of the specified width:

Console.Write(string.Format("{{0,{0}}}", width), value);

What's all that about then? There are two "tricks" at work in combination here, and they both have to do with hiding something. Firstly, the particular overload of Console.Write being used accepts a format string as its first parameter. But this format string itself is what's being computed in the string.Format expression. Without that overload, we would instead have to use something like this equivalent (effectively what the compiler does):

Console.Write(string.Format(string.Format("{{0,{0}}}", width), value));

For clarity, that repetition of string.Format is not a typo. This is in turn roughly equivalent to:

var format = string.Format("{{0,{0}}}", width);
Console.Write(string.Format(format, value));

The second trick is the doubling up of the curly braces in the string constant, "escaping" them in the context of the enclosing string.Format function. Rather than performing straightforward substitution inside "{{...}}", the function instead just removes one level of braces. However, the interior "{0}" itself, being unescaped, is replaced as normal by the number width. For illustration, suppose width is 6. Then after application of the first string.Format, we will have this:

var format = "{0,6}";
Console.Write(string.Format(format, value));

Finally, getting rid of our temporarily introduced format variable, this is equivalent to:

Console.Write(string.Format("{0,6}", value));

So there's no magic format string feature for run time specification of field widths. All we've done is create a particular format string instance at run time, one which happens to contain the desired field width as a string. Simples ;-)

Incidentally, this technique crops up incessantly whenever you're metaprogramming - writing code which, at run time, writes code. At the heart of a SQL Builder or an IQueryable implementation for example, you might find you have to brace yourself with three or even more nested levels of those things.

Number Systems Redux

Just What Exactly Is A Number?

Lots of feedback about those hypercomplex posts. Well, some. An email flooded in. Actually to tell the truth, the interest had less to do with hypercomplex numbers as such, more with the programmable field length string formatting trick used in printing the multiplication tables for Cayley-Dickson algebras. So, okay, I'll write that up as a separate mini-subject; but only after this recapitulation.

What I want to do is revisit and spell out the basics of the earlier progression, from one number system to the next, via the sequence of equations which force the introduction of new concepts into the realm of what we are willing to call a number. This is not the only such path, but it is an interesting one. Remember that at every stage, the "current" number system contains everything in every preceding system. Click on each title / picture for the related Wikipedia article.

The Natural Numbers N

We start like Romans, with the everyday system of object counting numbers, N = {1, 2, 3, 4, ...}; or more accurately I guess {I, II, III, IV, ...}; and ask if there are any problems it can't solve. It doesn't take long to turn up one:

x + 1 = 1

None of our counting numbers has this property, that if you add one to it, the result is one. So like the somewhat brighter-than-Roman Arabs, we introduce a new concept: the number zero. Adding this into N, we find the solution we were after, namely x = 0, in...

The Whole Numbers W

Or "nonnegative integers", for a less ambiguous term. Still, our work has only now begun. Immediately, we are confronted by another unsolved problem, another simple equation without a solution:

x + 1 = 0

What kind of thing becomes nothing, when you add something to it? Answer: a negative number. Adding all of these into W, we find our particular solution, x = -1, in...

The Integers Z

Still, we haven't yet solved even the full set of the very simplest equations. What about this one:

x + x = 1

That's going to require that we bring in fractions, too. Let's add in every possible number of the form p/q, where p and q are integers (and q is nonzero). Including x = 1/2, the solution to our latest problem. Then we have...

The Rationals Q

Surely that's everything? Well no, it's actually very easy to show that even with rational numbers as finely grained as we wish, there's still no solving this:

x² = 2

For that we need the so-called radicals. And while we're there, we might as well add in every solution, positive or negative, that we can find to any polynomial equation (in x, with rational coefficients). Then we will have...

The Algebraics

These include such radicals as x = √2, which was just what we needed right then. And while it might seem we've come a long way, still in truth we don't actually have any more numbers than we started out with in N. The algebraics are still just countably infinite. But all that's about to change, as soon as we solve the next candidate equation,

x^x = 2

No algebraic number satisfies this equation (proof here). To solve it, we have to extend our number system to include the transcendentals. Once we do so, we obtain our first uncountably infinite set of numbers, namely...

The Reals R

But even this power of the continuum leaves half the world's polynomials unsolved. Here's one such:

x² = -1

To solve this, we have to add yet another new kind of number, an imaginary number x = i, which squares to yield -1. Between them, the real and imaginary numbers in combination give us numbers of the form x + iy. Like the rationals Q before them, these are essentially nothing more than ordered pairs of preexisting numbers. We call these particular pairs...

The Complex Numbers C

And like the reals, they are a powerful lot. One ditty, called The Fundamental Theorem of Algebra, tells us we don't have to look any further for a full solution to any polynomial equation in x. Yet still we persevere; what if we want to mess with the basic rules of algebra itself? What if we want to solve something like maybe,

(xy - yx)² = -4

Inspecting this curiosity, plainly if we want xy to differ from yx, then by definition we need a new kind of number that does not commute. Historically, the first non-commutative algebra discovered was...

The Quaternions H

These are obtained from C simply by adding another new square root of -1. Call it j. Once done, we can use the identities i² = j² = (ij)² = ij(ij) = -1, easily to prove that x = i, y = j solves our non-commutative equation above. And naturally, we can go still further. What about

(x(yz) - (xy)z)² = -4

This time we need x(yz) and (xy)z to differ. Historically again, it happens that the first non-associative algebra discovered was...

The Octonions O

And that once again, these were constructed by adjoining another completely independent and brand new square root of -1, to H. Casually defying more than a century and a half of mathematical history, we'll call it k. Once we sort out its multiplication table, we can verify that x = i, y = j, z = k satisfies our previous, non-associative equation.

Now, let's drop back down from three variables to two. Consider:

((xy)y - x(y²))² = -4

This can no longer be solved in O, because now we need (xy)y to be different from x(y²), whereas these quantities are always equal in O. We express this by saying that while O is not associative, it is alternative. Historically, the first non-alternative algebra discovered was...

The Sedenions S

These are formed in the "usual" way, by adding yet another unique √-1 which we'll call l. Again with a suitable multiplication table, we can readily show that x = i, y = ij + kl satisfies that non-alternative equation.

There, once again, we stop. Not of course because we have run out of algebras. The Cayley-Dicksons alone go on forever! And not because these algebras have become any less interesting, or too "pathological" with the loss of the alternative property. But simply because we have to stop somewhere. Applications exist of algebras beyond S, including certain topological investigations and many physical curiosities.

Previously:

A Few Hypercomplex Numbers
A Few Hypercomplex Onions

Elbow, Glasgow SECC, 15 Mar 2011

Working Man's Poet

Warning: total setlist spoiler.

"How many of you have bought the new album?" asked Guy Garvey of Tuesday night's SECC audience. Some hands went up. "The rest of you are dragging your heels a bit!"

Guilty. Last year, when Guy announced Elbow were going into the recording studio, "to make a record for children", I can't have been the only one to cringe. OMG, it's unbearable. They're going to cover Bob The Builder. That dread only increased when I saw the track title Lippy Kids. And again, when I heard the name of the new CD: Build A Rocket Boys!

I never guessed that name could be one half of a most expressive couplet, concisely (and yes, a little sentimentally) devised to speak across the generations. In case of any doubt, the working man's poet set the scene Tuesday night, relating how he was given pause by his own reaction to some kids on a street corner. "They're just young people, but older people are wary of them. And all those right wing bastards feed on that." Okay, I guess you'll not be wanting your Daily Mail delivered, eh Guy.

Do they know - those - days
are golden?
Build a rocket, boys!

Sensitively succinct, wistfully nostalgic, literally essential - full of life.

Panic

I'd bought the tickets for Linda, Christmas 2010. Earlier, actually.

After our previous experience trying to get in and out of the SECC car park, for a John Bishop show at the Auditorium, we'd decided to take the full day off this time. Arrive early, get some dinner at the hall. But fates conspired to thwart us. I had to run a mercy errand that took up the whole afternoon. Then at the last minute, we discovered the show was at 7:30, not 8pm. Chucking some Heinz low fat macaroni cheese and toast down our necks, we ran.

Villagers

And so we arrived to find the support act, Dublin folk collective Villagers, already on stage playing songs from the Mercury nominated debut, Becoming A Jackal. "I love them!" was Linda's reaction, as she lovingly wiped a stray cheese macaronum from my chin. "Who are they like?"

There's a job for you, identifying front man, singer, songwriter and multi instrumentalist Conor J O'Brien's musical, lyrical, arrangement and production influences. All are diversity. Minute by minute, his songwriting inspiration might come from anywhere: now, the genius of Dylan's Positively 4th Street; next, Elton's Tiny Dancer. Musically, I found one undisputable Del Amitri reference. Linda heard Fleet Foxes. Writing in the Irish Times, Shane Hegarty may be right that Conor's Irishness isn't a factor, he could as easily be from Northampton or New York or anywhere; but I heard Feargal Sharkey twice.

Not that Conor lacks originality. Exactly the opposite. He is eclectic. He shares with a very few of the best modern tunesmiths, Charlotte Hatherley among them, that uncanny ability to weave something utterly new and good, from that tiny kit of just twelve notes. It's so very nearly impossible, inventing in this domain, something simple - a chord progression, a melody - that's simultaneously new and pleasing to the ear. Ship Of Promises boasts a hook-laden embarrassment of such riches, from interchanging chord patterns shifting under a repeating theme, through Neil Hannon-inspired baroque bridges, to its dying discordant howling suspensions.

Later we would return to the merchandising area to buy the Villagers CD. But for now, Villagers were really great live, with Pieces in particular - introduced by Conor as "a blues style thing" - benefiting especially well from the live atmosphere, and sounding remarkably better than the studio version. Which given that Conor played all instruments (except strings & french horn) on the CD, maybe isn't too surprising at all.

It's not the first time we have been treated to a "surprise" fantastic support band over the years, ever since seeing Simply Red at this same venue in the 80s, so very ably supported by Doreen Edwards's brilliant Distant Cousins. Villagers are supporting Elbow throughout this short tour. No sooner had Linda compared them to Fleet Foxes, than we discovered that these very same two are on the very same bill at The Very Eden Project this very July.

Elbow

During the break, picture frames on the projection screen displayed the five members of Elbow, posing live as for portraits. Eventually these avatars walked out of frame, then the band appeared on to the live stage, launching straight into their new CD opener The Birds. After The Bones Of You, we were into another new masterpiece, Lippy Kids.

My personal favourite Mirrorball, complete with appropriate visual accompaniment, came up pleasingly early in the set. A great singalong, I couldn't resist playing air piano at the end of each chorus. Next, With Love inevitably became an audience participation highlight, followed by the single Neat Little Rows, the beautiful The Night Will Always Win, and Great Expectations.

Grounds For Divorce was another (still more literal) highlight, belted out with fury by band and audience alike, the light show blinding us during the spikes. Then came The Loneliness of a Tower Crane Driver, with its breathtaking pauses, followed by the cut down Puncture Repair, Some Riot, and both informal acoustic and full band renditions of Perfect Weather To Fly.

After Open Arms, the band thanked us and exited, fooling nobody. Well, they hadn't yet played One Day Like This. With which, returning one obligatory standing ovation later to serve up the brass pillars of Starlings followed by Station Approach, they duly closed the set.

Speaking of which, there are a few surprising setlist omissions in there. They didn't play Linda's favourite, An Audience With The Pope, for this audience; while the stylistically similar The Fix Is In was also out - possibly for want of a duet partner. And no Leaders of the Free World - atopical perhaps? - or Scattered Black and Whites. But the new material was plenty strong enough to dispel any hint of disappointment.

The light shows and projection content were every bit as subtly, thoughtfully and artistically composed as is the music of Elbow. Time and again the tasteful special effects would build to a climax matching exactly their accompanying musical crescendo.

And just a quick word about the sound. Actually, it was very good. Unaccountably so, given the horrendous acoustics of that big bloody shed. I swore after my last Arcade Fire experience (who sounded like The Jesus And Mary Chain, only with distorted vocals) I'd never go back there again. And had these tickets not been for Linda, I still wouldn't. Have. Had.

Chat

This was Elbow's first night, on their very first ever big arena tour. I mean, can you imagine? One concern previously voiced by Guy was that the band's accustomed intimacy and connection with the audience might be difficult to achieve in such a setting. But he needn't have worried. Seemingly effortlessly, they achieved all that and a big bag of chips. Spokesman Guy's patter was of course key, as when he asked everyone to raise their glasses and toast the bloke in block C, row R, seat 31 - the seat furthest from the stage. Guy called him out by name, even making him descend a few stairs to accept the spotlight and the warm thanks and standing ovation from everyone else in the hall.

Guy's introductions grew into short stories, illuminating the inspiration for each song. Interspersed were repeated admissions of just how nervous the band were. Someone asked why, prompting the answer "Why? Look at you! There's fucking thousands of you!" (never has he sounded more like Johnny Vegas).

There were intimate set pieces where the band would come together in a close circle for a short song or two. One of these, around the upright piano stationed at the end of what Guy called "me catwalk", a raised promenade stretching into the middle of the arena, raised a lot of laughs when he lifted the piano top to reveal a built-in illuminated cocktail cabinet, and proceeded to serve drinks to the band. Though not to the orchestra, about whom he confided "We pay them peanuts." Came Glasgow's answer: "Well, sort it out!"

Home

I'd promised to make up for the missed dinner date by taking Linda to an all-night MacDonald's. Yeah, she is easily pleased, I've noticed that too.

But before that, we had to detour to a 24hr Tesco, where we finally managed to get a copy of the new Elbow CD (ironically given Guy's complaint, there were none on sale at the venue). And, a bunch of other stuff, because you know, midnight shopping!

Then burgers, then home about 2am. And despite having work the next day, we actually stayed up for a few more hours, playing our new Villagers and Elbow CDs.

We agree: this gig was the best standard of pure entertainment that we have ever experienced from a band. Ten out of ten.

Coda

Just recently, I finally made good on another of last Christmas's promises: buying a few magazine gift subscriptions for some nieces and nephews. You see, throughout the 60s and early 70s, my own Aunt Margaret (that "mercy errand" above was for her) did this for her only nephew, supplying me regularly and reliably with years' and years' worth of Tell Me Why and World Of Wonder. I wanted to do something similar. Educational or creative, their choice; so long as one or other half of the brain is nourished. Little Niece chose The Artist. The boys went for How It Works.

Do they know - those - days
are golden?
Build a rocket, boys!

Song lyrics: copyright © 2011 by Guy Garvey. Photography: copyright © 2011 by Linda Kerr.

Computer Museum (1)

About That Locomotive...

This recent blogging about hypercomplex numbers reminds me, I still haven't shown you the outcome of the wager mentioned here in August 2009: "I bet a friend one pint of Guinness, that I could get a line drawing of a locomotive engine published in PCW." Well, it so happens that for reasons unrelated to trainspotting, recently I've also been re-reading that very copy of Personal Computer World magazine: December 1982, 300 pages, cover price 75p.

For my money, this issue marked the birth of "Lustworthy Computing", the cover star being the deliciously lustworthy Epson HX20. A self-contained, all-in-one battery-operated portable computer, with full size typewriter keyboard. No pointing device, of course; the Apple Lisa wasn't announced until the following year. The HX80 did sport 16k of NV-RAM, 32k Basic in ROM, a built in 20-character by 4-line (120x32 pixel) monochrome LCD dot matrix display, 2¼" dot matrix printer, and a micro tape cassette drive.

PCW's managing editor Dick Pountain memorably characterised this A4-sized beauty as one of two "handheld" (or was it "two-hand held";-) devices, the other being Hewlett Packard's contemporary HP75C, to "advance the art of portable computing beyond recognition." Just looking at that picture today, I still want one.

The Computing Collective

What we had instead, my pal Brian and I, was 50% shares in a Sharp PC-1211, which we'd bought in 1981. The world's first truly pocket sized Basic programmable computer with QWERTY style keyboard. Designed using off-the-shelf CMOS components, including 256 kHz (kiloHertz!) SC43177/SC43178 processors, and three TC5514P 4Kbit (bit!) RAM modules. Oh, and there was a docking adapter, which allowed saving of programs to a standard audio cassette recorder. We took turns using the PC-1211, weekly I think, until about a year later when I launched a hostile buyout.

The memory model on the PC-1211 is unique. 26 permanent variable locations are accessed as either packed BCD (10 digit precision, exponent ±99) numbers A-Z, or strings of up to seven characters A$-Z$. The remaining memory is shared between your program steps (up to 1424) and more variables (max. 178). Variables can also be addressed as one unbroken array A() or A$().

Now Dick Pountain, being also the portable computing specialist in charge of Calculator Corner, accepted my article and program "PC-1211 Complex Arithmetic" for publication in this December 1982 issue. Here's the proof (click to enlegibilify):

And here on the second page, below those 23 lines of Basic code is that "locomotive" syntax diagram. Lovingly hammered out on a Sharp electric typewriter, then manually marked up with graphics using black Biro and a flowchart stencil:

As for that cool, mathematically pleasing Basic dialect: take another look at the hypotenuse calculation at the start of line 100, and in particular, the use of a √ symbol as a keyword. Notice also how the PC-1211's memory model renders redundant the multiplication symbol * between variables:

100: U=√(XX+YY)

In what was turning out to be a bumper month for pay copy, December 1982 also saw David Barrow join Alan Tootill in the magazine's machine code corner, PCW Sub Set, and they very kindly published the Zilog Z80 versions of my error correcting code assembler subroutines, ECal and EFix:

That the editors used to characterise this standard of contribution as "camera-ready", I guess just shows how uncritical was that hobbyist/enthusiast audience of three decades ago.

Sadly, the 1.35V MR44 mercuric oxide coin type cells used by the PC-1211 (a set of four lasting ~300 hours!) are now discontinued for environmental and toxicity reasons. Their manufacture being illegal since 1992, they're now virtually impossible to find. And when found, both ludicrously expensive, and already well beyond their nominal shelf life.

A Few Hypercomplex Onions

C# Generic Limitations

The C# class Onion (listing below) allows experimentation with any of the Cayley-Dickson algebras mentioned in the previous related article, from the monodimensional reals, right up to the 512-dimensional austons :-) and beyond.

Modern professional libraries for this purpose still tend to be based on technologies like C++ templates, allowing for type variation in the underlying coefficients. And not just between a few integer and floating point types. For example, with careful design you can define your Biquaternion type as Quaternion<Complex>. But while elegant and fun to develop, these techniques don't port well to C#. There are several reasons for this, two of them being the comparitively restrictive natures of C# generics, and of C# operator overloading.

Introducing The Onion

The obvious alternative is to create a single class to represent a Cayley-Dickson number of any dimension. That's what Onion does. While it has a private array of double called Values, containing its real coefficients, it also makes essential use of the composition build model. Complex numbers can be treated as ordered pairs of real numbers; quaternions as ordered pairs of complex; octonions, pairs of quaternions; and so on. To support this model, an Onion has read only properties named A and B returning these two lower dimensional Onions.

These let the class encapsulate the Cayley-Dickson definition of a product. Take any two Onions, p and q, of the same dimensionality:

p = (a, b)
q = (c, d)

The Cayley-Dickson construction defines the product of these as

pq = (ac - d'b, da + bc')

where c' and d' represent the conjugates of c and d. Since all of a, b, c, d have lower dimension than p and q, we can apply this definition recursively until we reach the reals, which we already knew how to multiply together. The implementation of operator * is complicated by the need to handle input parameters p, q of different dimensionalities; in such cases, the "missing" component (b or d) is replaced by zero.

Onion Operators, Properties, Methods

Operators implemented in Onion include the unary +, -, and also ~, which returns the conjugate; the binary ==, !=, +, -, *, /, and also ^, which has an optimized override raising an Onion to a signed integral power. Finally, there is an implicit conversion operator from type double, which allows real values to be intermixed with Onions in arithmetic expressions.

Care and parentheses are recommended with ^. In normal C# usage, ^ represents the logical XOR operation, and so has an inappropriately low precedence for the present context (midway between logical OR and logical AND). Also, the exponentiation operator is frequently expected to be right-associative:

2 ^ 3 ^ 4 = 2 ^ (3 ^ 4) = 2 ^ 81 = 2,417,851,639,229,258,349,412,352

whereas without explicit parentheses, we get this instead:

2 ^ 3 ^ 4 = (2 ^ 3) ^ 4 = 8 ^ 4 = 4,096

Most other properties and methods are self-explanatory. Dim is the dimension of the Onion; Re and Im its real and imaginary parts; Norm its norm or modulus, Norm_2 the square of that; and Reciprocal - well, take a wild guess. There are static Exp and (natural) Log functions, added for the particular investigations I happened to be interested in at the time; and a useful ToString() override using 1 + 2i + 3j + 4ij notation, omitting redundant 0s and 1s. Note the use of ij in place of the conventional quaternion k here, as in my earlier article; if you want to change the basis representation, private method AppendDim is the place to visit.

It's a Reference Type but...

Onion isn't quite as dynamic as it appears. Every algebra that it can represent is closed. For example, starting with a bunch of complex numbers, there's no way that any sequence of additions, multiplications etc. can generate a quaternion. Also, I've made it immutable, because it's not a struct (does not have value copy semantics) and I didn't want multireferenced instances changing in unexpected ways.

There is an indexer, but that just gives read access to the coefficients. Once created, an Onion cannot change its value. Expressions such as z *= 2, rather than operating on z itself, replace it with a new Onion.

Examples

Here's some sample code showing verification of the "odd" results used in the previous article:

var i = new Onion(0, 1);
Onion p = i, z1 = (p ^ 2) + 1; // Caution! Operator ^ has a low precedence!
Console.WriteLine("(Complex numbers) When p = {0}, then p² + 1 = {1}.", p, z1);
// Output: (Complex numbers) When p = i, then p² + 1 = 0.

var j = new Onion(0, 0, 1);
Onion q = j, z2 = (p*q - q*p) ^ 2;
Console.WriteLine("(Quaternions) When p = {0} and q = {1}, then (pq - qp)² = {2}.", p, q, z2);
// Output: (Quaternions) When p = i and q = j, then (pq - qp)² = -4.

var k = new Onion(0, 0, 0, 0, 1);
Onion r = k, z3 = ((p*q)*r - p*(q*r)) ^ 2;
Console.WriteLine("(Octonions) When p = {0}, q = {1} and r = {2}, then ((pq)r - p(qr))² = {3}.", p, q, r, z3);
// Output: (Octonions) When p = i, q = j and r = k, then ((pq)r - p(qr))² = -4.

var l = new Onion(0, 0, 0, 0, 0, 0, 0, 0, 1);
p = i*j + k*l; // p ≠ 0
q = i*k + j*l; // q ≠ 0
var pq = p*q;
Console.WriteLine("(Sedenions) When p = {0} and q = {1}, then pq = {2};", p, q, pq);
// Output: (Sedenions) When p = ij + kl and q = ik + jl, then pq = 0;
Console.WriteLine("(p == 0) = {0}; (q == 0) = {1}; (pq == 0) = {2}.", p == 0, q == 0, pq == 0);
// Output: (p == 0) = False; (q == 0) = False; (pq == 0) = True.

Another example: here is the code fragment I used to generate the sedenion multiplication table (order = 4, dim = 16) in the previous article.

const int order = 4;
const int dim = 1 << order;
var values = new double[dim];
for (var row = 0; row < dim; row++)
{
   values[row] = 1;
   var p = new Onion(values);
   values[row] = 0;
   for (var col = 0; col < dim; col++)
   {
     values[col] = 1;
     var q = new Onion(values);
     values[col] = 0;
     Console.Write(string.Format("{{0,{0}}}", order + 2), p*q);
   }
   Console.WriteLine();
}

Source Code

Okay, finally here's class Onion:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Onions
{
   public class Onion
   {
     private double[] Values { get; set; }

     public Onion(Onion x) : this(x.Values) { }

     public Onion(Onion a, Onion b)
     {
       var dim = Math.Max(a.Dim, b.Dim);
       Dim = dim*2;
       a.Values.CopyTo(Values, 0);
       b.Values.CopyTo(Values, dim);
     }

     public Onion(params double[] values)
     {
       var count = values.Count();
       var dim = 1;
       while (dim < count) dim <<= 1;
       Dim = dim;
       values.CopyTo(Values, 0);
     }

     private Onion(IEnumerable<double> values) : this(values.ToArray()) { }

     public double this[int index] { get { return index < Dim ? Values[index] : 0; } }

     public int Dim
     {
       get { return Values == null ? 0 : Values.Length; }
       private set { if (Dim != value) Values = new double[value]; }
     }

     public Onion A { get { return new Onion(Values.Take(Dim/2)); } }

     public Onion B { get { var dim = Dim/2; return new Onion(Values.Skip(dim).Take(dim)); } }

     public double Re { get { return this[0]; } }

     public Onion Im { get { return this - Re; } }

     public double Norm { get { return Dim == 1 ? Math.Abs(Re) : Math.Sqrt(Norm_2); } }

     private double Norm_2 { get { return Values.Sum(a => a*a); } }

     public Onion Reciprocal { get { return Dim == 1 ? 1/this[0] : ~this/Norm_2; } }

     public static implicit operator Onion(double value) { return new Onion(value); }

     public static Onion operator +(Onion x) { return x; }

     public static Onion operator -(Onion x) { return Operate(x, a => -a); }

     public static Onion operator ~(Onion x) { return x.Dim == 1 ? x : new Onion(~x.A, -x.B); }

     public static bool operator ==(Onion x, Onion y)
     {
       bool nullX = ReferenceEquals(null, x), nullY = ReferenceEquals(null, y);
       return nullX || nullY ? nullX && nullY : x.Equals(y);
     }

     public static bool operator !=(Onion x, Onion y) { return !(x == y); }

     public static Onion operator +(Onion x, Onion y) { return Operate(x, y, (a, b) => a + b); }

     public static Onion operator -(Onion x, Onion y) { return Operate(x, y, (a, b) => a - b); }

     public static Onion operator *(Onion x, Onion y)
     {
       int dimX = x.Dim, dimY = y.Dim;
       if (dimX == 1) return dimY == 1 ? x[0]*y[0] : Operate(y, value => x[0]*value);
       if (dimY == 1) return Operate(x, value => value*y[0]);
       if (dimX < dimY) return new Onion(x*y.A, y.B*x);
       if (dimX > dimY) return new Onion(x.A*y, x.B*~y);
       Onion a = x.A, b = x.B, c = y.A, d = y.B;
       return new Onion(a*c - ~d*b, d*a + b*~c);
     }

     public static Onion operator /(Onion x, Onion y) { return x*y.Reciprocal; }

     public static Onion operator ^(Onion x, long y)
     {
       if (y < 0) return x.Reciprocal ^ -y;
       Onion z = 1;
       var power = x;
       var unity = true;
       for (long mask = 1; y > 0 && mask > 0; mask <<= 1)
       {
         if ((y & mask) != 0)
         {
           if (unity) { z = power; unity = false; }
           else z *= power;
           y &= ~mask;
         }
         if (mask > 0) power *= power;
       }
       return z;
     }

     public static Onion operator ^(Onion x, Onion y)
     {
       return Exp(Log(x)*y);
     }

     private static void AppendDim(StringBuilder result, int index)
     {
       for (int n = 0, keys = index, mask = 1; keys != 0 && mask > 0; n++, mask <<= 1)
         if ((keys & mask) != 0)
         {
           result.Append((char)('i' + n));
           keys &= ~mask;
         }
     }

     public override bool Equals(object obj)
     {
       return
         !ReferenceEquals(null, obj) &&
         (ReferenceEquals(this, obj) || obj is Onion && Equals((Onion) obj));
     }

     private bool Equals(Onion other)
     {
       if (ReferenceEquals(null, other)) return false;
       if (ReferenceEquals(this, other)) return true;
       for (var n = 0; n < Math.Max(Dim, other.Dim); n++)
         if (this[n] != other[n]) return false;
       return true;
     }

     public static Onion Exp(Onion x)
     {
       var re = x.Re;
       Onion z = Math.Exp(re);
       if (x.Dim > 1)
       {
         var im = x.Im;
         var angle = im.Norm;
         if (angle != 0) z *= (Math.Cos(angle) + im*(Math.Sin(angle)/angle));
       }
       return z;
     }

     public override int GetHashCode()
     {
       return Values
         .Select(value => value.GetHashCode())
         .Aggregate((u, v) => u ^ v);
     }

     public static Onion Log(Onion x)
     {
       var norm = x.Norm;
       Onion z = Math.Log(norm);
       if (x.Dim > 1)
       {
         var im = x.Im;
         var angle = im.Norm;
         if (angle != 0) z += im*(Math.Acos(x.Re/norm)/angle);
       }
       return z;
     }

     private static Onion Operate(Onion x, Func<double, double> f)
     {
       var z = new Onion(x);
       for (var n = 0; n < x.Dim; n++) z.Values[n] = f(z[n]);
       return z;
     }

     private static Onion Operate(Onion x, Onion y, Func<double, double, double> f)
     {
       var dim = Math.Max(x.Dim, y.Dim);
       var z = new Onion { Dim = dim };
       for (var n = 0; n < dim; n++) z.Values[n] = f(x[n], y[n]);
       return z;
     }

     public override string ToString()
     {
       var result = new StringBuilder();
       var empty = true;
       for (var n = 0; n < Dim; n++)
       {
         var value = this[n];
         if (value == 0) continue;
         if (empty)
         {
           if (value < 0) result.Append('-');
           empty = false;
         }
         else result.Append(value < 0 ? " - " : " + ");
         var absValue = Math.Abs(value);
         if (n == 0 || absValue != 1) result.Append(absValue);
         AppendDim(result, n);
       }
       if (empty) result.Append('0');
       return result.ToString();
     }
   }
}

Happy hypercomplex numbering.