Getting Ripped

For the past few weeks I've been converting my DVD and Blu-ray Disc (BD) collection to MP4 format so everything can be easily viewed on the Apple TV. Generally, this has been fairly painless (especially for DVDs), but there is one thing that I desire that most people probably don't care about: captions.

Maybe I'm getting old, but for about a decade I've preferred to watch shows with captions. There are basically three types of captions present on DVD and BD media:

1. Closed Captions - text-based captions that may include hard-of-hearing information.
2. Bitmap Captions - bitmaps that are overlaid on the screen.
3. Forced Bitmap Captions - technically a subset of (2). Typically shown for foreign languages.

Bitmap Captions allow the DVD/BD publisher to ensure that captions look the same on every player, whereas text-based Closed Captions can look and perform differently on different players, TVs, etc. And in my experience, Bitmap Captions don't display on the Apple TV whereas Closed Captions will. Also of note is that DVD and BD each use a separate type of Bitmap Captions--VobSub for DVD and PGS for BD.

Now, if Bitmap Captions don't show on the Apple TV, why do I care about them? There are two main reasons: 1). If Closed Captions don't exist and 2). Forced Subtitles.

At this point I should mention that I'm using Handbrake to encode my movies for the Apple TV. Several pages exist as guides to using Handbrake, so I'm not going to cover it in much detail, except for dealing with captions.

If Closed Captions Don't Exist

If a DVD has Bitmap Captions (VobSub) but no Closed Caption, then we need to find a way to add text-based Closed Captions. Fortunately, there are a few options.

The first option is my least favorite. Handbrake has the ability to burn-in Bitmap Captions. This means that captions will be present, but there will be no way to turn them off. For all captions, that's not desirable, but as seen below it can be quite handy for Forced Captions.

The second option is to find a SubRipper (SRT) file that someone has created. Fortunately there are some great crowd-sourced resources for this, like Open Subtitles and my personal favorite, SubScene. These sites allow you to search for a SRT file that someone has created and uploaded. Handbrake can import the SRT file by using the Import SRT button (seen in the picture above). The downside to this method is that timing is everything. There can be Special Editions and Director's Cut versions of the movie you're searching for, so ensuring that you have the correct file will involve using Handbrake's Preview feature or using a player (like VLC Media Player) to preview before encoding. Otherwise you could end up with captions that don't match.

The final option is to create your own SRT file from the Bitmap Caption. This can either be done manually (VERY time consuming) or with the aid of OCR software. This was more of a last resort for me, but I did do it for a few of my DVDs. I used a program called Subresync. It is about as naive as OCR software can be, essentially asking the user the first time it encounters a specific pixel pattern:

Forced Captions

This is where things get a bit trickier. Forced captions were typically not a problem for DVDs as all of my DVDs that used Forced Captions actually had them burned in to the video stream. Not so for my BDs. A good example is Star Trek VI: The Undiscovered Country where the Klingon speech is a Forced Caption track and is not burned in to the video stream. And Forced Captions are something that everyone should want as they are essentially part of the movie.

Also complicating this process is the fact that Handbrake does not yet understand PGS-style Bitmap Captions (the system used for BDs). Therefore, the PGS (or 'Sup') Captions must be converted to VobSub before using Handbrake. This involves the following steps:

1. I use MakeMKV to get the BD data on the hard disk in MKV format.
2. Load the .mkv file in the mkvmerge tool from MKVToolNix. This will tell you which tracks contain PGS Caption data:
   
   In this example, IDs 2, 3, 4 and 5 contain PGS subtitle data. Leave this program open as we'll come back to it if we do indeed find Forced Captions.
3. Extract the subtitle data using mkvextract on the command line:
   mkvextract tracks Star_Trek_VI...mkv 2:sub2.sup 3:sub3.sup 4:sub4.sup 5:sub5.sup
   This will extract tracks 2-5 into files sub2.sup, sub3.sup, sub4.sup and sub5.sup
4. Open each extracted PGS Subtitle file using BDSup2Sub to see if it contains Forced Captions. In the Star Trek 6 example, we find that track 3 contains nothing but Forced Captions:
   
5. Since we've found Forced Captions, we need to convert them to a format that Handbrake understands. Fortunately, this is what BDSup2Sub was designed to do. File->Export gives the following dialog (make sure that 'Export only forced' is checked):
   
   Interestingly, VobSub is made up of a .idx text file and a .sub binary file.
