aboutsummaryrefslogtreecommitdiff
path: root/tests
diff options
context:
space:
mode:
authorpacien2018-12-03 18:16:04 +0100
committerpacien2018-12-03 18:16:04 +0100
commitb616e8f5773631945962d4b1256f8f2d575e0da1 (patch)
treec3b2f731ad3ef692ff9edb133f852d190e07ad2f /tests
parent200cb18aafa7f62fdca37ae8952b5e9c5bb3f25f (diff)
downloadgziplike-b616e8f5773631945962d4b1256f8f2d575e0da1.tar.gz
optimise lzss prefix lookup with custom hashmap
Diffstat (limited to 'tests')
-rw-r--r--tests/tlzss.nim71
1 files changed, 41 insertions, 30 deletions
diff --git a/tests/tlzss.nim b/tests/tlzss.nim
index ad667e5..39a89c6 100644
--- a/tests/tlzss.nim
+++ b/tests/tlzss.nim
@@ -14,25 +14,36 @@
14# You should have received a copy of the GNU Affero General Public License 14# You should have received a copy of the GNU Affero General Public License
15# along with this program. If not, see <https://www.gnu.org/licenses/>. 15# along with this program. If not, see <https://www.gnu.org/licenses/>.
16 16
17import unittest, sequtils, tables, lists 17import unittest, sequtils, tables, lists, algorithm
18import lzss/matchtable, lzss/lzssnode, lzss/lzsschain, lzss/lzssencoder 18import lzss/matchring, lzss/matchtable, lzss/lzssnode, lzss/lzsschain, lzss/lzssencoder
19 19
20suite "matchtable": 20suite "matchring":
21 test "matchList": 21 test "items (empty)":
22 let matchTable = initMatchTable(seq[int], int) 22 var ring = initMatchRing()
23 check matchTable.matchList(@[0, 1, 2]).len == 0 23 check toSeq(ring.items).len == 0
24
25 test "addMatch, items (partial)":
26 var ring = initMatchRing()
27 let items = [0, 1, 2]
28 for i in items: ring.addMatch(i)
29 check toSeq(ring.items) == items.reversed()
24 30
31 test "addMatch, items (rolling)":
32 var ring = initMatchRing()
33 let items = toSeq(0..13)
34 for i in items: ring.addMatch(i)
35 check toSeq(ring.items) == items[^matchLimit..<items.len].reversed()
36
37suite "matchtable":
25 test "addMatch": 38 test "addMatch":
26 let matchTable = initMatchTable(seq[int], int) 39 var matchTable = initMatchTable()
27 matchTable.addMatch(@[0, 1, 2], 42) 40 matchTable.addMatch([0'u8, 1, 2], 42)
28 matchTable.addMatch(@[2, 1, 0], 24) 41 matchTable.addMatch([2'u8, 1, 0], 24)
29 check matchTable.len == 2 42 check toSeq(matchTable.candidates([0'u8, 1, 2]).items) == [42]
30 check matchTable.matchList(@[0, 1, 2]) == [42] 43 check toSeq(matchTable.candidates([2'u8, 1, 0]).items) == [24]
31 check matchTable.matchList(@[2, 1, 0]) == [24] 44 matchTable.addMatch([0'u8, 1, 2], 1337)
32 matchTable.addMatch(@[0, 1, 2], 1337) 45 check toSeq(matchTable.candidates([0'u8, 1, 2]).items) == [1337, 42]
33 check matchTable.len == 2 46 check toSeq(matchTable.candidates([2'u8, 1, 0]).items) == [24]
34 check matchTable.matchList(@[0, 1, 2]) == [1337, 42]
35 check matchTable.matchList(@[2, 1, 0]) == [24]
36 47
37suite "lzssnode": 48suite "lzssnode":
38 test "equality": 49 test "equality":
@@ -54,11 +65,11 @@ suite "lzsschain":
54 65
55suite "lzssencoder": 66suite "lzssencoder":
56 test "commonPrefixLength": 67 test "commonPrefixLength":
57 check commonPrefixLength([], [], 0, 10) == 0 68 check commonPrefixLength([], [], 10) == 0
58 check commonPrefixLength([1'u8, 2], [1'u8, 2, 3], 0, 10) == 2 69 check commonPrefixLength([1'u8, 2], [1'u8, 2, 3], 10) == 2
59 check commonPrefixLength([1'u8, 2], [1'u8, 2, 3], 1, 10) == 2 70 check commonPrefixLength([1'u8, 2], [1'u8, 2, 3], 10) == 2
60 check commonPrefixLength([1'u8, 2, 3], [1'u8, 2, 4], 1, 10) == 2 71 check commonPrefixLength([1'u8, 2, 3], [1'u8, 2, 4], 10) == 2
61 check commonPrefixLength([1'u8, 2, 3, 4], [1'u8, 2, 3, 4], 1, 3) == 3 72 check commonPrefixLength([1'u8, 2, 3, 4], [1'u8, 2, 3, 4], 3) == 3
62 73
63 test "longestPrefix": 74 test "longestPrefix":
64 let buffer = [ 75 let buffer = [
@@ -67,22 +78,22 @@ suite "lzssencoder":
67 0, 1, 2, 78 0, 1, 2,
68 0, 1, 2, 3, 4] 79 0, 1, 2, 3, 4]
69 var candidatePos = [0, 4, 8] 80 var candidatePos = [0, 4, 8]
70 let result = longestPrefix(candidatePos, buffer.toOpenArray(0, 10), buffer.toOpenArray(11, buffer.len - 1)) 81 var matchRing = initMatchRing()
82 for pos in candidatePos: matchRing.addMatch(pos)
83 let result = longestPrefix(matchRing, buffer.toOpenArray(0, 10), buffer.toOpenArray(11, buffer.len - 1))
71 check result.pos == 4 84 check result.pos == 4
72 check result.length == 4 85 check result.length == 4
73 86
74 test "addGroups": 87 test "addGroups":
75 let matchTable = initMatchTable(seq[uint8], int) 88 var matchTable = initMatchTable()
76 let buffer = toSeq(0'u8..10'u8) 89 let buffer = toSeq(0'u8..10'u8)
77 matchTable.addGroups(buffer, 0, 1) 90 matchTable.addGroups(buffer, 0, 1)
78 check matchTable.len == 0
79 matchTable.addGroups(buffer, 2, 9) 91 matchTable.addGroups(buffer, 2, 9)
80 check matchTable.len == 5 92 check toSeq(matchTable.candidates([1'u8, 2, 3]).items).len == 0
81 check matchTable.matchList(@[1'u8, 2, 3]).len == 0 93 check toSeq(matchTable.candidates([7'u8, 8, 9]).items).len == 0
82 check matchTable.matchList(@[7'u8, 8, 9]).len == 0 94 check toSeq(matchTable.candidates([2'u8, 3, 4]).items) == [2]
83 check matchTable.matchList(@[2'u8, 3, 4]) == [2] 95 check toSeq(matchTable.candidates([4'u8, 5, 6]).items) == [4]
84 check matchTable.matchList(@[4'u8, 5, 6]) == [4] 96 check toSeq(matchTable.candidates([6'u8, 7, 8]).items) == [6]
85 check matchTable.matchList(@[6'u8, 7, 8]) == [6]
86 97
87 test "lzssEncode": 98 test "lzssEncode":
88 let buffer = [0'u8, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 4, 5, 0, 5, 5, 0, 5, 5] 99 let buffer = [0'u8, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 4, 5, 0, 5, 5, 0, 5, 5]