Enigma To Eureka

Creating a Basic Isometric Map

2011-11-22T19:48:00.000-08:00

Last year Christian Weber wrote a helpful introductory article showing how to use CSS to layout tiles for an isometric map. However, the screen shot and demo looked a little odd; note the black V below where you can see "underneath" a tile.

The problems were partly caused by placing tiles adjacent to each other when they didn't have matching sides (i.e. a side that is all grass should butt up against an all grass side of another tile). In addition, the CSS styles for the tiles had the wrong offsets for identifying the positions of the sprites. The code in the article compensated for the style errors with some "corrections", which of course made it more confusing.

I've posted a corrected version here. It has a table indicating the type of each tile side, allowing for the generation of a random map were each tile's neighbors are appropriate, such that there are no gaps. For example:

Writing a Windows Service in Java

2011-05-08T07:37:00.000-07:00

I've got a couple of Java programs that I want to leave running permanently on my laptop, so I set about creating a Windows Service. I investigated several of the alternatives (Java Service Wrapper, Yet Another Java Service Wrapper, etc.), but having recently discovered Java Native Access (JNA), I decided to see if I could produce a fairly lightweight solution.

JNA (and libffi on which it depends) provides a means to dynamically create a bridge between Java and native libraries, a feature I've been wanting for years. I'd used JNI in the past, but I find it rather brittle. I've been pleasantly surprised to find that even when I made various mistakes with JNA, the JVM didn't crash; instead, JNA threw relatively meaningful exceptions, such as when it was unable to bridge the gap between a call from Windows to a Java method I wrote to accept that call (i.e. the argument types I used weren't appropriate). For example, the Windows Service API requires the service to implement a ServiceMain function which will be called by Windows:

VOID WINAPI ServiceMain(
  __in DWORD dwArgc,
  __in LPTSTR *lpszArgv
);

That lpszArgv is a pointer to an array of pointers to strings that will be passed to the ServiceMain function. I wanted to define a type, ReceiveStringArray, extending Pointer, as the type of lpszArgv in Java. Unfortunately, JNA could not bridge the gap from the native arguments to ReceiveStringArray, so I had to fallback to using JNA's Pointer as its type, and fortunately Pointer has a method, getStringArray, that handles exactly the translation needed here.

interface SERVICE_MAIN_FUNCTION extends StdCallCallback {
  /**
   * ServiceMain is the main method of the service. It should return only
   * once the service is stopped.
   * 
   * @param dwArgc
   * @param argv A pointer to an array (of length dwArgc)
   *             of pointers to strings.
   */
  void ServiceMain(int dwArgc, Pointer argv);
}

It may be that I was missing some appropriate constructor in ReceiveStringArray, or that a JNA TypeMapper was needed to handle initializing a ReceiveStringArray in this situation.

Another interesting challenge I had was that the first of my callback functions, ServiceMain, was being called at the expected time, but it was also being called when I expected a different callback function to be called instead. I'm not certain, but I think this is because JNA doesn't really care about the name of the method in the interface; there must be a single method, and that is the one that will be called. I had created two interfaces, but only a single class implementing them both. I suspected that I needed to have a separate class (or instance?) to receive each type of callback.

StartServiceCtrlDispatcher
A typical Windows Service is basically just a program that runs in the background, with no direct interaction with the user, with a few extra required interactions with Windows. When the program is started it must call StartServiceCtrlDispatcher, passing in a table of services to be started (typically just one). The dispatcher starts another thread to run ServiceMain, then it dispatches various Windows events to the service (e.g. when Windows is shutting down), and returns once the service stops.

import com.sun.jna.Native;
import com.sun.jna.Structure;
import com.sun.jna.platform.win32.Advapi32;
import com.sun.jna.win32.W32APIOptions;

public interface ExtendedAdvapi32 extends Advapi32 {
  ExtendedAdvapi32 INSTANCE = (ExtendedAdvapi32) Native.loadLibrary(
      "Advapi32", ExtendedAdvapi32.class, W32APIOptions.UNICODE_OPTIONS);
  class SERVICE_TABLE_ENTRY extends Structure {
    public String serviceName;
    public SERVICE_MAIN_FUNCTION serviceProc;
  }
  boolean StartServiceCtrlDispatcher(SERVICE_TABLE_ENTRY[] lpServiceTable);
}

The API doesn't include a length parameter to tell the dispatcher how many services are implemented by the program. Instead, the last entry in the table must have NULL pointers. Therefore, while the program doesn't need (at this point) the name of the service it is implementing, the field must not be NULL. Instead, set it to an empty string. For example:

ExtendedAdvapi32.SERVICE_TABLE_ENTRY entry =
    new ExtendedAdvapi32.SERVICE_TABLE_ENTRY();
entry.serviceName = "";
entry.serviceProc = someServiceMainFunction;
ExtendedAdvapi32.SERVICE_TABLE_ENTRY[] serviceTable =
    (SERVICE_TABLE_ENTRY[]) entry.toArray(2);
boolean result =
    ExtendedAdvapi32.INSTANCE.StartServiceCtrlDispatcher(serviceTable);

ServiceMain

The ServiceMain callback function is invoked on another thread from the main thread, and shouldn't return until the service stops (usually when Windows is shutting down, but it can also be stopped and started via a control panel). The function is passed an array of strings (as an argc and argv, just like a C program's main). The first string in the array is the name of the service. The following elements of the array are the "Start Parameters". These can be set in the service's Properties dialog box:

