Refactor to allow for custom memory allocation functions

[GoogleCodeExporter]

For my program, all memory allocations must go though the memory manager, which 
means that any APIs we use need to be able to accept custom malloc/free 
function pointers, or alternatively allow for pre-allocated buffers to be 
passed in.

I've supplied a potential change to accomplish the second option, by exposing 
LZ4_init(), allowing you to replace a call to LZ4_compress or LZ4_compressHC 
with something like the following:

size_t sizeOfBuffer = LZ4_dataSize();
void* lz4Data = allocateSomeMemory( sizeOfBuffer );
LZ4_init( lz4Data, dataToBeCompressed );
int sizeOfCompressedData = LZ4_compress_continue( lz4Data, dataToBeCompressed , 
compressedData, sizeOfDataToBeCompressed );
freeSomeMemory( lz4Data );

The existing LZ4_init file is renamed to LZ4_initInternal, allowing it to keep 
it's inline'd nature.

There may need to be an additional function exposed, as the parameters that 
LZ4_compress() passes to LZ4_compress_generic() are different than those passed 
by LZ4_compress_continue().

Original issue reported on code.google.com by the.mep...@googlemail.com on 5 Dec 2013 at 4:52

Attachments:

• lz4.h.diff
• lz4.c.diff
• lz4hc.h.diff
• lz4hc.c.diff

[GoogleCodeExporter]

Original comment by yann.col...@gmail.com on 5 Dec 2013 at 6:56

• Added labels: Type-Enhancement
• Removed labels: Type-Defect

[GoogleCodeExporter]

It's an interesting enhancement.
I'll look into it.

Original comment by yann.col...@gmail.com on 5 Dec 2013 at 6:57

• Changed state: Accepted
• Added labels: Priority-Low
• Removed labels: Priority-minor

[GoogleCodeExporter]

Although it is not exclusive with your proposed solution,
one way to provide access to some custom memory allocation manager
could be inspired by these lines from xxHash :

//**************************************
// Includes & Memory related functions
//**************************************
#include "xxhash.h"
// Modify the local functions below should you wish to use some other memory 
related routines
// for malloc(), free()
#include <stdlib.h>
FORCE_INLINE void* XXH_malloc(size_t s) { return malloc(s); }
FORCE_INLINE void  XXH_free  (void* p)  { free(p); }
// for memcpy()
#include <string.h>
FORCE_INLINE void* XXH_memcpy(void* dest, const void* src, size_t size) { 
return memcpy(dest,src,size); }

Original comment by yann.col...@gmail.com on 5 Dec 2013 at 11:01

[GoogleCodeExporter]

I think a library that asks you to modify it when integrating it with your own 
codebase is a bad idea, as it generates more work when it comes time to upgrade 
the library to the latest version.

I think it'd be much better to have a simple "set allocator" function, which 
allows a program to pass in pointers for functions that match the signatures of 
malloc (or in your case, calloc) and free.

As an example, this is something I've done myself for realloc and free:

typedef void* (*ReallocatorFunc)( void* ptr, size_t size );
typedef void (*FreeFunc)( void* ptr );

void SetAllocator( ReallocatorFunc afunc, FreeFunc ffunc );

Original comment by the.mep...@googlemail.com on 6 Dec 2013 at 1:45

[GoogleCodeExporter]

I finally found some time to properly review your patch and integrate it.
It's a very good patch, with minimal effort and intrusion, yet creating a new 
important capability.
I kept the spirit of it, modifying minor details such as names and types, to 
respect the naming convention in place within LZ4 and xxHash.
The result of which is in attached file, for your review and comments.

I've used the same logic as your patch, which is to allow custom (external) 
allocator to provide the memory space to the stream functions.
However, reading your initial report, I'm not sure it was the correct intention.

Regards

Original comment by yann.col...@gmail.com on 26 Dec 2013 at 1:08

[GoogleCodeExporter]

I've eyeballed the changes and they look good (thanks for the complement by the 
way). I don't think I have anything to add, seems fine as it is.

I'm not sure what confusion you'd have from the original posting, unless it's 
my remarks about the different parameters from LZ4_compress() and 
LZ4_compress_continue().
 What I was talking about there is that I think (but I'm not certain) LZ4_compress_generic() uses larger header data ("withPrefix") to enable repeated calls to the function for the purpose of streaming the data gradually.
 But if you're doing everything in one go, there's no way to use "noPrefix" (since you're using the streaming functions, even though they all wrap the same function internally).
 I also assume the same is true of the HC functions with "noLimit" and "limitedOutput".

But I think that's another issue, if indeed it's an issue at all (and that I'm 
correct in my understanding of what's going on)

Original comment by the.mep...@googlemail.com on 26 Dec 2013 at 3:00

[GoogleCodeExporter]

Correct.

My understanding is :
you want to use "block mode compression" (noPrefix), but also want to allocate 
yourself the required memory.

The way you can do it is by using the "streaming" functions, and resetting the 
state between each block.

It works. It indeed does involve a bit more (useless) operations, but it is 
unlikely to be felt on performance, since it's just a few init checks.

So, on short term, the current issue seems solved.

However, from an API perspective, I'm not sure if the current situation is 
"clean" enough. After all, a user willing to compress in "block mode" is 
expecting to use LZ4_compress(), not the streaming variant 
LZ4_compress_continue().
I'll think a bit more about it...

Original comment by yann.col...@gmail.com on 26 Dec 2013 at 12:57

[GoogleCodeExporter]

I've been looking into it again, and here is my proposal.
To use the normal "block mode" LZ4, but using an custom allocation for the 
tables, the following API could be provided :

//*****************************
// Using an external allocation
//*****************************
int LZ4_sizeofState();
int LZ4_compress_withState               (void* state, const char* source, 
char* dest, int inputSize);
int LZ4_compress_limitedOutput_withState (void* state, const char* source, 
char* dest, int inputSize, int maxOutputSize);

Basically, the first function provides the size to allocate for state.
The compression functions accept the externally allocated table as argument.
They will check that it is aligned on 4-bytes boundaries, and memset it to 0. 
Then start the actual compression process, as usual.

Obviously, the same will have to be provided for LZ4 HC.

Original comment by yann.col...@gmail.com on 27 Dec 2013 at 11:04

[GoogleCodeExporter]

The following is an attempt at providing a cleaner interface for block-based 
compression using an externally allocated memory area.

It works almost the same as the streaming version, except there is no need to 
reset it.
Since each block is independent, the library is in charge of securing a clean 
start between each call.

The amount of memory reserved is slightly slower than the streaming version, 
and some checks are unnecessary, but it's unlikely to have any impact on 
performance.

This version also integrates these new functions into fuzzer test tool, to make 
sure they work appropriately.

Original comment by yann.col...@gmail.com on 28 Dec 2013 at 4:48

[GoogleCodeExporter]

This version also updates the fullbench test program, to observe potential 
performance differences between the standard version (stack allocation) and the 
new one (external allocation)

Original comment by yann.col...@gmail.com on 28 Dec 2013 at 5:37

Attachments:

• lz4-r110.tar.gz

[GoogleCodeExporter]

Implemented into r110

Original comment by yann.col...@gmail.com on 30 Dec 2013 at 5:22

[GoogleCodeExporter]

Implemented into r110

Original comment by yann.col...@gmail.com on 30 Dec 2013 at 5:22

• Changed state: Fixed