Adapting the Microsoft Chart WebControl to MVC

The Chart control for ASP.Net that comes baked into .NET 4 or as an add-on to .NET 3 is useful but it is built around the WebForms rendering model which is uncomfortable in MVC applications. There is no pretty way to embed the WebChart control out-of-the-box. Solutions I have seen revolve around either giving up on the MVC separation and embedding the control into a View or creating custom web user controls for each chart and treating these as partial views. The former solution will only work with the WebForm view engine and not Razor or other view engines and the latter is just messy. Either way it feels like walking around with toilet paper stuck to your shoe. A third way is to return the image bytes of from a Chart object created in the controller as a FileResult. This works but you lose the image map tooltips.

The crux of the problem is that Chart is a DataBoundControl which is designed to magically generate its own HTML and to serve an image resource to itself when the rendered HTML is interpreted. It isn’t really meant to have an external controller tell it what to do. However, the Chart control has some nice features:

  1. It generates cross-browser friendly output
  2. It generates mouseover tooltips
  3. It doesn’t require Flash, Silverlight or JavaScipt because it uses MAP and AREA elements to create the tooltips
  4. With a little coercion, it will generate its image resource for you as a byte array which means you can alternatively embed the chart in an alternate resource like a PDF or other document envelope

Chart the MVC Way

Having decided that the Chart control does something we want, can we bend it to the MVC rendering model while preserving the nice tooltip image maps? The answer is yes we can. I have created a handful of extension methods that turn Chart on its head and allow you to render it out of a Controller class as an ActionResult. I’ll show you how things look in the View and Controller and then walk you through how it works.

View

<% Html.RenderAction( "PerformanceHistoryChart", new { id = Model.Id, shareClass = Model.ShareClass } ); %>

Controller

[OutputCache( Duration = 10, VaryByParam = "id;shareClass" )]
public ActionResult PerformanceHistoryChart( Guid id, string shareClass )
{
    return this.RenderChartMap( "PerformanceHistoryImage", id, shareClass, NewPerformanceHistoryChart );
}

[OutputCache( Duration = 10, VaryByParam = "id;shareClass" )]
public ActionResult PerformanceHistoryImage( Guid id, string shareClass )
{
    return this.RenderChartImage( id, shareClass, NewPerformanceHistoryChart );
}

private static Chart NewPerformanceHistoryChart( Guid id, string shareClass )
{
    Chart chart = new Chart();
    var series = perfChart.Series.Add( "Default" );
    var area   = perfChart.ChartAreas.Add( "ChartArea" );
    var values = ReportUtility.GetNetReturnOnValuePercentageHistory( id, shareClass );
    series.Points.DataBindXY( values.Item1, values.Item2 );
    series.ToolTip = "Fiscal Year: #VALX, Growth: #VALY{P}";
    area.AxisY.Title = "%";
    area.AxisY.LabelStyle.Format = "{P2}";
    return chart;
}

What’s going on in the View is that we are rendering the result of calling PerformanceHistoryChart on the controller. PerformanceHistoryChart renders HTML which includes an IMG tag reference to the PerformanceHistoryImage action which streams back the chart image as a PNG.PerformanceHistoryChart and PerformanceHistoryImage make use of my Chart to MVC adapter extension methods to do their work. There are two sets of extension method overloads:

  • this.RenderChartMap
  • this.RenderChartImage

In order to render any chart to a browser you need to provide two action methods. One of them calls RenderChartMap which generates HTML and the other calls RenderChartImage which returns the image as a FileResult for the IMG tag generated by RenderChartMap. Both extension methods accept a factory Func delegate which they use to create the Chart object that they manipulate internally. I’ve created overloads which accept 1 to 5 arguments.

MvcChart Extension Method Adapter Class

I’m sure this could be made more elegant but my first cut is working well. One limitation of my implementation is that you need a pair of extension method overloads that has enough arguments for your Chart factory Func  to work. Another issue is that you need to have an explicit route defined for the Actions which return the chart image FileContentResult. The reason is that the Chart control always appends a ?<some-guid> which is part of the caching mechanism it uses for storing images when it is rendering itself as a WebForms control. Therefore, I need to have an explicit route without any query string and allow the query string the Chart control generates to dangle off the end. My assumption is that the arguments will be passed in order from left to right in the URL as they appear in the method call. Also, since we are taking over rendering the Chart control via our Controller we give up the baked-in image caching. This is probably not much of an issue but it makes sense to use OutputCaching attributes to reduce the hits on the Chart factory Funcs and therefore your database.

Here’s my MvcChart class which contains the adapter extension methods. Happy coding.

using System.IO;
using System.Web.UI;
using System.Web.UI.DataVisualization.Charting;

namespace System.Web.Mvc
{
    /// <summary>
    /// <para>This class adapts the System.Web.UI.DataVisualization.Charting.Chart API to something
    /// more friendly to ASP.Net MVC by attaching extension methods to the Controller type.Requires
    /// an explicit route mapping for all arguments. The arguments will be inserted into the Image 
    /// generating URL in order.</para>
    /// <para>In each controller we need a pair of ActionMethods. One generates the IMG, MAP and AREA tags.
    /// The other streams the chart PNG. The URL to the chart PNG method is referenced by the imageActionName
    /// parameter in the RenderChartMap() method call. We also need a factory method which generates the Chart
    /// object instance. The chart factory is passed as a delegate to these adapter extension methods.</para>
    /// <remarks>In order to render each chart in a browser, the factory method must be executed twice.
    /// Consider using the OutputCache attribute to reduce hits on the data backend.</remarks>
    /// </summary>
    public static class MvcChart
    {
        /// <summary>
        /// Render img tag and associated image map for a chart.
        /// </summary>
        /// <typeparam name="T">Type of the factory argument.</typeparam>
        /// <param name="imageActionName">Method name in this controller that streams the chart image.</param>
        /// <param name="arg">Id used by the chart factory to find the data to generate the chart.</param>
        /// <param name="chartFactory">Delegate capable of generating a new Chart instance.</param>
        /// <returns>ContentResult that generates HTML for the chart.</returns>
        public static ContentResult RenderChartMap<T>( this Controller controller, string imageActionName,
            T arg, Func<T, Chart> chartFactory )
        {
            Chart chart = chartFactory.Invoke( arg );
            //FWIW: ImageLocation URL will have ?{some-guid} appended which is part of its classic WebForms ASP.Net
            //web control rendering model
            chart.ImageLocation = string.Format( "{0}{1}/{2}/{3}/", 
                GetApplicationPath( controller ), 
                GetControllerName( controller ), 
                imageActionName, 
                arg );
            return RenderChartMap( chart );
        }

        /// <summary>
        /// Render img tag and associated image map for a chart.
        /// </summary>
        /// <typeparam name="T1">Type of the first factory argument.</typeparam>
        /// <typeparam name="T2">Type of the second factory argument.</typeparam>
        /// <param name="controller">Controller instance.</param>
        /// <param name="imageActionName">Method name in this controller that streams the chart image.</param>
        /// <param name="arg1">Id used by the chart factory to find the data to generate the chart.</param>
        /// <param name="arg2">Second parameter used by the chart factory.</param>
        /// <param name="chartFactory">Delegate capable of generating a new Chart instance.</param>
        /// <returns>ContentResult that generates HTML for the chart.</returns>
        public static ContentResult RenderChartMap<T1,T2>( this Controller controller, string imageActionName, 
            T1 arg1, T2 arg2, Func<T1, T2, Chart> chartFactory )
        {
            Chart chart = chartFactory.Invoke( arg1, arg2 );
            chart.ImageLocation = string.Format( "{0}{1}/{2}/{3}/{4}/", 
                GetApplicationPath( controller ), 
                GetControllerName( controller ), 
                imageActionName, 
                arg1, 
                arg2 );
            return RenderChartMap( chart );
        }

        /// <summary>
        /// Render img tag and associated image map for a chart.
        /// </summary>
        /// <typeparam name="T1">Type of the first factory argument.</typeparam>
        /// <typeparam name="T2">Type of the second factory argument.</typeparam>
        /// <typeparam name="T3">Type of the third factory argument.</typeparam>
        /// <param name="controller">Controller instance.</param>
        /// <param name="imageActionName">Method name in this controller that streams the chart image.</param>
        /// <param name="arg1">Id used by the chart factory to find the data to generate the chart.</param>
        /// <param name="arg2">Second parameter used by the chart factory.</param>
        /// <param name="arg3">Third parameter used by the chart factory.</param>
        /// <param name="chartFactory">Delegate capable of generating a new Chart instance.</param>
        /// <returns>ContentResult that generates HTML for the chart.</returns>
        public static ContentResult RenderChartMap<T1, T2, T3>( this Controller controller, string imageActionName,
            T1 arg1, T2 arg2, T3 arg3, Func<T1, T2, T3, Chart> chartFactory )
        {
            Chart chart = chartFactory.Invoke( arg1, arg2, arg3 );
            chart.ImageLocation = string.Format( "{0}{1}/{2}/{3}/{4}/{5}/",
                GetApplicationPath( controller ),
                GetControllerName( controller ),
                imageActionName,
                arg1,
                arg2,
                arg3 );
            return RenderChartMap( chart );
        }