ServiceMain needs to call RegisterServiceCtrlHandlerEx to provide the service control dispatcher with a function to be invoked when Windows notifies the service of events (e.g. when Windows is shutting down, a user logs in or out, or there is a change in connected hardware).

public interface ExtendedAdvapi32 extends Advapi32 {
  interface HandlerEx extends StdCallCallback {
    int serviceControlHandler(int serviceControlCode, int eventType,
                              Pointer eventData, Pointer context);
  }
  class SERVICE_STATUS_HANDLE extends HANDLE {
    public SERVICE_STATUS_HANDLE() { }
    public SERVICE_STATUS_HANDLE(Pointer p) { super(p); }
  }
  SERVICE_STATUS_HANDLE RegisterServiceCtrlHandlerEx(
      String serviceName, HandlerEx handler, Object context);
}

Next, ServiceMain must call SetServiceStatus to inform Windows that the service running, and the types of event notifications the service wants to receive.

public interface ExtendedAdvapi32 extends Advapi32 {
  static final int SERVICE_WIN32_OWN_PROCESS = 0x00000010;
  class SERVICE_STATUS extends Structure {
    public int serviceType = SERVICE_WIN32_OWN_PROCESS;
    public int currentState = 0;
    public int controlsAccepted = 0;
    public int win32ExitCode = W32Errors.NO_ERROR;
    public int serviceSpecificExitCode = 0;
    public int checkPoint = 0;
    public int waitHint = 0;
  }
  boolean SetServiceStatus(SERVICE_STATUS_HANDLE serviceStatusHandle,
                           SERVICE_STATUS serviceStatus);
}

For example:

public interface ExtendedAdvapi32 extends Advapi32 {
  static final int SERVICE_RUNNING = 0x00000004;
  static final int SERVICE_ACCEPT_SHUTDOWN = 0x00000004;
  static final int SERVICE_ACCEPT_STOP = 0x00000001;
}

SERVICE_STATUS serviceStatus = new SERVICE_STATUS();
serviceStatus.currentState = ExtendedAdvapi32.SERVICE_RUNNING;
serviceStatus.controlsAccepted = (
    ExtendedAdvapi32.SERVICE_ACCEPT_STOP |
    ExtendedAdvapi32.SERVICE_ACCEPT_SHUTDOWN);
ExtendedAdvapi32.INSTANCE.SetServiceStatus(serviceStatusHandle,
                                           serviceStatus);

