Tuesday, October 28, 2014

Create C# Class Code From a DataTable using CodeDOM



Note by author:

   Since writing this, I have expanded on this idea quite a bit. I have written a lightweight ORM class library that I call EntityJustWorks.

   The full project can be found on
GitHub or CodePlex.


   EntityJustWorks not only goes from a class to DataTable (below), but also provides:

Security Warning:
This library generates dynamic SQL, and has functions that generate SQL and then immediately executes it. While it its true that all strings funnel through the function Helper.EscapeSingleQuotes, this can be defeated in various ways and only parameterized SQL should be considered SAFE. If you have no need for them, I recommend stripping semicolons ; and dashes --. Also there are some Unicode characters that can be interpreted as a single quote or may be converted to one when changing encodings. Additionally, there are Unicode characters that can crash .NET code, but mainly controls (think TextBox). You almost certainly should impose a white list: string clean = new string(dirty.Where(c => "abcdefghijklmnopqrstuvwxyz0123456789.,\"_ !@".Contains(c)).ToArray()); 
PLEASE USE the SQLScript.StoredProcedure and DatabaseQuery.StoredProcedure classes to generate SQL for you, as the scripts it produces is parameterized. All of the functions can be altered to generate parameterized instead of sanitized scripts. Ever since people have started using this, I have been maintaining backwards compatibility. However, I may break this in the future, as I do not wish to teach one who is learning dangerous/bad habits. This project is a few years old, and its already showing its age. What is probably needed here is a total re-write, deprecating this version while keep it available for legacy users after slapping big warnings all over the place. This project was designed to generate the SQL scripts for standing up a database for a project, using only MY input as data. This project was never designed to process a USER'S input.! Even if the data isn't coming from an adversary, client/user/manually entered data is notoriously inconsistent. Please do not use this code on any input that did not come from you, without first implementing parameterization. Again, please see the SQLScript.StoredProcedure class for inspiration on how to do that.


So far I have posted several times on the DataTable class. I have shown how to convert a DataTable to CSV or tab-delimited file using the clipboard, how to create a DataTable from a class using reflection, as well as how to populate the public properties of a class from a DataTable using reflection. Continuing along these lines, I decided to bring the DataTable-To-Class wagons around full-circle and introduce a class that will generate the C# code for the class that is used by the DataTableToClass<T> function, so you don't have to create it manually. The only parameter required to generate the C# class code is, of course, a DataTable.

The code below is rather trivial. It uses CodeDOM to build up a class with public properties that match the names and data types of the data columns of the supplied DataTable. I really wanted the output code to use auto properties. This is not supported by CodeDOM, however, so I used a little hack or workaround to accomplish the same thing. I simply added the getter and setter code for the property to the member's field name. CodeDOM adds a semicolon to the end of the CodeMemberField statement, which would cause the code not to compile, so I added two trailing slashes "//" to the end of the field name to comment out the semicolon. The whole point of creating auto properties was to have clean, succinct code, so after I generate the source code file, I clean up the commented-out semicolons by replacing every occurrence with an empty string. The main disadvantage of this 'workaround' is that the code cannot be used to generate a working class in Visual Basic code. I do have proper CodeDOM code that does not employ this workaround, but I prefer the output code to contain auto-properties; auto-generated code is notorious for being messy and hard to read, and I did not want my generated code to feel like generated code.


Below is the DataTableToCode function, its containing class and its supporting functions. The code is short, encapsulated, clean and commented, so I will just let it speak for itself:

public static class DataTableExtensions
{
   public static string DataTableToCode(DataTable Table)
   {
      string className = Table.TableName;
      if(string.IsNullOrWhiteSpace(className))
      {   // Default name
         className = "Unnamed";
      }
      className += "TableAsClass";
      
      // Create the class
      CodeTypeDeclaration codeClass = CreateClass(className);
      
      // Add public properties
      foreach(DataColumn column in Table.Columns)
      {
         codeClass.Members.Add( CreateProperty(column.ColumnName, column.DataType) );
      }
      
      // Add Class to Namespace
      string namespaceName = "AutoGeneratedDomainModels";
      CodeNamespace codeNamespace = new CodeNamespace(namespaceName);
      codeNamespace.Types.Add(codeClass);
      
      // Generate code
      string filename = string.Format("{0}.{1}.cs",namespaceName,className);
      CreateCodeFile(filename, codeNamespace);
      
      // Return filename
      return filename;
   }
   
   static CodeTypeDeclaration CreateClass(string name)
   {
      CodeTypeDeclaration result = new CodeTypeDeclaration(name);
      result.Attributes = MemberAttributes.Public;
      result.Members.Add(CreateConstructor(name)); // Add class constructor
      return result;
   }
   
   static CodeConstructor CreateConstructor(string className)
   {
      CodeConstructor result = new CodeConstructor();
      result.Attributes = MemberAttributes.Public;
      result.Name = className;
      return result;
   }
   
   static CodeMemberField CreateProperty(string name, Type type)
   {
      // This is a little hack. Since you cant create auto properties in CodeDOM,
      //  we make the getter and setter part of the member name.
      // This leaves behind a trailing semicolon that we comment out.
      //  Later, we remove the commented out semicolons.
      string memberName = name + "\t{ get; set; }//";
      
      CodeMemberField result = new CodeMemberField(type,memberName);
      result.Attributes = MemberAttributes.Public | MemberAttributes.Final;
      return result;
   }
   
   static void CreateCodeFile(string filename, CodeNamespace codeNamespace)
   {
      // CodeGeneratorOptions so the output is clean and easy to read
      CodeGeneratorOptions codeOptions = new CodeGeneratorOptions();
      codeOptions.BlankLinesBetweenMembers = false;
      codeOptions.VerbatimOrder = true;
      codeOptions.BracingStyle = "C";
      codeOptions.IndentString = "\t";
      
      // Create the code file
      using(TextWriter textWriter = new StreamWriter(filename))
      {
         CSharpCodeProvider codeProvider = new CSharpCodeProvider();
         codeProvider.GenerateCodeFromNamespace(codeNamespace, textWriter, codeOptions);
      }
      
      // Correct our little auto-property 'hack'
      File.WriteAllText(filename, File.ReadAllText(filename).Replace("//;", ""));
   }
}


An example of the resulting code appears below:

namespace AutoGeneratedDomainModels
{
   public class CustomerTableAsClass
   {
      public CustomerTableAsClass()
      {
      }
      public string FirstName   { get; set; }
      public string LastName    { get; set; }
      public int  Age           { get; set; }
      public char Sex           { get; set; }
      public string Address     { get; set; }
      public string Birthdate   { get; set; }
   }
}

I am satisfied with the results and look of the code. The DataTableToCode() function can be a huge time saver if you have a large number of tables you need to write classes for, or if each DataTable contains a large number of columns.

If you found any of this helpful, or have any comments or suggestions, please feel free to post a comment.

Saturday, September 27, 2014

Resize form to match the contents of DataGridView



Sometimes the sole purpose of a Form is to display a DataGridView. In that case, you probably want the Form to automatically resize to the size of the contents in the DataGridView. I've seen solutions that loop through all the rows and add up the height, but this is ugly, and usually does not take into account margins, padding, DividerHeight and row header padding. There must be a better way...

My strategy is to temporarily undock the DataGridView, set AutoSize to true, then capture the DataGridView's Size at that point, then restore the Dock and AutoSize property. Then use the captured size to resize the Winform:


// Within the Form class
private void AutoSizeFormToDataGridView()
{
 Size contentsSize = GetDataGridViewContentsSize();
 this.ClientSize = contentsSize;
}

protected Size GetDataGridViewContentsSize()
{
 DockStyle dockStyleSave = dataGridView1.Dock;
 dataGridView1.Dock = DockStyle.None;
 dataGridView1.AutoSize = true;
 
 Size dataContentsSize = dataGridView1.Size;
 
 dataGridView1.AutoSize = false;
 dataGridView1.Dock = dockStyleSave;
 return dataContentsSize;
}


Or alternatively you can define this as an extension method:

