#!/usr/bin/ruby -w
# Optimized bitcode for ASCII English text.
# aaaaaaaa 1 = output (byte = aaaaaaaa^0x20)
# xxxxxxxx 0 yyyyyyyy 1 = branch (length=xxxxxxxx+3, offset=yyyyyyyy+1)

# Minimum length for repeat instructions, in units of number of input bytes.
# A single repeat instruction costs the same amount of space as two output
# instructions, so we the repeat length needs to be at least 3 for it to be
# worthwhile.
MIN_REPEAT = 3

# Minimum offset for repeat targets, in code block units (each output
# instruction counts as 1 unit, and each repeat instruction counts as
# 2 units).
MIN_OFFSET = 1

# Maximum offset for repeat targets.
MAX_OFFSET = 255 + MIN_OFFSET

# Maximum stack to be used at runtime.
MAX_STACK = 639
fail unless MAX_STACK % 2 == 1

# Instruction return states.
RS_NORMAL = 0
RS_FIRST_INSTRUCTION_AFTER_BRANCH = RS_NORMAL + 1
RS_SECOND_INSTRUCTION_AFTER_RETURN = 2
RS_FIRST_INSTRUCTION_AFTER_RETURN = RS_SECOND_INSTRUCTION_AFTER_RETURN + 1

# Maximum number of steps to run.
MAX_STEPS = 1000000000

# Size of ring buffer for storing code offsets.
#
# For each position in input text, we need to keep track of the output code
# position to decide whether the code can be referenced inside a repeat
# command.  The furthest text that might be referenced is:
#
#     furthest address repeat block = (max offset) / (repeat instruction size)
#                                   = 256 / 2 = 128
#
#     (maximum repeat block length) * (furthest addressable repeat block) =
#     258 * 128 = 33024
#
# But instead of using that odd size, we will round up to next power of 2.
# This allows us to use bitwise operations to compute ring offset.
RING_BUFFER_SIZE = 0x10000
RING_BUFFER_MASK = RING_BUFFER_SIZE - 1

# Maximum output size.
MAX_OUTPUT_SIZE = RING_BUFFER_SIZE * 3

# XOR all input bytes with this key.  This is to minimize the number of
# 1-bits in output.  See bit_frequencies.pl.
XOR_KEY = 0x20

# True to enable tracing.
TRACE = false

# Run assembled bitcode, returning output as a string.
def run(code)
   start = Time::now

   # Control flow stack:
   # stack[2*N-1] = return address.
   # stack[2*N] = output bytes remaining.
   #
   # Output bytes remaining is decremented each time a byte is printed, and
   # control flow is returned to parent frame once the counter reaches zero.
   stack = [MAX_OUTPUT_SIZE]

   # Stack pointer.
   sp = 0
   fail unless stack[sp] > 0

   # Instruction pointer.
   ip = -1

   # Instruction start.
   is = nil

   # Return state.  See RS_* constants near the top.
   rs = RS_FIRST_INSTRUCTION_AFTER_BRANCH

   # Accumulator.
   x = nil

   # Number of steps executed, used to detect runaway loops.
   steps = 0

   # Buffered output text.
   output_text = ""

   # Debug counters.
   max_stack = 0
   max_repeat_offset = 0
   max_repeat_length = 0

   # Output current states.
   unless defined?(trace)
      define_method :trace do |line, msg|
         return unless TRACE
         print " " * sp,
               "#{line}: steps=#{steps}, ip=#{ip}, ",
               "x=#{x ? '0x' + x.to_s(16) : 'nil'}, ",
               "stack[#{sp - 1}]=#{sp > 0 ? stack[sp - 1] : 'nil'}, ",
               "stack[#{sp}]=#{stack[sp]}, ",
               "is=#{is}, rs=#{rs}, #{msg}\n"
      end
   end

   while ip < code.size
      steps += 1
      fail if steps > MAX_STEPS

      # First instruction after a branch or return is always ignored.
      # We always return to the end of the previous instruction because
      # "1" bits are only guaranteed to appear at the end of instructions,
      # and only "1" bits are valid branch targets.
      if rs & 1 != 0
         trace(__LINE__, "next")
         fail unless ip >= -1
         fail unless (ip + 1) % 9 == 0
         rs -= 1
         fail unless (rs == 0 || rs == 2)
         x = 0
         is = ip + 1
         ip += 1
         next
      end

      # Instruction execution only happens at "1" bits.
      fail unless ip >= 0
      if code[ip] == "0"
         ip += 1
         next
      end
      fail unless is
      fail unless x
      fail unless x >= 0

      # Check if instruction pointer has reached the end of a complete
      # instruction.  If not, update accumulator and move on.
      if (ip + 1) % 9 != 0
         trace(__LINE__, "accumulate")
         x |= 1 << (ip - is)
         ip += 1
         next
      end
      fail unless (ip - is == 8 || ip - is == 17)

      # Check for repeat instruction.
      if ip - is == 17
         length = (x & 0xff) + MIN_REPEAT
         offset = ((x >> 9) + 2 + MIN_OFFSET) * 9

         if rs == RS_SECOND_INSTRUCTION_AFTER_RETURN
            # Recursive return.
            trace(__LINE__, "recursive_return: length=#{length}")
            stack[sp] -= length
            if stack[sp] <= 0
               rs = RS_FIRST_INSTRUCTION_AFTER_RETURN
               ip = stack[sp - 1]
               sp -= 2
               fail unless sp >= 0
               next
            end

            # Completed return chain.
            trace(__LINE__, "completed_return")
            rs = RS_NORMAL
            is = ip + 1
            ip += 1
            x = 0
            next
         end
         trace(__LINE__, "branch: offset=#{offset}, length=#{length}")
         fail unless rs == RS_NORMAL

         max_repeat_offset = [max_repeat_offset, offset].max
         max_repeat_length = [max_repeat_length, length].max

         # Set return address to be start of previous instruction, and
         # branch to earlier part of the code.
         fail unless is - 1 == ip - 18
         stack[sp + 1] = is - 1
         stack[sp + 2] = [stack[sp], length].min
         ip -= offset
         rs = RS_FIRST_INSTRUCTION_AFTER_BRANCH
         sp += 2
         max_stack = [max_stack, sp].max
         fail if max_stack >= MAX_STACK
         next
      end

      # Output byte.
      trace(__LINE__, "output")
      fail unless ip - is == 8
      fail unless rs == 0
      x ^= XOR_KEY
      if TRACE
         print " " * sp, "#{__LINE__}: output(#{x.chr.dump})\n"
      end
      output_text += x.chr
      x = 0

      # Return when enough bytes have been printed.
      stack[sp] -= 1
      if stack[sp] == 0
         fail unless sp > 0
         rs = RS_FIRST_INSTRUCTION_AFTER_RETURN
         ip = stack[sp - 1]
         sp -= 2
         next
      end

      is = ip + 1
      ip += 1
   end
   print "run_time=#{Time::now - start}, steps=#{steps}\n",
         "max_stack=#{max_stack}, ",
         "max_repeat_offset=#{max_repeat_offset}, ",
         "max_repeat_length=#{max_repeat_length}\n"
   return output_text
end

# Encode an 8-bit number, least significant bit first.
def encode_number(n)
   fail if n < 0
   fail if n > 255
   return (sprintf '%08b', n).reverse
end

# Return number of 1-bits in a number.
def bitcount(n)
   return n.to_s(2).count("1")
end

