Visualising and Understanding Recursion

As someone who learns best visually, recursion (recursive functions in software) can be a bit of a mind-bender and I periodically have to go back and refresh my understanding of it. A great video to do so with is this:

Computerphile is a brilliant YouTube channel generally and anyone with an interest in computing should subscribe to it. 

Understanding Base64 Encoding #5

Tier 5

This tier is aimed at filling in a few gaps, showing the wider applicability of base64 encoding, and pointing to further reading.

Padding: The Trailing Equals Character

When I first looked at the characters used in base64 encoding I noticed there was a cheeky 65^th character (‘=’) sometimes appearing once or twice at the end of encoded data. It’s actually a special character used for when source binary data doesn’t divide neatly into three byte blocks. A quick example to illustrate.

Imagine I want to base64 encode the following four 8-bit bytes:

01000001 01100100 01100001 01101101

I take the first three octets:

01000001 01100100 01100001

Represent them as four sextets:

010000 010110 010001 100001

And encode using my encoding key, producing: QWRh

But now I have a lonely, final octet left to encode: 01101101

In base64 encoding it’s simply padded out with trailing zeros until we have another three octets:

01101101 00000000 00000000

And converted it to sextets as normal:

011011 010000 000000 000000

Any sextet which contains nothing but padded zeros gets represented as ‘=’.

So the rest of the encoded data becomes: bQ==.

The ‘=’ character is a bit of a courtesy and not every implementation of base64 encoding uses it; it is possible to recreate the original binary data without using ‘=’ for padding, it’s is just more explicit to include it.

Other Uses:

Base64 encoding is typically used in scenarios where representing binary data as a limited set of ASCII characters is desirable. This could be when using an 8-bit (or greater) character encoding isn’t viable, or when you wish to embed binary data in a explicitly text-based medium, or when sending non-alpha-numeric characters could be an issue.  

Attachments to emails are base64 encoded, as are the username and passwords sent for basic HTTP authentication. The specifics of why base64 encoding is used in these scenarios is beyond this series, but reading about https://en.wikipedia.org/wiki/8-bit_clean and https://en.wikipedia.org/wiki/Email_attachment gives you a good idea of why this is the case. The below quote taken from the Email Attachment Wikipedia page gives a good sense of the history:

“Originally Internet SMTP email was 7-bit ASCII text only, and attaching files was done by manually encoding 8-bit files using uuencode, BinHex or xxencode and pasting the resulting text into the body of the message.”

Further Resources:

Once you grasped the basics of base64 encoding the Wikipedia article actually becomes useful. To my mind it’s missing a Tier 1 style explanation but it otherwise quite passable.

There’s an Oracle blog post which is also good – again, if you’ve got some base knowledge to work from.

And when you want to go full nerd there’s the IETF spec!

https://en.wikipedia.org/wiki/Base64

https://blogs.oracle.com/rammenon/entry/base64_explained

https://tools.ietf.org/html/rfc4648

Understanding Base64 Encoding #4

Tier 4

For this tier I’m going to start to push the strained and sanitised analogy into the background and, hopefully, bring the hard edges of base64 encoding into focus.

First, a quick recap on what we’ve established:

• Base64 encoding is a methodology by which we can represent arbitrary binary data (an image, in our example) as a string of ASCII characters.
• The 64 characters used when base64 encoding are a subset of the full ASCII character set. In our case: A-Z, a-z, 0-9, +, and /.
• 64 characters can be neatly represented by a block of 6 bits.
• When base64 encoding, the binary source data is broken into 3 octet blocks (24 bits) which is then parsed as 4 sextet blocks (also 24 bits); 24 being the first common multiple of 8 and 6. 

And our encoding key looked like this:

So far we’ve been using a contrived example – a world with no digital communication – in an attempt to remove the contextual complexity of base64 encoding, concentrating on the essence of subject instead. But this only takes us so far. Let’s take a real world example of where base64 encoding could be used: embedding images in XML.

Occasionally, it may be useful to be able to create an XML document which contains images – not references to images stored elsewhere, but the actual images themselves. I’ve seen this kind of thing done when archiving orders in an e-commerce context: a business wishes to archive orders made over five years ago, however, it also wants some reasonable level of access to that data should a pressing need to retrieve it arise.