public static Size GetContentsSize(this DataGridView dataGrid) { //...


Enjoy!

Friday, September 26, 2014

DataTable or DataGridView to CSV or HTML file using Clipboard



It turns out that DataGridView.GetClipboardContent() returns all the selected cells of a DataGridView as a type DataObject, which is conveniently consumed by the Windows.Forms.Clipboard class, as well as other WYSIWYG editors from Microsoft. From this you can set the Clipboard, then get the clipboard various data formats, including:
- Comma separated value
- Tab separated value
- HTML

So instead of looping though columns and then rows, you can output the entire DataGridView as a CSV file in just 3 lines of code! (4 if you count setting the ClipboardCopyMode, which can be set in the Form Builder.

Here is the code:

void DataGridViewToCSV(string Filename)
{
   bool allowAddRows = dataGridView1.AllowUserToAddRows;
   bool rowHeadersVisible = dataGridView1.RowHeadersVisible;
   dataGridView1.AllowUserToAddRows = false;
   dataGridView1.RowHeadersVisible = false;

   // Choose whether to write header. You will want to do this for a CSV file.
   dataGridView1.ClipboardCopyMode = DataGridViewClipboardCopyMode.EnableAlwaysIncludeHeaderText;
   // Select the cells we want to serialize.
   dataGridView1.SelectAll(); // One could also use DataGridView.Rows[RowIndex].Selected = true;

   // Save the current state of the clipboard so we can restore it after we are done
   IDataObject objectSave = Clipboard.GetDataObject();
   // Copy (set clipboard)
   Clipboard.SetDataObject(dataGridView1.GetClipboardContent());
   // Paste (get the clipboard and serialize it to a file)
   File.WriteAllText(Filename,Clipboard.GetText(TextDataFormat.CommaSeparatedValue));
   // Restore the current state of the clipboard so the effect is seamless
   if(objectSave != null)
   {
      Clipboard.SetDataObject(objectSave);
   }
   dataGridView1.AllowUserToAddRows = allowAddRows;
   dataGridView1.RowHeadersVisible = rowHeadersVisible;
}

Some improvements

For a tab-delimited file, use the TextDataFormat.Text enum in your call to Clipboard.GetText(). You can also output your DataGridView as HTML by using TextDataFormat.Html instead of TextDataFormat.CommaSeparatedValue, but there is extra header data you have to parse out:

   string result = Clipboard.GetText(TextDataFormat.CommaSeparatedValue);
   result = result.Substring( result.IndexOf("") );

Notes:
- An object must be serializable for it to be put on the Clipboard.

Sunday, August 3, 2014

Set Public Properties of C# class from a DataTable using reflection



Note by author:

   Since writing this, I have expanded on this idea quite a bit. I have written a lightweight ORM class library that I call EntityJustWorks.

   The full project can be found on
GitHub or CodePlex.


   EntityJustWorks not only goes from a class to DataTable (below), but also provides:



Security Warning:
This library generates dynamic SQL, and has functions that generate SQL and then immediately executes it. While it its true that all strings funnel through the function Helper.EscapeSingleQuotes, this can be defeated in various ways and only parameterized SQL should be considered SAFE. If you have no need for them, I recommend stripping semicolons ; and dashes --. Also there are some Unicode characters that can be interpreted as a single quote or may be converted to one when changing encodings. Additionally, there are Unicode characters that can crash .NET code, but mainly controls (think TextBox). You almost certainly should impose a white list:
string clean = new string(dirty.Where(c => "abcdefghijklmnopqrstuvwxyz0123456789.,\"_ !@".Contains(c)).ToArray());

PLEASE USE the SQLScript.StoredProcedure and DatabaseQuery.StoredProcedure classes to generate SQL for you, as the scripts it produces is parameterized. All of the functions can be altered to generate parameterized instead of sanitized scripts. Ever since people have started using this, I have been maintaining backwards compatibility. However, I may break this in the future, as I do not wish to teach one who is learning dangerous/bad habits. This project is a few years old, and its already showing its age. What is probably needed here is a total re-write, deprecating this version while keep it available for legacy users after slapping big warnings all over the place. This project was designed to generate the SQL scripts for standing up a database for a project, using only MY input as data. This project was never designed to process a USER'S input.! Even if the data isn't coming from an adversary, client/user/manually entered data is notoriously inconsistent. Please do not use this code on any input that did not come from you, without first implementing parameterization. Again, please see the SQLScript.StoredProcedure class for inspiration on how to do that.




In this post I showed how to create a DataTable where the column names and types matched the properties of a class. In this post, we work the opposite direction and start with a Data-First approach. Given an SQL Database, we can easily convert a query to a DataTable using System.Data's SqlDataAdapter.Fill method. Now, given a DataTable, I show you here how to use Reflection to populate a class's public properties from a DataRow in a DataTable (or a List<> of classes, one from each DataRow in the DataTable) where the ColumnName matches the name of the public property in the class exactly (case-sensitive).
If the DataTable has extra columns that don't match up to a property in the class, they are ignored. If the DataTable is missing columns to match a class property, that property is ignored and left at the default value for that type (since it is a property). If you desire the ColumnName/PropertyInfo.Name matching behavior to be case insensitive, simply modify the line that compares the two strings (PropertyInfo.Name and DataColumn.ColumnName) to include a call to String.ToUpper() or String.ToLower() for each name.

If you paying close attention, or have ever attempted this kind of thing before, you are probably thinking to yourself that the most laborious (and error-prone) process is going to be creating the C# classes plus their many auto-properties that have to match the columns of a table, all manually. Well, take solace in the fact that I already thought of this and created a solution to generate C# class object code files from a DataTable using CodeDOM. It even implements a little hack to generate the properties as auto-properties (something not supported by CodeDOM) for clean, compact code that isn't bloated with private backing fields, and full getter/setter implementation.
Ultimately, the goal is to have a full, end-to-end, class-to-DataTable-to-SQL and back-again class library solution. Something like a poor-man's Entity Framework, or minimum-viable ORM. So stay alert for the next piece that will bring these wagons 'round full-circle: Automatic generation of SQL CREATE, INSERT INTO, and UPDATE scripts from a DataTable, which was generated from a C# class object, which can be generated from a DataTable, which can be generated by a SQL Database, which can be... well you get the idea.

This code has been tested and is a a little more robust than some of the equivalent samples I have been finding on StackOverflow (such as being able to handle properties of type Nullable<>. However there probably exists some conditions or use cases that I have not thought of, so please feel free to leave a comment if you find a way I can improve this class or have a feature request. In the next paragraph, I describe what the code is doing, or if you don't care, you can jump straight to the code below it. Enjoy.

How it works: Fist we get a list of PropertyInfo from the class. This will effectively be a list of properties in that class that we will want to fill. PropertyInfo exposes the Name property and the SetValue method, which takes an object and a value as parameters.
    We are going to make three nested loops to do this (one for each DataRow, one for each PropertyInfo and one for each DataColumn) and return a List of classes, each one filled out from a single row in the DataTable. It is possible to fill out one class provided a DataTable and row index in only two nested loops, and this post will provide that example too.
    For each row in DataTable.Rows, we will need to loop through each property (to fill them) and then loop through each DataTable's DataColumn and match the PropertyInfo.Name to the DataColumn.ColumnName. We then call the PropertyInfo's SetValue method. This function will take advantage of generics so that we can pass in any class as a parameter.

Here is the code:

public static class Helper
{
   public static class Table
   {
      /// <summary>
      /// Fills the public properties of a class from the first row of a DataTable
      ///  where the name of the property matches the column name from that DataTable.
      /// </summary>
      /// <param name="Table">A DataTable that contains the data.</param>
      /// <returns>A class of type T with its public properties matching column names
      ///      set to the values from the first row in the DataTable.</returns>
      public static T ToClass<T>(DataTable Table) where T : class, new()
      {
          T result = new T();
          if (Validate(Table))
          {  // Because reflection is slow, we will only pass the first row of the DataTable
              result = FillProperties<T>(Table.Rows[0]);
          }
          return result;
      }
       
      /// <summary>
      /// Fills the public properties of a class from each row of a DataTable where the name of
      /// the property matches the column name in the DataTable, returning a List of T.
      /// </summary>
      /// <param name="Table">A DataTable that contains the data.</param>
      /// <returns>A List class T with each class's public properties matching column names
      ///      set to the values of a diffrent row in the DataTable.</returns>
      public static List<T> ToClassList<T>(DataTable Table) where T: class, new()
      {
          List<T> result = new List<T>();
          
          if (Validate(Table))
          {
              foreach(DataRow row in Table.Rows)
              {
                   result.Add(FillProperties<T>(row));
              }
          }
          return result;
      }
       
      /// <summary>
      /// Fills the public properties of a class from a DataRow where the name
      /// of the property matches a column name from that DataRow.
      /// </summary>
      /// <param name="Row">A DataRow that contains the data.</param>
      /// <returns>A class of type T with its public properties set to the
      ///      data from the matching columns in the DataRow.</returns>
      public static T FillProperties<T>(DataRow Row) where T: class, new()
      {
          T result = new T();
          Type classType = typeof(T);
          
          // Defensive programming, make sure there are properties to set,
          //   and columns to set from and values to set from.
          if(    Row.Table.Columns.Count < 1
              || classType.GetProperties().Length < 1
              || Row.ItemArray.Length < 1)
          {
              return result;
          }
          
          foreach (PropertyInfo property in classType.GetProperties())
          {
              foreach(DataColumn column in Row.Table.Columns)
              {
                  // Skip if Property name and ColumnName do not match
                  if(property.Name != column.ColumnName)
                      continue;
                  // This would throw if we tried to convert it below
                  if(Row[column] == DBNull.Value)
                      continue;
                  
                  object newValue;
                  
                  // If type is of type System.Nullable, do not attempt to convert the value
                  if (IsNullable(property.PropertyType))
                  {
                      newValue = Row[property.Name];
                  }
                  else
                  {   // Convert row object to type of property
                      newValue = Convert.ChangeType(Row[column], property.PropertyType);
                  }
                  
                  // This is what sets the class properties of the class
                  property.SetValue(result, newValue, null);
              }
          }
          return result;
      }
       
      /// <summary>
      /// Checks a DataTable for empty rows, columns or null.
      /// </summary>
      /// <param name="DataTable">The DataTable to check.</param>
      /// <returns>True if DataTable has data, false if empty or null.</returns>
      public static bool Validate(DataTable DataTable)
      {
          if (DataTable == null) return false;
          if (DataTable.Rows.Count == 0) return false;
          if (DataTable.Columns.Count == 0) return false;
          return true;
      }
       
      /// <summary>
      /// Checks if type is nullable, Nullable<T> or its reference is nullable.
      /// </summary>
      /// <param name="type">Type to check for nullable.</param>
      /// <returns>True if type is nullable, false if it is not.</returns>
      public static bool IsNullable(Type type)
      {
          if (!type.IsValueType) return true; // ref-type
          if (Nullable.GetUnderlyingType(type) != null) return true; // Nullable<T>
          return false; // value-type
      }
   }
}

Wednesday, April 9, 2014

An Implementation of a One-Way Hashing Algorithm using Substitution and Permutation




        This program is a one-way hashing algorithm that can be used for hashing passwords or verifying a file's integrity. Like other ciphers, it has rounds. While this particular implementation was designed to overwrite some of the information required to reverse the rounds operations to be asymmetric, the same core 'substitution' algorithm could be used to make a symmetric stream cipher by taking a different approach.
        Each round proceeds as follows: First a scrambling or mangling (sounds violent) of a substitution table is performed before substituting the plain-text (or last round's output) with values from the table chosen by the index corresponding to the plain-text character's equivalent byte value. The substituted-text is then converted into a List of bits (bool) and the list then split in half into two lists of bits. One of the lists of bits is optionally flipped (reversed) based on the value of the first bit of that list. The value of the middle bit of the other list is used to determine which list is to lead during the (next step) bit shuffling. Starting with the selected list, the bits of the two lists are interleaved (shuffled) making one list again. The bits are converted back into bytes via an extension method and used as the input for the next round.
        The substitution/cipher block step uses a variation of the RC4 cipher with the key-scheduling algorithm dropped in favor of a pseudo-random-appearing, but evenly distributed table with each number from 0 to 256 appearing exactly once. This table is deterministically populated by an initial value, IV, which is some number that is both greater than 256 and co-prime to it. Starting with zero, set each byte in the table to the value plus IV, modulus 256, in order. Then, to 'prime' the table/block, iterate over the table several thousand times with the RC4 algorithm, discarding the byte stream (in the case of RC4). In the case of my particular RC4 variant implementation, the result byte is put into the table at an index that congruent to 256 modulus the current iteration count multiplied by some co-prime of 256, in this case, 331.
        While many people believe that RC4 is well on its way to being broken, it is my hope that by using a smarter key-scheduling function with a different (larger) block size and maybe some bit country line-dancing (shuffling) will make a variant of RC4 that we all can have confidence in again. Hmm, there is already an RC5 and RC6. Maybe a good name would be RC4.1 or RC4.Awesome. RC4 and seven thirteenths? R2C2 perhaps? No, I got it: The stream cipher formally known as RC4. RC4Realz or RCL33t? Anyways, this article is not about symmetric algorithms, but rather asymmetric ones, so read on...

        Cryptography is one of my interests. I love the math behind it and I think the mechanics behind RSA are just so elegant. I often daydream that one day I will be able to come out with something incredibly clever and useful. For the past several months, I have been working on implementing several different concepts of cryptography in C#. I have wrote several classes that do one specific type of job, such as transposition, permutation or substitution. I have been toying with combinations these different methods into 'rounds', with each round getting its input from the output of the previous round.  In this post, I am proposing a one-way hashing algorithm that uses a combination of bit-shuffling (permutation) and a substitution table with logic that mangle the table based on the current state of the table. It is possible to make an asymmetric algorithm from this idea, but that is not the aim of this particular tool.

        This algorithm still has some areas that need improving. First of all, its rather slow, so hashing large files is not practical. The number of rounds has a large baring on its hash time. A smaller number of rounds is recommended for anything beyond a paragraph. The current default is 18. This is rather arbitrary, as I have not done any testing to find the optimal number of rounds. Anyone who uses less than 4 rounds will start to see some repeating characters, not to mention make their implementation more susceptible to cryptanalysis. Sometimes a lengthy hashing time can be desirable, such as a proof of work concept, or to make it more difficult to brute force. For a password-length input at 1024 rounds, it takes almost a full second.


        Another area for improvement is the permutation step; is basically just shuffles the bits by dividing the bit array in half and interleaving the bits (think a deck of cards). While there is some variation in the order, based off the input, a much better bit shuffling would probably be an expansion or compression style of permutation. See this link to Wikipedia for an visual depiction.


        Well that about sums it up, so now on to the code! Take note at how I used extension methods to take care of converting a BitArray and a Byte array into a string, and back again. This makes the code very readable and not take up nearly as many lines by reusing code. The code is pretty heavily commented, so I will just let it explaining itself:





public class AJRHash
{
 byte[] table;
 // Unsure the optimum setting for rounds.
 // No less that 4. 1024 takes around 1 second for password-length hashes.
 // Use lower setting for large hashes
 static int rounds = 18;
 static int minimumLength = 10;
 static int tableSize = 256; // Because we are using bytes
 // By choosing a co-prime to 256, we ensure we get an evenly distributed table
 static int[] coprimesOf256 = { 4489, 2209, 1369 }; // Changing the co-primes will change the hash
 
 public AJRHash()
 {
  table = new byte[tableSize];
  InitializeTable();
 }
 
 public string Hash(string Input)
 {
  // Pad the input to minimum length
  if(Input.Length<minimumLength)
  {
   List<byte> padding = new List<byte>();
   
   // Copy the input first
   if(Input.Length>0)
    padding.AddRange(Input.GetBytes());
   
   // Make up the diffrence with nulls
   int diffrence = minimumLength - Input.Length;
   while(diffrence>0)
   {
    padding.Add(0);
    diffrence--;
   }
   Input = padding.ToArray().GetString();
  }
  
  byte[] permutation = Input.GetBytes();
  byte[] substitution = new byte[Input.Length+1];
  
  int counter = rounds;
  while(counter>0)
  {
   substitution = Substitution(permutation);
   permutation  = Permutation_Interleave(substitution);
   counter--;
  }

  return Convert.ToBase64String(permutation);
 }
 
 void InitializeTable()
 {
  int prime = coprimesOf256[0];
  
  byte index = 0;
  for (int i = 0; i < tableSize; i++)
  {
   table[index] = (byte)i;
   
   unchecked // The large prime will just roll over. Essentially just modular arithmetic
   { // By choosing a co-prime to 256, we ensure we get an evenly distributed table
    index += (byte)prime;
   }
  }
  
  // Finish initializing the table by shuffling it
  ScrambleTable(prime);
 }
 
 void ScrambleTable(int iterations)
 {
  byte i = 0;
  byte j = 0;
  byte k = 0;
  byte l = 0;
  
  byte iteration = 0;
  int counter = iterations;
  
  // Just roll over on overflow
  unchecked
  {
   // Some initial values
   j=table[table.Length/2];
   i=table[j];

   // Use the current state of the table to determine how it is changed
   while(counter>0)
   {
    i++;
    l=(byte)(table[i]+1);
    j=(byte)(j+l+1);
    
    table[i] = (byte)(j + 3);
    table[j] = (byte)(l - 1);
    
    k = (byte)( (table[i] + table[j]));
    l = (byte)(k % 255);
    
    table[k] = (byte)(table[k]+1);
    
    k = table[l];
    l = table[iteration];
    
    table[(byte)(iteration*331)] = (byte)(k ^ l);
    
    counter--;
    iteration++;
   }
  }
 }
 
 byte[] Substitution(byte[] input)
 {
  // Shuffle the table by an ammount unique to the input
  ScrambleTable(input.Length*input[0]);
  
  // Apply input against the substitution table
  List<byte> result = new List<byte>();
  foreach(byte b in input)
  {
   result.Add( table[(int)b] );
  }
  
  return result.ToArray();
 }
 
 // TODO: Add more robust bit shuffling/permutation such as compression or expansion
 byte[] Permutation_Interleave(byte[] input)
 {
  // Convert input into an array of bits
  BitArray temp = new BitArray(input);
  List<bool> bits = temp.GetList();
  
  // Ensure we have an even number of bits
  if(bits.Count%2 != 0)
   bits.Add(false);
  
  // Split the input up into two arrays of bits
  List<bool[]> split = bits.Split();
  
  // Make sure we have at least two arrays to interleave
  if(split.Count<2)
   throw new Exception("Input is too short.");
  
  bool[] one = split[0];
  bool[] two = split[1];
  
  // Ensure both arrays are the same length
  if(one.Length != two.Length)
   throw new Exception("Lengths must match.");
  
  // If the first bit of two is 1, reverse it.
  //   This makes the deterministic shuffling more difficult to reverse 
  if(two[0])
   Array.Reverse(two);
  
  // If the 'middle' bit of one is 1, take from two first.
  //   This makes the deterministic shuffling more difficult to reverse
  bool SecondFirst = false;
  if(one[one.Length/2])
   SecondFirst = true;
  
  // Interleave the two arrays
  int counter = 0;
  List<bool> result = new List<bool>();
  while(counter<one.Length)
  {
   // Two possible ways to order (decided above)
   if(SecondFirst)
   {
    result.Add(two[counter]);
    result.Add(one[counter]);
   }
   else
   {
    result.Add(one[counter]);
    result.Add(two[counter]);
   }
   counter++;
  }
  
  return new BitArray(result.ToArray()).GetBytes();
 }
}



I also wrote a few extension methods to help with all the tedious converting of data types. Extension methods can help keep you code tidy, readable. Don't forget to add these extension methods, or the above code wont compile:




public static class ExtentionMethods
{
 public static byte[] GetBytes(this string Input)
 {
  if(Input == null) return new byte[0];   
  return Encoding.UTF8.GetBytes(Input);
 }
 
 public static string GetString(this byte[] Input)
 {
  if(Input == null) return string.Empty;   
  return Encoding.UTF8.GetString(Input);
 }
 
 public static string GetString(this BitArray Input)
 {
  if(Input == null) return string.Empty;   
  return Encoding.UTF8.GetString(Input.GetBytes());
 }
 
 public static byte[] GetBytes(this BitArray Input)
 {
  if(Input == null) return new byte[0];   
  int lengthInBytes = (Input.Length%8==0) ? Input.Length/8 : (Input.Length/8)+1;
  
  byte[] result = new byte[lengthInBytes];
  Input.CopyTo(result,0);
  return result;
 }
 
 public static bool[] GetArray(this BitArray Input)
 {
  if(Input == null) return new bool[0];   
  return Input.GetList().ToArray();
 }
 
 public static List<bool> GetList(this BitArray Input)
 {
  if(Input == null) return new List<bool>();
  
  List<bool> result = new List<bool>();
  foreach(bool b in Input)
  {
   result.Add(b);
  }   
  return result;
 }
 
 public static List<bool[]> Split(this List<bool> Input)
 {
  if(Input == null) return new List<bool[]>();
  
  int midpoint = (Input.Count/2);
  List<bool> result1 = new List<bool>();
  List<bool> result2 = new List<bool>();
  
  int counter = 0;
  foreach(bool b in Input)
  {
   if(counter<midpoint)
   {
    result1.Add(b);
   }
   else
   {
    result2.Add(b);
   }    
   counter++;
  }
  
  List<bool[]> result = new List<bool[]>();
  result.Add(result1.ToArray());
  result.Add(result2.ToArray());
  return result;   
 }
}

Wednesday, August 21, 2013

HowJSay Browser Plugins IE9, Chrome, Firefox

This plugin will add a context menu for IE9, Chrome and Firefox menus. When you select a text and right-click a text, you want to know not only how that word is spelled, but how it is pronounced. I elected HowJSay.com as the perfect venue for launching a new browser window for learning how to pronounce things proper. As I have always said, proper pronunciation is next to godliness.

Instructions: Simply highlight the word you want to have pronounced for you. Right-click on selected text to bring up the context menu. Simply click on 'Pronounce with Howjsay' (Under 'All Accelerators' in IE8) and a new window or tab will be opened to the appropriate page for that word on howjsay.com. Make sure your volume is not muted or too low. If you missed the pronounciation, you can mouse-over the word on howjsay to have it pronounced again.


Simply find your browser below:


Google chrome users
Instructions: If you can download the .crx, Google should automatically prompt you to install the plugin. If it does not, you download the .zip file and once downloaded, extract into a folder. Go into Google chrome's settings (the wrench icon), then click on 'extensions' in the left pane. In the right pane at the top, make sure the 'Developer mode' box is checked. Click on the 'Load unpacked extension...' button and select the folder that you extracted the .zip into. Click okay and Google will install the extension.

Installation links: Click here for a .crx file. Click here if you want to download as a .zip file.


Internet explorer users

Instructions: If you are using IE to browse this page, you should see a button below. Click on it to install the accelerator.





Firefox users

Instructions: It is easiest to install the FireFox extension through the secure add-on page hosted by addons.mozilla.org


Installation link: Click here for our secure add-on page hosted by addons.mozilla.org

Wednesday, August 7, 2013

Pseudo 'random' even distribution table




In my last post, I discussed what a co-prime is and showed you to find them.

So, what's so special about relatively prime numbers? Well, then can be used to create an one-for-one distribution table that is seemingly random, but is deterministically calculated (created).

To understand what I mean, picture the face of a clock...


It has the hours 1 through 12, and if you and an hour to 12, you get 1. This can also be thought of as a single digit in a base 12 number system. Now we need a co-prime to 12. 7 is relatively prime to 12, so lets choose 7.

Starting at hour 1, if we add 7 hours, it will be 8. If we add 7 more hours, we will get 3. 7 more, 10. If we keep adding 7 hours to our clock, the hour hand will land on each of the different numbers exactly once before repeating itself, 12 steps later. Intrigued yet?

If, say, we find a co-prime to the largest number that can be represented by a byte (8-bits, 256 [also expressed as 2^8=256 or 8=Log2(256)]), we can create an array of bytes with a length of 256, containing each of the 256 different possible bytes, distributed in a seemingly random order. The discrete order, or sequence, in which each each number is visited it completely dependent on the value of the co-prime that was selected.

This table is now essentially a one-to-one, bijective mapping of one byte to another. To express this mapping to another party, say to map a stream of bytes back to their original values (decrypt), the entire table need not be exchanged, only the co-prime.

This provides a foundation for an encryption scheme who's technical requirements are similar to handling a cipher-block-chain (CBC) and its changing IV (initialization vector).

Now, it it easy to jump to the conclusion that such an encryption scheme is less secure than a CBC, but this is not necessarily the case. While this approach may be conceptually more simple, the difficulty of discovering the sequence can be made arbitrarily hard.

First of all, the number of relatively prime numbers to 256 is probably infinite. A co-prime to 256 does not have to be less than 256. Indeed, it may be several thousand time greater than 256. Additionally, any prime greater than 256 is, by definition, co-prime to 256, and likely will have a seemingly more 'random' distribution/appearance.

There is, however, a limit here. It does not have to do with the number of co-primes, but is instead limited by the number of possible sequences that can be represented by our array of 256 bytes; eventually, two different co-primes are going to map to the same unique sequence. The order matters, and we don't allow repetition to exist in our sequence. This is called a permutation without repetition, and can be expressed as 256! or 256 factorial and is instructing one to calculate the product of 256 * 255 * 254 * 253 * [...] * 6 * 5 * 4 * 3 * 2 * 1, which equals exactly this number:

857817775342842654119082271681232625157781520279485619859655650377269452553147589377440291360451408450375885342336584306157196834693696475322289288497426025679637332563368786442675207626794560187968867971521143307702077526646451464709187326100832876325702818980773671781454170250523018608495319068138257481070252817559459476987034665712738139286205234756808218860701203611083152093501947437109101726968262861606263662435022840944191408424615936000000000000000000000000000000000000000000000000000000000000000

Yeah, that's right, that number has exactly 63 zeros on the end and is 507 digits long. (As an aside, the reason there is so many zeros on the end of this number is, well for one it is highly composite, but more specifically, its prime factorization includes 2^255 and 5^63 and so 63 fives multiply with 63 of those twos to make 63 tens, and hence that many zeros.)

Above I said arbitrarily hard. So far we have only considered one table, but try and fathom the complexity of many tables. I present three different ways to use multiple tables; Nested, sequentially, and mangled.
Furthermore, the distribution tables can be discarded and replaced.

I will explain what those mean and finish this post tomorrow.


Sunday, August 4, 2013

Topmost window always on top




This project was inspired by PowerMenu 1.51 by Thong Nyguyen. I wrote a small C# system tray application that provides some of the same functionality as PowerMenu. It can set/unset any application window as always on top or topmost. This is useful if you want to compare or edit two documents at once and you want to make a window float, sticky, or pin a window on top. I wrote this tool in C# and am giving you the source code here so you can see how it works. Since .NET does not support such level of control over other applications, our code must call the native WIN32 APIs SetWindowPos and FindWindow to accomplish this.

Besides being a system tray application (NotifyIcon), the application essentially has two main functions: GetWindowTitles(), which uses the Process class to return a list of windows' titles as an array of strings, and AssignTopmostWindow() which takes a windows title as a parameter.

But first, we must define our WIN32 API imports:

#region WIN32API
static readonly IntPtr HWND_TOPMOST = new IntPtr(-1);
static readonly IntPtr HWND_NOTOPMOST = new IntPtr(-2);
const UInt32 SWP_SHOWWINDOW = 0x0040;

[StructLayout(LayoutKind.Sequential)]
public struct RECT
{
    public int Left, Top, Right, Bottom;
    public RECT(int left,int top,int right,int bottom) {
        Left=left; Top=top; Right=right; Bottom=bottom; }
    public RECT(System.Drawing.Rectangle r) : this(r.Left, r.Top, r.Right, r.Bottom) { }
    public int X { get { return Left; } set { Right -= (Left - value); Left = value; } }
    public int Y { get { return Top; } set { Bottom -= (Top - value); Top = value; } }
    public int Height { get { return Bottom - Top; } set { Bottom = value + Top; } }
    public int Width { get { return Right - Left; } set { Right = value + Left; } }
    public static implicit operator System.Drawing.Rectangle(RECT r) {
        return new System.Drawing.Rectangle(r.Left, r.Top, r.Width, r.Height); }
    public static implicit operator RECT(System.Drawing.Rectangle r) { return new RECT(r); }
}

[DllImport("user32.dll", SetLastError = true)]
private static extern IntPtr FindWindow(String lpClassName, String lpWindowName);

[DllImport("user32.dll")]
[return: MarshalAs(UnmanagedType.Bool)]
public static extern bool GetWindowRect(HandleRef hwnd, out RECT lpRect);

[DllImport("user32.dll")]
[return: MarshalAs(UnmanagedType.Bool)]
private static extern bool SetWindowPos(IntPtr hWnd, IntPtr hWndInsertAfter,
                                        int x, int y, int cx, int cy, uint uFlags );
#endregion

Notice the RECT structure. The WIN32 RECT struct is different than the .NET version, and we need it to store and pass the window position during our call to SetWindowPos() or the window will likely disappear during resizing.

Here you can see in our implementation of AssignTopmostWindow, we get the window rectangle with GetWindowRect() and pass it straight to our call to SetWindowPos():

bool AssignTopmostWindow(string windowTitle,bool makeTopmost)
{
 IntPtr hWnd = FindWindow((string)null,windowTitle);
 
 RECT rect = new RECT();
 GetWindowRect(new HandleRef(this,hWnd),out rect);
 
 return SetWindowPos(hWnd,
              makeTopmost ? HWND_TOPMOST : HWND_NOTOPMOST,
              rect.X, rect.Y, rect.Width, rect.Height,
              SWP_SHOWWINDOW);
}

So your application is first going to want to get the titles of all the forms and windows:

string[] GetWindowTitles()
{
 List<string> winList = new List<string>();
 
 Process[] procArray = Process.GetProcesses();
 foreach(Process proc in procArray)
 {
  if(!string.IsNullOrWhiteSpace(proc.MainWindowTitle))
  {
   winList.Add(proc.MainWindowTitle);
  }
 }
 return winList.ToArray();
}

Then your application must then fill a listbox or somehow display this data to the user for selection. I choose to populate a dynamic context menu for my NotifyIcon application:

private MenuItem[] DynamicMenu()
{
 string[] titleArray = GetWindowTitles();
 
 List<MenuItem> menuList = new List<MenuItem>();
 foreach(string title in titleArray)
 {
  if(changeLog.ContainsKey(title))
  {
   if(changeLog[title])
   {
    menuList.Add(new MenuItem("* " + title, menuWinClick));
   }
   else
   {
    menuList.Add(new MenuItem(title, menuWinClick));
   }
  }
  else
  {
   menuList.Add(new MenuItem(title, menuWinClick));
  }
 }
 menuList.Add(new MenuItem("_____________"));
 menuList.Add(new MenuItem("About", menuAboutClick));
 menuList.Add(new MenuItem("Exit", menuExitClick));
 
 return menuList.ToArray();
}
Once the user has made a selection, a call to AssignTopmostWindow is made.

If your application should happen to exit without another call to AssignTopmostWindow(selectedTitle,false) to undo the topmost property, the window will remain topmost until reboot. As this is likely undesirable behavior, . My solution was to create a dictionary to keep track of the windows whose topmost property was modified, and 'roll back' those changes when your program/form is ending/closing:


private Dictionary<string,bool> changeLog = new Dictionary<string, bool>();

private void menuExitClick(object sender, EventArgs e)
{
 // Roll-back changes by
 //  unsetting every topmost window
 foreach(KeyValuePair<string,bool> entry in changeLog)
 {
  if(entry.Value) // If topmost
  {
   AssignTopmostWindow(entry.Key,false);
  }
 }   
 Application.Exit();
}


Here is the full code.

Thursday, August 1, 2013

Greatest common divisor & Co-primeness



Below are three different methods for finding the greatest common divisor of a number. I provide a method using modulus, one using Euclid's method, and one that uses the Stein method.

Believe it or not, the modulus method has the best performance. I would have guessed the Stein method. Credit goes to blackwasp for the stein method.


public static uint FindGCDModulus(uint value1, uint value2)
{
        while(value1 != 0 && value2 != 0)
        {
                if (value1 > value2)
                {
                        value1 %= value2;
                }
                else
                {
                        value2 %= value1;
                }
        }
        return Math.Max(value1, value2);
}

public static uint FindGCDEuclid(uint value1, uint value2)
{
        while(value1 != 0 && value2 != 0)
        {
                if (value1 > value2)
                {
                        value1 -= value2;
                }
                else
                {
                        value2 -= value1;
                }
        }
        return Math.Max(value1, value2);
}

public static uint FindGCDStein(uint value1, uint value2)
{
        if (value1 == 0) return value2;
        if (value2 == 0) return value1;
        if (value1 == value2) return value1;

        bool value1IsEven = (value1 & 1u) == 0;
        bool value2IsEven = (value2 & 1u) == 0;
                       
        if (value1IsEven && value2IsEven)
        {
                return FindGCDStein(value1 >> 1, value2 >> 1) << 1;
        }
        else if (value1IsEven && !value2IsEven)
        {
                return FindGCDStein(value1 >> 1, value2);
        }
        else if (value2IsEven)
        {
                return FindGCDStein(value1, value2 >> 1);
        }
        else if (value1 > value2)
        {
                return FindGCDStein((value1 - value2) >> 1, value2);
        }
        else
        {
                return FindGCDStein(value1, (value2 - value1) >> 1);
        }
}

Here are the results of my benchmark tests:

Stein: 36.4657 milliseconds.
Euclid: 31.2369 milliseconds.
Modulus: 7.5199 milliseconds.



Yeah, I couldn't believe it either, the modulus approach is the fastest!

Here is the benchmark code that I created:

public class CodeStopwatch
{
        //int m_pointer;
        Stopwatch m_elapsed;
        
        public CodeStopwatch()
        {
                Reset();
        }

        public double Stop()
        {
                m_elapsed.Stop();
                return m_elapsed.Elapsed.TotalMilliseconds;
        }
        
        public void Reset()
        {
                GC.Collect(GC.MaxGeneration);
                m_elapsed = new Stopwatch();
                m_elapsed.Start();
        }
}

public class CoprimeBenchmark
{
        public delegate bool IsCoprimeDelegate(uint value1, uint value2);
        public List<uint> FindCoprimesDelegate(uint quantity,IsCoprimeDelegate isCoprime)
        {
                List<uint> results = new List<uint>();
                if(quantity<2) {
                        return results;
                }
                
                for (uint count = 2; count < quantity; count++)
                {
                        if(isCoprime(count,quantity))
                        {
                                results.Add(count);
                        }
                }
                return results;
        }
        
        public static bool IsCoprimeModulus(uint value1, uint value2)
        {
                return FindGCDModulus(value1, value2) == 1;
        }
        
        public static bool IsCoprimeEuclid(uint value1, uint value2)
        {
                return FindGCDEuclid(value1, value2) == 1;
        }
        
        public static bool IsCoprimeStein(uint value1, uint value2)
        {
                return FindGCDStein(value1, value2) == 1;
        }

        // [ Please refer to methods above. Ommited for brevity. ]
        public static uint FindGCDModulus(uint value1, uint value2) { ... }
        public static uint FindGCDEuclid(uint value1, uint value2) { ... }
        public static uint FindGCDStein(uint value1, uint value2) { ... }
}

Usage of above classes:

// Button OnClick event
void ButtonBenchmarkClick(object sender, EventArgs e)
{
        uint number = 50000;
        List<uint> resultsStein = new List<uint>();
        List<uint> resultsEuclid = new List<uint>();
        List<uint> resultsModulus = new List<uint>();
        
        CoprimeBenchmark cop = new CoprimeBenchmark();
        
        CodeStopwatch time = new CodeStopwatch();
        resultsStein = cop.FindCoprimesDelegate(number,CoprimeBenchmark.IsCoprimeStein);
        string stein = time.Stop().ToString();
        
        time = new CodeStopwatch();
        resultsEuclid = cop.FindCoprimesDelegate(number,CoprimeBenchmark.IsCoprimeEuclid);
        string euclid = time.Stop().ToString();
        
        time = new CodeStopwatch();
        resultsModulus = cop.FindCoprimesDelegate(number,CoprimeBenchmark.IsCoprimeModulus);
        string modulus = time.Stop().ToString();
        
        textBoxOutput.Text = "Stein:\t" + stein + " milliseconds." + Environment.NewLine;
        textBoxOutput.Text += "Euclid:\t" + euclid + " milliseconds." + Environment.NewLine;
        textBoxOutput.Text += "Modulus:\t" + modulus + " milliseconds." + Environment.NewLine;
        
        textBoxOutput.Text += Environment.NewLine + Environment.NewLine;
        foreach(uint a in resultsStein)
        {
                textBoxOutput.Text += a.ToString() + Environment.NewLine;
        }
        
        textBoxOutput.Text += Environment.NewLine + Environment.NewLine;
        foreach(uint b in resultsEuclid)
        {
                textBoxOutput.Text += b.ToString() + Environment.NewLine;
        }
        
        textBoxOutput.Text += Environment.NewLine + Environment.NewLine;
        foreach(uint c in resultsModulus)
        {
                textBoxOutput.Text += c.ToString() + Environment.NewLine;
        }
}


--


Now, I will take the fastest algorithm and show you the code for finding co-primness and a list of co-primes for a given number.

Finding co-primness is simple; Two numbers are relatively prime to each other if their greatest common divisor is equal to one.

My function FindCoprimes returns a List<uint> of co-primes given a number and a range

public static class Coprimes
{
        public static List<uint> FindCoprimes(uint number,uint min,uint max)
        {
                if(max<2 || min<2 || max<=min || number<1) {    return null;    }
                
                List<uint> results = new List<uint>();
                for(uint counter = min; counter<max; counter++) {
                        if(IsCoprime(number,counter)) {
                                results.Add(counter);
                        }
                }
                return results;
        }
       
        public static bool IsCoprime(uint value1, uint value2)
        {
                return FindGCDModulus(value1, value2) == 1;
        }
}

Pretty easy!

What is so special about co-primes? Well, one thing I use co-primes for is for making an evenly distributed table. For an explanation and the code, see my post on Evenly Distributed Tables.



Captcha: Drawing Text along a Bézier Spline



The following post/code will achieve something to the effect of:


All this code, and this article was inspired by planetclegg.com/projects/WarpingTextToSplines.html.
Explanation of the math and why it works will come shortly. In the meantime, please see the above link for a detailed explanation.

This code assumes you have already drawn some text on your GraphicsPath. Here is the code to transform your GraphicsPath text to follow a cubic Bézier Spline:

GraphicsPath BezierWarp(GraphicsPath text,Size size)
{
 // Control points for a cubic Bézier spline
 PointF P0 = new PointF();
 PointF P1 = new PointF();
 PointF P2 = new PointF();
 PointF P3 = new PointF();
 
 float shrink = 20;
 float shift = 0;
 
 P0.X = shrink;
 P0.Y = shrink+shift;
 P1.X = size.Width-shrink;
 P1.Y = shrink;
 P2.X = shrink;
 P2.Y = size.Height-shrink;
 P3.X = size.Width-shrink;
 P3.Y = size.Height-shrink-shift;

 // Calculate coefficients A thru H from the control points
 float A = P3.X - 3 * P2.X + 3 * P1.X - P0.X;
 float B = 3 * P2.X - 6 * P1.X + 3 * P0.X;
 float C = 3 * P1.X - 3 * P0.X;
 float D = P0.X;

 float E = P3.Y - 3 * P2.Y + 3 * P1.Y - P0.Y;
 float F = 3 * P2.Y - 6 * P1.Y + 3 * P0.Y;
 float G = 3 * P1.Y - 3 * P0.Y;
 float H = P0.Y;

 PointF[] pathPoints = text.PathPoints;
 RectangleF textBounds = text.GetBounds();
 
 for (int i =0; i  < pathPoints.Length; i++)
 {
  PointF pt = pathPoints[i];
  float textX = pt.X;
  float textY = pt.Y;
  
  // Normalize the x coordinate into the parameterized
  // value with a domain between 0 and 1.
  float t  =  textX / textBounds.Width;
  float t2 = (t * t);
  float t3 = (t * t * t);
  
  // Calculate spline point for parameter t
  float Sx = A * t3 + B * t2 + C * t + D;
  float Sy = E * t3 + F * t2 + G * t + H;
  
  // Calculate the tangent vector for the point
  float Tx = 3 * A * t2 + 2 * B * t + C;
  float Ty = 3 * E * t2 + 2 * F * t + G;

  // Rotate 90 or 270 degrees to make it a perpendicular
  float Px = - Ty;
  float Py =   Tx;
  
  // Normalize the perpendicular into a unit vector
  float magnitude = (float)Math.Sqrt((Px*Px) + (Py*Py));
  Px /= magnitude;
  Py /= magnitude;
  
  // Assume that input text point y coord is the "height" or
  // distance from the spline.  Multiply the perpendicular
  // vector with y. it becomes the new magnitude of the vector
  Px *= textY;
  Py *= textY;
  
  // Translate the spline point using the resultant vector
  float finalX = Px + Sx;
  float finalY = Py + Sy;
  
  pathPoints[i] = new PointF(finalX, finalY);
 }
 
 return new GraphicsPath(pathPoints,text.PathTypes);
}