6. Now we need to add the newly created VobSub captions and re-mux into a new .mkv file. Go back to the mkvmerge that was open from step 2. Click the Add button and select the new .idx file that was created in step 5, then press Start Muxing:
   
7. When the muxing finishes, you can now load the new .mkv file up in Handbrake and burn-in the Forced Captions:
   

Qapla'!

Getting captions to work correctly on the Apple TV with custom-encoded movies can be a bit tricky, but if you're hard-of-hearing or just used to using captions, hopefully this guide can help you.

New Domain!

Well, I've finally gotten around to registering joshuakriegshauser.com. It's about time. Which means that this blog will appear at blog.joshuakriegshauser.com.

Oddly enough, kriegshauser.com is considered a premium domain and is listed for about $1600. I honestly hope whoever is holding it never gets that.

1 in 600,000

For Christmas this year, my wife gave me (among other things) Another Tough Puzzle. This puzzle claims that "with millions of wrong solutions, the chance of solving this puzzle is ONE in 600,000!"

There are 16 triangular pieces and each piece has three connections each being one of four possible shapes. The completed puzzle should be a pyramid with six connections on the edges pointing in and six pointed out.

The puzzle also claims that "it looks easy...but just when you think you've solved it, the last piece proves you wrong." This is very true and very frustrating. I (and others) played around with the puzzle for a while always ending up with one piece that didn't fit.

Then I thought, "I write software for a living; why don't I do that here?" I've enjoyed writing solvers in the past (my Minesweeper solver would actually play the GUI for you on previous Windows versions). I mostly use C++, so I decided to use it here as well. Certainly there are languages more suited to rapid development, but I'm a glutton for punishment.

The first step was to describe the pieces. We noticed pretty quickly that half of the pieces have two outward-facing connectors (outputs) and one inward-facing connector (input) and the other half are opposite (two inputs and one output). There are no pieces with three inputs or outputs.

enum FaceType
{
    eFaceTypeClover = 0,
    eFaceTypeHeart,
    eFaceTypeSpade,
    eFaceTypeDiamond,
};

enum Direction
{
    eDirIn = 0,
    eDirOut,
};

struct Node
{
    FaceType face;
    Direction dir;

    bool fits(const Node& rhs) const
    {
        return face == rhs.face && dir != rhs.dir;
    }
};
struct Piece
{
    Node node[eNumSides];

    Piece(FaceType in, FaceType out1, FaceType out2, bool)
    {
        node[0].face = in;
        node[1].face = out1;
        node[2].face = out2;
        node[0].dir = eDirIn;
        node[1].dir = node[2].dir = eDirOut;
    }
    Piece(FaceType in1, FaceType in2, FaceType out)
    {
        node[0].face = in1;
        node[1].face = in2;
        node[2].face = out;
        node[0].dir = node[1].dir = eDirIn;
        node[2].dir = eDirOut;
    }
};

Using these structures, all of the pieces can be declared:

Piece pieces[eNumPieces] =
{
// one input, two outputs
Piece(eFaceTypeSpade, eFaceTypeDiamond, eFaceTypeHeart),        // 0
Piece(eFaceTypeHeart, eFaceTypeDiamond, eFaceTypeSpade),        // 1
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeSpade),       // 2
Piece(eFaceTypeClover, eFaceTypeSpade, eFaceTypeHeart),         // 3
Piece(eFaceTypeSpade, eFaceTypeHeart, eFaceTypeClover),         // 4
Piece(eFaceTypeHeart, eFaceTypeSpade, eFaceTypeClover),         // 5
Piece(eFaceTypeSpade, eFaceTypeClover, eFaceTypeDiamond),       // 6
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeHeart),       // 7

// two inputs, one output
Piece(eFaceTypeClover, eFaceTypeDiamond, eFaceTypeHeart, true), // 8
Piece(eFaceTypeClover, eFaceTypeDiamond, eFaceTypeSpade, true), // 9
Piece(eFaceTypeHeart, eFaceTypeDiamond, eFaceTypeSpade, true),  // a
Piece(eFaceTypeHeart, eFaceTypeClover, eFaceTypeDiamond, true), // b
Piece(eFaceTypeHeart, eFaceTypeClover, eFaceTypeSpade, true),   // c
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeHeart, true), // d
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeSpade, true), // e
Piece(eFaceTypeSpade, eFaceTypeHeart, eFaceTypeDiamond, true)   // f
};