One approach to take could be to create an XML document for each order, one which contains a complete record of the transaction: top-level order details, items details, invoice address, delivery address, etc. All this is relatively straightforward. But the company may also decide, for completeness sake, that they wish to store a copy of the primary product images alongside the order. This causes a problem for a developer who doesn’t know about something like base64 encoding. For one who does, it’s fairly trivial. It could look something like this:

Here you have co-opted a medium which is designed to carry text to also carry binary data, although it doesn't even necessarily know it! Those characters between the image nodes are just text characters as far as the XML is concerned. But if the reader knows they're base64 encoded binary data, then the images can be retrieved.

Tier 5 will look to fill in a few of the gaps we've glossed over, briefly give a couple of other examples, and point at some further reading.

Next Understanding Base64 Encoding #5

Understanding Base64 Encoding #3

Tier 3

In Tier 2 I found myself with some binary data (a 10 x 10 pixel image) and a text-based medium (pen and paper) with which to communicate that image to another computer. The image is about a thousand bytes large and I didn’t fancy having to write down eight thousand ones and zeros in order to communicate that image. I’d decided I need to encode the raw data to save myself some pain.

My initial instinct to encode the raw data is that I’ll use a character to represent each possible byte value. This means I can reduce the characters I have to write out from 8000 to 1000. i.e. instead of having to write the byte value ‘00000000’, I could instead write ‘A’. As long as the recipient of my encoded image knows the encoding, e.g. ‘A’ = ‘00000000’, then they can decode the image. I start to write out my encoding key:

00 | 00000000 = A

01 | 00000001 = B

02 | 00000010 = C

…

24 | 00011000 = Y

25 | 00011001 = Z

26 | 00011010 = a

27 | 00011011 = b

…

50 | 00110010 = y

51 | 00110011 = z

52 | 00110100 = 0

53 | 00110101 = 1

…

61 | 00111110 = 9

However, as you might be able to see, by the time I’ve covered byte values 0 to 61 I’ve run out of standard alpha-numeric characters (A-Z, a-z and 0-9). I’m going to have to start using some less recognised characters – and/or possibly even fabricating new ones – in order to get all the way to 256 (the distinct values which can be represented by an 8-bit byte: 0 to 255). This gives me pause for thought. It feels like there’s potential for confusion if I start using arcane or made-up characters.

I stop and have a think. I’ve got 62 alphanumeric characters I’m confident any decoder can easily recognise. I also suspect I could probably be fairly confident using a handful of other characters, e.g. ‘=’, ‘!’, ‘+’, ‘:’, ‘&’, ‘/’, ‘\’, ‘%’, etc. But that doesn’t bring me anywhere near to the 256 characters I’d need for this encoding method.

While I’m ruminating on the problem a thought appears: 62, the number of easily recognised characters I have, is close to the binarily-significant number 64 – the distinct values which can be represented by 6 bits: 0 to 63 or 000000 to 111111. Perhaps I can use this? If I picked a couple of my additional characters at random, say ‘+’ and ‘/’ that would bring me up to a encoding set of 64 easily recognisable characters. I bank the thought.

Then comes the flash of inspiration! Ultimately, I’m just trying to communicate a series of ones and zeros from A to B. When thinking about those ones and zeros I’ve always naturally separated them into 8-bit bytes, but for the purpose of transmission there’s no inherent reason to do so; as long as the correct sequence of ones and zeros reaches the other end the interpretation of that data as 8-bit bytes is the receiving computer’s decision.

I start to jot down my thinking. Imagine the first 3 8-bit bytes of my 10 x 10 image are as follows:

00000010 – 0011011 – 00110100

For transmission, I could split those 24 bits any way I like. Into two bit chunks, for example:

00 – 00 – 00 – 10 – 00 – 01 – 10 - 11 – 00 – 11 – 01 – 00

Or - going back to my previous thinking! – as 6-bit chunks:

000000 – 100001 – 101100 – 110100

And with 6-bit chunks, I can use my recognisable character encoding key!

A – h – s – 0

I could send you "Ahs0" and, as long as you knew the decryption key, you could reverse the encryption and retrieve the bits.

And this is the bare bones of base64 encoding. I’ll fill in the gaps and attempt to extricate the tortured analogy from this explanation, applying the real world, in Tier 4.

Next >> Understanding Base64 Encoding #4

Understanding Base64 Encoding #2

Tier 2

