Base Sixty Four

wiki

Since the last implementation, I had a small competition for the smallest Base64 codec in JavaScript? - converting the new results to lua gave the following, very small as fast codec:

#!/usr/bin/env lua
-- Lua 5.1+ base64 v3.0 (c) 2009 by Alex Kloss <alexthkloss@web.de>
-- licensed under the terms of the LGPL2

-- character table string
local b='ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'

-- encoding
function enc(data)
    return ((data:gsub('.', function(x) 
        local r,b='',x:byte()
        for i=8,1,-1 do r=r..(b%2^i-b%2^(i-1)>0 and '1' or '0') end
        return r;
    end)..'0000'):gsub('%d%d%d?%d?%d?%d?', function(x)
        if (#x < 6) then return '' end
        local c=0
        for i=1,6 do c=c+(x:sub(i,i)=='1' and 2^(6-i) or 0) end
        return b:sub(c+1,c+1)
    end)..({ '', '==', '=' })[#data%3+1])
end

-- decoding
function dec(data)
    data = string.gsub(data, '[^'..b..'=]', '')
    return (data:gsub('.', function(x)
        if (x == '=') then return '' end
        local r,f='',(b:find(x)-1)
        for i=6,1,-1 do r=r..(f%2^i-f%2^(i-1)>0 and '1' or '0') end
        return r;
    end):gsub('%d%d%d?%d?%d?%d?%d?%d?', function(x)
        if (#x ~= 8) then return '' end
        local c=0
        for i=1,8 do c=c+(x:sub(i,i)=='1' and 2^(8-i) or 0) end
        return string.char(c)
    end))
end

-- command line if not called as library
if (arg ~= nil) then
	local func = 'enc'
	for n,v in ipairs(arg) do
		if (n > 0) then
			if (v == "-h") then print "base64.lua [-e] [-d] text/data" break
			elseif (v == "-e") then func = 'enc'
			elseif (v == "-d") then func = 'dec'
			else print(_G[func](v)) end
		end
	end
else
	module('base64',package.seeall)
end

Base64 is also implemented in the b64/unb64 methods in LuaSocket? ([1]), but you may still want to use this snippet for its few requirements -- and it is a nice example with educational value for how to perform logical operations without actual bit-shift or OR operators.

I want to apologize if somebody encountered a serious error with the former version of base64 - Not all logical functions can be easily replaced with mathematical ones, so I had to find a way around. The following code is not as fast as the mime C-Module - yet on smaller values the loading time can make a program slower, too. Find the newest (and corrected) version here:

#!/usr/bin/env lua
-- working lua base64 codec (c) 2006-2008 by Alex Kloss
-- compatible with lua 5.1
-- http://www.it-rfc.de
-- licensed under the terms of the LGPL2

-- bitshift functions (<<, >> equivalent)
-- shift left
function lsh(value,shift)
	return (value*(2^shift)) % 256
end

-- shift right
function rsh(value,shift)
	return math.floor(value/2^shift) % 256
end

-- return single bit (for OR)
function bit(x,b)
	return (x % 2^b - x % 2^(b-1) > 0)
end

-- logic OR for number values
function lor(x,y)
	result = 0
	for p=1,8 do result = result + (((bit(x,p) or bit(y,p)) == true) and 2^(p-1) or 0) end
	return result
end

-- encryption table
local base64chars = {[0]='A',[1]='B',[2]='C',[3]='D',[4]='E',[5]='F',[6]='G',[7]='H',[8]='I',[9]='J',[10]='K',[11]='L',[12]='M',[13]='N',[14]='O',[15]='P',[16]='Q',[17]='R',[18]='S',[19]='T',[20]='U',[21]='V',[22]='W',[23]='X',[24]='Y',[25]='Z',[26]='a',[27]='b',[28]='c',[29]='d',[30]='e',[31]='f',[32]='g',[33]='h',[34]='i',[35]='j',[36]='k',[37]='l',[38]='m',[39]='n',[40]='o',[41]='p',[42]='q',[43]='r',[44]='s',[45]='t',[46]='u',[47]='v',[48]='w',[49]='x',[50]='y',[51]='z',[52]='0',[53]='1',[54]='2',[55]='3',[56]='4',[57]='5',[58]='6',[59]='7',[60]='8',[61]='9',[62]='-',[63]='_'}

-- function encode
-- encodes input string to base64.
function enc(data)
	local bytes = {}
	local result = ""
	for spos=0,string.len(data)-1,3 do
		for byte=1,3 do bytes[byte] = string.byte(string.sub(data,(spos+byte))) or 0 end
		result = string.format('%s%s%s%s%s',result,base64chars[rsh(bytes[1],2)],base64chars[lor(lsh((bytes[1] % 4),4), rsh(bytes[2],4))] or "=",((#data-spos) > 1) and base64chars[lor(lsh(bytes[2] % 16,2), rsh(bytes[3],6))] or "=",((#data-spos) > 2) and base64chars[(bytes[3] % 64)] or "=")
	end
	return result
end

-- decryption table
local base64bytes = {['A']=0,['B']=1,['C']=2,['D']=3,['E']=4,['F']=5,['G']=6,['H']=7,['I']=8,['J']=9,['K']=10,['L']=11,['M']=12,['N']=13,['O']=14,['P']=15,['Q']=16,['R']=17,['S']=18,['T']=19,['U']=20,['V']=21,['W']=22,['X']=23,['Y']=24,['Z']=25,['a']=26,['b']=27,['c']=28,['d']=29,['e']=30,['f']=31,['g']=32,['h']=33,['i']=34,['j']=35,['k']=36,['l']=37,['m']=38,['n']=39,['o']=40,['p']=41,['q']=42,['r']=43,['s']=44,['t']=45,['u']=46,['v']=47,['w']=48,['x']=49,['y']=50,['z']=51,['0']=52,['1']=53,['2']=54,['3']=55,['4']=56,['5']=57,['6']=58,['7']=59,['8']=60,['9']=61,['-']=62,['_']=63,['=']=nil}

-- function decode
-- decode base64 input to string
function dec(data)
	local chars = {}
	local result=""
	for dpos=0,string.len(data)-1,4 do
		for char=1,4 do chars[char] = base64bytes[(string.sub(data,(dpos+char),(dpos+char)) or "=")] end
		result = string.format('%s%s%s%s',result,string.char(lor(lsh(chars[1],2), rsh(chars[2],4))),(chars[3] ~= nil) and string.char(lor(lsh(chars[2],4), rsh(chars[3],2))) or "",(chars[4] ~= nil) and string.char(lor(lsh(chars[3],6) % 192, (chars[4]))) or "")
	end
	return result
end

-- command line if not called as library
if (arg ~= nil) then
	local func = 'enc'
	for n,v in ipairs(arg) do
		if (n > 0) then
			if (v == "-h") then print "base64.lua [-e] [-d] text/data" break
			elseif (v == "-e") then func = 'enc'
			elseif (v == "-d") then func = 'dec'
			else print(_G[func](v)) end
		end
	end
else
	module('base64',package.seeall)
end

See also the same version but compatible with lua 5.0.

-- working lua base64 codec (c) 2006-2008 by Alex Kloss
-- compatible with lua 5.0
-- http://www.it-rfc.de
-- licensed under the terms of the LGPL2

-- bitshift functions (<<, >> equivalent)
-- shift left
function lsh(value,shift)
	return math.mod((value*(2^shift)), 256)
end

-- shift right
function rsh(value,shift)
	return math.mod(math.floor(value/2^shift), 256)
end

-- return single bit (for OR)
function bit(x,b)
	return (math.mod(x, 2^b) - math.mod(x, 2^(b-1)) > 0)
end

-- logic OR for number values
function lor(x,y)
	result = 0
	for p=1,8 do result = result + (((bit(x,p) or bit(y,p)) == true) and 2^(p-1) or 0) end
	return result
end

-- encryption table
local base64chars = {[0]='A',[1]='B',[2]='C',[3]='D',[4]='E',[5]='F',[6]='G',[7]='H',[8]='I',[9]='J',[10]='K',[11]='L',[12]='M',[13]='N',[14]='O',[15]='P',[16]='Q',[17]='R',[18]='S',[19]='T',[20]='U',[21]='V',[22]='W',[23]='X',[24]='Y',[25]='Z',[26]='a',[27]='b',[28]='c',[29]='d',[30]='e',[31]='f',[32]='g',[33]='h',[34]='i',[35]='j',[36]='k',[37]='l',[38]='m',[39]='n',[40]='o',[41]='p',[42]='q',[43]='r',[44]='s',[45]='t',[46]='u',[47]='v',[48]='w',[49]='x',[50]='y',[51]='z',[52]='0',[53]='1',[54]='2',[55]='3',[56]='4',[57]='5',[58]='6',[59]='7',[60]='8',[61]='9',[62]='-',[63]='_'}

-- function encode
-- encodes input string to base64.
function enc(data)
	local bytes = {}
	local result = ""
	for spos=0,string.len(data)-1,3 do
		for byte=1,3 do bytes[byte] = string.byte(string.sub(data,(spos+byte))) or 0 end
		result = string.format('%s%s%s%s%s',
			result,
			base64chars[rsh(bytes[1],2)],
			base64chars[lor(lsh((math.mod(bytes[1], 4)),4), rsh(bytes[2],4))] or "=",
			((string.len(data)-spos) > 1) and base64chars[lor(lsh(
				math.mod(bytes[2], 16)
			,2), rsh(bytes[3],6))] or "=",
			((string.len(data)-spos) > 2) and base64chars[(math.mod(bytes[3], 64))] or "="
		)
	end
	return result
end

-- decryption table
local base64bytes = {['A']=0,['B']=1,['C']=2,['D']=3,['E']=4,['F']=5,['G']=6,['H']=7,['I']=8,['J']=9,['K']=10,['L']=11,['M']=12,['N']=13,['O']=14,['P']=15,['Q']=16,['R']=17,['S']=18,['T']=19,['U']=20,['V']=21,['W']=22,['X']=23,['Y']=24,['Z']=25,['a']=26,['b']=27,['c']=28,['d']=29,['e']=30,['f']=31,['g']=32,['h']=33,['i']=34,['j']=35,['k']=36,['l']=37,['m']=38,['n']=39,['o']=40,['p']=41,['q']=42,['r']=43,['s']=44,['t']=45,['u']=46,['v']=47,['w']=48,['x']=49,['y']=50,['z']=51,['0']=52,['1']=53,['2']=54,['3']=55,['4']=56,['5']=57,['6']=58,['7']=59,['8']=60,['9']=61,['-']=62,['_']=63,['=']=nil}

-- function decode
-- decode base64 input to string
function dec(data)
	local chars = {}
	local result=""
	for dpos=0,string.len(data)-1,4 do
		for char=1,4 do chars[char] = base64bytes[(string.sub(data,(dpos+char),(dpos+char)) or "=")] end
		result = string.format('%s%s%s%s',
			result,
			string.char(lor(lsh(chars[1],2), rsh(chars[2],4))),
			(chars[3] ~= nil) and string.char(lor(lsh(chars[2],4), rsh(chars[3],2))) or "",
			(chars[4] ~= nil) and string.char(lor(math.mod(lsh(chars[3],6), 192), (chars[4]))) or ""
		)
	end
	return result
end

-- command line if not called as library
if (arg ~= nil) then
	local func = 'enc'
	for n,v in ipairs(arg) do
		if (n > 0) then
			if (v == "-h") then print "base64.lua [-e] [-d] text/data" break
			elseif (v == "-e") then func = 'enc'
			elseif (v == "-d") then func = 'dec'
			else print(_G[func](v)) end
		end
	end
else
	module('base64',package.seeall)
end

On a further notice, I received a mail from someone using my code without acknowledgement of my copyright and license. If you need another license as explicitly stated in the code, feel free to contact me on my email address.

Using binary operators in Lua 5.3

I wrote the snippet below today to speed up the base64 encoding in my application using the new binary operators in Lua5.3, it might be of use for others. I think the algorithm is pretty much optimal, but I'm open to any suggestions and improvements.

Every three input bytes are mapped to four output bytes using the binary operations below:

        
         a                   b                   c
  +-----------------+-----------------+-----------------+
  | 0 0 0 0 0 0 1 1 | 1 1 1 1 2 2 2 2 | 2 2 3 3 3 3 3 3 |
  +|- - - - - -|- - + - - - -|- - - - + - -|- - - - - -|+
  /           /              |              \           \
 /           /               |               \           \
     a>>2     (a&3)<<4|b>>4    (b&15)<<2|c>>6      c&63

The input is padded to always be a multiple of three bytes, the output padding with '='s is fixed up after calculating the base64 of the padded input string.

local bs = { [0] =
   'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P',
   'Q','R','S','T','U','V','W','X','Y','Z','a','b','c','d','e','f',
   'g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v',
   'w','x','y','z','0','1','2','3','4','5','6','7','8','9','+','/',
}

local function base64(s)
   local byte, rep = string.byte, string.rep
   local pad = 2 - ((#s-1) % 3)
   s = (s..rep('\0', pad)):gsub("...", function(cs)
      local a, b, c = byte(cs, 1, 3)
      return bs[a>>2] .. bs[(a&3)<<4|b>>4] .. bs[(b&15)<<2|c>>6] .. bs[c&63]
   end)
   return s:sub(1, #s-pad) .. rep('=', pad)
end


assert(base64("") == "")
assert(base64("f") == "Zg==")
assert(base64("fo") == "Zm8=")
assert(base64("foo") == "Zm9v")
assert(base64("foob") == "Zm9vYg==")
assert(base64("fooba") == "Zm9vYmE=")
assert(base64("foobar") == "Zm9vYmFy")

See Also

• [ee5_base64] faster natural Lua 5.2 base64 encoding/decoding
• [lbase64] lhf's lbase64 library (Lua library implemented in C)
• [luasocket/mime.html#b64] base64 in LuaSocket? (Lua library implemented in C)
• http://libb64.sourceforge.net/ is a fast, public domain base64 encoder/decoder. It's implemented in a coroutine-like style in C. Something similar might be done in Lua, perhaps using real coroutines, or you could bind directly to this library (or just use the base64 routines in luasocket mentioned above).
• Lua/APR provides [base64 encoding and decoding functions] (wraps APR functions in C).
• RiscluaExamples shows base64 encoding/decoding functions in RiscLua. This might be of interest syntactically: RiscLua adds bit-twiddling operators (&, |, ^^, ~, >>, <<) to the VM. \ and => are alternatives for function and return.