Now that the pieces are all set up, the gameboard must be described. The end result should be a pyramid made up of all 16 pieces (see diagram). Therefore, I had to describe how the pieces relate to each other in the gameboard. This will allow the solver algorithm to test that a piece 'fits' if its connectors match the adjacent pieces. In order to do this, each position in the desired puzzle shape is marked with a number and each side of the triangular pieces are numbered as well. The sides are always numbered clockwise starting at the horizontal side so that adjacent pieces in the puzzle have sides matching (for instance, pieces 7 and 8 both share their side number 2).

The array of PieceLoc structures define how each piece relates to adjacent pieces:

PieceLoc locs[eNumPieces] =
{
// Sides:     0               1               2          // Pieces
PieceLoc(eInvalidPiece,  eInvalidPiece,              1), // 0
PieceLoc(            7,              2,              0), // 1
PieceLoc(eInvalidPiece,              1,              3), // 2
PieceLoc(            9,              4,              2), // 3
PieceLoc(eInvalidPiece,              3,              5), // 4
PieceLoc(           11,              6,              4), // 5
PieceLoc(eInvalidPiece,              5,  eInvalidPiece), // 6
PieceLoc(            1,  eInvalidPiece,              8), // 7
PieceLoc(           12,              9,              7), // 8
PieceLoc(            3,              8,             10), // 9
PieceLoc(           14,             11,              9), // a
PieceLoc(            5,             10,  eInvalidPiece), // b
PieceLoc(            8,  eInvalidPiece,             13), // c
PieceLoc(           15,             14,             12), // d
PieceLoc(           10,             13,  eInvalidPiece), // e
PieceLoc(           13,  eInvalidPiece,  eInvalidPiece)  // f
};

The fitting function is recursive. The first time it is called it has all 16 pieces remaining to try and fit. It loops through all remaining pieces rotating them in all possible positions each time checking to see if the piece fits. If the piece fits, it calls itself again this time with 15 pieces remaining. When a pieces is found that fits, it calls itself again with 14 pieces remaining. And so on, and so forth until all pieces have been used. If a piece doesn't fit, it goes on to the next piece. If a solution is found or no more pieces fit, the function returns and tries the next piece.

Since we only have 16 pieces, I use a bitmask to determine which pieces are already used.

void FitRemaining(int remain)
{
    if (remain <= 0)
    {
        ShowSolution();
    }
    else
    {
        int index = eNumPieces-remain;
        for (int i = 0; i < eNumPieces; ++i)
        {
            if ((used & (1 << i)) == 0)
            {
                used |= (1 << i); // Mark in-use
                pieces[index] = i;
                for (int r = 0; r < eNumRotations; ++r)
                {
                    rotation[index] = r;
                    if (validate(index))
                    {
                        FitRemaining(remain - 1);
                    }
                }
                pieces[index] = eInvalidPiece;
                used &= ~(1 << i); // No longer in-use
            }
        }
    }
}

The last part is the validation function. We really only need to validate the most recent piece added. Figuring out which sides are facing each other is the most difficult part, but even that is pretty easy. Because of how the gameboard is organized we already know that side indexes on adjacent pieces always face each other. All we need to do is take the rotation into account and ensure that the shapes match:

bool validate(int piece) const
{
    assert(piece >= 0 && piece < eNumPieces);
    const Piece* cur = Get(piece);
    int rot1 = rotation[piece];
    const PieceLoc& fit = locs[piece];
    for (int f = 0; f < eNumSides; ++f)
    {
        const Piece* p = Get(fit.neighbors[f]);
        if (p)
        {
            int rot2 = rotation[fit.neighbors[f]];
            if (!cur->node[(rot1 + f) % 3].fits(p->node[(rot2 + f) % 3]))
            {
                return false;
            }
        }
    }
    return true;
}

That's all there is to it! I probably spent less time writing this program than manually (and frustratingly) trying to find the solution.

In fact with this program I found all 518,469 solutions to the puzzle. Here's the first one:

If you'd like the full C++ source: Go here.

GDC Online 2011

I haven't done a speaking engagement since LOGIN 2009, but I really enjoyed it, so I figured it was high time to give it another shot.

