Archive for October 2011

The Step-by-Step RSA Algorithm

Security is important and there is a lot to learn. I am reading the book Security in Computing and trying to memorize the RSA algorithm.

Prerequisite Math Knowledge

You must understand the following mathematical principles to understand this algorithm and if you don’t understand these principles, look them up first (I had to look up the last one, the Euler totient function, as I had never heard of it):

  • Exponentials
  • Prime numbers
  • Prime factorization
  • Greatest Common Denominator (GCD)
  • Modular arithmetic
  • Euler totient function

This is also going to have development in mind, so you maybe should also understand: binary, char, bits, ascii, UTF-8, etc..

The book is good. However, it can be quite annoying for me when it shows algorithms using one character variables. This may be the mathematical way but I prefer to use a developer style where variables are named clearly. I need to make sure I understand how RSA works so I am going to write about it.

Here is an example of how they use just one character:

The RSA algorithm uses two keys, d and e, which work in pairs, for decryption and encryption, respectively. A plaintext message P is encrypted to ciphertext C by

C = Pe mod n

The plaintext is recovered by

P = Cd mod n

Because of symmetry in modular arithmetic, encryption and decryption are mutual inverses and commutative. Therefore,

P = Cd mod n = (Pe)d mod n = (Pd)e mod n

This relationship means that one can apply the encrypting transformation and then the decrypting one, or the one followed by the encrypting one.1

I would never write code this way and looking at this, it might leave one who is not an expert wondering what do the variables P, C, d, e, n represent again? And is there a reason P, C are capitalized and d, e, n are lower case? Lets rewrite these with nice developer variable names where the name comments itself based on the what it really is. In the quoted text above each variable is defined clearly except what “mod n” really represents, I had to read on to determine this. Also, where to get the values for each variable is not defined, again, I had to read on to determine this, and this led to more equations to add to the list.These are the equations, in order

Equation List

  1. ProductOfPrime1Prime2 = Prime1 * Prime2
  2. Totient = (Prime1 – 1) * (Prime2 -1)
  3. (Totient * AnyInteger) + 1 = 1 mod Totient
  4. EncryptPrime * DecryptPrime = 1 mod Totient
  5. EncryptPrime * DecryptPrime = (Totient * AnyInteger) + 1 where (Totient * AnyInteger) + 1 has exactly prime factors
  6. CipherText = PlainTextEncryptPrime mod ProductOfPrime1Prime2
  7. PlainText = CiphertextDecryptPrime mod ProductOfPrime1Prime2
  8. PlainText = CiphertextDecryptPrime mod ProductOfPrime1Prime2 = (PlainTextEncryptPrime)DecryptPrime mod ProductOfPrime1Prime2 = (PlainTextDecryptPrime)EncryptPrime mod n

Some of the values above you get to “choose” or if you were writing this algorithm in code, you would probably not “choose” so much as generate the value at random. So if we get to choose, then lets learn how to choose.

Step 1 – Choose two prime numbers, Prime1 and Prime2 to get the ProductOfPrime1Prime2 variable

So our Equation List above starts out with this simple math equation:

Prime1 * Prime2 = ProductOfPrime1Prime2

Ok, so where do you get Prime1 and Prime2 to start? You simply choose the two primes yourself. Find or generate or a list of primes and choose two. Close your eyes and point or pull them out of a hat. It doesn’t matter just choose two primes numbers.

Of course, there are recommendations for choosing primes in production use. Here are a two basic recommendations:

  1. Prime1 and Prime2 should be very large prime numbers, at minimum 100 digits long but as larger is more secure and less efficient.
  2. Prime 1 and Prime2 should not be the same prime number

Even though Prime1 and Prime2 should be very large, I want to keep this simple, so for example’s sake, let’s use two primes from the list below:

Primes between 0 and 100.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97;

So we can choose any primes we want, for this example, I will choose these two: 19, 31

ProductOfPrime1Prime2 = Prime1 * Prime2

ProductOfPrime1Prime2  = 19 * 31 = 589

ProductOfPrime1Prime2  = 589

Step 2 – Find the Totient of ProductOfPrime1Prime2

You can search the internet and to study to figure out how to get the totient, but it is pretty easy to get. Totient uses a weird symbol that looks like the letter ‘p’ but is not:

Totient = φ(ProductOfPrime1Prime2)

φ(ProductOfPrime1Prime2) = (Prime1 -1) * (Prime2 – 1)

So I guess you don’t really need to know about a totient, you can just trust me, right? Ok, mathematicians are big on proofs and not just trusting someone so, go learn totient. Anyway,  the equation is as simple as this:

Totient = (Prime1 -1) * (Prime2 – 1)

So we already chose Prime1 as 19 and Prime2 as 31 in Step 1, so we have this:

Totient = (19 – 1) * (31 – 1) = 18*30 = 540

Totient = 540

Step 3 – Get a list of possible integers that result in 1 mod Totient

So we have our third and fourth equations in the Equation List:

EncryptPrime * DecryptPrime = 1 mod Totient

(Totient * AnyInteger) + 1 = 1 mod Totient

Notice that in both equations, the right sides are the same: 1 mod Totient

We get the fifth equation in our Equation List by simply merging these equations three and four:

EncryptPrime * DecryptPrime = (Totient * AnyInteger) + 1 where (Totient * AnyInteger) + 1 has exactly two prime factors

In step 2 we determined the totient is 540, so we have this:

EncryptPrime * DecryptPrime = 1 mod 540

