std::string strMyBlog = "Chris Taylor";

My first attempt at using the HTML 5 Canvas

2011-10-02T19:04:00.001+03:00

Today I found myself wondering what kind of performance I can get with Javascript and the new HTML 5 Canvas. Looking for something fun to implement quickly I dug up some code for a demo I did of the Silverlight WriteableBitmap and started porting that to Javascript.

Now I am not much of a Javascript guy, in fact I can safely say that this is probably the most Javascript I have written, probably more than all other previous attempts at playing with Javascript put together.

So why am I writing about this if I lack so much experience, well to be honest, it is because I was actually quite surprised by the results and I thought it would be worth sharing.

I did the initial development using IE 9, and I was impressed by the performance, I hit the test page using Firefox 7, Google Chrome 14 and Safari 5.1. By far Firefox was the slowest, IE 9, Chrome and Safari all performed really well on my Window 7 box. So if you are viewing this in Firefox, try it with IE 9 and see if your experience is similar.

Practical Algorithms and Data Structures : Arrays–Part 1

2011-09-06T18:39:00.001+03:00

To understand arrays, you first need to understand some basic concepts of how computer memory is managed. This is going to be a very high-level explanation with many over simplifications, basically I hope to share just enough to ensure that you don’t get lost when we get into the details of arrays.

You can think of computer memory as a collection of blocks which are placed sequentially one after the other in a row. Each block is uniquely identified by a number, this number in known as a memory address. For example, the first block would be at memory address 0 the next at memory address 1 and so on until you reach the last block.

Each of of these blocks or memory locations can store a single piece of data, this piece of data is known as a byte. A byte is made-up of 8 bits where each bit can have a binary state of either ‘1’ or ‘0’, 256 unique combinations of 1s and 0s can be formed for a byte. The interpretation or meaning associated to each of these patterns depends on what part of the system is looking at the data and how it has chosen to interpret the data. For example if your application is interpreting the data in the memory area as letters of the alphabet you might choose to interpret the bit pattern 01000001 as the upper case letter ‘A’. If on the other hand your application is treating the data as a numerical quantity representing someone's age for example, that same bit pattern would be interpreted as the numeric value 65. (See note 1 below)

More complex data can be represented by combining the patterns of multiple memory locations and interpreting those patterns appropriately. Let me give you an example.

Suppose you wanted to store a string of characters in memory, you could choose to store that string with a length prefix which indicates how many characters are in the string, and the subsequent memory locations would contain the bytes that represent each character of the string.

The above image represents a string stored in memory with a length prefix of 5. Memory location 0 contains the bit pattern for the number 5 indicating that the next 5 memory locations contain the character data of the string. Memory location 1 contains the bit pattern 01100011 which has the numeric value of 99, but because we know this is a character of a string we will map this to the character ‘c’ (We are using an ASCII mapping here, see note 2 below), the ‘r at memory address 3 is encoded as 01110010 which represents the numeric value 114. This mapping is done for the 5 memory locations after the length prefix.

Similarly we need encoding mechanisms to store large numeric integer values, real numbers which can represent fractions of a whole number etc. As you might have already realized, the data stored in a single memory location can be quite limiting having only 256 possible values. That is not much to work with, it might be fine for storing your age, but what about the population of a country? As with the example above where we used multiple memory locations to store a string, a similar solution can be found for storing larger numbers that will require multiple memory locations which when interpreted as a whole represent a larger numeric value. For example, using 4 memory locations we have a total of 32 bits of data which gives you 4,294,967,295 unique bit patterns which covers us for the population for any country in the world, we need to go even bigger if we want to store the entire population of the world however.

The important thing here is that you know up front how to interpret the various pieces of information stored in the memory and how many bytes make up a single unit of information.

As you can imagine, these encodings get quite complex, fortunately you rarely need to deal with these low level details, for the most part the details are nicely taken care of for us by the higher level tools that we use to write our software.

The important take away from this post, is that more complex data representations can require multiple memory locations to store a single instance of data.

Prev – Introduction

* Notes:

The bit patterns are not random, they follow a numbering scheme known as the binary system. Read more about this here.
Interpreting the bit patterns as characters is done using a look-up table, in this case I have used the ASCII table which you can read more about here.

Practical Algorithms and Data Structures : Introduction

2011-07-09T21:28:00.000+03:00

Welcome to the first of hopefully many posts on Algorithms and Data Structures.

One of the areas of computer science that I have always felt drawn to is the study of algorithms. That is not to say that I have developed any kind of specialized expertise in the field, but I do find it tremendously interesting and continuously strive to expand on my understanding and ability to apply algorithms effectively.

For me at least, the best way to evolve my knowledge of a topic is to attempt to explain some aspect of the particular topic to someone else. On countless occasions I have found that by answering questions and having my explanations challenged, has enabled me to reach new levels of that “Aha” moment when suddenly a topic that I thought I understood just became that much clearer.

Now you might be wondering why I would even bother writing something like this, especially given all the material out there covering this specific area. Well other than my selfish motivation to learn more in the process, I have also realized that so many developers today lack the basics in terms of even the simplest algorithms. They might know the terminology and sometimes not even that, but as soon as you start probing on the specifics of the algorithms, how to decide which algorithm to use under which circumstance etc. things start to go sideways.

Why is it the case, that so many practicing developers today find themselves lacking in this area? Well I guess, the truth is that with all the excellent tooling and libraries accompanying most languages and development platforms today, very few people need to actually delve into the depths of the algorithms and data structures they use. Everything is right there, got a list and want to find something in it, just call Find, Search, IndexOf or whatever function is documented to find an item in the list and be done with it. There is definitely nothing wrong with this, these libraries are professionally developed, robust and already used by thousands of developers so they are well QA’d. There is however tremendous value in having a good understanding of the algorithms and data structures you use.

If you understand your data, and you know what it is you need to do with that data, the next step is selecting the most appropriate data structure to store your data. Algorithms and data structures are tightly coupled together, often the data structures you use to store your data will determine which algorithms can be used efficiently on the data. While most data structures can be searched, what will vary is how efficiently that search can be performed, depending on the underlying data structure or even the ordering of the data in the structure. Having an understanding of the various data structures and the corresponding algorithms can help you choose the most efficient way to work with your data and ensure your software does not buckle under the pressure of huge data volumes just because you selected the wrong data structure and/or algorithm to manipulate and manage your data. Selecting the right algorithm for the job often it the key to a successful outcome, but to do that you need to understand the pros and cons of what is available to you.

With this series of blog posts I hope to share some of my learning's and at the same time gain a deeper level of understanding as we explore the algorithms and data structures together. I invite you to participate in this series, if you know a better way to implement something or have a better approach to explaining a specific algorithm, please share with us and help enrich our journey.

What are Data Structures?

Data structures are the containers that you use to store and manage the data for your application.

As we design and develop software, one of the decisions we need to make is what data types to use to store the application specific data. If we where developing a simple contact management system, in which we can enter contact information and later retrieve that information, we would need to define how the contacts would be represented internally within the system i.e. the data elements that represent a contact, such as first name, last name, address, email address, mobile number, date of birth etc. as well as the data types used to store each of these elements, how multiple contacts will be maintained and managed within the system, all of which help define the data structures that will be required to build a functional system.

However simply looking at the data requirements is not always enough, we also need to look at the algorithms we intend to apply to these data structures, how will we manipulate the data, perform searches, sort the data etc.. As we will discover through this series, the intended algorithms will have a bearing on the data structures we might select to represent the data in the system.

What is an Algorithm?

An algorithm is a recipe or set of instructions that can be followed to solve a specific type of problem.

Assume we have chosen to store our contacts from earlier in a list in which we can access each contact by walking through the list item by item, like paging through a book. We now need to find an algorithm we can use to search through the list to locate a contact by last name. How would you go about that? Given what we know about the data structure, the obvious solution would be to iterate through the list of contacts comparing the last name element to the search key. If you find a match you can stop the iteration and return the instance of the contact that was found, otherwise if you reach the end of the list and no match was found you return some indication that the contact does not exist. These steps describe what is known as a Sequential Search.

There are situations where using the simple Sequential Search algorithm might not be the best option and could severely hurt the performance of your system. For example, if the list in question contained a significant number of items and you need to perform frequent searches to determine the existence of an item in the list, this could quickly become a bottleneck. Every time we search for an item that does not exist, we will be iterating through the entire list just to determine that the item does not exist, in the best case the item we are searching for is found quickly within the first few items of the list, while on other occasions the item might only be found towards the end of the list. We will look at this in a little more depth in the section on Big-O notation.

Let’s look at one possible alternative, we could use a Binary Search. This algorithm can be significantly more efficient than a Sequential Search, especially in the worst case scenarios where the item being searched is either not in the list or it exists far from the beginning of the list. However, to be able to use the Binary Search, the collection of items will need to conform to the basic requirements of the Binary Search.

The list of items must be sorted
The list structure must support what is often called random access. i.e. we should be able to access item 83 in a list of 100 items without needing to iterate over the first 82 items.

Given the above constraints are met, for the moment we will ignore the cost of ensuring the data is sorted, while not insignificant, for the purposes of the discussion we will choose to ignore it for now, we can use the Binary Search algorithm to introduce some significant optimization.

Here is a quick introductory example of the basics of the Binary Search algorithm.

First you select the item in the middle of the list, in a list of 100 items that will be item 50. Now compare item 50 (the midpoint item) to the search key, if it is a match we can terminate the search and return item, if the search key is greater than the midpoint item then we know that, if the item exists, it must be in the second half of the list. We know this because the list is sorted, therefore if the the search key is greater than the midpoint item, if must be greater than all the items preceding the midpoint item. And visa versa, if the search key is less than the midpoint item, then a potentially matching item would be in the first half of the list. Can you see how with a single comparison we have eliminated half of the items to be searched?

Having determined which half of the list the item might be in, you can repeat the same logic on that subset of the data. Having narrowed the list of items down to a subset of 50, you can again select the midpoint item and compare it to the search key, which will either be a match or indicate that the search key potentially exists in the top or bottom half of the subset. After 2 comparisons we have eliminated roughly 75% of the items to be searched. You can continue until you either find the item or run out of items to search which would indicate that the item does not exist in the list.

We will cover both the Sequential and Binary Search in more detail later, for now I just want to use this to demonstrate how selecting the right algorithm for the job can make a difference and how the nature of the data might influence the algorithms you can use. And it also leads us into the next topic and that is Big-O notation.

Big-O notation

