Standard library · Encoding and data

compress

Byte buffers, compression methods from RLE through DEFLATE, gzip and checksums.

import compress

On this page

Types
Constants and variables
Functions

This package is the base of all binary data work in Salam: ByteBuf and ByteReader are what packages such as encoding/binary, archive and encoding/msgpack pass around.

For compression, reach for gzip when the data has to be read by other programs. The other methods are mostly there to learn from and experiment with, and their output format belongs to this package alone. The examples show that for small data the overhead of Huffman and DEFLATE comes to more than the data itself.

Types

`Method`

enum Method

The compression method, as an enum.

Name	Type	Description
`None`		No compression.
`RLE`		Run length encoding.
`Huffman`		Huffman.
`LZ77`		LZ77.
`LZW`		LZW.
`Deflate`		LZ77 and Huffman.
`BWT`		Burrows Wheeler.

compress-Methods.salam

import compress

func main:
    text := "ababababab hello hello hello hello hello hello hello hello"
    b := compress.BufFromStr(text)
    each method in [compress.MethodNone, compress.MethodRLE, compress.MethodHuffman, compress.MethodLZ77, compress.MethodLZW, compress.MethodDeflate, compress.MethodBWT]:
        mut c := compress.CompressBuf(method, b)
        mut back := compress.DecompressBuf(method, c)
        println method, compress.BufLen(c), compress.BufEquals(b, back)
        compress.BufFree(c)
        compress.BufFree(back)
    end
    mut best := 0
    c := compress.CompressBest(b.data, b.len, best)
    println best, compress.Ratio(c.len, b.len) < 1.0
    s := compress.CompressStr(compress.MethodDeflate, "aaaaaaaaaa")
    b3 := compress.Decompress(compress.MethodDeflate, s.data, s.len)
    println compress.BufToStrUnsafe(b3)
    b4 := compress.Compress(compress.MethodRLE, b.data, b.len)
    println compress.BufLen(b4) > 0, compress.Method.Huffman
    println compress.BufLen(compress.RLEDecompress(compress.RLECompress(b.data, b.len).data, compress.RLECompress(b.data, b.len).len)) == b.len
    h := compress.HuffmanCompress(b.data, b.len)
    println compress.BufEquals(compress.HuffmanDecompress(h.data, h.len), b)
    l := compress.LZ77Compress(b.data, b.len)
    println compress.BufEquals(compress.LZ77Decompress(l.data, l.len), b)
    w := compress.LZWCompress(b.data, b.len)
    println compress.BufEquals(compress.LZWDecompress(w.data, w.len), b)
    bw := compress.BWTCompress(b.data, b.len)
    println compress.BufEquals(compress.BWTDecompress(bw.data, bw.len), b)
    mut primary := 0
    t := compress.BWTTransform(b.data, 3, primary)
    println primary, compress.BufToStrUnsafe(compress.BWTInverse(t.data, t.len, primary)) == "aba"
    m := compress.MTFEncode(b)
    println compress.BufEquals(compress.MTFDecode(m), b)
end

Output0 62 true 1 63 true 2 281 true 3 22 true 4 35 true 5 545 true 6 282 true 3 true aaaaaaaaaa true 2 true true true true true 1 true true

`ByteBuf`

struct ByteBuf

A byte buffer: an array of bytes that grows by itself. Most packages in this group take and give binary data in one.

Name	Type	Description
`data`	`void*`	The memory address of the bytes.
`len`	`int = 0`	The number of bytes.
`cap`	`int = 0`	The capacity.

compress-Buffer.salam

import compress

func main:
    mut b := compress.NewByteBufCap(16)
    compress.BufPush(b, 72)
    compress.BufPush(b, 105)
    mut other := compress.BufFromStr("!!")
    compress.BufPushBuf(b, other)
    compress.BufPushBytes(b, other.data, 1)
    compress.BufPushU32(b, 10)
    println compress.BufLen(b), compress.BufGet(b, 0), compress.BufToBase64(b)
    compress.BufSet(b, 0, 104)
    c := compress.BufClone(b)
    println compress.BufEquals(b, c), compress.BufToStrUnsafe(compress.BufFromStr("hello"))
    mut r := compress.ReaderFromBuf(b)
    println compress.RdLeft(r), compress.RdByte(r), compress.RdByte(r)
    three := compress.RdBytes(r, 3)
    println compress.BufLen(three), compress.RdU32(r), compress.RdLeft(r), r.bad
    _ := compress.RdByte(r)
    println r.bad
    mut r2 := compress.NewByteReader(c.data, 2)
    println compress.RdByte(r2)
    compress.BufReset(b)
    println compress.BufLen(b)
    compress.BufFree(b)
    compress.BufFree(c)
    compress.BufFree(other)
end

Output9 72 SGkhISEAAAAK true hello 9 104 105 3 10 0 false true 104 0

`ByteReader`

struct ByteReader

A sequential reader of bytes over one piece of memory.

Name	Type	Description
`data`	`void*`	The address of the data.
`len`	`int = 0`	The length of the data.
`pos`	`int = 0`	The current position.
`bad`	`bool = false`	A read went past the end of the data.

The example for this item is shown with the ones above: compress-Buffer.salam

`BitWriter`

struct BitWriter

A writer of bits; it fills each byte from the least significant bit.

Name	Type	Description
`buf`	`ByteBuf`	The bytes written.
`acc`	`int = 0`	The bits waiting.
`nbits`	`int = 0`	The number of bits waiting.

compress-Bits.salam

import compress

func main:
    mut w := compress.NewBitWriter()
    compress.BitWriteBit(w, 1)
    compress.BitWriteBits(w, 5, 3)
    compress.BitWriteBits(w, 255, 8)
    compress.BitFlush(w)
    println compress.BitWriterLen(w)
    mut r := compress.BitReaderFromBuf(w.buf)
    println compress.BitReadBit(r), compress.BitReadBits(r, 3), compress.BitReadBits(r, 8)
    mut r2 := compress.NewBitReader(w.buf.data, 1)
    println compress.BitReadBits(r2, 4)
    compress.BitWriterFree(w)
end

Output2 1 5 255 11

`BitReader`

struct BitReader

A reader of bits in the same order.

Name	Type	Description
`data`	`void*`	The data.
`len`	`int = 0`	The length of the data.
`pos`	`int = 0`	The current byte position.
`acc`	`int = 0`	The bits read.
`nbits`	`int = 0`	The number of bits ready.
`bad`	`bool = false`	A read went past the end of the data.

The example for this item is shown with the ones above: compress-Bits.salam

Constants and variables

Method numbers `Method…`

The same Method enum cases as plain numbers, for Compress and Decompress.

Name	Value
`MethodNone`	`0`
`MethodRLE`	`1`
`MethodHuffman`	`2`
`MethodLZ77`	`3`
`MethodLZW`	`4`
`MethodDeflate`	`5`
`MethodBWT`	`6`

The example for this item is shown with the ones above: compress-Methods.salam

Functions

`LZWCompress`

func LZWCompress(p: void*, n: int): ByteBuf

LZW compression, with a dictionary built as it goes.

The example for this item is shown with the ones above: compress-Methods.salam

`LZWDecompress`

func LZWDecompress(p: void*, n: int): ByteBuf

Decompresses LZW data.

The example for this item is shown with the ones above: compress-Methods.salam

`RLECompress`

func RLECompress(p: void*, n: int): ByteBuf

Run length encoding: shortens runs of the same byte; for data that repeats a lot.

The example for this item is shown with the ones above: compress-Methods.salam

`RLEDecompress`

func RLEDecompress(p: void*, n: int): ByteBuf

Decompresses RLE data.

The example for this item is shown with the ones above: compress-Methods.salam

`GzipCompress`

func GzipCompress(p: void*, n: int): ByteBuf

Compresses the data into the gzip format, the one in .gz files.

compress-Gzip.salam

import compress

