aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/huffmantree.nim31
-rw-r--r--src/lzsschain.nim12
2 files changed, 38 insertions, 5 deletions
diff --git a/src/huffmantree.nim b/src/huffmantree.nim
index 1711879..adcaec7 100644
--- a/src/huffmantree.nim
+++ b/src/huffmantree.nim
@@ -14,6 +14,7 @@
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 tables, heapqueue
17import integers, bitreader, bitwriter 18import integers, bitreader, bitwriter
18 19
19const valueLengthFieldBitLength* = 6 # 64 20const valueLengthFieldBitLength* = 6 # 64
@@ -28,19 +29,32 @@ type HuffmanTreeNode*[T: SomeUnsignedInt] = ref object
28 left, right: HuffmanTreeNode[T] 29 left, right: HuffmanTreeNode[T]
29 of leaf: 30 of leaf:
30 value: T 31 value: T
32 weight: int
31 33
32proc huffmanBranch*[T](left, right: HuffmanTreeNode[T]): HuffmanTreeNode[T] = 34proc huffmanBranch*[T](left, right: HuffmanTreeNode[T]): HuffmanTreeNode[T] =
33 HuffmanTreeNode[T](kind: branch, left: left, right: right) 35 HuffmanTreeNode[T](kind: branch, left: left, right: right, weight: left.weight + right.weight)
34 36
35proc huffmanLeaf*[T](value: T): HuffmanTreeNode[T] = 37proc huffmanLeaf*[T](value: T, weight = 0): HuffmanTreeNode[T] =
36 HuffmanTreeNode[T](kind: leaf, value: value) 38 HuffmanTreeNode[T](kind: leaf, value: value, weight: weight)
37 39
38proc `==`*[T](a, b: HuffmanTreeNode[T]): bool = 40proc `==`*[T](a, b: HuffmanTreeNode[T]): bool =
39 if a.kind != b.kind: return false 41 if a.kind != b.kind or a.weight != b.weight: return false
40 case a.kind: 42 case a.kind:
41 of branch: a.left == b.left and a.right == b.right 43 of branch: a.left == b.left and a.right == b.right
42 of leaf: a.value == b.value 44 of leaf: a.value == b.value
43 45
46proc `~=`*[T](a, b: HuffmanTreeNode[T]): bool =
47 if a.kind != b.kind: return false
48 case a.kind:
49 of branch: a.left ~= b.left and a.right ~= b.right
50 of leaf: a.value == b.value
51
52proc `!~`*[T](a, b: HuffmanTreeNode[T]): bool =
53 not (a ~= b)
54
55proc `<`*[T](left, right: HuffmanTreeNode[T]): bool =
56 left.weight < right.weight
57
44proc maxValue*[T](node: HuffmanTreeNode[T]): T = 58proc maxValue*[T](node: HuffmanTreeNode[T]): T =
45 case node.kind: 59 case node.kind:
46 of branch: max(node.left.maxValue(), node.right.maxValue()) 60 of branch: max(node.left.maxValue(), node.right.maxValue())
@@ -68,3 +82,12 @@ proc serialise*[T](tree: HuffmanTreeNode[T], bitWriter: BitWriter) =
68 bitWriter.writeBits(valueBitLength, node.value) 82 bitWriter.writeBits(valueBitLength, node.value)
69 bitWriter.writeBits(valueLengthFieldBitLength, valueBitLength.uint8) 83 bitWriter.writeBits(valueLengthFieldBitLength, valueBitLength.uint8)
70 writeNode(tree) 84 writeNode(tree)
85
86proc symbolQueue*[T](stats: CountTableRef[T]): HeapQueue[HuffmanTreeNode[T]] =
87 result = newHeapQueue[HuffmanTreeNode[T]]()
88 for item, count in stats.pairs: result.push(huffmanLeaf(item, count))
89
90proc buildHuffmanTree*[T: SomeUnsignedInt](stats: CountTableRef[T]): HuffmanTreeNode[T] =
91 var symbolQueue = symbolQueue(stats)
92 while symbolQueue.len > 1: symbolQueue.push(huffmanBranch(symbolQueue.pop(), symbolQueue.pop()))
93 result = symbolQueue[0]
diff --git a/src/lzsschain.nim b/src/lzsschain.nim
index 8203cb8..073aa5e 100644
--- a/src/lzsschain.nim
+++ b/src/lzsschain.nim
@@ -15,7 +15,7 @@
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 lists, tables, sugar 17import lists, tables, sugar
18import polyfill, integers, lzssnode 18import polyfill, integers, lzssnode, huffmantree
19 19
20const maxChainByteLength = 32_000 * wordBitLength 20const maxChainByteLength = 32_000 * wordBitLength
21 21
@@ -34,3 +34,13 @@ proc decode*(lzssChain: LzssChain): seq[uint8] =
34 of reference: 34 of reference:
35 let absolutePos = result.len - node.relativePos 35 let absolutePos = result.len - node.relativePos
36 result.add(result.toOpenArray(absolutePos, absolutePos + node.length - 1)) 36 result.add(result.toOpenArray(absolutePos, absolutePos + node.length - 1))
37
38proc stats*(lzssChain: LzssChain): tuple[characters: CountTableRef[uint8], lengths, positions: CountTableRef[int]] =
39 result = (newCountTable[uint8](), newCountTable[int](), newCountTable[int]())
40 for node in lzssChain.items:
41 case node.kind:
42 of character:
43 result.characters.inc(node.character)
44 of reference:
45 result.lengths.inc(node.length)
46 result.positions.inc(node.relativePos)