I am sure you have at some point seen or read about Big-O notation even if you did not know what it meant. If you spent anytime reading about algorithms you might have seen something like the following O(n), O(log n) or O(n³). And if you wondered what it all means, I will try to give a very brief non-mathematical description of how you can make some basic sense of this notation.

When selecting an algorithm there are a number of factors that you might have to take into consideration. For desktops or server based applications your primary criteria might be performance, where you want to select the algorithm that is going to give you the best performance regardless of the amount of memory the algorithm requires to be executed. On the other hand, on mobile devices you might be more concerned about the memory requirements of a particular algorithm. In either case, we need some way to represent this these characteristics of an algorithm, this representation needs to be simple enough that just by looking at it I can tell if one algorithm will perform better than another or if it will be more memory efficient without needing to read or understand the complex mathematical analysis of each algorithm. For our purposes we will focus on the performance aspect and discuss the memory aspect later when we work with actual algorithms.

Big-O notation gives us a concise notation that captures the performance characteristics of an algorithm over a collection of items. Basically we can see at a glace if the algorithm performance will degrade rapidly, linearly or gradually as the number of items in the collection increases. Of course as we saw earlier algorithms have best case scenarios as well as worst case scenarios, Big-O notation represents the average case, so looking at the Big-O for a Binary Search I can say that on average the Binary Search will out perform a Sequential Search. That does not mean it will always out perform the Sequential Search, remember, if the matching item is first in the list the Sequential Search will find it immediately, while the Binary Search will need to perform a few iterations before finding that the first item is the matching item, but on average we would expect that the Binary Search will perform better for real world searches.

Using Big-O notation, the Sequential Search would be described as an O(n) algorithm, where n represents the number of items the algorithm will be working with. If we searched a list of 10 items then n=10 and if we searched a list of 1000 items then n=1000. From this we can conclude that on average the algorithm performs linearly, if we double the number of items the average search time will double, so the relationship between the number of items and the execution time is linear.

How does that compare to our Binary Search algorithm, well without getting into the details now, I will tell you that a Binary Search is an O(log n) algorithm. This means that as the number of items increase the execution time increases logarithmically. Mathematically log(n) < n were n is a positive integer (see the table below), therefore we can say that Binary Search is faster than a Sequential search.

Lets look a quick analysis, if the item that I am searching for is the first item in a list of 1,000,000 items then the Sequential Search will clearly out perform the Binary Search which is going to jump to the middle of the list, see that the item is in the first half of the list and half that portion and so on for a total of 20 comparisons before locating the target item at the beginning of the list. However if the item being searched was the last item in the list then the Sequential Search would require 1,000,000 comparisons while the Binary Search worst case would not be more than 20 comparisons. So the worst case of the Binary Search of a collection of sorted items is 20 comparisons while the sequential search will exceed this worst case for when searching of any of the 999 980 that are after the first 20 items in the list.

What we have seen here is that the Sequential Search has a best case execution of O(1), that is constant time regardless of the number of items in the list, of course this is the absolute best case when you are lucky enough to have the item you are looking for be the first item in the list. While the worst case if the item is the last item or the item does not exist at all will be O(n) which is also the average case.

The Binary Search also has a best case scenario of O(1), that is when the item you are searching for happens to be the item in the middle of the list, in which case the item would be found on the first comparison, but the average case is O(log n).

n	O(1)	O(n)	O(log n)	O(n log n)	O(n²)
1	1	1	0	0	1
10	1	10	3.32	33.22	100
100	1	100	6.64	664.39	10000
1000	1	1000	9.97	9965.78	1000000
10000	1	10000	13.29	132877.12	100000000
100000	1	100000	16.61	1660964.05	10000000000
1000000	1	1000000	19.93	19931568.57	1000000000000

Looking at the above table you see a comparison of some Big-O representations for various values of n. This should give you a feel for how one algorithm would perform relative to another based on the Big-O of the algorithm. The best general purpose sorting algorithms today are O(n log n) algorithms.

Given the speed of computers today, even the worst performing algorithms will appear to perform efficiently for small values of n. That is why it is very important to understand the volume of data that your system might need to work with and make sure you test with volumes that are representative of what you expect to see in the production environment.

When selecting your algorithms, make sure that you fully grasp the context in which the algorithm will be used and how that scope might change overtime as your system hopefully becomes more and more popular.

If you would like to see a visual representation of the table above take a look at my Big-O Visualizer. Note this application requires Silverlight 4.

Next: Arrays – Part 1

Visualizing Big-O complexity functions

2010-12-23T14:12:00.002+02:00

I quickly threw this little Silverlight application together to help visualize some of the common Big-O complexity functions often quoted in any discusion on Data Structures and Algorithms.

This works on Linux Firefox with Moonlight 3 Preview Release it is a little slow but it works.

The following is a brief summary of the functions demonstrated in the application. You can get more detail here.

Function	Description	Example
O(1)	Constant complexity regardless of the domain size.	Array direct indexing, Hash table
O(n)	Linear complexity. As the domain size increases, the time/complexity increases linearly. If you double the items the complexity will double.	Sequential search
O(log n)	Logarithmic complexity. As the domain size increases, the time/complexity increases logorithmically	Binary Search on sorted data, Lookup in balanced binary tree
O(n log n)	Log Linear complexity. As the domain size increases, the time/complexity increases at a log linear or geometric rate.	Heap Sort, Merge Sort, Quick Sort¹
O(n²)	Quadratic complexity. As the domain size increases, the time/complexity increases quadratically.	Bubble Sort, Insertion sort
O(n³)	Cubic complexity. As the domain size increases, the time/complexity increases at a cubic rate.	Naive multiplication of two nxn matrices.
O(2ⁿ)	Exponential complexity. As the domain size increases, the time/complexity increases exponentialy.	Some graph algoritms like finding the exact solution to the traveling salesman problem.

¹Quick sort has best and average case of O(n log n) but worst case of O(n²)

Code Share: Finding controls by control type.

2010-09-25T01:08:00.001+03:00

On stackoverflow.com the question was asked, how to ‘Find ContentPlaceHolders in Master Page’.

In this case the OP wanted to work with a Master Page other than the one that was already The first part of the problem was getting the Master Page loaded in memory so that the Control tree could be interrogated.

Fortunately loading the Master Page is quite simple, you can use LoadControl to load the Master Page just like you would load any other user control.

For example in the Page_Load handler you could use something like the following to load the Master Page.

var site1Master = LoadControl("Site1.Master");

The next part, finding all the controls of a specific type, requires a simple recursive routine to search the control tree for all the controls of the type that you are interested in. Here is a simple implementation of just such a routine.

static class WebHelper
{
  public static IList<T> FindControlsByType<T>(Control root) 
    where T : Control
  {
    if (root == null) throw new ArgumentNullException("root");

    List<T> controls = new List<T>();
    FindControlsByType<T>(root, controls);
    return controls;
  }

  private static void FindControlsByType<T>(Control root, IList<T> controls)
    where T : Control
  {
    foreach (Control control in root.Controls)
    {
      if (control is T)
      {
        controls.Add(control as T);
      }
      if (control.Controls.Count > 0)
      {
        FindControlsByType<T>(control, controls);
      }
    }
  }
}

Using the tow pieces of code above, finding all the ContentPlaceHolders on the Master Page can be done like this.

// Load the Master Page
var site1Master = LoadControl("Site1.Master");

// Find the list of ContentPlaceHolder controls
var controls = WebHelper.FindControlsByType<ContentPlaceHolder>(site1Master);

// Do something with each control that was found
foreach (var control in controls)
{
  Response.Write(control.ClientID);
  Response.Write("<br />");
}

Hope someone finds this useful. I thought I would share it since I took the few moments to write it and did not want it to go to waste.

Crossing the process boundary with .NET

2010-06-27T18:25:00.001+03:00

Every so often my post Hacking my way across the process boundary gets some attention. Mostly in the form of requests for a .NET version of this technique. Now out of laziness more than anything else I have not actually taken the time or effort to do the conversion until now. So for those that need to access ListView or TreeView data from another process here is a simple example of one possible way to do it. Since I used C# for the example, I could very well have used unsafe code blocks to do some of the work, however I decided to avoid this making this example applicable to VB.NET developers as well. If you would like to see a version using unsafe code blocks, drop me a note and I will get round to it. To keep the sample short I have removed anything but the most rudimentary error checking. For an explanation of this code, please refer to the original post sighted above.

using System;
using System.Runtime.InteropServices;
using System.Text;
public class CrossProcessMemory
{
  const int LVM_GETITEM = 0x1005;
  const int LVM_SETITEM = 0x1006;
  const int LVIF_TEXT   = 0x0001;
  const uint PROCESS_ALL_ACCESS = (uint)(0x000F0000L | 0x00100000L | 0xFFF);
  const uint MEM_COMMIT         = 0x1000;
  const uint MEM_RELEASE        = 0x8000;
  const uint PAGE_READWRITE     = 0x04;

  [DllImport("user32.dll")]
  static extern bool SendMessage(IntPtr hWnd, Int32 msg, Int32 wParam, IntPtr lParam);
  
  [DllImport("user32")]
  static extern IntPtr GetWindowThreadProcessId( IntPtr hWnd, out int lpwdProcessID );    
  
  [DllImport("kernel32")]
  static extern IntPtr OpenProcess(uint dwDesiredAccess, bool bInheritHandle, 
    int dwProcessId);

  [DllImport("kernel32")]
  static extern IntPtr VirtualAllocEx( IntPtr hProcess, IntPtr lpAddress, 
    int dwSize, uint flAllocationType, uint flProtect);

  [DllImport("kernel32")]
  static extern bool VirtualFreeEx( IntPtr hProcess, IntPtr lpAddress, int dwSize, 
    uint dwFreeType );

  [DllImport("kernel32")]
  static extern bool WriteProcessMemory( IntPtr hProcess, IntPtr lpBaseAddress, 
    ref LV_ITEM buffer, int dwSize, IntPtr lpNumberOfBytesWritten );

  [DllImport("kernel32")]
  static extern bool ReadProcessMemory( IntPtr hProcess, IntPtr lpBaseAddress, 
    IntPtr lpBuffer, int dwSize, IntPtr lpNumberOfBytesRead );

  [DllImport("kernel32")]
  static extern bool CloseHandle( IntPtr hObject );

  [StructLayout(LayoutKind.Sequential)]
  public struct LV_ITEM
  {
    public uint   mask; 
    public int    iItem; 
    public int    iSubItem; 
    public uint   state; 
    public uint   stateMask; 
    public IntPtr pszText; 
    public int    cchTextMax; 
    public int    iImage;
  }