# Translate input text into bit encoding.
def encode(input)
   start = Time::now

   # Tweak bits in input to minimize 1-bits in output.
   input = input.bytes.map{|x| (x ^ XOR_KEY).chr} * ""

   # Output code.
   code = ""

   # Ring buffer of code offsets.
   offsets = [0] * RING_BUFFER_SIZE

   # Ring buffer of runtime stack sizes.
   stack_size = [nil] * RING_BUFFER_SIZE

   # Indices for offsets[] and stack_size[]
   o_read = 0
   o_write = 0

   # Offset of next byte to be encoded.
   read_offset = 0

   # Debug counters.
   max_history_size = 0
   match_steps = 0

   while read_offset < input.size
      fail unless o_write == (read_offset & RING_BUFFER_MASK)

      # Expire old ring buffer entries that are too far away to be reachable.
      while o_read != o_write
         if offsets[o_read] && code.size - offsets[o_read] <= MAX_OFFSET * 9
            break
         end
         o_read = (o_read + 1) & RING_BUFFER_MASK
      end
      history_size = o_write >= o_read ? o_write - o_read
                                       : o_write + RING_BUFFER_SIZE - o_read
      max_history_size = [max_history_size, history_size].max

      if TRACE
         print "#{__LINE__}: input=",
               (input[read_offset].ord ^ XOR_KEY).chr.dump,
               ", read_offset=#{read_offset}, ",
               "o_read=#{o_read}, o_write=#{o_write}, ",
               "history_size=#{history_size}, ",
               "code.size=#{code.size}\n"
      end

      # Find longest match in previous input.
      repeat_code_offset = nil   # Offset within code string.
      repeat_input_offset = nil  # Offset within input string.
      repeat_length = 0          # Number of bytes matched.
      history_size.times{|i|
         ring_start = (o_read + i) & RING_BUFFER_MASK
         fail unless ring_start != o_write
         code_offset = offsets[ring_start]

         # Skip code offsets that can't be referenced, i.e. the string that
         # we want to copy is covered by a repeat block.
         next unless code_offset

         # Check for matching substring.
         match_offset = read_offset - history_size + i
         match_length = 0
         fail unless match_offset < read_offset
         (255 + MIN_REPEAT).times{|j|
            break if read_offset + j >= input.size
            break if input[match_offset + j] != input[read_offset + j]

            overlap = match_offset + j - read_offset
            if overlap < 0
               # Matching some text in the past, where stack size is
               # guaranteed to be defined.
               k = (ring_start + j) & RING_BUFFER_MASK
               fail unless stack_size[k]
               break if stack_size[k] + 2 >= MAX_STACK
            else
               # Matching some text in the future.  Stack size depends on
               # how many times we have repeated the prefix.
               prefix_length = read_offset - match_offset
               depth = overlap / prefix_length + 1
               k = (ring_start + (overlap % prefix_length)) & RING_BUFFER_MASK
               fail unless stack_size[k]
               break if stack_size[k] + 2 * depth >= MAX_STACK
            end

            match_length += 1
         }
         match_steps += 1

         # A previous substring is a potential repeat candidate if it's
         # at least 3 bytes long.
         if match_length >= MIN_REPEAT
            if TRACE
               print "#{__LINE__}: match_offset=#{match_offset}, ",
                     "match_length=#{match_length}, ",
                     "code_offset=#{code_offset}\n"
            end
            if match_length > repeat_length
               # Candidates that are longer than what we have matched before
               # are always accepted, since they improve compression ratio.
               repeat_code_offset = code_offset
               repeat_input_offset = match_offset
               repeat_length = match_length
            elsif match_length == repeat_length
               # Candidates that are of same length as what we have matched
               # before are accepted only if it takes fewer 1-bits to encode
               # those offsets.
               fail unless repeat_code_offset % 9 == 0
               fail unless code_offset % 9 == 0
               if bitcount(code_offset / 9 - MIN_OFFSET) <
                  bitcount(repeat_code_offset / 9 - MIN_OFFSET)
                  repeat_code_offset = code_offset
                  repeat_input_offset = match_offset
                  repeat_length = match_length
               end
            end
         end
      }

      if repeat_length <= 0 then
         # Did not match a previous substring.  Will output a literal byte.
         if TRACE
            print "#{__LINE__}: literal=",
                  (input[read_offset].ord ^ XOR_KEY).chr.dump,
                  "\n"
         end

         # Mark current position.
         offsets[o_write] = code.size

         # Literal bytes does not cost any stack, other than the initial
         # stack entry that maintains maximum output limit.
         stack_size[o_write] = 1

         # Update ring buffer pointer.
         o_write = (o_write + 1) & RING_BUFFER_MASK

         # Ring buffer is never full because of the expiry step at the
         # beginning of the loop where we drop blocks that are too far
         # to be reachable.
         fail if o_write == o_read

         # Output a literal byte.
         code += encode_number(input[read_offset].ord) + "1"
         read_offset += 1
      else
         # Matched a previous substring that's sufficiently long.
         # Will output a repeat command.
         if TRACE
            print "#{__LINE__}: repeat_code_offset=#{repeat_code_offset}, ",
                  "repeat_input_offset=#{repeat_input_offset}, ",
                  "repeat_length=#{repeat_length}\n"
         end
         fail unless repeat_code_offset
         fail unless repeat_input_offset
         fail unless (code.size - repeat_code_offset) % 9 == 0
         fail unless repeat_input_offset < read_offset
         fail unless repeat_length >= MIN_REPEAT

         ring_start = repeat_input_offset & RING_BUFFER_MASK

         # Remove code positions for region covered by repeat code.
         repeat_length.times{|i|
            # Mark code position for first byte the region covered by
            # repeated code.  All subsequent bytes do not have positions
            # associated with them since they are not reachable.
            if i == 0
               offsets[o_write] = code.size
            else
               offsets[o_write] = nil
            end

            # Record runtime stack depth for each byte in region.
            old_stack_size = stack_size[(ring_start + i) & RING_BUFFER_MASK]
            fail unless old_stack_size
            stack_size[o_write] = old_stack_size + 2

            o_write = (o_write + 1) & RING_BUFFER_MASK
            fail if o_write == o_read
         }

         # Output repeat code.
         code +=
            encode_number(repeat_length - MIN_REPEAT) +
            "0" +
            encode_number((code.size - repeat_code_offset) / 9 - MIN_OFFSET) +
            "1"
         read_offset += repeat_length
      end

      if TRACE
         print "#{__LINE__}: read_offset=#{read_offset}, ",
               "o_write=#{o_write}, code.size=#{code.size}\n"
      end
   end
   print "encode_time=#{Time::now - start}, ",
         "input.size=#{input.size}, code.size=#{code.size}, ",
         "1-bits=#{code.count('1')}, ",
         "max_history_size=#{max_history_size}, match_steps=#{match_steps}\n"
   return code