So here is where you need to understand modular arithmetic. There are many possible values that equal 1 mod 540. It is a series. The series can be created with this function:

(Totient * AnyInteger) + 1 = 1 mod Totient

(540 * AnyInteger) + 1 = 1 mod 540

AnyInteger is just what it sounds like, it is any integer:  1, 2, 3, 4, 5, …, 100, …, ∞

540 * 1 + 1 = 541

540 * 2 + 1 = 1081

540 * 3 + 1 = 1621

540 * 4 + 1 = 2161

540 * 5 + 1 = 2701

540 * 100 + 1 = 54001

Or we make a list of these possible values that equal 1 mod 540 (which as you can see goes on for infinity)

541, 1081, 1621, 2161, 2701, …, 54001, … , ∞

Step 5 – Choose a 1 mod Totient value with exactly two prime factors: EncryptPrime and DecryptPrime

Now that we have a list, we apply the where clause to it:

{ 541, 1081, 1621, 2161, 2701, …, 54001, …, ∞ } where (Totient * AnyInteger) + 1 has exactly two prime factors

Now is when you need to understand Prime Factorization. There are three possibilities for factors and only the second one matches our where clause.

  1. The integer is a prime (has only one factor, itself)
  2. The integer has two prime factors
  3. The integer has more than two prime factors

So let’s get the factors of the integers in our list.

541 = Prime

1081 = 23 × 47

1621 = Prime

2161 = Prime

2701 = 37 × 73

54001 = Prime

So from the short list (and remember the list is infinite, we just selected a few) we have two possible representations of 1 mod Totient.
(We didn’t even see any values with more than two prime factors but don’t worry, with bigger numbers you will find them.)

Here is another place where we get to choose. Once again, close your eyes and point or pull them out of a hat. It doesn’t matter just choose.

Again, there is a recommendation:

  1. For EncryptPrime choose a prime larger than (p – 1) or (q – 1).

For this example, I have chosen 37 × 73 even though they don’t meet the above recommendation, however, I can make either EncryptPrime or DecryptPrime, they are interchangable.

So I will make the bigger value EncryptPrime.

EncryptPrime = 73

DecryptPrime = 37

Step 6 – Encrypt

We now have everything we need to Encrypt and Decrypt.

CipherText = PlainTextEncryptPrime mod ProductOfPrime1Prime2

Lets say we have an ascii character ‘A’ or 65. We already know what all the variables except for the CipherText are.

PlainText = 65

EncryptPrime = 73

ProductOfPrime1Prime2 = 589

So lets put these values into our equation. This can be done with a simple calculator.

CipherText = 6573 mod 589 = 179

CipherText = 179

Step 6 – Decrypt

Now lets decrypt this.

PlainText = CiphertextDecryptPrime mod ProductOfPrime1Prime2

We already know what all the variables are. Normally the PlainText is not known before hand as it is known in this example.

CipherText = 179

DecryptPrime = 37

ProductOfPrime1Prime2 = 589

Lets put these values into our equation and make sure they return ‘A’ or 65.

PlainText = 17937 mod 589 = 65

PlainText = 65

How does this apply to Public/Private key security (your PC to an HTTPS web server)

It is simple. A public and private key are created on the server. When you hit a web server, the web server sends you the public key.

PublicKey contains: EncryptPrime and ProductOfPrime1Prime2

You are never sent the PrivateKey.

PrivateKey = DecryptPrime and ProductOfPrime1Prime2

This works because you cannot derive EncryptPrime from DecryptPrime and ProductOfPrime1Prime2

You encrypt everything you send to the web server with the PublicKey and they encrypt everything they send you with the PrivateKey. You can decrypt what the server sends you, but only the server can decrypt what you send back. So when you type in your Password into a your bank’s web page, your password is sent encrypted so only the server can decrypt it.

1. Pfleeger, Charles P.; Pfleeger, Shari Lawrence (2007-01-23). Security in Computing (4th Edition) (Kindle Locations 19886-19887). Prentice Hall. Kindle Edition.

Android and Xml Serialization with Simple

Xml serialization is almost becoming a standard requirement for a language these days and so as I have been taking an Android class and I couldn’t find an Xml Serialization library as part of Android by default, I set out in search of one.

I came across a java XML Serialization project called Simple.

So here is a quick entry-level example of how to use Simple in an Android development project.

Note: This walk-thru assumes you are using Eclipse.

Step 1 – Create a new Android Project

  1. Go to File | New Project and select Android.
  2. Provide a Project Name.
  3. Select the minimum build target.
  4. Provide a Package name.
  5. Click Finish.

Step 2 – Download Simple

  1. Go to the Simple download page: http://simple.sourceforge.net/download.php
  2. Extract the zip file.

Step 3 – Add the Simple library to your project

  1. Create a folder called libs in your project.
  2. Copy the jar file called simple-xml-2.6.2.jar to the libs directory you just created.Note: Be aware your version may be newer than 2.6.2.
  3. In Eclipse, right-click on simple-xml-2.6.2.jar (if it doesn’t show up refresh) and choose Build Path | Add to Build Path.

