Skip to main content
fixed grammar
Source Link
Ed H.
  • 1k
  • 7
  • 3

Addendum: It appears that the original code-packer produces code that does not represent valid UTF-8 encoded binary strings, and thus is technically invalid according to the rules. To make it valid, we must use only character values up to 128. I recently read the UTF-8 encoding rules, and trying to use all 8 bits and generate UTF-encoded strings is not fruitful because most binary strings (over half of all possibly binary strings of any given length) will not represent valid UTF-8 encodings. So using straight up 7-bit ascii code is more efficient. I've modified the code-packer code below to produce only unreadable 7-bit ascii strings by replacereplacing "256" with "128" and "<<8" with "<<7". This makes the packing compression idea not worthwhile for small programs (< 700 or so bytes), although it does still reduce Actven's 1000+ byte solution down to 937 bytes.

Addendum: It appears that the original code-packer produces code that does not represent valid UTF-8 encoded binary strings, and thus is technically invalid according to the rules. To make it valid, we must use only character values up to 128. I recently read the UTF-8 encoding rules, and trying to use all 8 bits and generate UTF-encoded strings is not fruitful because most binary strings (over half of all possibly binary strings of any given length) will not represent valid UTF-8 encodings. So using straight up 7-bit ascii code is more efficient. I've modified the code-packer code below to produce only unreadable 7-bit ascii strings by replace "256" with "128" and "<<8" with "<<7". This makes the packing compression idea not worthwhile for small programs (< 700 or so bytes), although it does still reduce Actven's 1000+ byte solution down to 937 bytes.

Addendum: It appears that the original code-packer produces code that does not represent valid UTF-8 encoded binary strings, and thus is technically invalid according to the rules. To make it valid, we must use only character values up to 128. I recently read the UTF-8 encoding rules, and trying to use all 8 bits and generate UTF-encoded strings is not fruitful because most binary strings (over half of all possibly binary strings of any given length) will not represent valid UTF-8 encodings. So using straight up 7-bit ascii code is more efficient. I've modified the code-packer code below to produce only unreadable 7-bit ascii strings by replacing "256" with "128" and "<<8" with "<<7". This makes the packing compression idea not worthwhile for small programs (< 700 or so bytes), although it does still reduce Actven's 1000+ byte solution down to 937 bytes.

readability fix
Source Link
Ed H.
  • 1k
  • 7
  • 3

If you run the current code-packer program on the above short solution, you get an expansion to 627 bytes. The packed string itself is about 50 bytes shorter, but adding the decompression code blows up the overall size.

If you run the current code-packer program on the above short solution, you get an expansion to 627 bytes. The packed string itself is about 50 bytes shorter, but the decompression code blows up the overall size.

If you run the current code-packer program on the above short solution, you get an expansion to 627 bytes. The packed string itself is about 50 bytes shorter, but adding the decompression code blows up the overall size.

complies with utf-8 encoding restrictions.
Source Link
Ed H.
  • 1k
  • 7
  • 3

Ruby (549)(549) binary chars

Addendum: It appears that the original code-packer produces code that does not represent valid UTF-8 encoded binary strings, and thus is technically invalid according to the rules. To make it valid, we must use only character values up to 128. I recently read the UTF-8 encoding rules, and trying to use all 8 bits and generate UTF-encoded strings is not fruitful because most binary strings (over half of all possibly binary strings of any given length) will not represent valid UTF-8 encodings. So using straight up 7-bit ascii code is more efficient. I've modified the code-packer code below to produce only unreadable 7-bit ascii strings by replace "256" with "128" and "<<8" with "<<7". This makes the packing compression idea not worthwhile for small programs (< 700 or so bytes), although it does still reduce Actven's 1000+ byte solution down to 937 bytes.

#!/usr/bin/env ruby
# This program takes a ruby file as input
# and outputs an equivalent ruby file as output that
# is functionally equivalent, but "compressed". 
# Compression is done by creating a string representing the original program
# which contains unprintable characters (including chars with value between 128 and 255)
# The string is just a binary packed version of the input program text.
# 
# the "decompression" algorithm for the string is written in ruby as part of the output, 
# along with an eval on the decompressed string. 
# NOTE: assumes input file doesn't contain any unprintable chars with value > 126, otherwise this will fail.

DEBUG=false # turn on debug to produce larger code that uses code sequences for the unprintable characters, 
         # and prints debugging information, and ruby code instead of executing it.
#DEBUG=true

# returns array of frequency counts for str
def frequency_count(str)
  freq= Array.new(127,0)
  str.bytes {|b| freq[b]+=1}
  freq
