Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- --BASE FUNCTIONS
- local huffman = _G.huffman or {}
- function dequeue(buff)
- os.sleep(0)
- if buff.next then
- buff.next()
- end
- local val = buff[1]
- if #buff <= 1 then
- buff[1] = nil
- return val
- else
- for i=2,#buff do
- buff[i-1] = buff[i]
- buff[i] = nil
- end
- end
- return val
- end
- function enqueue(tab,data,ind)
- if ind then
- for i=#tab,ind,-1 do
- tab[i+1] = tab[i]
- end
- else
- ind = #tab+1
- end
- tab[ind] = data
- end
- function insertOrder(data,tab,valueFunc)
- local n_val = valueFunc(data)
- for i2=1,#tab do
- local val = valueFunc(tab[i2])
- if n_val <= val then
- enqueue(tab,data,i2)
- return
- end
- end
- enqueue(tab,data)
- end
- function sort(tab,valueFunc)
- local tab2 = {}
- for i,v in pairs(tab) do
- tab2[i] = v
- end
- for i=1,#tab do
- tab[i] = nil
- end
- for i=1,#tab2 do
- local data = tab2[i]
- insertOrder(data,tab,valueFunc)
- end
- end
- function makeLeaf(freq,char)
- local leaf = {}
- leaf.freq = freq
- leaf.char = char
- return leaf
- end
- function isLeaf(leaf)
- return leaf.char ~= nil
- end
- function makeNode(n_l1,n_l2)
- local node = {}
- node.freq = n_l1.freq + n_l2.freq
- node.left = n_l1
- node.right = n_l2
- print("Node made")
- return node
- end
- function getFreq(node)
- return node.freq
- end
- function makeCharBitTable_node(node,tbl,base)
- if isLeaf(node) then
- tbl[node.char] = base
- return
- end
- local m_base1 = {}
- local m_base2 = {}
- for i=1,#base do
- m_base1[i] = base[i]
- m_base2[i] = base[i]
- end
- m_base1[#base+1] = 0
- m_base2[#base+1] = 1
- makeCharBitTable_node(node.left,tbl,m_base1)
- makeCharBitTable_node(node.right,tbl,m_base2)
- end
- function makeCharBitTable(node_tree)
- print(node_tree)
- local tbl = {}
- makeCharBitTable_node(node_tree.left,tbl,{0})
- makeCharBitTable_node(node_tree.right,tbl,{1})
- return tbl
- end
- huffman.checkNodeTable = makeCharBitTable
- function make_table(txt)
- local tab = {}
- for chr in txt:gmatch(".") do
- tab[chr] = (tab[chr] or 0) + 1
- end
- return tab
- end
- function sort_huffman_table(tab)
- while #tab > 1 do
- sort(tab,getFreq)
- --print(textutils.serialize(tab))
- local n1 = dequeue(tab)
- --print("node1: "..textutils.serialize(n1))
- local n2 = dequeue(tab)
- --print("node2: "..textutils.serialize(n2))
- --print(#tab)
- local n3 = makeNode(n1,n2)
- --print("Node3: "..textutils.serialise(n3))
- --print(textutils.serialise(tab))
- insertOrder(n3,tab,getFreq)
- end
- return tab
- end
- function make_huffman_table(txt)
- local tab = make_table(txt)
- --print(#tab)
- local nodeTable = {}
- for chr,freq in pairs(tab) do
- nodeTable[#nodeTable+1] = makeLeaf(freq,chr)
- end
- --print(textutils.serialize(nodeTable))
- sort_huffman_table(nodeTable)
- return nodeTable[1]
- end
- function decode_node(node_base,bits)
- --print("NodeBase: "..textutils.serialize(node_base or {}))
- local m_bit = dequeue(bits)
- --print("Bit: "..m_bit)
- local m_node = nil
- if m_bit == 0 then
- m_node = node_base.left
- --print("Node: "..textutils.serialize(m_node))
- else
- m_node = node_base.right
- end
- if isLeaf(m_node) then
- --print("IS a leaf")
- return m_node.char
- else
- return decode_node(m_node,bits)
- end
- end
- function decode(node_tree,bits_str,has_table)
- local bits_appended = {}
- function bits_appended.next()
- if #bits_appended == 0 then
- local chr_bits = bit.table(string.byte(bits_str:sub(1,1)))
- bits_str = bits_str:sub(2)
- for i=1,8 do
- bits_appended[#bits_appended+1] = chr_bits[i]
- end
- end
- end
- print("DEPEND")
- local bits = huffman.depend(bits_appended)
- print("DEPENDED")
- if has_table then
- node_tree = huffman.unserializeTree(bits)
- end
- local txt = ""
- while #bits > 0 do
- txt = txt..decode_node(node_tree,bits)
- end
- return txt
- end
- function encode(node_tree,txt,addTree)
- local chartbl = {}
- local nodeCharTable = makeCharBitTable(node_tree,chartbl)
- for i,v in pairs(nodeCharTable) do
- write(i)
- print(unpack(v))
- end
- for chr in string.gmatch(txt,".") do
- chartbl[#chartbl+1] = nodeCharTable[chr]
- end
- local end_table = {}
- local function m_unpack(tbl)
- for i=1,#tbl do
- end_table[#end_table+1] = tbl[i]
- end
- end
- if addTree == true then
- huffman.serializeTree(node_tree,end_table)
- end
- for i=1,#chartbl do
- m_unpack(chartbl[i])
- end
- local tbl = huffman.append(end_table)
- local enc_str = ""
- for i=1,(#tbl/8) do
- local byte_bits = {}
- for i2=1,8 do
- byte_bits[i2] = tbl[(8*(i-1))+i2]
- end
- enc_str = enc_str..string.char(bit.untable(byte_bits))
- end
- print("Returned")
- return tbl,enc_str
- end
- huffman.decode = decode
- huffman.makeTable = make_huffman_table
- huffman.encode = encode
- --FUNCTIONS For bit Resizing
- function huffman.append(bit_tbl)
- local needed = 8 - (#bit_tbl%8)
- if needed == 8 then
- needed = 0
- else
- for i=1,needed do
- bit_tbl[#bit_tbl+1] = 0
- end
- end
- local num_tbl = bit.table(needed)
- for i=1,#num_tbl do
- bit_tbl[#bit_tbl+1] = num_tbl[i]
- end
- return bit_tbl
- end
- function huffman.depend(bit_tbl)
- print("Bit table"..tostring(bit_tbl))
- local needed_bits = {}
- for i=0,7 do
- needed_bits[8-i] = bit_tbl[#bit_tbl]
- bit_tbl[#bit_tbl] = nil
- end
- local needed = bit.untable(needed_bits)
- if needed ~= 0 then
- for i=1,needed do
- bit_tbl[#bit_tbl] = nil
- end
- end
- return bit_tbl
- end
- function bitPrint(bitTbl)
- for i=1,#bitTbl do
- write(bitTbl[i].."\t")
- end
- print()
- end
- huffman.printBit = bitPrint
- --FUNCTIONS For bit manipulation
- function bit_table(num)
- local tab = {}
- for i=1,8 do
- if (num % 2) == 1 then
- tab[9-i] = 1
- num = num - 1
- else
- tab[9-i] = 0
- end
- num = num / 2
- end
- return tab
- end
- function bit_untable(tab)
- local num = 0
- for i=1,8 do
- num = num * 2
- num = num + tab[i]
- end
- return num
- end
- _G.bit.table = bit_table
- _G.bit.untable = bit_untable
- --FUNCTIONS For tree serialization
- function add(buff,val)
- buff[#buff+1] = val
- end
- function addLeaf(leaf,buff)
- local chr = leaf.char
- add(buff,1)
- for i,v in pairs(bit.table(string.byte(chr))) do
- add(buff,v)
- end
- end
- function addNode(node,buff)
- add(buff,0)
- if isLeaf(node.left) then
- addLeaf(node.left,buff)
- else
- addNode(node.left,buff)
- end
- if isLeaf(node.right) then
- addLeaf(node.right,buff)
- else
- addNode(node.right,buff)
- end
- end
- function huffman.serializeTree(tree,buff)
- buff = buff or {}
- addNode(tree,buff)
- return buff
- end
- function unserializeLeaf(buff)
- local leaf = {}
- local chr_bits = {}
- for i=1,8 do
- chr_bits[i] = dequeue(buff)
- end
- leaf.char = string.char(bit.untable(chr_bits))
- return leaf
- end
- function unserializeNode(buff)
- local node = {}
- local n_bit = dequeue(buff)
- if n_bit == 1 then
- node.left = unserializeLeaf(buff)
- else
- node.left = unserializeNode(buff)
- end
- n_bit = dequeue(buff)
- if n_bit == 1 then
- node.right = unserializeLeaf(buff)
- else
- node.right = unserializeNode(buff)
- end
- return node
- end
- function huffman.unserializeTree(buff)
- dequeue(buff)
- return unserializeNode(buff)
- end
- _G.huffman = huffman
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement