Chris Miceli

Implementing Generators/Yield in Languages Without Support

2011-11-20T16:43:00.001-06:00

As a follow up to my previous post, I intent to go into detail how generators are actually implemented in a language. The way I intend to do this is to actually implement the generator paradigm without using language provided tools such as keywords. The first step to this process is actually understanding what is happening when you use the yield keyword. Perhaps an simple walk through will be illustrative.

A function that wishes to use a generator will iterate over that generator. To the function using the generator, the generator acts more like a data structure that implements the enumerable (iterable) interface than a function at all. The generator function cannot be called except by iterating over it. This is the proper way to think of a generator, a data structure. If you are only using a generator, than this is all you need to know. Implementing a generator requires a little more detail. Let's examine a the most basic generator, one that counts down. This example uses, C#, but the syntax is only slightly different than other languages such as python.

public IEnumerable<int> count(int start, int end)
{
   int counter = end;
   while (counter <= end)
   {
      yield return counter;
      counter++;
   }
}

I used a while loop here intentionally so the control flow is obvious. Up until the yield statement, everything is normal. So what is happening at "yield return counter"? The function execution stops and returns the variable counter for each "call" happening indirectly through the iterator. So what happens the next time the iterator issues a call to this function? Well, the execution picks up at counter++! But what is the value of counter? The special yield return statement is saving the entire state of the generator(local variables, instruction pointer, and any other state information), allowing the generator to be resumed exactly where it left off. I'll get to that other information later. To wrap up the basic, right before yielding a value, save the state of the generator. Upon entering the generator again, restore the saved state and jump to where we left off.

Let's examine another example. This time we will be looking at a recursive implementation of our count generator. I'm going to be intentionally avoiding the use of foreach to bring out the enumerator (iterator).

public IEnumerable<int> count(int start, int end)
{
   yield return start;
   if (start != end)
   {
      // foreach (int result in count(start + 1, end))
      // {
      //    yield return result;
      // }
      IEnumerator<int> enumerator = count(start + 1, end).GetEnumerator();
      while (false != enumerator.MoveNext())
      {
         yield return enumerator.Current;
      }
   }
}

This generator does the same thing, just in a recursive fashion. The first yield is exactly as the one previously examined. Things get slightly more difficult to keep track when the recursion begins, but the same exact process is followed. The enumerator is saved as part of the state of the count generator. When returning, the iterator is restored and so the generator continues as expected.

If C# allowed us to directly recur on the generator itself instead of iterating over the results as shown below:

public IEnumerable<int> count(int start, int end)
{
   yield return start;
   if (start != end)
   {
      // Will not compile
      yield return count(start + 1, end);
   }
}

then the state would have to include the call stack of the recursion produced by the generator. By explicitly restricting yield to return the enumerated base type (int), we are prevented from this operation because count returns an enumerable type. This makes implementing generators manually easier. We don't have to worry about recursion at all.

So now we get to implementing a generator. The basic ideas have been captured above. We need to save locals upon yielding, restore state upon calling, and allow enumeration. Since we generators are essentially data structures, we are going to have our desired operation (count) be a member function of a class that extends from a Generator class. Then your program can call foreach on this data type. Let's shown the Generator class first.

class Generator<T, State, RetType>

   : IEnumerable<RetType> where T : GeneratorIterator<State, RetType>, new()
{
   public Generator(State initialState)
   {
      this.initialState = initialState;
   }

   private State initialState;

   #region IEnumerable
   public IEnumerator<RetType> GetEnumerator()
   {
      GeneratorIterator<State, RetType> yieldedFunction = new T();
      yieldedFunction.Initialize(initialState);
      return yieldedFunction;
   }

   IEnumerator IEnumerable.GetEnumerator()
   {
      return this.GetEnumerator();
   }
   #endregion
}

public abstract class GeneratorIterator<State, RetType> : IEnumerator<RetType>
{
   public void Initialize(State initialState)
   {
      this.initialState = initialState;
      this.currentState = initialState;
   }

   public RetType YieldReturn(State state, RetType result)
   {
      // Save state before returning
      this.currentState = state;
      return result;
   }

   private State initialState;

   private State currentState;

   private RetType nextResult;

   public abstract RetType function(State currentState);

   #region IEnumerator
   public RetType Current
   {
      get
      {
         return this.nextResult;
      }
   }

   object IEnumerator.Current
   {
      get
      {
         return this.Current;
      }
   }

   public void Reset()
   {
      // Set the state back and invalid nextResult
      this.Initialize(this.initialState);
      this.nextResult = default(RetType);
   }

   public bool MoveNext()
   {
      this.nextResult = this.function(this.currentState);
      return this.currentState != null;
   }

   public void Dispose() { }
   #endregion
}

Let's examine what this class is doing. It is taking a class that is expected to override a member called function. This will be the function that is expected to be using the YieldReturn method provided by this class. Most of the code is setting up the enumerator. The enumerator takes care of calling the function when appropriate. The real magic that enables this class to be a generator is the currentState variable. This is where the function's state is saved. Whenever the function is needed, the function is passed the current state that was saved by YieldReturn. The function is responsible for using the state to produce the expected results.

To actually use the state, we are going to have functions that resemble finite state machines more than traditional functions. This is due to limitations of the C# compiler to allow us to jump to exactly where we need to. Below is a version of the first non recursive count and the appropriate state class representing all locals.

class Count : GeneratorIterator<CountState, int>
{
   public override int function(CountState currentState)
   {
      if (currentState.stateIndex == 0)
      {
         currentState.counter = currentState.start;
         currentState.stateIndex = 1;
         // Proceed to state 1
      }

      if (currentState.stateIndex == 1)
      {
         while (currentState.counter <= currentState.end)
         {
            // Set the next state
            currentState.stateIndex = 2;
            // yield return
            return YieldReturn(currentState, currentState.counter);
         }

         // Signal no more to yield, normally accomplished by reaching end of the function
         return YieldReturn(null, default(int));
      }

      if (currentState.stateIndex == 2)
      {
         currentState.counter = currentState.counter + 1;
         currentState.stateIndex = 1;
         // Use recursion to jump to state already passed
         return function(currentState);
      }
      
      // Can only get here if an invalid stateIndex was given
      throw new Exception("Unreachable");
   }
}