At this point the service can do its job, but it must also have some way to be notified that it is time to stop (e.g. via a flag shared between the ServiceMain thread and the service control handler). When ServiceMain learns that it needs to stop, it must tell Windows that it has stopped before returning.

public interface ExtendedAdvapi32 extends Advapi32 {
  static final int SERVICE_STOPPED = 0x00000001;
}

SERVICE_STATUS serviceStatus = new SERVICE_STATUS();
serviceStatus.currentState = ExtendedAdvapi32.SERVICE_STOPPED;
serviceStatus.controlsAccepted = 0; // Accept no more notifications.
ExtendedAdvapi32.INSTANCE.SetServiceStatus(serviceStatusHandle,
                                           serviceStatus);

Service Control Handler (HandlerEx)

The service control dispatcher calls the service's control handler when the requested events occur. To support just shutdown and stop events, this suffices:

public interface ExtendedAdvapi32 extends Advapi32 {
  static final int SERVICE_CONTROL_SHUTDOWN = 0x00000005;
  static final int SERVICE_CONTROL_STOP = 0x00000001;

  // Must return NO_ERROR for this, not ERROR_CALL_NOT_IMPLEMENTED.
  static final int SERVICE_CONTROL_INTERROGATE = 0x00000004;    
}

public int serviceControlHandler(int serviceControlCode, int eventType,
                                   Pointer eventData, Pointer context) {
  switch (serviceControlCode) {
  case ExtendedAdvapi32.SERVICE_CONTROL_INTERROGATE:
    return W32Errors.NO_ERROR;
  case ExtendedAdvapi32.SERVICE_CONTROL_SHUTDOWN:
  case ExtendedAdvapi32.SERVICE_CONTROL_STOP:
    // TODO Signal ServiceMain to stop.
    return W32Errors.NO_ERROR;
  default:
    return W32Errors.ERROR_CALL_NOT_IMPLEMENTED;
  }
}

Encapsulating the Windows API

To avoid polluting the 'pure' Java with all of the above, I defined the following simple interface that my services would implement (which I can use on other operating systems):

public interface ISimpleService {
  int run(String[] args);
  void stop();
}

The return value from run could (in a slightly more complicated solution) be used to set the SERVICE_STATUS.serviceSpecificExitCode field.

These two classes are used to invoke the methods of ISimpleService:

class ServiceControlHandler implements HandlerEx {
  private final ISimpleService service;
  public ServiceControlHandler(ISimpleService service) {
    this.service = service;
  }
  public int serviceControlHandler(int serviceControlCode, int eventType,
                                   Pointer eventData, Pointer context) {
    switch (serviceControlCode) {
    case ExtendedAdvapi32.SERVICE_CONTROL_INTERROGATE:
      return W32Errors.NO_ERROR;
    case ExtendedAdvapi32.SERVICE_CONTROL_STOP:
      service.stop();
      return W32Errors.NO_ERROR;
    default:
      return W32Errors.ERROR_CALL_NOT_IMPLEMENTED;
    }
  }
}

class SimpleServiceMain implements SERVICE_MAIN_FUNCTION {
  private final ISimpleService simpleService;
  private final SimpleServiceControlHandler handler;
  private SERVICE_STATUS_HANDLE serviceStatusHandle;
  public SimpleServiceMain(ISimpleService simpleService,
                           SimpleServiceControlHandler handler) {
    this.simpleService = simpleService;
    this.handler = handler;
  }
  public void ServiceMain(int argc, Pointer argv) {
    if (argc < 1 || argv == null) {
      // Missing the service name.
      return;
    }
    try {
      String[] args = argv.getStringArray(0, argc, true);
      String serviceName = args[0];
      String[] startParameters = Arrays.copyOfRange(args, 1, args.length);
      serviceStatusHandle =
          ExtendedAdvapi32.INSTANCE.RegisterServiceCtrlHandlerEx(
              serviceName, handler, null);
      setServiceStatus(ExtendedAdvapi32.SERVICE_RUNNING,
          ExtendedAdvapi32.SERVICE_ACCEPT_STOP |
          ExtendedAdvapi32.SERVICE_ACCEPT_SHUTDOWN);
      simpleService.run(startParameters);
    } finally {
      setServiceStatus(ExtendedAdvapi32.SERVICE_STOPPED, 0);
    }
  }
  private void setServiceStatus(int currentState, int controlsAccepted) {
    SERVICE_STATUS serviceStatus = new SERVICE_STATUS();
    serviceStatus.currentState = currentState;
    serviceStatus.controlsAccepted = controlsAccepted;
    ExtendedAdvapi32.INSTANCE.SetServiceStatus(
        serviceStatusHandle, serviceStatus);
  }
}