func main:
    text := "hello gzip! hello gzip! hello gzip!"
    g := compress.GzipCompressStr(text)
    println compress.BufGet(g, 0), compress.BufGet(g, 1)
    mut ok := false
    b := compress.GzipDecompressBuf(g, ok)
    println ok, compress.BufToStrUnsafe(b) == text
    b2 := compress.BufFromStr(text)
    g2 := compress.GzipCompressBuf(b2)
    g3 := compress.GzipCompress(b2.data, b2.len)
    println compress.BufEquals(g2, g3)
    _ := compress.GzipDecompress(b2.data, b2.len, ok)
    println ok
    d := compress.DeflateCompress(b2.data, b2.len)
    println compress.BufEquals(compress.DeflateDecompress(d.data, d.len), b2)
    raw := compress.RawDeflate(b2.data, b2.len)
    back := compress.RawInflate(raw.data, raw.len, b2.len, ok)
    println ok, compress.BufEquals(back, b2)
end

Output31 139 true true true false true true true

`GzipDecompress`

func GzipDecompress(p: void*, n: int, ok &: bool): ByteBuf

Decompresses gzip data; ok becomes false when the data is not gzip. The checksum inside the file is not checked.

The example for this item is shown with the ones above: compress-Gzip.salam

`GzipCompressBuf`

func GzipCompressBuf(b: ByteBuf): ByteBuf

Gzips a buffer.

The example for this item is shown with the ones above: compress-Gzip.salam

`GzipCompressStr`

func GzipCompressStr(s: str): ByteBuf

Gzips a string.

The example for this item is shown with the ones above: compress-Gzip.salam

`GzipDecompressBuf`

func GzipDecompressBuf(b: ByteBuf, ok &: bool): ByteBuf

Decompresses a gzip buffer.

The example for this item is shown with the ones above: compress-Gzip.salam

`RawInflate`

func RawInflate(p: void*, n: int, expected_size: int, ok &: bool): ByteBuf

Decompresses raw DEFLATE; expected_size is the rough size of the output.

The example for this item is shown with the ones above: compress-Gzip.salam

`NewBitWriter`

func NewBitWriter(): BitWriter

A new bit writer.

The example for this item is shown with the ones above: compress-Bits.salam

`BitWriteBit`

func BitWriteBit(w &: BitWriter, bit: int)

Writes one bit.

The example for this item is shown with the ones above: compress-Bits.salam

`BitWriteBits`

func BitWriteBits(w &: BitWriter, value: int, count: int)

Writes the low count bits of value.

The example for this item is shown with the ones above: compress-Bits.salam

`BitFlush`

func BitFlush(w &: BitWriter)

Sends the remaining bits to the last byte, padded with zeros.

The example for this item is shown with the ones above: compress-Bits.salam

`BitWriterLen`

func BitWriterLen(w &: BitWriter): int

The number of bytes written.

The example for this item is shown with the ones above: compress-Bits.salam

`BitWriterFree`

func BitWriterFree(w &: BitWriter)

Frees the memory.

The example for this item is shown with the ones above: compress-Bits.salam

`NewBitReader`

func NewBitReader(p: void*, n: int): BitReader

A bit reader over memory.

The example for this item is shown with the ones above: compress-Bits.salam

`BitReaderFromBuf`

func BitReaderFromBuf(b: ByteBuf): BitReader

A bit reader over a buffer.

The example for this item is shown with the ones above: compress-Bits.salam

`BitReadBit`

func BitReadBit(r &: BitReader): int

Reads one bit.

The example for this item is shown with the ones above: compress-Bits.salam

`BitReadBits`

func BitReadBits(r &: BitReader, count: int): int

Reads count bits.

The example for this item is shown with the ones above: compress-Bits.salam

`CRC32`

func CRC32(p: void*, n: int): u32

The CRC-32 checksum, the one in ZIP and gzip, for checking that data is intact.

compress-Checksum.salam

import compress

func main:
    println compress.CRC32Str("123456789"), compress.Adler32Str("Wikipedia")
    b := compress.BufFromStr("123456789")
    println compress.CRC32(b.data, b.len) == compress.CRC32Buf(b)
    println compress.Adler32(b.data, b.len) == compress.Adler32Buf(b)
    println compress.CRC32Str("hello")
end

Output3421780262 300286872 true true 907060870

`CRC32Str`

func CRC32Str(s: str): u32

The CRC-32 of a string.

The example for this item is shown with the ones above: compress-Checksum.salam

`CRC32Buf`

func CRC32Buf(b: ByteBuf): u32

The CRC-32 of a buffer.

The example for this item is shown with the ones above: compress-Checksum.salam

`Adler32`

func Adler32(p: void*, n: int): u32

The Adler-32 checksum, the one in zlib; faster than CRC-32 but a little weaker.

The example for this item is shown with the ones above: compress-Checksum.salam

`Adler32Str`

func Adler32Str(s: str): u32

The Adler-32 of a string.

The example for this item is shown with the ones above: compress-Checksum.salam

`Adler32Buf`

func Adler32Buf(b: ByteBuf): u32

The Adler-32 of a buffer.

The example for this item is shown with the ones above: compress-Checksum.salam

`NewByteBuf`

func NewByteBuf(): ByteBuf

An empty buffer.

The example for this item is shown with the ones above: compress-Buffer.salam

`NewByteBufCap`

func NewByteBufCap(capacity: int): ByteBuf

An empty buffer with an initial capacity.

The example for this item is shown with the ones above: compress-Buffer.salam

`BufPush`

func BufPush(b &: ByteBuf, v: int)

Adds one byte.

The example for this item is shown with the ones above: compress-Buffer.salam

`BufPushBytes`

func BufPushBytes(b &: ByteBuf, p: void*, n: int)

Adds n bytes from memory.

The example for this item is shown with the ones above: compress-Buffer.salam

`BufPushBuf`

func BufPushBuf(b &: ByteBuf, src: ByteBuf)

Adds the bytes of another buffer.

The example for this item is shown with the ones above: compress-Buffer.salam

`BufPushU32`

func BufPushU32(b &: ByteBuf, v: int)

Adds a 32 bit integer as 4 little-endian bytes.

The example for this item is shown with the ones above: compress-Buffer.salam

`BufGet`

func BufGet(b: ByteBuf, i: int): int

Byte number i.

The example for this item is shown with the ones above: compress-Buffer.salam

`BufSet`

func BufSet(b &: ByteBuf, i: int, v: int)

Sets byte number i.

The example for this item is shown with the ones above: compress-Buffer.salam

`BufLen`

func BufLen(b: ByteBuf): int

The number of bytes.

The example for this item is shown with the ones above: compress-Buffer.salam

`BufFree`

func BufFree(b &: ByteBuf)

Frees the memory of the buffer.

The example for this item is shown with the ones above: compress-Buffer.salam

`BufReset`

func BufReset(b &: ByteBuf)

Empties the buffer and keeps the memory.

The example for this item is shown with the ones above: compress-Buffer.salam

`BufClone`

func BufClone(b: ByteBuf): ByteBuf

An independent copy of the buffer.

The example for this item is shown with the ones above: compress-Buffer.salam

`BufEquals`

func BufEquals(a: ByteBuf, b: ByteBuf): bool

True when two buffers hold the same bytes.

The example for this item is shown with the ones above: compress-Buffer.salam

`BufFromStr`

func BufFromStr(s: str): ByteBuf

Puts the bytes of a string into a new buffer.

The example for this item is shown with the ones above: compress-Buffer.salam

`BufToStrUnsafe`

func BufToStrUnsafe(b: ByteBuf): str

Takes the buffer to be a string; when the buffer holds a zero byte, the string ends right there.

The example for this item is shown with the ones above: compress-Buffer.salam

`BufToBase64`

func BufToBase64(b: ByteBuf): str

Turns the buffer into base64, for showing binary data.

The example for this item is shown with the ones above: compress-Buffer.salam

`NewByteReader`

func NewByteReader(p: void*, n: int): ByteReader

A reader over n bytes of memory.

The example for this item is shown with the ones above: compress-Buffer.salam

`ReaderFromBuf`

