aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/blocks/lzssblock.nim31
-rw-r--r--src/huffman/huffmantree.nim10
-rw-r--r--src/lzss/lzsschain.nim17
-rw-r--r--src/lzss/lzssencoder.nim2
-rw-r--r--src/lzsshuffman/lzsshuffmandecoder.nim34
-rw-r--r--src/lzsshuffman/lzsshuffmanencoder.nim34
-rw-r--r--src/lzsshuffman/lzsshuffmanstats.nim32
-rw-r--r--src/lzsshuffman/lzsshuffmansymbol.nim34
8 files changed, 171 insertions, 23 deletions
diff --git a/src/blocks/lzssblock.nim b/src/blocks/lzssblock.nim
index f68f665..b23cee2 100644
--- a/src/blocks/lzssblock.nim
+++ b/src/blocks/lzssblock.nim
@@ -14,19 +14,38 @@
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 ../bitio/bitreader, ../bitio/bitwriter 17import lists
18import ../bitio/integers, ../bitio/bitreader, ../bitio/bitwriter
19import ../lzss/lzsschain, ../lzss/lzssencoder
20import ../huffman/huffmantree, ../huffman/huffmantreebuilder, ../huffman/huffmanencoder, ../huffman/huffmandecoder
21import ../lzsshuffman/lzsshuffmanstats, ../lzsshuffman/lzsshuffmandecoder, ../lzsshuffman/lzsshuffmanencoder
22
23const maxDataByteLength = 32_000
18 24
19type LzssBlock* = object 25type LzssBlock* = object
20 discard 26 lzssChain: LzssChain
21 27
22proc readSerialised*(bitReader: BitReader): LzssBlock = 28proc readSerialised*(bitReader: BitReader): LzssBlock =
23 discard 29 let symbolHuffmanTree = huffmantree.deserialise(bitReader, uint16)
30 let positionHuffmanTree = huffmantree.deserialise(bitReader, uint16)
31 let symbolDecoder = symbolHuffmanTree.decoder()
32 let positionDecoder = positionHuffmanTree.decoder()
33 LzssBlock(lzssChain: readChain(bitReader, symbolDecoder, positionDecoder, maxDataByteLength))
24 34
25proc writeSerialisedTo*(lzssBlock: LzssBlock, bitWriter: BitWriter) = 35proc writeSerialisedTo*(lzssBlock: LzssBlock, bitWriter: BitWriter) =
26 discard 36 let (symbolStats, positionStats) = aggregateStats(lzssBlock.lzssChain)
37 let symbolHuffmanTree = buildHuffmanTree(symbolStats)
38 let positionHuffmanTree = buildHuffmanTree(positionStats)
39 let symbolEncoder = symbolHuffmanTree.encoder(uint16)
40 let positionEncoder = positionHuffmanTree.encoder(uint16)
41 symbolHuffmanTree.serialise(bitWriter)
42 positionHuffmanTree.serialise(bitWriter)
43 lzssBlock.lzssChain.writeChain(symbolEncoder, positionEncoder, bitWriter)
27 44
28proc readRaw*(bitReader: BitReader): LzssBlock = 45proc readRaw*(bitReader: BitReader): LzssBlock =
29 discard 46 let byteBuf = bitReader.readSeq(maxDataByteLength, uint8)
47 LzssBlock(lzssChain: lzssEncode(byteBuf.data))
30 48
31proc writeRawTo*(lzssBlock: LzssBlock, bitWriter: BitWriter) = 49proc writeRawTo*(lzssBlock: LzssBlock, bitWriter: BitWriter) =
32 discard 50 let byteSeq = lzssBlock.lzssChain.decode()
51 bitWriter.writeSeq(byteSeq.len * wordBitLength, byteSeq)
diff --git a/src/huffman/huffmantree.nim b/src/huffman/huffmantree.nim
index 58a840e..f3fce1b 100644
--- a/src/huffman/huffmantree.nim
+++ b/src/huffman/huffmantree.nim
@@ -31,6 +31,11 @@ type HuffmanTreeNode*[T: SomeUnsignedInt] = ref object
31 of leaf: 31 of leaf:
32 value*: T 32 value*: T
33 33
34proc maxValue*[T](node: HuffmanTreeNode[T]): T =
35 case node.kind:
36 of branch: node.maxChildValue
37 of leaf: node.value
38
34proc huffmanBranch*[T](left, right: HuffmanTreeNode[T]): HuffmanTreeNode[T] = 39proc huffmanBranch*[T](left, right: HuffmanTreeNode[T]): HuffmanTreeNode[T] =
35 HuffmanTreeNode[T]( 40 HuffmanTreeNode[T](
36 kind: branch, left: left, right: right, 41 kind: branch, left: left, right: right,
@@ -45,11 +50,6 @@ proc `==`*[T](a, b: HuffmanTreeNode[T]): bool =
45 of branch: a.left == b.left and a.right == b.right 50 of branch: a.left == b.left and a.right == b.right
46 of leaf: a.value == b.value 51 of leaf: a.value == b.value
47 52
48proc maxValue*[T](node: HuffmanTreeNode[T]): T =
49 case node.kind:
50 of branch: node.maxChildValue
51 of leaf: node.value
52
53proc deserialise*[T](bitReader: BitReader, valueType: typedesc[T]): HuffmanTreeNode[T] = 53proc deserialise*[T](bitReader: BitReader, valueType: typedesc[T]): HuffmanTreeNode[T] =
54 let valueBitLength = bitReader.readBits(valueLengthFieldBitLength, uint8).int 54 let valueBitLength = bitReader.readBits(valueLengthFieldBitLength, uint8).int
55 proc readNode(): HuffmanTreeNode[T] = 55 proc readNode(): HuffmanTreeNode[T] =
diff --git a/src/lzss/lzsschain.nim b/src/lzss/lzsschain.nim
index 8b49914..8ebcb1a 100644
--- a/src/lzss/lzsschain.nim
+++ b/src/lzss/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 ../bitio/integers, ../huffman/huffmantree 18import ../bitio/integers
19import listpolyfill, lzssnode 19import listpolyfill, lzssnode
20 20
21const maxChainByteLength = 32_000 * wordBitLength 21const maxChainByteLength = 32_000 * wordBitLength
@@ -26,6 +26,11 @@ type LzssChain* =
26proc lzssChain*(): LzssChain = 26proc lzssChain*(): LzssChain =
27 initSinglyLinkedList[LzssNode]() 27 initSinglyLinkedList[LzssNode]()
28 28
29proc lzssChain*(chainArray: openArray[LzssNode]): LzssChain =
30 var chain = lzssChain()
31 for node in chainArray: chain.append(node)
32 chain
33
29proc decode*(lzssChain: LzssChain): seq[uint8] = 34proc decode*(lzssChain: LzssChain): seq[uint8] =
30 result = newSeqOfCap[uint8](maxChainByteLength) 35 result = newSeqOfCap[uint8](maxChainByteLength)
31 for node in lzssChain.items: 36 for node in lzssChain.items:
@@ -35,13 +40,3 @@ proc decode*(lzssChain: LzssChain): seq[uint8] =
35 of reference: 40 of reference:
36 let absolutePos = result.len - node.relativePos 41 let absolutePos = result.len - node.relativePos
37 result.add(result.toOpenArray(absolutePos, absolutePos + node.length - 1)) 42 result.add(result.toOpenArray(absolutePos, absolutePos + node.length - 1))
38
39proc stats*(lzssChain: LzssChain): tuple[characters: CountTableRef[uint8], lengths, positions: CountTableRef[int]] =
40 result = (newCountTable[uint8](), newCountTable[int](), newCountTable[int]())
41 for node in lzssChain.items:
42 case node.kind:
43 of character:
44 result.characters.inc(node.character)
45 of reference:
46 result.lengths.inc(node.length)
47 result.positions.inc(node.relativePos)
diff --git a/src/lzss/lzssencoder.nim b/src/lzss/lzssencoder.nim
index 8b750fb..82fbe7b 100644
--- a/src/lzss/lzssencoder.nim
+++ b/src/lzss/lzssencoder.nim
@@ -17,7 +17,7 @@
17import lists 17import lists
18import listpolyfill, matchtable, lzssnode, lzsschain 18import listpolyfill, matchtable, lzssnode, lzsschain
19 19
20const matchGroupLength = 3 20const matchGroupLength* = 3
21const maxRefByteLength = high(uint8).int + matchGroupLength 21const maxRefByteLength = high(uint8).int + matchGroupLength
22let emptySinglyLinkedList = initSinglyLinkedList[int]() 22let emptySinglyLinkedList = initSinglyLinkedList[int]()
23 23
diff --git a/src/lzsshuffman/lzsshuffmandecoder.nim b/src/lzsshuffman/lzsshuffmandecoder.nim
new file mode 100644
index 0000000..cd71914
--- /dev/null
+++ b/src/lzsshuffman/lzsshuffmandecoder.nim
@@ -0,0 +1,34 @@
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 lists
18import ../bitio/bitreader
19import ../lzss/listpolyfill, ../lzss/lzssnode, ../lzss/lzsschain
20import ../huffman/huffmantree, ../huffman/huffmandecoder
21import lzsshuffmansymbol
22
23proc readChain*(bitReader: BitReader, symbolDecoder, positionDecoder: HuffmanDecoder[uint16], maxDataByteLength: int): LzssChain =
24 var chain = lzssChain()
25 var (symbol, byteCursor) = (symbolDecoder.decode(bitReader).Symbol, 0)
26 while not symbol.isEndMarker():
27 if byteCursor > maxDataByteLength: raise newException(IOError, "lzss block too long")
28 if symbol.isCharacter():
29 chain.append(lzssCharacter(symbol.uint8))
30 else:
31 let position = positionDecoder.decode(bitReader)
32 chain.append(unpackLzssReference(symbol, position))
33 (symbol, byteCursor) = (symbolDecoder.decode(bitReader).Symbol, byteCursor + 1)
34 chain
diff --git a/src/lzsshuffman/lzsshuffmanencoder.nim b/src/lzsshuffman/lzsshuffmanencoder.nim
new file mode 100644
index 0000000..ea89f85
--- /dev/null
+++ b/src/lzsshuffman/lzsshuffmanencoder.nim
@@ -0,0 +1,34 @@
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 lists
18import ../bitio/bitwriter
19import ../lzss/listpolyfill, ../lzss/lzssnode, ../lzss/lzsschain, ../lzss/lzssencoder
20import ../huffman/huffmantree, ../huffman/huffmantreebuilder, ../huffman/huffmanencoder
21import lzsshuffmansymbol
22
23proc writeSymbol(bitWriter: BitWriter, encodedSymbol: tuple[bitLength: int, value: uint16]) =
24 bitWriter.writeBits(encodedSymbol.bitLength, encodedSymbol.value)
25
26proc writeChain*(lzssChain: LzssChain, symbolEncoder, positionEncoder: HuffmanEncoder[uint16, uint16], bitWriter: BitWriter) =
27 for node in lzssChain.items:
28 case node.kind:
29 of character:
30 bitWriter.writeSymbol(symbolEncoder.encode(node.character))
31 of reference:
32 bitWriter.writeSymbol(symbolEncoder.encode(shiftLzssLength(node.length)))
33 bitWriter.writeSymbol(positionEncoder.encode(node.relativePos.uint16))
34 bitWriter.writeSymbol(symbolEncoder.encode(endSymbol))
diff --git a/src/lzsshuffman/lzsshuffmanstats.nim b/src/lzsshuffman/lzsshuffmanstats.nim
new file mode 100644
index 0000000..037ce5f
--- /dev/null
+++ b/src/lzsshuffman/lzsshuffmanstats.nim
@@ -0,0 +1,32 @@
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#