And a function to create instances and start the service control dispatcher:

public static void runSimpleService(ISimpleService service) {
  SimpleServiceControlHandler handler =
      new SimpleServiceControlHandler(service);
  SimpleServiceMain serviceMain =
      new SimpleServiceMain(service, handler);
  SERVICE_TABLE_ENTRY entry = new SERVICE_TABLE_ENTRY();
  entry.serviceName = "";
  entry.serviceProc = serviceMain;
  SERVICE_TABLE_ENTRY[] serviceTable =
      (SERVICE_TABLE_ENTRY[]) entry.toArray(2);
  ExtendedAdvapi32.INSTANCE.StartServiceCtrlDispatcher(serviceTable);
}

Example Service
Here is a trivial service that just waits to be stopped.

public class WindowsServiceHandlerExample implements ISimpleService {
  private final CountDownLatch latch = new CountDownLatch(1);
  public int run(String[] args) {
    try {
      latch.await();
    } catch (InterruptedException e) {
    }
    return 0;
  }
  public void stop() {
    latch.countDown();
  }
  public static void main(String[] args) {
    WindowsServiceUtil.runSimpleService(new WindowsServiceHandlerExample());
  }
}

Distributing Work

2011-02-26T12:54:00.000-08:00

During November and December of last year I developed my checkers program to the point where I could run all three of the experiments conducted by Fogel and Chellapilla. The longest ran for 5 days on my 2 processor laptop, which indicates that it'll take months to run some of the experiments I have in mind.

