From d9768cd0315b0415d20818de9c897c6168c95b78 Mon Sep 17 00:00:00 2001 From: pacien Date: Fri, 23 Nov 2018 12:57:00 +0100 Subject: Split bitstream into bitreader and bitwriter --- src/bitreader.nim | 72 +++++++++++++++++++++++++++++++++ src/bitstream.nim | 112 ---------------------------------------------------- src/bitwriter.nim | 59 +++++++++++++++++++++++++++ src/integers.nim | 7 ++++ src/lzssblock.nim | 10 ++--- src/rawblock.nim | 22 +++++------ src/streamblock.nim | 37 ++++++++--------- 7 files changed, 173 insertions(+), 146 deletions(-) create mode 100644 src/bitreader.nim delete mode 100644 src/bitstream.nim create mode 100644 src/bitwriter.nim (limited to 'src') diff --git a/src/bitreader.nim b/src/bitreader.nim new file mode 100644 index 0000000..35e9d57 --- /dev/null +++ b/src/bitreader.nim @@ -0,0 +1,72 @@ +# "à-la-gzip" 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 streams +import integers + +# Stream functions + +proc newEIO(msg: string): ref IOError = + new(result) + result.msg = msg + +proc read[T](s: Stream, t: typedesc[T]): T = + if readData(s, addr(result), sizeof(T)) != sizeof(T): + raise newEIO("cannot read from stream") + +proc peek[T](s: Stream, t: typedesc[T]): T = + if peekData(s, addr(result), sizeof(T)) != sizeof(T): + raise newEIO("cannot read from stream") + +# BitReader + +type BitReader* = ref object + stream: Stream + bitOffset: int + +proc bitReader*(stream: Stream): BitReader = + BitReader(stream: stream, bitOffset: 0) + +proc atEnd*(bitReader: BitReader): bool = + bitReader.stream.atEnd() + +proc readBits*[T: SomeUnsignedInt](bitReader: BitReader, bits: int, to: typedesc[T]): T = + let targetBitLength = sizeof(T) * wordBitLength + if bits < 0 or bits > targetBitLength: + raise newException(RangeError, "invalid bit length") + elif bits == 0: + result = 0 + elif bits < targetBitLength - bitReader.bitOffset: + result = bitReader.stream.peek(T) shl (targetBitLength - bits - bitReader.bitOffset) shr (targetBitLength - bits) + elif bits == targetBitLength - bitReader.bitOffset: + result = bitReader.stream.read(T) shl (targetBitLength - bits - bitReader.bitOffset) shr (targetBitLength - bits) + else: + let rightBits = targetBitLength - bitReader.bitOffset + let leftBits = bits - rightBits + let right = bitReader.stream.read(T) shr bitReader.bitOffset + let left = bitReader.stream.peek(T) shl (targetBitLength - leftBits) shr (targetBitLength - bits) + result = left or right + bitReader.bitOffset = (bitReader.bitOffset + bits) mod wordBitLength + +proc readBool*(bitReader: BitReader): bool = + bitReader.readBits(1, uint8) != 0 + +proc readSeq*[T: SomeUnsignedInt](bitReader: BitReader, bitLength: int, to: typedesc[T]): tuple[bitLength: int, data: seq[T]] = + result = (0, newSeqOfCap[T](bitLength /^ (sizeof(T) * wordBitLength))) + for _, chunkBitLength in chunks(bitLength, T): + if bitReader.atEnd(): return + result.bitLength += chunkBitLength + result.data.add(bitReader.readBits(chunkBitLength, T)) diff --git a/src/bitstream.nim b/src/bitstream.nim deleted file mode 100644 index 81401ce..0000000 --- a/src/bitstream.nim +++ /dev/null @@ -1,112 +0,0 @@ -# "à-la-gzip" 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 streams -import integers - -# Stream functions - -proc newEIO(msg: string): ref IOError = - new(result) - result.msg = msg - -proc read[T](s: Stream, t: typedesc[T]): T = - if readData(s, addr(result), sizeof(T)) != sizeof(T): - raise newEIO("cannot read from stream") - -proc peek[T](s: Stream, t: typedesc[T]): T = - if peekData(s, addr(result), sizeof(T)) != sizeof(T): - raise newEIO("cannot read from stream") - -# Utils - -iterator chunks*(totalBitLength: int, chunkType: typedesc[SomeInteger]): tuple[index: int, chunkBitLength: int] = - let chunkBitLength = sizeof(chunkType) * wordBitLength - let wordCount = totalBitLength div chunkBitLength - for i in 0..<(wordCount): yield (i, chunkBitLength) - let remainder = totalBitLength mod chunkBitLength - if remainder > 0: yield (wordCount, remainder) - -# BitStream - -type BitStream* = ref object - stream: Stream - bitOffset: int - writeBuffer: uint8 - -proc bitStream*(stream: Stream): BitStream = - BitStream(stream: stream, bitOffset: 0, writeBuffer: 0) - -proc flush*(bitStream: BitStream) = - if bitStream.bitOffset == 0: return - bitStream.stream.write(bitStream.writeBuffer) - bitStream.stream.flush() - (bitStream.bitOffset, bitStream.writeBuffer) = (0, 0'u8) - -proc atEnd*(bitStream: BitStream): bool = - bitStream.stream.atEnd() - -proc readBits*[T: SomeUnsignedInt](bitStream: BitStream, bits: int, to: typedesc[T]): T = - let targetBitLength = sizeof(T) * wordBitLength - if bits < 0 or bits > targetBitLength: - raise newException(RangeError, "invalid bit length") - elif bits == 0: - result = 0 - elif bits < targetBitLength - bitStream.bitOffset: - result = bitStream.stream.peek(T) shl (targetBitLength - bits - bitStream.bitOffset) shr (targetBitLength - bits) - elif bits == targetBitLength - bitStream.bitOffset: - result = bitStream.stream.read(T) shl (targetBitLength - bits - bitStream.bitOffset) shr (targetBitLength - bits) - else: - let rightBits = targetBitLength - bitStream.bitOffset - let leftBits = bits - rightBits - let right = bitStream.stream.read(T) shr bitStream.bitOffset - let left = bitStream.stream.peek(T) shl (targetBitLength - leftBits) shr (targetBitLength - bits) - result = left or right - bitStream.bitOffset = (bitStream.bitOffset + bits) mod wordBitLength - -proc readBool*(bitStream: BitStream): bool = - bitStream.readBits(1, uint8) != 0 - -proc readSeq*[T: SomeUnsignedInt](bitStream: BitStream, bitLength: int, to: typedesc[T]): tuple[bitLength: int, data: seq[T]] = - result = (0, newSeqOfCap[T](bitLength /^ (sizeof(T) * wordBitLength))) - for _, chunkBitLength in chunks(bitLength, T): - if bitStream.atEnd(): return - result.bitLength += chunkBitLength - result.data.add(bitStream.readBits(chunkBitLength, T)) - -proc writeBits*(bitStream: BitStream, bits: int, value: SomeUnsignedInt) = - let valueContainerBitLength = sizeof(value) * wordBitLength - if bits < 0 or bits > valueContainerBitLength: - raise newException(RangeError, "invalid bit length") - var bitsToWrite = bits - if bitsToWrite + bitStream.bitOffset >= wordBitLength: - bitStream.stream.write(truncateToUint8(value shl bitStream.bitOffset) or bitStream.writeBuffer) - bitsToWrite -= wordBitLength - bitStream.bitOffset - (bitStream.bitOffset, bitStream.writeBuffer) = (0, 0'u8) - while bitsToWrite >= wordBitLength: - bitStream.stream.write(truncateToUint8(value shr (bits - bitsToWrite))) - bitsToWrite -= wordBitLength - if bitsToWrite > 0: - let left = truncateToUint8((value shl (valueContainerBitLength - bits)) shr (valueContainerBitLength - bitsToWrite)) - bitStream.writeBuffer = (left shl bitStream.bitOffset) or bitStream.writeBuffer - bitStream.bitOffset = (bitStream.bitOffset + bitsToWrite) mod wordBitLength - -proc writeBool*(bitStream: BitStream, value: bool) = - bitStream.writeBits(1, value.uint8) - -proc writeSeq*[T: SomeUnsignedInt](bitStream: BitStream, bitLength: int, data: seq[T]) = - for i, chunkBitLength in chunks(bitLength, T): - bitStream.writeBits(chunkBitLength, data[i]) diff --git a/src/bitwriter.nim b/src/bitwriter.nim new file mode 100644 index 0000000..aac96f9 --- /dev/null +++ b/src/bitwriter.nim @@ -0,0 +1,59 @@ +# "à-la-gzip" 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 streams +import integers + +type BitWriter* = ref object + stream: Stream + bitOffset: int + writeBuffer: uint8 + +proc bitWriter*(stream: Stream): BitWriter = + BitWriter(stream: stream, bitOffset: 0, writeBuffer: 0) + +proc flush*(bitWriter: BitWriter) = + if bitWriter.bitOffset == 0: return + bitWriter.stream.write(bitWriter.writeBuffer) + bitWriter.stream.flush() + (bitWriter.bitOffset, bitWriter.writeBuffer) = (0, 0'u8) + +proc atEnd*(bitWriter: BitWriter): bool = + bitWriter.stream.atEnd() + +proc writeBits*(bitWriter: BitWriter, bits: int, value: SomeUnsignedInt) = + let valueContainerBitLength = sizeof(value) * wordBitLength + if bits < 0 or bits > valueContainerBitLength: + raise newException(RangeError, "invalid bit length") + var bitsToWrite = bits + if bitsToWrite + bitWriter.bitOffset >= wordBitLength: + bitWriter.stream.write(truncateToUint8(value shl bitWriter.bitOffset) or bitWriter.writeBuffer) + bitsToWrite -= wordBitLength - bitWriter.bitOffset + (bitWriter.bitOffset, bitWriter.writeBuffer) = (0, 0'u8) + while bitsToWrite >= wordBitLength: + bitWriter.stream.write(truncateToUint8(value shr (bits - bitsToWrite))) + bitsToWrite -= wordBitLength + if bitsToWrite > 0: + let left = truncateToUint8((value shl (valueContainerBitLength - bits)) shr (valueContainerBitLength - bitsToWrite)) + bitWriter.writeBuffer = (left shl bitWriter.bitOffset) or bitWriter.writeBuffer + bitWriter.bitOffset = (bitWriter.bitOffset + bitsToWrite) mod wordBitLength + +proc writeBool*(bitWriter: BitWriter, value: bool) = + bitWriter.writeBits(1, value.uint8) + +proc writeSeq*[T: SomeUnsignedInt](bitWriter: BitWriter, bitLength: int, data: seq[T]) = + for i, chunkBitLength in chunks(bitLength, T): + bitWriter.writeBits(chunkBitLength, data[i]) diff --git a/src/integers.nim b/src/integers.nim index 1b9121c..1f83488 100644 --- a/src/integers.nim +++ b/src/integers.nim @@ -22,3 +22,10 @@ proc `/^`*[T: Natural](x, y: T): T = proc truncateToUint8*(x: SomeUnsignedInt): uint8 = (x and wordBitMask).uint8 + +iterator chunks*(totalBitLength: int, chunkType: typedesc[SomeInteger]): tuple[index: int, chunkBitLength: int] = + let chunkBitLength = sizeof(chunkType) * wordBitLength + let wordCount = totalBitLength div chunkBitLength + for i in 0..<(wordCount): yield (i, chunkBitLength) + let remainder = totalBitLength mod chunkBitLength + if remainder > 0: yield (wordCount, remainder) diff --git a/src/lzssblock.nim b/src/lzssblock.nim index 87b62a0..959ad09 100644 --- a/src/lzssblock.nim +++ b/src/lzssblock.nim @@ -14,19 +14,19 @@ # You should have received a copy of the GNU Affero General Public License # along with this program. If not, see . -import bitstream +import bitreader, bitwriter type LzssBlock* = object discard -proc readSerialised*(bitStream: BitStream): LzssBlock = +proc readSerialised*(bitReader: BitReader): LzssBlock = discard -proc writeSerialisedTo*(lzssBlock: LzssBlock, bitStream: BitStream) = +proc writeSerialisedTo*(lzssBlock: LzssBlock, bitWriter: BitWriter) = discard -proc readRaw*(bitStream: BitStream): LzssBlock = +proc readRaw*(bitReader: BitReader): LzssBlock = discard -proc writeRawTo*(lzssBlock: LzssBlock, bitStream: BitStream) = +proc writeRawTo*(lzssBlock: LzssBlock, bitWriter: BitWriter) = discard diff --git a/src/rawblock.nim b/src/rawblock.nim index bdbfc71..aa3e7ae 100644 --- a/src/rawblock.nim +++ b/src/rawblock.nim @@ -14,7 +14,7 @@ # You should have received a copy of the GNU Affero General Public License # along with this program. If not, see . -import integers, bitstream +import integers, bitreader, bitwriter const maxDataBitLength = 100_000_000 * wordBitLength # 100MB const bitLengthFieldBitLength = 2 * wordBitLength @@ -23,18 +23,18 @@ type RawBlock* = object bitLength: int data: seq[uint8] -proc readSerialised*(bitStream: BitStream): RawBlock = - let bitLength = bitStream.readBits(bitLengthFieldBitLength, uint16).int - let data = readSeq(bitStream, bitLength, uint8) +proc readSerialised*(bitReader: BitReader): RawBlock = + let bitLength = bitReader.readBits(bitLengthFieldBitLength, uint16).int + let data = readSeq(bitReader, bitLength, uint8) RawBlock(bitLength: bitLength, data: data.data) -proc writeSerialisedTo*(rawBlock: RawBlock, bitStream: BitStream) = - bitStream.writeBits(bitLengthFieldBitLength, rawBlock.bitLength.uint16) - writeSeq(bitStream, rawBlock.bitLength, rawBlock.data) +proc writeSerialisedTo*(rawBlock: RawBlock, bitWriter: BitWriter) = + bitWriter.writeBits(bitLengthFieldBitLength, rawBlock.bitLength.uint16) + bitWriter.writeSeq(rawBlock.bitLength, rawBlock.data) -proc readRaw*(bitStream: BitStream, bits: int = maxDataBitLength): RawBlock = - let data = readSeq(bitStream, bits, uint8) +proc readRaw*(bitReader: BitReader, bits: int = maxDataBitLength): RawBlock = + let data = readSeq(bitReader, bits, uint8) RawBlock(bitLength: data.bitLength, data: data.data) -proc writeRawTo*(rawBlock: RawBlock, bitStream: BitStream) = - writeSeq(bitStream, rawBlock.bitLength, rawBlock.data) +proc writeRawTo*(rawBlock: RawBlock, bitWriter: BitWriter) = + bitWriter.writeSeq(rawBlock.bitLength, rawBlock.data) diff --git a/src/streamblock.nim b/src/streamblock.nim index 8d2b4b1..eef916f 100644 --- a/src/streamblock.nim +++ b/src/streamblock.nim @@ -15,7 +15,8 @@ # along with this program. If not, see . import sequtils -import integers, bitstream, rawblock, lzssblock +import integers, bitreader, bitwriter +import rawblock, lzssblock type BlockKind* = enum uncompressed = 0b00'u8, @@ -33,32 +34,32 @@ type StreamBlock* = object else: discard -proc readSerialised*(bitStream: BitStream): StreamBlock = - result.last = bitStream.readBool() - result.kind = bitStream.readBits(2, uint8).BlockKind +proc readSerialised*(bitReader: BitReader): StreamBlock = + result.last = bitReader.readBool() + result.kind = bitReader.readBits(2, uint8).BlockKind case result.kind: - of uncompressed: result.rawBlock = rawblock.readRaw(bitStream) - of lzss: result.lzssBlock = lzssblock.readRaw(bitStream) + of uncompressed: result.rawBlock = rawblock.readRaw(bitReader) + of lzss: result.lzssBlock = lzssblock.readRaw(bitReader) else: raise newException(ValueError, "unhandled block type") -proc writeSerialisedTo*(streamBlock: StreamBlock, bitStream: BitStream) = - bitStream.writeBool(streamBlock.last) - bitStream.writeBits(2, streamBlock.kind.uint8) +proc writeSerialisedTo*(streamBlock: StreamBlock, bitWriter: BitWriter) = + bitWriter.writeBool(streamBlock.last) + bitWriter.writeBits(2, streamBlock.kind.uint8) case streamBlock.kind: - of uncompressed: streamBlock.rawBlock.writeSerialisedTo(bitStream) - of lzss: streamBlock.lzssBlock.writeSerialisedTo(bitStream) + of uncompressed: streamBlock.rawBlock.writeSerialisedTo(bitWriter) + of lzss: streamBlock.lzssBlock.writeSerialisedTo(bitWriter) else: raise newException(ValueError, "unhandled block type") -proc readRaw*(bitStream: BitStream, kind: BlockKind = uncompressed): StreamBlock = +proc readRaw*(bitReader: BitReader, kind: BlockKind = uncompressed): StreamBlock = result.kind = kind case kind: - of uncompressed: result.rawBlock = rawblock.readRaw(bitStream) - of lzss: result.lzssBlock = lzssblock.readRaw(bitStream) + of uncompressed: result.rawBlock = rawblock.readRaw(bitReader) + of lzss: result.lzssBlock = lzssblock.readRaw(bitReader) else: raise newException(ValueError, "unhandled block type") - result.last = bitStream.atEnd() + result.last = bitReader.atEnd() -proc writeRawTo*(streamBlock: StreamBlock, bitStream: BitStream) = +proc writeRawTo*(streamBlock: StreamBlock, bitWriter: BitWriter) = case streamBlock.kind: - of uncompressed: streamBlock.rawBlock.writeRawTo(bitStream) - of lzss: streamBlock.lzssBlock.writeRawTo(bitStream) + of uncompressed: streamBlock.rawBlock.writeRawTo(bitWriter) + of lzss: streamBlock.lzssBlock.writeRawTo(bitWriter) else: raise newException(ValueError, "unhandled block type") -- cgit v1.2.3