From e88f60b63cb05f56a61060a953c726b7a78c0652 Mon Sep 17 00:00:00 2001 From: pacien Date: Fri, 30 Nov 2018 17:08:01 +0100 Subject: isolate huffman encoding module --- src/huffman/huffmandecoder.nim | 35 +++++++++++ src/huffman/huffmanencoder.nim | 40 +++++++++++++ src/huffman/huffmantree.nim | 74 +++++++++++++++++++++++ src/huffman/huffmantreebuilder.nim | 44 ++++++++++++++ src/huffmandecoder.nim | 34 ----------- src/huffmanencoder.nim | 39 ------------ src/huffmantree.nim | 74 ----------------------- src/huffmantreebuilder.nim | 44 -------------- src/lzsschain.nim | 2 +- tests/thuffman.nim | 119 +++++++++++++++++++++++++++++++++++++ tests/thuffmandecoder.nim | 43 -------------- tests/thuffmanencoder.nim | 39 ------------ tests/thuffmantree.nim | 74 ----------------------- tests/thuffmantreebuilder.nim | 29 --------- 14 files changed, 313 insertions(+), 377 deletions(-) create mode 100644 src/huffman/huffmandecoder.nim create mode 100644 src/huffman/huffmanencoder.nim create mode 100644 src/huffman/huffmantree.nim create mode 100644 src/huffman/huffmantreebuilder.nim delete mode 100644 src/huffmandecoder.nim delete mode 100644 src/huffmanencoder.nim delete mode 100644 src/huffmantree.nim delete mode 100644 src/huffmantreebuilder.nim create mode 100644 tests/thuffman.nim delete mode 100644 tests/thuffmandecoder.nim delete mode 100644 tests/thuffmanencoder.nim delete mode 100644 tests/thuffmantree.nim delete mode 100644 tests/thuffmantreebuilder.nim diff --git a/src/huffman/huffmandecoder.nim b/src/huffman/huffmandecoder.nim new file mode 100644 index 0000000..9a58b55 --- /dev/null +++ b/src/huffman/huffmandecoder.nim @@ -0,0 +1,35 @@ +# gzip-like LZSS compressor +# Copyright (C) 2018 Pacien TRAN-GIRARD +# +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU Affero General Public License as +# published by the Free Software Foundation, either version 3 of the +# License, or (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU Affero General Public License for more details. +# +# You should have received a copy of the GNU Affero General Public License +# along with this program. If not, see . + +import ../bitio/bitreader +import huffmantree + +type HuffmanDecoder*[T: SomeUnsignedInt] = object + tree: HuffmanTreeNode[T] + +proc decoder*[T](tree: HuffmanTreeNode[T]): HuffmanDecoder[T] = + HuffmanDecoder[T](tree: tree) + +proc decode*[T](decoder: HuffmanDecoder[T], bitReader: BitReader): T = + proc walk(node: HuffmanTreeNode[T]): T = + case node.kind: + of branch: + case bitReader.readBool(): + of false: walk(node.left) + of true: walk(node.right) + of leaf: + node.value + walk(decoder.tree) diff --git a/src/huffman/huffmanencoder.nim b/src/huffman/huffmanencoder.nim new file mode 100644 index 0000000..3ed41ec --- /dev/null +++ b/src/huffman/huffmanencoder.nim @@ -0,0 +1,40 @@ +# gzip-like LZSS compressor +# Copyright (C) 2018 Pacien TRAN-GIRARD +# +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU Affero General Public License as +# published by the Free Software Foundation, either version 3 of the +# License, or (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU Affero General Public License for more details. +# +# You should have received a copy of the GNU Affero General Public License +# along with this program. If not, see . + +import tables +import ../integers, ../bitio/bitwriter +import huffmantree + +type HuffmanEncoder*[T, U: SomeUnsignedInt] = object + codebook: TableRef[T, U] + +proc buildCodebook*[T, U](tree: HuffmanTreeNode[T], codeType: typedesc[U]): TableRef[T, U] = + var codebook = newTable[T, U]() + proc addCode(node: HuffmanTreeNode[T], path: U, depth: int) = + case node.kind: + of branch: + addCode(node.left, path, depth + 1) + addCode(node.right, path or (1.U shl depth), depth + 1) + of leaf: + codebook[node.value] = path + addCode(tree, 0.U, 0) + codebook + +proc encoder*[T, U](tree: HuffmanTreeNode[T], codeType: typedesc[U]): HuffmanEncoder[T, U] = + HuffmanEncoder[T, U](codebook: buildCodebook(tree, codeType)) + +proc encode*[T, U](decoder: HuffmanEncoder[T, U], value: T): U = + decoder.codebook[value] diff --git a/src/huffman/huffmantree.nim b/src/huffman/huffmantree.nim new file mode 100644 index 0000000..1140694 --- /dev/null +++ b/src/huffman/huffmantree.nim @@ -0,0 +1,74 @@ +# gzip-like LZSS compressor +# Copyright (C) 2018 Pacien TRAN-GIRARD +# +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU Affero General Public License as +# published by the Free Software Foundation, either version 3 of the +# License, or (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU Affero General Public License for more details. +# +# You should have received a copy of the GNU Affero General Public License +# along with this program. If not, see . + +import tables, heapqueue +import ../integers, ../bitio/bitreader, ../bitio/bitwriter + +const valueLengthFieldBitLength* = 6 # 64 + +type HuffmanTreeNodeKind* = enum + branch, + leaf + +type HuffmanTreeNode*[T: SomeUnsignedInt] = ref object + case kind*: HuffmanTreeNodeKind + of branch: + left*, right*: HuffmanTreeNode[T] + maxChildValue: T + of leaf: + value*: T + +proc huffmanBranch*[T](left, right: HuffmanTreeNode[T]): HuffmanTreeNode[T] = + HuffmanTreeNode[T]( + kind: branch, left: left, right: right, + maxChildValue: max(left.maxValue(), right.maxValue())) + +proc huffmanLeaf*[T](value: T): HuffmanTreeNode[T] = + HuffmanTreeNode[T](kind: leaf, value: value) + +proc `==`*[T](a, b: HuffmanTreeNode[T]): bool = + if a.kind != b.kind: return false + case a.kind: + of branch: a.left == b.left and a.right == b.right + of leaf: a.value == b.value + +proc maxValue*[T](node: HuffmanTreeNode[T]): T = + case node.kind: + of branch: node.maxChildValue + of leaf: node.value + +proc deserialise*[T](bitReader: BitReader, valueType: typedesc[T]): HuffmanTreeNode[T] = + let valueBitLength = bitReader.readBits(valueLengthFieldBitLength, uint8).int + proc readNode(): HuffmanTreeNode[T] = + case bitReader.readBool(): + of false: huffmanBranch(readNode(), readNode()) + of true: huffmanLeaf(bitReader.readBits(valueBitLength, valueType)) + readNode() + +proc serialise*[T](tree: HuffmanTreeNode[T], bitWriter: BitWriter) = + let maxValue = tree.maxValue() + let valueBitLength = maxValue.bitLength() + proc writeNode(node: HuffmanTreeNode[T]) = + case node.kind: + of branch: + bitWriter.writeBool(false) + writeNode(node.left) + writeNode(node.right) + of leaf: + bitWriter.writeBool(true) + bitWriter.writeBits(valueBitLength, node.value) + bitWriter.writeBits(valueLengthFieldBitLength, valueBitLength.uint8) + writeNode(tree) diff --git a/src/huffman/huffmantreebuilder.nim b/src/huffman/huffmantreebuilder.nim new file mode 100644 index 0000000..4169099 --- /dev/null +++ b/src/huffman/huffmantreebuilder.nim @@ -0,0 +1,44 @@ +# gzip-like LZSS compressor +# Copyright (C) 2018 Pacien TRAN-GIRARD +# +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU Affero General Public License as +# published by the Free Software Foundation, either version 3 of the +# License, or (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU Affero General Public License for more details. +# +# You should have received a copy of the GNU Affero General Public License +# along with this program. If not, see . + +import tables, heapqueue +import huffmantree + +type WeighedHuffmanTreeNode[T] = ref object + weight: int + huffmanTreeNode: HuffmanTreeNode[T] + +proc weighedHuffmanBranch[T](left, right: WeighedHuffmanTreeNode[T]): WeighedHuffmanTreeNode[T] = + WeighedHuffmanTreeNode[T]( + weight: left.weight + right.weight, + huffmanTreeNode: huffmanBranch(left.huffmanTreeNode, right.huffmanTreeNode)) + +proc weighedHuffmanLeaf[T](value: T, weight: int): WeighedHuffmanTreeNode[T] = + WeighedHuffmanTreeNode[T]( + weight: weight, + huffmanTreeNode: huffmanLeaf(value)) + +proc `<`*[T](left, right: WeighedHuffmanTreeNode[T]): bool = + left.weight < right.weight + +proc symbolQueue[T](stats: CountTableRef[T]): HeapQueue[WeighedHuffmanTreeNode[T]] = + result = newHeapQueue[WeighedHuffmanTreeNode[T]]() + for item, count in stats.pairs: result.push(weighedHuffmanLeaf(item, count)) + +proc buildHuffmanTree*[T: SomeUnsignedInt](stats: CountTableRef[T]): HuffmanTreeNode[T] = + var symbolQueue = symbolQueue(stats) + while symbolQueue.len > 1: symbolQueue.push(weighedHuffmanBranch(symbolQueue.pop(), symbolQueue.pop())) + symbolQueue[0].huffmanTreeNode diff --git a/src/huffmandecoder.nim b/src/huffmandecoder.nim deleted file mode 100644 index 5cf4ca5..0000000 --- a/src/huffmandecoder.nim +++ /dev/null @@ -1,34 +0,0 @@ -# gzip-like LZSS compressor -# Copyright (C) 2018 Pacien TRAN-GIRARD -# -# This program is free software: you can redistribute it and/or modify -# it under the terms of the GNU Affero General Public License as -# published by the Free Software Foundation, either version 3 of the -# License, or (at your option) any later version. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU Affero General Public License for more details. -# -# You should have received a copy of the GNU Affero General Public License -# along with this program. If not, see . - -import huffmantree, bitio/bitreader - -type HuffmanDecoder*[T: SomeUnsignedInt] = object - tree: HuffmanTreeNode[T] - -proc decoder*[T](tree: HuffmanTreeNode[T]): HuffmanDecoder[T] = - HuffmanDecoder[T](tree: tree) - -proc decode*[T](decoder: HuffmanDecoder[T], bitReader: BitReader): T = - proc walk(node: HuffmanTreeNode[T]): T = - case node.kind: - of branch: - case bitReader.readBool(): - of false: walk(node.left) - of true: walk(node.right) - of leaf: - node.value - walk(decoder.tree) diff --git a/src/huffmanencoder.nim b/src/huffmanencoder.nim deleted file mode 100644 index 05ed64f..0000000 --- a/src/huffmanencoder.nim +++ /dev/null @@ -1,39 +0,0 @@ -# gzip-like LZSS compressor -# Copyright (C) 2018 Pacien TRAN-GIRARD -# -# This program is free software: you can redistribute it and/or modify -# it under the terms of the GNU Affero General Public License as -# published by the Free Software Foundation, either version 3 of the -# License, or (at your option) any later version. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU Affero General Public License for more details. -# -# You should have received a copy of the GNU Affero General Public License -# along with this program. If not, see . - -import tables -import integers, huffmantree, bitio/bitwriter - -type HuffmanEncoder*[T, U: SomeUnsignedInt] = object - codebook: TableRef[T, U] - -proc buildCodebook*[T, U](tree: HuffmanTreeNode[T], codeType: typedesc[U]): TableRef[T, U] = - var codebook = newTable[T, U]() - proc addCode(node: HuffmanTreeNode[T], path: U, depth: int) = - case node.kind: - of branch: - addCode(node.left, path, depth + 1) - addCode(node.right, path or (1.U shl depth), depth + 1) - of leaf: - codebook[node.value] = path - addCode(tree, 0.U, 0) - codebook - -proc encoder*[T, U](tree: HuffmanTreeNode[T], codeType: typedesc[U]): HuffmanEncoder[T, U] = - HuffmanEncoder[T, U](codebook: buildCodebook(tree, codeType)) - -proc encode*[T, U](decoder: HuffmanEncoder[T, U], value: T): U = - decoder.codebook[value] diff --git a/src/huffmantree.nim b/src/huffmantree.nim deleted file mode 100644 index 6208ecf..0000000 --- a/src/huffmantree.nim +++ /dev/null @@ -1,74 +0,0 @@ -# gzip-like LZSS compressor -# Copyright (C) 2018 Pacien TRAN-GIRARD -# -# This program is free software: you can redistribute it and/or modify -# it under the terms of the GNU Affero General Public License as -# published by the Free Software Foundation, either version 3 of the -# License, or (at your option) any later version. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU Affero General Public License for more details. -# -# You should have received a copy of the GNU Affero General Public License -# along with this program. If not, see . - -import tables, heapqueue -import integers, bitio/bitreader, bitio/bitwriter - -const valueLengthFieldBitLength* = 6 # 64 - -type HuffmanTreeNodeKind* = enum - branch, - leaf - -type HuffmanTreeNode*[T: SomeUnsignedInt] = ref object - case kind*: HuffmanTreeNodeKind - of branch: - left*, right*: HuffmanTreeNode[T] - maxChildValue: T - of leaf: - value*: T - -proc huffmanBranch*[T](left, right: HuffmanTreeNode[T]): HuffmanTreeNode[T] = - HuffmanTreeNode[T]( - kind: branch, left: left, right: right, - maxChildValue: max(left.maxValue(), right.maxValue())) - -proc huffmanLeaf*[T](value: T): HuffmanTreeNode[T] = - HuffmanTreeNode[T](kind: leaf, value: value) - -proc `==`*[T](a, b: HuffmanTreeNode[T]): bool = - if a.kind != b.kind: return false - case a.kind: - of branch: a.left == b.left and a.right == b.right - of leaf: a.value == b.value - -proc maxValue*[T](node: HuffmanTreeNode[T]): T = - case node.kind: - of branch: node.maxChildValue - of leaf: node.value - -proc deserialise*[T](bitReader: BitReader, valueType: typedesc[T]): HuffmanTreeNode[T] = - let valueBitLength = bitReader.readBits(valueLengthFieldBitLength, uint8).int - proc readNode(): HuffmanTreeNode[T] = - case bitReader.readBool(): - of false: huffmanBranch(readNode(), readNode()) - of true: huffmanLeaf(bitReader.readBits(valueBitLength, valueType)) - readNode() - -proc serialise*[T](tree: HuffmanTreeNode[T], bitWriter: BitWriter) = - let maxValue = tree.maxValue() - let valueBitLength = maxValue.bitLength() - proc writeNode(node: HuffmanTreeNode[T]) = - case node.kind: - of branch: - bitWriter.writeBool(false) - writeNode(node.left) - writeNode(node.right) - of leaf: - bitWriter.writeBool(true) - bitWriter.writeBits(valueBitLength, node.value) - bitWriter.writeBits(valueLengthFieldBitLength, valueBitLength.uint8) - writeNode(tree) diff --git a/src/huffmantreebuilder.nim b/src/huffmantreebuilder.nim deleted file mode 100644 index 5b33d34..0000000 --- a/src/huffmantreebuilder.nim +++ /dev/null @@ -1,44 +0,0 @@ -# gzip-like LZSS compressor -# Copyright (C) 2018 Pacien TRAN-GIRARD -# -# This program is free software: you can redistribute it and/or modify -# it under the terms of the GNU Affero General Public License as -# published by the Free Software Foundation, either version 3 of the -# License, or (at your option) any later version. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU Affero General Public License for more details. -# -# You should have received a copy of the GNU Affero General Public License -# along with this program. If not, see . - -import tables, heapqueue -import huffmantree, lzssencoder - -type WeighedHuffmanTreeNode[T] = ref object - weight: int - huffmanTreeNode: HuffmanTreeNode[T] - -proc weighedHuffmanBranch[T](left, right: WeighedHuffmanTreeNode[T]): WeighedHuffmanTreeNode[T] = - WeighedHuffmanTreeNode[T]( - weight: left.weight + right.weight, - huffmanTreeNode: huffmanBranch(left.huffmanTreeNode, right.huffmanTreeNode)) - -proc weighedHuffmanLeaf[T](value: T, weight: int): WeighedHuffmanTreeNode[T] = - WeighedHuffmanTreeNode[T]( - weight: weight, - huffmanTreeNode: huffmanLeaf(value)) - -proc `<`*[T](left, right: WeighedHuffmanTreeNode[T]): bool = - left.weight < right.weight - -proc symbolQueue[T](stats: CountTableRef[T]): HeapQueue[WeighedHuffmanTreeNode[T]] = - result = newHeapQueue[WeighedHuffmanTreeNode[T]]() - for item, count in stats.pairs: result.push(weighedHuffmanLeaf(item, count)) - -proc buildHuffmanTree*[T: SomeUnsignedInt](stats: CountTableRef[T]): HuffmanTreeNode[T] = - var symbolQueue = symbolQueue(stats) - while symbolQueue.len > 1: symbolQueue.push(weighedHuffmanBranch(symbolQueue.pop(), symbolQueue.pop())) - symbolQueue[0].huffmanTreeNode diff --git a/src/lzsschain.nim b/src/lzsschain.nim index 073aa5e..44200f2 100644 --- a/src/lzsschain.nim +++ b/src/lzsschain.nim @@ -15,7 +15,7 @@ # along with this program. If not, see . import lists, tables, sugar -import polyfill, integers, lzssnode, huffmantree +import polyfill, integers, lzssnode, huffman/huffmantree const maxChainByteLength = 32_000 * wordBitLength diff --git a/tests/thuffman.nim b/tests/thuffman.nim new file mode 100644 index 0000000..0294694 --- /dev/null +++ b/tests/thuffman.nim @@ -0,0 +1,119 @@ +# gzip-like LZSS compressor +# Copyright (C) 2018 Pacien TRAN-GIRARD +# +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU Affero General Public License as +# published by the Free Software Foundation, either version 3 of the +# License, or (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU Affero General Public License for more details. +# +# You should have received a copy of the GNU Affero General Public License +# along with this program. If not, see . + +import unittest, streams, sequtils, tables, heapqueue +import bitio/bitreader, bitio/bitwriter +import huffman/huffmantree, huffman/huffmantreebuilder, huffman/huffmanencoder, huffman/huffmandecoder + +let + stats = newCountTable(concat(repeat(1'u, 3), repeat(2'u, 1), repeat(3'u, 2))) + tree = huffmanBranch( + huffmanLeaf(1'u), + huffmanBranch( + huffmanLeaf(2'u), + huffmanLeaf(3'u))) + +suite "huffmantree": + test "equality": + check huffmanLeaf(12'u) == huffmanLeaf(12'u) + check huffmanLeaf(12'u) != huffmanLeaf(21'u) + check huffmanLeaf(12'u) != huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(12'u)) + check huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(21'u)) == huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(21'u)) + check huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(21'u)) != huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(1'u)) + check tree == tree + + test "maxValue": + check tree.maxValue() == 3 + + test "deserialise": + let stream = newStringStream() + defer: stream.close() + let bitWriter = stream.bitWriter() + bitWriter.writeBits(valueLengthFieldBitLength, 2'u8) + bitWriter.writeBool(false) # root + bitWriter.writeBool(true) # 1 leaf + bitWriter.writeBits(2, 1'u) + bitWriter.writeBool(false) # right branch + bitWriter.writeBool(true) # 2 leaf + bitWriter.writeBits(2, 2'u) + bitWriter.writeBool(true) # 3 leaf + bitWriter.writeBits(2, 3'u) + bitWriter.flush() + + stream.setPosition(0) + let bitReader = stream.bitReader() + check huffmantree.deserialise(bitReader, uint) == tree + + test "serialise": + let stream = newStringStream() + defer: stream.close() + let bitWriter = stream.bitWriter() + tree.serialise(bitWriter) + bitWriter.flush() + + stream.setPosition(0) + let bitReader = stream.bitReader() + check bitReader.readBits(valueLengthFieldBitLength, uint8) == 2 + check bitReader.readBool() == false # root + check bitReader.readBool() == true # 1 leaf + check bitReader.readBits(2, uint8) == 1 + check bitReader.readBool() == false # right branch + check bitReader.readBool() == true # 2 leaf + check bitReader.readBits(2, uint8) == 2 + check bitReader.readBool() == true # 3 leaf + check bitReader.readBits(2, uint8) == 3 + +suite "huffmantreebuilder": + test "buildHuffmanTree": + check buildHuffmanTree(stats) == tree + +suite "huffencoder": + let tree = huffmanBranch( + huffmanLeaf(1'u), + huffmanBranch( + huffmanLeaf(2'u), + huffmanLeaf(3'u))) + + test "buildCodebook": + let codebook = buildCodebook(tree, uint) + check codebook.len == 3 + check codebook[1'u] == 0b0 + check codebook[2'u] == 0b01 + check codebook[3'u] == 0b11 + + test "encode": + let encoder = tree.encoder(uint) + check encoder.encode(1'u) == 0b0 + check encoder.encode(2'u) == 0b01 + check encoder.encode(3'u) == 0b11 + +suite "huffdecoder": + test "decode": + let stream = newStringStream() + defer: stream.close() + let bitWriter = stream.bitWriter() + bitWriter.writeBool(true) # 2 + bitWriter.writeBool(false) + bitWriter.writeBool(false) # 1 + bitWriter.writeBool(true) # 3 + bitWriter.writeBool(true) + bitWriter.flush() + stream.setPosition(0) + let bitReader = stream.bitReader() + let decoder = tree.decoder() + check decoder.decode(bitReader) == 2'u + check decoder.decode(bitReader) == 1'u + check decoder.decode(bitReader) == 3'u diff --git a/tests/thuffmandecoder.nim b/tests/thuffmandecoder.nim deleted file mode 100644 index 9b44e9d..0000000 --- a/tests/thuffmandecoder.nim +++ /dev/null @@ -1,43 +0,0 @@ -# gzip-like LZSS compressor -# Copyright (C) 2018 Pacien TRAN-GIRARD -# -# This program is free software: you can redistribute it and/or modify -# it under the terms of the GNU Affero General Public License as -# published by the Free Software Foundation, either version 3 of the -# License, or (at your option) any later version. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU Affero General Public License for more details. -# -# You should have received a copy of the GNU Affero General Public License -# along with this program. If not, see . - -import unittest, streams -import bitio/bitreader, bitio/bitwriter -import huffmantree, huffmandecoder - -suite "huffdecoder": - let tree = huffmanBranch( - huffmanLeaf(1'u), - huffmanBranch( - huffmanLeaf(2'u), - huffmanLeaf(3'u))) - - test "decode": - let stream = newStringStream() - defer: stream.close() - let bitWriter = stream.bitWriter() - bitWriter.writeBool(true) # 2 - bitWriter.writeBool(false) - bitWriter.writeBool(false) # 1 - bitWriter.writeBool(true) # 3 - bitWriter.writeBool(true) - bitWriter.flush() - stream.setPosition(0) - let bitReader = stream.bitReader() - let decoder = tree.decoder() - check decoder.decode(bitReader) == 2'u - check decoder.decode(bitReader) == 1'u - check decoder.decode(bitReader) == 3'u diff --git a/tests/thuffmanencoder.nim b/tests/thuffmanencoder.nim deleted file mode 100644 index 9c46eed..0000000 --- a/tests/thuffmanencoder.nim +++ /dev/null @@ -1,39 +0,0 @@ -# gzip-like LZSS compressor -# Copyright (C) 2018 Pacien TRAN-GIRARD -# -# This program is free software: you can redistribute it and/or modify -# it under the terms of the GNU Affero General Public License as -# published by the Free Software Foundation, either version 3 of the -# License, or (at your option) any later version. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU Affero General Public License for more details. -# -# You should have received a copy of the GNU Affero General Public License -# along with this program. If not, see . - -import unittest, streams, tables -import bitio/bitreader, bitio/bitwriter -import huffmantree, huffmanencoder - -suite "huffencoder": - let tree = huffmanBranch( - huffmanLeaf(1'u), - huffmanBranch( - huffmanLeaf(2'u), - huffmanLeaf(3'u))) - - test "buildCodebook": - let codebook = buildCodebook(tree, uint) - check codebook.len == 3 - check codebook[1'u] == 0b0 - check codebook[2'u] == 0b01 - check codebook[3'u] == 0b11 - - test "encode": - let encoder = tree.encoder(uint) - check encoder.encode(1'u) == 0b0 - check encoder.encode(2'u) == 0b01 - check encoder.encode(3'u) == 0b11 diff --git a/tests/thuffmantree.nim b/tests/thuffmantree.nim deleted file mode 100644 index 467fac5..0000000 --- a/tests/thuffmantree.nim +++ /dev/null @@ -1,74 +0,0 @@ -# gzip-like LZSS compressor -# Copyright (C) 2018 Pacien TRAN-GIRARD -# -# This program is free software: you can redistribute it and/or modify -# it under the terms of the GNU Affero General Public License as -# published by the Free Software Foundation, either version 3 of the -# License, or (at your option) any later version. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU Affero General Public License for more details. -# -# You should have received a copy of the GNU Affero General Public License -# along with this program. If not, see . - -import unittest, streams, sequtils, tables, heapqueue -import bitio/bitreader, bitio/bitwriter, huffmantree - -suite "huffmantree": - let tree = huffmanBranch( - huffmanLeaf(1'u), - huffmanBranch( - huffmanLeaf(2'u), - huffmanLeaf(3'u))) - - test "equality": - check huffmanLeaf(12'u) == huffmanLeaf(12'u) - check huffmanLeaf(12'u) != huffmanLeaf(21'u) - check huffmanLeaf(12'u) != huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(12'u)) - check huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(21'u)) == huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(21'u)) - check huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(21'u)) != huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(1'u)) - check tree == tree - - test "maxValue": - check tree.maxValue() == 3 - - test "deserialise": - let stream = newStringStream() - defer: stream.close() - let bitWriter = stream.bitWriter() - bitWriter.writeBits(valueLengthFieldBitLength, 2'u8) - bitWriter.writeBool(false) # root - bitWriter.writeBool(true) # 1 leaf - bitWriter.writeBits(2, 1'u) - bitWriter.writeBool(false) # right branch - bitWriter.writeBool(true) # 2 leaf - bitWriter.writeBits(2, 2'u) - bitWriter.writeBool(true) # 3 leaf - bitWriter.writeBits(2, 3'u) - bitWriter.flush() - - stream.setPosition(0) - let bitReader = stream.bitReader() - check huffmantree.deserialise(bitReader, uint) == tree - - test "serialise": - let stream = newStringStream() - defer: stream.close() - let bitWriter = stream.bitWriter() - tree.serialise(bitWriter) - bitWriter.flush() - - stream.setPosition(0) - let bitReader = stream.bitReader() - check bitReader.readBits(valueLengthFieldBitLength, uint8) == 2 - check bitReader.readBool() == false # root - check bitReader.readBool() == true # 1 leaf - check bitReader.readBits(2, uint8) == 1 - check bitReader.readBool() == false # right branch - check bitReader.readBool() == true # 2 leaf - check bitReader.readBits(2, uint8) == 2 - check bitReader.readBool() == true # 3 leaf - check bitReader.readBits(2, uint8) == 3 diff --git a/tests/thuffmantreebuilder.nim b/tests/thuffmantreebuilder.nim deleted file mode 100644 index f782b37..0000000 --- a/tests/thuffmantreebuilder.nim +++ /dev/null @@ -1,29 +0,0 @@ -# gzip-like LZSS compressor -# Copyright (C) 2018 Pacien TRAN-GIRARD -# -# This program is free software: you can redistribute it and/or modify -# it under the terms of the GNU Affero General Public License as -# published by the Free Software Foundation, either version 3 of the -# License, or (at your option) any later version. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU Affero General Public License for more details. -# -# You should have received a copy of the GNU Affero General Public License -# along with this program. If not, see . - -import unittest, tables, sequtils -import huffmantree, huffmantreebuilder - -suite "huffmantreebuilder": - let stats = newCountTable(concat(repeat(1'u, 3), repeat(2'u, 1), repeat(3'u, 2))) - let tree = huffmanBranch( - huffmanLeaf(1'u), - huffmanBranch( - huffmanLeaf(2'u), - huffmanLeaf(3'u))) - - test "buildHuffmanTree": - check buildHuffmanTree(stats) == tree -- cgit v1.2.3