If Tier 1 is about establishing the scantest familiarity with a subject – hoping to avoid looking glassy-eyed whenever it’s mentioned – then Tier 2 is about beginning to understand the topic; perhaps a cursory interest has been kindled and/or you’d like to be able to do a bit more than just identify the subject by sight.

To that end, one of the first questions I like answered when getting to grips with a new topic is “why does this thing exist?”. I’m going to begin to attempt to answer this question for base64 encoding by giving a disingenuous, rather long-winded, somewhat tortured analogy. I promise I’ll make amends in later tiers.

Imagine a strange parallel universe in which inter-computer communication has never happened. The parallel universe’s computers work in the same manner as ours, just no one ever bothered to invent the technologies which allow computers to communicate: no Internet, Bluetooth, portable digital devices – no floppy discs, CDs, DVDs, USB drives, etc. Essentially, each computer is a lonely digital island.

In this reality, if I create a super-cool bitmap image in the alternative universe’s version of MS Paint, you’d physically have to come over to my house and look at it on my screen; I have no digital means by which to transmit the data to you. To add to my misery, you live on the other side of the country and, despite my enthusiasm and entreatment for you to come visit, you’re not going decamp for the sake of one bitmap image.

So, scratching my head, I begin to think about the problem and in a fit of pique I come up with my first – and worst – solution to this problem: I’m going to write the binary code out on pieces of paper and send the code in the post to you. Every single one and zero. And then when you receive the paper full of bits you can key them all in at your end and recreate the image. Perfect!

However, I soon find, even if I only wanted to send the small 10 x 10 pixel image from Tier 1 it’s ~1000 bytes. And given there are 8 bits in a byte that’s ~8000 ones and zeros I’ll have to transcribe! I’m not so keen on this and imagine you’re even less keen about having to key 8000 binary digits in at your end. We need a shortcut.

I’m convinced the part about mailing you the code still has merit but I’m also certain that raw ones and zeros aren’t the answer. What I need is some sort of shorthand way of representing the same raw binary data; I need to encode it.

This is the essence of the problem base64 encoding looks to solve: how can a text-based medium, in our case pieces of paper, be re-purposed to effectively transmit binary data.

Tier 3 will, hopefully, begin to straighten this all out…

Next >> Understanding Base64 Encoding #3

Understanding Base64 Encoding #1

Disclaimer: I’m writing this blog post in an attempt to present a tiered approach to learning a new subject. It's also to solidify my understanding of the topic of base64 encoding as well as to act as an aide-memoire. I’m not presenting this information as infallible fact.

                                                     

Preamble: Personally, learning a new programming concept (or any complex topic for that matter) requires me to take a very particular approach if I want gain and maintain a comprehensive understanding of it, and I don’t see resources which represent and facilitate my learning process very much in evidence.

Learning for me involves moving from the general to the specific and for my sources of information to assume as little as possible while establishing context and purpose quickly. Producing this type of learning resource usually manifests in tiered levels of explanation. To my mind, Tier 1 is where the biggest shortage of good resource on a topic generally is. It should be what the opening paragraph of the Wikipedia topic strives to attain: a succinct and clear overview of the topic that someone immersed in the relevant field can read and feel more illuminated right away. Further tiers of explanation should elaborate on what previous tiers have established.

Let me try presenting the first couple of tiers for base64 encoding in the style I'm talking about.

What I assume: you have a programming background and that you’re looking to better understand base64 encoding.

Tier 1:

Okay, Tier 1 explanations might be relevant if you’ve just heard someone say “base64 encode” in a meeting and you’re thinking “I should probably have some idea what on Earth they’re talking about”; you’re googling about for five minutes to see if you can shed some light on the topic.

Wikipedia’s Base64 opening salvo is: “Base64 is a [...] binary-to-text encoding scheme that represent[s] binary data in an ASCII string format”.

This isn’t particularly illuminating on its own but there are a couple of clues in there: it’s something do with binary data being represented as ASCII characters.

Warning: rather unhelpfully, it is possible to immediately jump down the rabbit hole with base64 encoding and you may be thinking, as I was, “hang on a minute, everything eventually boils down to binary data - including ASCII characters - so that seems like a bit of a nonsense”. Or perhaps you have come across an example whereby someone is showing you how they converted a sentence (one string of characters) into base64 encoded text (another string of characters) and are thinking “what could possibly be the value in that!?”. If you’ve done either (or both) of these things, please, for the moment, put those thoughts on ice – don’t worry, I’m with you comrade, I feel your pain.