class CountState
{
   public int stateIndex;
   public int start;
   public int end;
   public int counter;
}

The stateIndex variable of the CountState class is used to determine where in the code path we left off. The function has no locals to avoid having variables no properly restored when upon reentry. To use this generator, we simply instantiate the wrapper and then the class behaves as all enumerator types do.

CountState initialState = new CountState
{
   start = 0,
   end = 5,
   stateIndex = 0
};

Generator<Count, CountState, int> generator = new Generator<Count, CountState, int>(initialState);
foreach (int result in generator)
{
   Console.WriteLine(result);
}

To illustrate that recursion is supported, I am translated the recursive count above to an appropriate finite state machine. You can try for yourself, but you can observe that there is no need to save a call stack to support recursion in your generators.

class RecursiveCount : GeneratorIterator<RecursiveCountState, int>
{
   public override int function(RecursiveCountState currentState)
   {
      if (currentState.stateIndex == 0)
      {
         currentState.stateIndex = 1;
         return YieldReturn(currentState, currentState.start);
      }

      if (currentState.stateIndex == 1)
      {
         if (currentState.start == currentState.end)
         {
            // We are done, signal no more results in this generator
            currentState.stateIndex = 3;
         }
         else
         {
            /// repeat
            currentState.recursiveCall = new Generator<RecursiveCount, RecursiveCountState, int>(
               new RecursiveCountState
                  {
                     start = currentState.start + 1,
                     end = currentState.end,
                     stateIndex = 0
                  }).GetEnumerator();
            // Go to state 2
            currentState.stateIndex = 2;
         }
      }

      if (currentState.stateIndex == 2)
      {
         while (false != currentState.recursiveCall.MoveNext())
         {
            return YieldReturn(currentState, currentState.recursiveCall.Current);
         }

         // We are done, signal no more results in this generator
         currentState.stateIndex = 3;
      }

      if (currentState.stateIndex == 3)
      {
         return YieldReturn(null, default(int));
      }

      throw new Exception("Unreachable");
   }
}

class RecursiveCountState
{
   public int stateIndex;
   public int start;
   public int end;
   public IEnumerator<int> recursiveCall;
}

I hope that this has been informative of the inner workings of generators and the yield statement. Please comment below with any questions.

Yield statement in C#

2011-11-04T00:38:00.000-05:00

My great friend recently did on his wonderful blog covered in a recent post the basics of generators in Python. To further my own knowledge about generators, especially in the language I use most at work, I decided to port his permutation function to C#, yield statement and all.

To basically reiterate what my friend stated, the yield statement allows a function's state to be saved. For functions that are designed to generate a set of data to be iterated over this is great. Instead of computing the entire list and storing the results in memory, the function is able to pick up where it left off and generate the next element of the set when requested. Here is an example with a function that generates permutations.


   private static IEnumerable<string> Permutations(string input)
   {
      List<string> result = new List<string>();
      if (string.IsNullOrEmpty(input))
      {
         yield return string.Empty;
      }
      else
      {
         for (int i = 0; i < input.Count(); i++)
         {
            foreach (string permutation in Permutations(input.Substring(0, i) + input.Substring(i + 1)))
            {   
               yield return input[i] + permutation;
            }
         }
      }
   }

If you iterate over this function, you will notice that the entire list is never generated entirely in memory. The syntax would be something along the lines of:


   foreach (string permutation in Permutations("vegetable"))
      {
         System.Console.WriteLine(permutation);
      }

Thanks to my friend for helping me understand this topic and bring attention to features of a language I use every day.

Time Lapse

2011-10-25T22:15:00.000-05:00

Recently, I set up my server with a copy of Yawcam on my home server. The initial plan was to experiment with using a webcam for security purposes, but found myself a little creeped out. I decided to turn the camera away from the door and out to the window. I set the software to take a picture every 10 seconds for a full day. You can see the results on Vimeo.

Formatting Lilypond Sheet Music for the Kindle

2011-10-23T20:30:00.000-05:00

Tired of fumbling around with my collection of sheet music looking for a certain piece, I thought it would be great to have some sheet music on my third generation kindle (now called the Kindle Keyboard). I have always been a fan of the open source program Lilypond. Lilypond is a TeX-like system where sheet music is written to a text file and then compiled into the desired output.
Since Lilypond is similar to Tex, Lilypond files have incredible control of the output. No exception is adjusting paper dimensions, only a simple command is required:

\paper {
   paper-height = H\mm
   paper-width = W\mm
}

where H is the desired height in millimeters and W is the desired width in millimeters of the output paper. Since the kindle was a "fit-to-width" option for PDFs, the first step is to figure out the aspect ratio of the display. Once we have the aspect ratio, then we can configure the scaling to make the actual output legible from a reasonable distance. At first I thought that this would be easy. The Kindle has a resolution of 600x800, or an aspect ratio of 3:4 (the screen is taller than it is wide). However, when creating sheet music of this ratio and the display mode of the Kindle set to "fit-to-width", the pages spanned multiple virtual pages. This meant that the music was cut off between virtual pages. This makes playing the music impossible. From here I decided to figure out the ratio by creating a bunch of files of varying ratios and testing the output.

It turns out that the Kindle is doing a little fudging on the display and allows a range of display ratios that will appear as one virtual page. From what I observe, any ratio between .57-.61. I tried many variations and it also seems there is some other logic going on in the "fit-to-width" option and determining when to page, but this is a decent rule of thumb to work with. Now that we have a few aspect ratios to work with, I wanted to figure out some nice paper size in absolute terms such that Lilypond will output notes about the same size as normal sheet music.