        /// <summary>
        /// Render img tag and associated image map for a chart.
        /// </summary>
        /// <typeparam name="T1">Type of the first factory argument.</typeparam>
        /// <typeparam name="T2">Type of the second factory argument.</typeparam>
        /// <typeparam name="T3">Type of the third factory argument.</typeparam>
        /// <typeparam name="T4">Type of the fourth factory argument.</typeparam>
        /// <param name="controller">Controller instance.</param>
        /// <param name="imageActionName">Method name in this controller that streams the chart image.</param>
        /// <param name="arg1">Id used by the chart factory to find the data to generate the chart.</param>
        /// <param name="arg2">Second parameter used by the chart factory.</param>
        /// <param name="arg3">Third parameter used by the chart factory.</param>
        /// <param name="arg4">Fourth parameter used by the chart factory.</param>
        /// <param name="chartFactory">Delegate capable of generating a new Chart instance.</param>
        /// <returns>ContentResult that generates HTML for the chart.</returns>
        public static ContentResult RenderChartMap<T1, T2, T3, T4>( this Controller controller, string imageActionName,
            T1 arg1, T2 arg2, T3 arg3, T4 arg4, Func<T1, T2, T3, T4, Chart> chartFactory )
        {
            Chart chart = chartFactory.Invoke( arg1, arg2, arg3, arg4 );
            chart.ImageLocation = string.Format( "{0}{1}/{2}/{3}/{4}/{5}/{6}/",
                GetApplicationPath( controller ),
                GetControllerName( controller ),
                imageActionName,
                arg1,
                arg2,
                arg3,
                arg4);
            return RenderChartMap( chart );
        }

        /// <summary>
        /// Render img tag and associated image map for a chart.
        /// </summary>
        /// <typeparam name="T1">Type of the first factory argument.</typeparam>
        /// <typeparam name="T2">Type of the second factory argument.</typeparam>
        /// <typeparam name="T3">Type of the third factory argument.</typeparam>
        /// <typeparam name="T4">Type of the fourth factory argument.</typeparam>
        /// <typeparam name="T5">Type of the fifth factory argument.</typeparam>
        /// <param name="imageActionName">Method name in this controller that streams the chart image.</param>
        /// <param name="arg1">Id used by the chart factory to find the data to generate the chart.</param>
        /// <param name="arg2">Second parameter used by the chart factory.</param>
        /// <param name="arg3">Third parameter used by the chart factory.</param>
        /// <param name="arg4">Fourth parameter used by the chart factory.</param>
        /// <param name="arg5">Fifth parameter used by the chart factory.</param>
        /// <param name="chartFactory">Delegate capable of generating a new Chart instance.</param>
        /// <returns>ContentResult that generates HTML for the chart.</returns>
        public static ContentResult RenderChartMap<T1, T2, T3, T4, T5>( this Controller controller, string imageActionName,
            T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, Func<T1, T2, T3, T4, T5, Chart> chartFactory )
        {
            Chart chart = chartFactory.Invoke( arg1, arg2, arg3, arg4, arg5 );
            chart.ImageLocation = string.Format( "{0}{1}/{2}/{3}/{4}/{5}/{6}/{7}/",
                GetApplicationPath( controller ),
                GetControllerName( controller ),
                imageActionName,
                arg1,
                arg2,
                arg3,
                arg4,
                arg5 );
            return RenderChartMap( chart );
        }

        /// <summary>
        /// Render chart image byte stream as a PNG file.
        /// </summary>
        /// <typeparam name="T">Type of the id.</typeparam>
        /// <param name="controller">Controller instance.</param>
        /// <param name="arg">Id used by the chart factory to find the data to generate the chart.</param>
        /// <param name="chartFactory">Delegate capable of generating a new Chart instance.</param>
        /// <returns></returns>
        public static FileContentResult RenderChartImage<T>( this Controller controller, T arg, Func<T, Chart> chartFactory )
        {
            Chart chart = chartFactory.Invoke( arg );
            return RenderChartImage( chart );
        }

        /// <summary>
        /// Render chart image byte stream as a PNG file.
        /// </summary>
        /// <typeparam name="T1">Type of the first factory parameter.</typeparam>
        /// <typeparam name="T2">Type of the second factory parameter.</typeparam>
        /// <param name="controller">Controller instance.</param>
        /// <param name="arg1">Id used by the chart factory to find the data to generate the chart.</param>
        /// <param name="arg2">Second parameter used by the chart factory.</param>
        /// <param name="chartFactory">Delegate capable of generating a new Chart instance.</param>
        /// <returns></returns>
        public static FileContentResult RenderChartImage<T1, T2>( this Controller controller, 
            T1 arg1, T2 arg2, Func<T1, T2, Chart> chartFactory )
        {
            Chart chart = chartFactory.Invoke( arg1, arg2 );
            return RenderChartImage( chart );
        }

        /// <summary>
        /// Render chart image byte stream as a PNG file.
        /// </summary>
        /// <typeparam name="T1">Type of the first factory parameter.</typeparam>
        /// <typeparam name="T2">Type of the second factory parameter.</typeparam>
        /// <typeparam name="T3">Type of the third factory argument.</typeparam>
        /// <param name="controller">Controller instance.</param>
        /// <param name="arg1">Id used by the chart factory to find the data to generate the chart.</param>
        /// <param name="arg2">Second parameter used by the chart factory.</param>
        /// <param name="arg3">Third parameter used by the chart factory.</param>
        /// <param name="chartFactory">Delegate capable of generating a new Chart instance.</param>
        /// <returns></returns>
        public static FileContentResult RenderChartImage<T1, T2, T3>( this Controller controller, 
            T1 arg1, T2 arg2, T3 arg3, Func<T1, T2, T3, Chart> chartFactory )
        {
            Chart chart = chartFactory.Invoke( arg1, arg2, arg3 );
            return RenderChartImage( chart );
        }

        /// <summary>
        /// Render chart image byte stream as a PNG file.
        /// </summary>
        /// <typeparam name="T1">Type of the first factory parameter.</typeparam>
        /// <typeparam name="T2">Type of the second factory parameter.</typeparam>
        /// <typeparam name="T3">Type of the third factory argument.</typeparam>
        /// <typeparam name="T4">Type of the fourth factory argument.</typeparam>
        /// <param name="controller">Controller instance.</param>
        /// <param name="arg1">Id used by the chart factory to find the data to generate the chart.</param>
        /// <param name="arg2">Second parameter used by the chart factory.</param>
        /// <param name="arg3">Third parameter used by the chart factory.</param>
        /// <param name="arg4">Fourth parameter used by the chart factory.</param>
        /// <param name="chartFactory">Delegate capable of generating a new Chart instance.</param>
        /// <returns></returns>
        public static FileContentResult RenderChartImage<T1, T2, T3, T4>( this Controller controller,
            T1 arg1, T2 arg2, T3 arg3, T4 arg4, Func<T1, T2, T3, T4,  Chart> chartFactory )
        {
            Chart chart = chartFactory.Invoke( arg1, arg2, arg3, arg4 );
            return RenderChartImage( chart );
        }

        /// <summary>
        /// Render chart image byte stream as a PNG file.
        /// </summary>
        /// <typeparam name="T1">Type of the first factory parameter.</typeparam>
        /// <typeparam name="T2">Type of the second factory parameter.</typeparam>
        /// <typeparam name="T3">Type of the third factory argument.</typeparam>
        /// <typeparam name="T4">Type of the fourth factory argument.</typeparam>
        /// <typeparam name="T5">Type of the fifth factory argument.</typeparam>
        /// <param name="controller">Controller instance.</param>
        /// <param name="arg1">Id used by the chart factory to find the data to generate the chart.</param>
        /// <param name="arg2">Second parameter used by the chart factory.</param>
        /// <param name="arg3">Third parameter used by the chart factory.</param>
        /// <param name="arg4">Fourth parameter used by the chart factory.</param>
        /// <param name="arg5">Fourth parameter used by the chart factory.</param>
        /// <param name="chartFactory">Delegate capable of generating a new Chart instance.</param>
        /// <returns></returns>
        public static FileContentResult RenderChartImage<T1, T2, T3, T4, T5>( this Controller controller,
            T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, Func<T1, T2, T3, T4, T5, Chart> chartFactory )
        {
            Chart chart = chartFactory.Invoke( arg1, arg2, arg3, arg4, arg5 );
            return RenderChartImage( chart );
        }
        
        private static ContentResult RenderChartMap( Chart chart )
        {
            chart.RenderType = RenderType.ImageMap;
            //Make sure that each chart rendered into the page has a unique ID in HTML by
            //assigning a Guid to the ID property. Otherwise, they will all have the same
            //ID and the image map will only work for the first chart at best.
            chart.ID = Guid.NewGuid().ToString( "N" );
            using( var writer = new StringWriter() )
            using( var htmlTextWriter = new HtmlTextWriter( writer ) )
            {
                chart.RenderControl( htmlTextWriter );
                return new ContentResult() { Content = writer.ToString() };
            }
        }