  public static string ReadListViewItem( IntPtr hWnd, int item )
  {
    const int dwBufferSize = 1024;
          
    int         dwProcessID;
    LV_ITEM     lvItem;      
    string      retval;
    bool        bSuccess;
    IntPtr      hProcess        = IntPtr.Zero;
    IntPtr      lpRemoteBuffer  = IntPtr.Zero;
    IntPtr      lpLocalBuffer   = IntPtr.Zero;
    IntPtr      threadId        = IntPtr.Zero;
          
    try
    {
      lvItem = new LV_ITEM();
      lpLocalBuffer = Marshal.AllocHGlobal(dwBufferSize);
      // Get the process id owning the window
      threadId = GetWindowThreadProcessId( hWnd, out dwProcessID );
      if ( (threadId == IntPtr.Zero) || (dwProcessID == 0) )
        throw new ArgumentException( "hWnd" );

      // Open the process with all access
      hProcess = OpenProcess( PROCESS_ALL_ACCESS, false, dwProcessID );
      if ( hProcess == IntPtr.Zero )
        throw new ApplicationException( "Failed to access process" );

      // Allocate a buffer in the remote process
      lpRemoteBuffer = VirtualAllocEx( hProcess, IntPtr.Zero, dwBufferSize, MEM_COMMIT, 
        PAGE_READWRITE );
      if ( lpRemoteBuffer == IntPtr.Zero )
        throw new SystemException( "Failed to allocate memory in remote process" );
      
      // Fill in the LVITEM struct, this is in your own process
      // Set the pszText member to somewhere in the remote buffer,
      // For the example I used the address imediately following the LVITEM stuct
      lvItem.mask = LVIF_TEXT;
      lvItem.iItem = item;
      lvItem.pszText = (IntPtr)(lpRemoteBuffer.ToInt32() + Marshal.SizeOf(typeof(LV_ITEM)));
      lvItem.cchTextMax = 50;

      // Copy the local LVITEM to the remote buffer
      bSuccess = WriteProcessMemory( hProcess, lpRemoteBuffer, ref lvItem, 
        Marshal.SizeOf(typeof(LV_ITEM)), IntPtr.Zero );
      if ( !bSuccess )
        throw new SystemException( "Failed to write to process memory" );

      // Send the message to the remote window with the address of the remote buffer
      SendMessage( hWnd, LVM_GETITEM, 0, lpRemoteBuffer);
      
      // Read the struct back from the remote process into local buffer
      bSuccess = ReadProcessMemory( hProcess, lpRemoteBuffer, lpLocalBuffer, dwBufferSize, 
        IntPtr.Zero );
      if ( !bSuccess )
        throw new SystemException( "Failed to read from process memory" );
      
      // At this point the lpLocalBuffer contains the returned LV_ITEM structure
      // the next line extracts the text from the buffer into a managed string
      retval = Marshal.PtrToStringAnsi((IntPtr)(lpLocalBuffer.ToInt32() + 
        Marshal.SizeOf(typeof(LV_ITEM))));
    }
    finally
    { 
      if ( lpLocalBuffer != IntPtr.Zero )
        Marshal.FreeHGlobal( lpLocalBuffer );
      if ( lpRemoteBuffer != IntPtr.Zero )
        VirtualFreeEx( hProcess, lpRemoteBuffer, 0, MEM_RELEASE ); 
      if ( hProcess != IntPtr.Zero )
        CloseHandle( hProcess );
    }
    return retval;
  }
}

Visual Studio 2010 – Box Selection

2010-06-06T10:57:00.001+03:00

This has been blogged about and promoted everywhere and it is true, it is a super cool feature that even the pre-.NET IDE supported, but VS2010 breaths new life into the feature with some great enhancements. For a very cool intro to the functionality take a look here where a member of the IDE team demonstrates the enhancements.

So, why on earth would I be blogging about “old” news. Well one thing that I found “missing” with this feature until now was the ability to use the keyboard to perform a block selection. Now with VS 2010 you can use Shift+Alt+[Up, Down, Left, Right] to perform a block selection. This is a great enhancement, and worth knowing about if you are a keyboard junkie.

Archive: Binary data from a Structure

2010-04-17T14:37:00.002+03:00

For this post, I will be using the binary structure used by the trusty old DBF file structure.

[StructLayout(LayoutKind.Sequential, Pack = 1)]
struct DBFHeader
{
  public byte Tag;
  public byte Year;
  public byte Month;
  public byte Day; 
  public int RecCount;
  public short HeaderSize;
  public short RecSize;
  public short Reserved1;
  public byte Trans;
  public byte Encrypt;
  public long Reserved2_1;
  public short Reserved2_2;
  public byte MDX;
  public byte LangId;
  public short Reserved3;
}

Given the above structure, our challenge now is to transfer it from its in memory binary format to a stream. The stream may be a physical file, memory stream even a network stream. The most important aspect of all the techniques that I will investigate here is that the resulting binary data format is consistent with the format expected by the reader.

After looking at the interface provided by the Stream class, from which all streams inherit, I came to the conclusion that I would have to convert the structure to a byte array (byte[]).

Again our first stop is the interop services provided by the .NET framework. The following piece of code will convert a structure to a byte[] that can then be written to a stream.

DBFHeader hdr = new DBFHeader(); 
byte[] data = new byte[Marshal.SizeOf(hdr)];
unsafe
{
  DBFHeader *p = &hdr;
  Marshal.Copy( (IntPtr)p, data, 0, data.Length ); 
}

This code requires that you compile with unsafe code allowed. This can be done either by supplying the /unsafe switch to the command line compiler or in the Visual Studio .NET project properties under Configuration Properties>Build, you can set the Allow Unsafe Code Blocks to True.

After creating a instance of the structure DBFHeader a byte[] is created large enough to hold the contents of the structure. At that point we need to transfer the contents of the DBFHeader instance to the byte[]. To accomplish this, I declared an unsafe block and assigned the address of the structure, being a ValueType the structure is allocated on the local stack and is therefore implicitly pinned. Then the Marshal.Copy method is used to copy the data from an address in memory to the byte[]. Now we are free to write the byte array to a stream using the Write method provided by the stream.

There are a number of things that count against this technique. Using unsafe code blocks means that the assembly can not be verified and the caller would require the SkipVerification permission. The use of the Marshal methods requires that the immediate caller has SecurityPermissionAttribute.UnmanagedCode. This technique also requires that the data be moved in two stages, from the structure to the byte[] an then from there to the stream, this could be costly for large structures.

The first problem of the code being non-verifiable can be overcome by using a technique very similar to the above technique, without the requirement for unsafe code blocks. The following code demonstrates this technique.

DBFHeader hdr = new DBFHeader(); 
byte[] data = new byte[Marshal.SizeOf(hdr)];
IntPtr p = Marshal.AllocHGlobal( Marshal.SizeOf(hdr) );
Marshal.StructureToPtr( hdr, p, false );
Marshal.Copy( (IntPtr)p, data, 0, data.Length ); 
Marshal.FreeHGlobal( p );

Notice that it still requires that the data be moved in two stages and the use of the Marshal class carries the same security requirements as earlier. The only benefit is that the resulting assembly remains verifiable, not requiring the /unsafe option. However, allocating memory from the unmanaged heap carries with it additional performance overheads.

And finally the pure managed code solution that while not as easy as the prior techniques, it does benefit from the fact that the code is easily ported to other .NET languages and does not have the same security restrictions as the other two techniques. The solution is to use the BinaryWriter class to write each bit of information from the structure to the stream.

using (BinaryWriter wr = new BinaryWriter( stm ))
{
  wr.Write( hdr.Tag );
  wr.Write( hdr.Year );
  wr.Write( hdr.Month );
  wr.Write( hdr.Day );
  wr.Write( hdr.RecCount );
  wr.Write( hdr.HeaderSize );
  wr.Write( hdr.RecSize );
  wr.Write( hdr.Reserved1 );
  wr.Write( hdr.Trans );
  wr.Write( hdr.Encrypt );
  wr.Write( hdr.Reserved2_1 );
  wr.Write( hdr.Reserved2_2 );
  wr.Write( hdr.MDX );
  wr.Write( hdr.LangId );
  wr.Write( hdr.Reserved3 ); 
}

This code first creates a BinaryWriter that provides binary methods to access the underlying stream. In this case the underlying stream is designated by the stm argument passed to the BinaryWriter constructor. Then using the binary writer, each member of the structure is written in order to the stream through the BinaryWriter instance. I have already mentioned the clear advantages of this technique, but it does carry with it a share of disadvantages. The first and most obvious is that it requires you to write out each member individually, and with larger structures, this can be a tedious and error prone task. This brings me to the second disadvantage, if the data is not written out in the exact order expected by the reader, the reader will either fail to read the structure or even worse, corrupt data.

Just as a closing note, the final technique could also be used to get a byte[] by writing to a MemoryStream and then calling the GetBuffer method provided by MemoryStream to access the underlying byte[].

Conclusion

As with every design, it is a series of compromises that determines the ultimate chooses we make. The above techniques provide a number of alternative ranging from simplicity of code to flexibility of implementation. I believe that the final option is most likely the more purist and from a reusability standpoint the more effective solution.

Archive: Structure from Binary Data

2010-04-17T14:06:00.005+03:00

Original Post Date: 8 Jan 2004

The question of moving stream data into a structure seems to be addressed every so often on the newsgroups. While I was building a front-end for a small packet sniffing application I was faced with these same questions. While I was aware of the standard approaches I decided to investigate what the alternative options where. This article is a summary of the primary ways I looked at of mapping binary data to a structure.

Defining the structure

The first thing that I did was to define the structure, for this example I am going to use the IP header. Deciding on the correct definition of the structure is dependent on the solution or approach taken to solve this problem.

Given that I have spent a considerable amount of time familiarizing myself with the intricacies of the P/Invoke or interoperability services, my first solution was to use System.Runtime.InteropServices to marshal the data into a structure. I promptly defined the following structure to handle the marshaled data.

[StructLayout(LayoutKind.Sequential, Pack = 1)]
struct IpHeader
{
  public byte VerLen;
  public byte TOS;
  public short TotalLength; 
  public short ID;
  public short Offset;
  public byte TTL;
  public byte Protocol;
  public short Checksum;
  public int SrcAddr;
  public int DestAddr;
}

The two things to note about the definition of the structure is that it is defined as a sequential structure which ensures that the order of the members and relative location of these members are not altered by the CLR.

Now that the structure is defined the next step is to populate the structure with data. In this case the data came from a call to the Receive method of the Socket class. To read IP header the socket was created using SocketType.Raw. The Receive method fills a byte array with the data and it is the first 20 bytes of this data that makes up the IP header. Because the structure that I have defined, and the structure of the data in these 20 bytes are a one to one match, using a language like C++ reading this data would be a relatively simple task requiring only a cast.

