The squash unit tests were failing on Windows. It looks like I made a cut-and-paste error in the Python script I used to create the labels for the switch statemet, so eos was swapped with one of the nop labels.

So far LZFSE seems to be quite nice as an alternative to zlib. But I hope that I'm not the only one having troubles using a proprietary copyrighted algorithm which might deny me to use this software piece in future.

My questions so far are:

1. Will there be an RFC for LZFSE or any intention to standardize this algorithm to the public so that cross-platform adaption is possible?
2. Will LZFSE be distributed via another License (like Apache, BSD or MIT)?
3. What kind of patents by Apple are involved in the usage and adaption of LZFSE?

Thanks in advice.

Please review this carefully, I'm not particularly confident of the change.

I'd really like to be able to expose a LZVN in Squash, but the requirement of the input buffer being at least 8 bytes is a problem. Output isn't a big deal since I can just compress to a temporary 8-byte buffer, then copy it over to the "real" output buffer if there is enough room.

After poking around the code a bit, it occurs to me that it should be possible to just skip the compression part and write the entire buffer as a literal, just like you already do for the trailing few bytes. This patch, I think, does that. I'm not very familiar with the code base, or the compression format, though, so please be careful applying this.

I've modified the Squash LZFSE plugin to also expose LZVN, and with this change it does pass all Squash's unit tests, which is about all I can do. Here is the diff for the changes to Squash in case you want to play with it:

diff --git a/plugins/lzfse/squash-lzfse.c b/plugins/lzfse/squash-lzfse.c
index f72324f..39514e5 100644
--- a/plugins/lzfse/squash-lzfse.c
+++ b/plugins/lzfse/squash-lzfse.c
@@ -34,6 +34,8 @@

 #include "lzfse/src/lzfse.h"
 #include "lzfse/src/lzfse_internal.h"
+#include "lzfse/src/lzvn_encode_base.h"
+#include "lzfse/src/lzvn_decode_base.h"

 SQUASH_PLUGIN_EXPORT
 SquashStatus squash_plugin_init_codec (SquashCodec* codec, SquashCodecImpl* impl);
@@ -101,14 +103,101 @@ squash_lzfse_compress_buffer (SquashCodec* codec,
   return SQUASH_OK;
 }