        private static FileContentResult RenderChartImage( Chart chart )
        {
            using( MemoryStream chartStream = new MemoryStream() )
            {
                chart.SaveImage( chartStream, ChartImageFormat.Png );
                return new FileContentResult( chartStream.ToArray(), "image/png" ) { FileDownloadName = "chart.png" };
            }
        }

        private static string GetApplicationPath( Controller controller )
        {
            var applicationPath = controller.HttpContext.Request.ApplicationPath;
            applicationPath = applicationPath.EndsWith( "/" ) ? applicationPath : applicationPath + "/";
            return applicationPath;
        }

        private static string GetControllerName( Controller controller )
        {
            var controllerName = controller.GetType().Name;
            if( !controllerName.EndsWith( "Controller" ) )
                throw new InvalidOperationException( "Controller names must end with \"Controller\"" );

            controllerName = controllerName.Substring( 0, controllerName.Length - 10 ); ;
            return controllerName;
        }
    }
}

Secure Password Hashing in C#

Long-term storage of logon credentials in computer systems is a serious point of vulnerability. Too many systems store credentials in an unencrypted or weakly encrypted form that system administrators or database power-users can view or edit. This may seem OK as long as a set of conditions were true:

  • The administrators of the system are known to be trustworthy and no untrusted users have the ability to view, alter or copy the password file or table.
  • The normal execution flow of the system could not be used to reveal plaintext passwords.
  • The online and backup repositories of authentication data are secure.
    Employee turnover, the increasing complexity of internet-connected systems, and the spread of knowledge and tools for executing simple security exploits all work together to change the rules of the game so that storing passwords in plaintext is no longer acceptable.  Disgruntled employees are now widely acknowledged to be the single largest vulnerability for most companies, and are the most common attackers of computer systems.  Defects in production software, runtimes and platforms can also disclose sensitive information to attackers. A litany of recent headlines where a wide range of organizations have lost control of their authentication database prove that systems that store “secret” but plaintext logon information are unsafe.

Theory of Password Hashing in Brief

The key to hardening authentication systems to use a strong cryptographic function to hash passwords into an unrecoverable blob. A strong hashing algorithm must guard against brute force offline attack via a rainbow tables precompiled hashes on dictionary words. Rainbow tables and software to use them are publicly available which lowers the password cracking bar to the level of script kiddie.

Niels Furguson and Bruce Schneier in Practical Cryptography describe strong a strong hashing technique for safe storage of passwords which requires.

  • A publicly tested secure hashing algorithm such as SHA-256. Neither MD5 nor SHA-1 are good enough anymore.
  • A randomly-generated value known as a Salt is mixed with the plaintext. The salt value is not a secret, it exists to make the output of the hash non-deterministic. There should be a unique salt for each user and a new random salt value should be generated every time a password is set.
  • The hash is stretched, meaning that the output is fed back through the algorithm a large number of times in order to slow down the hashing algorithm to make brute force attacks impractical.

In order to authenticate a user, the system retrieves the salt for the username, calculates the hash for the password the user provided and compares that hash to the value in the authentication database. If the hashes match, then access is granted.

Implementation in C#

In hope of making it easy for .NET developers to implement good authentication security, my company published a secure password hashing algorithm in C# under the BSD license in 2005. This algorithm is a part of the security subsystem of our PeopleMatrix product.

Because the code is no longer available on thoughtfulcomputing.com, so I’m republishing hit here.

Download HashManager source with a sample application.

//*****************************************************************
// <copyright file="HashManager.cs" company="WolfeReiter">
// Copyright (c) 2005 WolfeReiter, LLC.
// </copyright>
//*****************************************************************

/*
** Copyright (c) 2005 WolfeReiter, LLC
**
** This software is provided 'as-is', without any express or implied warranty. In no 
** event will the authors be held liable for any damages arising from the use of 
** this software.
**
** Permission is granted to anyone to use this software for any purpose, including 
** commercial applications, and to alter it and redistribute it freely, subject to 
** the following restrictions:
**
**    1. The origin of this software must not be misrepresented; you must not claim 
**       that you wrote the original software. If you use this software in a product,
**       an acknowledgment in the product documentation would be appreciated but is 
**       not required.
**
**    2. Altered source versions must be plainly marked as such, and must not be 
**       misrepresented as being the original software.
**
**    3. This notice may not be removed or altered from any source distribution.
**
*/

using System;
using System.Globalization;
using System.Text;
using System.Security.Cryptography;

namespace WolfeReiter.Security.Cryptography
{
	/// <summary>
	/// HashManager provides the service of cryptographically hashing and verifying strings
	/// against an existing hash. HashManager uses the SHA-256 hashing transform by default.
	/// </summary>
	/// <remarks>
	/// <para>The MD5 and SHA1 algorithms should be avoided because they are not strong enough
	/// to resist attack with modern processors. Also, it appears that the algorithms for MD5 and SHA1
	/// may have a flaw known as "collision". The short story is that  an attacker can discover the 
	/// plaintext used to generate the hash in much fewer steps than expected.</para>
	/// <para>For example, SHA1 should theoretically require 2<sup>80</sup> steps to brute-force recover 
	/// the original plaintext. Researchers have recently claimed to have a method of recovering SHA1 plaintext
	/// in 2<sup>33</sup> steps.</para></remarks>
	[Serializable]
	public sealed class HashManager 
	{
		private HashAlgorithm _transform;
		private readonly ulong _iterations;

		/// <summary>
		/// CTOR. Creates a new HashManager object that uses the SHA-256 algorithm and stretches the entropy in the hash
		/// with 2<sup>16</sup> iterations.
		/// </summary>
		public HashManager() : this("SHA-256",65536){}
		/// <summary>
		/// CTOR. Creates a new HashManager object that uses the specified well-known hash transform algorithm.
		/// </summary>
		/// <param name="transform">Well-known transform algorithm (eg. MD5, SHA-1, SHA-256, SHA-384, SHA-512, etc.).</param>
		/// <param name="iterations">Number of iterations used to sretch the entropy of the plaintext. 2<sup>16</sup> iterations
		/// is a recommended minimum.</param>
		/// <exception cref="ArgumentOutOfRangeException">Throws if iterations is less than 1.</exception>
		public HashManager(string transform, ulong iterations) : this(HashAlgorithm.Create(transform),iterations){}

		/// <summary>
		/// CTOR. Creates a new HashManager object that uses provided transform hash algorithm.
		/// </summary>
		/// <param name="transform">HashAlgorithm object to use.</param>
		/// <param name="iterations">Number of iterations used to sretch the entropy of the plaintext. 2<sup>16</sup> iterations
		/// is a recommended minimum.</param>
		/// <exception cref="ArgumentOutOfRangeException">Throws if iterations is less than 1.</exception>
		public HashManager(HashAlgorithm transform, ulong iterations)
		{
			if( iterations < 1 )
				throw new ArgumentOutOfRangeException("iterations", iterations, "The number of iterations cannot be less than 1");
			_transform  = transform;
			_iterations = iterations;
		}
		/// <summary>
		/// CTOR. Creates a new HashManager object that uses the specified well-known hash transform algorithm.
		/// </summary>
		/// <param name="transform">Well-known transform algorithm (eg. MD5, SHA-1, SHA-256, SHA-384, SHA-512, etc.).</param>
		/// <param name="iterations">Number of iterations used to sretch the entropy of the plaintext. 2<sup>16</sup> iterations
		/// is a recommended minimum.</param>
		/// <exception cref="ArgumentOutOfRangeException">Throws if iterations is less than 1.</exception>
		public HashManager(string transform, long iterations) : this(HashAlgorithm.Create(transform),iterations){}

		/// <summary>
		/// CTOR. Creates a new HashManager object that uses provided transform hash algorithm.
		/// </summary>
		/// <param name="transform">HashAlgorithm object to use.</param>
		/// <param name="iterations">Number of iterations used to sretch the entropy of the plaintext. 2<sup>16</sup> iterations
		/// is a recommended minimum.</param>
		/// <exception cref="ArgumentOutOfRangeException">Throws if iterations is less than 1.</exception>
		public HashManager(HashAlgorithm transform, long iterations)
		{
			if( iterations < 1 )
				throw new ArgumentOutOfRangeException("iterations", iterations, "The number of iterations cannot be less than 1");
			_transform  = transform;
			_iterations = (ulong)iterations;
		}
		/// <summary>
		/// Hashes a plaintext string.
		/// </summary>
		/// <param name="s">Plaintext to hash. (not nullable)</param>
		/// <param name="salt">Salt entropy to mix with the s. (not nullable)</param>
		/// <returns>HashManager byte array.</returns>
		/// <exception cref="ArgumentNullException">Throws if either the s or salt arguments are null.</exception>
		public byte[] Encode( string s, byte[] salt )
		{
			if( s==null )
				throw new ArgumentNullException("s");
			if( salt==null )
				throw new ArgumentNullException("salt");

            return Encode( ConvertStringToByteArray( s ), salt );
		}