IpHeader *pHeader = (IpHeader*)packet;

With the structure of the IpHeader overlayed on the memory stream it is a matter of accessing the members of the structure. Unfortunately our structure is stored in managed memory and using code like the above in C# would require entering an unsafe code block. The following piece of code demonstrates how this could be achieved in C#.

IpHeader iphdr;
unsafe
{
  fixed ( byte *pData = packet)
  {
    iphdr = *(IpHeader*)pData;
  }
}
//Use iphdr...

For the above code to compile successfully you will have to flip the switch to allow unsafe code to be compiled. This can be achieved using either the /unsafe switch for the command line compiler or in the Visual Studio .NET project properties under Configuration Properties>Build you can set the Allow Unsafe Code Blocks to true.

The code in the unsafe block uses the fixed keyword to pin the packet structure in memory ensuring that the garbage collector does not shift the memory around under our feet. Because the memory is fixed it can now be used much like a standard C/C++ pointer allowing us to cast the block of memory to an IpHeader* and assign the pointer to iphdr structure.

Though this is a relatively simple piece of code there are a few points to be noted about this solution. First whenever we allow unsafe code blocks in a C# application we inhibit the CLR’s ability to verify the code. In this case, by fixing the data in memory and accessing it like a pointer the CLR can no longer check the array bounds and our code is open to a buffer overrun. The second point of concern with the fixed memory is that the garbage collector cannot shift this memory impacting the garbage collection process and the performance of the garbage collector if a collection is required. And finally this solution, as far as I know, can not be done in VB.NET, so it would have to be written in C# and the assembly referenced from VB.NET.

That brings me to the solution of using the marshaling provided by interop services. The clear advantage of this solution is that it can be applied in both C# and VB.NET and it does not require the use of unsafe code blocks therefore the code remains verifiable. Before I discuss this solution any further let me present a code snippet that demonstrates the solution.

IntPtr pIP = Marshal.AllocHGlobal( len );
Marshal.Copy( packet, 0, pIP, len );
iphdr = (IpHeader)Marshal.PtrToStructure( pIP, typeof(IpHeader) );
Marshal.FreeHGlobal( pIP );

Now the moment I wrote this piece of code it felt like a knife stabbing into my back. The first thing that happens is that a block of memory is allocated on the unmanaged heap. Since the memory is allocated from the unmanaged heap it does not impact the garbage collector in anyway. The problem is that the packet is stored in the managed heap so we need to first copy the data from the buffer in the managed heap to the buffer in the unmanaged heap using Marshal.Copy. Once the data resides in the unmanaged heap we can use the Marshal.PtrToStructure to marshal the data back to the managed heap in the form of our IpHeader structure. And finally we must free the unmanaged memory that we allocated.

This really gave me a sour taste in my mouth. Every packet that I picked up needs to be shifted from the managed heap to the unmanaged heap and then be marshaled back to managed heap. Are there words to describe this? Clearly I was not satisfied with this solution.

The options investigated so far have required somehow side stepping the way the CLR normally would go about its business. Introducing risks such as buffer overruns or even memory leaks if we fail to free the unmanaged memory we have allocated.

So is there a completely managed solution to the problem? Well yes there is and at first this might seem like it is really the long way around in comparison to the options we have explored so far. However after I present the code I will demonstrate why in this particular case it was actually less code than the previous solutions. This solution makes use of the BinaryReader to read the data directly into the structures members.

System.IO.MemoryStream stm = new System.IO.MemoryStream( packet, 0, len );
System.IO.BinaryReader rdr = new System.IO.BinaryReader( stm );
iphdr.VerLen = rdr.ReadByte();
iphdr.TOS = rdr.ReadByte();
iphdr.TotalLength = rdr.ReadInt16();
iphdr.ID = rdr.ReadInt16();
iphdr.Offset = rdr.ReadInt16();
iphdr.TTL = rdr.ReadByte();
iphdr.Protocol = rdr.ReadByte();
iphdr.Checksum = rdr.ReadInt16();
iphdr.SrcAddr = rdr.ReadInt32();
iphdr.DestAddr = rdr.ReadInt32();

This solution has it’s own set of advantages and disadvantages. Firstly the structure definition can loose the StructLayoutAttribute since the physical layout of the structure is no longer important. The primary advantage in my opinion of this code is that we are working with code that is 100% managed and there are no cute tricks that could end up tripping us up, although there are other aspects to this solution that could. Another advantage is particular to the case of reading network data, which I will address shortly.

The code creates a MemoryStream on the existing packet buffer and a BinaryReader is created to read the data from the MemoryStream. Then byte for byte (and now and then a int or short) the data is read into an instance of the structure.

As I said earlier, the next advantage is specific to the requirements of this particular case. As you know when reading data from a socket the data is in network byte order or big-endian form. This byte ordering is incompatible with Intel processors, which expect multi-byte numeric data types to be represented in little-endian form. Since the packet’s data is in big-endian we are required to convert each Int16 and Int32 (short and int) to little-endian form. I use IPAddress.NetworkToHostOrder to do the byte swapping for me, since this is required regardless of which of the above solutions where chosen, this would mean calling the function on each non-byte member of the struct. Using the last solution we investigated this could be accomplished in one step while filling the structure.

iphdr.VerLen = rdr.ReadByte();
iphdr.TOS = rdr.ReadByte();
iphdr.TotalLength = IPAddress.NetworkToHostOrder(rdr.ReadInt16());
iphdr.ID = IPAddress.NetworkToHostOrder(rdr.ReadInt16());
iphdr.Offset = IPAddress.NetworkToHostOrder(rdr.ReadInt16());
iphdr.TTL = rdr.ReadByte();
iphdr.Protocol = rdr.ReadByte();
iphdr.Checksum = IPAddress.NetworkToHostOrder(rdr.ReadInt16());
iphdr.SrcAddr = IPAddress.NetworkToHostOrder(rdr.ReadInt32());
iphdr.DestAddr = IPAddress.NetworkToHostOrder(rdr.ReadInt32());

The most obvious concern using this solution is the possibility of misaligned reads, e.g. reading a Byte where you should have read an Int. One mistake of this kind and all the data after that point are misaligned and make no sense. This solution also requires that you maintain both the structure and the code that populates the structure, if the structure changes in someway the code to read the structure needs to be updated. And even with medium sized structures you end up doing a lot of byte counting and checking that every read is performed in the correct order, which is very error prone.

I have found that including a constructor and/or a static method provides an elegant means of hiding the actual method used to perform the de-serialization. The following pieces of code demonstrate the two possible ways of creating a de-serialized packet using either a static method or constructor.

IpHeader iphdr = IpHeader.FromPacket( packet, len );

IpHeader iphdr = new IpHeader( packet, len );

Typically I implement both, and the static method just creates an instance of the structure using the appropriate constructor.

Conclusion

Though the above solutions are not the only solutions, most other solutions are some form of one of these. Alternatively you could use managed C++ and get the best of both worlds and the expense of verifiable code. The presented solutions are applicable whenever you want to read binary data into a structured form; regardless of the source of the data, be it a network byte stream, or data from a disk file.

Selecting an appropriate solution is dependent on your requirements and constraints; personally I tend towards using unsafe code blocks especially if the structures are large (call me lazy) or the final solution of reading the data byte for byte. I just can’t feel good about moving perfectly good memory all over the show.

Archive – Debugging WindowsIdentity and IsInRole

2009-11-07T17:32:00.001+02:00

This is one of those invaluable little utility functions, you never need it until you face a problem trying to determine why IsInRole is returning and unexpected value when you run your application in a non development production environment. Using this function you can quickly determine the list of roles or groups that IsInRole is matching against.

Framework 2.0 and Later

public string[] GetWindowsIdentityRoles(WindowsIdentity identity)
{
  if (identity == null) throw new ArgumentNullException("identity");

  IdentityReferenceCollection groups = identity.Groups.Translate(typeof(NTAccount));
  string[] roles = new string[groups.Count]; 
  for (int i = 0; i < groups.Count; ++i)
  {
    roles[i] = groups[i].Value; 
  }

  return roles;
}

Framework 1.0/1.1 (For that legacy code)

public static string[] GetWindowsIdentityRoles( WindowsIdentity identity )
{
  object result = typeof(WindowsIdentity).InvokeMember( "_GetRoles",
    BindingFlags.Static | BindingFlags.InvokeMethod | BindingFlags.NonPublic,
    null, identity, new object[]{identity.Token}, null );

  return (string[])result; 
}

Archive - Thread Local Storage in .NET

2009-11-01T15:21:00.002+02:00

Another repost from my original blog.
Those of you familiar with the intricacies of Win32 multi-threaded programming will be intimately familiar with thread local storage (TLS). And you might have wondered how .NET exposes this often useful construct.
Before we begin I would like to offer a brief description of what TLS is, for those of you that might not have had the fortune of learning Win32 multi-threaded programming. TLS is a means of storing data on a per-thread basis. Any methods accessing the data will access the data associated with the thread in which the method is running. And this is achieved without the method having any special knowledge of the thread in which it is executing.
Now the real question, how can we achieve the same results in the .NET managed environment? Well depending on your situation there are a number of options available. I will describe only 3 options here. First I will describe the more commonly known CallContext and then what in my experience is less widely known Thread Static variables and finally there is the thread data slots.

The CallContext
Most of you are probably familiar with the CallContext class and how it relates to .NET remoting. A CallContext is used to flow data across multiple calls with out having to pass the data along as some part of the argument list of each called method. And if the stored data implements the ILogicalThreadAffinative interface the data will flow across machine boundaries.
A call context is maintained by the .NET framework for each logical thread of execution. By storing data in the call context you are essentially storing data specific to the thread currently executing the method, and any method called in that thread of execution has access to the threads call context. As a simple example, if you wanted to maintain a count of the number of times a function was called per thread you could do some thing like the following.

