The Endeavour delay: Complexity, the APU, and the Load Control Assembly

The last launch of the Endeavour space shuttle has been delayed 48 hours (update: indefinitely) due to a problem with the APU heater and the Load Control Assembly. I wanted to find out what exactly these troublesome components are, so I did some investigation. There's a lot of extremely detailed information on the Space Shuttle available online, but it is very hard to find. I've summarized the information here in case anyone else wants to know the specifics.

The Space Shuttle has three independent hydraulic systems to operate engine valves, actuators, landing gear, and so forth during launch and landing. The hydraulic pumps are powered by three Auxiliary Power Units (or APUs), which are hydrazine-powered turbines. Each APU is 88 pounds and produces 135 horsepower (which is about the same horsepower as a Honda Accord).

Hydrazine is a highly-toxic rocket fuel; when exposed to a catalyst, it energetically decomposes into hot gases at 1700°F. It is convenient for applications such as the APU, since it doesn't need oxygen, and the decomposition can be easily started and stopped.

(Click on the image for tons of detailed information.)

Apparently the fuel heaters in APU 1 are not working. Since the hydrazine fuel will freeze at 34°F, each APU has redundant heaters to keep the system above 45°F. Since the heaters are redundant, the Space Shuttle would still be able to operate with the current problem, but would not be able to handle another failure. If the second fuel heater failed, then the fuel would freeze and the APU would not be able to work. Since there are three APUs, even this failure would not be a major problem. But still, you wouldn't want to take off with the heater not working, because losing hydraulic pressure would be a very bad thing.

According to articles, the fuel heater problem is due to a lack of power from the Aft Cabin Load Control Assembly, a switchbox that powers a heater circuit for Auxiliary Power Unit 1. There are three Aft Load Controller Assemblies, as well as many other Load Controller Assemblies. (Sources are inconsistent about whether it is called a Control vs Controller.)

A complex Electrical Power System provides power to all parts of the Shuttle. Three fuel cells (10 kW each) generate 28-volt direct current. The fuel cells feed three main DC power buses, as well as powering AC inverters to feed three AC buses with three-phase, 117-volt, 400-hertz AC power. From the fuel cell, power goes to a Distribution Assembly (DA), then to the aft Power Controller Assemblies, and then to the Aft Load Controller Assemblies.

The Load Control Assemblies contain solid-state switching devices for loads up to 20 amps, and relays for loads up to 135 amps. These switching devices are internally fused.

Reportedly there is a short or other electrical fault in the Aft Load Controller Assembly 2, which is causing the APU heater to fail to operate. The fuel is being drained from Endeavour so technicians can access the assembly and resolve the problem. If I'm interpreting everything correctly, it seems like they'll need to replace one of the internal fuses in the Load Control Assembly.

Complexity and the Space Shuttle

One amazing thing about the Space Shuttle is the layers and layers of complexity. The APU system is just one example of this. For instance, each APU has as lube oil system to keep it lubricated. This requires a lube oil pump, which requires a nitrogen pressurization system to start the pump in zero gravity. The oil also requires a 181-pound water spray boiler system, which sprays cooling water onto the oil pipes; the water boils into steam and is vented into space. The boiler requires controllers, panel switches, and status displays, as well as yet another nitrogen pressurization tank, and yet another system of heaters to keep the water from freezing.

The water spray boiler doesn't have anything to do with the current launch delay, other than being part of the APU, but it provides an interesting example of the complexity of the systems involved. To summarize the complexity along just this one path, the engines require hydraulic pressure, which requires APUs to power the hydraulic pumps, which require a lubricating oil system, which requires a complex boiler system, which requires a own control and monitoring system. And this is just one small sub-path! I'm ignoring equally complex systems such as the APU injector cooling system (more water and pressurized nitrogen), or the APU fuel pump (which for instance, has a catch bottle in case its seals leak, a drain port if the catch bottle overflows, and associated monitoring system).

Conclusion

Given the level of complexity of the Space Shuttle, I'm not surprised by the launch delays, and wish NASA the best of luck in resolving the problem promptly. My opinion is while the Space Shuttle is a marvel of engineering, simpler rocket systems such as the SpaceX Falcon will turn out to be more practical in the long run.

The images and much of the information above is from the 1988 Shuttle Reference Manual at shuttlepresskit.com. This manual goes into extreme detail and is very interesting (if you find this sort of thing interesting). I should probably make it clear that this posting is based on what I've read; I have no connection with the space program.

P.S. I've found extensive details on the LCA and launch issues are available at nasaspaceflight.com, e.g. Endeavour receives her new LCA – Blown driver examined.

Solving a math problem of Schrödinger (Part II)

What's the better way to solve a math problem? A few lines of code, or a bunch of mathematical thought? I wanted to solve the following math problem: how many 12-digit numbers can you make from the digits 1 through 5 if each digit must appear at least once. In Part I, I described how to use Python or Arc to solve this problem. Now, in the eagerly-awaited Part II, I'll describe how to solve it using Exponential Generating Functions. This turned out to involve more mathematics than I expected, although it's mostly just algebra.

The exponential generating function solution

My old combinatorics textbook describes how to solve all sorts of combinatorial problems. Section 3.2.13 has a somewhat similar sequence problem: how many sequences of 1,2, or 3 of length l, in which no symbol occurs exactly p times. This approach can be generalized to the problem we're solving.

For our specific problem, we want to exclude solutions where a digit appears 0 times, but we'll stick with the generalized approach of excluding solutions where a digit appears exactly p times, and then we'll set p to 0 later. We'll let d be the range of each digit (e.g. if the digits are 1 through 5, then d=1). And n will be the total number of digits in the sequence (e.g. n=12 in our original problem).

Generating functions are way too complex to explain here, but I'll try to give a quick overview. The idea is that if you have c things of size n, you represent this by cx^n. For instance, if you roll a die, you can get 1 through 6, so the generating function would be x+x^2+x^3+x^4+x^5+x^6. If you roll a die twice, you would square that. If you want to figure out how many ways to roll a 9, you'd extract the coefficient of x^9 (which is represented as [x^9]). If you multiply out the polynomial, you'll find that the coefficient of x^9 is 4, corresponding to the 4 ways to roll a 9 (6+3, 5+4, 4+5, 3+6).

In these polynomials, x is just a placeholder, not a genuine variable; you never actually evaluate the polynomial. It's almost like magic the way the answer pops out of the formulas.

One source of more information on generating functions is Cut the knot: generating functions.

