I was messing around with some code for run-length encoding and decoding over the past couple of days, and with the help of Jamey Sharp, Josh Triplett, and Jules Kongslie got it to be constant-time per symbol and fast.
Get the code at BartForge. (B)