class Class1
{
static void Main(string[] args)
{
System.Threading.Thread t1 = new System.Threading.Thread(new System.Threading.ThreadStart(ThreadFunction));
System.Threading.Thread t2 = new System.Threading.Thread(new System.Threading.ThreadStart(ThreadFunction));

// Start the threads
t1.Start();
t2.Start();

// Wait for the threads to complete
t1.Join();
t2.Join();

System.Console.Read();
} 

private const string PerThreadCallCounterKey = "CallCounter";
private static Random Rnd = new Random();

private static void ThreadFunction()
{
// Initialize the per-thread CallCounter
System.Runtime.Remoting.Messaging.CallContext.SetData(PerThreadCallCounterKey, 0);
// Pick a randon number of times to call the target method
int iterations = Rnd.Next(255); 
// Call the method iteration number of times
for (int i = 0; i < iterations; ++i)
{
DoTheWork();
}
DisplayCounterValue();
}

private static void DoTheWork()
{
// Get the current threads CallCounter from the CallContext
int counter = (int)System.Runtime.Remoting.Messaging.CallContext.GetData(PerThreadCallCounterKey);

// Increment the counter and store the new value in the CallContext
// Notice the pre-increment (++counter).
System.Runtime.Remoting.Messaging.CallContext.SetData(PerThreadCallCounterKey, ++counter);

//OK, so we updated the counter now do the real work of this method
//...
}

private static void DisplayCounterValue()
{
// Get the current threads CallCounter from the CallContext
int counter = (int)System.Runtime.Remoting.Messaging.CallContext.GetData(PerThreadCallCounterKey);
System.Console.WriteLine("The method was called {0} times from this thread", counter);
}
}

Notice how neither the DoTheWork or DisplayCounterValue methods have any knowledge of the calling thread. They are only aware of context information which is thread specific.

Thread Static Members
As an alternative to using the CallContext class, .NET provides support for what I call Thread Static Members. Thread static members for the most part act like normal static members except that they have per-thread storage rather than per-AppDomain. Declaring a thread static member is very similar to declaring a normal static member, except that the ThreadStaticAttribute attribute is applied to the declaration as follows.

[ThreadStatic]
private static int PerThreadCallCounter;

From this point on any thing that is done to the PerThreadCallCounter member affects the instance of this member associate with the current thread of execution. The following achieves the same results as the earlier example, only this time rather than using the CallContext class a thread static member is used.

class Class1
{
static void Main(string[] args)
{
System.Threading.Thread t1 = new System.Threading.Thread(new System.Threading.ThreadStart(ThreadFunction));
System.Threading.Thread t2 = new System.Threading.Thread(new System.Threading.ThreadStart(ThreadFunction));

// Start the threads
t1.Start();
t2.Start();

// Wait for the threads to complete
t1.Join();
t2.Join();
System.Console.Read();
} 


[ThreadStatic]
private static int PerThreadCallCounter;

private static Random Rnd = new Random();

private static void ThreadFunction()
{ 
// Pick a randon number of times to call the target method 
int iterations = Rnd.Next(255); 

// Call the method iteration number of times
for (int i = 0; i < iterations; ++i)
{
DoTheWork();
}
DisplayCounterValue();
}

private static void DoTheWork()
{
// Increment the static member associated with the current thread
PerThreadCallCounter++;

//OK, so we updated the counter now do the real work of this method
//...
}

private static void DisplayCounterValue()
{
// Display the value of the thread static member to the user
System.Console.WriteLine("The method was called {0} times from this thread", PerThreadCallCounter);
}
}

As you can see and I am sure you will agree this is a much simpler solution. However a word of caution, with this example the naming of the instance becomes critical, sooner or later you will need to come back to a piece of code and if you loose site of the fact that a particular static member is bound to a thread rather than the entire AppDomain you could be in for some interesting debugging in the early hours of the morning.

While thread static members appear to work just like there normal static member counter parts, there are a few caveats. Firstly you might be tempted to initialize your thread static members in a static constructor. Unfortunately the results might surprise you. At first inspection it might appear that your initialization was ignored, however this is not the case, it is just that the static constructor is not run per-thread, but per-AppDomain. That is it is only executed once which means that the Thread Static member is only initialized for one thread, the and the rest are left untouched. And no, you can not apply the ThreadStaticAttribute to the constructor, this attribute can only be applied to member variables (fields).

Of course as apposed to the CallContext solution the ThreadStatic member is limited to the AppDomain boundary, which for most requirements is sufficient.

Thread Data Slots

Thread data slots are allocated once for every thread by using the Thread.AllocateDataSlot(). Once a data slot has been allocated the slot can be used from any thread to access the data stored in the data slot for the executing thread. This most closely matches the workings of the TLS APIs in the Win32 API. Rather than bore you with another rendition of the demonstration application I will leave it to the reader to investigate this solution which is adequately documented in the MSDN documentation.

See Also:

Along similar lines as the ThreadStaticAttribute, you might also want to take a look at the ContextStaticAttribute. Especially for those of you interested in the potential of AOP offered by context bound objects.

Color Gradient

2009-11-01T15:12:00.001+02:00

Here is a quick routine I put together which is used to calculate discrete transitions from a start color to an end color in 255 steps. You could call this function in a loop to generate all the color transitions from the start color to the end color.

public Color Gradient(Color from, Color to, byte step)
{
   double stepFactor = (double)step / 255;
   return Color.FromArgb(
      (int)(from.R + ((to.R - from.R) * stepFactor)),
      (int)(from.G + ((to.G - from.G) * stepFactor)),
      (int)(from.B + ((to.B - from.B) * stepFactor)));
}

Re-throw InnerException and preserve the original StackTrace

2009-09-26T12:01:00.001+03:00

Repost from my original blog at the dotnetjunkies (03 March 2004)

One of the problems when throwing a new exception from with-in a catch handler is that the stack trace information captured for the initial exception is lost and a new stack trace is built from the point of the throw. Of course when throwing the new exception all that is required to circumvent this problem is to set the inner exception of the new exception to the initial exception that was caught by the catch handler.

However, on occasion, you want to throw the InnerException it self. Recently on the SADeveloper forum exactly this scenario arose. A poster on the forum was using reflection to invoke a method. The poster realized that exceptions thrown by methods invoked through reflection were wrapped in the InnerException of a TargetInvocationException. Now what the poster wanted to do was to catch the TargetInvocationException and then re-throw the InnerException. I assume the reason for this was that the caller of the method, which performed the reflection invoke, was not concerned with the current implementation detail and was only required to deal with the original exceptions. The only problem with this solution is that once the InnerException is rethrown, the stack trace no longer contained the original stack trace information.

Naturally curiosity got the better of me and I set out to see if I could find a solution. After all, this is what I enjoy most about my free time (between 2-3 in the morning), I get to do things I enjoy and that is learn how the internals work. On this occasion, I got lucky and the first idea I had worked. I new that the remoting infrastructure in fact did something very similar. When an exception is throw from the remoting server, the server side stack trace is preserved on the client side. This is done by setting the private member _remoteStackTraceString to the server side stack trace. Then when the StackTrace property of the exception is called, the _remoteStackTraceString is concatenated with the _stackTraceString and returned to the caller. So I figured that all that was required was the set the _remoteStackTraceString of the InnerException to the current StackTrace of the InnerException. Then when the InnerException is re thrown, the stack trace is replaced with the new stack trace, but the _remoteStackTraceString is preserved. And the end result is a complete stack trace as if the original exception being throw never even saw a TargetInvocationException. So the question is how do we go about manipulating the private _remoteStackTraceString, well you guessed it, reflection.

As usual, before I present the code for this I have to say, just because something works does not mean it is the right thing to do. But is was Fun... And now I know a little more about how the remoting mechanism and exceptions fit together.

public void test1()
{
  // Throw an exception for testing purposes
  throw new ArgumentException( "test1" ); 
}

void test2()
{
  try
  {  
    MethodInfo mi = typeof(Form1).GetMethod( "test1" );
    mi.Invoke( this, null );
  }
  catch( TargetInvocationException tiex )
  { 
    // NB: Error checking etc. excluded
    // Get the _remoteStackTraceString of the Exception class
    FieldInfo remoteStackTraceString = typeof(Exception).GetField("_remoteStackTraceString",
      BindingFlags.Instance | BindingFlags.NonPublic );

    // Set the InnerException._remoteStackTraceString to the current InnerException.StackTrace
    remoteStackTraceString.SetValue( tiex.InnerException, 
      tiex.InnerException.StackTrace + Environment.NewLine );

    // Throw the new exception
    throw tiex.InnerException;
  }
}

...

// Test the effect of the above code by calling test2() and handling 
// the exception that is thrown
try
{
  test2(); // Call the method that uses reflection to call another method
}
catch ( Exception ex )
{
  Console.WriteLine( ex.ToString() );
}

Silverlight – Ray casting engine

2009-09-24T22:38:00.001+03:00

I have been writing a little ray casting engine for Silverlight, this is a topic that I was very interested in some 12 or so years ago and the last time I did anything like this was all in C++. So I whipped out those old notes and references as started out writing the basic engine. So far it can handle multi-height textured walls, textured floors and ceilings, background textures, very basic lighting and in game objects that can be interacted with.

While testing the engine I found that my test cases resembled a pac man type game in a “3d” world so I thought what the heck and added some basic scoring, lives and a compass. The results can be seen here

Make no mistake, this is no master piece it is mostly some test code that I was using to test the engine. There are still some minor rendering artefacts that can sometimes be seen in the distance between the walls and the textured floors. The engine still suffers from minor cumulative rounding errors that degrades the quality of the generated scene, but all in good time.

Silverlight – SpriteSheet management with WriteableBitmap

2009-08-22T15:41:00.003+03:00

As part of my Silverlight education process I have been writing some games. First a few basic things like Sildoku and Peg Solitaire. Now I am advancing to something a bit more challenging, I am writting a small 2d racing game. For this I started with some of the fun parts, writing a Sprite manager, while this is still in the early stages I thought I would share one of my basic classes the SpriteSheet class.
For those of you who do not know what a sprite sheet is, it is an set of images placed in a grid layout and composed into one larger image. Often sequential images in the grid will represent frames in an animation of some action such as walking etc. Take a look at this Wikipedia link.
My sprite manager at this stage supports both static and animated sprites, using one or more sprite sheets as a source of the images. Here is the code for the SpriteSheet class.

public class SpriteSheet
{
  private BitmapSource _spriteSheetSource;
  private WriteableBitmap _spriteSheetBitmap;
  private int _sheetWidth;
  private int _sheetHeight;    

  public SpriteSheet(BitmapSource spriteSheetSource)
  {
    if (spriteSheetSource == null) throw new ArgumentNullException("spriteSheetSource");

    _spriteSheetSource = spriteSheetSource;
    _spriteSheetBitmap = new WriteableBitmap(_spriteSheetSource);
    _sheetWidth = _spriteSheetBitmap.PixelWidth;
    _sheetHeight = _spriteSheetBitmap.PixelHeight;
  }

  public WriteableBitmap GetBitmap(int x, int y, int width, int height)
  {
    WriteableBitmap destination = new WriteableBitmap(width, height);      
    GetBitmap(destination, x, y, width, height);
    return destination;
  }

  public void GetBitmap(WriteableBitmap targetBitmap, int x, int y, int width, int height)
  {
    // Validate incomming data
    if (targetBitmap == null) throw new ArgumentNullException("targetBitmap");
    if (x < 0 || x >= _sheetWidth) throw new ArgumentOutOfRangeException("x");
    if (y < 0 || y >= _sheetHeight) throw new ArgumentOutOfRangeException("y");
    if (width < 0 || (x + width > _sheetWidth)) throw new ArgumentOutOfRangeException("width");
    if (height < 0 || (y + height > _sheetHeight)) throw new ArgumentOutOfRangeException("height");

    // Get pixel buffers for the sprite sheet and the target bitmap
    int[] sourcePixels = _spriteSheetBitmap.Pixels;
    int[] targetPixels = targetBitmap.Pixels;

    // Calculate starting offsets into the pixel buffers      
    int sourceOffset = x + (y * _sheetWidth);      
    int targetOffset = 0;

    // Note that the offsets and widths are multiplied by 4, this is because Buffer.BlockCopy requires
    // byte offsets into the buffers and our buffers are integer buffers. To optimize this I have 
    // premultiplied to values so that the multiplication is removed from the loop
    int sourceByteOffset = sourceOffset << 2;
    int sheetByteWidth = _sheetWidth << 2;
    int targetByteWidth = width << 2;
    for (int row = 0; row < height; ++row)
    {
      Buffer.BlockCopy(sourcePixels, sourceByteOffset, targetPixels, targetOffset, targetByteWidth);
      sourceByteOffset += sheetByteWidth;
      targetOffset += targetByteWidth;
    }      
  }    

  public int Width
  {
    get { return _sheetWidth; }
  }

  public int Height
  {
    get { return _sheetHeight; }
  }
}

The interesting function in this class is the GetBitmap(WriteableBitmap targetBitmap, int x, int y, int width, int height) overload. This function is the work horse of the class. It is responsible for transferring a region of the source image starting at x, y to the new WriteableBitmap. The GetBitmap(int x, int y, int width, int height) overload calls this function with a pre-allocated WriteableBitmap of the correct dimensions.
Using the class is quite simple. Assume you have a couple of standard Image controls declared on your page, something like the following.

<UserControl x:Class="Vulcan.SL.TestApplication.MainPage"
xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation" 
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
xmlns:d="http://schemas.microsoft.com/expression/blend/2008" xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
mc:Ignorable="d" d:DesignWidth="640" d:DesignHeight="480">
  <Canvas x:Name="LayoutRoot">  
    <Image x:Name="mySprite1" Width="100" Height="100" Canvas.Left="0"/>
    <Image x:Name="mySprite2" Width="100" Height="100" Canvas.Left="110"/>
  </Canvas>
</UserControl>

You will notice that I have not set the Source of the images, we will do this in code using the GetBitmap function of the SpriteSheet class.
Next in the code behind file we need to load the image that and create an instance of the SpriteSheet class passing the image. The trick here is that you should only create the SpriteSheet instance once the image has been fully downloaded. Here is one way of doing this.

public MainPage()
{
  InitializeComponent();

  BitmapImage spriteSheetBitmap = new BitmapImage(new Uri("/Images/WindmillLeft.png", UriKind.Relative));      
  spriteSheetBitmap.CreateOptions = BitmapCreateOptions.None;
  spriteSheetBitmap.ImageOpened += new EventHandler<RoutedEventArgs>(image_ImageOpened);       
}

void image_ImageOpened(object sender, RoutedEventArgs e)
{
  BitmapImage spriteSheetBitmap = sender as BitmapImage;

  SpriteSheet spriteSheet = new SpriteSheet(spriteSheetBitmap);

  // Set the source of the mySprite1 to an image extracted from the SpriteSheet
  mySprite1.Source = spriteSheet.GetBitmap(0, 0, 224, 240);

  // Set the source of the mySprite2 to an image extracted from the SpriteSheet
  mySprite2.Source = spriteSheet.GetBitmap(2240, 0, 224, 240);
}

Here I create a BitmapImage class and set the CreateOptions to BitmapCreateOptions.None. This ensures that the image is created without delay, however the creation still takes place asynchronously so we need attach a handler to the ImageOpened event which indicates that the image has been downloaded and decoded, indicating that we can now use the image.
In the ImageOpened event handler we can construct our SpriteSheet and used the GetBitmap function to extract the regions of interest and assign them to the relevant Image instances. I have purposely not used instance members in these examples so that each piece of code is self contained, and of course I have forgone error checks etc. for the sake of clarity.
Note that the SpriteSheet does not perform any kind of caching of the regions that are extracted, this means that if you request the same region multiple times with the GetBitmap function you will receive new instances of WriteableBitmaps for each call. In my case I take care of the caching at a higher level. I have a SpriteFrameSet class which is a cache of the frames used for an animation sequence, internally this class uses the SpriteSheet to build an array of images ie. frames, and from that point on the array is referenced to retrieve each frame from the frame set.
As my code for the Sprite and AnimatedSprite classes matures I will hopefully find some time to release that on this blog.

Silverlight – My first Silverlight games published

2009-08-19T02:33:00.001+03:00

To day is somewhat of a milestone for me, after more than 15 years in the industry I have never released anything I have written into the wild. More than that, I do very little UI work, focusing mainly on backend server components.

So what is all my excitement about, well I have written 2 small Silverlight games and submitted them to Silver Arcade. Neither game is really ground breaking, they have served as an avenue gaining some basic experience with Silverlight. Each game was written in less than 24 hours so there are no fancy bells and whistles, heck they do not even have sound (Mostly because I do not even have speakers attached to my computer, no I do not play games :))

The first game is called Sildoku, yes you guessed it, it is a Sudoku clone. It has 4 levels of difficulty and each game is randomly generated on the fly. Try it here

The second game is Peg Solitaire. Which you can try here

Archive – Hacking my way across the process boundary

2009-08-18T13:00:00.002+03:00

This is another one of the posts that I am migrating from my previous blog. The post is based on an answer I provided on a news group post. A subsequent post provides a similar solution for .NET. This post was put up in early 2004.

About 2 years ago a C++/MFC question appeared on the news groups asking how to send windows messages to a ListView control in another process and receive the data returned in the LVITEM structure. At the time I came up with what I thought to be an imaginative solution and it worked for the op. Recently this question reappeared but this time for the .NET environment, a quick Google search and I pointed the OP to the original post, leaving the conversion to .NET as an exercise for the reader. Since the routine did the job again and I remember having some fun playing around with the routine so I thought I would revive it here. Now I just need to get around to converting it to .NET :)

In short you allocate a block of memory in the target process using VirtualAllocEx, this block must be big enough to hold both the LVITEM structure and any string data you expect back. You also declare an instance of the structure in your local process and setup all the necessary fields; the only field that is configured differently is the pszText member, which is defined as pointing to the block of memory in the target process offset by the sizeof the LVITEM structure. Then the local structure is moved to the target process using WriteProcessMemory. Once all the structures are in place and in the correct process all that remains is to send the message using SendMessage, and passing the address of the structure in the remote process as the lParam. On successful return of the SendMessage the remote process should contain the requested data and you can copy the data back to the local process using ReadProcessMemory. Once again the pszText pointer has to be fixed up in the local process to reference the local buffer offset again by the sizeof LVITEM.

The following C++ code provides an example of getting a item from a ListView hosted in another process.

const DWORD dwBufSize = 1024;

DWORD dwProcessID;
DWORD dwResult;
HANDLE hProcess;

BYTE *lpRemoteBuffer;

LVITEM lvItem = {0};

BYTE lpLocalBuffer[dwBufSize] = {0};

// Get the process id owning the window
::GetWindowThreadProcessId( hwndListView, &dwProcessID );

// Open the process wih all access (You may not have the rights to do this)
hProcess = ::OpenProcess( PROCESS_ALL_ACCESS, FALSE, dwProcessID );

// Allocate a buffer in the remote process
lpRemoteBuffer = (BYTE*)::VirtualAllocEx( hProcess, NULL, dwBufSize,
MEM_COMMIT, PAGE_READWRITE );

// Fill in the LVITEM struct, this is in your own process
// Set the pszText member to somewhere in the remote buffer,
// For the example I used the address imediately following the LVITEM stuct
lvItem.mask = LVIF_TEXT;
lvItem.iItem = 0;
lvItem.cchTextMax = 50;

// Point to after LVITEM in the remote buffer
lvItem.pszText = (LPTSTR)(lpRemoteBuffer + sizeof( LVITEM )); 

// Copy the local LVITEM to the remote buffer
::WriteProcessMemory( hProcess, (LPVOID)lpRemoteBuffer, 
  &lvItem, sizeof(LVITEM), NULL );

// Send the message
::SendMessage( hwndListView, LVM_GETITEM, 0, (LPARAM)lpRemoteBuffer);

// Read the struct back from the remote process into local buffer
::ReadProcessMemory( hProcess, (LPVOID)lpRemoteBuffer, lpLocalBuffer,
  dwBufSize, NULL );

//Fix pszText to point to same offset in local buffer
lvItem.pszText = (LPTSTR)(lpLocalBuffer + sizeof( LVITEM ));

// Clean-up
::VirtualFreeEx( hProcess, (LPVOID)lpRemoteBuffer, 0, MEM_RELEASE ); 
::CloseHandle( hProcess );

Silverlight – WriteableBitmap SetPixel extension method

2009-08-15T16:36:00.001+03:00

I am in the process of writing two interesting controls (At least interesting to me). For one of the controls I needed a way to directly set pixels on the WriteableBitmap with full support for alpha blending, the result is the following extension method.

using System;
using System.Windows.Media;
using System.Windows.Media.Imaging;