Step 4 – Create an Serializeable object

  1. Right-click on your package and choose New | Class.
  2. Provide a class name and click ok.
  3. The following is an example Person class:Person.java
    package org.jaredbarneck.cs6890;
    
    import org.simpleframework.xml.Element;
    import org.simpleframework.xml.Root;
    
    @Root
    public class Person
    {
    
    	public Person()
    	{
    	}
    
    	public Person(String inFirstName, String inLastName)
    	{
    		SetFirstname(inFirstName);
    		SetLastname(inLastName);
    	}
    
    	@Element
    	private String FirstName;
    
    	public String GetFirstName()
    	{
    		return FirstName;
    	}
    
    	public void SetFirstname(String inFirstName)
    	{
    		FirstName = inFirstName;
    	}
    
    	@Element
    	private String LastName;
    
    	public String GetLastName()
    	{
    		return LastName;
    	}
    
    	public void SetLastname(String inLastName)
    	{
    		LastName = inLastName;
    	}
    
    	@Override
    	public boolean equals(Object inObject)
    	{
    		if (inObject instanceof Person)
    		{
    			Person inPerson = (Person)inObject;
    			return this.FirstName.equalsIgnoreCase(inPerson.FirstName)
    				&& this.LastName.equalsIgnoreCase(inPerson.LastName);
    		}
    		return false;
    	}
    }
    

Step 5 – Serialize and Deserialize in your main Activity

  1. Add the following code to your main Activity:Note: Code should be clear and is commented.PersonActivity.java
    package org.jaredbarneck.cs6890;
    
    import java.io.File;
    
    import org.simpleframework.xml.Serializer;
    import org.simpleframework.xml.core.Persister;
    
    import android.app.Activity;
    import android.os.Bundle;
    
    public class PersonActivity extends Activity
    {
    	public void onCreate(Bundle savedInstanceState)
    	{
    		super.onCreate(savedInstanceState);
    		setContentView(R.layout.main);
    
    		// Create a Person object
    		Person person1 = new Person("John", "Johnson");
    
    		// Create a file to save to and make sure to use the path provided from
    		// getFilesDir().getPath().
    		File xmlFile = new File(getFilesDir().getPath() + "/Person.xml");
    
    		// Serialize the Person
    
    		try
    		{
    			Serializer serializer = new Persister();
    			serializer.write(person1, xmlFile);
    		}
    		catch (Exception e)
    		{
    			e.printStackTrace();
    		}
    
    		// Create a second person object
    		Person person2 = null;
    
    		// Deserialize the Person
    		if (xmlFile.exists())
    		{
    			try
    			{
    				Serializer serializer = new Persister();
    				person2 = serializer.read(Person.class, xmlFile);
    			}
    			catch (Exception e)
    			{
    				e.printStackTrace();
    			}
    		}
    
    		boolean b = person1.equals(person2);
    	}
    }
    

Go ahead and try this in your Android emulator and step through it with a debugger.

You have now successfully implemented Xml Serialization in Java on Android using Simple.

Architecting a large application with interface-based architecture

Design and architect and write your software solution so that its different pieces can be independent in the following ways:

  1. Develop Independently
  2. Build Independently
  3. Install Independently
  4. Test Independently
  5. Refactor/Replaced Independently

Don’t just separate the concerns in one way and call it good. Separate your concerns all the ways listed above.

What will this do for your project?

  • It will make it so it can be easily unit tested.
  • It will make it so it can be easily built.
  • It will make it so it can be easily installed.
  • It will make it so it can be easily changed: Patched, Refactored, or Replaced.

Wow, all that sounds great, why doesn’t everyone do this?

Because the one area that is harder is the initial development. You have to design a lot more. You have to code different. It can be hard.

However, it is the easiest way overall, just not the easiest way at the start developing.

How do I separate my code into pieces?

There is a though among many that a software tool should do one thing only, but it should do it really well. When you think of your entire project, that should be kept in mind.

The smallest item in a project is the likely the “object”.

The term object is very abstract. It is like the work “thing” in that it can be anything.

So look at it from a high level view. Imagine your software has four pieces.

Decoupled Architecture

Ok, how do these pieces interact? Can you build each piece without having to link to another piece? You should be able to do this.

However, you have to link to something in someway in order to use its code so what do you link to?

Interfaces.

Ok, so you double the size of your pieces by having a piece and an interface for it. These could be eight separate dlls.

If Piece1 needs Peice2, it should link to IPiece2 and not to Piece2. This allows for Piece2 to be:

  1. Any version of Piece2 that implements the interface.
  2. Refactored without breaking the Piece1 build.
  3. Replaced by a completely different implementation
  4. Mocked for testing (really the same as three but used for Unit tests)

Real life example

In real life, applications are database driven. So what if your Piece2 is a database tool and Peice1, Piece3, and Piece4 all need to access the database using Piece2.

If you link directly to Piece2, you have a problem where you must have a real database in order to test your code in Piece1, Piece3, and Piece4.

This is a huge testing burden. This prevents your tests from running as Unit Tests and instead they must be run as Functional Tests.

However, by designing properly using interfaces, you can get back to Unit Tests for Piece1, Piece3, and Piece4 by mocking Piece2.

You use IPiece2 to create a new block called Mock2, which is just a Mock of Piece2, which can be run during a Unit Test. Now all the other blocks are testable.

Lets look at our Independent Architecture rules and see if this design works.

  • Yes – It will make it so it can be easily unit tested.
  • Yes – It will make it so it can be easily built.
  • Yes – It will make it so it can be easily installed.
  • Yes – It will make it so it can be easily changed: Patched, Refactored, or Replaced.

If you have a large application, this is one design pattern you should look at.

Other Resources

How to make a Makefile?

Most software compiled on BLU (BSD/Linux/Unix) operating systems is done using make.

