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 --- tests/thuffman.nim | 119 ++++++++++++++++++++++++++++++++++++++++++ tests/thuffmandecoder.nim | 43 --------------- tests/thuffmanencoder.nim | 39 -------------- tests/thuffmantree.nim | 74 -------------------------- tests/thuffmantreebuilder.nim | 29 ---------- 5 files changed, 119 insertions(+), 185 deletions(-) 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 (limited to 'tests') 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