aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/huffmanencoder.nim39
-rw-r--r--tests/thuffmanencoder.nim39
2 files changed, 78 insertions, 0 deletions
diff --git a/src/huffmanencoder.nim b/src/huffmanencoder.nim
new file mode 100644
index 0000000..60c3d46
--- /dev/null
+++ b/src/huffmanencoder.nim
@@ -0,0 +1,39 @@
1# gzip-like LZSS compressor
2# Copyright (C) 2018 Pacien TRAN-GIRARD
3#
4# This program is free software: you can redistribute it and/or modify
5# it under the terms of the GNU Affero General Public License as
6# published by the Free Software Foundation, either version 3 of the
7# License, or (at your option) any later version.
8#
9# This program is distributed in the hope that it will be useful,
10# but WITHOUT ANY WARRANTY; without even the implied warranty of
11# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12# GNU Affero General Public License for more details.
13#
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/>.
16
17import tables
18import integers, huffmantree, bitwriter
19
20type HuffmanEncoder*[T, U: SomeUnsignedInt] = object
21 codebook: TableRef[T, U]
22
23proc buildCodebook*[T, U](tree: HuffmanTreeNode[T], codeType: typedesc[U]): TableRef[T, U] =
24 var codebook = newTable[T, U]()
25 proc addCode(node: HuffmanTreeNode[T], path: U, depth: int) =
26 case node.kind:
27 of branch:
28 addCode(node.left, path, depth + 1)
29 addCode(node.right, path or (1.U shl depth), depth + 1)
30 of leaf:
31 codebook[node.value] = path
32 addCode(tree, 0.U, 0)
33 codebook
34
35proc encoder*[T, U](tree: HuffmanTreeNode[T], codeType: typedesc[U]): HuffmanEncoder[T, U] =
36 HuffmanEncoder[T, U](codebook: buildCodebook(tree, codeType))
37
38proc encode*[T, U](decoder: HuffmanEncoder[T, U], value: T): U =
39 decoder.codebook[value]
diff --git a/tests/thuffmanencoder.nim b/tests/thuffmanencoder.nim
new file mode 100644
index 0000000..04318b7
--- /dev/null
+++ b/tests/thuffmanencoder.nim
@@ -0,0 +1,39 @@
1# gzip-like LZSS compressor
2# Copyright (C) 2018 Pacien TRAN-GIRARD
3#
4# This program is free software: you can redistribute it and/or modify
5# it under the terms of the GNU Affero General Public License as
6# published by the Free Software Foundation, either version 3 of the
7# License, or (at your option) any later version.
8#
9# This program is distributed in the hope that it will be useful,
10# but WITHOUT ANY WARRANTY; without even the implied warranty of
11# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12# GNU Affero General Public License for more details.
13#
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/>.
16
17import unittest, streams, tables
18import bitreader, bitwriter
19import huffmantree, huffmanencoder
20
21suite "huffencoder":
22 let tree = huffmanBranch(
23 huffmanLeaf(1'u),
24 huffmanBranch(
25 huffmanLeaf(2'u),
26 huffmanLeaf(3'u)))
27
28 test "buildCodebook":
29 let codebook = buildCodebook(tree, uint)
30 check codebook.len == 3
31 check codebook[1'u] == 0b0
32 check codebook[2'u] == 0b01
33 check codebook[3'u] == 0b11
34
35 test "encode":
36 let encoder = tree.encoder(uint)
37 check encoder.encode(1'u) == 0b0
38 check encoder.encode(2'u) == 0b01
39 check encoder.encode(3'u) == 0b11