First, we create the generating function for a single digit, say 1. If the digit appears zero times, we represent it by term x^0. If it appears 1 time, we have x^1. If it appears twice, we have x^2/2!. (We divide by 2! because there are 2! equivalent ways the digit can appear twice.) Likewise, if it appears three times, we represent it by x^3/3!. We end up with x^0 + x^1 + x^2/2! + x^3/3! + x^4/4! + ... Now for the crazy part. This is the series expansion of e^x, so we replace this with e^x. Finally we subtract x^p/p!, which is the "forbidden" case. We end up with the generating function e^x - x^p/p!.

If we have d choices for each digit, we multiply together d copies of the generating function, which is of course raising it to the power of d:

To get our solution, if we want to find how many solutions are n digits long, we simply extract the coefficient of x^n/n! from the above generating function, and that gives us the value we want:

Next step: how do we evaluate the above? First, let's expand the right half using the standard binomial formula:

Now we'll take a quick detour through some generating function facts, which I will present without proof.

Important generating function facts

Extracting the coefficient of x^n in an exponential gives you:

Unless n=0. Then you're looking for the coefficient of x^n in 1. This is simply 1 if n=0, and 0 otherwise.

Or unless n<0. Then the result is 0.

Second important generating function fact: if you're looking for the coefficient of, say, x^9 in an expression multiplied by x^3, then you can look instead for the coefficient of x^6 in the expression, if you use the appropriate scaling:

Solving one term of the summation

Now let's extract our desired coefficient from one term of the summation.

If n<kp, then the coefficient is 0.

If d != k, then from the second important fact, the value is:

If k = d, then the exponential drops out and the value is 0 if n != kp (i.e. n != dp), and otherwise:

Putting the summation together

Let's first assume n != dp. Then we can skip the k=d term, and we get:

where limit = min(d-1, n/p) (or d-1 if p=0). This ensures that n-kp >=0.

On the other hand, if n = dp, then we need to handle the k=d term.

Note that if n=dp, then n-kp>0, so we don't need to add an extra upper limit on k.

Solving the original problem

In the original problem, no value is allowed to appear zero times, so the forbidden count p=0. Then the solution simplifies to

Thus, the number of sequences of length 12 consisting of the digits 1 through 5, with each digit appearing at least once, is given by n=12 and d=5:

Happily, this is the same result we got in Part I.

Implementing this in Python

Implementing the above formula is straightforward:

from math import factorial

def solve(d, n, p):
  total = 0
  for k in range(0, d):
    if n-k*p < 0: break
    total += (pow(-1, k) * choose(d, k) *
              factorial(n) / factorial(n-k*p) *
              pow(d-k, n-k*p) / pow(factorial(p), k))
  if n == d*p:
    total += pow(-1, d) * factorial(n) / pow(factorial(p), d)
  return total

Since I didn't entirely trust the mathematics above, I also implemented a totally brute-force solution that generates and tests all the sequences of the given length:

import itertools

def bruteforce(d, n, p):
  total = 0
  for seq in itertools.product(range(0, d), repeat=n):
    ok = 1
    for i in range(0, d):
      if len([x for x in seq if x==i]) == p:
        ok = 0
        break
    total += ok
  return total

The mathematical solution and the brute force solution agree on the cases I tested, which increased my confidence that I didn't mess up the math. The brute force solution is, of course, too slow to use except for fairly small values.

Conclusion

The mathematical solution involved more mathematics than I was expecting. The resulting solution isn't quite as clean as I'd hoped, due to various corner cases that need to be handled. But it can be implemented fairly easily, and also lets us solve a more general problem than the original problem.

IPv6 web serving with Arc or Python: adventures in IPv6

I've been experimenting with IPv6 on my home network. In part 1, I described how I set up an IPv6 tunnel on Windows 7 and how IPv6 killed my computer. Now, I will describe how I set up a simple (i.e. trivial) IPv6 web server using Arc or Python, on Windows or Linux, which can be accessed at http://ipv6.nlanguages.com.

My IPv6 explorations are roughly driven by Hurricane Electric's IPv6 Certification levels. To get from "Newbie" to "Enthusiast" you have to have an IPv6 web server. I expected I could just use the web server you're viewing right now (provided through Pair), but Pair (like most web providers) doesn't support IPv6. So I figured I'd just set up my own simple web server.

To make things more interesting, I decided to set up the server on my Sheevaplug, a very small plug-based computer running Linux. (See my previous articles about Arc on the Sheevaplug, and Arduino with the Sheevaplug.) The things I describe will work just as well on a standard Linux or Windows box, though.

Setting up the SixXS IPv6 tunnel on the Sheevaplug was much easier than setting it up on Windows; I just followed the directions. One gotcha: if your clock is wrong, aiccu will silently fail - check /var/log/syslog.

IPv6 with the Python web server

Python comes with a simple web server. It is easy to configure the web server for IPv6 once you know how, but it took some effort to figure out how to do it.

import socket
from BaseHTTPServer import HTTPServer
from SimpleHTTPServer import SimpleHTTPRequestHandler

class MyHandler(SimpleHTTPRequestHandler):
  def do_GET(self):
    if self.path == '/ip':
      self.send_response(200)
      self.send_header('Content-type', 'text/html')
      self.end_headers()
      self.wfile.write('Your IP address is %s' % self.client_address[0])
      return
    else:
      return SimpleHTTPRequestHandler.do_GET(self)

class HTTPServerV6(HTTPServer):
  address_family = socket.AF_INET6

def main():
  server = HTTPServerV6(('::', 80), MyHandler)
  server.serve_forever()

if __name__ == '__main__':
  main()

Most of this code is standard Python SimpleHTTPServer code. It implements a handler for the path /ip, which returns the client's IP address. For other paths, SimpleHTTPRequestHandler returns a file from the current directory; this is not particulary secure, but works for a demonstration.

The key change to support IPv6 is subclassing HTTPServer and setting the address_family to IPv6. The other key change is starting the server with the name '::', which is the IPv6 equivalent of '', and binds to no specific address. Similar changes work with related Python classes such as SocketServer.

IPv6 with Arc's web server

My next adventure was to run Arc's web server (which I've documented here) on IPv6. Much to my surprise, Arc's web server worked on Windows with IPv6 without any trouble. You don't have to do anything different to serve on IPv6 and the code and logs handle IPv6 addresses as you'd expect. (Most of the credit for this should go to MzScheme/Racket, which provides the underlying socket implementation.)

I simply start a server thread on port 80, and then define a simple web operation on the home page (represented as || for obscure reasons).

