C#: Doing stuff with Google using OAuth - an idiot's guide

I have been playing around with OAuth and connecting to Google apps. After wading through the OAuth standards and Google API docs I decided a library was the way forward, so downloaded DotNetOpenAuth.

As often seems to be the case with freely provided software, it is awesome and well documented at the reference level, but not very good at handholding you through a basic scenario; although that may be due to my preferred way of starting up a blank project and attempting to get a simple application working rather than starting up a sample project and modifying it :o)

I eventually found a good example of what I wanted to do in Samples\OAuthConsumerWpf, but having done hardly any WPF and being too old and grumpy to use lambda functions, it still took a while to get my head round it and get a simple Windows Forms app going.

This is what I did:

1. Created a new Windows Forms application in VS2008
2. Added a reference to the DotNetOpenAuth assembly.
3. Copied the files GoogleConsumer.cs and Util.cs from \Samples\DotNetOpenAuth.ApplicationBlock to my application.

4. You also need an object implementing IConsumerTokenManager. The samples use the InMemoryTokenManager, which is fine for testing - obviously you will need to re-authorise the application on each run, and a useful application would have some kind of backing store.

   The InMemoryTokenManager is located in \Samples\DotNetOpenAuth.ApplicationBlock\InMemoryTokenManager.cs but is disabled outside the samples using compiler directives; I copied it into my new project and removed the compiler directives because I'm too lazy to change the DEFINEs - and again, I prefer to start with nothing and work up to a working sample app in order to get my head round things.

Once you have all these files, you can talk to Google from a Windows Forms app with a tiny amount of code, most of which is palmed off to the GoogleConsumer object in GoogleConsumer.cs.

If you, like me, are new to OAuth programming, the sequence is as follows:

1. Create a DesktopConsumer that will talk to Google, using the GoogleConsumer.ServiceDescription and a new IConsumerTokenManager for the consumer key anonymous and secret anonymous.

   The consumer key and secret identify your application - it will not be registered with Google, so you use anonymous - see http://code.google.com/apis/accounts/docs/OAuth_ref.html#SigningOAuth.

2. Call GoogleConsumer.RequestAuthorization with this consumer and flags specifying the Google apps you want access to. This returns the URL of a page that will ask the user to authorise your application, and a request token which is used later in the process.
3. So far, you have just told Google you want to access application data; at this point, no specific user has been mentioned. You now need to start up a web browser to the URL returned by GoogleConsumer.RequestAuthorization. This will allow a user to grant access to an application, and give them a verification key. The easiest way to achieve this is to start off the browser with System.Diagnostics.Process.Start(url) and show a modal window asking for the verification key to be pasted when it is retrieved.
4. You now use the ProcessUserAuthorization of the DeskTopConsumer instance to get an access token, passing in the request token returned in step 2 and the verification code pasted in by the user.
5. Once you have the access token, you can use that and the consumer to start interacting with Google apps!

Assuming all of the required DotNetOpenAuth files have been referenced or copied in as above, here is the (very simple) code to post a blog entry on Google:

// You will need the following using directives:
using DotNetOpenAuth.OpenId.Extensions.OAuth;
using DotNetOpenAuth.OAuth;
using DotNetOpenAuth.OAuth.ChannelElements;
using DotNetOpenAuth.OAuth.Messages;

// Needed for GoogleConsumer
using DotNetOpenAuth.ApplicationBlock;

// Set up consumer
DesktopConsumer consumer = new DesktopConsumer(GoogleConsumer.ServiceDescription, new InMemoryTokenManager("anonymous", "anonymous"));

// Get the request token and user access authorisation URL
String requesttoken;
Uri authuri = GoogleConsumer.RequestAuthorization(consumer, GoogleConsumer.Applications.Blogger, out requesttoken);

// Start up a browser for the user to grant access and be given the verification key
System.Diagnostics.Process.Start(authuri.AbsoluteUri);

// I have not documented my FormGetKey, but it is a simple form with one textbox and an Ok button on 
// it that just sits there being modal until the user pastes the verification key in and clicks Ok.
FormGetKey form = new FormGetKey();
form.ShowDialog();

// Oh yes, and the form has a public property which is simply { get { return textboxVerificationKey.Text; } } :o)
String vercode = form.VerificationCode;
//

// Get the access token given the request token and the verification code
AuthorizedTokenResponse grantedAccess = consumer.ProcessUserAuthorization(requesttoken, vercode);
String accesstoken = grantedAccess.AccessToken;
//