func ReaderFromBuf(b: ByteBuf): ByteReader

A reader over the bytes of a buffer.

The example for this item is shown with the ones above: compress-Buffer.salam

`RdLeft`

func RdLeft(r: ByteReader): int

The number of bytes not yet read.

The example for this item is shown with the ones above: compress-Buffer.salam

`RdByte`

func RdByte(r &: ByteReader): int

Reads one byte; past the end bad becomes true.

The example for this item is shown with the ones above: compress-Buffer.salam

`RdU32`

func RdU32(r &: ByteReader): int

Reads a 4 byte little-endian integer.

The example for this item is shown with the ones above: compress-Buffer.salam

`RdBytes`

func RdBytes(r &: ByteReader, n: int): ByteBuf

Reads n bytes into a new buffer.

The example for this item is shown with the ones above: compress-Buffer.salam

`DeflateCompress`

func DeflateCompress(p: void*, n: int): ByteBuf

LZ77 and Huffman in a format of Salam's own. This is not standard zlib DEFLATE; for the standard format use RawDeflate or gzip.

The example for this item is shown with the ones above: compress-Gzip.salam

`DeflateDecompress`

func DeflateDecompress(p: void*, n: int): ByteBuf

Decompresses the output of DeflateCompress.

The example for this item is shown with the ones above: compress-Gzip.salam

`MTFEncode`

func MTFEncode(inbuf: ByteBuf): ByteBuf

Move to front encoding: every byte is replaced by its place in a list of the recent bytes.

The example for this item is shown with the ones above: compress-Methods.salam

`MTFDecode`

func MTFDecode(inbuf: ByteBuf): ByteBuf

Undoes move to front.

The example for this item is shown with the ones above: compress-Methods.salam

`BWTTransform`

func BWTTransform(p: void*, n: int, primary_out &: int): ByteBuf

The Burrows Wheeler transform: moves the bytes so that similar bytes end up next to each other; the index of the original row comes back in primary_out.

The example for this item is shown with the ones above: compress-Methods.salam

`BWTInverse`

func BWTInverse(p: void*, n: int, primary: int): ByteBuf

Undoes the Burrows Wheeler transform, given the index of the original row.

The example for this item is shown with the ones above: compress-Methods.salam

`BWTCompress`

func BWTCompress(p: void*, n: int): ByteBuf

Burrows Wheeler, then move to front, then compression.

The example for this item is shown with the ones above: compress-Methods.salam

`BWTDecompress`

func BWTDecompress(p: void*, n: int): ByteBuf

Decompresses data compressed with Burrows Wheeler.

The example for this item is shown with the ones above: compress-Methods.salam

`RawDeflate`

func RawDeflate(p: void*, n: int): ByteBuf

Standard DEFLATE (RFC 1951) with no header; what sits inside ZIP and gzip.

The example for this item is shown with the ones above: compress-Gzip.salam

`Compress`

func Compress(method: int, p: void*, n: int): ByteBuf

Compresses the data with the given method. The output does not carry the method number, so you have to know it to decompress.

The example for this item is shown with the ones above: compress-Methods.salam

`Decompress`

func Decompress(method: int, p: void*, n: int): ByteBuf

Decompresses data that was compressed with the given method.

The example for this item is shown with the ones above: compress-Methods.salam

`CompressStr`

func CompressStr(method: int, s: str): ByteBuf

Compresses a string.

The example for this item is shown with the ones above: compress-Methods.salam

`CompressBuf`

func CompressBuf(method: int, b: ByteBuf): ByteBuf

Compresses a buffer.

The example for this item is shown with the ones above: compress-Methods.salam

`DecompressBuf`

func DecompressBuf(method: int, b: ByteBuf): ByteBuf

Decompresses a compressed buffer.

The example for this item is shown with the ones above: compress-Methods.salam

`CompressBest`

func CompressBest(p: void*, n: int, method_out &: int): ByteBuf

Tries every method, returns the shortest output and puts its method in method_out.

The example for this item is shown with the ones above: compress-Methods.salam

`Ratio`

func Ratio(compressed_len: int, original_len: int): f64