Since I'm doing this exercise for fun, and I like building "systems", I decided to make a system for distributing work (games to be played) to other machines in the house. I've developed a somewhat complicated Java web app (using embedded Jetty) that manages a jar repository and runs (in subprocesses) Java programs whose descriptions are uploaded. The description consists of jar names and jar hashes (to avoid running the wrong version of a jar as I'm developing), a main class name, and command line. The Java program is provided with a work area in the file system, to which the remote client can upload any necessary files prior to starting the program, and from which the remote client can download any files after the program is done, including files containing the output of the stdout and stderr streams.

I say "somewhat complicated" because I didn't make the decision to use embedded Jetty until late in the process, and if I'd made it earlier, I would have used more of Jetty's facilities to handle the file management.

To simplify creating the description of a Java program, I created a mechanism for walking the current process's classpath, creating jars for unpacked entries (e.g. the bin folders of my Eclipse projects), and uploading them to the various servers.

Next up I'm working on how to transfer units of work from the main program to the workers, and how to get the responses back. My current plan is to have the main program run an embedded web server (Jetty) with a servlet that a worker will contact to get a unit of work (e.g. two checkers players to compete), and will then re-contact with the result of the unit of work (e.g. the game outcome).

This mechanism is certainly sufficient to the task, but feels a bit awkward. I think I'd like some variant of a ThreadPoolExecutor that supports distributed threads, but I've not located nor invented such a beast. Sigh.

More later.

Yes, Virginia, Testing is Important!

2010-12-29T06:15:00.000-08:00

In my zeal to optimize my checkers playing program, I included a number of optimizations in the search algorithm: minimax with alpha-beta pruning, plus a memory of previous partial search trees to assist in ordering of future searches, and to skip evaluations when the results are known. Too many optimizations, as it happens.

I wrote quite a few JUnit tests for the basic checkers board manipulation code, but wasn't sure how to go about testing the search algorithm. I wrote some very basic tests that the pruning was happening as expected, but left it at that.

I then wrote a system for evolving the neural networks, and repeated the evolution experiments described by Fogel and Chellapilla. Again, I wasn't quite sure how to evaluate the results, as I'm not yet ready to play hundreds of games online using the best evolved network as my evaluation function.

So, I studied the last generation's networks and the games they played, and noticed that they'd all played the same first move... and the same first reply... and the same next reply! The first three moves were all the same. Wow! Did they all stumble upon the best opening moves? Or perhaps all of the surviving networks were descended from a relatively recent network that made that choice?

I decided to confirm that initial generation of networks was much more random in its play. Unfortunately, upon reviewing their games, I found they too played the same first three moves. Sigh. Back to the drawing board.

To track this down, I tried shuffling the legal move choices presented to the search algorithm, but that made no difference. Next, I implemented minimax and compared its choices to those of my enhanced alpha-beta search. As you might expect, they didn't agree. So, I implemented a basic alpha-beta search, which did agree with minimax. In the course of debugging, I found several mistakes in the over optimized alpha-beta implementation, and I don't think I've found them all. Fortunately, testing will help me figure out when I've got it wrong, and hopefully the next 1000+ generations of evolution will be more fruitful.

Evaluating a Checker Board with a Feed Forward Neural Network

2010-12-04T17:49:00.000-08:00

With two-player zero-sum games such as checkers and chess, it is common to build computer players based on the idea of searching the game tree to select moves using some variant of the minimax search algorithm and an evaluation function. The evaluation function takes a game board as input and returns a numeric score as output, where the score is highest when the board is a win for the player, and the score is lowest when the board is a loss for the player. For checkers, an extremely simple example of an evaluation function just adds up the number of pieces the player has, and subtracts the number of pieces the opponent has.

When using a neural network to evaluate a checkers board, we need some representation of the checkers board and the pieces on it. Fogel and Chellapilla chose to map the board to an array of 32 floating point numbers, where each entry had one of five values:

+K Player's King
+1 Player's Man
0 Empty
-1 Opponent's Man
-K Opponent's King

K was an evolvable value, initialized to 2.0.

In addition to the above, in their second and third experiments, they computed a value directly from the inputs (i.e. without weights): they summed the 32 floating point inputs, to come up with a value that reflects the piece differential between the two players.

We can imagine other mappings. For example, we might have several binary inputs per square, such as:

3 bits: black, white, king; at most one of black or white would be set, and king is only set if one of the other two is set.
4 bits: empty, black, white, king; at most one of empty, black or white would be set, and king is only set if black or white is set.
4 bits: black king, black, white, white king; at most one would be set at a time.
5 bits: black king, black, empty, white, white king; exactly one would be set at a time.

Fogel and Chellapilla chose a search depth of 4 ply (2 moves by each player), but extended the depth whenever a move by a player was "forced". Unfortunately I found their description of how this was handled a bit vague:

In addition, when forced moves were involved, the search depth was extended (let f be the number of forced moves) because in these situations the player has no real decision to make. The ply depth was extended by steps of two, up to the smallest even number that was greater than or equal to the number of forced moves f that occurred along that branch. If the extended ply search produced more forced moves then the ply was once again increased in a similar fashion. Furthermore, if the final board position was left in an "active" state, where the player has a forced jump, the depth was once again incremented by two ply. Maintaining an even depth along each branch of the search tree ensured that the boards were evaluated after the opponent had an opportunity to respond to the player's move.

It wasn't clear to me whether this test is performed only on the moves of the player, or also on the moves of the opponent. Furthermore, it wasn't clear what the definition of "forced move" was. Did it mean that the player to move had only jumps to choose among (i.e. possibly more than one); or did it mean that the player to move had only a single move that was possible, whether it was a simple move or a jump; or did it mean that the player to move had only a single jump available.

My best guess is that whenever the player, and not the opponent, had only jumps available (whether they had a choice of jumps or not), the search depth on that branch of the game tree was increased by 2 ply.

UPDATE 2010-12-09: Dr. Fogel was kind enough to respond to my questions about forced jumps, and he recalls that this meant the player whose choice it was had only a single move, and thus had no real choice. This applied for either player in the game tree, and it didn't matter whether the move was a simple move or was a jump.

Blondie24 Reconsidered

2010-12-01T19:14:00.000-08:00

I discovered David Fogel's "Blondie24: Playing at the Edge of AI" in 2006 while killing time at the library waiting for my daughter. It is a very engaging story of his effort, with colleague Kumar Chellapilla, to evolve an American Checkers (English Draughts) "player", with no human expertise provided, and then to evaluate that player by competing online against (presumably) people on zone.com (now zone.msn.com).

Dr. Fogel covers the history of AI in playing chess and checkers, and provides background on evolutionary algorithms and artificial neural networks. He then covers the three network topologies they used, and the training algorithm, the key feature of which is that they created a random of population of players (really, evaluation functions), and had those players, and their offspring, compete against each other in tens of thousands of checkers games across hundreds of generations, keeping and evolving the most successful players..

One of the challenges they faced was limited computing resources; I think they were doing this work around the year 2000, and that the machine they had available to (mostly) dedicate to this task was a PC with a 400MHz Pentium processor. For their final network topology, in which their were more than 5000 weights to be adjusted, it took 6 months to run through 800 generations. As a result, they were not able to explore the many lines of investigation that spring to mind.

I'm interested in following some of those lines, and I have the luxury of 10 more years of CPU development. To provide a baseline, I've been working to reproduce their work, based on the information in Dr. Fogel's book, and the several papers they published together on the topic. I'll be writing about my efforts in posts to follow this.

Android Emulator -- Please Wait

2009-12-27T10:58:00.000-08:00

I'm trying out the Android Development Tools (Eclipse-based), and have been very frustrated at the fact that the Hello World application wouldn't run. The emulator just sat there display the word Android (not the logo) for several minutes until I gave up:

I searched for suggestions, and it turned out that the problem was simply that I was being impatient. The first time you run the emulator with a specific Android Virtual Device (avd), it sets up a bunch of image files, and this is apparently rather time consuming. After a while, you see this screen (SDK 1.6) with the animated Android logo:

And finally, it reaches the home screen (or your application, depending on how you launched the emulator):

So, apparently patience IS a virtue. :-)