+static size_t
+squash_lzvn_get_max_compressed_size (SquashCodec* codec, size_t uncompressed_size) {
+  return (uncompressed_size) + (uncompressed_size / 80) + 16;
+}
+
+static SquashStatus
+squash_lzvn_decompress_buffer (SquashCodec* codec,
+                               size_t* decompressed_size,
+                               uint8_t decompressed[SQUASH_ARRAY_PARAM(*decompressed_size)],
+                               size_t compressed_size,
+                               const uint8_t compressed[SQUASH_ARRAY_PARAM(compressed_size)],
+                               SquashOptions* options) {
+  lzvn_decoder_state decoder = { 0, };
+
+  decoder.src = compressed;
+  decoder.src_end = compressed + compressed_size;
+
+  decoder.dst = decompressed;
+  decoder.dst_begin = decompressed;
+  decoder.dst_end = decompressed + *decompressed_size;
+  decoder.dst_current = decompressed;
+
+  lzvn_decode (&decoder);
+
+  const size_t bytes_read = decoder.src - compressed;
+  const size_t bytes_written = decoder.dst - decoder.dst_begin;
+
+  if (SQUASH_UNLIKELY(bytes_read != compressed_size)) {
+    if (bytes_written == *decompressed_size)
+      return SQUASH_BUFFER_FULL;
+    else
+      return SQUASH_FAILED;
+  }
+
+  *decompressed_size = bytes_written;
+
+  return SQUASH_OK;
+}
+
+static SquashStatus
+squash_lzvn_compress_buffer (SquashCodec* codec,
+                             size_t* compressed_size,
+                             uint8_t compressed[SQUASH_ARRAY_PARAM(*compressed_size)],
+                             size_t uncompressed_size,
+                             const uint8_t uncompressed[SQUASH_ARRAY_PARAM(uncompressed_size)],
+                             SquashOptions* options) {
+  uint8_t outbuf[LZVN_ENCODE_MIN_DST_SIZE];
+  uint8_t* dest;
+  size_t dest_l;
+
+  if (SQUASH_UNLIKELY(*compressed_size < sizeof(outbuf))) {
+    dest = outbuf;
+    dest_l = sizeof(outbuf);
+  } else {
+    dest = compressed;
+    dest_l = *compressed_size;
+  }
+
+  void* workmem = squash_malloc (LZVN_ENCODE_WORK_SIZE);
+  if (SQUASH_UNLIKELY(workmem == NULL))
+    return squash_error (SQUASH_MEMORY);
+
+  dest_l =
+    lzvn_encode_buffer(dest, dest_l,
+                       uncompressed, uncompressed_size,
+                       workmem);
+
+  squash_free (workmem);
+
+  if (SQUASH_UNLIKELY(dest_l == 0))
+    return squash_error (SQUASH_BUFFER_FULL);
+
+  if (SQUASH_UNLIKELY(dest == outbuf)) {
+    if (*compressed_size < dest_l)
+      return squash_error (SQUASH_BUFFER_FULL);
+
+    memcpy (compressed, dest, dest_l);
+  }
+
+  *compressed_size = dest_l;
+  return SQUASH_OK;
+}
+
 SquashStatus
 squash_plugin_init_codec (SquashCodec* codec, SquashCodecImpl* impl) {
   const char* name = squash_codec_get_name (codec);

-  if (SQUASH_LIKELY(strcmp ("lzfse", name) == 0)) {
+  if (strcmp ("lzfse", name) == 0) {
     impl->get_max_compressed_size = squash_lzfse_get_max_compressed_size;
     impl->decompress_buffer = squash_lzfse_decompress_buffer;
     impl->compress_buffer = squash_lzfse_compress_buffer;
+  } else if (strcmp ("lzvn", name) == 0) {
+    impl->get_max_compressed_size = squash_lzvn_get_max_compressed_size;
+    impl->decompress_buffer = squash_lzvn_decompress_buffer;
+    impl->compress_buffer = squash_lzvn_compress_buffer;
   } else {
     return SQUASH_UNABLE_TO_LOAD;
   }
diff --git a/plugins/lzfse/squash.ini b/plugins/lzfse/squash.ini
index 11f1324..e3fcf60 100644
--- a/plugins/lzfse/squash.ini
+++ b/plugins/lzfse/squash.ini
@@ -1,3 +1,4 @@
 license=BSD3

 [lzfse]
+[lzvn]

LZFSE currently fails to build with MSVC. See https://ci.appveyor.com/project/quixdb/squash/build/470/job/1fvyqd3lrkrpem6t#L1388 for a build log.

@jibsen kindly looked into this, and it seems the major issue is reliance on a gcc extension in lzvn_decode_base.c.

Hi, I noticed the project doesn't have proper releases and that makes hard to build package for third party distribution.

In particular, I was adding the package for this library to conda-forge (see https://github.com/conda-forge/staged-recipes/pull/2596) and having versions somewhat required. It would be posible to have tags (and optionally releases) that we can refer to?

CC @jakirkham

As discussed in #15, rebased on master. Still wondering about the answers to the questions I asked there, but this should at least be a good starting point.

FWIW, I'm willing to help with maintenance on this, just ping me if you need something.

One potential optimization is to require that memory passed to the encode and decode functions already be zeroed, which would let you save the memset call. It can be much faster to call calloc than malloc + memset. For people doing lots of small operations without reusing memory this could result in a significant speedup (I've seen big boosts in other codec's performance by doing this).

Hi. Fix for the above issue. I hope the code and comments are reasonably clear.

Cause. The main decode loop cannot differentiate between an invalid decode input and a destination buffer that is too small. When it encounters an invalid input it will exponentially malloc until it can malloc no more, at which point it fails with the dreaded malloc: Cannot allocate memory error.

Fix. We fast fail zero-length inputs, which are always invalid. This obliviates the allocation of zero destination buffers. We can now interpret a zero lzfse_decode_buffer return value as a decode failure. The API docs are a bit vague in regards to invalid inputs: but as we can see here, lzfse_decode_buffer will return a zero value in the case of failure.

Hi, I've compiled the most recent lzfse library using Xcode 11.7 and ran it with UB sanitizer enabled. It flags these two warnings when I ran it against my test data:

file lzfse_decode_base.c lines 240-241: for (size_t i = 0; i < M; i++) dst[i] = dst[i - D];

UBsan flags line 241 as "Thread 1: Pointer overflow" "Addition of unsigned offset to 0x000106a85801 overflowed to 0x000106a85800"

variables: D = 1 M = 1023 i = 0

The actual problem is that this code is trying to copy bytes with overlapping buffers and it ends up performing the copy incorrectly.

In this specific case, it will first copy dst[-1] to dst[0] and then on the next loop iteration, it will copy dst[0] to dst[1] but this will be the same value as dst[-1] which is almost certainly not what the code's author intended because the comment above this code states // ..."a more // careful path that applies a permutation to account for the // possible overlap between source and destination if the distance // is small". which is referring to this loop.

I believe the code should be performing the equivalent of

memmove(dst, dst - D, M);

which is what the fast code path above it does (the fast code path assumes that the buffers do not overlap however so it performs its work using a memcpy-like loop).

I've patched my working copy of the source file to use memmove and this stopped the warning from being generated.

There is another UBsan warning in the same file on line 280-281:

    for (size_t i = 0; i < M; i++)
      dst[i] = dst[i - D];

UBsan flags line 281 as "Thread 1: Pointer overflow" "Addition of unsigned offset to 0x000106b790f4 overflowed to 0x000106b3f0f4"

with variables:

M = 1801 D = 237568 i = 0

which clearly is a non-overlapping copy so the only issue here is the way the code appears to access invalid array elements.

I've patched my working copy of the source file to use memcpy(dst, dst - D, M) and this stopped the warning from being generated.

I will also note that lines 294-295 are another loop similar to these 2 and may also generate a similar warning (but my test data did not cause this code to execute).

Cheers.

I would appreciate some sort of clarification on LZFSE's patent situation. At minimum, if Apple believes it has any patents relevant to LZFSE they should disclose them, and if Apple doesn't have any relevant patents it should provide a statement to that effect (Google recently did something similar for Brotli).

Ideally, though, I would like to see some sort of patent license grant for any patents it owns or acquires which read on LZFSE, at least for the purpose of using LZFSE.

How can I build this as a dylib on macOS, rather than a .a (static library)?

I've tried the following with no success:

• passing -DBUILD_SHARED_LIBS=ON parameter to xcodebuild
• Explicitly specified "Dynamic Library" as a "Match-O Type": https://take.ms/4Tzj6

compile success over msys2(win10x64) encode all fine only issue is with decode :

decoding file of 14mb, RAM increase insanely like 5GB+ then output :

malloc: Not enough space

lzfse is available as a port in vcpkg, a C++ library manager that simplifies installation for lzfse and other project dependencies. Documenting the install process here will help users get started by providing a single set of commands to build lzfse, ready to be included in their projects.

We also test whether our library ports build in various configurations (dynamic, static) on various platforms (OSX, Linux, Windows: x86, x64) to keep a wide coverage for users.

I'm a maintainer for vcpkg, and here is what the port script looks like. We try to keep the library maintained as close as possible to the original library. :)

This commit enables CPack for CMake to generate target packages for each platform: RPMs and DEBs. It also generates packages for Mac and Windows platforms. The commit includes the regular packages and devel packages with the LZFSE header. To generate the package, you should pass -DBUILD_PACKAGING=ON and to generate devel packages you should also include -DINSTALL_HEADERS.

Signed-off-by: Julio Faracco [email protected]

Fixes a broken link to the Compression library documentation on developer.apple.com. Also fixes a remaining instance of "OS X" to "macOS". I didn't change the initial one since 10.11 was still correctly called OS X.