arc> (thread (serve 80))
arc> (defop || req (pr "Welcome to Arc!  Your IP is " (req 'ip)))

Accessing this home page displays a message and the IP address of the client (IPv4 or IPv6 as appropriate).

Unfortunately, when I tried running the same Arc code on the Sheevaplug or another Linux box, it refused to work at all with IPv6. The problem turned out to be misconfiguration in the compilation of Racket (the new name for mzscheme). To get IPv6 working, you can recompile Racket following the instructions here. After recompiling, I was able to get Arc working on my Sheevaplug with IPv6. Eventually this fix will get into the official builds.

Note that implementing web pages in Arc requires much less boilerplate than in Python. This isn't too surprising, given that the primary application of Arc is web serving.

Putting the server's IPv6 address into DNS

Once you have an IPv6 web server, how do you access it? You can access a server with a raw IPv6 address: http://[2001:1938:81:1f8::2]/mypage. (Note that the IPv6 address is enclosed in square brackets, unlike a regular IP address.) However, you'll almost certainly want to access your IPv6 server through a domain name in DNS. To do this, you need to create an AAAA record in your domain zone file.

I had the domain name nlanguages.com available, and wanted to point it at my IPv6 web server. To do this, I went to the DNS Zone File Editor for my nameserver (godaddy.com in my case). I created one AAAA entry for host @ to point to my IPv6 address, and a second AAAA entry for host ipv6 to point to my IPv6 address. The @ provides an entry for my top-level domain (nlanguages.com), and the second provides an entry for ipv6.nlanguages.com. I then tested the DNS entries with a nslookup query, asking for the AAAA record: nslookup -q=aaaa nlanguages.com

The result is that http://ipv6.nlanguages.com will access my IPv6 server (if you have IPv6 access.)

Conclusion

Running a simple IPv6 web server in Python or Arc is straightforward, at least if you don't run into a problem with the underlying language implementation. Python requires just a couple additional lines to support IPv6, while Arc supports IPv6 automatically. Thus, you can easily set up an IPv6 web server, just in time for World IPv6 Day.

Solving a math problem of Schrödinger with Arc and Python

I recently received an interesting math problem: how many 12-digit numbers can you make from the digits 1 through 5 if each digit must appear at least once. The problem seemed trivial at first, but it turned out to be more interesting than I expected, so I'm writing it up here. I was told the problem is in a book of Schrodinger's, but I don't know any more details of its origin.

(The problem came to me via Aardvark (vark.com), which is a service where you can send questions to random people, and random people send you questions. Aardvark tries to match up questions with people who may know the answer. I find it interesting to see the questions I receive.)

The brute force solution

I didn't see any obvious solution to the problem, so I figured I'd first use brute force. I didn't use the totally brute force solution - enumerating all 12 digit sequences and counting the valid ones - since it would be pretty slow, so I took a slightly less brute force approach.

If 1 appears a times, 2 appears b times, and 3, 4, and 5 appear c, d, and e times, then the total number of possibilities is 12!/(a!b!c!d!e!) - i.e. the multinomial coeffient.

Then we just need to sum across all the different combinations of a through e. a has to be at least 1, and can be at most 8 (in order to leave room for the other 4 digits). Then b has to be at least 1 and at most 9-a, and so on. Finally, e is whatever is left over.

The Python code is straightforward, noting that range(1, 9) counts from 1 to 8:

from math import factorial
total = 0
for a in range(1, 8+1):
  for b in range(1, 9-a+1):
    for c in range(1, 10-a-b+1):
      for d in range(1, 11-a-b-c+1):
        e = 12-a-b-c-d
        total += (factorial(12) / factorial(a) / factorial(b)
          / factorial(c) / factorial(d) / factorial(e))
print total

Or, in Arc:

(def factorial (n)
  (if (<= n 1) 1
     (* n (factorial (- n 1)))))

(let total 0
  (for a 1 8
    (for b 1 (- 9 a)
      (for c 1 (- 10 a b)
        (for d 1 (- 11 a b c)
          (let e (- 12 a b c d)
            (++ total (/ (factorial 12) (factorial a) (factorial b)
              (factorial c) (factorial d) (factorial e))))))))
  total)

Either way, we quickly get the answer 165528000.

The generalized brute force solution

The above solution is somewhat unsatisfying, since if we want to know how many 11 digits numbers can be made from at least one of 1 through 6, for instance, there's no easy way to generalize the code.

We can improve the solution by writing code to generate the vectors of arbitrary digits and length. In Python, we can use yield, which magically gives us the vectors one at a time. The vecs function recursively generates the vectors that sum to <= t. The solve routine adds the last entry in the vector to make the sum exactly equal the length. My multinomial function is perhaps overly fancy, using reduce to compute the factorials of all the denominator terms and multiply them together in one go.

from math import factorial

# Generate vectors of digits of length n with sum <= t, and minimum digit 1.
def vecs(n, t):
  if n <= 0:
    yield []
  else:
    for vec in vecs(n-1, t-1):
      for last in range(1, t - sum(vec) + 1):
        yield vec + [last]

def multinomial(n, ks):
  return factorial(n) / reduce(lambda prod, k: prod * factorial(k), ks, 1)
  
# Find number of sequences of digits 1 to n, of length len,
# with each digit appearing at least once
def solve(n, len):
  total = 0
  for vec0 in vecs(n-1, len-1):
    # Make the vector of length n summing exactly to len
    vec = vec0 + [len - sum(vec0)]
    total += multinomial(len, vec)
  return total

Now, solve(5, 12) solves the original problem, and we can easily solve related problems.

In Arc, doing yield would need some crazy continuation code, so I just accumulate the list of vectors with accum and then process it. The code is otherwise similar to the Python code:

(def vecs (n t)
  (if (<= n 0) '(())
    (accum accfn
      (each vec (vecs (- n 1) (- t 1))
       (for last 1 (- t (reduce + vec))
          (accfn (cons last vec)))))))

(def multinomial (n ks)
  (/ (factorial n) (reduce * (map factorial ks))))

(def solve (n len)
  (let total 0
    (each vec0 (vecs (- n 1) (- len 1))
        (++ total (multinomial len
                    (cons (- len (reduce + vec0)) vec0))))
    total))

This solution will solve our original problem quickly, but in general it's exponential, so solving something like n = 10 and length = 30 gets pretty slow.

The dynamic programming solution

By thinking about the problem a bit more, we can come up with a simpler solution. Let's take all the sequences of 1 through 5 of length 12 with each number appearing at least once, and call this value S(5, 12). How can we recursively find this value? Well, take a sequence and look at the last digit, say 5. Either 5 appears in the first 11 digits, or it doesn't. In the first case, the first 11 digits form a sequence of 1 through 5 of length 11 with each number appearing at least once. In the second case, the first 11 digits form a sequence of 1 through 4 of length 11 with each number appearing at least once. So we have S(5, 11) sequences of the first case, and S(4, 11) of the second case. We assumed the last digit was a 5, but everything works the same if it was a 1, 2, 3, or 4; there are 5 possibilities for the last digit.

The above shows that S(5, 12) = 5 * (S(5, 11) + S(4, 11)). In general, we have the nice recurrence S(n, len) = n * (S(n, len-1) + S(n-1, len-1)). Also, if you only have a single digit, there's only one solution, so S(1, len) = 1. And if you have more digits than length to put them in, there are clearly no solutions, so S(n, len) = 0 if n > len. We can code this up in a nice recursive solution with memoization:

memo = {}
def solve1(digits, length):
  if memo.has_key((digits, length)):
    return memo[(digits, length)]
  if digits > length:
    result = 0
  elif digits == 1:
    result = 1
  else:
    result = digits * (solve1(digits-1, length-1) + solve1(digits, length-1))
  memo[(digits, length)] = result
  return result

An interesting thing about this solution is it breaks down each function call into two simpler function calls. Each of these turns into two simpler function calls, and so forth, until it reaches the base case. This results in an exponential number of function calls. This isn't too bad for solving the original problem of length 12, but the run time rapidly gets way too slow.

Note that the actual number of different function evaluations is pretty small, but the same ones keep getting evaluated over and over exponentially often. The traditional way of fixing this is to use dynamic programming. In this approach, the structure of the algorithm is examined and each value is calculated just one, using previously-calculated values. In our case, we can evaluate S(1, 0), S(2, 0), S(3, 0), and so on. Then evaluate S(2, 1), S(2, 2), S(2, 3) using those values. Then evaluate S(3, 2), S(3, 3), and so on. Note that each evaluation only uses values that have already been calculated. For an introduction to dynamic programming, see Dynamic Programming Zoo Tour.

Rather than carefully looping over the sub-problems in the right order to implement a dynamic programming solution, it is much easier to just use memoization. The trick here is once a subproblem is solved, store the answer. If we need the answer again, just use the stored answer rather than recomputing it. Memoization is a huge performance win. Without memoization solve1(10, 30) takes about 15 seconds, and with it, the solution is almost immediate. (solve1 10 35) takes about 80 seconds.

The Arc implementation is nice, because defmemo creates a function that is automatically memoized.

(defmemo solve1 (digits length)
  (if (> digits length) 0
      (is digits 1) 1
      (* digits (+ (solve1 (- digits 1) (- length 1))
                   (solve1 digits (- length 1))))))

A faster dynamic programming solution

When trying to count the number of things satisfying a condition, it's often easier to figure out how many don't satisfy the condition. We can apply that strategy to this problem. The total number of 12-digit sequences made from 1 through 5 is obviously 5^12. We can just subtract the number of sequences that are missing one or more digits, and we get the answer we want.

How many sequences are missing 1 digit? S(4, 12) is the number of sequences containing at least one of 1 through 4, and by definition missing the digit 5. Of course, we need to consider sequences missing 4, 3, 2, or 1 as well. Likewise, there are S(4, 12) of each of these, so 5 * S(4, 12) sequences missing exactly one digit.

Next, sequences missing exactly 2 of the digits 1 through 5. S(3, 12) is the number of sequences containing at least one of 1 through 3, so they are missing 4 and 5. But we must also consider sequences missing 1 and 2, 1 and 3, and so on. There are 5 choose 2 pairs of digits that can be missing. Thus in total, (5 choose 2) * S(3, 12) sequences are missing exactly 2 of the digits.

Likewise, the number of sequences missing exactly 3 digits is (5 choose 3) * S(2, 12). The number of sequences missing exactly 4 digits is (5 choose 4) * S(1, 12). And obviously there are no sequences missing 5 digits.

Thus, we get the recurrence S(5, 12) = 5^12 - 5*S(4, 12) - 10*S(3, 12) - 10*S(2, 12) - 5*S(1, 12)

In general, we get the recurrence:

The same dynamic programming techniques and memoization can be applied to this. Note that the subproblems all have the same length, so there are many fewer subproblems than in the previous case. That is, instead of a 2-dimensional grid of subproblems, the subproblems are all in a single row.

In Python, the solution is:

memo = {}
def solve2(digits, length):
  if memo.has_key((digits, length)):
    return memo[(digits, length)]
  if digits > length:
    result = 0
  elif digits == 1:
    result = 1
  else:
    result = digits**length
    for i in range(1, digits):
      result -= sol2(i, length)*choose(digits, i)
  memo[(digits, length)] = result
  return result

And in Arc, the solution is similar. Instead of looping, I'm using a map and reduce just for variety. That is, the square brackets define a function to compute the choose and solve term. This is mapped over the range 1 to digits-1. Then the results are summed with reduce. As before, defmemo is used to memoize the results.

(def choose (m n)
  (/ (factorial m) (factorial n) (factorial (- m n))))

(defmemo solve2 (digits length)
  (if (> digits length) 0
      (is digits 1) 1
      (- (expt digits length)
         (reduce +
           (map [* (choose digits _) (solve2 _ length)]
             (range 1 (- digits 1)))))))

The mathematical exponential generating function solution

At this point, I dug out my old combinatorics textbook to figure out how to solve this problem. By using exponential generating functions and a bunch of algebra, we obtain a fairly tidy answer to the original problem:

Since the mathematics required to obtain this answer is somewhat complicated, I've written it up separately in Part II.

Discussion

This problem turned out to be a lot more involved than I thought. It gave me the opportunity to try out some new things in Python and Arc, and make use of my fading knowledge of combinatorics and generating functions.

The Python and Arc code was pretty similar. Python's yield construct was convenient. Arc's automatic memoization was also handy. On the whole, both languages were about equally powerful in solving these problems.

Acknowledgement: equations created through CodeCogs' equation editor

IPv6 killed my computer: Adventures in IPv6

You may have heard that the Internet is running out of IP addresses and disaster will strike unless everyone switches over to IPv6. This may be overhyped, since civilization continues even though the last block of addresses was given out on February 3, 2011.

However, with World IPv6 Day fast approaching (June 8), I figured this was a good time to try out IPv6 on my home network. I was also motivated by Hurricane Electric's IPv6 Certification (which is a "fun and educational" certification, not a "study thick books of trivia" certification).

This article describes my efforts to run IPv6 on my Windows 7 64-bit machine, and future articles will describe other IPv6 adventures.

IPv6 tunnels

If your ISP provides IPv6, then using IPv6 is easy. Comcast, for instance, is rolling out some IPv6 support. Unfortunately, AT&T (which I have) doesn't provide IPv6 and is lagging other providers in their future IPv6 plans.

The alternative is an IPv6 tunnel, which lets your computer connect to IPv6 sites over a normal IP connection. The number of different IPv6 tunnel mechanisms is very confusing: 6to4, Teredo, AYIYA, and 6in4, to name a few.

A Hacker News thread recommended Hurricane Electric's free tunnel, so I tried that. Unfortunately that tunnel requires IP protocol 41, and I quickly found that my 2Wire AT&T router inconveniently blocks protocol 41.

SixXS IPv6 tunnel on Windows 7 64-bit

Next, I tried SixXS's free IPv6 tunnel service, which doesn't require protocol 41 and promises IPv6 in 10 easy steps. This went well until Step 5, and then things got complicated.

This section gets into the gory details of setting up the tunnel; it's only to help people who are actually setting up a tunnel, and can be ignored by most readers :-)

Eventually I figured that for Windows 7 64-bit, you should ignore most of the 10 easy steps. Instead, get the Tap driver by installing OpenVPN according to the Vista64 instructions. Then go to the Vista instructions and follow all the mysterious steps including the obscure Vista parameter setup commands. Finally, use the AICCU command line, not the GUI.

If you encounter these errors, you're probably using the wrong Tap driver:

tapinstall.exe failed.
[warning] Error opening registry key: SYSTEM\CurrentControlSet\Control\Class\{4D
36E972-E325-11CE-BFC1-08002BE10318}\Properties (t1)
[warning] Found = 0, Count = 0
[error] [tun-start] TAP-Win32 Adapter not configured properly...

Finally, I was able to get my tunnel running with aiccu-2008-03-15-windows-console.exe start.

Once I had the tunnel running, my computer had an IPv6 address, it could talk to other IPv6 addresses, and my computer could be accessed via IPv6.

So now that I have IPv6 running on my computer, what can I do with it? Well, that's one of the problems. There isn't a whole lot you can do with IPv6 that you couldn't do before. You can connect to ipv6.google.com. You can see the animated kame turtle instead of the static turtle. You can see your IPv6 address at whatismyipv6address.com. But there's no IPv6 killer app.

Overall, the immediate benefit of running IPv6 is pretty minimal, which I think is a big barrier to adoption. As I discussed in a surprisingly popular blog post, the chance of adoption of a new technology depends on the ratio of perceived crisis to perceived pain of adoption. Given a high level of pain to run IPv6 and a very low benefit - any potential crisis is really someone else's crisis - I expect the rate of adoption to be very slow until people are forced to switch.

Getting IPv6 running reminds me a lot of TCP/IP circa 1992, when using TCP/IP required a lot of configuration, tunneling (over a serial line) with SLIP, and using immature software stacks such as Winsock. And most of what you wanted to do back then didn't even need TCP/IP. It will be interesting to see how long it takes IPv6 to get to the point where it just works and nobody needs to think about it. (None of this is meant as a criticism of SixXS or Hurricane Electric, by the way, who are providing useful free services. AT&T on the other hand...)

Running IPv6 did let me gain another level in the Hurricane Electric certification, though.

IPv6 kills my computer

The day after setting up IPv6, I turned on my computer. The power light came on, and that was all, no Windows, no BIOS screen, and not even a startup beep. I tried a different monitor with no luck. I opened up the computer, re-seated the memory modules, and poked at anything else that might be loose. I powered up my system again, and everything worked, fortunately enough.

The pedant might insist that IPv6 didn't kill my computer since any IPv6 issues wouldn't show up until after the OS boots, and IPv6 couldn't possibly have stopped my computer from even booting to the BIOS. However, I remain suspicious. Just a coincidence that I set up IPv6 and my computer dies? I don't think so. What about the rest of you? Anyone's computer get killed by IPv6?

Sheevaplug as IPv6 router

A few weeks later, I decided to try using my Sheevaplug as an IPv6 router for my home network, so all my machines could access IPv6 through my Sixxs tunnel. Although I used a Sheevaplug, these steps should work for other Linux systems too. The following are the gory details in the hope that they may be helpful to someone.

I started with the page Sixxs Sheevaplug, which describes how to set up the Sheevaplug with IPv6. Unfortunately, it didn't quite work. It suggests using a program called ufw, which stands for Uncomplicated FireWall. Unfortunately, I found it to be anything but uncomplicated. The first problem was that the default ufw version 0.29 didn't work for me - it failed to create the necessary chains with the inconvenient side-effect of blocking all ports; version 0.30 avoids this problem. I ended up using ip6tables directly, which was much easier - see instructions here.

The steps I took to setting up the Sheevaplug:

• Request a subnet from Sixxs. In the examples below, I use: 2001:1938:2a9::/48. Important: use your subnet, not mine.
• aiccu start to start the tunnel
• sysctl -w net.ipv6.conf.all.forwarding=1 to enable IPv6 routing.
• Configure /etc/radvd.conf as follows:

  interface eth0
  {
   AdvSendAdvert on;
   AdvLinkMTU 1280;
   prefix 2001:1938:2a9::/64
   {
                 AdvOnLink on;
                 AdvAutonomous on;
   };
  };
  

  Note that your subnet is /48, but you need to use /64 in the file.
• ip -6 ro add 2001:1938:2a9::/48 dev lo
• ip -6 add add 2001:1938:2a9::1/64 dev eth0
  I'm not sure why adding that address is necessary, but routing just doesn't work without it.
• service radvd start
  radvd is the Router Advertisement Daemon, which lets other computers on your network know about your IPv6 tunnel.

At this point, you should be able to start up a Windows box, and it will automatically get an IPv6 address on the subnet. You should then be able to access ipv6.google.com or ip6.me.

Debugging: if the IPv6 subnet doesn't work, many things can be wrong. First, make sure your host machine can access IPv6. Assuming your client machine runs Windows, you can do "ping -6 ipv6.google.com" or "tracert -6 ipv6.google.com". With "ipconfig /all" you should see a "Temporary IPv6 Address" on the subnet, and a "Default Gateway" pointing at your Sheevaplug. If tracert gets one step and then hangs, try disabling your firewall on the Sheevaplug. If these tips don't work, then I guess you'll end up spending hours with tcpdump like I did :-(

Also read Part 2: IPv6 Web Serving with Arc or Python.

Solving edge-match puzzles with Arc and backtracking

I recently saw a tricky nine piece puzzle and wondered if I could use Arc to solve it. It turned out to be straightforward to solve using standard backtracking methods. This article describes how to solve the puzzle using the Arc language.

The puzzle consists of nine square titles. The tiles must be placed so the pictures match up where two tiles meet. As the picture says, "Easy to play, but hard to solve." It turns out that this type of puzzle is called an edge-matching puzzle, and is NP-complete in general. For dozens of examples of these puzzles, see Rob's Puzzle Page.

Backtracking is a standard AI technique to find a solution to a problem step by step. If you reach a point where a solution is impossible, you backtrack a step and try the next possibility. Eventually, you will find all possible solutions. Backtracking is more efficient than brute-force testing of all possible solutions because you abandon unfruitful paths quickly.

To solve the puzzle by backtracking, we put down the first tile in the upper left. We then try a second tile in the upper middle. If it matches, we put it there. Then we try a third tile in the upper right. If it matches, we put it there. The process continues until a tile doesn't match, and then the algorithm backtracks. For instance, if the third tile doesn't match, we try a different third tile and continue. Eventually, after trying all possible third tiles, we backtrack and try a different second tile. And after trying all possible second tiles, we'll backtrack and try a new first tile. Thus, the algorithm will reach all possible solutions, but avoids investigating arrangements that can't possibly work.

The implementation

I represent each tile with four numbers indicating the pictures on each side. I give a praying mantis the number 1, a beetle 2, a dragonfly 3, and an ant 4. For the tail of the insect, I give it a negative value. Each tile is then a list of (top left right bottom). For instance, the upper-left tile is (2 1 -3 3). With this representation, tiles match if the value on one edge is the negative of the value on the other edge. I can then implement the list of tiles:

(with (mantis 1 beetle 2 dragonfly 3 ant 4)
  (= tiles (list
    (list beetle mantis (- dragonfly) dragonfly)
    (list (- beetle) dragonfly mantis (- ant))
    (list ant (- mantis) beetle (- beetle))
    (list (- dragonfly) (- ant) ant mantis)
    (list ant (- beetle) (- dragonfly) mantis)
    (list beetle (- mantis) (- ant) dragonfly)
    (list (- ant) (- dragonfly) beetle (- mantis))
    (list (- beetle) ant mantis (- dragonfly))
    (list mantis beetle (- dragonfly) ant))))

Next, I create some helper functions to access the edges of a tile, convert the integer to a string, and to prettyprint the tiles.

;; Return top/left/right/bottom entries of a tile
(def top (l) (l 0))
(def left (l) (l 1))
(def right (l) (l 2))
(def bottom (l) (l 3))

;; Convert an integer tile value to a displayable value
(def label (val)
  ((list "-ant" "-dgn" "-btl" "-man" "" " man" " btl" " dgn" " ant")
   (+ val 4)))

;; Print the tiles nicely
(def prettyprint (tiles (o w 3) (o h 3))
  (for y 0 (- h 1)
    (for part 0 4
      (for x 0 (- w 1)
        (withs (n (+ x (* y w)) tile (tiles n))
          (if
     (is part 0)
       (pr " ------------- ")
     (is part 1)
       (pr "|    " (label (top tile)) "     |")
     (is part 2)
       (pr "|" (label (left tile)) "    " (label (right tile)) " |")
     (is part 3)
       (pr "|    " (label (bottom tile)) "     |")
     (is part 4)
       (pr " ------------- "))))
      (prn))))

The prettyprint function uses optional arguments for width and height: (o w 3). This sets the width and height to 3 by default but allows it to be modified if desired. The part loop prints each tile row is printed as five lines. Now we can print out the starting tile set and verify that it matches the picture. I'll admit it's not extremely pretty, but it gets the job done:

arc> (prettyprint tiles)
 -------------  -------------  ------------- 
|     btl     ||    -btl     ||     ant     |
| man    -dgn || dgn     man ||-man     btl |
|     dgn     ||    -ant     ||    -btl     |
 -------------  -------------  ------------- 
 -------------  -------------  ------------- 
|    -dgn     ||     ant     ||     btl     |
|-ant     ant ||-btl    -dgn ||-man    -ant |
|     man     ||     man     ||     dgn     |
 -------------  -------------  ------------- 
 -------------  -------------  ------------- 
|    -ant     ||    -btl     ||     man     |
|-dgn     btl || ant     man || btl    -dgn |
|    -man     ||    -dgn     ||     ant     |
 -------------  -------------  ------------- 

Next is the meat of the solver. The first function is matches, which takes a grid of already-positioned tiles and a new tile, and tests if a particular edge of the new tile matches the existing tiles. (The grid is represented simply as a list of the tiles that have been put down so far.) This function is where all the annoying special cases get handled. First, the new tile may be along an edge, so there is nothing to match against. Second, the grid may not be filled in far enough for there to be anything to match against. Finally, if there is a grid tile to match against, and the value there is the negative of the new tile's value, then it matches. One interesting aspect of this function is that functions are passed in to it to select which edges (top/bottom/left/right) to match.

;; Test if one edge of a tile will fit into a grid of placed tiles successfully
;;  grid is the grid of placed tiles as a list of tiles e.g. ((1 3 4 2) nil (-1 2 -1 1) ...)
;;  gridedge is the edge of the grid cell to match (top/bottom/left/right)
;;  gridx is the x coordinate of the grid tile
;;  gridy is the y coordinate of the grid tile
;;  newedge is the edge of the new tile to match (top/bottom/left/right)
;;  newtile is the new tile e.g. (1 2 -1 -3)
;;  w is the width of the grid
;;  h is the height of the grid
(def matches (grid gridedge gridx gridy newedge newtile w h)
  (let n (+ gridx (* gridy w))
    (or
      (< gridx 0) ; nothing to left of tile to match, so matches by default
      (< gridy 0) ; tile is at top of grid, so matches
      (>= gridx w) ; tile is at right of grid, so matches
      (>= gridy h) ; tile is at bottom of grid, so matches
      (>= n (len grid)) ; beyond grid of tiles, so matches
      (no (grid n)) ; no tile placed in the grid at that position
      ; Finally, compare the two edges which should be opposite values
      (is (- (gridedge (grid n))) (newedge newtile)))))

With that method implemented, it's easy to test if a new tile will fit into the grid. We simply test that all four edges match against the existing grid. We don't need to worry about the edges of the puzzle, because the previous method handles them:

;; Test if a tile will fit into a grid of placed tiles successfully
;;   grid is the grid of tiles
;;   newtile is the tile to place into the grid
;;   (x, y) is the position to place the tile
(def is_okay (grid newtile x y w h)
    (and 
      (matches grid right (- x 1) y left newtile w h)
      (matches grid left (+ x 1) y right newtile w h)
      (matches grid top x (+ y 1) bottom newtile w h)
      (matches grid bottom x (- y 1) top newtile w h)))

Now we can implement the actual solver. The functions solve1 and try recursively call each other. solve1 calls try with each candidate tile in each possible orientation. If the tile fits, try updates the grid of placed tiles and calls solve1 to continue solving. Otherwise, the algorithm backtracks and solve1 tries the next possible tile. My main problem was accumulating all the solutions properly; on my first try, the solutions were wrapped in 9 layers of parentheses! One other thing to note is the conversion from a linear (0-8) position to an x/y grid position.

A couple refactorings are left as an exercise to the reader. The code to try all four rotations of the tile is a bit repetitive and could probably be cleaned up. More interesting would be to turn the backtracking solver into a general solver, with the puzzle just one instance of a problem.

;; grid is a list of tiles already placed
;; candidates is a list of tiles yet to be placed
;; nextpos is the next position to place a tile (0 to 8)
;; w and h are the dimensions of the puzzle
(def solve1 (grid candidates nextpos w h)
  (if
    (no candidates)
      (list grid) ; Success!
    (mappend idfn (accum addfn ; Collect results and flatten
      (each candidate candidates
        (addfn (try grid candidate (rem candidate candidates) nextpos w h))
        (addfn (try grid (rotate candidate) (rem candidate candidates) nextpos w h))
        (addfn (try grid (rotate (rotate candidate)) (rem candidate candidates) nextpos w h))
        (addfn (try grid (rotate (rotate (rotate candidate))) (rem candidate candidates) nextpos w h)))))))

; Helper to append elt to list
(def append (lst elt) (join lst (list elt)))

;; Try adding a candidate tile to the grid, and recurse if successful.
;; grid is a list of tiles already placed
;; candidate is the tile we are trying
;; candidates is a list of tiles yet to be placed (excluding candidate)
;; nextpos is the next position to place a tile (0 to 8)
;; w and h are the dimensions of the puzzle
(def try (grid candidate candidates nextpos w h)
  (if (is_okay grid candidate (mod nextpos w) (trunc (/ nextpos w)) w h)
    (solve1 (append grid candidate) candidates (+ nextpos 1) w h)))

The final step is a wrapper function to initialize the grid:

(def solve (tiles (o w 3) (o h 3))
  (solve1 nil tiles 0 w h))

With all these pieces, we can finally solve the problem, and obtain four solutions (just rotations of one solution):

arc> (solve tiles)
(((1 -2 -4 3) (2 4 1 -3) (4 -1 2 -2) (-3 1 4 -2) (3 -4 -1 2) (2 1 -3 3) (2 -4 -1 -3) (-2 1 4 -3) (-3 -4 4 1))
((2 4 -2 -1) (-3 2 3 1) (4 -3 1 -4) (1 2 -3 4) (-1 3 2 -4) (4 -2 -3 1) (-4 1 3 -2) (4 -3 -2 1) (-1 2 -3 -4))
((1 4 -4 -3) (-3 4 1 -2) (-3 -1 -4 2) (3 -3 1 2) (2 -1 -4 3) (-2 4 1 -3) (-2 2 -1 4) (-3 1 4 2) (3 -4 -2 1))
((-4 -3 2 -1) (1 -2 -3 4) (-2 3 1 -4) (1 -3 -2 4) (-4 2 3 -1) (4 -3 2 1) (-4 1 -3 4) (1 3 2 -3) (-1 -2 4 2)))
arc> (prettyprint (that 0))
 -------------  -------------  ------------- 
|     man     ||     btl     ||     ant     |
|-btl    -ant || ant     man ||-man     btl |
|     dgn     ||    -dgn     ||    -btl     |
 -------------  -------------  ------------- 
 -------------  -------------  ------------- 
|    -dgn     ||     dgn     ||     btl     |
| man     ant ||-ant    -man || man    -dgn |
|    -btl     ||     btl     ||     dgn     |
 -------------  -------------  ------------- 
 -------------  -------------  ------------- 
|     btl     ||    -btl     ||    -dgn     |
|-ant    -man || man     ant ||-ant     ant |
|    -dgn     ||    -dgn     ||     man     |
 -------------  -------------  ------------- 

I've used gimp on the original image to display the solution. I've labeled the original tiles A-I so you can see how the solution relates to the original image. Using Arc to display a solution as an image is left as an exercise to the reader :-) But seriously, this is where using a language with extensive libraries would be beneficial, such as Python's PIL imaging library.

Theoretical analysis

I'll take a quick look at the theory of the puzzle. The tiles can be placed in 9! (9 factorial) different locations, and each tile can be oriented 4 ways, for a total of 9! * 4^9 possible arrangements of the tiles, which is about 95 billion combinations. Clearly this puzzle is hard to solve by randomly trying tiles.

arc> (* (apply * (range 1 9)) (expt 4 9))
95126814720

We can do a back of the envelope calculation to see how many solutions we can expect. If you put the tiles down randomly, there are 12 edge constraints that must be satisfied. Since only one of the 8 possibilities matches, the chance of all the edges matching randomly is 1 in 8^12 or 68719476736. Dividing this into the 95 billion possible arrangements yields 1.38 solutions for an arbitrary random puzzle. (If this number were very large, then it would be hard to create a puzzle with only one solution.)

We can test this calculation experimentally by seeing how many solutions there are are for a random puzzle. First we make a function to create a random puzzle, consisting of 9 tiles, each with 4 random values. Then we solve 100 of these:

arc> (def randtiles ()
  (n-of 9 (n-of 4 (rand-elt '(1 2 3 4 -1 -2 -3 -4)))))
arc> (n-of 100 (len (solve (randtiles))))
(0 0 0 8 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 8 0 0 4 0
0 0 4 8 0 8 0 0 0 0 0 0 0 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 0
0 0 32 8 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 0 0 8 0 0 4 0 0 32)
arc> (apply + that)
196

Out of 100 random puzzles, there are 196 solutions, which is close to the 1.38 solutions per puzzle estimate above. (that is an obscure Arc variable that refers to the previous result.) Note that only 16% of the puzzles have solutions, though. Part of the explanation is that solutions always come in groups of 4, since the entire puzzle can be rotated 90 degrees into four different orientations. Solving 100 puzzles took 146 seconds, by the way.

Another interesting experiment is to add a counter to try to see how many tile combinations the solver actually tries. The result is 66384, which is much smaller than the 95 billion potential possibilities. This suggests that the puzzle is solvable manually by trial-and-error with backtracking; at a second per tile, it would probably take you 4.6 hours to get the first solution.

Conclusions

Solving the puzzle with Arc was easier than I expected, and I ran into only minor problems along the way. The code is available as puzzle.arc.

64-bit RC6 codes, Arduino, and Xbox remotes

I've extended my Arduino IRremote library to support RC6 codes up to 64 bits long. Now your Arduino can control your Xbox by acting as an IR remote control. (The previous version of my library only supported 32 bit codes, so it didn't work with the 36-bit Xbox codes.) Details of the IRremote library are here.

Note: I don't actually have an Xbox to test this code with, so please let me know if the code works for you.

Download

This code is in my "experimental" branch since I'd like to get some testing before releasing it to the world. To use it:

• Download the IRremote library zip file from GitHub from the Arduino-IRremote experimental branch.
• Unzip the download
• Move/rename the shirriff-Arduino-IRremote-nnnn directory to arduino-000nn/libraries/IRremote.

Sending an Xbox code

The following program simply turns the Xbox on, waits 10 seconds, turns it off, and repeats.

#include <IRremote.h>
IRsend irsend;
unsigned long long OnOff = 0xc800f740cLL;
int toggle = 0;

void sendOnOff() {
  if (toggle == 0) {
    irsend.sendRC6(OnOff, 36);
  } else {
    irsend.sendRC6(OnOff ^ 0x8000, 36);
  }
  toggle = 1 - toggle;
}
   
void setup() {}

void loop() {
  delay(10000);  // Wait 10 seconds
  sendOnOff();  // Send power signal
}

The first important thing to note is that the On/Off code is "unsigned long long", and the associated constant ends in "LL" to indicate that it is a long long. Because a regular long is only 32 bits, a 64-bit long long must be used to hold the 64 bit code. If you try using a regular long, you'll lose the top 4 bits ("C") from the code.

The second thing to notice is the toggle bit (which is explained in more detail below). Every time you send a RC5 or RC6 code, you must flip the toggle bit. Otherwise the receiver will ignore the code. If you want to send the code multiple times for reliability, don't flip the toggle bit until you're done.

Receiving an Xbox code

The following code will print a message on the serial console if it receives an Xbox power code. It will also dump the received value.

#include <IRremote.h>

int RECV_PIN = 11;
IRrecv irrecv(RECV_PIN);
decode_results results;

void setup()
{
  Serial.begin(9600);
  irrecv.enableIRIn(); // Start the receiver
}

void loop() {
  if (irrecv.decode(&results)) {
    if ((results.value & ~0x8000LL) == 0xc800f740cLL) {
      Serial.println("Got an OnOff code");
    }
    Serial.println(results.value >> 32, HEX);
    Serial.println(results.value, HEX);
    irrecv.resume(); // Receive the next value
  }
}

Two things to note in the above code. First, the received value is anded with ~0x8000LL; this clears out the toggle bit. Second, Serial.println is called twice, first to print the top 32 bits, and second to print the bottom 32 bits.

The output when sent power codes multiple times is:

Got an OnOff code
C
800FF40C
Got an OnOff code
C
800F740C
Got an OnOff code
C
...

Note that the received value is split between the two Serial.println calls. Also note that the output oscillates between ...F740C and ...FF40C as the sender flips the toggle bit. This is why the toggle bit must be cleared when looking for a particular value.

The IRremote/IRrecvDump example code has also been extended to display values up to 64 bits, and can be used for testing.

A quick description of RC6 codes

RC6 codes are somewhat more complicated than the usual IR code. They come in 20 or 36 bit varieties (that I know of). The code consists of a leader pulse, a start bit, and then the 20 (or 36) data bits. A 0 bit is sent as a space (off) followed by a mark (on), while a 1 bit is sent as a mark (on) followed by a space (off).

The first complication is the fourth data bit sent (called a trailer bit for some reason), is twice as long as the rest of the bits. The IRremote library handles this transparently.

The second complication is RC5 and RC6 codes use a "toggle bit" to distinguish between a button that is held down and a button that is pressed twice. While a button is held down, a code is sent. When the button is released and pressed a second time, a new code with one bit flipped is sent. On the third press, the original code is sent. When sending with the IRremote library, you must keep track of the toggle bit and flip it each time you send. When receiving with the IRremote library, you will receive one of two different codes, so you must clear out the toggle bit. (I would like the library to handle this transparently, but I haven't figured out a good way to do it.)

For details of the RC6 encoding with diagrams and timings, see SB projects.

The LIRC database

The LIRC project collects IR codes for many different remotes. If you want to use RC6 codes from LIRC, there a few things to know. A typical code is the Xbox360 file, excerpted below:

begin remote
  name  Microsoft_Xbox360
  bits           16
  flags RC6|CONST_LENGTH
  pre_data_bits   21
  pre_data       0x37FF0
  toggle_bit_mask 0x8000
  rc6_mask    0x100000000

      begin codes
          OpenClose                0x8BD7
          XboxFancyButton          0x0B9B
          OnOff                    0x8BF3
...

To use these RC6 code with the Arduino takes a bit of work. First, the codes have been split into 21 bits of pre-data, followed by 16 bits of data. So if you want the OnOff code, you need to concatenate the bits together, to get 37 bits: 0x37ff08bf3. The second factor is the Arduino library provides the first start bit automatically, so you only need to use 36 bits. The third issue is the LIRC files inconveniently have 0 and 1 bits swapped, so you'll need to invert the code. The result is the 36-bit code 0xc800f740c that can be used with the IRremote library.

The rc6_mask specifies which bit is the double-wide "trailer" bit, which is the fourth bit sent (both in 20 and 36 bit RC6 codes). The library handles this bit automatically, so you can ignore it.

The toggle_bit_mask is important, as it indicates which position needs to be toggled every other transmission. For example, to transmit OnOff you will send 0xc800f740c the first time, but the next time you will need to transmit 0xc800ff40c.

More details of the LIRC config file format are at WinLIRC.

Xbox codes

Based on the LIRC file, the following Xbox codes should work with my library:

OpenClose	0xc800f7428	XboxFancyButton	0xc800ff464	OnOff	0xc800f740c
Stop	0xc800ff419	Pause	0xc800f7418	Rewind	0xc800ff415
FastForward	0xc800f7414	Prev	0xc800ff41b	Next	0xc800f741a
Play	0xc800ff416	Display	0xc800f744f	Title	0xc800ff451
DVD_Menu	0xc800f7424	Back	0xc800ff423	Info	0xc800f740f
UpArrow	0xc800ff41e	LeftArrow	0xc800f7420	RightArrow	0xc800ff421
DownArrow	0xc800f741f	OK	0xc800ff422	Y	0xc800f7426
X	0xc800ff468	A	0xc800f7466	B	0xc800ff425
ChUp	0xc800f7412	ChDown	0xc800ff413	VolDown	0xc800ff411
VolUp	0xc800ff410	Mute	0xc800ff40e	Start	0xc800ff40d
Play	0xc800f7416	Enter	0xc800ff40b	Record	0xc800f7417
Clear	0xc800ff40a	0	0xc800f7400	1	0xc800f7401
2	0xc800ff402	3	0xc800f7403	4	0xc800ff404
5	0xc800f7405	6	0xc800ff406	7	0xc800f7407
8	0xc800ff408	9	0xc800f7409	100	0xc800ff41d
Reload	0xc800f741c

Key points for debugging

The following are the main things to remember when dealing with 36-bit RC6 codes:

• Any 36-bit hex values must start with "0x" and end with "LL". If you get the error "integer constant is too large for 'long' type", you probably forgot the LL.
• You must use "long long" or "unsigned long long" to hold 36-bit values.
• Serial.print will not properly print 36-bit values; it will only print the lower 32 bits.
• You must flip the toggle bit every other time when you send a RC6 code, or the receiver will ignore your code.
• You will receive two different values for each button depending if the sender has flipped the toggle bit or not.