Update to Finding Your IP v4 Broadcast Address Using Java

2009-09-27T08:22:00.000-07:00

My earlier post Finding Your IP v4 Broadcast Address Using Java mentioned that you can set the property java.net.preferIPv4Stack using System.setProperty(). I recently wrote a JUnit test of code that used that approach, which failed. After some investigation I realized that Eclipse's JUnit test runner uses a socket to communicate test results back to Eclipse, and that socket had been opened long before my code was able to set the system property.

So, the basic conclusion is that if you must force the use of the IPv4 stack, do so using the command-line:

-Djava.net.preferIPv4Stack=true

I'm A Ternary Expression, What's My Type?

2009-08-29T07:34:00.000-07:00

I was rather annoyed today to find yet another difference between the Eclipse Java compiler, and the Sun Java compiler (1.5, in both cases). Today's challenge was with a ternary expression. I had code with the following structure:

package dummy;
interface Proxy {}

abstract class Base {
 Base(Base owner) {}
}

abstract class TypedBase extends Base {
  TypedBase(Base owner) {super(owner);}
}

class ObjectClass extends TypedBase implements Proxy {
  public ObjectClass() {
    super(null);
  }
}

class SubType extends Base implements Proxy {
  SubType(ObjectClass owner) {
    super(owner);
  }
}