        public byte[] Encode( byte[] plaintext, byte[] salt )
        {
            byte[] sp = salt;
            byte[] hash = plaintext;
            //stretching via multiple iterations injects entropy that makes collision plaintext recovery much
            //more difficult.
            for( ulong i = 0; i < _iterations; i++ )
            {
                sp = Salt( hash, salt );
                hash = _transform.ComputeHash( sp );
            }

            return hash;
        }

		private byte[] Salt( byte[] p, byte[] salt )
		{
			byte[] buff = new byte[p.Length + salt.Length];
			for( int i=0; i<p.Length; i++ )
				buff[i] = p[i];
			for( int i=0; i<salt.Length; i++ )
				buff[i + p.Length] = salt[i];
			
			return buff;
		}

		/// <summary>
		/// Verifies a plaintext string against an existing hash. This is a case-sensitive operation.
		/// </summary>
		/// <param name="s">Plaintext to verify</param>
		/// <param name="hash">HashManager to compare with the s</param>
		/// <param name="salt">Salt that was used with the original s to generate the hash</param>
		/// <returns>True if the s is the same as the one used to generate the original hash.
		/// Otherwise false.</returns>
		/// <exception cref="ArgumentNullException">Throws if any of the s, hash or salt arguments are null.</exception>
		public bool Verify( string s, byte[] hash, byte[] salt )
		{
			if( s == null )
				throw new ArgumentNullException("s");
			if( salt == null )
				throw new ArgumentNullException("salt");
			if( hash == null )
				throw new ArgumentNullException("hash");

            byte[] testhash = Encode( s, salt );
            return _Verify( testhash, hash );
		}

        public bool Verify( byte[] plaintext, byte[] hash, byte[] salt )
        {
            if( plaintext == null )
                throw new ArgumentNullException( "plaintext" );
            if( salt == null )
                throw new ArgumentNullException( "salt" );
            if( hash == null )
                throw new ArgumentNullException( "hash" );

            byte[] testhash = Encode( plaintext, salt );
            return _Verify( testhash, hash );
        }

        private bool _Verify( byte[] a, byte[] b )
        {
            if( a.Length != b.Length )
                return false;
            for( int i = 0; i < a.Length; i++ )
            {
                if( a[i] != b[i] )
                    return false;
            }
            return true;
        }

		/// <summary>
		/// Generates a 32 byte (256 bit) cryptographically random salt.
		/// </summary>
		/// <returns>256 element Byte array containing cryptographically random bytes.</returns>
		public static byte[] GenerateSalt()
		{
			return GenerateSalt(32);
		}
		/// <summary>
		/// Generates a cryptogrpahically random salt of arbirary size.
		/// </summary>
		/// <param name="size">size of the salt</param>
		/// <returns>Byte array containing cryptographically random bytes.</returns>
		public static byte[] GenerateSalt(int size)
		{
			Byte[] saltBuff = new Byte[size];
			RandomNumberGenerator.Create().GetBytes( saltBuff );
			return saltBuff;
		}

		/// <summary>
		/// Convert a hash (or salt or any other) byte[] to a hexadecimal string.
		/// </summary>
		/// <param name="hash">Byte[] to convert to hex.</param>
		/// <returns></returns>
		public static string ConvertToHexString( byte[] hash )
		{
			StringBuilder sb = new StringBuilder();
			foreach( byte b in hash )
			{
				string bytestr = Convert.ToInt32(b).ToString("X").ToLower();
				if( bytestr.Length==1)
					bytestr = '0' + bytestr;
				sb.Append( bytestr );
			}
			return sb.ToString();
		}

		/// <summary>
		/// Convert a hexadecimal string to byte[].
		/// </summary>
		/// <param name="s"></param>
		/// <returns></returns>
		public static byte[] ConvertFromHexString( string s )
		{
			string hex = s.ToLower();
			if( hex.StartsWith("0x") )
				hex = hex.Substring(2);

			//ensure an even hex number
			hex = (hex.Length % 2 == 0) ? hex : '0' + hex;
			//2 hex digits per byte
			byte[] b = new byte[hex.Length/2];
			for(int i=0,j=0; i<hex.Length; i+=2,j++)
			{
				b[j] = byte.Parse( hex.Substring(i,2), NumberStyles.HexNumber );
			}
			return b;
		}

		/// <summary>
		/// Convert a hash (or salt or any other) byte[] to a base64 string.
		/// </summary>
		/// <param name="hash">Byte[] to convert to base64</param>
		/// <returns></returns>
		public static string ConvertToBase64String( byte[] hash )
		{
			return Convert.ToBase64String(hash);
		}
		
		/// <summary>
		/// Convert a base64 encoded string into a byte array.
		/// </summary>
		/// <param name="s">Base64 string.</param>
		/// <returns>Byte array.</returns>
		public static byte[] ConvertFromBase64String( string s )
		{
			return Convert.FromBase64String( s );
		}

		/// <summary>
		/// Converts a String to a Byte array.
		/// </summary>
		/// <remarks>Only works on .NET string objects or Unicode encoded strings.</remarks>
		/// <param name="s">String to convert</param>
		/// <returns>Byte array.</returns>
		public static byte[] ConvertStringToByteArray( string s )
		{
			if (s == null)
				return null;
			Char[] chars = s.ToCharArray();
			Encoder encoder = Encoding.Unicode.GetEncoder();
			int bytecount = encoder.GetByteCount( chars, 0, chars.Length, true );
			byte[] outbuff = new byte[bytecount];
			encoder.GetBytes(chars, 0, chars.Length, outbuff, 0, true );
			return outbuff;
		}
	}
}

Ximian is Dead, Long Live Xamarin

I was depressed when I heard that Attachmate disbanded the Mono team as a part of it’s acquisition of Novell but Miguel de Icaza has a lot of chutzpa. He has reformed his team in nothing flat and launched a new company to continue the development of Mono and its associated C#-based mobile toolkits, MonoToch (iOS) and  MonoDriod (Android) and Moonlight (Silverlight for Linux).

To make a long story short, the plan to spin off was not executed. Instead on Monday May 2nd, the Canadian and American teams were laid off; Europe, Brazil and Japan followed a few days later. These layoffs included all the MonoTouch and MonoDroid engineers and other key Mono developers. Although Attachmate allowed us to go home that day, we opted to provide technical support to our users until our last day at Novell, which was Friday last week.

Now, two weeks later, we have a plan in place, which includes both angel funding for keeping the team together, as well as a couple of engineering contracts that will help us stay together as a team while we ship our revenue generating products.

~Miguel de Icaza

All the best Miguel.

Simple ASP.Net MVC Globalization with Graceful Fallback

We recently began work on a website project using ASP.Net MVC 3.0 where one of the requirements was that the site will be globalized into different languages. However, one of the design considerations is that the content is going to be originally produced in English and then translated and published as available into the other supported languages. What the site needs to do is gracefully degrade to English when the desired globalized content is not available.

Other issues are that some languages are wordier or  more compact than English which can affect the graphic design. For example “Structured Investment Vehicles” (30 characters) translates in French to “Véhicules d’Investissement Structurés” (37 characters). The French version requires 23% characters which is—roughly speaking (because of proportional fonts)—about 20% more space than the English version. It’s pretty typical for French phrases to contain 20-30% more characters than the English equivalent which means that resource file strings and just swapping out text can ruin the visual design layout. What is needed is re-layout of parts of views to accommodate the space consumed by different languages.

The idea is that we have English as an invariant which has every view the site uses in the normal place. We then have a /Views/Globalization directory which contains a subdirectory with the ISO 639-1 two-letter macro-language code ( ar = Arabic, fr = French, es = Spanish, etc.) which contain whatever translated content is available. If the browser requests a particular non-English language translation, we want to views to come from the appropriate Globalization directory  but if the content doesn’t exist, we fall back to English.

Our solution is to use views, partial views and master pages as the unit of globalization. In order to do this we created a new IViewEngine which extends whatever view engine we would otherwise be using. Our team is comfortable with WebForms so we extended WebFormViewEngine.

Example View Layout

/Views
    /Globalization
        /ar
            /Home
                /Index.aspx
            /Shared
                /Site.master
                /Navigation.aspx
        /es
            /Home
                /Index.aspx
            /Shared
                /Navigation.aspx
        /fr
            /Home
                /Index.aspx
            /Shared
    /Home
        /Index.aspx
    /Shared
        /Error.aspx
        /Footer.aspx
        /Navigation.aspx
        /Site.master

In the sample above, French is not fully globalized so when French views are served, the Navigation.ascx partial view should be served from /Views/Shared/Navigation.ascx, the Arabic views declare themselves as using the /Views/Globalization/ar/Shared/Site.master rather than /Views/Shared/Site.master and the default English Error.aspx view is always served.