// Now we are authorized, we have an access token, and we can do stuff
GoogleConsumer.PostBlogEntry(consumer, accesstoken, "http://mylovelyblog.blogspot.com", "OAuth test", XElement.Parse("<p>OAuth test content.</p>"));
//

The next step in the process is providing a more useful implementation of IConsumerTokenManager with a backing store and using the tokens from that. I will post a similarly lift-up-flaps level post on that when I have tried it out, and again with a web app based system.

Looking at the code now, it must be just the fact that it's Friday that I found this complicated...

C#: The Gödel at the Starbow's End

The Gold at the Starbow's End is a short story collection by one of my favourite sci-fi authors, Frederick Pohl, author of the superb Heechee Saga, which still to this day makes me extremely annoyed that we haven't found a fleet of faster than light alien spaceships anywhere in the solar system yet. Still, apparently Phobos is probably hollow, so there's fresh hope!

The eponymous story in the collection is an extremely bleak story I find quite unsettling, like so many Cold War era novels. The basic premise is that a bunch of astronauts are sent off on a long boring journey with nothing to do but play around with maths in the hope they will derive some completely new physics. I can assure you that the story and indeed the others in the book are a good 85,000 times better than my primary school summary.

At one point in the book, the astronauts, having developed theories and modes of thought way beyond the poor suckers left on a socially disintegrating Earth, send back their research, including the theory of easy fusion power, in what is called a Gödelized form.

Maths is not my strong suit, so this was new to me. Basically, it encodes arbitrary information in the form of a single number. A big number. A very very big number. A really quite stupendously large number. A number so big ... well, you get the idea.

How it works is this:

1. List the prime numbers, one for each of the characters in your message.
2. Raise each prime number to the power of your character encoding - e.g. a = 1, b = 2, ...
3. Multiply them all together.

So, to encode the word "whelk", you would calculate:

(2^23) * (3^8) * (5^5) * (7^12) * (11^11) =
679,212,979,662,721,270,806,215,943,782,400,000

To decode, you simply factor the number for each of the primes in the list. So, factoring for 2 gives you the first character, for 3 the 2nd, 5 the 3rd etc. etc.

Note: If you are like me a maths muppet, then this is how you factor a number, using the first prime, 2 as as example:

1. Divide the number by 2 and get the remainder
2. If the remainder is 0, add one to a counter and go back to the first step with the halved value
3. Stop when the remainder is not 0

The counter gives you the factors of two, and hence your first character - e.g. if it were 26, it would be "z".

As you can see, this results in numbers of a size I may have already indicated as being quite large, and decoding requires huge amounts of factoring. Plus of course you need to generate lots and lots of primes in the first place.

In the story, the data size is "the contents of a standard unabridged dictionary". The number is transmitted as a sum of bases and exponents in a highl compact format that fits on one line, like this: (73^3489 + 342^43 + 67^12 + 56^4) - 78. (This is not the actual number, I will update that later when I have the book in front of me).

I really have no idea if it is possible to reduce the numbers to sums of bases and exponents like this and still maintain the information in it; it seems to me to result in such a ludicrously high compression ratio that there is no way it could work - but as I said, maths is not my strong suit. And if it is possible, I don't have a clue how to go about it. In the story, IBM require a 25 year development time before they will even bid on building a machine capable of dealing with the whole number.

So, as I don't know how to reduce the size of the numbers, it is basically a scheme which takes very short strings and turns them into very long ones. Brilliant! How incredibly useful!

However, I am a sucker for the useless, so I decided to write a class which did it.

The C# built in types are not sufficient; using a double any string over about 3 characters runs out of precision and results in garbage, so I downloaded the excellent freeware BigNum library from http://www.fractal-landscapes.co.uk/bigint.html.

The code itself is pretty simple, I was just messing around so it is arbitrarily limited to lowercase alphabetic characters only and a maximum input length of 25 characters. The input length limit is because I lazily copied the first 25 primes from the Wikipedia entry. The precision in the BigInt stuff is arbitrary too; it just needs to be big. I didn't really spend a lot of time on this code :o)

// You will need the BigNum assembly on your application path and "using BigNum" in the source file

public class Godel
{
    public PrecisionSpec Precision { get { return precision; } set { precision = value; } }

    public String Chars { get { return chars; } set { chars = value; } }
    public uint[] Primes { get { return primes; } set { primes = value; } }