end

# figure out an appropriate contiguous
# range of characters (via ASCII) to use for representing str. 
# returns 
#  1) forward hash of chars, when applied to str, give only chars in the range
#  2) backward hash of chars for undoing #1
#  3) start character of range
#  4) length of range
def translate_range(str)
  freq = frequency_count(str)
  forward_hash = {}
  backward_hash = {}
  left_index = 0
  right_index = 126

  # ignore unused top range
  while right_index > 0 && freq[right_index] == 0
    right_index -= 1
  end

  if right_index == -1
    raise "Error: empty input string"
  end
  last_char_index = right_index

  # figure out chars to swap to get contiguous range
  # we want to minimize number of swaps, so this
  # naive approach won't always yield the best results.
  while left_index < right_index do
    if freq[left_index] == 0
       left_index += 1
       next
    end

    if freq[right_index] > 0
       right_index -= 1
       next
    end

    # found char on left that can move to empty spot on right
    forward_hash[left_index] = right_index
    backward_hash[right_index] = left_index
    freq[right_index] = 1 # mark it as filled.
    left_index +=1
    right_index -=1
  end 

  while freq[left_index]== 0
     left_index +=1
  end

  [forward_hash, backward_hash, left_index, last_char_index - left_index + 1]
end

# translates text into big num of given base, assuming all chars in string
# are in range start_char..(start_char+base-1)
def text_to_num (str, start_char, base)
   num = 0
   if (str[0] == start_char)
     raise "Sorry.. I can't handle strings that start with #{start_char.chr}"
   end  
   str.reverse.bytes {|x| num = num * base + (x - start_char)}
   num
end

# translates back from num to text. 
def num_to_text (num, start_char, base)
   text = ""
   while num > 0 do
      text += (num % base + start_char).chr
      num /= base
   end
  text
end

# translates from packed num string to original string, without translation part
# will be output into code.. present here for testing.
def packed_num_decode(str, start_char, base)
    m=0;str.bytes{|x|m=(m<<8)+x}
    t=""
    while m>0 ; t+=(m%base+start_char).chr;m/=base end
    t
end

# takes a string used for input into translate, and escapes
# chars with special meaning (^ at beginning, '-' between two chars, backslash)
def tr_escapes(str)
   str.sub("\\","\\\\\\\\").sub(/^\^/,"\\^").sub(/(.)-(.)/m, "\\1\\-\\2")
end

# takes a binary string, and escapes out characters problematic
# when writing the string within single quotes. 
# this includes ' and \.
def packed_string_escapes(str)
  chars_to_escape = "\\\'"
  escaped_str = ""
  str.bytes {|b| if chars_to_escape.include?(b.chr) 
    then
       escaped_str += "\\" + b.chr
    else
       escaped_str += b.chr
    end
  }
  escaped_str 
end

#======== Main program ========
if (ARGV.length != 2)
   puts "Usage: #{__FILE__} <input program> <output program>"
end
inputfile = ARGV[0] 
outputfile = ARGV[1]

inputtext = File.read(inputfile)
input_info = translate_range(inputtext)

from = ""
to = ""
input_info[0].each_pair {|x,y| from += x.chr ; to += y.chr }
input_mod = inputtext.tr(tr_escapes(from), tr_escapes(to))

input_num = text_to_num(input_mod, input_info[2], input_info[3])

packed_num = num_to_text(input_num,0,256128).reverse # do reverse so decompression code doesn't have to do it.


if (DEBUG) then 
   pretext="input_mod=#{input_mod.inspect}\nfrom=#{from.inspect}\nto=#{to.inspect}\n"
   packed_num_with_quotes = packed_num.inspect
   operation = "puts \"t=\#\{t.inspect\}\";puts"
else
   pretext=""
   packed_num_with_quotes = "'" +  packed_string_escapes(packed_num) + "'"
   operation = "eval"
end

start_char = input_info[2]
base = input_info[3]
from = ""
to = ""
input_info[1].each_pair {|x,y| from += x.chr ; to += y.chr }

from_str = tr_escapes(from).inspect
to_str = tr_escapes(to).inspect

File.open(outputfile, "w+") {|f|f.puts("#{pretext}m=0;#{packed_num_with_quotes}.bytes{|x|m<<=8;m+=x|x|m<<=7;m+=x};" +
              "t=\"\";while m>0;t+=(m%#{base}+#{start_char}).chr;m/=#{base} end;" +
              "#{operation} t.tr(#{from_str},#{to_str})")}