namespace ExtensionMethods
{
  public static class WriteableBitmapExtensions
  {
    public static void SetPixel(this WriteableBitmap wb, int x, int y, Color color)
    {
      // Validate that the x,y coordinates are within the bounds of the bitmap
      if (x < 0 || x >= wb.PixelWidth || y < 0 || y >= wb.PixelHeight) return;
      
      int offset = (y * wb.PixelWidth) + x; 
      int pixel;
      int[] buffer = wb.Pixels;

      if (color.A == 255)
      {                
        // Since no alpha blending is required we can directly use the incomming color
        // compose the integer that needs to be written to the pixel buffer.
        pixel = (color.A << 24) | (color.R << 16) | (color.G << 8) | color.B;
      }
      else
      {
        // Get the current pixle in the pixel buffer that we need to blend with
        pixel = buffer[offset];
          
        // calculate the alpha channel ratios used for the blend of 
        // the source and destination pixels
        double sourceAlpha = color.A / 255.0;
        double inverseSourceAlpha = 1 - sourceAlpha;

        // Extract the color components of the current pixel in the buffer
        byte destA = (byte)(pixel >> 24);
        byte destR = (byte)(pixel >> 16);
        byte destG = (byte)(pixel >> 8);
        byte destB = (byte)pixel;
        
        // Calculate the color components of the new pixel. 
        // This is the blend of the destination pixel and the new source pixel
        byte pixelA = (byte)((color.A * sourceAlpha) + (inverseSourceAlpha * destA));
        byte pixelR = (byte)((color.R * sourceAlpha) + (inverseSourceAlpha * destR));
        byte pixelG = (byte)((color.G * sourceAlpha) + (inverseSourceAlpha * destG));
        byte pixelB = (byte)((color.B * sourceAlpha) + (inverseSourceAlpha * destB));

        // Reconstitute the color components into an int to be written to the pixel buffer
        pixel = (pixelA << 24) | (pixelR << 16) | (pixelG << 8) | pixelB;
      }

      // Write new pixel to the pixel buffer
      buffer[offset] = pixel;
    }
  }
}

If you are interested, the 2 controls I have written are

TextureSurface – A control which supports direct manipulation of the pixel buffer. The convenience is that there is no need for the developer to manage the WriteableBitmap and the Image control and there are precooked functions for setting pixels with alpha channel support etc.

ImageEx – This is an enhanced Image control which supports rendering only a portion of the source image, the purpose is to provide a means of rendering regions from a source image to be used like a sprite sheet.

Both controls are quite functional, but being quite new to Silverlight and not having done any WPF I am a little concerned that I have not made the most efficient use of the Control life cycle and feel like I have hacked a few things to work. Anyone out there willing to take a look at the code and make a few recommendations?

Silverlight – Set focus to the silverlight control

2009-08-14T12:26:00.001+03:00

When loading a web page which hosts a Silverlight application, I noticed that before interacting with the Silverlight application the user was required to first click on the application so that it got input focus. It was immediately obvious that I would need to use a small piece of java script to set the focus to the control. This is how I got it to work.

1. Give the <object> element in the web page an ID
2. Pass the ‘onLoad’ parameter on the Silverlight application assigning a JavaScript function that will focus to application in the browser.

<object id="silverlightControl" data="data:application/x-silverlight-2," type="application/x-silverlight-2" width="100%" height="100%">
  <param name="source" value="ClientBin/DragSnapDemo.xap"/>
  <param name="onError" value="onSilverlightError" />
  <param name="onLoad" value="silverlightControlHost_Load" />
  <param name="background" value="white" />
  <param name="minRuntimeVersion" value="3.0.40624.0" />
  <param name="autoUpgrade" value="true" />
  <a href="http://go.microsoft.com/fwlink/?LinkID=149156&v=3.0.40624.0" style="text-decoration:none">
    <img src="http://go.microsoft.com/fwlink/?LinkId=108181" alt="Get Microsoft Silverlight" style="border-style:none"/>
  </a>
</object>

3. Finally write the JavaScript function that is called when the Silverlight application has be loaded

function silverlightControlHost_Load(sender, args) 
{
  var control = document.getElementById("silverlightControl");
  control.focus();
}

The trick here is that the JavaScript function is only called once the Silverlight application has been fully downloaded and loaded into the browser. To achieve this I used the onLoad event of the application.

Range<> data type - Examples for XNA

2009-04-20T16:01:00.005+03:00

During the course of some hobby projects I like to take the time to investigate ways I might be able to provide cleaner more intuitive interfaces between the various components of the software. Currently I am building a small game and decided to write everything from scratch, mostly as a learning experience. Currently I am working on the Particle System, and besides the fact that there a hundreds of implementations out there, and I have personally written more than a few over the years, I always seem to learn something new.

As with most particle systems I would imagine, I have a class that provides the initial setup of the particle system, the values that the particle emitter works with to select the initial starting point, velocity, colour, size, lifespan etc, and how those values change over the life of the particle. Typically such a class might look something like the following fragment

  public class ParticleSystemSettings
  {
    public Color MinColorStart
    {
      get;
      set;
    }

    public Color MaxColorStart
    {
      get;
      set;
    }

    public Color MinColorEnd
    {
      get;
      set;
    }

    public Color MaxColorEnd
    {
      get;
      set;
    }

    public float MinLifeSpan
    {
      get;
      set;
    }

    public float MaxLifeSpan
    {
      get;
      set;
    }
  }

Using the above settings class the particle emitter would randomly select a starting colour between MinColorStart and MaxColorStart, likewise it would randomly select the final target colour for the particle in the range of MinColorEnd and MaxColorEnd. The lifespan of the particle would randomly be selected to fall between MinLifeSpan and MaxLifeSpan and so on.

As you can imagine a fully fleshed out Settings class can become quite elaborate, so I thought I would create a Range type class something that would allow me to write code along the following lines.

  public class ParticleSystemSettings
  {
    public Range<Color> StartColorRange
    {
      get;
      set;
    }

    public Range<Color> EndColorRange
    {
      get;
      set;
    }

  
    public Range<float> LifeSpanRange
    {
      get;
      set;
    }
  }

Clearly this is much less noisy, but besides the arguably more readable interface I also hope to gain some functional enhancements, especially when it comes to selecting values between the ranges and interpolating from one value to the next.

For example, the following code demonstrates how I would like to be initializing an instance of the ParticleSystemSettings class.

ParticleSystemSettings settings = new ParticleSystemSettings();

settings.StartColorRange = new Range<Color>(Color.Yellow, Color.Orange);
settings.EndColorRange = new Range<Color>(Color.Orange, Color.Red);
settings.LifeSpanRange = new Range<float>(0.2f, 0.5f);

And the the following is an example of how a new particle could be initialized

Particle particle = new Particle();
particle.LifeSpan = settings.LifeSpanRange.Random();
particle.ColorRange = new Range<Color>(
  settings.StartColorRange.Random(),
  settings.EndColorRange.Random());

And the final piece of the puzzle, calculating the appropriate value from the particles ranges based on the current progression of the particle through it’s lifespan. The following would typically be done in the Update method of the particle.

float lerpAmount = particle.Age / particle.LifeSpan;

Color renderColor = particle.ColorRange.Lerp(lerpAmount);
float renderSize = particle.SizeRange.Lerp(lerpAmount);

From these examples, you should be notice that the goal for our Range type implementation is to provide not only a container for start and end points of a range, but also methods to select a random value from the range as well as perform a linear interpolation (lerp) on the range. And most importantly the Range type should support this for any number of base types ranging from floats, Colors, Vector2, Vector3 even between dates if you so desired.

So with a basic outline of what I wanted to achieve I went through essentially two iterations before settling on a final solution. I will share both solutions and highlight a few of the pros and cons I have come across. I will start with saying that neither is perfect, but they do achieve the core goals albeit with some caveats.

Below is the complete code for my first implementation of the Range type.

  public struct Range<T>
  {
    private T _start;
    private T _end;
    private Func<T, T, float, T> _lerp;
 
    public Range(T value, Func<T, T, float, T> lerp)
      : this(value, value, lerp)
    {
    }

    public Range(T start, T end, Func<T, T, float, T> lerp)
    {
      _start = start;
      _end = end;
      _lerp = lerp;
    }

    public T Start
    {
      get { return _start; }
    }

    public T End
    {
      get { return _end; }
    }

    public T Lerp(float amount)
    {
      if (_lerp == null) return _start;
      return _lerp(_start, _end, amount);
    }

    public T Random()
    {
      return Lerp(Utilities.GetRandomFloat());
    }
  }

First some things you will notice,

The type is defined as a struct, since literally hundreds if not thousands of particles will be initialized per frame I wanted to ensure that the minimum of objects are created on the heap.

The range constructor requires that an appropriate Lerp functor is provided. This deviates from my initial construction syntax and was one of the motivators to explore alternative implementations. This signature of the lerp argument matches the implementation of Lerp on the XNA Vector2, Vector3 and Color types, but I will need to provide a custom implementation for interpolating floats or any other type that does not provide a ready made Lerp function of sorts.

The Utilities.GetRandomFloat() just returns a random float value between 0.0f and 1.0f.

The next bit of code shows a few examples of how this implementation of the Range type would be used. For this example I have used a simple Lambda expression to provide the Lerp implementation for the float data type, later we will explore a more reusable solution.

// Initialize a few ranges
Range<Vector2> positionRange = new Range<Vector2>(Vector2.Zero, Vector2.One, Vector2.Lerp);
Range<Color> colorRange = new Range<Color>(Color.White, Color.Black, Color.Lerp);
Range<float> floatRange = new Range<float>(0.0f, 5.0f,
  (start, end, amount) => { return start + ((end - start) * amount); });

// Get a value midway through the range
Vector2 position = positionRange.Lerp(0.5f);
Color color = colorRange.Lerp(0.5f);
float value = floatRange.Lerp(0.5f);

Of course having to pass a Lambda expression every time you wanted to use a Range on a type that does not provide a Lerp function in some form or the other would be very error prone. The obvious solution is to create some static helper methods in a static class and as we require additional lerp functions we can build on this library. We could go one step further and provide factory functions to create type specific Ranges that would provide the Lerp function internally that way we do not need to pass it every time. An example of this might look like the following.

public static class Range
{
  // Factory Functions
  public static Range<Vector2> CreateVector2(Vector2 start, Vector2 end)
  {
    return new Range<Vector2>(start, end, Vector2.Lerp);
  }

  public static Range<Color> CreateColor(Color start, Color end)
  {
    return new Range<Color>(start, end, Color.Lerp);
  }

  public static Range<float> CreateFloat(Color start, Color end)
  {
    return new Range<Color>(start, end, LerpFloat);
  }

  // Custom Lerp functions
  public static float LerpFloat(float start, float end, float amount)
  {
    return start + ((end - start) * amount);
  }

}

You will notice that I named the class Range, this seems to conflict with the name of the generic struct, however the CS compiler is “smart” enough to distinguish which type is being referenced in the code and while a name like RangeHelper or something similar might be a safer option, I liked the symmetry in the following code.

// Initialize a few ranges
Range<Vector2> positionRange = Range.CreateVector2(Vector2.Zero, Vector2.One);
Range<Color> colorRange = Range.CreateColor(Color.White, Color.Black);
Range<float> floatRange = Range.CreateFloat(0.0f, 5.0f);

