Yango Blog

Introduction

Communicating medium to large groups of data in a compressed format is often required for modern systems. Therefore downloading a 100MB file for example when only 5KB has change is a complete waste of time. A better approach is to simply download the changes and reconstruct the file from this information.

Therefore the question is how do you work out which parts of the file have change and successfully communicate them to a client?

The answer is variable length chunking, this approach breaks the file up into variable lengths, we can then create a hash of the chunk and send it to the client, if the client’s hash of that part is different then the client can download it, otherwise the client will skip it and check the next hash in the collection.

So how can this be successfully accomplished? What he need is a algorithm which will traverse the data set, in this case a file. While it is traversing it needs to check each chunk part to see if it is a boundary. This is usually accomplished by checking if the mod 125 of the chunk part is equal to 0. The algorithm also needs to set boundaries on minimum and maximum chunk sizes so as to create an efficient transfer of data.

/// <summary>
/// Returns true if the Minor Chunk Part is a boundary indicator,
/// IF the minor part chunk is equal to 0 when mod 25 is applied
/// to it and the chunk location is greater than the minimum size,
/// or the chunk location is greater than the maximum size.
/// </summary>
/// <param name="m_chunkPart">The 64 bit minor part chunk</param>
/// <param name="Location">
/// The location of the minor part chunk in the file against
/// the previous chunk location
/// </param>
/// <returns>True if the minor chunk part is a boundary indicator</returns>
public bool IsBoundary(UInt64 m_chunkPart, long Location)
{
return (((m_chunkPart % 25) == 0 && Location >= iMinimumChunkSize) || Location >= iMaximumChunkSize);
}

This method of using variable boundaries provides the function of highlighting changes, as well as providing the same boundaries in the data set for unchanged data groups.

So all that is needed now is a reader function to traverse the data set and check if the chunk part is a boundary;

void workerThread_DoWork(object sender, DoWorkEventArgs e)
{
Stream fs = File.Open(iFilePath, FileMode.Open, FileAccess.Read, FileShare.None);
using (BinaryReader br = new BinaryReader(fs))
{
byte[] buffer = new byte[8];
long StartPos = 0;
long CurrentPos = 0;
List<byte> CurrentChunk = new List<byte>();
for (buffer = br.ReadBytes(8); buffer.Length > 0 && !workerThread.CancellationPending; buffer = br.ReadBytes(8))
{
CurrentPos = br.BaseStream.Position;
CurrentChunk.AddRange(buffer);
if (buffer.Length <
{
byte[] tempBuffer = new byte[8];
tempBuffer.Initialize();
Array.Copy(buffer, tempBuffer, buffer.Length);
buffer = tempBuffer;
}
UInt64 mChunk = BitConverter.ToUInt64(buffer, 0);
if (IsBoundary(mChunk, CurrentPos - StartPos) || br.BaseStream.Position == br.BaseStream.Length)
{
FileChunk fChunk = new FileChunk(StartPos, ((int)CurrentPos - (int)StartPos),
new SHA1Hash(CurrentChunk.ToArray()));
InnerList.Add(fChunk);
StartPos = CurrentPos + 1;
CurrentChunk.Clear();
float perc = ((float) 100 / fs.Length) * (float)fs.Position;
workerThread.ReportProgress((int)perc);
GC.Collect();
}
}
}
fs.Close();
e.Cancel = workerThread.CancellationPending;
workerThread.ReportProgress(100);
}

Each chunk should then be assigned a hash code, for this a cryptographically secure hashing function should be used, for this example a SHA1 hash code is implemented. this provides a numeric representation of the chunk, which can be easily checked.

Implementation Features

The FileChunk class provides storage for the offset and the length of the chunk along with the SHA1 Hash code for the chunk data. The SHA1 Hash is wrapped in a holding class called SHA1Hash. This class provides wrapper functions for the SHA1 Hash cryptography namespace.

When the file is checked for changes the entire file is checked against its hash code, if the hash codes don not match, each individual chunk is check in three ways, firstly its start position, then its length, if they are the same, then the chunk hash is checked. This method allows for the file to be checked in whole and the changes to be highlited and downloaded (or uploaded).

Using a SHA1 Hash function ensures the hash is reasonably cryptographically secure (see http://www.rsa.com/rsalabs/node.asp?id=2927)while being not overly complex to implement.

Introduction

The Google Maps AJAX interface is a very clever piece of coding, It allows the user to navigate around a two dimensional map using input from the mouse. The Google Maps interface can be seen at http://maps.google.com. What I will outline here is how to create an area on a web page which you can pan around with images in the background.

A link to a simple example is here My Google Maps Clone

HTML Code

There is very little HTML code to go with the example.

<br clear="all" />
<div id="quilt_dragLayer"></div>
<div id="quilt">

Here we can see that the HTML simply contains two div tags. The first is the special one, the second contains all the content. The CSS for the two div’s allows the first one to be transparent, and the second one the have an overflow of hidden.

#quilt {
width: 640px;
height: 480px;
background-position:center;
background-repeat:no-repeat;
background-color:#000000;
position:relative;
overflow:hidden;
z-index:0;
}

#quilt_dragLayer {
width: 640px;
height: 480px;
position:absolute;
background-image:url(../images/transparent-pixel.gif);
background-color: transparent;
border:#999999 1px solid;
z-index:2;
cursor: -moz-grab, url("images/grab.cur"), default;
}

So we can see from the CSS the quilt_dragLayer is transparent. The reason for the transparent layer on top of the display layer is to stop the mouse dragging from highlighting the objects displayed and turning them a nasty blue shade.

Javascript Code

The javascript code is the key to the Google Maps Clone working, the script has to handle the mouse events and create images to be displayed in the display area. For this example the MooTools framework was used. See http://www.mootools.net for more information about the framework.

The code implements handlers for three mouse events, move, down and up, in addition to these the over and out events are implemented to change the cursor.

The Mouse Down handler

The mouse down handler enables the dragging of the quilt, the code is shown below;

function QuiltMouseDown(event)
{
drag = true;
dragStartXPos = event.client.x;
dragStartYPos = event.client.y;
setCursor(true);
};

The function sets drag to true, enabling dragging, sets up the start position of the drag and makes the cursor ‘grab’ the area.

The mouse move handler moves the area when drag is set to true. The move function then calculates the region containing the visable blocks before calling the addMissingBlocks function to add in any missing blocks.

function QuiltMouseMove(event)
{
if (drag)
{
var blockStartX = 99999;
var blockStartY = 99999;
var blockEndX = 0;
var blockEndY = 0;
var coordStartX = 99999;
var coordStartY = 99999;
var coordEndX = 0;
var coordEndY = 0;
var numBlockEndX = 0;
var numBlockEndY = 0;
$$('img.imageBox').each(function(p){
///

The addMissingBlocks function adds the missing blocks of the area’s background.

function addMissingBlocks(blockStartX, blockStartY, blockEndX, blockEndY, coordStartX, coordStartY, coordEndX, coordEndY)
{
var q = $('quilt').getCoordinates();
///

So there it is, I hope that this has helped anyone needing to create a Google Maps Clone.

Update: I have updated the code to work with the newer v1.2 of mootools. Just follow the link at the top of the page (or click here). Hope this helps everyone.