The simplest Makefile

The simplest Makefile compiles one single executable. Think of your simplest “Hello, World!” project.

HelloWorld.cpp

#include <iostream>
using namespace std;
int main() {
  cout << "Hello, World!";
  return(0);
}

Of course, for one file you don’t need a Makefile. You could simply run this command that will compile hw.cpp

g++ -o HelloWorld HelloWorld.cpp

So even though a Makefile seems useless for a single file, here is how you would do it.

all:
	g++ -o HelloWorld HelloWorld.cpp

Notice that you have a label and the same compile command one line below the label.

Important! The syntax requires the second line to start with a tab.

Adding objects to your Makefile

Lets assume instead of one file, you have the three file HelloWord.

  • Main.cpp
  • HelloWorld.h
  • HelloWord.cpp

Main.cpp

#include <iostream>
#include "HelloWorld.h"

using namespace std;

int main()
{
  HelloWorld hw = HelloWorld();
  cout << hw.Text << endl;
}

HelloWorld.h

#include <iostream>

using namespace std;

class HelloWorld
{
public:
  HelloWorld();
  ~HelloWorld();

  string Text;
};

HelloWorld.cpp

#include "HelloWorld.h"

HelloWorld::HelloWorld()
{
  Text = string("Hello, World!");
}

HelloWorld::~HelloWorld()
{
}

This simple project can also easily be compiled without a Makefile using this command line.

g++ -o HelloWorld Main.cpp HelloWorld.cpp

However, even with only three files you can start to see how it is much easier to type make than the lengthening command above.

Makefile

all:
	g++ -o HelloWorld Main.cpp HelloWorld.cpp

This is not perfect however, as this compiles both files every time make is run. If changes are made only to Main.cpp there is no reason to recompile HelloWorld.cpp. We can accomplish this by compiling HelloWorld.cpp to a HelloWorld.o module.

all: HelloWorld.o
	g++ -o HelloWorld Main.cpp HelloWorld.o

Similarly if you make changes to HelloWorld.h or HelloWorld.cpp, why do you need to recompile Main.cpp? So you can make it a module too.

all: Main.o HelloWorld.o
	g++ -o HelloWorld Main.o HelloWorld.o

Now only the libraries that have been modified will be recompiled when you run make. This can save significant build time when the project size increases.

Using variables in your Makefile

Mistakes are annoying.  Having to type the same thing in multiple places often leads to mistakes and typos. If you look at the above, there is duplication that is unnecessary.

Makefile with duplication

all: Main.o HelloWorld.o
	g++ -o HelloWorld Main.o HelloWorld.o

Makefile using a variable to avoid duplication

objs = Main.o HelloWorld.o
all: ${objs}
	g++ -o HelloWorld ${objs}

We can even add more variables which may not seem useful now, but are useful later.

CXX = g++
CXXFLAGS =
objs = Main.o HelloWorld.o
Outfile = HelloWorld

all: ${objs}
	${CXX} ${CXXFLAGS} -o ${Outfile} ${objs}

Think about it. Right now you only have one build command, but someday on a huge project you may have dozens and possibly hundreds. Could you imaging changing the CXXFLAGS everywhere? We don’t even have one listed yet, but of course, with the variable you only have to change it once in one place and it will work everywhere you used it.

Adding make clean to your Makefile

It is very common to want to delete all build files and build again. This is often done with the make clean command. But to get make clean to work you have to create a section or label in the make file called clean.

Because we already have variables, it is easy to configure the Makefile to support make clean.

Makefile with clean

CC = g++
CXXFLAGS = -W
objs = Main.o HelloWorld.o
Outfile = HelloWorld

all: ${objs}
	${CC} ${CXXFLAGS} -o ${Outfile} ${objs}

clean:
	rm ${objs} ${outfile}

So simple, we just use rm to delete the files we created, which are all in variables so we had a nice clean short command.

Adding debugging to your make file

There are two schools of thought for debugging.

  • All builds should be release builds unless you run make debug.
  • All builds should be debug builds unless you run make release.

I am not going to tell you which school of thought you should have.  What matters is that you can configure the Makefile to perform how you want it to.

This make file will always build without debugging (release) unless yous specify make debug.

CXX = g++
CXXFlags = -W
objs = Main.o HelloWorld.o
Outfile = HelloWorld

all: objects build

objects: ${objs}

debug: clean
CXXFLAGS += -g
LDFLAGS += -g

debug: objects build

build:
	${CXX} ${CXXFLAGS} -o ${Outfile} ${objs}

clean:
	rm -f ${objs} ${Outfile}

Notice we set LDFLAGS but we never actually call it. It is a special variable that is called automatically by the linker when creating the objects. Yes it must be capitalized.

How to create an Android menu?

Ok, so adding a menu that pops up from the bottom when the menu button is clicked is very common and quite easy to do.

Note: This assumes you have the Android SDK, Emulator, and Eclipse all working already.

Step 1 – Create your Android project

  1. In Eclipse, select File | New Project | Android | Android Project.
  2. Give your project a Name.
    I named this project “HelloAll”.
  3. Select the Build Target (the minimum version of Android).
    I selected Android 2.2.
  4. Enter a Package name.
    Package name is like a namespace, it can be anything you want, but you should actually choose a name as carefully as you choose and the name of an object.  I named the package this: org.rhyous.
  5. Click Finish.

Your project is now created.

Step 2 – Add an XML file for the menu

  1. Expand the res directory in your project.
  2. Right-click on the layout folder and choose New | Other.
  3. Choose XML | XML file and click Next.
  4. Name the file.
    I named my file menu.xml.
  5. Click Finish.
  6. Add the following text into your menu:
    <menu xmlns:android="http://schemas.android.com/apk/res/android">
        id="@+id/menu_item_1" android:title="@string/menu_1"/>
        id="@+id/menu_item_2" android:title="@string/menu_2"/>
        <item android:id="@+id/menu_item_3" android:title="@string/menu_3"/>
    </menu>
    

Step 3 – Add the strings for the menu items

  1. Expand the res\values directory in your project.
  2. Open the strings.xml.
  3. Add strings for each menu item.
    Make sure you use the same id strings you used in the menu.xml for the title of each menu item.
    Your strings.xml should now look like this:

    <?xml version="1.0" encoding="utf-8"?>
    <resources>
        <string name="hello">Hello World, HelloAllActivity!</string>
        <string name="app_name">HelloAll</string>
        <string name="menu_1">Menu 1</string>
        <string name="menu_2">Menu 2</string>
        <string name="menu_3">Menu 3</string>
    </resources>
    

You now have a menu and strings for each menu item.

Step 4 – Overload onCreateOptionsMenu

  1. Open your Activity.
    Mine is src\org.rhyous\HelloAllActivity.java.
    It should look like this:

    package org.rhyous;
    
    import android.app.Activity;
    import android.os.Bundle;
    
    public class HelloAllActivity extends Activity {
    	/** Called when the activity is first created. */
    	@Override
    	public void onCreate(Bundle inSavedInstanceState) {
    		super.onCreate(inSavedInstanceState);
    		setContentView(R.layout.main);
    	}
    }
    
  2. Add code to override onCreateOptionsMenu and add code to inflate the menu.
    	@Override
    	public boolean onCreateOptionsMenu(Menu inMenu) {
    		super.onCreateOptionsMenu(inMenu);
    		getMenuInflater().inflate(R.layout.menu, inMenu);
    		return true;
    	}
    

You can now build your application and test that the menu pops up. However, the menu doesn’t do anything yet.