jQuery Script to Switch Languages

/// <reference path="jquery-1.4.4.js" />
/// <reference path="jquery.cookie.js" />

//declare namespace to avoid collisions with extension js in the browser
var mySiteNamespace = {};

mySiteNamespace.switchLanguage = function (lang) {
    $.cookie('language', lang);
    window.location.reload();
};

$(document).ready(function () {
    // attach mySiteNamespace.switchLanguage to click events based on css classes
    $('.lang-english').click(function () { mySiteNamespace.switchLanguage('en'); });
    $('.lang-french').click(function () { mySiteNamespace.switchLanguage('fr'); });
    $('.lang-arabic').click(function () { mySiteNamespace.switchLanguage('ar'); });
    $('.lang-spanish').click(function () { mySiteNamespace.switchLanguage('es'); });
});

This little JavaScript attaches a switchLanguage function to elements (such as <a/>) which declare the specified css classes. It sets a language cookie which our custom IViewEngine is looking for.

Extending WebFormViewEngine

The key methods to override when extending WebFormViewEngine are CreatePartialView and CreateView. What we need to do is detect what language the browser is requesting and then choose the correct globalized view if it exists and fall back to the default behavior if it doesn’t. For simplicity, I’m showing code that uses a cookie to determine what language the end user wants but this detection can be as sophisticated as you like.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Web.Mvc;
using System.Text.RegularExpressions;
using System.IO;

namespace System.Web.Mvc
{
    public sealed class WebFormGlobalizationViewEngine : WebFormViewEngine
    {
        protected override IView CreatePartialView( ControllerContext controllerContext, string partialPath )
        {
            partialPath = GlobalizeViewPath( controllerContext, partialPath );
            return new WebFormView( controllerContext, partialPath, null, ViewPageActivator );
        }

        protected override IView CreateView( ControllerContext controllerContext, string viewPath, string masterPath )
        {
            viewPath = GlobalizeViewPath( controllerContext, viewPath );
            return base.CreateView( controllerContext, viewPath, masterPath );
        }

        private static string GlobalizeViewPath( ControllerContext controllerContext, string viewPath )
        {
            var request = controllerContext.HttpContext.Request;
            var lang = request.Cookies["language"];
            if( lang != null &&
                !string.IsNullOrEmpty(lang.Value) &&
                !string.Equals( lang.Value, "en", StringComparison.InvariantCultureIgnoreCase ) )
            {
                string localizedViewPath = Regex.Replace(
                    viewPath,
                    "^~/Views/",
                    string.Format( "~/Views/Globalization/{0}/",
                    lang.Value
                    ) );
                if( File.Exists( request.MapPath( localizedViewPath ) ) )
                { viewPath = localizedViewPath; }
            }
            return viewPath;
        }
    }
}

Registration in Global.asax.cs

The final step is to register WebFormsGlobalizationViewEngine when the Application.Start event fires.

protected void Application_Start()
{

    ViewEngines.Engines.Clear();
    ViewEngines.Engines.Add( new WebFormGlobalizationViewEngine() );

    // rest of application start stuff
}

Summing Up

There are a lot of ways to globalize content. This solution has the advantage of being straightforward and flexible. The main disadvantage is that we have to maintain translations of all the views and partial views.

C# in Depth 2nd Edition for Kindle but not from Amazon

skeet2_cover150Jon Skeet blogged this morning that C# in Depth 2nd edition is now available on Kindle. The original C# in Depth is just about the best programming book I’ve ever read, so I will definitely check this out. Don’t look on the Amazon Kindle store, though. Manning is self-publishing eBooks through its own website in PDF, epub and mobi. Mobi is the un-DRMed proto-format of Kindle and is read by Kindle devices and the Kindle desktop software. Interesting.

petricek_cover150Before I get C# in Depth 2nd Edition, though, I think I’ll check out Real-World Functional Programming by Tomas Petricek and Jon Skeet. This book is about both F# and C# (surely mostly LINQ). I’ve been playing around with Haskell lately and while it is interesting, it doesn’t seem all that practical. F# seems like a more approachable language and it targets .NET/Mono so it can mix with C# code that already exists and generally seems likely to be more immediately practical for real-world projects.

Also, if you have never heard of Jon Skeet, he’s an over-achiever who knows more about C# than just anyone not on the compiler team at Microsoft and he has by far the highest score on Stack Overflow. I don’t know how he has time for all of this because his day job has him working at Google in Java on the Android Market. He was interviewed on This Devleoper’s Life 1.1.3. Give it a listen.

IEnumerable<char> Random Password Generator

Last time I showed that IEnumerable uses lazy evaluation with a Fibonacci Sequence generator as an example. Perhaps a more practical example of an infinite series is a random character sequence from which you could generate passwords. This is using IEnumerable a lot like the /dev/random file in Unix.

This example is a password generator program based on a RandomCharSequence type which implements IEnumerable<char>. RandomCharSequence is again not much more than a factory for RandomCharEnumerator. The interesting thing here is that it passes the set of characters to be used in the random generation to RandomCharEnumerator. The character sets are upper, lower, digit and special and are themselves statically defined but are composable  using a CharTypes enumeration.

Like FibonacciSequence, RandomCharSequence is an infinite set. You have to limit how much of it you grab at a particular time using the Take(int) extension method from System.Linq.

RandomCharSequence as Password Generator

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Security.Cryptography;
using System.Reflection;
using System.Collections.ObjectModel;

namespace NewPassword
{
    class Program
    {
        static void Main( string[] args )
        {
            int length = -1;
            int count  = -1;
            if( args.Length > 0 )
            { int.TryParse( args[0], out length ); }
            else
            { length = 8; }
            if( args.Length > 1 )
            { int.TryParse( args[1], out count ); }
            else
            { count = 5; }
            
            var pwdseq = new RandomCharSequence();
            for( int i = 0; i < count; i++ )
            {
                Console.WriteLine( pwdseq.Take( length ).ToArray() );
            }
        }
    }

