Base85 Encoding

Question

The Challenge

Write a program that can take an input of a single-line string containing any ASCII printable characters, and output the same string encoded in Base85 (using a big-endian convention). You can assume that the input will always be ≤ 100 characters.

---

A Guide to Base85

• Four octets are encoded into (usually) five Base85 characters.

• Base85 characters range from ! to u (ASCII 33 - 117) and z (ASCII 122).

• To encode, you continuously perform division by 85 on the four octets (a 32-bit number), and add 33 to the remainder (after each division) to get the ASCII character for the encoded value. For example, the first application of this process produces the rightmost character in the encoded block.

• If a set of four octets contains only null bytes, they are encoded as a z instead of !!!!!.

• If the last block is shorter than four octets, it's padded with null bytes. After encoding, the same number of characters that were added as padding, are removed from the end of the output.

• The encoded value should be preceded by <~ and followed by ~>.

• The encoded value should contain no whitespace (for this challenge).

---

Examples

In: easy
Out: <~ARTY*~>

In: test
Out: <~FCfN8~>

In: code golf
Out: <~@rGmh+D5V/Ac~>

In: Programming Puzzles
Out: <~:i^JeEa`g%Bl7Q+:j%)1Ch7Y~>

The following snippet will encode a given input to Base85.

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><script>String.prototype.toAscii85=function(){if(""==this)return"<~~>";for(var r=[],t=0;t<this.length;t+=4){for(var i=(this.substr(t,4)+"\x00\x00\x00").substr(0,4),o=0,n=0;4>n;n++)o=256*o+i.charCodeAt(n);var s=[];for(n=0;5>n;n++){var e=o%85;o=(o-e)/85,s.unshift(String.fromCharCode(e+33))}r=r.concat(s)}var a=4-this.length%4;return 4!=a&&r.splice(-a,a),"<~"+r.join("").replace(/!!!!!/g,"z")+"~>"};</script><style>#in,#out{margin:20px;width:400px;resize:none}</style><input id="in" type="text" value="Base85"><button onclick="$('#out').text($('#in').val().toAscii85())">Submit</button><br><textarea id="out" rows=5 disabled></textarea>

Answer 1

CJam, 43 39 35 bytes

"<~"q4/{:N4Ue]256b85b'!f+}/N,)<"~>"

Try it online in the CJam interpreter.

How it works

"<~"      e# Push that string.
q4/       e# Read all input from STDIN and split it into chunks of length 4.
{         e# For each chunk:
  :N      e#   Save it in N.
  4Ue]    e#   Right-pad it with 0's to a length of 4.
  256b85b e#   Convert from base 256 to base 85.
  '!f+    e#   Add '!' to each base-85 digit.
}/        e#
N,)       e# Push the length of the last unpadded chunk, plus 1.
<         e# Keep that many chars of the last encoded chunk.
"~>"      e# Push that string.

If the input was empty, N,) will apply to the string "<~". Since N initially holds a single character, the output will be correct.

We don't have to deal with z or pad the encoded chunks to length 5, since the input will contain only printable ASCII characters.

Answer 2

Python 3, 71 bytes

from base64 import*
print(a85encode(input().encode(),adobe=1).decode())

I've never golfed in Python, so this is probably sub-optimal.

Thanks to @ZachGates for golfing off 3 bytes!

Answer 3

Pure bash, ~738

Encoder first (something golfed):

#!/bin/bash
# Ascii 85 encoder bash script
LANG=C

printf -v n \\%o {32..126};printf -v n "$n";printf -v m %-20sE abtnvfr;p=\<~;l()
{ q=$(($1<<24|$2<<16|$3<<8|$4));q="${n:1+(q/64#378iN)%85:1}${n:1+(q/614125)%85:1
}${n:1+(q/7225)%85:1}${n:1+(q/85)%85:1}${n:1+q%85:1}";};k() { ((${#p}>74))&&ech\
o "${p:0:75}" && p=${p:75};};while IFS= read -rd '' -n 1 q;do [ "$q" ]&&{ print\
f -v q "%q" "$q";case ${#q} in 1|2)q=${n%$q*};o+=($((${#q}+32)));;7)q=${q#*\'\\}
o+=($((8#${q%\'})));;5)q=${q#*\'\\};q=${m%${q%\'}*};o+=($((${#q}+07)));;esac;}||
o+=(0);((${#o[@]}>3))&&{ [ "${o[*]}" = "0 0 0 0" ]&& q=z|| l ${o[@]};p+="${q}";k
o=(); };done;[ "$o" ]&&{ f=0;for((;${#o[@]}<4;)){ o+=(0);((f++));};((f==0))&&[ \
"${o[*]}" = "0 0 0 0" ]&&q=z||l ${o[@]};p+="${q:0:5-f}";};p+="~>";k;[ "$p" ]&&e\
cho "$p"

Tests:

for word in easy test code\ golf Programming\ Puzzles ;do
    printf "    %-24s %s\n" "$word:" $(./enc85.sh < <(printf "$word"))
  done
    easy:                   <~ARTY*~>
    test:                   <~FCfN8~>
    code golf:              <~@rGmh+D5V/Ac~>
    Programming Puzzles:    <~:i^JeEa`g%Bl7Q+:j%)1Ch7Y~>