Step 5 – Overload onCreateOptionsMenu

  1. Add code to override onOptionsItemSelected and add code to inflate the menu.
  2. Use a switch statement with the inItem.getItemId() function to perform the appropriate action for each menu item.
    	@Override
    	public boolean onOptionsItemSelected(MenuItem inItem) {
    		switch (inItem.getItemId()) {
    		case R.id.menu_item_1:
    			// Do something here
    			return true;
    		case R.id.menu_item_2:
    			// Do something here
    			return true;
    		default:
    			// Should never get here
    			return false;
    		}
    

Based on the item clicked, the appropriate code will run.

Hope you enjoyed this simple Android development example.

Ghost 2.5 Beta 2 available – Ghost is a BSD distribution based on GNOME

Ghost 2.5 is a BSD desktop distribution based on FreeBSD. This version is keeping up with the latest FreeBSD 9 release. This is both a live distribution as well as an installer for FreeBSD 9.

It is exciting for a lot of BSD users who didn’t really have an out-of-the-box GNOME option on FreeBSD to have a distribution where GNOME is the focus.

The DVD ISO in 64 bit is only 1.3 GB, though there is a “lite” version that is on a single CD.

It is nice that they are using pcsysintall for their installer, though they are in early stages as the installer is a text installer and not for an Ubuntu user yet. 😉

If you are excited about this project go ahead and give them a donation. I just tossed them $5. http://ghostbsd.org/donate/

Prime Factors calculator in C++

Hey all, I wrote a C++ object that gets the prime factors of any number and thought I would share it.

The comments should help you and the variables have very clear names, so it should be self-documenting.

PrimeFactorsOfCalculator.h

#pragma once

#include <vector>

using namespace std;

class PrimeFactorsOfCalculator
{
public:
	PrimeFactorsOfCalculator(void);
	~PrimeFactorsOfCalculator(void);

	long GetNumber();
	void SetNumber(long inNumber);
	vector<int> GetPrimeFactors(bool inAllowDuplicates = false, bool inForceRecalculate = false);


private:
	long Number;
	vector<int> PrimeFactors;
	bool IsPrime(long inNumber);

	long MultiplyPrimes();

};

PrimeFactorsOfCalculator.cpp

#include "PrimeFactorsOfCalculator.h"
#include <math.h>
#include <algorithm>

using namespace std;

PrimeFactorsOfCalculator::PrimeFactorsOfCalculator(void)
{
}


PrimeFactorsOfCalculator::~PrimeFactorsOfCalculator(void)
{
}

long PrimeFactorsOfCalculator::GetNumber()
{
	return Number;
}

void PrimeFactorsOfCalculator::SetNumber(long inNumber)
{
	Number = inNumber;
	PrimeFactors.clear();
}

//
// Gets the prime factors of Number. 100 return 2,5.
//	
// inAllowDuplicates - Allow duplicates, for example, 100 has prime 
// factors of 2 and 5,but in order to get 100, you need 2*2*5*5. So 
// instead of returning 2,5 the return array will be 2,2,5,5.
//
// inForceRecalculate - By default the values are stored at first
// calculation and only recalcuated when needed. this is for efficiency.
vector<int> PrimeFactorsOfCalculator::GetPrimeFactors(bool inAllowDuplicates, bool inForceRecalculate)
{
	// Don't recalculate if already calculated.
	if (PrimeFactors.size() > 0 && !inForceRecalculate)
		return PrimeFactors;

	PrimeFactors.clear();
	// Calculate
	if (Number % 2 == 0 && Number >= 2)
	{
		PrimeFactors.push_back(2);
	} 

	for (int i = 3; i < Number/3; i++)
	{
		if (Number % i == 0 && IsPrime(i))
			PrimeFactors.push_back(i);
	}

	// Allow duplicates, for example, 100 has prime factors of 2 and 5,
	// but in order to get 100, you need 2*2*5*5. So instead of returning
	// 2,5 the return array will be 2,2,5,5.
	if (inAllowDuplicates)
	{
		while (MultiplyPrimes() != Number)
		{
			long multipliedVal = MultiplyPrimes();
			long val = 0;

			if (multipliedVal != 0)
				val = Number / multipliedVal;

			if (IsPrime(val))
			{
				PrimeFactors.push_back(val);
				continue;
			}
			else
			{
				// recursion
				PrimeFactorsOfCalculator calc = PrimeFactorsOfCalculator();
				calc.SetNumber(val);
				vector<int> duplicateFactors = calc.GetPrimeFactors();
				for (size_t i = 0; i < duplicateFactors.size(); i++)
				{
					PrimeFactors.push_back(duplicateFactors.at(i));
				}
			}
		}
	}

	sort(PrimeFactors.begin(), PrimeFactors.end());
	return PrimeFactors;
}

bool PrimeFactorsOfCalculator::IsPrime(long inNumber)
{
	// Get square root as that is the highest possible factor
	// and add one in case precision is screwy.
	long highestPossibleFactor = (long)(sqrt((double)inNumber) + 1);

	// Handle 2 separatly then no other even has to be checked
	if (inNumber % 2 == 0) 
		return false;

	// See if the value is divisible by any odd number
	// if so it is not prime
	for (int i = 3; i < highestPossibleFactor; i+=2)
	{
		if (inNumber % i == 0) 
			return false;
	}
	return true;
}

long PrimeFactorsOfCalculator::MultiplyPrimes()
{
	if (PrimeFactors.size() == 1)
		return PrimeFactors.at(0);
	else if (PrimeFactors.size() > 1)
	{
		int minVal = PrimeFactors.at(0);
		for (size_t i = 1; i < PrimeFactors.size(); i++)
		{
			minVal *= PrimeFactors.at(i);
		}
		return minVal;
	}
	else return 1; // 1 is always a prime
}

And last here is a sample main function that uses this.

Main.cpp

#include <vector>
#include "PrimeFactorsOfCalculator.h"

using namespace std;

int main()
{
	PrimeFactorsOfCalculator calc = PrimeFactorsOfCalculator();
	calc.SetNumber(100);
	vector<int> primeFactors = calc.GetPrimeFactors();
	vector<int> primeFactorsWithDuplicates = calc.GetPrimeFactors(true, true);


	calc.SetNumber(200);
	primeFactors = calc.GetPrimeFactors();
	primeFactorsWithDuplicates = calc.GetPrimeFactors(true, true);


	calc.SetNumber(1000);
	primeFactors = calc.GetPrimeFactors();
	primeFactorsWithDuplicates = calc.GetPrimeFactors(true, true);

	calc.SetNumber(14593);
	primeFactors = calc.GetPrimeFactors();
	primeFactorsWithDuplicates = calc.GetPrimeFactors(true, true);

	calc.SetNumber(12345678);
	primeFactors = calc.GetPrimeFactors();
	primeFactorsWithDuplicates = calc.GetPrimeFactors(true, true);
}

What is a Unit Test?

Unit Testing is the idea of writing additional code, called test code, for the purpose of testing the smallest blocks of production code to the full extent possible to make sure those blocks of code are error free.

Code is usually designed into Classes or Objects. The term “Class” and the term “Object” are usually used interchangeably. Classes are made up of variables and functions that include Constructors, Methods, and Properties but they may also include sub-classes.

For each Object in code, you should have a Unit Test for that object. For each method in an Object, the correlating Unit Test should have a test. In fact, a test should exist that makes sure that every line of your code functions as expected.

Code Coverage

Unit Tests are about making sure each line of code functions properly. A Unit Test will execute lines of codes. Imagine you have 100 lines of code and a Unit Test tests only 50 lines of code. You only have 50% code coverage. The other 50% of you code is untested.

Most Unit Test tools, MSTest, MBUnit, NUnit, and others can provide reports on code coverage.

Cyclomatic Complexity

Cyclomatic Complexity is a measurement of how complex your code is. This usually comes up in Unit Testing because in order to get 100% code coverage, one has to tests every possible path of code. The more your code branches, the more complex the code is.

If you have to write twenty tests just to get 100% coverage for a single function, you can bet your cyclomatic complexity is too high and you should probably break the function up or reconsider the design.

Parameter Value Coverage

Parameter Value Coverage is the idea of checking both expected and unexpected values for a given type. Often bugs occur because testing is not done on an a type that occurs unexpectedly at run time. Often a value is unexpectedly null and null was not handled, causing the infamous null reference exception.

Look at this function. Can you see the bug?

public bool CompareStrings(String inStr1, String inStr2)
{
    return inStr1.Equals(inStr2);
}

A System.NullReferenceExecption will occur if inStr1 is null.

How can we find these bugs before a customer reports them? A unit test can catch these bugs. We can make lists of anything we can think of that might react differently.

For example, imagine a function that takes a string. What should we try to test:

  1. An actual string: “SomeText”;
  2. An uninitialized string: null;
  3. A blank string: “”
  4. A string with only whitespace: ”   “;

Now imaging a function takes an object called PersonName that has a string member for FirstName and LastName value. We should try to test some of the above.

  1. A PersonObject but nothing populated: new PersonName();
  2. A PersonObject but everything populated: new PersonName() {FirstName=”John”, LastName=”Johnson”};
  3. A PersonObject but partially populated: new PersonName() {LastName=”Johnson”} || new PersonName() {FirstName=”John”};
  4. An uninitialized PersonName object: null;

Here is a test that will check for null in the compare strings code.

Note: There is a decision to make here. If comparing two string objects and both are null, do you want to return true, because both are null so they match? Or do you want to return false, because neither are even strings? For the code below, I’ll assume two null strings should not be considered equal.

public bool CompareStrings_Test()
{
    String test1 = null;
    String test2 = null;
    bool expected = false;
    bool actual = CompareStrings(test1, test2);
    Assert.AreEqual(expected, actual);
}

Now your unit test is going to encounter a System.NullReferenceExecption. Assuming you write Unit Tests before you release your code to a customer, you will catch the bug long before the code reaches a customer and fix it.

Here is the fixed function.

public bool CompareStrings(String inStr1, String inStr2)
{
    // If either input values are null, return false
    if (null == inStr1 || null == inStr2)
        return false;
    return inStr1.Equals(inStr2);
}

Unit Test Example

Here is an example object called PersonName. We tried to make it have a little more meat to this object than just a FirstName, LastName password.

PersonName.cs

using System;
using System.Collections.Generic;
using System.Text;

namespace PersonExample
{
    ///<summary>
    /// An Ojbect representing a Person
    /// </summary>
    public class PersonName : IPersonName
    {
        #region Constructor
        public PersonName()
        {
        }
        #endregion

        #region Properties
        /// <summary>
        /// The persons first name.
        /// </summary>
        public String FirstName { get; set; }

        /// <summary>
        /// The persons Middle Name(s). Some people have multiple middle names.
        /// So as many middle names as desired can be added.
        /// </summary>
        public List MiddleNames
        {
            get
            {
                if (null == _MiddleNames)

                    _MiddleNames = new List();
                return _MiddleNames;
            }
            set { _MiddleNames = value; }
        } private List _MiddleNames;

        public String LastName { get; set; }
        #endregion

        #region Methods
        /// <summary>
        /// Converts the name to a string.
        /// </summary>
        public override string ToString()
        {
            return ToString(NameOrder.LastNameCommaFirstName);
        }

        ///<summary>
        /// Converts the name to a string.
        /// </summary>
        ///
        ///
        private String ToString(NameOrder inOrder)
        {
            switch (inOrder)
            {
                case NameOrder.LastNameCommaFirstName:
                    return LastName + ", " + FirstName;

                case NameOrder.LastNameCommaFirstNameWithMiddleNames:
                    return LastName + ", " + FirstName + " " + MiddleNamesToString();

                case NameOrder.FirstNameSpaceLastname:
                    return FirstName + " " + LastName;

                case NameOrder.FirstNameMiddleNamesLastname:
                    return FirstName + MiddleNamesToString() + LastName;

                default:
                    return LastName + ", " + FirstName;
            }
        }

        /// <summary>
        /// Converts the list of middle names to a single string.
        /// </summary>
        /// String
        private String MiddleNamesToString()
        {
            StringBuilder builder = new StringBuilder();

            bool firstTimeThrough = true;
            foreach (var name in MiddleNames)
            {
                if (firstTimeThrough)
                    firstTimeThrough = false;
                else
                    builder.Append(" ");
                builder.Append(name);
            }
            return builder.ToString();
        }

        /// <summary>
        /// Compares the object passed in to see if it is a Person.
        /// </summary>
        ///
        /// True if FirstName and LastName and MiddleNames match, False if the object
        /// is not a Person or FirstName and LastName and MiddleNames do not match
        public override bool Equals(object inObject)
        {
            PersonName p = inObject as PersonName;
            if (null == p)
                return false;
            else
                return Equals(p);
        }

        /// <summary>
        /// Compares one PersonName to another PersonName.
        /// </summary>
        public bool Equals(IPersonName inPersonName)
        {
            return inPersonName.FirstName.Equals(FirstName, StringComparison.CurrentCultureIgnoreCase)
                && inPersonName.LastName.Equals(LastName, StringComparison.CurrentCultureIgnoreCase);
        }

        /// <summary>
        /// Compares a string to see if it matches a person.
        /// </summary>
        public bool Equals(String inString)
        {
            string tmpLastNameCommaFirstName = ToString(NameOrder.LastNameCommaFirstName);
            string tmpLastNameCommaFirstNameWithMiddleNames = ToString(NameOrder.LastNameCommaFirstNameWithMiddleNames);
            string tmpFirstNameSpaceLastname = ToString(NameOrder.FirstNameSpaceLastname);
            string FirstNameMiddleNamesLastname = ToString(NameOrder.FirstNameMiddleNamesLastname);

            return tmpLastNameCommaFirstName.Equals(inString, StringComparison.CurrentCultureIgnoreCase)
                || tmpLastNameCommaFirstNameWithMiddleNames.Equals(inString, StringComparison.CurrentCultureIgnoreCase)
                || tmpFirstNameSpaceLastname.Equals(inString, StringComparison.CurrentCultureIgnoreCase)
                || FirstNameMiddleNamesLastname.Equals(inString, StringComparison.CurrentCultureIgnoreCase);
        }

        ///
        public override int GetHashCode()
        {
            return base.GetHashCode();
        }
        #endregion

        #region Enums
        /// <summary>
        /// The order of the names when converted to a string.
        /// </summary>
        public enum NameOrder
        {
            LastNameCommaFirstName = 0,
            LastNameCommaFirstNameWithMiddleNames,
            FirstNameSpaceLastname,
            FirstNameMiddleNamesLastname
        }
        #endregion
    }
}

Ok, so in a separate test project, the following corresponding test class can be created.

PersonNameTest.cs

using Microsoft.VisualStudio.TestTools.UnitTesting;
using PersonExample;

namespace PersonExample_Test
{
    /// <summary>
    ///This is a test class for PersonNameTest and is intended
    ///to contain all PersonNameTest Unit Tests
    ///</summary>
    [TestClass()]
    public class PersonNameTest
    {
        #region PersonName()
        /// <summary>
        ///A test for PersonName Constructor
        ///</summary>
        [TestMethod()]
        public void PersonName_ConstructorTest()
        {
            PersonName person = new PersonName();
            Assert.IsNotNull(person);
            Assert.IsInstanceOfType(person, typeof(PersonName));
            Assert.IsNull(person.FirstName);
            Assert.IsNull(person.LastName);
            Assert.IsNotNull(person.MiddleNames);
        }
        #endregion

        #region Equals(Object inObject)
        /// <summary>
        ///A test for Equals(Object inObject) with matching first and last names
        ///</summary>
        [TestMethod()]
        public void Equals_Obj_Test_Matching_First_Last_Names()
        {
            PersonName target = new PersonName() { FirstName = "John", LastName = "Johnson" };
            object inObject = new PersonName() { FirstName = "John", LastName = "Johnson" };
            bool expected = true;
            bool actual = target.Equals(inObject);
            Assert.AreEqual(expected, actual);
        }

        /// <summary>
        ///A test for Equals(Object inObject) with different last name
        ///</summary>
        [TestMethod()]
        public void Equals_Obj_Test_Matching_Different_Last_Names()
        {
            PersonName target = new PersonName() { FirstName = "John", LastName = "Johnson" };
            object inObject = new PersonName() { FirstName = "John", LastName = "Jameson" };
            bool expected = false;
            bool actual = target.Equals(inObject);
            Assert.AreEqual(expected, actual);
        }

        /// <summary>
        ///A test for Equals(Object inObject) with different first name
        ///</summary>
        [TestMethod()]
        public void Equals_Obj_Test_Matching_Different_First_Names()
        {
            PersonName target = new PersonName() { FirstName = "John", LastName = "Johnson" };
            object inObject = new PersonName() { FirstName = "James", LastName = "Johnson" };
            bool expected = false;
            bool actual = target.Equals(inObject);
            Assert.AreEqual(expected, actual);
        }

        /// <summary>
        ///A test for Equals(Object inObject) when a null is passed in.
        ///</summary>
        [TestMethod()]
        public void Equals_Obj_Test_Null()
        {
            PersonName target = new PersonName();
            object inObject = null;
            bool expected = false;
            bool actual;
            actual = target.Equals(inObject);
            Assert.AreEqual(expected, actual);
        }
        #endregion

        #region Equals(String inString)
        /// <summary>
        ///A test for Equals(String inString) where inString is null
        ///</summary>
        [TestMethod()]
        public void Equals_String_Test_null()
        {
            PersonName target = new PersonName() { FirstName = "Tom", LastName = "Tomison" };
            string inString = null;
            bool expected = false;
            bool actual;
            actual = target.Equals(inString);
            Assert.AreEqual(expected, actual);
        }

        /// <summary>
        ///A test for Equals(String inString) where inString is a match using
        ///PersonName.NameOrder.FirstNameSpaceLastname
        ///</summary>
        [TestMethod()]
        public void Equals_String_Test_FirstNameSpaceLastname_Match()
        {
            PersonName target = new PersonName() { FirstName = "Tom", LastName = "Tomison" };
            string inString = "Tom Tomison";
            bool expected = true;
            bool actual;
            actual = target.Equals(inString);
            Assert.AreEqual(expected, actual);
        }

        /// <summary>
        ///A test for Equals(String inString) where inString is a match using
        ///PersonName.NameOrder.LastNameCommaFirstName
        ///</summary>
        [TestMethod()]
        public void Equals_String_Test_LastNameCommaFirstName_Match()
        {
            PersonName target = new PersonName() { FirstName = "Tom", LastName = "Tomison" };
            string inString = "Tomison, Tom";
            bool expected = true;
            bool actual;
            actual = target.Equals(inString);
            Assert.AreEqual(expected, actual);
        }
        #endregion

        // TODO: Finish testing this object

    }
}

For more learning, answer the following questions:

  1. What functions are Unit Tested?
  2. What is the code coverage of this Unit Test? (What percent of the Code is Unit Tested?)
  3. You have an enum with twenty items in it. One function has a switch on the enum with all twenty possibilities. The cyclomatic complexity appears to be high and is causing a red flag? Should you change your code? Why or Why not?
  4. Assume you finish the unit test so that the code is 100% covered. What reasons exist for needing still more tests on that code?

Return to C# Unit Test Tutorial