Code sample test

This is a test putting some code sample as a blog entry.

 

factorial.h

 

// These are ‘public’

int

factorial_iterative(__in unsigned __int32 input, __out unsigned __int32 &output);

int

factorial_recursive(__in unsigned int input, __out unsigned int &output);

int

factorial_lookup_table(__in unsigned int input, __out unsigned int &output);

// There are ‘private’, i.e. not for general use.

int

factorial_recursive_internal(__in unsigned int input, __out unsigned int &output);

int

factorial_unit_test();

 

// Samples library.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include

"factorial.h"

// As we don’t have ATL to re-use their error code (no ATL in the standard V C++ 2k5 express),

// we have to define our own error code.

// As a standard from main(…) 0 is success code

// 1 is arithmetic overflow

// 2 is unspecified error. Great for test code and request dev to take a look, but terrible in release code.

// When does int overflows?

// An unsigned integer with n bits can encode up to the number (2^n) -1.

// Assuming 32 bits per unsigned int32

// Google tells us logarithm base 2 of 12! with 28 bits consumption fits, but 13! with slightly over 32 won’t.

int factorial_iterative(__in unsigned __int32 input, __out unsigned __int32 &output)

{

int iResult = 0;

output = 1;

// for better predictability output is initialized even if we stop on overflow

if (input >= 13)

{

iResult = 1;

}

else

{

// Note that input of zero will skip this loop

// and cause the function to properly keep output at 1.

for (; input > 1; input–)

{

output *= input;

}

}

return iResult;

}

// Caller should take in consideration this recursion will eat some stack – up to 12 recursion.

// The quick arithmetic overflow limits this drastically.

int

factorial_recursive(__in unsigned int input, __out unsigned int &output)

{

int iResult = 0;

if (input >= 13)

{

output = 1;

iResult = 1;

}

else

{

iResult = factorial_recursive_internal(input, output);

}

return iResult;

}

// With preFAST we could add a range definition on input to limit it to 0..12

int factorial_recursive_internal(__in unsigned int input, __out unsigned int &output)

{

int iResult = 0;

if (input > 1)

{

iResult = factorial_recursive_internal(input – 1, output);

output = output * input;

}

else

{

output = 1;

}

return iResult;

}

// Now as 12 is so few values… Why not compute them in advance?

int

factorial_lookup_table(__in unsigned int input, __out unsigned int &output)

{

int iResult = 0;

if (input >= 13)

{

output = 1;

iResult = 1;

}

else

{

unsigned int lookup_table[13] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600};

output = lookup_table[input];

}

return iResult;

}

int

factorial_unit_test()

{

// A the set of input values accepted by our factorial functions is limited,

// we can afford an almost exhaustive testing.

int iResult = 0;

for (unsigned __int32 i = 0; iResult == 0 && i < 1000; i++)

{

int iResult_iterative, iResult_recursive, iResult_lookup = 0;

unsigned __int32 output_iterative, output_recursive, output_lookup = 0;

iResult_iterative = factorial_iterative(i, output_iterative);

iResult_recursive = factorial_recursive(i, output_recursive);

iResult_lookup = factorial_lookup_table(i, output_lookup);

if ((iResult_iterative != iResult_recursive) || (iResult_recursive != iResult_lookup))

{

printf(

"Return value mistmatch for i=%x\n", i);

iResult = 2;

}

if ((output_iterative != output_recursive) || (output_recursive != output_lookup))

{

printf(

"Output value mistmatch for i=%x\n", i);

iResult = 2;

}

}

if (iResult == 0)

{

printf(

"All unit tests for factorial completed with success.\n");

}

return iResult;

}

int

_tmain(int argc, _TCHAR* argv[])

{

int iResult = 0;

// Eat the return value, we’ll look at the text output.

factorial_unit_test();

return iResult;

}

This entry was posted in Computers and Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s