Binary Calculator Implementation in Apache mod_rewrite

en

Many text replacement dialects utilizing regular expressions become turing complete when combined with conditional loops or recursion. Apache's mod_rewrite is no exception here; you can write turing-complete programs using RewriteRules only. A few weeks ago I decided to try my hand at this and wrote a binary calculator (well, only an adder, to be precise) implemented in an Apache2 config file.

mod_rewrite Basics

Apache's mod_rewrite allows for conditionally rewriting request URLs. A RewriteRule directive looks like this:

RewriteRule "pattern" "replacement" [flags]

The pattern is matched against the URL of the request, and if it matches, the matching region is replaced by the replacement expression. The flags control the exact behavior of the rule. We only make use of three flags in this implementation:

  • L aka last terminates the rewrite engine, no more rules are processed for this request. L is used to "exit the program".
  • R aka redirect causes the web server to respond with a 302 Found, rather than processing the rewritten URL internally. This is used to return the result to the client in the Location header.
  • N aka next causes the rewrite engine to start over from the beginning, operating on the result of the last iteration. The combination of N and L is what gives us conditional recursion.

The Calculator

The calculator works as explained in the following example, which adds the binary representations of 11 and 7, and should ideally result in 18.

  1. The client sends a request such as GET /1011+111 HTTP/1.1
  2. The server first adds an equality sign to the end: /1011+111=.
  3. The server iteratively performs the addition bit-by-bit (# represents the carry bit):
    1. /1011+111= → /101+11=#0
    2. /101+11=#0 → /10+1=#10
    3. /10+1=#10 → /1+=#010
    4. /1+=#010 → /1+0=#010 (add zero padding)
    5. /1+0=#010 → /+=#0010
  4. The server cleans up the request, removing the operators and resolving the last carry bit, if present:
    • /+=#0010 → /10010
  5. The server responds with a redirect with a Location: /10010 header.

And here's the whole mod_rewrite Config:

RewriteEngine on
# Termination condition: no more digits left, also strips leading zeros
RewriteRule "^/\+=0*([01]+)$"                    "/$1"           [L,R]
# Termination condition with carry flag
RewriteRule "^/\+=#0*([01]+)"                    "/1$1"          [L,R]
# Add = if absent
RewriteRule "^/([01]+)\+([01]+)$"              "/$1+$2="       
# Pad first number with zeros if too short
RewriteRule "^/\+([01]+)=(#?[01]*)"            "/0+$1=$2"      
# Pad second number with zeros if too short
RewriteRule "^/([01]+)\+=(#?[01]*)"            "/$1+0=$2"      
# 0+0 nocarry
RewriteRule "^/([01]*)0\+([01]*)0=([01]*)$"    "/$1+$2=0$3"    [N]
# 0+0 carry
RewriteRule "^/([01]*)0\+([01]*)0=#([01]*)$"   "/$1+$2=1$3"    [N]
# 1+0 nocarry
RewriteRule "^/([01]*)1\+([01]*)0=([01]*)$"    "/$1+$2=1$3"    [N]
# 1+0 carry
RewriteRule "^/([01]*)1\+([01]*)0=#([01]*)$"   "/$1+$2=#0$3"   [N]
# 0+1 nocarry
RewriteRule "^/([01]*)0\+([01]*)1=([01]*)$"    "/$1+$2=1$3"    [N]
# 0+1 carry
RewriteRule "^/([01]*)0\+([01]*)1=#([01]*)$"   "/$1+$2=#0$3"   [N]
# 1+1 nocarry
RewriteRule "^/([01]*)1\+([01]*)1=([01]*)$"    "/$1+$2=#0$3"   [N]
# 1+1 carry
RewriteRule "^/([01]*)1\+([01]*)1=#([01]*)$"   "/$1+$2=#1$3"   [N]