Advertisement
Guest User

Compression algorithms in lua

a guest
May 24th, 2016
230
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Lua 8.66 KB | None | 0 0
  1. --localization--
  2. local fInsert = table.insert
  3. local fRemove = table.remove
  4. local fConcat = table.concat
  5. local fFloor = math.floor
  6. local fChar = string.char
  7. local fSort = table.sort
  8. local fMax = math.max
  9.  
  10.  
  11. --variables--
  12. local tHex = {[0]="0",[1]="1",[2]="2",[3]="3",[4]="4",[5]="5",[6]="6",[7]="7",[8]="8",[9]="9",[10]="a",[11]="b",[12]="c",[13]="d",[14]="e",[15]="f",[16]=" "}
  13. local tDec = {["0"]=0,["1"]=1,["2"]=2,["3"]=3,["4"]=4,["5"]=5,["6"]=6,["7"]=7,["8"]=8,["9"]=9,["a"]=10,["b"]=11,["c"]=12,["d"]=13,["e"]=14,["f"]=15,[" "]=16}
  14. local tMTFTable = {} --this will be a table of all bytes 0-255
  15.  
  16.  
  17. --basic functions--
  18.  
  19. local function fSetBits(tData, sCurrBit, sThisBit, bInternal)--converts frequency tree to bits for huffman
  20.     local tSet
  21.  
  22.     sCurrBit = sCurrBit or ""
  23.     sThisBit = sThisBit or "0"
  24.    
  25.     local tSolution = {}
  26.     if type(tData.contains)=="table"    then
  27.         tSet = fSetBits(tData.contains[1],sCurrBit..(bInternal and sThisBit or ""),1,true)
  28.         for k,v in next,tSet  do
  29.             tSolution[k] = v
  30.         end
  31.         tSet = fSetBits(tData.contains[2],sCurrBit..(bInternal and sThisBit or ""),0,true)
  32.         for k,v in next,tSet  do
  33.             tSolution[k] = v
  34.         end
  35.     else
  36.         tSolution[tData.contains]=sCurrBit..sThisBit
  37.     end
  38.     return tSolution
  39. end
  40.  
  41. local function fTblHexToDec(tData) --converts all hex characters to decimal numbers
  42.     for k,v in ipairs(tData) do
  43.         tData[k] = tDec[v]
  44.     end
  45.     return tData
  46. end
  47.  
  48. local function fTblCharToDec(tData) --converts all text to decimal in a table
  49.     for k,v in next, tData do
  50.         tData[k] = v:byte()
  51.     end
  52.     return tData
  53. end
  54.  
  55. --next two reverse the above two
  56. local function fTblDecToHex(tData)
  57.     for k,v in next, tData do
  58.         tData[k] = tHex[v]
  59.     end
  60.     return tData
  61. end
  62.  
  63. local function fTblDecToChar(tData)
  64.     for k,v in ipairs(tData) do
  65.         tData[k] = fChar(v)
  66.     end
  67.     return tData
  68. end
  69.  
  70. local function fShallowCopy(tData) --makes a shallow copy of a table changing pointers
  71.     local tOutput = {}
  72.     for k,v in ipairs(tData) do
  73.         tOutput[k] = v
  74.     end
  75.     return tOutput
  76. end
  77.  
  78. local function fIsEqual(tA,tB) --checks if tables contain the same data
  79.     for i=1,#tA do
  80.         if tA[i]~=tB[i] then
  81.             return false
  82.         end
  83.     end
  84.     return #tA==#tB
  85. end
  86.  
  87. local function fLexTblSort(tA,tB) --sorter for tables
  88.     for i=1,#tA do
  89.         if tA[i]~=tB[i] then
  90.             return tA[i]<tB[i]
  91.         end
  92.     end
  93.     return false
  94. end
  95.  
  96. local function fDecToBin(iNum)--convert base 10 to base 2
  97.     if iNum==0 then
  98.         return "00000000" --0 needs a special handle
  99.     end
  100.     local tBinary = {}
  101.     while iNum > 0 do
  102.         fInsert(tBinary,1,iNum%2)
  103.         iNum=fFloor(iNum/2)
  104.     end
  105.     return (#tBinary%8>0 and ("0"):rep(8-#tBinary%8) or "")..fConcat(tBinary)
  106. end
  107.  
  108.  
  109. --BWT functions--
  110. local function fBWT(tData)
  111.  
  112.     --setup--
  113.     local iSize = #tData
  114.     local tSolution = {}
  115.     local tSolved = {}
  116.    
  117.    
  118.     --key table--
  119.     for n=1,iSize do
  120.         tData[iSize] = fRemove(tData,1)
  121.         tSolution[n] = fShallowCopy(tData)
  122.     end
  123.     table.sort(tSolution,fLexTblSort)
  124.    
  125.    
  126.     --encode output--
  127.     for i=1,iSize do
  128.         tSolved[i] = tSolution[i][iSize]
  129.     end
  130.    
  131.    
  132.     --finalize--
  133.     for i=1,iSize do
  134.         if fIsEqual(tSolution[i],tData) then
  135.             return i,tSolved
  136.         end
  137.     end
  138.     return false
  139. end
  140.  
  141. local function fUnBWT(iPointer,tData)
  142.  
  143.     --setup--
  144.     local tSolution = {}
  145.     local iLen = #tData
  146.    
  147.    
  148.     --decode--
  149.     for _=1,iLen do
  150.         for i=1,iLen do
  151.             if not tSolution[i] then
  152.                 tSolution[i] = {} --prevent an error
  153.             end
  154.             fInsert(tSolution[i],1,tData[i]) --insert each entry into each column
  155.         end
  156.         table.sort(tSolution,fLexTblSort) --sort after each set of adds
  157.     end
  158.    
  159.    
  160.     --finalize--
  161.     return tSolution[iPointer]
  162. end
  163.  
  164.  
  165. --MTF functions--
  166. local function fFlushMTF() --reset the MTF table for handling
  167.     for i=0,255 do
  168.         tMTFTable[i+1] = i
  169.     end
  170. end
  171.  
  172. local function fMTF(tData)
  173.  
  174.     --setup--
  175.     local tSolution = {}
  176.     fFlushMTF()
  177.    
  178.    
  179.     --encode--
  180.     for _,iNum in next,tData do
  181.         for i=1,256 do
  182.             if tMTFTable[i]==iNum then --if bits are the same
  183.                 fInsert(tMTFTable,1,fRemove(tMTFTable,i)) --move bit to front
  184.                 fInsert(tSolution,i) --insert bit position
  185.                 break --next entry
  186.             end
  187.         end
  188.     end
  189.    
  190.    
  191.     --finalize--
  192.     return tSolution
  193. end
  194.  
  195. local function fUnMTF(tData)
  196.  
  197.     --setup--
  198.     local tSolution = {}
  199.     fFlushMTF()
  200.    
  201.    
  202.     --decode--
  203.     for _,iNum in next,tData do
  204.         fInsert(tMTFTable,1,fRemove(tMTFTable,iNum)) --move bit to front
  205.         fInsert(tSolution,tMTFTable[1]) --record bit
  206.     end
  207.    
  208.    
  209.     --finalize--
  210.     return tSolution
  211. end
  212.  
  213.  
  214. --String RLE functions--
  215. local function fSRLE(tData)
  216.    
  217.     --setup--
  218.     local tSolution = {}
  219.    
  220.     --encode--
  221.     while #tData>0 do
  222.         fInsert(tSolution,tData[1])
  223.         if fRemove(tData,1) == tData[1] then--if theres a run
  224.             local iEnc = tData[1]
  225.             local iCount = 1
  226.             while tData[1]==iEnc and iCount<255 do --count how long the run is
  227.                 fRemove(tData,1)
  228.                 iCount = iCount + 1
  229.             end
  230.             fInsert(tSolution,#tSolution,iCount)
  231.             fInsert(tSolution,#tSolution,iCount) --insert count identifier
  232.         end
  233.     end
  234.    
  235.    
  236.     --finalize--
  237.     return tSolution
  238. end
  239.  
  240. local function fUnSRLE(tData)
  241.  
  242.     --setup--
  243.     local tSolution = {}
  244.    
  245.    
  246.     --decode--
  247.     while #tData>0 do
  248.         if tData[1]==tData[2] then --we found a counter so now add it
  249.             fRemove(tData,1)
  250.             local iCount = fRemove(tData,1)
  251.             local iChar = fRemove(tData,1)
  252.             for _=1,iCount do
  253.                 fInsert(tSolution,iChar)
  254.             end
  255.         else
  256.             fInsert(tSolution,fRemove(tData,1))
  257.         end
  258.     end
  259.    
  260.    
  261.     --finalize--
  262.     return tSolution
  263. end
  264.  
  265.  
  266. --Color RLE functions--
  267. local function fCRLE(tData)
  268.  
  269.     --setup--
  270.     local tSolution = {}
  271.     local sInter = ""
  272.     local iLast = -1
  273.    
  274.     --encode--
  275.     for _,iNum in next, tData do
  276.         if iNum==iLast then
  277.             sInter=sInter.."0"
  278.         else
  279.             if iNum==16 then
  280.                 sInter = sInter.."11"
  281.             else
  282.                 sInter=sInter.."1"..fDecToBin(iNum):sub(4,8)
  283.             end
  284.         end
  285.         iLast = iNum
  286.     end
  287.     sInter = sInter:sub(2,#sInter)
  288.     if #sInter%8~=0 then
  289.         sInter = sInter..("1"):rep(8-#sInter%8)
  290.     end
  291.     while #sInter>=8 do
  292.         fInsert(tSolution,tonumber(sInter:sub(1,8),2))
  293.         sInter = sInter:sub(9,#sInter)
  294.     end
  295.    
  296.    
  297.     --finalize--
  298.     return tSolution
  299. end
  300.  
  301. local function fUnCRLE(iLength, tData)
  302.    
  303.     --setup--
  304.     local sInter = ""
  305.     local tSolution = {}
  306.    
  307.     for _,v in next,tData do
  308.         sInter = sInter..fDecToBin(v)
  309.     end
  310.     tSolution[1] = tonumber(sInter:sub(1,5),2)
  311.     iLength = iLength - 1
  312.     sInter = sInter:sub(6,#sInter)
  313.    
  314.     --decode--
  315.     while iLength>0 do
  316.         iLength = iLength - 1
  317.         if sInter:sub(1,1)=="0" then
  318.             fInsert(tSolution,tSolution[#tSolution])
  319.             sInter = sInter:sub(2,#sInter)
  320.         else
  321.             if sInter:sub(2,2)=="1" then
  322.                 fInsert(tSolution,16)
  323.                 sInter = sInter:sub(3,#sInter)
  324.             else
  325.                 fInsert(tSolution,tonumber(sInter:sub(2,6),2))
  326.                 sInter = sInter:sub(7,#sInter)
  327.             end
  328.         end
  329.     end
  330.    
  331.     --finalize--
  332.     return tSolution
  333. end
  334.  
  335. --Huffman functions--
  336. local function fHuffman(tData)
  337.  
  338.     --setup--
  339.     local tFreq = {}
  340.     local tTree = {}
  341.     local tKey = {}
  342.     local sInter = ""
  343.     local tSolution = {}
  344.     local iMaxSize, iCount = 0, 0
  345.    
  346.    
  347.     --key table--
  348.     for _,v in next, tData do
  349.         tFreq[v] = tFreq[v] and tFreq[v]+1 or 1
  350.     end
  351.     for k,v in next,tFreq do
  352.         iCount = iCount + 1
  353.         fInsert(tTree,{freq=v,contains=k,depth=0})
  354.     end
  355.     while #tTree>1 do
  356.         fSort(tTree, function(a,b)
  357.             return a.freq==b.freq and a.depth<b.depth or a.freq<b.freq
  358.         end)
  359.         fInsert(tTree,{depth=fMax(tTree[1].depth,tTree[2].depth)+1,freq=tTree[1].freq+tTree[2].freq,contains={tTree[1],tTree[2]}})
  360.         fRemove(tTree,1)
  361.         fRemove(tTree,1)
  362.     end
  363.     tKey = fSetBits(tTree[1])
  364.    
  365.    
  366.     --encode--
  367.     sInter = fDecToBin(iCount)
  368.     for k,v in next, tKey do
  369.         sInter = sInter..fDecToBin(#v)
  370.     end
  371.     for k,v in next, tKey do
  372.         sInter = sInter..fDecToBin(k)..v
  373.     end
  374.     for _,v in next, tData do
  375.         sInter = sInter..tKey[v]
  376.     end
  377.     sInter = ("0"):rep(8 - ((#sInter%8)+1)).."1"..sInter
  378.     while #sInter>=8 do
  379.         fInsert(tSolution,tonumber(sInter:sub(1,8),2))
  380.         sInter = sInter:sub(9,#sInter)
  381.     end
  382.    
  383.     --finalize--
  384.     return tSolution
  385. end
  386.  
  387. local function fUnHuffman(tData)
  388.    
  389.     --setup--
  390.     local sInter = ""
  391.     local sBuild = ""
  392.     local tSolution = {}
  393.     local tKeys = {}
  394.     local iCount
  395.    
  396.    
  397.     --key table--
  398.     for k,v in next, tData do
  399.         sInter = sInter..fDecToBin(v)
  400.     end
  401.     while sInter:sub(1,1)=="0" do
  402.         sInter = sInter:sub(2,#sInter)
  403.     end
  404.     iCount = tonumber(sInter:sub(2,9),2)
  405.     sInter = sInter:sub(10,#sInter)
  406.     for i=1,iCount do
  407.         tKeys[i] = tonumber(sInter:sub(1,8),2)
  408.         sInter = sInter:sub(9,#sInter)
  409.     end
  410.     for i=1,iCount do
  411.         tKeys[sInter:sub(9,8+tKeys[i])] = tonumber(sInter:sub(1,8),2)
  412.         sInter = sInter:sub(tKeys[i]+9,#sInter)
  413.         tKeys[i] = nil
  414.     end
  415.    
  416.    
  417.     --decode--
  418.     while #sInter>0 do
  419.         sBuild = sBuild..sInter:sub(1,1)
  420.         if tKeys[sBuild] then
  421.             fInsert(tSolution,tKeys[sBuild])
  422.             sBuild = ""
  423.         end
  424.         sInter = sInter:sub(2,#sInter)
  425.     end
  426.    
  427.    
  428.     --finalize--
  429.     return tSolution
  430. end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement