[Tool/Example] Write/Read to binary Buffer Demo.

[BorhilIan]

This is a project aimed at visualizing the binary representation of number values. This tool provides a few functions for converting to/from binary and an interactive demo to visualize it in action.

[BorhilIan]

Cleaned up the code and post in general.

[airstruck]

I wrote what I consider to be the most efficient method.

Do you mean efficient in terms of speed, or memory use, or lines of code? Naturally if there's a more efficient method, then this isn't the most efficient method. Do you have any particular rationale for considering it to be the most efficient?

For example, it's pretty well known that string concatenation in Lua is inefficient, and you're doing a lot of it. I suspect if you did less of it, you'd have a more efficient solution. Consider the code I posted in your last thread to get a string of ones and zeros from a number; I suspect if you take the time to benchmark it you'll learn that what you have here is not the most efficient method. Here's that code again:

Code: Select all

local bits = { [0] = '000', '001', '010', '011', '100', '101', '110', '111' }
local function digits (d) return bits[tonumber(d)] end
local function tobits (n) return (('%o'):format(n):gsub('.', digits)) end

That said, building a string of ones and zeros can be avoided entirely, and I suspect avoiding that unnecessary step will result in an even more efficient solution. Here's some code for you to consider:

Code: Select all

local FULL_BYTE = 256
local INV_BYTE = 1 / FULL_BYTE

local char, floor = string.char, math.floor
local tinsert, tconcat = table.insert, table.concat

local function bytesToString (byteArray)
    for i = 1, #byteArray do
        byteArray[i] = char(byteArray[i])
    end
    return tconcat(byteArray) 
end

