From 4361a9e9c918bc4feff4d04e47dbe686b1d31a6c Mon Sep 17 00:00:00 2001 From: pacien Date: Fri, 30 Nov 2018 14:38:09 +0100 Subject: add huffman encoder --- src/huffmanencoder.nim | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) create mode 100644 src/huffmanencoder.nim (limited to 'src/huffmanencoder.nim') 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 @@ +# 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, 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] -- cgit v1.2.3