Pure Lua LZ4 library

i’ve spent the past week with this lol, so many weird edgecases

lz4-lua

A pure Lua implementation of the LZ4 compression algorithm

LZ4 is a compression algorithm that uses dictionary-based matching to compress data. It compressess data into a block format.

This library attempts to work with the block format, and compress to it using a different algorithm (probably) to the C++ library. That being said, it should still work with the C++ tools and decompress C++ encoded data.

Source Code

Documentation

To compress a stream:

lz4.compress(data)

To decompress a stream:

lz4.decompress(data)

Notes

This library could definitely be more well optimised. Feel free to contribute optimisations on the GitHub, for whatever reason, data compressed with this may not work with the native decompressor

18 Likes

i might compare this with LZW, ill keep updated on how this goes

Wouldn’t it be better to compare LZ4 and LZW in their native languages and not use a port?. lz4’s original source code is hosted here

i want to compare your port with that. i will do it tommorow

I can no longer find this on GitHub.

2 Likes

Rehosted source code since there seems to be demand for this all of a sudden

1 Like

Hey! I’m just letting you know I’m rewriting this to use the new buffer datatype. Pretty sure I’ve also figured out why the compressor doesn’t work with the native decompressor (i love sliding windows!).

You can message me for access to the GitHub repository if you want to help :3

2 Likes

Hello! Great library, but sadly it seemed to choke on compression with Shakespeare’s Twelvth Night that I used to test out my own compression algorithm (rbx-deflate).

ReplicatedStorage.LZ4:203: invalid argument #2 to ‘pack’ (unsigned overflow)

As someone who rewrote @1waffle1’s text compression to work with ascii values 0-255 (emoji support), I’ve been looking for a more faster way to compress data since compressing about 4 mb of code to fit it into DataStores takes a good second for the server to compute, let alone with 50+ players in one server. LZ4 apparently seems to be a faster algorithm than LZW, which is how I found your post.

I’m hoping that this project goes somewhere!

2 Likes

Not sure if it’s well-known:

LZ4 is used for compressing rbxl files.

1 Like

Have you tried turning it off and back on again?

I crave for the day someone uses Actors to parallelize these compressions with a chunking method to separate the work, I don’t know if Roblox is up for this task yet though

Definitely never happening. Actors are only useful for doing engine stuff, since they have to have so much thread locking and VM transfer overhead.

I honestly believe Parallel Luau is a waste of engineering time because the only feasible performance improvement it can provide is bulk engine calls, which should already be built-in to the API.

You cant parallelise LZ4 anyway because the decompression algorithm references previously decompressed data.

1 Like

Hey! Thanks for this code project!

I changed the decoder over to use buffers for a project of ours, thought I should share it here.
We saw an improvement of about 10,000x, going from 115 seconds to 15ms

function lz4.decompress(input: buffer, offset: number): buffer
	offset = offset or 0

	local compressedLen   = buffer.readi32(input, offset + 0)
	local decompressedLen = buffer.readi32(input, offset + 4)
	-- bytes 8 - 11 are not used in this implementation

	if compressedLen == 0 then
		local output = buffer.create(decompressedLen)
		buffer.copy(output, 0, input, offset + 12, decompressedLen)
		return output
	end

	return lz4.decompressHeaderless(input, offset + 12, decompressedLen)
end

function lz4.decompressHeaderless(input: buffer, offset: number, decompressedLen: number): buffer
	local output = buffer.create(decompressedLen)

	local iHead = offset
	local oHead = 0

	while true do
		local token = buffer.readu8(input, iHead)
		local litLen = token // 0b10000
		local matLen = token  % 0b10000
		iHead += 1

		if litLen == 0b1111 then
			repeat -- this tally system is actually not a smart way to encode length in general.
				local extraLen = buffer.readu8(input, iHead)
				litLen += extraLen
				iHead += 1
			until extraLen ~= 0b11111111
		end

		buffer.copy(output, oHead, input, iHead, litLen)
		iHead += litLen
		oHead += litLen

		-- this is smart, it helps recuperate some of the losses at the beginning from storing the length
		if oHead == decompressedLen then break end

		local readback = buffer.readu16(input, iHead)
		local copyStart = oHead - readback
		iHead += 2

		if matLen == 0b1111 then
			repeat
				local extraLen = buffer.readu8(input, iHead)
				matLen += extraLen
				iHead += 1
			until extraLen ~= 0b11111111
		end
		matLen += 4

		-- unfortunately, buffer.copy(output, oHead, output, copyStart, matLen) does not work
		-- also why not do this for the literal read too?
		while matLen > oHead - copyStart do
			local maxLen = oHead - copyStart
			buffer.copy(output, oHead, output, copyStart, maxLen)
			matLen -= maxLen
			oHead += maxLen
		end

		buffer.copy(output, oHead, output, copyStart, matLen)
		oHead += matLen

		if oHead == decompressedLen then break end
	end

	return output
end

I see that you were working on an implementation using the buffer object, could I see that link?

Also if you wanted to take a compression ratio hit for faster performance, you could totally chunk it up into several smaller pieces. With very large pieces of data, the compression ratio hit would probably be very small.

4 Likes

Seeing this, I’m excited to see if a possible pure-Lua LZ4 encoder implementation may be developed from you and @metatablecat soon!

Message me. LGTM! I still haven’t started on this, but seeing this getting a spike again might motivate me lol.

2 Likes