-
Notifications
You must be signed in to change notification settings - Fork 0
/
lzw.lua
119 lines (112 loc) · 4.1 KB
/
lzw.lua
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
local lzw = {}
local nDefaultCode = 42 -- init token code
local primeKey = 97 -- prime key to mod
local function lzwFindFirstNormalChar(tbDeCodeToken, szCode)
local szNormalChar = szCode
while (tbDeCodeToken[tonumber(szNormalChar)]) do
szNormalChar = tbDeCodeToken[tonumber(szNormalChar)][1]
end
return szNormalChar
end
local function lzwDecodeToSource(szSource, tbDeCodeToken, szPrefix)
local tbPrefix = { szPrefix }
while #tbPrefix ~= 0 do
local szFirst = table.remove(tbPrefix, 1)
local tbDecode = tbDeCodeToken[tonumber(szFirst)]
if tbDecode then
table.insert(tbPrefix, 1, tbDecode[2])
table.insert(tbPrefix, 1, tbDecode[1])
else
szSource = szSource .. szFirst
end
end
return szSource
end
local function getToken(tNum)
local sum = 0
for _, v in pairs(tNum) do
sum = sum + v
end
return sum % primeKey
end
-- compress
function lzw.deflate(szSource, szToken)
local tbOutput = {}
local tbChar = {}
local szPrefix = ""
local tbToken = {}
local nTokenCode = nDefaultCode
if szToken then
nTokenCode = getToken(table.pack(string.byte(szToken, 1, string.len(szToken))))
end
for szChar in string.gmatch(szSource, ".") do
tbChar[szChar] = true
if szPrefix == "" then
szPrefix = szChar
else
if tbToken[szPrefix .. szChar] then
szPrefix = tbToken[szPrefix .. szChar]
else
tbToken[szPrefix .. szChar] = nTokenCode
nTokenCode = nTokenCode + 1
table.insert(tbOutput, szPrefix)
szPrefix = szChar
end
end
end
if szPrefix~= "" then
table.insert(tbOutput, szPrefix)
end
return tbOutput, tbChar
end
-- decompress
function lzw.inflate(tbCode, tbChar, szToken)
local szSource = ""
local szPrefix = ""
local tbToken = {}
local tbDeCodeToken = {}
local nTokenCode = nDefaultCode
if szToken then
nTokenCode = getToken(table.pack(string.byte(szToken, 1, string.len(szToken))))
end
for _, szCode in ipairs(tbCode) do
if szPrefix ~= "" then
if tbChar[szCode] then -- judge whether is a normal suffix
tbToken[szPrefix .. szCode] = nTokenCode
tbDeCodeToken[nTokenCode] = { szPrefix, szCode }
nTokenCode = nTokenCode + 1
--put prefix to output steam
szSource = lzwDecodeToSource(szSource, tbDeCodeToken, szPrefix)
else
if tbDeCodeToken[tonumber(szCode)] then
local szSuffix = lzwFindFirstNormalChar(tbDeCodeToken, tbDeCodeToken[tonumber(szCode)][1])
tbToken[szPrefix .. szSuffix] = nTokenCode
tbDeCodeToken[nTokenCode] = { szPrefix, szSuffix }
nTokenCode = nTokenCode + 1
--put prefix to output steam
szSource = lzwDecodeToSource(szSource, tbDeCodeToken, szPrefix)
else
if tbChar[szPrefix] then
tbToken[szPrefix .. szPrefix] = nTokenCode
tbDeCodeToken[nTokenCode] = { szPrefix, szPrefix }
else
local szSuffix = lzwFindFirstNormalChar(tbDeCodeToken, tbDeCodeToken[tonumber(szPrefix)][1])
tbToken[szPrefix .. szSuffix] = nTokenCode
tbDeCodeToken[nTokenCode] = { szPrefix, szSuffix }
end
nTokenCode = nTokenCode + 1
--put prefix to output steam
szSource = lzwDecodeToSource(szSource, tbDeCodeToken, szPrefix)
end
end
end
szPrefix = szCode
end
szSource = lzwDecodeToSource(szSource, tbDeCodeToken, szPrefix)
return szSource
end
function lzw.setToken(token)
-- assert(type(num) == "number")
nTokenCode = token
end
return lzw