end

srand 1

# Generate random blocks of varying length.
blocks = []
[3, 127, 255, 258, 259].each{|i|
   b = ""
   i.times{
      b += rand(3).to_s
   }
   blocks += [b]
}

# Interleave the blocks.
input_text = ""
2.times{
   blocks.size.times{|i|
      input_text += blocks[i]
      blocks.size.times{|j|
         input_text += blocks[j]
      }
   }
}

# Append random blocks until input is sufficiently long.
while input_text.size < RING_BUFFER_SIZE * 2
   input_text += blocks[rand(blocks.size)]
end
if TRACE
   print "#{__LINE__}: encode(#{input_text})\n"
end

code = encode(input_text)
if TRACE
   i = 0
   while i < code.size
      if code[i + 8] == "1"
         print code[i, 9], ": output(",
               (code[i, 8].reverse.to_i(2) ^ XOR_KEY).chr.dump, ")\n"
         i += 9
      else
         print code[i, 18], ": repeat(",
               code[i, 8].reverse.to_i(2) + MIN_REPEAT, ", ",
               -(code[i + 9, 8].reverse.to_i(2) + MIN_OFFSET), ")\n"
         i += 18
      end
   end
end
output_text = run(code)
unless input_text == output_text
   print " input=#{input_text}\n",
         "output=#{input_text}\n"
   fail
end