    // ------------------------------------------------------------------------------------------------------------------------------------------------------------
    public BigInt Encode(String s)
    {        
        if (s != null && s.Length <= primes.Length)
        {
            BigInt res = new BigInt(1, precision);

            s = s.ToLower();

            int idx;
            for (int i = 0; i < s.Length; i++)
            {
                idx = chars.IndexOf(s.Substring(i, 1));
                idx = idx >= 0 ? idx : chars.Length - 1;

                BigInt curr = new BigInt(primes[i], precision);

                // Exponents should start at 1, then we can use zero occurrences to check for end of data
                BigInt pow = new BigInt(idx + 1, precision);

                curr.Power(pow);

                res.Mul(curr);
            }

            return res;
        }
        else if (s.Length > primes.Length)
            throw new ArgumentException("String cannot be longer than " + primes.Length.ToString() + " characters");
        else
            return new BigInt(0, precision);
    }

    public String Decode(BigInt value)
    {
        String res = "";
        for (int primeidx = 0; primeidx < primes.Length; primeidx++)
        {
            int exponent = Factor(value, primes[primeidx]);

            if (exponent <= 0)
                break;

            int cidx = exponent - 1;

            if (cidx < chars.Length)
                res += chars[cidx];
            else
                res += "[" + cidx.ToString() + "]";
        }

        return res;
    }

    // ------------------------------------------------------------------------------------------------------------------------------------------------------------
    private int Factor(BigInt value, uint prime)
    {
        int res = 0;
        int sanity = 10000;
        
        BigInt remaining = new BigInt(value);
        BigInt mod;

        BigInt.DivMod(remaining, prime, out remaining, out mod);

        while(mod.IsZero() && sanity-- > 0)
        {
            BigInt.DivMod(remaining, prime, out remaining, out mod);
        
            res++;
        }

        if (sanity <= 0)
            throw new InvalidOperationException("Sanity check reached");

        return res;
    }

    // ------------------------------------------------------------------------------------------------------------------------------------------------------------
    private uint[] primes = new uint[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };
    private String chars = "abcdefghijklmnopqrstuvwxyz_";
    private PrecisionSpec precision = new PrecisionSpec(10000, PrecisionSpec.BaseType.DEC);
}

Pretty easy to use:

Godel godel = new Godel();

BigInt encoded = godel.Encode("test");

String originalstring = godel.Decode(encoded);

In the highly unlikely event you find a use for this, you can set the Primes property for longer strings, and the Chars to encode more than just lowercase strings. If decoding doesn't give you back the original string, you may need to increase the precision.

C#: Exceptions are slllooooowwwww

Exceptions, eh? I've always avoided them in high performace code, because everyone knows they're slow. I have never actually bothered testing this though, relying on cleverer and more dedicated people than me doing the grunt work.

Currently, I am writing a high throughput application that performs actions based on a passed in "verb".

Normally, I deal with this by setting up the verbs as an enum and using Enum.Parse() to return the verb and check it is valid at the same time.

I had no idea how quick Enum.Parse() actually is, so decided to test it.

The testing code uses the handy System.Diagnostics.Stopwatch class. It uses an enum containing 3 names, and creates a List<String> of 500,000 of each of those three values; so 1,500,000 strings in total.

The code the loops through the array and converts the strings to the enum values using either Enum.Parse() or hardcoded if / else constructs using String.Compare(String, String, StringComparison).

I also tossed a switch statement in there; usually I avoid them because I find the syntax ugly and opaque, but I read on an MS blog that switches on strings are converted to a hash comparison, so I though if that was true it may be worth checking for speed against the if / else. The switch used String.ToUpper() in the checking loop to provide case-insensitivity.

I then repeated the tests, but this time with every string an invalid enum value. Obviously with the Enum.Parse() this requires catching an exception, and with the other two just an extra condition, in all cases just setting a private member bool flag.

Here are the results:

DoTheEnumThing()

Enum.Parse
00:00:08.64

if/else
00:00:03.48

switch
00:00:02.53

DoTheEnumThingWithErrors()

Enum.Parse
00:05:15.11

if/else
00:00:05.63

switch
00:00:02.74

I think that pretty conclusively demonstrates that exception handling is slow. You certainly wouldn't want to use it in a high throughput situation where you were expecting a lot of invalid values to be passed. The switch is appreciably faster than the if / else, so this hardcoded solution, though ugly, is definitely the speediest way to go.