The ratio of the compressed size to the original; under 1 means it got smaller.

The example for this item is shown with the ones above: compress-Methods.salam

`LZ77Compress`

func LZ77Compress(p: void*, n: int): ByteBuf

LZ77 compression: repeated pieces are replaced by a reference to where they were before.

The example for this item is shown with the ones above: compress-Methods.salam

`LZ77Decompress`

func LZ77Decompress(p: void*, n: int): ByteBuf

Decompresses LZ77 data.

The example for this item is shown with the ones above: compress-Methods.salam

`HuffmanCompress`

func HuffmanCompress(p: void*, n: int): ByteBuf

Huffman coding: the more frequent bytes get shorter codes. The code table is stored with the data, so for small data the output gets bigger.

The example for this item is shown with the ones above: compress-Methods.salam

`HuffmanDecompress`

func HuffmanDecompress(p: void*, n: int): ByteBuf

Decompresses Huffman data.

The example for this item is shown with the ones above: compress-Methods.salam

compress

Types

Method

ByteBuf

ByteReader

BitWriter

BitReader

Constants and variables

Method numbers Method…

Functions

LZWCompress

LZWDecompress

RLECompress

RLEDecompress

GzipCompress

GzipDecompress

GzipCompressBuf

GzipCompressStr

GzipDecompressBuf

RawInflate

NewBitWriter

BitWriteBit

BitWriteBits

BitFlush

BitWriterLen

BitWriterFree

NewBitReader

BitReaderFromBuf

BitReadBit

BitReadBits

CRC32

CRC32Str

CRC32Buf

Adler32

Adler32Str

Adler32Buf

NewByteBuf

NewByteBufCap

BufPush

BufPushBytes

BufPushBuf

BufPushU32

BufGet

BufSet

BufLen

BufFree

BufReset

BufClone

BufEquals

BufFromStr

BufToStrUnsafe

BufToBase64

NewByteReader

ReaderFromBuf

RdLeft

RdByte

RdU32

RdBytes

DeflateCompress

DeflateDecompress

MTFEncode

MTFDecode

BWTTransform

BWTInverse

BWTCompress

BWTDecompress

RawDeflate

Compress

Decompress

CompressStr

CompressBuf

DecompressBuf

CompressBest

Ratio

LZ77Compress

LZ77Decompress

HuffmanCompress

HuffmanDecompress

`Method`

`ByteBuf`

`ByteReader`

`BitWriter`

`BitReader`

Method numbers `Method…`

`LZWCompress`

`LZWDecompress`

`RLECompress`

`RLEDecompress`

`GzipCompress`

`GzipDecompress`

`GzipCompressBuf`

`GzipCompressStr`

`GzipDecompressBuf`

`RawInflate`

`NewBitWriter`

`BitWriteBit`

`BitWriteBits`

`BitFlush`

`BitWriterLen`

`BitWriterFree`

`NewBitReader`

`BitReaderFromBuf`

`BitReadBit`

`BitReadBits`

`CRC32`

`CRC32Str`

`CRC32Buf`

`Adler32`

`Adler32Str`

`Adler32Buf`

`NewByteBuf`

`NewByteBufCap`

`BufPush`

`BufPushBytes`

`BufPushBuf`

`BufPushU32`

`BufGet`

`BufSet`

`BufLen`

`BufFree`

`BufReset`

`BufClone`

`BufEquals`

`BufFromStr`

`BufToStrUnsafe`

`BufToBase64`

`NewByteReader`

`ReaderFromBuf`

`RdLeft`

`RdByte`

`RdU32`

`RdBytes`

`DeflateCompress`

`DeflateDecompress`

`MTFEncode`

`MTFDecode`

`BWTTransform`

`BWTInverse`

`BWTCompress`

`BWTDecompress`

`RawDeflate`

`Compress`

`Decompress`

`CompressStr`

`CompressBuf`

`DecompressBuf`

`CompressBest`

`Ratio`

`LZ77Compress`

`LZ77Decompress`

`HuffmanCompress`

`HuffmanDecompress`