If you run the original code-packer program on the above short solution, it will generate a solution that is valid ruby source code that is 549 bytes long. Running this generated ruby source code will print out the required lyrics. Note that although the compressed string is over 100 bytes shorter than the original program, most of the savings is taken up by the decompression code.

Note that althoughIf you run the compressedcurrent code-packer program on the above short solution, you get an expansion to 627 bytes. The packed string itself is over 100about 50 bytes shorter than the original program, most ofbut the savings is takendecompression code blows up by the decompressionoverall size.

Thanks to the commenters for pointing out the technicalities of UTF-8 encoding. To me, the "valid UTF-8" restriction seems rather arbitrary-- if you're going to allow unprintable ascii characters in valid code, why shouldn't you also allow "invalidly coded UTF-8 characters?" The original code-packer still does generate valid ruby source code that really takes up only 549 bytes of storage when run on the 556-byte solution presented above.

Ruby (549) binary chars

#!/usr/bin/env ruby
# This program takes a ruby file as input
# and outputs an equivalent ruby file as output that
# is functionally equivalent, but "compressed". 
# Compression is done by creating a string representing the original program
# which contains unprintable characters (including chars with value between 128 and 255)
# The string is just a binary packed version of the input program text.
# 
# the "decompression" algorithm for the string is written in ruby as part of the output, 
# along with an eval on the decompressed string. 
# NOTE: assumes input file doesn't contain any unprintable chars with value > 126, otherwise this will fail.

DEBUG=false # turn on debug to produce larger code that uses code sequences for the unprintable characters, 
         # and prints debugging information, and ruby code instead of executing it.
#DEBUG=true

# returns array of frequency counts for str
def frequency_count(str)
  freq= Array.new(127,0)
  str.bytes {|b| freq[b]+=1}
  freq
end

# figure out an appropriate contiguous
# range of characters (via ASCII) to use for representing str. 
# returns 
#  1) forward hash of chars, when applied to str, give only chars in the range
#  2) backward hash of chars for undoing #1
#  3) start character of range
#  4) length of range
def translate_range(str)
  freq = frequency_count(str)
  forward_hash = {}
  backward_hash = {}
  left_index = 0
  right_index = 126

  # ignore unused top range
  while right_index > 0 && freq[right_index] == 0
    right_index -= 1
  end

  if right_index == -1
    raise "Error: empty input string"
  end
  last_char_index = right_index

  # figure out chars to swap to get contiguous range
  # we want to minimize number of swaps, so this
  # naive approach won't always yield the best results.
  while left_index < right_index do
    if freq[left_index] == 0
       left_index += 1
       next
    end

    if freq[right_index] > 0
       right_index -= 1
       next
    end

    # found char on left that can move to empty spot on right
    forward_hash[left_index] = right_index
    backward_hash[right_index] = left_index
    freq[right_index] = 1 # mark it as filled.
    left_index +=1
    right_index -=1
  end 

  while freq[left_index]== 0
     left_index +=1
  end

  [forward_hash, backward_hash, left_index, last_char_index - left_index + 1]
end

# translates text into big num of given base, assuming all chars in string
# are in range start_char..(start_char+base-1)
def text_to_num (str, start_char, base)
   num = 0
   if (str[0] == start_char)
     raise "Sorry.. I can't handle strings that start with #{start_char.chr}"
   end  
   str.reverse.bytes {|x| num = num * base + (x - start_char)}
   num
end

# translates back from num to text. 
def num_to_text (num, start_char, base)
   text = ""
   while num > 0 do
      text += (num % base + start_char).chr
      num /= base
   end
  text
end

# translates from packed num string to original string, without translation part
# will be output into code.. present here for testing.
def packed_num_decode(str, start_char, base)
    m=0;str.bytes{|x|m=(m<<8)+x}
    t=""
    while m>0 ; t+=(m%base+start_char).chr;m/=base end
    t
end

# takes a string used for input into translate, and escapes
# chars with special meaning (^ at beginning, '-' between two chars, backslash)
def tr_escapes(str)
   str.sub("\\","\\\\\\\\").sub(/^\^/,"\\^").sub(/(.)-(.)/m, "\\1\\-\\2")
end

# takes a binary string, and escapes out characters problematic
# when writing the string within single quotes. 
# this includes ' and \.
def packed_string_escapes(str)
  chars_to_escape = "\\\'"
  escaped_str = ""
  str.bytes {|b| if chars_to_escape.include?(b.chr) 
    then
       escaped_str += "\\" + b.chr
    else
       escaped_str += b.chr
    end
  }
  escaped_str 
