aboutsummaryrefslogtreecommitdiff
path: root/src/lzsshuffman
diff options
context:
space:
mode:
authorpacien2018-12-02 00:22:56 +0100
committerpacien2018-12-02 00:22:56 +0100
commit5cc4256a931b98ea167291397421d0db60c5d40c (patch)
tree54c7ba39e69fb31322db431a82dbf31aedbb53b9 /src/lzsshuffman
parent1850acb5b77aabbf4e9ba24ae6d5314c3d4d896a (diff)
downloadgziplike-5cc4256a931b98ea167291397421d0db60c5d40c.tar.gz
implement lzss block
Diffstat (limited to 'src/lzsshuffman')
-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
4 files changed, 134 insertions, 0 deletions
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#
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 tables, lists
18import ../lzss/lzssnode, ../lzss/lzsschain
19import lzsshuffmansymbol
20
21proc aggregateStats*(chain: LzssChain): tuple[symbolTable, positionTable: CountTableRef[uint16]] =
22 var (symbolTable, positionTable) = (newCountTable[uint16](), newCountTable[uint16]())
23 for node in chain.items:
24 case node.kind:
25 of character:
26 symbolTable.inc(node.character)
27 of reference:
28 symbolTable.inc(shiftLzssLength(node.length))
29 positionTable.inc(node.relativePos.uint16)
30 symbolTable.inc(endSymbol)
31 if positionTable.len < 1: positionTable.inc(0) # ensure non-empty tree
32 (symbolTable, positionTable)
diff --git a/src/lzsshuffman/lzsshuffmansymbol.nim b/src/lzsshuffman/lzsshuffmansymbol.nim
new file mode 100644
index 0000000..cfd3fe4
--- /dev/null
+++ b/src/lzsshuffman/lzsshuffmansymbol.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 ../lzss/lzssnode, ../lzss/lzssencoder
19
20type Symbol* = uint16
21
22const endSymbol* = 256.Symbol
23
24proc isEndMarker*(symbol: Symbol): bool =
25 symbol == endSymbol
26
27proc isCharacter*(symbol: Symbol): bool =
28 symbol < endSymbol
29
30proc unpackLzssReference*(symbol: Symbol, position: uint16): LzssNode =
31 lzssReference(symbol.int - endSymbol.int - 1 + matchGroupLength, position.int)
32
33proc shiftLzssLength*(length: int): uint16 =
34 (length + endSymbol.int + 1 - matchGroupLength).uint16