A concrete example might help. Imagine I have an 10 x 10 pixel jpeg image (some binary data) and I want to represent it (for some ungodly reason) as ASCII characters. Up steps base64 encoding. In fact, here is a base64 encoded 10 x 10 jpeg:

/9j/4AAQSkZJRgABAQEAYABgAAD/4QBmRXhpZgAATU0AKgAAAAgABAEaAAUAAAAB

AAAAPgEbAAUAAAABAAAARgEoAAMAAAABAAIAAAExAAIAAAAQAAAATgAAAAAAAABg

AAAAAQAAAGAAAAABcGFpbnQubmV0IDQuMC45AP/bAEMAAQEBAQEBAQEBAQEBAQEB

AQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEB

Af/bAEMBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEB

AQEBAQEBAQEBAQEBAQEBAQEBAQEBAf/AABEIAAoACgMBIgACEQEDEQH/xAAfAAAB

BQEBAQEBAQAAAAAAAAAAAQIDBAUGBwgJCgv/xAC1EAACAQMDAgQDBQUEBAAAAX0B

AgMABBEFEiExQQYTUWEHInEUMoGRoQgjQrHBFVLR8CQzYnKCCQoWFxgZGiUmJygp

KjQ1Njc4OTpDREVGR0hJSlNUVVZXWFlaY2RlZmdoaWpzdHV2d3h5eoOEhYaHiImK

kpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4eLj

5OXm5+jp6vHy8/T19vf4+fr/xAAfAQADAQEBAQEBAQEBAAAAAAAAAQIDBAUGBwgJ

Cgv/xAC1EQACAQIEBAMEBwUEBAABAncAAQIDEQQFITEGEkFRB2FxEyIygQgUQpGh

scEJIzNS8BVictEKFiQ04SXxFxgZGiYnKCkqNTY3ODk6Q0RFRkdISUpTVFVWV1hZ

WmNkZWZnaGlqc3R1dnd4eXqCg4SFhoeIiYqSk5SVlpeYmZqio6Slpqeoqaqys7S1

tre4ubrCw8TFxsfIycrS09TV1tfY2dri4+Tl5ufo6ery8/T19vf4+fr/2gAMAwEA

AhEDEQA/AP5/fg7rH7M+nWv7EPjn4nfsT/ACH49fsz/D/wDZbvPgR+xr4R+Hf7Qn

x1tf+C7/APwvX9o7x3D4p8R+Ivi14A+I3jn4ZeAviB8FbK8Xw/P4K8QeGfil/bn7

R3hz4i/sufEfwBqngX4ZaX+xF8FPxB+LFn/Z3xT+Jen/APCN/D/wd9g+IHjKz/4R

H4T+Nf8AhZXws8K/ZfEepQf8I58NPiL/AMJ/8V/+E++H+h7P7M8G+Nf+FpfEr/hK

vDlrpuu/8J/4x+3/APCRaj6B4A/ax/an+FHws8a/Av4W/tLftAfDX4JfEr/hI/8A

hYvwd8AfGT4i+DvhZ4+/4THw5Z+D/F3/AAmvw+8O+I9O8JeKv+Eq8Jadp/hbxH/b

ukX/APbnhyws9E1P7VplrBap8/0Af//Z

Sceptical? If you copy that text and save it into a new text file (called, say, “encodedJpg.txt”) and then navigate to the folder the file is saved in from a Windows command prompt, you can run the following command certutil -decode encodedJpg.txt 10x10.jpg and you should see the jpg recreated.

You can turn the jpg back in to the text above by running the alternative certutil -encode "input" "output" command.

And that’s Tier 1. For the moment we’re not going to worry about the mechanics of the operation, it’s enough to know that base64 encoding changes binary data into text that looks like the above. Why you'd want to do such a thing and how it's achieved are Tier 2 explanations. N.B. the binary data doesn’t have to be a jpeg image, it could be anything: an executable, a zip file, a Word document, etc.

Next >> Understanding base64 Encoding #2

Visualising Sorting Algorithms

Stumbled across a few really good videos for visualising sorting algorithms. I've seen a few which show the sorting happening but not the logic behind it. I think these convey both aspects really well.