end

#======== Main program ========
if (ARGV.length != 2)
   puts "Usage: #{__FILE__} <input program> <output program>"
end
inputfile = ARGV[0] 
outputfile = ARGV[1]

inputtext = File.read(inputfile)
input_info = translate_range(inputtext)

from = ""
to = ""
input_info[0].each_pair {|x,y| from += x.chr ; to += y.chr }
input_mod = inputtext.tr(tr_escapes(from), tr_escapes(to))

input_num = text_to_num(input_mod, input_info[2], input_info[3])

packed_num = num_to_text(input_num,0,256).reverse # do reverse so decompression code doesn't have to do it.


if (DEBUG) then 
   pretext="input_mod=#{input_mod.inspect}\nfrom=#{from.inspect}\nto=#{to.inspect}\n"
   packed_num_with_quotes = packed_num.inspect
   operation = "puts \"t=\#\{t.inspect\}\";puts"
else
   pretext=""
   packed_num_with_quotes = "'" +  packed_string_escapes(packed_num) + "'"
   operation = "eval"
end

start_char = input_info[2]
base = input_info[3]
from = ""
to = ""
input_info[1].each_pair {|x,y| from += x.chr ; to += y.chr }

from_str = tr_escapes(from).inspect
to_str = tr_escapes(to).inspect

File.open(outputfile, "w+") {|f|f.puts("#{pretext}m=0;#{packed_num_with_quotes}.bytes{|x|m<<=8;m+=x};" +
              "t=\"\";while m>0;t+=(m%#{base}+#{start_char}).chr;m/=#{base} end;" +
              "#{operation} t.tr(#{from_str},#{to_str})")}

If you run the code-packer program on the above short solution, it will generate a solution that is valid ruby source code that is 549 bytes long. Running this generated ruby source code will print out the required lyrics.

Note that although the compressed string is over 100 bytes shorter than the original program, most of the savings is taken up by the decompression code.

Ruby (549) binary chars

Addendum: It appears that the original code-packer produces code that does not represent valid UTF-8 encoded binary strings, and thus is technically invalid according to the rules. To make it valid, we must use only character values up to 128. I recently read the UTF-8 encoding rules, and trying to use all 8 bits and generate UTF-encoded strings is not fruitful because most binary strings (over half of all possibly binary strings of any given length) will not represent valid UTF-8 encodings. So using straight up 7-bit ascii code is more efficient. I've modified the code-packer code below to produce only unreadable 7-bit ascii strings by replace "256" with "128" and "<<8" with "<<7". This makes the packing compression idea not worthwhile for small programs (< 700 or so bytes), although it does still reduce Actven's 1000+ byte solution down to 937 bytes.

#!/usr/bin/env ruby
# This program takes a ruby file as input
# and outputs an equivalent ruby file as output that
# is functionally equivalent, but "compressed". 
# Compression is done by creating a string representing the original program
# which contains unprintable characters (including chars with value between 128 and 255)
# The string is just a binary packed version of the input program text.
# 
# the "decompression" algorithm for the string is written in ruby as part of the output, 
# along with an eval on the decompressed string. 
# NOTE: assumes input file doesn't contain any unprintable chars with value > 126, otherwise this will fail.

DEBUG=false # turn on debug to produce larger code that uses code sequences for the unprintable characters, 
         # and prints debugging information, and ruby code instead of executing it.
#DEBUG=true

# returns array of frequency counts for str
def frequency_count(str)
  freq= Array.new(127,0)
  str.bytes {|b| freq[b]+=1}
  freq
end

# figure out an appropriate contiguous
# range of characters (via ASCII) to use for representing str. 
# returns 
#  1) forward hash of chars, when applied to str, give only chars in the range
#  2) backward hash of chars for undoing #1
#  3) start character of range
#  4) length of range
def translate_range(str)
  freq = frequency_count(str)
  forward_hash = {}
  backward_hash = {}
  left_index = 0
  right_index = 126

  # ignore unused top range
  while right_index > 0 && freq[right_index] == 0
    right_index -= 1
  end

  if right_index == -1
    raise "Error: empty input string"
  end
  last_char_index = right_index

  # figure out chars to swap to get contiguous range
  # we want to minimize number of swaps, so this
  # naive approach won't always yield the best results.
  while left_index < right_index do
    if freq[left_index] == 0
       left_index += 1
       next
    end

    if freq[right_index] > 0
       right_index -= 1
       next
    end

    # found char on left that can move to empty spot on right
    forward_hash[left_index] = right_index
    backward_hash[right_index] = left_index
    freq[right_index] = 1 # mark it as filled.
    left_index +=1
    right_index -=1
  end 

  while freq[left_index]== 0
     left_index +=1
  end

  [forward_hash, backward_hash, left_index, last_char_index - left_index + 1]