There you have it, the first iteration of a passable Range type that met most of the goals I initially set out to achieve. I only have one major concern, and that is of performance. I do not even own an XBOX 360 so I have no idea what the performance impact is of calling Func<> delegate thousands of times per frame. On the notebook I am using to write this post, the code easily achieves about 30,000 (thirty thousand) calls per frame, but I have no clue how efficient this would be on the XBOX 360. So what are my alternatives?

Well, having used C and latter C++ since ‘89 I grew with the evolution of C++ templates and one aspect of template that would have come in handy here would have been support for template specialization. Essentially you can provide a specialized implementation of a template for a specific type, then when ever you declare a template of that type the specialized implementation is used rather than the “generic” implementation. Cool, but generics do not offer this functionality so what can I do?

One option might be to make the Range type a class (reference type), and provide specialized implementations which inherit from Range<T>, for example class FloatRange : Range<float>. The big problem with this is that I would end up creating millions of objects on the heap that need to be garbage collected resulting in significant performance degradation. Of course I could work around this as well since my particles are cached, I could make sure I reuse the member instances rather than recreate new ones each time. Maybe this is the route I should have gone. My only concern is this would require the developer to be very conscious of how the type is used to ensure optimal performance, no I would like to stick to the struct option.

So the next take on the solution required basically to declarations, the Range type and extension methods which provided the illusion of “type specialization”. The Range type is significantly simplified and no longer provides an implementation of Lerp or Random, these have been delegated to the realm of extension methods.

Here is the new code for the Range type

public struct Range<T>
{
  private T _start;
  private T _end;

  public Range(T value)
    : this(value, value)
  {
  }

  public Range(T start, T end)
  {
    _start = start;
    _end = end;
  }

  public T Start
  {
    get { return _start; }
    set { _start = value; }
  }

  public T End
  {
    get { return _end; }
    set { _end = value; }
  }
}

As you will notice, the Range type now only contains the start and end points of the range without any implied functionality. The following set of extension methods provide the functionality we expect from the Range type and is specialized for each type.

public static class XnaRangeExtensions
{
  public static float Lerp(this Range<float> range, float amount)
  {
    return range.Start + ((range.End - range.Start) * amount);
  }

  public static Vector2 Lerp(this Range<Vector2> range, float amount)
  {
    return Vector2.Lerp(range.Start, range.End, amount);
  }

  public static Vector3 Lerp(this Range<Vector3> range, float amount)
  {
    return Vector3.Lerp(range.Start, range.End, amount);
  }

  public static Color Lerp(this Range<Color> range, float amount)
  {
    return Color.Lerp(range.Start, range.End, amount);
  }

  public static float Random(this Range<float> range)
  {
    return Lerp(range, Utilities.GetRandomFloat());
  }

  public static Vector2 Random(this Range<Vector2> range)
  {
    return Lerp(range, Utilities.GetRandomFloat());
  }

  public static Vector3 Random(this Range<Vector3> range)
  {
    return Lerp(range, Utilities.GetRandomFloat());
  }

  public static Color Random(this Range<Color> range)
  {
    return Lerp(range, Utilities.GetRandomFloat());
  }

  public static bool IsEmpty(this Range<float> range)
  {
    return range.Start == range.End;
  }

  public static bool IsEmpty(this Range<Vector2> range)
  {
    return range.Start == range.End;
  }

  public static bool IsEmpty(this Range<Vector3> range)
  {
    return range.Start == range.End;
  }

  public static bool IsEmpty(this Range<Color> range)
  {
    return range.Start == range.End;
  }
}

Since this is the implementation I went with there are a few additional methods like the IsEmpty methods which identify empty Ranges. Lets see how this implementation of the Range class would be used.

// Initialize a few ranges
Range<Vector2> positionRange = new Range<Vector2>(Vector2.Zero, Vector2.One);
Range<Color> colorRange = new Range<Color>(Color.White, Color.Black);
Range<float> floatRange = new Range<float>(0.0f, 5.0f);

// Get a value midway through the range
Vector2 position = positionRange.Lerp(0.5f);
Color color = colorRange.Lerp(0.5f);
float value = floatRange.Lerp(0.5f);

Syntactically this code matches exactly our original requirements, even if it required the syntactic sugar of extension methods, but to be honest, I was not dissatisfied with syntax imposed by the first implementation. So which option is better, well you can rest assured I will be evolving my thinking on this as well as possible implementation routes, hopefully with the aid of your input. As new and better alternatives evolve I will definitely post updates.

SQL Injection - Are parameterized queries safe?

2009-04-11T19:04:00.001+03:00

This is a repost and rework of a popular blog entry from my previous blog, the original post can be found here.

SQL Injection is one of those vulnerabilities that crop up without even realizing it. Attackers potentially use SQL Injection to

Bypass authentication
Gain access to sensitive information
Interrupt system availability by tampering with or destroying data
Elevate privileges by tampering with data

As most developers already know, a few of the key ways to protect against SQL injection is to

Validate user input to ensure that the input conforms to the business requirements, and ensure that suspicious input is filtered to reduce the possible attack vectors.
Apply the principals of least privilege to further limit the scope of a successful hack
Use parameterized SQL queries rather than building SQL statements dynamically using string concatenation

Following the above guidelines will go along way to protect your software from a range of strategies used by potential hackers to penetrate your systems. This is not a complete guide, it is just a starting point, I am not even talking about the various web site vulnerabilities like cross site scripting etc.

The goal of this post is to demonstrate a scenario where parameterized queries could still pose a potential vulnerability. Using the following code as an example, a .NET developer might feel that the code is reasonably secure, using a nice parameterized query to a stored procedure.

oCmd.CommandText = "VulnerableDynamicSQL";
oCmd.CommandType = CommandType.StoredProcedure;
oCmd.Parameters.Add( "@userName", strUserName);
using (oCon)
{
  oCon.Open();
  string result = (string)oCmd.ExecuteScalar();
}

Everything seems fine, but unfortunately the code in the stored procedure could still pose a problem to the unsuspecting caller. The following rather contrived implementation of the stored procedure would leave the door wide open to SQL injection.

create proc VulnerableDynamicSQL(@userName nvarchar(25)) as
  declare @sql nvarchar(255)
  set @sql = 'select TelephoneNumber from users where UserName = ''' + @userName + ''''
  exec sp_executesql @sql

go

For example, the user input below, passed to the above stored procedure demonstrates a simple SQL Injection attack

';drop table users --

This input would result in the procedure formulating and executing the following SQL statement;

select TelephoneNumber from users where UserName = '';drop table users –-'

I have chosen the above for simplicity and obviously this would require adequate permissions to be successful, however this does not make the example any less significant. Had the procedure been a procedure used to authenticate users of a system; only a slightly more complex injection would be required to bypass the authentication and gain unauthorized admin access to the system.

As I mentioned above, the procedure could be written without using dynamic SQL, and resulted in more secure implementation. However there are situations in which dynamic SQL is indispensible and this raises the question, Can dynamic SQL be used more securely? The answer is a definite ‘YES’. Firstly you should always consider if you require dynamic SQL normally there is an alternate solution that does not require dynamic SQL. However if you have exhausted all possibilities and the only recourse is dynamic SQL then there is a safer way to use it. Just like we are able to use parameters for our SQL statements from within .NET, so can you use parameters for your dynamic SQL. The following procedure is a reimplementation using parameterized dynamic SQL.

create proc SaferDynamicSQL(@userName nvarchar(25))  as
  declare @sql nvarchar(255)
  set @sql = 'select TelephoneNumber from users where UserName = @p_userName'
  exec sp_executesql @sql, N'@p_userName nvarchar(25)', @p_userName = @userName

go

As you can see in this case I have defined a parameter to be used in the dynamic SQL statement called @p_userName. This parameter is defined as part of the call to sp_executesql and its value set in the same call.

Don’t make the mistake of thinking that security alone will prevent users from performing a successful SQL injection. It might prevent the user from dropping your tables, but you will still be open to many other forms of attack. When ever you concatenate strings to build SQL statements think carefully of the potential implications. Security requires a mindset where you are always questioning the implications of your decisions and even questioning things you might not have been responsible for.

And most importantly: Always validate user input.

Extension Methods: In<> and Between<>

2009-04-11T00:43:00.004+03:00

For my first real post I thought I would kick off with something light. I was writing some code recently and realized that the code readability would benefit from two simple extension methods, In<> and Between<>.

I often find myself writing code along the lines of

if (x >= 0 && x <= 10) ...
or
if (new[] {1,2,3}.Contains(x)) ...

So I thought I would throw two extension methods at the problem, I was looking for something that would give me the following syntax.

if (x.Between(0, 10)) ...
and
if (x.In(1,2,3)) ...

The result of my first attempt is the code below, note there are a few overloads to support various alternatives and customizing the comparison.

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

namespace DotNetWarrior
{
  public static class ExtensionMethods
  {
    public static bool In<T>(this T value, params T[] values)
    {
      return ExtensionMethods.In(value, null, values);
    }

    public static bool In<T>(this T value, IEqualityComparer<T> comparer, params T[] values)
    {   
      return In(value, comparer, values as IEnumerable<T>);
    }

    public static bool In<T>(this T item, IEnumerable<T> values)
    {
      return In(item, null, values);
    }

    public static bool In<T>(this T value, IEqualityComparer<T> comparer, IEnumerable<T> values)
    {
      return values.Contains(value, comparer);
    }

    public static bool Between<T>(this T item, T min, T max)
    {
      return ExtensionMethods.Between(item, null, min, max);
    }

    public static bool Between<T>(this T item, IComparer<T> comparer, T min, T max)
    {
      if (comparer == null)
      {
        comparer = Comparer<T>.Default;
      }   
      if (comparer.Compare(min, max) == 1) throw new ArgumentException("min must be less than or equal to max.");

      return (comparer.Compare(item, min) >= 0) && (comparer.Compare(item, max) <= 0);
    }
  }
}

Well, I hope you find this useful. Till I blog again.

Welcome to my new Blog

2009-04-11T00:33:00.001+03:00

Well it has been nearly two years since I last actively blogged. Recently I felt inspired to try and pickup on my community involvement, so I thought why not start blogging again. This is the start of that experiment.

For the most part I will be blogging about .NET and some C++. Though these days my focus is probably less techie than I would like it to be I will try to blog about the hobby tasks that I do and which inspire me to continue learning more about the technologies I am involved with. Mostly it will cover the random things I toy with in my own time.

I hope you will find what I share interesting and most importantly I hope to see your comments on my posts, especially if you have inputs that help me learn more about a topic.