    [Flags]
    public enum CharTypes
    {
        Lower   = 0x01,
        Upper   = 0x02,
        Digit   = 0x04,
        Special = 0x08,
        All     = Upper | Lower | Digit | Special
    }
    public class RandomCharSequence : IEnumerable<char>
    {
        static readonly IEnumerable<char> s_lower   = new[] { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'q', 'y', 'z' };
        static readonly IEnumerable<char> s_upper   = new[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'Q', 'Y', 'Z' };
        static readonly IEnumerable<char> s_digit   = new[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
        static readonly IEnumerable<char> s_special = new[] { '!', '"', '#', '$', '%', '&', '\'', '(', ')', '*', '+', ',', '-', '.', '/', ':', ';', '<', '=', '>', '?', '@', '[', '\\', ']', '^', '_', '`', '{', '|', '}', '~' };

        //these static properties must exactly match the flags defined in the CharTypes enum
        private static IEnumerable<Char> Lower   { get{ return s_lower; } }
        private static IEnumerable<Char> Upper   { get{ return s_upper; } }
        private static IEnumerable<Char> Digit   { get{ return s_digit; } }
        private static IEnumerable<Char> Special { get{ return s_special; } }

        public RandomCharSequence() : this( CharTypes.All ){}
        public RandomCharSequence( CharTypes charTypes )
        {
            CharTypes = charTypes;
        }

        public CharTypes CharTypes {get; set;}

        public IEnumerator<char> GetEnumerator()
        {
            List<char> pool = new List<char>();
            foreach( var type in (CharTypes[])Enum.GetValues(typeof(CharTypes) ) )
            {
                //CharTypes.All is not a single bit flag. We don't want that one.
                if( type != CharTypes.All && (CharTypes & type) == type )
                {
                    //use reflection to add the static char list properties which
                    //match the flag bits.
                    pool.AddRange( 
                        (IEnumerable<char>)typeof(RandomCharSequence).GetProperty( 
                            type.ToString(), 
                            BindingFlags.Static | BindingFlags.NonPublic 
                            ).GetValue( this, null )
                        );
                }
            }
            return new RandomCharEnumerator( pool );
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }

    public class RandomCharEnumerator : IEnumerator<char>
    {
        public RandomCharEnumerator( IList<char> pool )
        {
            Disposing = false;
            Pool      = new ReadOnlyCollection<char>( pool );
            Random    = RandomNumberGenerator.Create();
        }

        RandomNumberGenerator Random { get; set; } 
        public IList<char> Pool { get; private set; }
        int Index { get; set; }

        public char  Current
        {
            get { return Pool[Index]; }
        }
        object IEnumerator.Current { get { return Current; } }


        private bool Disposing{ get; set; }
        public void  Dispose()
        {
            //RandomNubmerGenerator only implements IDisposable as of .NET Framework 4.0
            IDisposable randDisposable = Random as IDisposable;
            if( randDisposable != null && !Disposing )
            {
                randDisposable.Dispose();
                Disposing = true;
            }
        }

        public bool  MoveNext()
        {
            Index = Random.GetInt( 0, Pool.Count );
            //infinite sequence of random chars. There's always a next one.
            return true;
        }

        public void  Reset(){ /* nothing */ }
    }

    public static class RandomNumberGeneratorExtension
    {
        public static int GetInt( this RandomNumberGenerator random, int min, int max )
        {
            if( min >= max )
                throw new InvalidOperationException( "The min value must be less than the max value." );
            byte[] buff = new byte[8];
            random.GetBytes(buff);
            long r = Math.Abs( BitConverter.ToInt64( buff, 0 ) );
            return (int)((long)min + (r % ((long)max - (long)min)));
        }
    }
}

Compile and run the program to pull some password strings out of the infinite random character sequence.

PS> csc -nologo -out:newpassword.exe ./Program.cs; ./newpassword 10 15
^mVhNjHdds
o4Eq=q;`es
%1R\rL3r3{
+PFRrl4e)u
TvAB+tjNu-
?8zCq~{?KB
@WY)+sF;^I
B+)'?sRee-
G'\e)QkjYp
L8(`@o};$$
)j`$7?RG)4
QcC{4;fZcb
_S89_tm]76
}kAiirj^!=
,qq|%-(s)@

Update: RandomNumberGenerator does not implement IDisposable until .Net Framework 4.0 so I needed to dynamically invoke the interface if present rather than statically compiling with Random.Dispose() in there.

IEnumerable is Lazy… And That’s Cool

We tend to think of IEnumerable<T> as this thing in C# collections which allows foreach to iterate a collection without having to deal with a counter. There’s another semantic feature of IEnumerable that is different from an Array or List<T> or any other concrete collection. IEnumerable is lazy while an array or list is implicitly eager.

Consider an array. First, you have to define its size which is fixed. Then you have to loop over the array and populate it with values. Then you can use it in some other loop later. Array is conducive to eager evaluation because you have to define its size in advance and you have to fill it up before you can use it. Lists are similar conceptually and are actually implemented with arrays internally. The main advantage of a list is that it is dynamically expandable.

IEnumerable is a very different thing. At its core IEnumerable is a contract to provide a factory for an IEnumerator<T> object. IEnumerator then just provides a mechanism to get the current element of the enumeration, move to the next element and reset. IEnumerator only has to know how to get the next element or start over. It doesn’t actually need a collection to exist. MoveNext() only has to get the next value. There’s no requirement that all values are known at any give time and there’s no requirement that the values are finite. This is the essence of lazy evaluation. Only enough work needs to be done to get the next answer. Nothing more.

Fibonacci: An infinite IEnumberable<T>

To illustrate that IEnumerable is a lazy evaluation pattern, I implemented the Fibonacci Sequence as an enumerable type in C#. I can pass a FibonacciSequence object to things that understand IEnumerable and it works. If IEnumerable were an eager implementation my code would spin in an infinite loop but it doesn’t because MoveNext() only calculates the next number in the series if it is asked.

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

namespace LazyFibonacci
{
    class Program
    {
        static void Main( string[] args )
        {
            int i = -1;
            if( args.Length > 0 )
            { int.TryParse( args[0], out i ); }
            else
            { i = 100; }

            var fibonacci = new FibonacciSequence();
            /***
             * fibonacci is infinite.
             * Don't try operations that require the entire set to be enumerated:
             *  - fibinacci.ToList() --> NO!
             *  - fibonacci.Reverse() --> NO!
             *
             * Using .Skip(int) and .Take(int) is a good way to get slices of fibonacci, though.
             ***/

            foreach( var item in fibonacci.Take( i ) )
            {
                Console.WriteLine( item );
            }
        }
    }

    //FibonnacciSequence has no state.
    //It's just a factory for FibonacciEnumerator.
    public class FibonacciSequence : IEnumerable<BigInteger>
    {
        public IEnumerator<BigInteger> GetEnumerator()
        {
            return new FibonacciEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }

    public class FibonacciEnumerator : IEnumerator<BigInteger>
    {
        public FibonacciEnumerator()
        {
            Reset();
        }

        BigInteger Last { get; set; }
        public BigInteger Current { get; private set; }
        object IEnumerator.Current { get { return Current; } }

        public void Dispose() { /*do nothing*/}

        public void Reset()
        {
            Current = -1;
        }

        public bool MoveNext()
        {
            if( Current == -1 )
            {
                //State after first call to MoveNext() before the first element is read
                //Fibonacci is defined to start with 0.
                Current = 0;
            }
            else if( Current == 0 )
            {
                //2nd element in the Fibonacci series is defined to be 1.
                Current = 1;
            }
            else
            {
                //Fibonacci infinite series algorithm.
                BigInteger next = Current + Last;
                Last = Current;
                Current = next;
            }
            //infinite series. there is always another.
            return true;
        }
    }
}

The moment of truth. If IEnumerable is lazy this will work.

 

PS> csc -nologo -r:System.Numerics.dll -out:fibonacci.exe ./program.cs
PS> $fib = (./fibonacci.exe 25); [string]::join(', ', $fib)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368

Exploring Functional Programming with Erik Meijer and Haskell

Haskell logoErik Meijer of Microsoft Research is an inspiring guy and his work on LINQ is impressive. I just stumbled across his lecture series on exploring Functional Programming Fundamentals and I decided I would do the course and learn Haskell. I want to expand my frame of reference from primarily imperative and relational thinking to functional thinking. I like the idea of starting with Haskell instead of something like F# simply because Haskell is designed as a pure functional language for teaching and research. Working with Haskell sets aside the complexity of integrating huge a huge framework library.

The text that Dr. Meijer is using is Graham Hutton’s Programming in Haskell which is conveniently available at a discount on Kindle. Hutton’s text uses the Hugs98 Haskell interpreter which is available from haskell.org but seems to have been unmaintained since 2006. The Haskell Platform is also available from haskell.org and is prominently linked on the haskell.org home page. The Haskell Platform is “batteries included’ (ala Python) and based on the Glasgow Haskell Compiler (GHC) and interpreter (GHCi). It seems like GHCi is equivalent to Hugs and works in the same way.

A quick aside here. The maintainer of GHC, Simon Peyton Jones, is also a fellow at Microsoft Research. Interesting.

Homework: Transliterate QuickSort from Haskell C#

OK. I’ve read the first chapter of Hutton and watched the first lecture from Dr. Meijer. In addition to the exercises in Hutton’s text, Dr. Meijer suggested a homework problem of transliterating the Haskell qsort example into C# using LINQ.

Here’s my implementation.

QuickSort in Haskell

qsort []     = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
                where
                    smaller = [a|a <- xs, a <= x]
                    larger = [b|b <- xs, b > x]

QuickSort in C# with LINQ extension methods

The C# version is more verbose primarily because of some of the Haskell syntactic sugar, like the ++ operator for concatenating lists and the sort of function overloading in Haskell:

  • f [] = [] means that when an empty list is the input of function, f, then an empty list is the output.
  • f (x:xs) automagically takes the first element of the list an puts it into x while the remainder is in xs.

Also, Haskell implicitly knows that types are comparable whereas in C# I have to do some gross syntax with generic constraints an explicitly use IEnumerable<T>.CompareTo(T). Other than those syntactic differences, the C# version works essentially the same way as the Haskell version.

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

namespace QuickSort
{
    static class Program
    {
        static void Main( string[] args )
        {
            var t = new [] { 3, 5, 1, 4, 2 };
            Console.WriteLine( string.Join( ", ", t.QuickSort().ToArray() ) );
        }

        //this does not do the sort in place, but neither did the Haskell version
        public static IEnumerable<T> QuickSort<T>( this IEnumerable<T> list ) where T : IComparable<T>
        {
            //qsort [] = []
            if( list.Count() == 0 )
            { return list; }

            //qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
            var x  = list.First();
            var xs = list.Skip( 1 );

            return QuickSort( xs.Where( a => a.CompareTo( x ) <= 0 ) )
                    .Concat( new[] { x } )
                    .Concat( QuickSort( xs.Where( a => a.CompareTo( x ) > 0 ) ) );
        }
    }
}

PS> csc -nologo Program.cs; ./program
1, 2, 3, 4, 5

Custom JsonResult Class for ASP.Net MVC to Avoid MaxJsonLength Exceeded Exception

Shortly before Christmas, I was working on an application that sent a large data set to jqGrid using an Ajax JSON stream in ASP.Net MVC. We were trying out using a “get everything once” model where all of the I/O happens when jqGrid is initialized or reset and then all of the data is available on the client for fast sort and filter. It was working well with test data of ~5-6K rows until a colleague checked in a change that added a new  column. Suddenly my jqGrid was blank while hers (with a different, somewhat smaller, set of test data) was fine. Usually this sort of behavior from jqGrid indicates that the JSON was broken. Sure enough when I fired up my Fiddler HTTP debugger, I saw an error 500 for the JSON ajax query.


Server Error in ‘/’ Application.

Error during serialization or deserialization using the JSON JavaScriptSerializer. The length of the string exceeds the value set on the maxJsonLength property.

Description: An unhandled exception occurred during the execution of the current web request. Please review the stack trace for more information about the error and where it originated in the code. 

Exception Details: System.InvalidOperationException: Error during serialization or deserialization using the JSON JavaScriptSerializer. The length of the string exceeds the value set on the maxJsonLength property.

Source Error: 


An unhandled exception was generated during the execution of the current web request. Information regarding the origin and location of the exception can be identified using the exception stack trace below.

Stack Trace: 


[InvalidOperationException: Error during serialization or deserialization using the JSON JavaScriptSerializer. The length of the string exceeds the value set on the maxJsonLength property.]
   System.Web.Script.Serialization.JavaScriptSerializer.Serialize(Object obj, StringBuilder output, SerializationFormat serializationFormat) +551497
   System.Web.Script.Serialization.JavaScriptSerializer.Serialize(Object obj, SerializationFormat serializationFormat) +74
   System.Web.Script.Serialization.JavaScriptSerializer.Serialize(Object obj) +6
   System.Web.Mvc.JsonResult.ExecuteResult(ControllerContext context) +341
   System.Web.Mvc.ControllerActionInvoker.InvokeActionResult(ControllerContext controllerContext, ActionResult actionResult) +10
   System.Web.Mvc.<>c__DisplayClass14.<InvokeActionResultWithFilters>b__11() +20
   System.Web.Mvc.ControllerActionInvoker.InvokeActionResultFilter(IResultFilter filter, ResultExecutingContext preContext, Func`1 continuation) +251
   System.Web.Mvc.<>c__DisplayClass16.<InvokeActionResultWithFilters>b__13() +19
   System.Web.Mvc.ControllerActionInvoker.InvokeActionResultWithFilters(ControllerContext controllerContext, IList`1 filters, ActionResult actionResult) +178
   System.Web.Mvc.ControllerActionInvoker.InvokeAction(ControllerContext controllerContext, String actionName) +314
   System.Web.Mvc.Controller.ExecuteCore() +105
   System.Web.Mvc.ControllerBase.Execute(RequestContext requestContext) +39
   System.Web.Mvc.ControllerBase.System.Web.Mvc.IController.Execute(RequestContext requestContext) +7
   System.Web.Mvc.<>c__DisplayClass8.<BeginProcessRequest>b__4() +34
   System.Web.Mvc.Async.<>c__DisplayClass1.<MakeVoidDelegate>b__0() +21
   System.Web.Mvc.Async.<>c__DisplayClass8`1.<BeginSynchronous>b__7(IAsyncResult _) +12
   System.Web.Mvc.Async.WrappedAsyncResult`1.End() +59
   System.Web.Mvc.MvcHandler.EndProcessRequest(IAsyncResult asyncResult) +44
   System.Web.Mvc.MvcHandler.System.Web.IHttpAsyncHandler.EndProcessRequest(IAsyncResult result) +7
   System.Web.CallHandlerExecutionStep.System.Web.HttpApplication.IExecutionStep.Execute() +8682542
   System.Web.HttpApplication.ExecuteStep(IExecutionStep step, Boolean& completedSynchronously) +155


Version Information: Microsoft .NET Framework Version:2.0.50727.4952; ASP.NET Version:2.0.50727.4955

 

The error is inside of a call from MVC to BCL

It turns out that the exception happens inside of JsonResult.ExecuteResult(ControllerContext context). What is going on in there? Well, fortunately, ASP.Net MVC code is open source (MS-PL) and the .NET Framework class library source code is available for reference as well. Let’s take a look.

The meat of JsonResult.ExecuteResult(ControllerContext)

if (Data != null) {
    JavaScriptSerializer serializer = new JavaScriptSerializer();
    response.Write(serializer.Serialize(Data));
}

The meat of JavaScriptSerializer.Serialize(object obj)

public string Serialize(object obj) {
    return Serialize(obj, SerializationFormat.JSON);
}

private string Serialize(object obj, SerializationFormat serializationFormat) {
    StringBuilder sb = new StringBuilder(); 
    Serialize(obj, sb, serializationFormat); 
    return sb.ToString();
}

internal void Serialize(object obj, StringBuilder output, SerializationFormat serializationFormat) {
    SerializeValue(obj, output, 0, null, serializationFormat); 
    // DevDiv Bugs 96574: Max JSON length does not apply when serializing to Javascript for ScriptDescriptors
    if (serializationFormat == SerializationFormat.JSON && output.Length > MaxJsonLength) {
        throw new InvalidOperationException(AtlasWeb.JSON_MaxJsonLengthExceeded);
    } 
}

JavaScriptSerializer completely serializes object obj into StringBuilder output and then, having allocated that memory, checks the size of the StringBuilder and if it is larger than the MaxJsonLength property it throws an InvalidOperationException. JsonResult just creates a new JavaScriptSerializer and uses it so there is no way to change the default MaxJsonLength when using JsonResult in MVC. Since the memory is allocated before the InvalidOperationException is thrown, I’m not really clear what the point of MaxJsonLength is this deep in the framework. Surely whatever is going to use the JSON string would be in a better position to decide if the string returned by JavaScriptSerializer.Serialize() was too long to use?

Anyway, we have the problem isolated now for a solution. We need to implement our own ActionResult that will generate JSON while allowing the caller to twiddle the knobs on JavaScriptSerializer.

LargeJsonResult ActionResult class

using System;
using System.Web.Script.Serialization;

namespace System.Web.Mvc
{
    public class LargeJsonResult : JsonResult
    {
        const string JsonRequest_GetNotAllowed = "This request has been blocked because sensitive information could be disclosed to third party web sites when this is used in a GET request. To allow GET requests, set JsonRequestBehavior to AllowGet.";
        public LargeJsonResult()
        {
            MaxJsonLength = 1024000;
            RecursionLimit = 100;
        }

        public int MaxJsonLength { get; set; }
        public int RecursionLimit { get; set; }

        public override void ExecuteResult( ControllerContext context )
        {
            if( context == null )
            {
                throw new ArgumentNullException( "context" );
            }
            if( JsonRequestBehavior == JsonRequestBehavior.DenyGet &&
                String.Equals( context.HttpContext.Request.HttpMethod, "GET", StringComparison.OrdinalIgnoreCase ) )
            {
                throw new InvalidOperationException( JsonRequest_GetNotAllowed );
            }

            HttpResponseBase response = context.HttpContext.Response;

            if( !String.IsNullOrEmpty( ContentType ) )
            {
                response.ContentType = ContentType;
            }
            else
            {
                response.ContentType = "application/json";
            }
            if( ContentEncoding != null )
            {
                response.ContentEncoding = ContentEncoding;
            }
            if( Data != null )
            {
                JavaScriptSerializer serializer = new JavaScriptSerializer() { MaxJsonLength = MaxJsonLength, RecursionLimit = RecursionLimit };
                response.Write( serializer.Serialize( Data ) );
            }
        }
    }
}

You can use return new LargeJsonResult(){ Data = data } from any Action method where you would have used return Json(data). Also, you have direct control over the MaxJsonLength and RecursionLimit properites of JavaScriptSerializer.

return new LargeJsonResult() { Data = output, MaxJsonLength = int.MaxValue };

Is F# Math Really Faster than C#?

I ran across an article claiming that F# was about an order of magnitude faster at calculating a basic math algorithm. Can this be true?

Sigmoid in C#

public static float Sigmoid(float value) 
{
    return 1.0f / (1.0f + (float) Math.Exp(-value));
}
//csc -o -debug-
.method public static float32 Sigmoid(float32 'value') cil managed
{
    .maxstack 8
    L_0000: ldc.r8 1
    L_0009: ldc.r8 1
    L_0012: ldarg.0 
    L_0013: neg 
    L_0014: conv.r8 
    L_0015: call float64 [mscorlib]System.Math::Exp(float64)
    L_001a: add 
    L_001b: div 
    L_001c: conv.r4 
    L_001d: ret 
}

Sigmoid in F#

let Sigmoid value = 1.0f/(1.0f + exp(-value));
//fsc --debug- --optimize+
.method public static float32 Sigmoid(float32 'value') cil managed
{
    .maxstack 5
    .locals init (
        [0] float32 num)
    L_0000: ldc.r4 1
    L_0005: ldc.r4 1
    L_000a: ldarg.0 
    L_000b: neg 
    L_000c: stloc.0 
    L_000d: ldloc.0 
    L_000e: conv.r8 
    L_000f: call float64 [mscorlib]System.Math::Exp(float64)
    L_0014: conv.r4 
    L_0015: add 
    L_0016: div 
    L_0017: ret 
}

The IL generated is nearly the same. The F# version allocates a little less memory using float32 variables on the stack where C# uses float64 and generally manages with a smaller stack, but the basic math operations are the same. Can these differences make an order of magnitude performance difference? Short answer is no.

Benchmarks are Tricky

C# sigmoid algorithm benchmark

// (c) Rinat Abdullin
// http://abdullin.com/journal/2009/1/5/caching-activation-function-is-not-worth-it.html
// sigmoidcs.cs

using System;
using System.Diagnostics;

static class App
{
	const float Scale = 320.0f;
	const int Resolution = 2047;
	const float Min = -Resolution/Scale;
	const float Max = Resolution/Scale;

	static readonly float[] _lut = InitLut();

	static float[] InitLut()
	{
	  var lut =  new float[Resolution + 1];
	  for (int i = 0; i < Resolution + 1; i++)
	  {
	    lut[i] = (float) (1.0/(1.0 + Math.Exp(-i/Scale)));
	  }
	  return lut;
	}

	static float Sigmoid1(double value)
	{
	  return (float) (1.0/(1.0 + Math.Exp(-value)));
	}

	static float Sigmoid2(float value)
	{
	  if (value <= Min) return 0.0f;
	  if (value >= Max) return 1.0f;
	  var f = value*Scale;
	  if (value >= 0) return _lut[(int) (f + 0.5f)];
	  return 1.0f - _lut[(int) (0.5f - f)];
	}

	static float TestError()
	{
	  var emax = 0.0f;
	  for (var x = -10.0f; x < 10.0f; x += 0.000001f)
	  {
	    var v0 = Sigmoid1(x);
	    var v1 = Sigmoid2(x);

	    var e = Math.Abs(v1 - v0);
	    if (e > emax) emax = e;
	  }
	  return emax;
	}

	static double TestPerformancePlain()
	{
	  var sw = new Stopwatch();
	  sw.Start();
	  for (int i = 0; i < 10; i++)
	  {
	    for (float x = -5.0f; x < 5.0f; x += 0.000001f)
	    {
	      Sigmoid1(x);
	    }
	  }

	  return sw.Elapsed.TotalMilliseconds;
	}

	static double TestPerformanceOfLut()
	{
	  var sw = new Stopwatch();
	  sw.Start();
	  for (int i = 0; i < 10; i++)
	  {
	    for (float x = -5.0f; x < 5.0f; x += 0.000001f)
	    {
	      Sigmoid2(x);
	    }
	  }
	  return sw.Elapsed.TotalMilliseconds;
	}

	static void Main()
	{
	  var emax = TestError();
	  var t0 = TestPerformancePlain();
	  var t1 = TestPerformanceOfLut();

	  Console.WriteLine("Max detected deviation using LUT: {0}", emax);
	  Console.WriteLine("10^7 iterations using Sigmoid1() took {0} ms", t0);
	  Console.WriteLine("10^7 iterations using Sigmoid2() took {0} ms", t1);
	}
}

F# sigmoid algorithm benchmark

// (c) Rinat Abdullin
// http://abdullin.com/journal/2009/1/6/f-has-better-performance-than-c-in-math.html
// sigmoidfs.fs

#light

let Scale = 320.0f;
let Resolution = 2047;

let Min = -single(Resolution)/Scale;
let Max = single(Resolution)/Scale;

let range step a b =
  let count = int((b-a)/step);
  seq { for i in 0 .. count -> single(i)*step + a };

let lut = [| 
  for x in 0 .. Resolution ->
    single(1.0/(1.0 +  exp(-double(x)/double(Scale))))
  |]

let sigmoid1 value = 1.0f/(1.0f + exp(-value));

let sigmoid2 v = 
  if (v <= Min) then 0.0f;
  elif (v>= Max) then 1.0f;
  else
    let f = v * Scale;
    if (v>0.0f) then lut.[int (f + 0.5f)]
    else 1.0f - lut.[int(0.5f - f)];

let getError f = 
  let test = range 0.00001f -10.0f 10.0f;
  let errors = seq { 
    for v in test -> 
      abs(sigmoid1(single(v)) - f(single(v)))
  }
  Seq.max errors;

open System.Diagnostics;

let test f = 
  let sw = Stopwatch.StartNew(); 
  let mutable m = 0.0f;
  let result = 
    for t in 1 .. 10 do
      for x in 1 .. 1000000 do
        m <- f(single(x)/100000.0f-5.0f);
  sw.Elapsed.TotalMilliseconds;

printf "Max deviation is %f\n" (getError sigmoid2)
printf "10^7 iterations using sigmoid1: %f ms\n" (test sigmoid1)
printf "10^7 iterations using sigmoid2: %f ms\n" (test sigmoid2)
PS> csc -o -debug- .\sigmoidcs.cs
Microsoft (R) Visual C# 2010 Compiler version 4.0.30319.1
Copyright (C) Microsoft Corporation. All rights reserved.

PS> fsc --debug- --optimize+  .\sigmoidfs.fs
Microsoft (R) F# 2.0 Compiler build 4.0.30319.1
Copyright (c) Microsoft Corporation. All Rights Reserved.
PS> .\sigmoidcs.exe
Max detected deviation using LUT: 0.001663984
10^7 iterations using Sigmoid1() took 2644.5935 ms
10^7 iterations using Sigmoid2() took 510.9379 ms
PS> .\sigmoidfs.exe
Max deviation is 0.001664
10^7 iterations using sigmoid1: 403.974300 ms
10^7 iterations using sigmoid2: 124.520100 ms

Wow. That’s 404ms for F# and 2,656 for C#. That’s a huge difference. Why?

We already established that the IL for the Sigmoid1() algorithm above compiles to very similar IL. What else could be different?

fsharp-test-func

Wait a minute.

let result = 
    for t in 1 .. 10 do
      for x in 1 .. 1000000 do
        m <- f(single(x)/100000.0f-5.0f);

The F# loop is not equivalent to the C# version. In the F# version the counter is an int and the C# version the counter is a float. (Also the F# version is passing a delegate to the test function.)

for (int i = 0; i < 10; i++)
{
	for (float x = -5.0f; x < 5.0f; x += 0.000001f)
	{
		Sigmoid1(x);
	}
}

Does that int counter thing make a big difference.

using System;
using System.Diagnostics;

static class App
{
	static float Sigmoid1(double value)
	{
	  return (float) (1.0/(1.0 + Math.Exp(-value)));
	}

	static double TestPerformancePlain()
	{
		var sw = new Stopwatch();
		sw.Start();
		float num = 0f;
		for (int i = 0; i < 10; i++)
		{
			for (int j = 1; j < 1000001; j++)
			{
				num = Sigmoid1((((float) j) / 100000f) - 5f);
			}
		}  
		return sw.Elapsed.TotalMilliseconds;
	}

	static void Main()
	{
	  var t0 = TestPerformancePlain();
	  Console.WriteLine("10^7 iterations using Sigmoid1() took {0} ms", t0);
	}
}
PS> csc -o -debug- .\sigmoid-counter.cs
Microsoft (R) Visual C# 2010 Compiler version 4.0.30319.1
Copyright (C) Microsoft Corporation. All rights reserved.

PS> ./sigmoid-counter
10^7 iterations using Sigmoid1() took 431.6634 ms

Yup C# just executed that Sigmoid1() test in 431ms. Recall that F# was 404ms.

The other difference was that the F# code was passing a delegate of FsharpFunc<float,float> rather than making a method call. Lets try the same thing in C# using a Lambda expression to create an anonymous Func<float,float> delegate.

using System;
using System.Diagnostics;

static class App
{
	static double Test(Func<float,float> f)
	{
		var sw = new Stopwatch();
		sw.Start();
		float num = 0f;
		for (int i = 0; i < 10; i++)
		{
			for (int j = 1; j < 1000001; j++)
			{
		   		num = f((((float) j) / 100000f) - 5f);
			}
		}  
		return sw.Elapsed.TotalMilliseconds;
	}

	static void Main()
	{
	  var t0 = Test( x => { return (float) (1.0/(1.0 + Math.Exp(-x))); } );
	  Console.WriteLine("10^7 iterations using Sigmoid1() took {0} ms", t0);
	}
}
PS> ./sigmoid-counter
10^7 iterations using Sigmoid1() took 431.6634 ms
PS> csc -o -debug- .\sigmoid-lambda.cs
Microsoft (R) Visual C# 2010 Compiler version 4.0.30319.1
Copyright (C) Microsoft Corporation. All rights reserved.

PS> .\sigmoid-lambda.exe
10^7 iterations using Sigmoid1() took 275.1087 ms

Now C# is 30ms faster than F#.

For what it’s worth the C version of the Sigmoid1() benchmark executes in 166ms on my machine using CL 16 x64 on my machine.

  • C: 166ms
  • C# (delegate): 275ms
  • C# (method): 431ms
  • C# (method, float counter): 2,656ms
  • F#: 404ms
  • So, what have we learned?

  • Never, ever use a float as a counter in a for loop in C#.
  • Invoking a delegate in the CLR is slightly faster than a normal method invocation.
  • It’s very easy to measure something other than what you intended when benchmarking.
  • In as much as this little test means anything, C# and F# have similar performance. C is still faster.
Follow

Get every new post delivered to your Inbox.