end

# translates text into big num of given base, assuming all chars in string
# are in range start_char..(start_char+base-1)
def text_to_num (str, start_char, base)
   num = 0
   if (str[0] == start_char)
     raise "Sorry.. I can't handle strings that start with #{start_char.chr}"
   end  
   str.reverse.bytes {|x| num = num * base + (x - start_char)}
   num
end

# translates back from num to text. 
def num_to_text (num, start_char, base)
   text = ""
   while num > 0 do
      text += (num % base + start_char).chr
      num /= base
   end
  text
end

# translates from packed num string to original string, without translation part
# will be output into code.. present here for testing.
def packed_num_decode(str, start_char, base)
    m=0;str.bytes{|x|m=(m<<8)+x}
    t=""
    while m>0 ; t+=(m%base+start_char).chr;m/=base end
    t
end

# takes a string used for input into translate, and escapes
# chars with special meaning (^ at beginning, '-' between two chars, backslash)
def tr_escapes(str)
   str.sub("\\","\\\\\\\\").sub(/^\^/,"\\^").sub(/(.)-(.)/m, "\\1\\-\\2")
end

# takes a binary string, and escapes out characters problematic
# when writing the string within single quotes. 
# this includes ' and \.
def packed_string_escapes(str)
  chars_to_escape = "\\\'"
  escaped_str = ""
  str.bytes {|b| if chars_to_escape.include?(b.chr) 
    then
       escaped_str += "\\" + b.chr
    else
       escaped_str += b.chr
    end
  }
  escaped_str 
end

#======== Main program ========
if (ARGV.length != 2)
   puts "Usage: #{__FILE__} <input program> <output program>"
end
inputfile = ARGV[0] 
outputfile = ARGV[1]

inputtext = File.read(inputfile)
input_info = translate_range(inputtext)

from = ""
to = ""
input_info[0].each_pair {|x,y| from += x.chr ; to += y.chr }
input_mod = inputtext.tr(tr_escapes(from), tr_escapes(to))

input_num = text_to_num(input_mod, input_info[2], input_info[3])

packed_num = num_to_text(input_num,0,128).reverse # do reverse so decompression code doesn't have to do it.


if (DEBUG) then 
   pretext="input_mod=#{input_mod.inspect}\nfrom=#{from.inspect}\nto=#{to.inspect}\n"
   packed_num_with_quotes = packed_num.inspect
   operation = "puts \"t=\#\{t.inspect\}\";puts"
else
   pretext=""
   packed_num_with_quotes = "'" +  packed_string_escapes(packed_num) + "'"
   operation = "eval"
end

start_char = input_info[2]
base = input_info[3]
from = ""
to = ""
input_info[1].each_pair {|x,y| from += x.chr ; to += y.chr }

from_str = tr_escapes(from).inspect
to_str = tr_escapes(to).inspect

File.open(outputfile, "w+") {|f|f.puts("#{pretext}m=0;#{packed_num_with_quotes}.bytes{|x|m<<=7;m+=x};" +
              "t=\"\";while m>0;t+=(m%#{base}+#{start_char}).chr;m/=#{base} end;" +
              "#{operation} t.tr(#{from_str},#{to_str})")}

If you run the original code-packer program on the above short solution, it will generate a solution that is valid ruby source code that is 549 bytes long. Running this generated ruby source code will print out the required lyrics. Note that although the compressed string is over 100 bytes shorter than the original program, most of the savings is taken up by the decompression code.

If you run the current code-packer program on the above short solution, you get an expansion to 627 bytes. The packed string itself is about 50 bytes shorter, but the decompression code blows up the overall size.

Thanks to the commenters for pointing out the technicalities of UTF-8 encoding. To me, the "valid UTF-8" restriction seems rather arbitrary-- if you're going to allow unprintable ascii characters in valid code, why shouldn't you also allow "invalidly coded UTF-8 characters?" The original code-packer still does generate valid ruby source code that really takes up only 549 bytes of storage when run on the 556-byte solution presented above.

added 156 characters in body
Source Link
Ed H.
  • 1k
  • 7
  • 3
Loading
attempted to fix code-packer with &gt; instead of >
Source Link
Ed H.
  • 1k
  • 7
  • 3
Loading
Source Link
Ed H.
  • 1k
  • 7
  • 3
Loading