class ObjectProperty extends TypedBase implements Proxy {
  public ObjectProperty(ObjectClass objectClass, SubType optionalSubType) {
    super(optionalSubType == null ? objectClass : optionalSubType);
  }
}

This code compiled fine with Eclipse, but not with the Sun compiler, which complained as follows:

CompilerTest.java:[27,4] cannot find symbol
symbol  : constructor TypedBase(java.lang.Object&dummy.Proxy&dummy.Base)
location: class dummy.TypedBase

CompilerTest.java:[27,4] cannot find symbol
symbol  : constructor TypedBase(java.lang.Object&dummy.Proxy&dummy.Base)
location: class dummy.TypedBase

It appears that Eclipse has determined the type of the ternary expression to be dummy.Base (makes sense to me), but the Sun compiler seems to have employed the Java Generics facilities which allow one to have multiple constraints on a type variable. Reading the Java Language Specification, the Sun compiler appears to be doing what the spec says, which is little consolation. I found a bug report that explains the problem in more detail, and requests that the spec for the ternary expression be fixed to avoid this problem (which I think would make the spec line up with the Eclipse compiler's behavior).

There is of course a simple fix: add a cast to the desired type, Base in this case. I actually chose to create a helper method as shown below because I find ternary expressions problematic to debug (i.e. I prefer to have if/then/else statements, which allow me to set separate breakpoints on the branches of the if).

class ObjectProperty extends TypedBase implements Proxy {
  public ObjectProperty(
      ObjectClass objectClass,
      SubType optionalSubType) {
    super(chooseOwner(objectClass, optionalSubType));
  }
  private static Base chooseOwner(
      ObjectClass objectClass,
      SubType optionalSubType) {
    if (optionalSubType == null)
      return objectClass;
    else
      return optionalSubType;
  }
}

Finding Your IP v4 Broadcast Address Using Java

2009-08-23T12:52:00.000-07:00

I was pleased when Java 1.4 added the ability to find the available network interfaces, and more recently added the ability to get details of the addresses of those interfaces (in 1.6), because these features make it easier to write "system" tools.

As part of writing a Java interface to the HDHomeRun, I wanted to broadcast a discovery packet to my local subnet, to which the HDHomeRun would respond. At first I just hard-coded the address 192.168.0.255, which worked fine, but wasn't very portable. In fact, I've since changed routers, which happened to change the local subnet to 192.168.1.0, with a broadcast address of 192.168.1.255. So, I made use of the Java classes java.net.NetworkInterface and java.net.InterfaceAddress, roughly as follows:

Enumeration<NetworkInterface> interfaces =
    NetworkInterface.getNetworkInterfaces();
while (interfaces.hasMoreElements()) {
  NetworkInterface networkInterface = interfaces.nextElement();
  if (networkInterface.isLoopback())
    continue;    // Don't want to broadcast to the loopback interface
  for (InterfaceAddress interfaceAddress :
           networkInterface.getInterfaceAddresses()) {
    InetAddress broadcast = interfaceAddress.getBroadcast();
    if (broadcast == null)
      continue;
    // Use the address
  }
}

I was surprised when I ran my test of this code to discover that the broadcast address reported was 255.255.255.255. Something was clearly wrong. It turns out that the JRE will use the IPv6 stack if it is available, else will use IPv4. When using an IPv6 stack, InterfaceAddress never has an accurate IPv4 broadcast address. Sigh.

Fortunately, there is a Java system property that directs the JRE to use the IPv4 stack:
java.net.preferIPv4Stack

This can be set on the command line (i.e. -Djava.net.preferIPv4Stack=true), or it can be set prior to calling NetworkInterface.getNetworkInterfaces(). Changing the system property after the first call to getNetworkInterfaces() has no effect (i.e. it is too late; it appears that the choice of network stacks is locked at that point). I suspect that any call that loads the networking stack will lock the choice.

I found the pointer to the Java system property in a Sun Forums posting by Ivan Jozsef Balazs.

HDHomeRun Packet Structure

2009-08-22T10:07:00.001-07:00

The HDHomeRun has 3 types of RPC:

Discover, which locates HDHomeRun devices on the network
Get/Set, which read and write variables
Upgrade, used to upgrade the firmware (I've only done this using the provided tool)

The variables are used to tune one of the two tuners on the device to a particular frequency (i.e. select an MPEG-2 Transport Stream from the many that might be provided by source), to get status information (e.g. the signal strength and error count measured by each tuner), and of course to specify where the selected video data stream is to be sent.

Except for the video data stream, all packets to and from the HDHomeRun have the following structure:

Packet Type (16-bit big endian integer)
Payload Length in Bytes (16-bit big endian integer)
Payload
CRC (32-bit little endian integer)

The payload of the Discover and Get/Set packets consists of a sequence of TLV (Tag, Length, Value) tuples with this structure:

Tag (8-bit integer)
Value Length in Bytes (variable length integer, 1 or 2 bytes, described below)
Value

When the value length is 127 or less, it is just 1 byte. But when it is 128 or greater, the first byte is the low-order 7 bits, with bit 8 (the high bit) set, and the next byte is the length shifted down by 7 bits. The value length won't be larger than 1460, because that is the maximum length of an entire packet, so we won't ever need to send more than 11 bits of length. For those familiar with Unicode, this is vaguely reminiscent of UTF-8 (though UTF-8 is big endian, and supports encoding code points with more bits).

HDHomeRun and Java

2009-08-17T14:01:00.001-07:00

I've had several DVRs over the last 5 years: a Panasonic DMR-E85H, a Windows Media Center PC with Linksys Media Center Extenders, and currently a Verizon FiOS HD DVR. While I liked their basic capabilities, I've always found that there were features I wanted to add, but the devices weren't (very) open to extension.

I was thus intrigued by an unusual device, the HDHomeRun from SiliconDust. It has two digital TV tuners, and forwards the selected video data stream(s) via Ethernet to an IP address and port. Each tuner has its own coax jack, and can be connected to either cable TV, or to a digital TV antenna (e.g. for over-the-air HDTV). The HDHomeRun could easily be a key component of a home brew DVR, and the price was low enough that I decided to buy one to experiment with.

The HDHomeRun comes with a C library and command-line program for controlling the HDHomeRun, but I prefer to write in Java, especially when it comes to multi-threaded software, which a DVR would definitely be. Fortunately, the library source is available, along with a document explaining quite about the process of interacting with the device.

This will be the first of several posts regarding the HDHomeRun and the Java library I created to interact with it. More soon...

NEJUG: Career 2.0, JFugue and Log4JFugue

2009-08-14T04:38:00.000-07:00

The NEJUG (New England Java Users Group) event last night featured not one but three presentations.

The headliner was Jared Richardson with his presentation "Career 2.0: Take Control of Your Life". Prior to that were two short presentations: David Koelle introducing JFugue, an API for generating music with little code; and Brian Tarbox demonstrating Log4JFugue, an entertaining intersection of Log4J and JFugue.

Jared had some good observations about types of workers (Jellyfish and Sharks), and some sensible advice for being proactive with your career (Learn and Share).

In Jared's parlance, a Jellyfish is someone who does what his job requires, what his boss needs, but doesn't do more than that; the career of a Jellyfish drifts on the currents of work assignments. His best example was a friend who wouldn't learn anything new if he wasn't being paid to do it (nice work if you can get it, but you're not likely to get that often). At the other extreme, a Shark regularly seeks out new opportunities, and learning proactively so as to be ready for those opportunities.

Grossly simplified, Jared had these recommendations:

Learn something, such as the LOTY (Language Of The Year) or the TOTY (Technology Of The Year)
Share what you learn: Blog, Speak, Write Articles, etc.
Set measurable goals: short term goals (e.g. write 1 page today) that help you take steps to meet your long term goals (write that book!)

Jared has posted a video of this presentation at http://qik.com/video/1009098.