At first I tried 100mm x 59mm. As you can see, the notes were extremely large and didn't allow many notes to displayed at once. This would making paging an annoying operation while trying to play the music.

Next I doubled everything. I found 200mm x 122mm appears nice.

Compared to actual sheet music, the font is a little small, but completely usable. If you want a bigger font and don't mind paging frequently, I tried the in the between, 150mm x 80mm.

This is the closest to actual size, but fine tuning could be done.

It is worth noting that while doing this, the "fudge" factor I mentioned earlier, or variability in determining the aspect ratio of the virtual page the Kindle will chose to display, is frustrating. These values I found through trial and error by generating many sheet music files, and looking at all of them.

Custom HTML "Widgets" for ASP.NET MVC3

2011-10-16T17:38:00.000-05:00

I was experimenting with ASP.NET MVC3 and found myself in need of some HTML outputted by the Razor engine that would need to be used many times. I wanted to follow the DRY (Don't Repeat Yourself) principle by having the HTML appear in one spot and allow me to use it many times. Ideally I wanted something like the builtin HTML "widgets".


   @Html.DropDownList("DropDownID", Model.Items)

The way I accomplished this was extension methods. Extension methods are an interesting way to add functionality to a class without inheritence. There are drawbacks, such as not being able to access protected members of the base class, but for some cases this is ok.

I decided to use extension methods to add a method to the class that corresponded to the @Html object in the Razor engine. I found out that this class was the HtmlHelper class in the System.Web.Mvc namespace. By extending the HtmlHelper class via extension methods, I was able to achieve my goal of adding a custom widget.


namespace MvcHtml
{
   using System.Web.Mvc;

   public static class ExtensionHtml
   {
      public static MvcHtmlString CustomWidget(this HtmlHelper htmlHelper, string property)
      {
         TagBuilder tagBuilder = new TagBuilder("div");
         tagBuilder.SetInnerText(property);
         return new MvcHtmlString(tagBuilder.ToString());
      }
   }
}

After this little bit of work, we are ready to use the custom widget in our view template just as traditional widgets provided for us.


   @Html.CustomWidget("SampleProperty")

I hope this helps people understand how Razor is producing HTML from these view files!

Combining the Decorator Pattern with the Template Method Pattern

2011-10-05T00:33:00.000-05:00

Design patterns are exactly that, patterns of design. These patterns have been determined to appear frequently throughout software development. These patterns appear so often that they have become well documented and given names. I cannot recommend more highly the book Design Patterns by the "Gang of Four" as a resource on the topic of patterns.Recently I came across the need to combine to of the most common patterns, the decorator pattern and the template method pattern. I needed multiple implementation of a class to simultaneously coexist, the template method pattern, and I also needed to be able to decorate these classes, the decorator pattern. I noticed that while combining these two patterns, the decorator class behaves just as another class that implements the template method.

/* The template method */
interface AbstractClass
{
   void Method();
}

/* One implementation */
class ConcreteClass1 : AbstractClass
{
   public void Method()
   {
      System.Console.WriteLine("   ConcreteClass1");
   }
}

/* Second implementation */
class ConcreteClass2 : AbstractClass
{
   public void Method()
   {
      System.Console.WriteLine("   ConcreteClass2");
   }
}

/* Now comes the decorator, which feels just like any other implementation */
abstract class AbstractClassDecorator : AbstractClass
{
   public AbstractClassDecorator(AbstractClass abstractClass)
   {
      this.abstractClass = abstractClass;
   }

   public virtual void Method()
   {
      this.abstractClass.Method();
   }

   protected AbstractClass abstractClass;
}

Now it becomes time to implement the decorators. The nice thing about the decorator pattern is that it allows you to add decorators simply by extending a class. Here I have two decorators.

class ConcreteDecoratedAbstractClass1 : AbstractClassDecorator
{
   public ConcreteDecoratedAbstractClass1(AbstractClass abstractClass)
      : base(abstractClass)
   {
   }

   public override void Method()
   {
      this.abstractClass.Method();
      System.Console.WriteLine("   Decorator1");
   }
}

class ConcreteDecoratedAbstractClass2 : AbstractClassDecorator
{
   public ConcreteDecoratedAbstractClass2(AbstractClass abstractClass)
      : base(abstractClass)
   {
   }

   public override void Method()
   {
      this.abstractClass.Method();
      System.Console.WriteLine("   Decorator2");
   }
}

And now that the patterns are in place, all we have to do is simply use them. Because of the decoration and template pattern, we are able to create many possibilities to execute the "same" method. We can decorate or not decorate with any of the decorators, and we have multiple implementations of each method.

class Program
{
   static void Main(string[] args)
   {
      AbstractClass concrete1 = new ConcreteClass1();
      AbstractClass concrete2 = new ConcreteClass2();
      ConcreteDecoratedAbstractClass1 decorated1Concrete1 = new ConcreteDecoratedAbstractClass1(concrete1);
      ConcreteDecoratedAbstractClass1 decorated1Concrete2 = new ConcreteDecoratedAbstractClass1(concrete2);
      ConcreteDecoratedAbstractClass2 decorated2Concrete1 = new ConcreteDecoratedAbstractClass2(concrete1);
      ConcreteDecoratedAbstractClass2 decorated2Concrete2 = new ConcreteDecoratedAbstractClass2(concrete2);
      ConcreteDecoratedAbstractClass2 decorated21Concrete1 = new ConcreteDecoratedAbstractClass2(decorated1Concrete1);
      /* Et cetra */

      System.Console.WriteLine("Implementaiton 1");
      concrete1.Method();

      System.Console.WriteLine("Implementation 2");
      concrete2.Method();

      System.Console.WriteLine("Implementation 1 decorated by decorator 1");
      decorated1Concrete1.Method();

      System.Console.WriteLine("Implementation 2 decorated by decorator 1");
      decorated1Concrete2.Method();

      System.Console.WriteLine("Implementation 1 decorated by decorator 2");
      decorated2Concrete1.Method();

      System.Console.WriteLine("Implementation 2 decorated by decorator 2");
      decorated2Concrete2.Method();

      System.Console.WriteLine("Implementation 1 decorated by decorator 1 and decorator 2");
      decorated21Concrete1.Method();
}

This program outputs

Implementaiton 1
   ConcreteClass1
Implementation 2
   ConcreteClass2
Implementation 1 decorated by decorator 1
   ConcreteClass1
   Decorator1
Implementation 2 decorated by decorator 1
   ConcreteClass2
   Decorator1
Implementation 1 decorated by decorator 2
   ConcreteClass1
   Decorator2
Implementation 2 decorated by decorator 2
   ConcreteClass2
   Decorator2
Implementation 1 decorated by decorator 1 and decorator 2
   ConcreteClass1
   Decorator1
   Decorator2

I hope that this was informative in demonstrating the power of patterns and how they can be combined for even greater utility. Please feel free to comment below.

Scrobbler support in DAAP

2011-08-09T00:27:00.002-05:00

A popular feature request for DAAP has been Last.fm's Scrobbler support. Scrobbling is a mechanism that allows Last.fm to know what songs you listen to on your personal devices, such as iPods, computer, or your Android device. This allows Last.fm to personalize which songs to suggest more quickly than normal. Big thanks to my brother Michael for implementing this.

The feature is pretty straight forward. First, a Scrobbling application must be installed on your device. For this version, Scrobbling has been tested with scrobbledroid and A Simple Last.fm Scrobbler. Next, navigating to the preferences via Menu -> Preferences from the Servers screen presents an option to enable this feature. From now on, your music listening will be relayed to your Scrobbling application which in turn relays that to your Last.fm account! No interaction required.

You can download DAAP via the android market by

The Android Market Application
Scanning the tag

Don't forget about DAAP

2011-07-24T17:33:00.000-05:00

I recently updated some of the Android applications my brother and I have on the market. I left out by far the most popular application that we have. I have now fixed that. The DAAP application last night received a small but very useful bug fix. I expect more features to come out for the application in due time.

The bug fixed was a user experience (UX) design bug. Take the following scenario for instance: Select a song to play. Upon selection, the notification appears and you are free to continue using your phone for other purposes. Suppose that then you decided to return to the home screen or another application via repeatedly pressing the back button on the phone. You can use your phone, but if you returned to the DAAP application, you would have to re-login. If you clicked the notification, there was no way to return to the song selection screen. Essentially there was no way to return to pick a new song without re-logging in, a time consuming process.

The fix was easy. I added a new menu option on the media player (the screen viewed after clicking the notification) that allows you to return to the playlists. To prevent overloading of the menu options, I moved the shuffle and repeat buttons onto the screen. They are viewable at all times now. A screenshot below is included for demonstration purposes.

You can download DAAP via the android market by

The Android Market Application
Scanning the tag

Updates to mOTP and Utlimate Search Widget

2011-07-17T19:46:00.002-05:00

I have finally found some free time to fix things that have been bothering me in my Android applications. That means updates!

First, I have fixed a minor bug in the mOTP application affecting some users. The bug was a simple oversight when originally implementing profile editing. When editing TOTP profiles with a non-default time interval, the time interval would be listed as default. The fix was simple: pre-populate the spinner similar to how the other fields operate.

The second update was much more demanding. The Ultimate Search Widget application had no support for custom search providers. For instance, if I wanted to search my blog using the widget, I could not. I was restricted to a predefined list of search providers. Also, if I constantly switched between providers, I would have to scroll through the huge list of providers to find the search provider I wanted.

I solved the first problem by adding support for custom search providers. Simply fill in the name of the provider, the URL portion that appears before the query, the URL portion that appears after the query, and you are set.

Now this newly created search provider will appear in the list of providers when clicking the icon on the left hand side of the widget!

To fix the second problem, I added a preference type screen where you may click which providers are to appear in the list. This allows you to remove unused providers and make the widget more useful when frequently switching between search providers.

You can find both of the newly updated applications in The Android Market:

mOTP on The Android Market

Ultimate Search on The Android Market

Integrating Doxygen with Autotools

2011-01-16T23:34:00.000-06:00

For my thesis source code, I desired to have Doxygen documentation automatically generated by make. However, after searching the Internet, I was unable to find a decent tutorial. Luckily after reading the great book that I cannot recommend enough, A Practitioner's Guide to GNU Autoconf, Automake, and Libtool by John Calcote, I learned a great solution. I intend to outline that solution based off his book.

The first step is to decide how the process will work. In my case, I wrote documentation for a library that I plan for other developers to use. I want the documentation to be able to be viewed using the man utility. The documentation should be generated when the user runs 'make' and should be installed when the user runs 'make install'. If doxygen is not installed, output a warning message during configuration and do not generate any documentation.

The first step is to determine if the user has Doxygen installed. We can do this by searching for the Doxygen program using the Autoconf macro AC_CHECK_PROGS. If Doxygen is not found, output a warning message. We can put all of this logic in an m4 script or in-line in the configure.ac file. For this example, I will just put this in configure.ac:
AC_CHECK_PROGS([DOXYGEN], [doxygen])
if test -z "$DOXYGEN";
then AC_MSG_WARN([Doxygen not found - continuing without Doxygen support])
fi

Now in configure.ac, we can check to see if we have Doxygen and if so, add some files to later be processed.
AM_CONDITIONAL([HAVE_DOXYGEN],
[test -n "$DOXYGEN"])AM_COND_IF([HAVE_DOXYGEN], [AC_CONFIG_FILES([docs/Doxyfile])])

We see a mention to 'docs/Doxyfile' above. To any Autotools users, this should outline the next step, to write the 'Doxyfile.in' file. This is a file that will be transformed into 'Doxyfile', which will control how Doxygen generates the documentation. The reason we describe the configuration file in a way that configure modifies it is in case that we want certain properties of the documentation to be configurable. For example, we could add a configure option to optionally generate html documentation, --enable-html-doc for example.

In the subdirectory docs of the project, we can start by running:

doxygen -g Doxyfile.in

This generates a template configuration file for Doxygen that we can modify to get our final configuration file. We need to supply the project name, project version, and any other options determined by configure. Change the following properties as below:

PROJECT_NAME = @PACKAGE_NAME@
PROJECT_NUMBER = @PACKAGE_VERSION@
INPUT = @top_srcdir@

Be sure to change other options that you desire, such as HTML output, man output, etc.

Now that we have a configuration file ready to be parsed by configuration script, we need to tell Automake to generate makefiles that have rules to generate the actual documentation. In the docs subdirectory, we can create the 'Makefile.am' file that will be transformed by automake into 'Makefile'. Here is a what it looks like:

if HAVE_DOXYGEN
directory = $(top_srcdir)/docs/man/man3/

dist_man_MANS = $(directory)/man_page_1.3 $(directory)/man_page_2.3
$(directory)/man_page_1.3: doxyfile.stamp
$(directory)/man_page_2.3: doxyfile.stamp

doxyfile.stamp:
   $(DOXYGEN) Doxyfile
   echo Timestamp > doxyfile.stamp

CLEANFILES = doxyfile.stamp

all-local: doxyfile.stamp
clean-local:
   rm -rf $(top_srcdir)/docs/man
endif 

Now let's look at this carefully. The first thing that you should notice is that all the rules are only generated if configure set HAVE_DOXYGEN. We can see in the m4 code above that this is set is Doxygen is found.

Next we set up a convenience variable directory to save typing later on. Then we set the man pages that we wish to install when 'make install' is called. We set up a "Product List Variable" dist_man_MANS. This is a normal product list variable with a dist modifier. This means that we want to install these files when we run 'make install'. The man_ portion is the prefix, meaning we want to install these files in the $(mandir) directory. This is set by configure. The MANS portion of this product list is one of the primaries telling Autoconf which types of files are in this list.

We need make rules to build these man pages during the make stage. To do this, we make a rule for each man page to be installed, each one depending on a file called doxyfile.stamp. The reason we use one file is because of the one to many relationship between the one doxygen command and the many files generated. We need to be able to determine when we need to generate documentation, but which file do we check for. It doesn't make sense to pick one documentation file at random and check for its existence, so we use this solution.

The doxyfile.stamp target will generate the documentation by using the $DOXYGEN file determined by configure and the 'Doxyfile' generated from 'Doxyfile.in'. This target must also generate the doxyfile.stamp file also so future documentation file dependency checks are satisfied.

Now we need to tell Automake we want these built not at 'make install' time, but at 'make' time. To do this, we use a hook to the normal all target. By making the target all-local, we are making a target that will get executed before the normal all target. Now we are set. Make will install the man pages with the 'make install' command as we use the product list man_MANS with the dist prefix. We just need to handle cleaning up files on make clean. To do this, we add the 'doxyfile.stamp' file to the CLEANFILES list. This list is automatically cleaned when 'make clean' is run. To remove the directory of man pages is slightly different though. We can't easily remove a directory using the CLEANFILES variable. We simply hook into clean as we did with all and manually remove the directory.

Now we are set and ready to go. Please comment on improvements or errors in my guide.

Network Information

2010-12-01T11:41:00.001-06:00

Whenever you join a company's, campus's, or employer's wireless network, does it ever feel like it is missing something? For instance, when you go to a cafe and join their wireless, there is a disconnect between the companies offerings (coffee) and the service you just received (wireless connectivity). Earlier in the semester I thought of a system that would bridge this disconnect. The system would provide information about the network which was recently joined. The information could be anything, but should be tailored to the company providing the wireless. An example of this could be the cafe providing information of products, sales, contact information, or privacy information regarding the internet.

To accomplish this, there would be some server running (could be the router providing internet/wireless) that would store the information to be provided. The information could be stored in anyway, but for me I chose to use XML as there are many parsers available. Here is an example of such an XML file describing the network, and some upcoming events.

 <Network>  
   <name>University of New Orleans</name>  
   <link>http://www.uno.edu</link>  
   <policy>http://www.uno.edu/NonDiscrimination.asp</policy>  
   <Events>  
    <Event>  
      <title>Party at the library</title>  
      <description>Free food</description>  
      <eventLocation>Library</eventLocation>  
      <dtstart>1288515600000</dtstart>  
      <dtend>1288522800000</dtend>  
    </Event>  
    <Event>  
      <title>Campus Meeting</title>  
      <description>Talk with the governor</description>  
      <eventLocation>Administration building</eventLocation>  
      <dtstart>1293890400000</dtstart>  
      <dtend>1293901200000</dtend>  
    </Event>  
   </Events>  
 </Network>

This XML file describes a campus network that may wish to provide students and other network users of upcoming events, but the idea is clear that other types of information may be presented as described above.

For one of my classes, I decided to craft this idea into an Android project. The fun part about this is that I would use service discovery to automatically discover the server on the network providing the information. This is in contrast to perhaps a static network address or some DHCP information similar to DNS information.

I chose to use zeroconf technology for the service discovery as there was an easy to use java version of mDNS (a portion of zeroconf) that I used for DAAP that works nicely in this situation (well not so nicely, but it works). The idea is that the network server that is providing the information, also registers a service of a network-info service type and clients that join the network request services of the network-info service type that was registered. The server responds and provides the information, which the client displays.

I created an Avahi XML file describing the service so that it would be automatically broadcast on boot. Avahi is an open source implementation of zeroconf and provides utilities such as this to advertise services.

 <?xml version="1.0" standalone='no'?>  <!DOCTYPE service-group SYSTEM "avahi-service.dtd">  <service-group>    <name>UNO</name>    <service>     <type>_netfo._tcp</type>     <port>9090</port>    </service>  </service-group>

So now that the service is advertised and the information being provided is set up, we just need clients to connect.

Here are the screenshots of the implementation I wrote for my mobile computing class.

Screen presented after a server is discovered and information provided.

Screen presented when an even was clicked, providing more information.

This is great. Imagine all the possibilities of having information from your network. If there are any great ideas that could take advantage of this, feel free to comment with them! One idea that I came up with after beginning the project is an emergency channel. Take the university campus example for instance. Imagine that campus police spotted an armed individual and wanted to alert everyone in as many ways as possible. They can send mass emergency texts, emails, etc. Using the clients connected and listening to network information could be alerted also. I wrote this quickly for the android application as well.

Clients receive a notification upon emergency information becoming available.

Information presented when the emergency is clicked.

Ok, so maybe budget cuts aren't as scary as armed individuals, but they are scary!

Python's any and all in C++

2010-10-06T23:55:00.004-05:00

When working on some Project Euler problems with a friend, he used a handy little Python trick called all. Here is a typical use of all:


if all([x > 1 for key in some_list]):
   print 'True'

Simply put, if every element of some_list is greater than 1, then true is returned. Similarly, there is another function called any which returns true is any element in a list is true. I decided to test out my C++ skills and write this. Here is my attempt.


template<class InputIterator, class UnaryFunction>
   bool all(InputIterator first, InputIterator last, UnaryFunction f) {
   bool allTrue;
   for(allTrue = true; first != last; ++first) {
      if(f(*first) == false) {
         allTrue = false;
         break;
      }
   }
   return allTrue;
}
  
template<class InputIterator, class UnaryFunction>
   bool any(InputIterator first, InputIterator last, UnaryFunction f) {
   bool anyTrue;
   for(anyTrue = false; first != last; ++first) {
      if(f(*first) == true) {
         anyTrue = true;
         break;
      }
   }
   return anyTrue;
}

Now to use these functions, simply use it like any other STL function. Make a function or functor that takes the type of the list, and pass it to the any or all function.


struct apply {
   bool operator() (int x) {
      if(x > 1) {
         return true;
      }
      return false;
   } 
};

And now we just use it like you would expect.


int main() {  
   std::vector<int> integers;

   integers.push_back(0);
   integers.push_back(1);
   integers.push_back(2);
   integers.push_back(3);
   bool result = all(integers.begin(), integers.end(), apply());
   std::cout << "Result is: " << result << std::endl;
   result = any(integers.begin(), integers.end(), apply());
   std::cout << "Result is: " << result << std::endl;
   return 0;
 }

Please give me your comments on what you think.

Tire Pressure Monitoring Systems

2010-09-11T15:03:00.000-05:00

Recently there was a discussion in one of my classes where a student claimed that they read of an attack against the tire pressure monitoring system (TPMS) required in all United States automobiles. They claimed the attack could stop the car, accelerate the car, lock the breaks, or anything else conceivable. I was in disbelief so I did some research and made a presentation for our weekly Information Assurance Research meeting.

I found that the current attacks on TPMS are very limiting. The researchers were able to turn on and off the tire pressure and general information light, but only temporarily. Most experts agree that a more troubling matter exists with current TPMS implementations; they allow someone to track your car by listening to the wireless sensors in the tires themselves. I argue in my presentation, however, that tracking someone by this means would be more difficult than license plates, car color, car model, car year, car make, or toll tags.

The presentation also covers the researchers use of cheap hardware to decode the wireless signal. I found this aspect very interested. For those interested, here is the link: Tire Pressure Monitoring Systems (pdf)

Lesson from a Reference

2010-08-12T18:05:00.000-05:00

I learned a valuable lesson recently. When implemented TOTP on the OTP Android application, I used the Java reference implementation from the draft RFC document. The outputs matched and I assumed everything was fine. Last week, I was given a heads up through email that TOTP output values were not matching output values of other TOTP implementations. I assumed the other applications were wrong as I followed the true reference implementation.

I realized, however, that I was wrong. I was incorrectly using the source code by not verifying how the input was specified. The source attached to the document assumed that the ASCII seed had already been transformed into a hexadecimal string. For example, the seed in the reference implementation was "3132333435363738393031323334353637383930" which is the hexadecimal representation of the ASCII string "01234567890123456789". I thought that the long string was supposed to be entered by the user. If I would have though shortly about the ridiculous nature of that number, I may have realized my mistake.

I have released an update to the market correcting this error and a few other bugs. I fixed the activity stack to behave more in line with other Android applications (I didn't know much at the time of writing the older releases). I also cleaned up some interfaces to behave properly on different screen sizes.

Ultimate Search Widget for Android

2010-08-07T18:08:00.000-05:00

All major browsers have done it. By providing different search providers, a web browser user is quickly able to search their favorite search engine by selecting the search provider and then the desired query. The Google Search widget or Android is great, except it only searches Google. Frequently I find myself typing search queries with the following pattern: "* Wikipedia," "* IMDB," etc. to quickly bring up the desired page. My brother and I decided it would be great if there was a widget of a similar fashion to the way modern web browsers handle searching. Ultime Search Widget is the result of this labor.

Ultimate Search widget is an Android widget that installs directly on your home screen and bears a similar appearance to Google's Search widget.

There is a subtle difference however, the Google favicon to the right. As per modern web browsers, by selecting the favicon, the searcher is able to select which search provider they would like to carry out their search.

After selecting the search provider, the searcher is able to enter a query. All the features of the Google Search widget are provided, such as voice searching and suggestions.

The current providers:
* Amazon
* Answers
* Bing
* Creative Commons
* Dictionary
* eBay
* IMDB
* Google
* Google Images
* Merriam-Webster
* Wikipedia
* Yahoo!
* Youtube

Wherever applicable, the search results will be the mobile version of the search provider to improve response times of search queries. The Ultimate Search Widget is available on the Android market for a 99¢.

Check it out!

Silverlight Resources

2010-07-05T22:14:00.000-05:00

Recently T-Mobile USA put up a website T-Mobile Clue to tease the upcoming Samsung Vibrant cell phone. The website displayed a series of tiles covering an image. The tiles would slowly be removed and after four days, the image would be completely revealed. After realizing that the entire page was a Silverlight application, I decided to attempt to find the obscured image by examining the application using some of my reverse engineering skills picked up last semester.

I first examined the website's source code to find the actual Silverlight application which can be found here at the time of writing. Extracting this file would have been difficult if it weren't for Ubuntu assigning a zip icon for it. I simply double clicked the file and extracted the dlls.

I took the dlls and identified the one that was of importance (T-MobileClue.dll) and examined it in a PE Resource editor. I know realize that .NET Silverlight applications store resources differently than normal PE executables. Luckily there are applications similar to PE resource editors for .NET/Silverlight applications.

I used a program called Reflector to help go through the decompiled application. I quickly found by examining the source code that the obscured image to be revealed was the resource images/rebus.png. Reflector's resource browser quickly allowed me to open the resource. Sure enough this is the image that was revealed four days later. This was a few days ago so I do not feel bad revealing this information, but I will refrain from posting the rebus.png image here.

Proactive Secret Sharing

2010-06-15T00:15:00.000-05:00

I have been researching proactive secret sharing for my master's thesis quite extensively. I was upset to see that no wikipedia article existed so I created one myself. Check it out!
Proactive Secret Sharing on Wikipedia

Google Code Project for DAAP Android Client

2010-06-08T00:12:00.000-05:00

We have used Google Code Project Hosting to set up a project page for the Android DAAP client. This will hopefully keep DAAP from overriding this blog. This move also allows bugs, feature requests, and issues to be reported and well maintained. There is also a subversion repository provided by Google which will make handling commits between the two developers much easier. I hope to provide with the wiki section useful tutorials that explain some of the features, such as streaming, downloading of songs, queuing, etc. Releases will be posted there.

DAAP Android Client Updates

2010-05-10T18:51:00.000-05:00

The first release of the DAAP client for Android had a bit more problems than I would like to admit. We have been happily working with many users to get the application to work in their situations, and in doing so, we have made the DAAP client far better than it was in its initial release. The changes below are great:

Major memory optimizations
Minor bandwith optimizations
Automatically detect local shares
Playlist support
Queue support
Rhythmbox as server support

By eliminated many buffers that were created very frequently, the DAAP client is now able to handle much larger libraries. It is also easy to navigate thanks to playlist support. Queue support is nice, but the interface is probably in its beta. The auto-detection of local shares is really hit or miss and I can find no reason for it. According to a couple of android bug reports I have found, Android does not support connecting to multicast sockets, but it has worked for me a few times, but not very consistently. This is strange. Streaming will come as soon as I can find a good way to do it in Android without skips and jutters.

My main point in this post is to get feedback from the users. Is the DAAP client working for you, and if not, which server are you using? Are there any suggestions? Also, if you like the application, please rate it positively.

DAAP Media Player released to Android Market

2010-04-23T13:03:00.000-05:00

I am very happy to say that I have published the DAAP Media Player to the Android Market today and should be available for everyone to download! This is an initial release with many planned features to come, but I figured that everyone wanted something to use now. The application uses a heavily modified version of the Java Get It Together Client that has been stripped down to remove all GUI elements, all external libraries, and the integrated with an Android interface. The media player portion may look familiar because it is a modified version of the default Music player interface from Android.

We only have one server to test it on, but the application is known to work with a mt-daapd/firefly media server. Please comment on the functionality with other media servers. A google code project may be on the horizon. For more information on DAAP, please refer to wikipedia or my previous post.

Screenshots:

Downloads:

TOTP on Android

2010-04-19T11:30:00.000-05:00

Time-based One-time Password Algorithm is an expansion of the HOTP algorithm that uses time as the "moving counter" instead of a normal counter. Still is draft at the time of publishing, I decided that it would not be too difficult to add this to the mOTP application that is currently in the market. A brief description of TOTP can be found on wikipedia and the full current specification here. Since I already went through the trouble of making mOTP have a multiple OTP framework, all I had to do was add a class and some error checks in the setup page. I will upload the apks soon, but they are already available on the market.

Source code

Screenshots:

HOTP on Android

2010-02-26T01:00:00.002-06:00

I have updated the Android mOTP application to support the HOTP algorithm for One-Time Passwords. This involved implementing HOTP in Java. This was not such a chore thanks to Java's easy to use security tools. However, after writing this from scratch, I realized at the end of the RFC was example source code in Java! I used this reference implementation for the android app. I did have to make a minor change to the reference implementation to support more than 10 digits of output for the generated password.

After this step was done, all that was required was to add an option to make a profile either a HOTP profile or a mOTP type, edit some database fields, and generate a new layout for the HOTP generation page. The Mobile-OTP application is translated into three languages, English, Traditional Chinese, and Simplified Chinese. A goal of mine was to have all additional strings required for this update to also be translated. I have tried very hard to make this happen.

I also wanted to implement this change in such a way that if a third OTP comes around the corner (S/Key), that change wouldn't be so hard. I didn't implement any design patterns per the Gang of Four, the code would not require that many modifications to support another algorithm.

Some screenshots for the visual people (often the first thing I look for when evaluating software):

mDNS

2010-01-26T10:11:00.000-06:00

I have been reading about mDNS in preparation for the DAAP client that is coming along nicely. mDNS is the component of DAAP applications that allows automatic discovery of shares on the local network. mDNS is a portion of Apple's Bonjour (formerly Rendezvous) protocol. The way that mDNS works is by essentially creating a pseudo-distributed DNS name server on the local network. Whenever a client wants to discover information about which services reside on the local network, that client creates a query to a multicast address. All machines that posses some DNS records will receive this query. The machines that has information regarding that query will reply.

JmDNS is an implementation of mDNS in Java that is very simple. They have a sample application that fetches information about the network and displays what is discovered graphically. I mimicked this code in an attempt to discover all DAAP servers on the network. I always received information that a DAAP server existed on the network, but when my application attempted to resolve the name of the server, JmDNS would never issue the callback. My application would wait indefinitely for this callback and never know how to talk to the server. This was strange to me as wireshark showed that mDNS was behaving properly and returning the address when my application was resolving the name. JmDNS was just not issuing the callback. Even more strange was the sample application included in the source would always resolve. I found a thread on the support forums at sourceforge where someone describes the same problem. They noted that the only difference between their application and the sample one was that they request was issued in a thread. Wrapping just the request for resolving a name in a thread strangely fixes the issue. I filed a bug here. Now we can move forward and incorporate the great feature of automatic server discover for DAAP into our android client.

Mobile-OTP Android Client

2009-12-28T02:38:00.004-06:00

My brother and I have recently published an application to the Android Market that implements the mimics the Mobile-OTP reference implementation. I am proud of this for two reasons:
1. This is my first application into the android market.
2. I believe the features of this applications are better than the other MobileOTP clients I have seen thus far.

Our implementation allows for multiple profiles; essentially this allows a user to store credentials for multiple servers. Also, instead of remembering codes such as "#**#" to initialize a device, our client has easy to navigate menus that follow traditional Android applications' feel.

Here are some links

DAAP with Android

2009-12-20T22:15:00.001-06:00

I recently set up my router to port forward incoming DAAP request to my personal server. Essentially this allows me to listen to all my wonderful music over the internet. There exists a few problems though. iTunes does not allow connecting to DAAP servers that aren't connected on the local network. There are a few windows programs that do this, but just a heads up. Also, My phone currently has no software to allow me to connect to DAAP shares.

I am considering writing an android application that would allow this. I am still in the research phases though. First off, the software would only be able to access custom daap servers or iTunes applications whose version number is less than 7.2 as the protocol was changed then and no reverse engineering has broke it yet. Perhaps my reverse engineering course can change that, but let's see. Second, I need to be able to make android stream an mp3 file. I found this nice blog post which seems very helpful. Let's see where this goes.

HMAC with gcrypt

2009-10-21T17:31:00.001-05:00

On my way towards a working RFC4226 implementation, I needed an HMAC implementation. I originally started working on my own, but then I was going to need a working suite of hash functions. Obviously I should use some well-known cryptographic libraries for these hash functions. I found libgcrypt, part of GPG. I didn't expect for some reason to find that HMAC was already implemented in this suite as well.

I decided to use their HMAC to have better integration with their hash functions and for assured functionality. This turned out to be a good thing because it took lots ot tinkering to get my digest to match RFC 4231. Skipping the dirty work, here are the important functions (in order):

   gcry_check_version(GCRYPT_VERSION);
   gcry_control(GCRYCTL_SUSPEND_SECMEM_WARN);
   gcry_control(GCRYCTL_INIT_SECMEM, 1);
   gcry_control(GCRYCTL_RESUME_SECMEM_WARN);
   gcry_control(GCRYCTL_INITIALIZATION_FINISHED);
   gcry_md_open(&hash_handle_, hash_type,
      GCRY_MD_FLAG_SECURE| GCRY_MD_FLAG_HMAC);
   gcry_md_setkey(hash_handle_, key, key_length);
   gcry_md_write(hash_handle_, message, length);
   gcry_md_read(hash_handle_, 0);

The hardest part was getting the key to be correct. I take the hexadecimal description of the key, and convert it to an array of unsigned chars for safety (signedness is notorious for messing up values). This is all it takes (more or less) to get a working HMAC implementation. I arraned things more nicely in preparation for the full-blown RFC 4226 code.

Unit Testing Not a Panacea

2009-10-20T16:59:00.000-05:00

I attempted to use unit testing on my recently finished HMAC implementation in an attempt to use what I have been told repeatedly and experienced first hand. I first start by noting that when writing in C, unit testing libraries offer little more than a central block of code where tests should be placed. I looked at some libraries here and they seemed suitable, but for my small HMAC implementation, I just made a function that calls some tests I came up with on the spot.

Here is where my problems began. Unit tests can only test functionality that you explicitly write. This is all that a programmer could ask for, unless someone implements some FSA to represent a function. That would work on a small subset of useful functions (regular languages), but that is certainly a tangent. I tested some utility functions I wrote by supplying input and the known output. Example below:

   char *ascii_hex;
   unsigned char *binary;
   ascii_hex = (char *)malloc(4);
   ascii_hex[0] = 'A';
   ascii_hex[1] = 'B';
   ascii_hex[2] = 'C';
   ascii_hex[3] = '9';
   binary = ascii_hex_to_binary(ascii_hex, 2); /* 2 is size in bytes */
   if(binary[0] != 0xAB && binary[1] != 0xC9)
   {
       printf("Error, ascii_hex_to_binary didn't work\n");
   }

I was happy to know that my test passed, but I realized later that ascii_hex_to_binary was not behaving properly. My test did not check the all possible casess of the input string, especially the one that caused my program to not function correctly. The lesson I suppose would be one test is certainly not enough to check the behavior of a nontrivial function.

RFC 4226

2009-10-14T17:44:00.000-05:00

I found this when reading about OATH. I am now working on implementing this in C++ with eclipse using the C++ development tools. I find these are not up to par in comparison with Eclipse's java integration, but there is some utility when compared to vim (certainly not in the text editing field though).

I first need to implement HMAC. I am going to use the strategy pattern so that any hash function can be used with my HMAC implementation. Since I am not writing my own hash algorithms though, I will be limited to what Libgcrypt has to offer.

I noticed some problems though in my wikipedia research, so I corrected what I saw. I noticed that Existential forgery had its own page, where as selective and universal forgery were on one page. I combined the existential forgery page into the generic forgery page. I then renamed the forgery page to reflect the use of digital signatures as well as macs, so now Forgery (MAC) becomes Forgery (Cryptography). I also added a disambiguation page for Forgery.