and decoder now:

#!/bin/bash
# Ascii 85 decoder bash script
LANG=C

printf -v n "\%o" {33..117};printf -v n "$n";o=1 k=1;j(){ read -r q||o=;[ "$q" \
]&&[ -z "${q//*<~*}" ]&&((k))&&k= q="${q#*<~}";m+="$q";m="${m%~>*}";};l(){ r=;f\
or((i=0;i<${#1};i++)){ s="${1:i:1}";case "$s" in "*"|\\|\?)s=\\${s};;esac;s="${\
n%${s}*}";((r+=${#s}*(85**(4-i))));};printf -v p "\%03o" $((r>>24)) $((r>>16&255
)) $((r>>8&255)) $((r&255));};for((;(o+${#m})>0;)){ [ "$m" ] || j;while [ "${m:0
:1}" = "z" ];do m=${m:1};printf "\0\0\0\0";done;if [ ${#m} -ge 5 ];then q="${m:0
:5}";m=${m:5};l "$q";printf "$p";elif ((o));then j;elif [ "${m##z*}" ];then pri\
ntf -v t %$((5-${#m}))s;l "$m${t// /u}";printf "${p:0:16-4*${#t}}";m=;fi;}

Copy this in enc85.sh and dec85.sh, chmod +x {enc,dec}85.sh, then:

for string in 'ARTY*' 'FCfN8' '@rGmh+D5V/Ac' ':i^JeEa`g%Bl7Q+:j%)1Ch7Y' ;do
    printf "    %-42s %s\n" "<~$string~>:" "$(./dec85.sh <<<"<~$string~>")"
  done
    <~ARTY*~>:                                 easy
    <~FCfN8~>:                                 test
    <~@rGmh+D5V/Ac~>:                          code golf
    <~:i^JeEa`g%Bl7Q+:j%)1Ch7Y~>:              Programming Puzzles

./enc85.sh <<<'Hello world!'
<~87cURD]j7BEbo80$3~>
./dec85.sh <<<'<~87cURD]j7BEbo80$3~>'
Hello world!

But you could do some stronger test:

ls -ltr --color $HOME/* | gzip | ./enc85.sh | ./dec85.sh | gunzip

Reduced to 724 chars:

printf -v n \\%o {32..126};printf -v n "$n";printf -v m %-20sE abtnvfr;p=\<~
l(){ q=$(($1<<24|$2<<16|$3<<8|$4))
q="${n:1+(q/64#378iN)%85:1}${n:1+(q/614125)%85:1}${n:1+(q/7225)%85:1}${n:1+(q/85)%85:1}${n:1+q%85:1}"
};k() { ((${#p}>74))&&echo "${p:0:75}" && p=${p:75};};while IFS= read -rd '' -n 1 q;do [ "$q" ]&&{
printf -v q "%q" "$q";case ${#q} in 1|2)q=${n%$q*};o+=($((${#q}+32)));;7)q=${q#*\'\\}
o+=($((8#${q%\'})));;5)q=${q#*\'\\};q=${m%${q%\'}*};o+=($((${#q}+07)));;esac;}||o+=(0)
((${#o[@]}>3))&&{ [ "${o[*]}" = "0 0 0 0" ]&&q=z||l ${o[@]};p+="${q}";k
o=();};done;[ "$o" ]&&{ f=0;for((;${#o[@]}<4;)){ o+=(0);((f++));}
((f==0))&&[ "${o[*]}" = "0 0 0 0" ]&&q=z||l ${o[@]};p+="${q:0:5-f}";};p+="~>";k;[ "$p" ]&&echo "$p"

Answer 4

Python 2, 193 162 bytes

from struct import*
i=raw_input()
k=4-len(i)%4&3
i+='\0'*k
o=''
while i:
 b,=unpack('>I',i[-4:]);i=i[:-4]
 while b:o+=chr(b%85+33);b/=85
print'<~%s~>'%o[k:][::-1]

This is my first code golf, so I'm sure there's something wrong with my approach. I also wanted to actually implement base85 rather than just call the library function. :)

Answer 5

Octave, 133 131 bytes

Thanks to @ojdo for suggesting I take input from argv rather than stdin, saving me 2 bytes.

function g(s) p=mod(-numel(s),4);s(end+1:end+p)=0;disp(['<~' dec2base(swapbytes(typecast(s,'uint32')),'!':'u')'(:)'(1:end-p) '~>'])

Ungolfed:

function g(s)             %// function header
p=mod(-numel(s),4);       %// number of missing chars until next multiple of 4
s(end+1:end+p)=0;         %// append p null characters to s
t=typecast(s,'uint32');   %// cast each 4 char block to uint32
u=swapbytes(t);           %// change endian-ness of uint32's
v=dec2base(u,'!':'u');    %// convert to base85
w=v'(:)'(1:end-p);        %// flatten and truncate resulting string
disp(['<~' w '~>']);      %// format and display final result

I've posted the code on ideone. The standalone function doesn't require and end statement, but because ideone has the function and the calling script in the same file it requires a separator.

I still haven't been able to figure out how to get stdin to work on ideone. If anyone knows, I'm still interested, so please drop me a comment.

Sample output from ideone:

easy
<~ARTY*~>
test
<~FCfN8~>
code golf
<~@rGmh+D5V/Ac~>
Programming Puzzles
<~:i^JeEa`g%Bl7Q+:j%)1Ch7Y~>

Answer 6

Matlab, 175 bytes

s=input('','s');m=3-mod(numel(s)-1,4);s=reshape([s zeros(1,m)]',4,[])';t=char(mod(floor(bsxfun(@rdivide,s*256.^[3:-1:0]',85.^[4:-1:0])),85)+33)';t=t(:)';['<~' t(1:end-m) '~>']

Example:

>> s=input('','s');m=3-mod(numel(s)-1,4);s=reshape([s zeros(1,m)]',4,[])';t=char(mod(floor(bsxfun(@rdivide,s*256.^[3:-1:0]',85.^[4:-1:0])),85)+33)';t=t(:)';['<~' t(1:end-m) '~>']
code golf
ans =
<~@rGmh+D5V/Ac~>

Answer 7

PHP, 181 Bytes

foreach(str_split(bin2hex($argn),8)as$v){for($t="",$d=hexdec(str_pad($v,8,0));$d;$d=$d/85^0)$t=chr($d%85+33).$t;$r.=str_replace("!!!!!",z,substr($t,0,1+strlen($v)/2));}echo"<~$r~>";

Online Version

Expanded

foreach(str_split(bin2hex($argn),8)as$v){
    for($t="",$d=hexdec(str_pad($v,8,0));$d;$d=$d/85^0)
      $t=chr($d%85+33).$t;
    $r.=str_replace("!!!!!",z,substr($t,0,1+strlen($v)/2));
}
echo"<~$r~>";

Answer 8

PHP, 171 bytes

foreach(unpack('N*',str_pad($argn,($m=4-($l=strlen($argn))%4&3)+$l,"\0"))as$c){for($a=$c?'':z;$c|0;$c/=85)$a=chr($c%85+33).$a;$b.=$a;}echo'<~',$m?substr($b,0,-$m):$b,'~>';

Try it online!

Answer 9

JavaScript, 314 Bytes

a=>(g="<~",h="~>",r=[],t=0,[...a].map((d,h)=>{if(0==h%4){for(n=0,o=0,f=0,s=[],e=0;4>n;)o=256*o+(a.substr(t,4)+"\0\0\0").substr(0,4).charCodeAt(n),n++;for(;5>f;)e=o%85,o=(o-e)/85,s.unshift(String.fromCharCode(e+33)),f++;r=[...r,...s],t+=4}}),d=4-a.length%4,4!=d&&r.splice(-d,d),g+r.join("").replace(/!!!!!/g,"z")+h)

This is my first code golf :)

Try It‽

<h2>Type Below</h2><input oninput='document.querySelector("p").innerText = (a=>(g="<~",h="~>",r=[],t=0,[...a].map((d,h)=>{if(0==h%4){for(n=0,o=0,f=0,s=[],e=0;4>n;)o=256*o+(a.substr(t,4)+"\0\0\0").substr(0,4).charCodeAt(n),n++;for(;5>f;)e=o%85,o=(o-e)/85,s.unshift(String.fromCharCode(e+33)),f++;r=[...r,...s],t+=4}}),d=4-a.length%4,4!=d&&r.splice(-d,d),g+r.join("").replace(/!!!!!/g,"z")+h))(this.value)'><p>Stuff will go here...</p>

Answer 10

PowerShell, 169 165 162 160 bytes

$ofs=''
"<~$($args-replace'.{1,4}',{$v=$_
&{0..3|%{$n=256*$n+"$v"[$_]}
0..4|%{$r=[char]($n%85+33)+$r;$n-=$n%85;$n/=85}
$r[0..$v.Length]-replace'!!!!!','z'}})~>"

Try it online!

Answer 11

Ruby, 128 114 bytes

$_="<~#{$_.gsub(/.{1,4}/){$&.ljust(4,?\0).unpack1("L>").digits(85).reverse.map{(_1+33).chr}.join[..$&.size-5]}}~>"

Attempt This Online!