function smash (ints, bits)
    local out, num = {}, 0
    for i = 1, #bits do
        num = num * 2 ^ bits[i] + (ints[i] or 0)
    end
    while num > 0 do
        out[#out + 1] = num % FULL_BYTE
        num = floor(num * INV_BYTE)
    end
    return bytesToString(out)
end

function unsmash (str, bits)
    local out, num = {}, 0
    for i = #str, 1, -1 do
        num = num * FULL_BYTE + str:byte(i)
    end
    for i = #bits, 1, -1 do
        local mod = 2 ^ bits[i]
        tinsert(out, 1, num % mod)
        num = floor(num / mod)
    end
    return out
end

function smashArray (ints, bits)
    local out, num = {}, 0
    for i = 1, #ints do
        num = num * 2 ^ bits + ints[i]
    end
    while num > 0 do
        out[#out + 1] = num % FULL_BYTE
        num = floor(num * INV_BYTE)
    end
    return bytesToString(out)
end

function unsmashArray (str, bits)
    local out, num = {}, 0
    for i = #str, 1, -1 do
        num = num * FULL_BYTE + str:byte(i)
    end
    while num > 0 do
        local mod = 2 ^ bits
        tinsert(out, 1, num % mod)
        num = floor(num / mod)
    end
    return out
end

The first pair of functions take as the second argument an array of bit-lengths, one for each field. The second pair is almost identical except they take a single number of bits to use for every field. I just now wrote these up and have only had time to test that they work, but haven't written any benchmarks.

I'm looking for ways to not only improve this Demo/Tool but also the explanation of it on this post, please post some below.

Well, here you go. You mentioned efficiency; you can check how this compares to your solution with some quick benchmarks. If you plan on using LuaJIT, you can substitute bitwise operations for some of the arithmetic and see how that stacks up as well. Looking forward to hearing the results.

[BorhilIan]

I see what you mean, I'll definitely benchmark the various methods I've considered and the one you've provided.

[BorhilIan]

Just did a basic benchmark and your method is considerably faster. Seems the optimal setup is assembling the numbers into tables like in your test. However changing out the '..' for a single 'table.concat' in my function yielded no noticeable change whatsoever. Nor did localizing the function like in your above code.

Here is the 'main.lua' I used for my bench-marking, I removed the localization of functions because it didn't have a noticeable effect.

Code: Select all

--	Temp values for the test function.
local A , B , C

--	TEST ALPHA

if ( true ) then

	--	The function that converts a number value into a string of zeroes and ones.
	local function tobinary( n , bits )
		local n = math.abs( n )
		local s = ""
		local b
		while ( n > 0 ) do
			b = math.fmod( n , 2 )
			s = b .. s
			n = ( n - b ) / 2
		end
		if ( bits ) then
			local l = string.len( s )
			if ( l > bits ) then
				return string.sub( s , ( l + 1 ) - bits )
			elseif ( l < bits ) then
				return string.rep( '0' , bits - l ) .. s
			end
		end
		return s
	end
	--	Compile a binary string of zeroes and ones into a proper string.
	--	NOTE: Each character represents up to 8 bits, no extra padding or spacing is inserted in the string.
	--	NOTE: To read binary from the compiled string it will first need to be decompiled, function below.
	local function compile( binary )
		local output = ""
		for i = 1 , string.len( binary ) , 8 do
			--	Just a formality we are reading 8-bits or one char at a time
			local bin = string.sub( binary , i , i + 7 )
			--	Make sure that binary will be appropriate
			if ( string.len( bin ) < 8 ) then
				bin = bin .. string.rep( '0' , 8 - string.len( bin ) )
			end
			--	Convert the bits to an actual number within byte range.
			local byte = tonumber( bin , 2 )
			--	Get the character that represent the above byte.
			local char = string.char( byte )
			--	Append char to the output string.
			output = output .. char
		end
		return output
	end
	--	Compile a binary string of zeroes and ones from a normal string.
	local function decompile( str )
		local binary = ""
		for i = 1 , string.len( str ) do
			--	Convert the char into a byte.
			local byte = string.byte( string.sub( str , i , i ) )
			--	Convert that byte into binary.
			local bin = tobinary( byte , 8 )
			--	Append the bits to the buffer.
			binary = binary .. bin
		end
		return binary
	end
	--	Print a simple test of the above functions combined.
	function test1()
		A = tobinary( 47 , 6 ) .. tobinary( 13 , 6 ) .. tobinary( 255 , 8 ) .. tobinary( 4 , 5 ) .. tobinary( 3 , 2 )
		B = compile( A )
		C = decompile( B )
	end

end

--	TEST BRAVO

if ( true ) then

	--	The function that converts a number value into a string of zeroes and ones.
	local function tobinary( n , bits )
		local n = math.abs( n )
		local s = ""
		local b
		while ( n > 0 ) do
			b = math.fmod( n , 2 )
			s = b .. s
			n = ( n - b ) / 2
		end
		if ( bits ) then
			local l = string.len( s )
			if ( l > bits ) then
				return string.sub( s , ( l + 1 ) - bits )
			elseif ( l < bits ) then
				return string.rep( '0' , bits - l ) .. s
			end
		end
		return s
	end
	--	Compile a binary string of zeroes and ones into a proper string.
	--	NOTE: Each character represents up to 8 bits, no extra padding or spacing is inserted in the string.
	--	NOTE: To read binary from the compiled string it will first need to be decompiled, function below.
	local function compile( binary )
		local output = {}
		for i = 1 , string.len( binary ) , 8 do
			--	Just a formality we are reading 8-bits or one char at a time
			local bin = string.sub( binary , i , i + 7 )
			--	Make sure that binary will be appropriate
			if ( string.len( bin ) < 8 ) then
				bin = bin .. string.rep( '0' , 8 - string.len( bin ) )
			end
			--	Convert the bits to an actual number within byte range.
			local byte = tonumber( bin , 2 )
			--	Get the character that represent the above byte.
			local char = string.char( byte )
			--	Append char to the output string.
			table.insert( output , char )
		end
		return table.concat( output )
	end
	--	Compile a binary string of zeroes and ones from a normal string.
	local function decompile( str )
		local binary = {}
		for i = 1 , string.len( str ) do
			--	Convert the char into a byte.
			local byte = string.byte( string.sub( str , i , i ) )
			--	Convert that byte into binary.
			local bin = tobinary( byte , 8 )
			--	Append the bits to the buffer.
			table.insert( binary , bin )
		end
		return table.concat( binary )
	end
	--	Print a simple test of the above functions combined.
	function test2()
		A = table.concat{ tobinary( 47 , 6 ) , tobinary( 13 , 6 ) , tobinary( 255 , 8 ) , tobinary( 4 , 5 ) , tobinary( 3 , 2 ) }
		B = compile( A )
		C = decompile( B )
	end

end

--	TEST CHARLIE

if ( true ) then

	local FULL_BYTE = 256
	local INV_BYTE = 1 / FULL_BYTE
	local function bytesToString (byteArray)
		for i = 1, #byteArray do
			byteArray[i] = string.char(byteArray[i])
		end
		return table.concat(byteArray) 
	end
	function smash (ints, bits)
		local out, num = {}, 0
		for i = 1, #bits do
			num = num * 2 ^ bits[i] + (ints[i] or 0)
		end
		while num > 0 do
			out[#out + 1] = num % FULL_BYTE
			num = math.floor(num * INV_BYTE)
		end
		return bytesToString(out)
	end
	function unsmash (str, bits)
		local out, num = {}, 0
		for i = #str, 1, -1 do
			num = num * FULL_BYTE + str:byte(i)
		end
		for i = #bits, 1, -1 do
			local mod = 2 ^ bits[i]
			table.insert(out, 1, num % mod)
			num = math.floor(num / mod)
		end
		return out
	end
	function smashArray (ints, bits)
		local out, num = {}, 0
		for i = 1, #ints do
			num = num * 2 ^ bits + ints[i]
		end
		while num > 0 do
			out[#out + 1] = num % FULL_BYTE
			num = math.floor(num * INV_BYTE)
		end
		return bytesToString(out)
	end
	function unsmashArray (str, bits)
		local out, num = {}, 0
		for i = #str, 1, -1 do
			num = num * FULL_BYTE + str:byte(i)
		end
		while num > 0 do
			local mod = 2 ^ bits
			table.insert(out, 1, num % mod)
			num = math.floor(num / mod)
		end
		return out
	end
	--	Print a simple test of the above functions combined.
	function test3()
		A = smash( {47,13,255,4,3} , {6,6,8,5,2} )
		B = unsmash( A , {6,6,8,5,2} )
	end

end

--	TESTER

function love.load()
	for i = 1 , 8 do
		print()
	end
	print( "BRAVO:" )
	for z = 1 , 5 do
		local start = love.timer.getTime()
		for x = 1 , 3 do
			for y = 1 , 24 do
				test2()
			end
		end
		print( ' ' , love.timer.getTime() - start )
	end
	print( "CHARLIE:" )
	for z = 1 , 5 do
		local start = love.timer.getTime()
		for x = 1 , 3 do
			for y = 1 , 24 do
				test3()
			end
		end
		print( ' ' , love.timer.getTime() - start )
	end
	print( "ALPHA:" )
	for z = 1 , 5 do
		local start = love.timer.getTime()
		for x = 1 , 3 do
			for y = 1 , 24 do
				test1()
			end
		end
		print( ' ' , love.timer.getTime() - start )
	end
end

Will rework my Buffer Example to include your 'smash' and 'unsmash' functions, will still keep the binary buffer to visualize information.

[airstruck]

Very nice, will run these when I get a chance.

I started refactoring the code a bit, this version is completely untested but feel free to use it for whatever you want. I may work on it some more later, can be improved by using lshift and rshift where available and falling back to the thing it does now.

https://gist.github.com/airstruck/75126 ... 8290045ad8

[BorhilIan]

Had some issues working out your code on that github link as it errors, however I updated my little program. It now separates the binary into the 8-bit (byte) groupings for each string character. And the number entry now accepts keypad input and clamps values to reasonable ranges. The buffer also shows a maximum of 256 bits though it can still handle more than that in the Write/Read.