(And no, acting out Beyoncé's Single Ladies dance on stage at the Developer War Stories panel of Fan Faire 2011 doesn't count.)

I've always enjoyed attending GDC Online (formerly GDC Austin or Austin Game Developers' Conference) and since it has always catered to a large crowd of online game developers (and I do miss Austin a bit), it's as good as any a place to foist my shenanigans on the somnolent audience.

This year I'll be talking about the trials and tribulations of taking a square peg never designed for streaming, EverQuest II and inserting it into a round hole. If you've read this blog, I've mentioned things about this before, but this is your opportunity to see the veil ripped away and the nitty-gritty of the good and bad choices that were made.

If you're heading to GDC Online (and you should for this lecture alone!), click here to see the lecture in their Schedule Builder.

Also (and completely to my surprise), Gamasutra listed my lecture as a 'highlight' of GDC Online. Fortunately they don't know me that well yet. ;D

Philosophy of Code

Programming in a business environment requires creating a product or service that is intended to produce a higher profit than cost. However, I believe that few programmers understand this or think about it on a daily basis. At the end of the day, we must be working towards making a profit.

I'll be the first to tell you that I'm not a business major. I'm not an economist. I love programming and was best friends with a keyboard in the third grade. I can write code like the dickens but I'm no Wizard of Business. However, throughout the past year working on Clone Wars Adventures I've had time (while my code is compiling) and inclination to reflect on the nature of programming in a business environment.

I've basically come to the conclusion that programming is a balance of three distinct yet intertwined facets: Developer Efficiency, Code Correctness and Performance. I call this the Philosophy of Code:

Performance - How quickly the code executes.
Developer Efficiency - How quickly developers are able to complete tasks.
Code Correctness - Adherence to best practices (avoiding global memory, avoiding macros, namespaces, templates, etc.).

These three aspects are not necessarily mutually exclusive. Every programming task that we work on has some balance of the above. However, when evaluating this philosophy from a business perspective, I've come to believe that the most important element of the triad is Developer Efficiency. Developing a Philosophy of Code that puts emphasis on Developer Efficiency will allow your programmers (and incidentally your entire development team) to work faster and smarter. It can also require less code to be written and fewer bugs.

Mutual Exclusivity
In some cases, an Efficiency-based Philosophy of Code will compromise the Performance and Code Correctness aspects. For instance, EverQuest II has a console-variable system. With one line of code in an implementation file I can add a semi-constant: a named value that can be changed by typing a slash-command into the chat window:

CV_FLOAT(max_radius, 30.0);

Presto. This is like saying float max_radius = 30.0; but I can also change it in real-time by typing "/max_radius 25" into the chat window. This typically is frowned upon from Code Correctness aspects for a few reasons:

• It uses macros
• It uses global memory
• It causes code to execute before main()

If your Philosophy of Code leans towards Code Correctness, doing it the Right Way™ would entail at least:

• Creating a manager object as a member of your application manager class
  
• Writing explicit code to register a member of your class with the manager object
• Writing explicit code to unregister that member when your class instance is destroyed
• A lot more than one line of code
  

Leaning towards Code Correctness over Developer Efficiency in this case would require that your programmers spend more time writing code and compiling (since members are typically declared in header files) to accomplish a very simple task.

Compile Times
In some cases, Code Correctness philosophies can institute policies that work to the detriment of Developer Efficiency:

• Extensive use of templates
• Excessive class declarations
• Lack of forward declarations

Excessive templatization typically means that header files are included in more places and more code is written in header files. When header files are changed, they require more of the code to be rebuilt. More code written in header files can also contribute to longer link times.

Time spent compiling and linking can't necessarily be taken at face value. As programmers wait for a rebuild they tend to do something else which probably takes longer than the rebuild. The shorter the rebuild time, the more likely the programmer is going to stay focused. From a Developer Efficiency perspective, it's in your best interest to keep compile times as low as possible.

Code Bloat
The less code that is required to perform a task, the more efficiently a developer can implement said code. I'll give another practical example from EverQuest II. I've previously mentioned a bit about how the designer data system works. Every server-side data file uses the same data format. As such, no special code is required to load each type of file. Weapons, quests, characters, everything is all defined by the same generic data description language. To load data from any data file uses a simple interface:

DataObject* pObject = DataLoader::Load("weapons/sword_of_awesomesauce");
if (pObject->IsA("Weapon"))
{
  String name = pObject->GetField("Name").AsString();
}

Due to data object inheritance, pObject may actually be a Sword, but inherits from Weapon. The server's object model is further generified so that instantiating any object requires just providing the type:

Item* pItem = ObjectFactory::Spawn(Item::Type, "weapons/sword_of_awesomesauce");
if (pItem && pItem->IsA(Weapon::Type))
{
 // Successfully spawned and is actually a Weapon.
}

In other words, there is very little code that needs to be written to add a new game object type.

Conclusion
Programmers should consider their Philosophy of Code. I believe that focusing on Developer Efficiency in a business setting makes the most sense given the deadlines, the complexity of the tasks at hand, and the goal to make a profit.

Debugging information cannot be found? No Problem!

In my last post, I discussed the frustrations of Visual Studio 2005 (and later versions) not being able to locate debugging information, even though it was present and fully usable by other tools.

I believe I have discovered a workaround that works nearly all the time: Remote Debugging.

It turns out that running the Remote Debugging Monitor on the same machine and setting up the project to use Remote Debugging seems to work around whatever issue Visual Studio is experiencing.

Remote Debugging is really useful if another machine is experiencing a problem that you can't reproduce locally. The Remote Debugging Monitor is primarily intended to run on a different machine than Visual Studio, but can also run on the same machine.

Here is how to set up Remote Debugging:

1. Generally, the machine running the Remote Debugging Monitor will need the files. These are found under the Visual Studio install location: C:\Program Files (x86)\Microsoft Visual Studio 8\Common7\IDE\Remote Debugger\x86 (for 32-bit) or C:\Program Files\Microsoft Visual Studio 8\Common7\IDE\Remote Debugger\x64 (for 64-bit).
2. Copy the files from the above directory to the machine that will run the Remote Debugging Monitor (skip if you are running the Monitor locally).
3. To start the Remote Debugging Monitor, run msvsmon.exe. If you are running locally, there should be shortcuts in the start menu:
   
4. Configure the options if necessary. Take note of 'Server name'.
   
   
5. Configure your project to do Remote Debugging. Change the 'Debugger to launch' to 'Remote Windows Debugger'. The 'Remote Server Name' must match the 'Server name' configured above if using Windows Authentication. If you are running the Monitor on a remote machine, the Remote Command and Working Directory will be paths on the remote machine.
   

When you Start Debugging, Step Into or Step Over to start debugging the application, Visual Studio will now connect to the Remote Debugging Monitor. You should be able to verify this by looking at the Remote Debugging Monitor and seeing how many connections it has.

So far this appears (for me at least) to be a successful work around to the 'Debugging information for 'X.exe' cannot be found or does not match. No symbols loaded.' error message. There have only been about two times in the past month where a problem occurred. In those cases, a restart of Visual Studio (and killing mspdbsrv.exe) fixed it.

Please let me know if this worked for you!

The (current) Bane of my Existence

Yes, Microsoft Visual Studio 2005, I'm looking at you.

Whenever I try to run the Clone Wars Adventures AdminClient in the debugger, I have about an 80% chance of seeing this:

This is a debug build. I most assuredly have debug symbols turned on:

And I'm not the only one to ever have this problem. People have also reported this problem on VS2008.

Oddly enough, no one else on my team has been complaining about this problem. When I start VS2005, I can generally run the client in debug once or twice and then I perpetually get this error.

Sometimes, exiting VS2005 and killing mspdbsrv.exe followed by a restart of VS2005 usually allows me to run a couple more times. However, with our huge solution (112 projects), this takes a few minutes or so. Definitely not conducive to small changes.

Some of the links above have responses from MS folks who state that they aren't able to reproduce the problem, but there is most definitely a problem.

I've only experienced this problem on our internal AdminClient, which, unfortunately, is the project that I'm most often trying to run. Other projects in the solution file seem to work just fine. I've tried several suggestions from the above links, including others like replacing dbghelp.dll with the latest version, altering the symbol search paths, trying to manually load symbols, and so on.

As a last-ditch effort, some of the links above suggest re-installing VS2005. I'll give that a shot.

If that doesn't work, I may have to become a Pirate or something.

Update: (3/23/2011): I believe I have found a work-around by using the Remote Debugging Monitor. More info in this post.