vurtun / lib Goto Github PK

Very nice set of tools, thank you 👍

Would be great if you could add more math tools!

Hi! When trying to compress a 4096x4096 RGBA (32bit per pixel) image I noticed it was quite slow (about 14 seconds on my old [email protected], 8GB RAM), compiled in release mode, optimized for fast.

Analysing the process with Visual Studio 2022 it seems to find a Hot Path in sdefl_fnd() and sdefl_uload32(), is it expected? Do you know if there could be any issue in that point?

I tested saving the same image data with stbi_write_png() and it takes about 4 seconds.

For comparison I also tested it with the QOI file format and it takes less than a second.

About the output compressed sizes (it could be related), I got:

 - rpng (sdefl) -> 5012KB
 - stbi ---------> 7392KB
 - qoi ----------> 8792KB

Maybe the issue is on my side when providing the scanlines for compression? The compression size is quite small, it makes sense it could take way longer to process...

Please, note that this is more an issue for discussion than an actual problem, it just call my attention and I decided to ask.

At the top of json.h, it states json.h - public domain, but the README states that the license is zlib. Is this a mistake?

When making calls to sdeflate() for a variety of in-memory buffers for compression-testing, one of my test buffers (~3MB) always triggers the assert() in sdefl_seq(). I can't find anything special about the data that is causing it, and it triggers consistently, regardless of compression level (0-8).

sdefl.h:537: sdefl_seq: Assertion `s->seq_cnt + 2 < SDEFL_SEQ_SIZ' failed.

What is this assert signaling? Obviously that the sequence buffer is about to be overrun, but what can be done to prevent this issue? Is there some parameter change or guard that can be added to detect and avoid this assert?

If I dump the state just prior to invoking the failing sdefl_seq() (@ line 601), these are the parameters in sdefl_compr():

*** ERROR ********************** 
          in_len:  3145728 
             lvl:  5 
               i:  242665 
         blk_end:  262144 
   SDEFL_BLK_MAX:  262144 
          litlen:  0 
       max_chain:  64 
 SDEFL_MIN_MATCH:  4 
 SDEFL_MAX_MATCH:  258 
       max_match:  258 
      nice_match:  48 
             run:  1 
             inc:  1 
           m.len:  4 
           m.off:  18301 
      s->seq_cnt:  65535 
   SDEFL_SEQ_SIZ:  65537 
********************************

compiled https://github.com/vurtun/lib/blob/master/tests/defl_test.c with latest version of https://github.com/vurtun/lib/blob/master/sdefl.h and https://github.com/vurtun/lib/blob/master/sinfl.h and for the test i passed a file that contain some 250kb of text as argument and it failed with error error: 183449:183450 !
running diff error.bin and my text file it shows that 1 character is missing from the decompressed file (error.bin) which is the last character.
and that because it didnt end with a newline, so after adding a newline to my text, it runs fine without errors... however adding two more newlines generate an error error: 183451:183452 ! and again error.bin is missing one newline character from the original text.
so it seems like some alignment issues with sinfl.h, and this issue happens only after this commit (tested with earlier version today and it was fine) 8252ab9

p.s. sorry for the long user name, i had to create github account report this issue, and i really hate it when developers dont put their email to contact them by mail. (beside that i never used github or any git based service or anything relaying on git variants)
p.p.s. i never used your defalte and inflate headers, actually i just discovered them after browsing your repository, and i know you are the creator of nuklear, which is something i use for quite some time.

When I compile with mingw64, I get:

In file included from mm_sched.h:515:0,
                 from ccg.c:2:
mm_sched.h: In function 'scheduler_add':
mm_sched.h:965:20: error: called object is not a function or function pointer
     range_to_run = SCHED_MAX(1, task->size / s->partitions_num);
                    ^

There's a name collision with SCHED_MAX, which is #define'd in pthread.h. Changing SCHED_MAX to anything else fixes this.

The documentation of scheduler_add method said that:

/* this function adds a task into the scheduler to execute and directly returns

• if the pipe is not full. Otherwise the task is run directly. Should only be
• called from main thread or within task handler.
  Input:
  • function to execute to process the task
  • userdata to call the execution function with
  • array size that will be divided over multible threads
    Output:
  • task handle used to wait for the task to finish or check if done. Needs
    to be persistent over the process of the task
    */

Is it not safe to call the scheduler_add method from the same thread where we call scheduler_start if this thread is different from the main thread?

"lastest version" is not a thing and should be corrected to "latest version".

Nice libraries & effort!

Recently I was suggested to add mm_json.h to nativejson-benchmark but I found that the root of JSON parsed by mm_json.h must be object type.

When parsing an invalid JSON ["Extra close"]] the parser seems go into dead-loop.

P.S. How to get number of key-value pairs at the root?

In this code:

      while (run-- != 0) {
        unsigned h = sdefl_hash32(&in[i]);

sdefl_hash32 triggers an access violation when there's less than 4 bytes left until the end of input, and the array is on a page boundary. This change fixes it but I'm not sure it's correct to just skip the hash:

        unsigned h = (i + 4 <= in_len) ? sdefl_hash32(&in[i]) : 0;

There's similar code in sdefl_fnd but that - as far as I can tell - is safe since it's only ever called with an offset that's far enough away from the end of input, as long as SDEFL_MIN_MATCH is at least 3.

Suggest to add a license to mmx, some license identifiers https://spdx.org/licenses/.

I tried to use sdefl as the built-in compression tool in my webserver to deflate the http messages . It seems that the compressed data is not compatible with the firefox built-in decompression method. The firefox continues to issue complaints of "The page you are trying to view cannot be shown because it uses an invalid or unsupported form of compression." I have tried a webkit based browser too, it keeps showing junk all the time.

I had used the earlier version of sdefl when it was only ~300 lines of code (before you moved the sdefl code to lib), it worked perfectly with my webserver. The sdefl is a great library, the reason for me to move to your new sdefl is to adapt to get higher compression ratio.

Have you made this incompatible change on purpose? If not, would you make it compatible with firefox built-in deflate method?

If sched.h is in a folder added to the include path on Linux and WSL e.g. by gcc -Iinclude then <pthread.h> will attempt to include this sched.h rather than the system one. This can be tested by just compiling the sched demo whilst including sched.h from a different folder. It may be sensible to rename sched.h, perhaps back to mm_sched.h, or scheduler.h, so it doesn't clash with system headers when -I is used.

Today I tried the latest update and I got a crash when trying to compress some data.

It happens when calling zdeflate(), I attach the crash line and call-stack for convenience. It happens for different images at different sizes, input data is valid and it worked with previous implementation. I had no problem with the updated sinfl.

Recently I found a very weird issue while generating PNG files with my rpng library that uses sdefl for deflate stream generation.

It worked very well with most image file generation but I found a very specific issue while generating a 512x512 image file. The generated file is somewhat corrupted and can not be opened. I tried with many other sizes and everything works fine.

I attach a .zip containing two files, one generated with stb_image_write and one generated with rpng: rfxgen_512x512.zip

Actually, some image viewers can decompress the rpng generated image but others can't. stbiw generated images work in all cases.

I tried to load rpng image with stb_image loader and I narrowed the issue to one specific line:

    if (z >= 286) return stbi__err("bad huffman code","Corrupt PNG"); // per DEFLATE, length codes 286 and 287 must not appear in compressed data

Located in function: static int stbi__parse_huffman_block(stbi__zbuf *a)

It seems the sdefl stream generates a z = 286 value under very specific circumstances.

I also reviewed the image data PNG filtering on rpng side but I couldn't find any issue in there...

EDIT 1: In case it could be useful, the stream to be compressed has a size of (512x512x4 + 512) = 1049088 bytes, it is the scanlines size (512 pixels width x 4 bytes/pixel) with the additional pre-filter byte (+1) multiplied by the image height (512).

EDIT 2: Note the problematic image can be read back correctly using rpng, despite being reported as corrupted by stbi and some image viewers.

EDIT 3: rpng image can read by Paint.NET but I noticed the last scanline of the image is completely blank, maybe the point were it fails decompression?

This computation:

  int a = 128 + (len * 110) / 100;

overflows when len is more than ~19 MB. I assume int a = 128 + len + len / 10; would work better here?

Found a typo in usage example.
Parser implementation is great.

/* query type */
int type0 = json_query_number(toks, num, "map.soldier[2]");

So lexer_read goes through the 'lexer_read_name' path when encountering a slash. This is likely incorrect, for the use case below; I was expecting punctuation instead. Check line 1315 of lexer.h.

For reference, I'm trying to parse code like this:
inline Vector2 operator/(float scalar) const;

{ "shader": { "name": "Voronoi", "category": "Patterns", "help": "Generates Voronoi cells", "includes": [ "/shaders/include/header.include", ], "stages": [ "VERT_SHADER", "FRAG_SHADER" ], "parameters": [ {"name": "scale", "value": 1.5000, "min": 0.1, "max": 5.0, "step": 0.2}, {"name": "color", "value": [0.7546, 0.500000, -0.012345, 1.0000]} ] } }

The value '-0.012345' will return a positive json_number instead of negative.

What is the best way to add N tasks to the scheduler?

Just adding them in a loop?

To reproduce, run gcc -fsanitize=address test.c && ./a.out on this file:

#define SDEFL_IMPLEMENTATION
#include "extern/sdefl.h"

int main()
{
        const unsigned char input[384] = {
        0x00, 0xb8, 0x00, 0x38, 0x00, 0xb8, 0x00, 0x00, 0x00, 0x7f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3c,
        0x00, 0xb8, 0x00, 0x38, 0x00, 0x38, 0x00, 0x00, 0x00, 0x7f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x38, 0x00, 0x38, 0x00, 0x38, 0x00, 0x00, 0x00, 0x7f, 0x00, 0x00, 0x00, 0x3c, 0x00, 0x00,
        0x00, 0x38, 0x00, 0x38, 0x00, 0xb8, 0x00, 0x00, 0x00, 0x7f, 0x00, 0x00, 0x00, 0x3c, 0x00, 0x3c,
        0x00, 0xb8, 0x00, 0x38, 0x00, 0xb8, 0x00, 0x00, 0x81, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3c,
        0x00, 0xb8, 0x00, 0xb8, 0x00, 0xb8, 0x00, 0x00, 0x81, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0xb8, 0x00, 0xb8, 0x00, 0x38, 0x00, 0x00, 0x81, 0x00, 0x00, 0x00, 0x00, 0x3c, 0x00, 0x00,
        0x00, 0xb8, 0x00, 0x38, 0x00, 0x38, 0x00, 0x00, 0x81, 0x00, 0x00, 0x00, 0x00, 0x3c, 0x00, 0x3c,
        0x00, 0x38, 0x00, 0x38, 0x00, 0x38, 0x00, 0x00, 0x7f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3c,
        0x00, 0x38, 0x00, 0xb8, 0x00, 0x38, 0x00, 0x00, 0x7f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x38, 0x00, 0xb8, 0x00, 0xb8, 0x00, 0x00, 0x7f, 0x00, 0x00, 0x00, 0x00, 0x3c, 0x00, 0x00,
        0x00, 0x38, 0x00, 0x38, 0x00, 0xb8, 0x00, 0x00, 0x7f, 0x00, 0x00, 0x00, 0x00, 0x3c, 0x00, 0x3c,
        0x00, 0x38, 0x00, 0x38, 0x00, 0xb8, 0x00, 0x00, 0x00, 0x00, 0x81, 0x00, 0x00, 0x00, 0x00, 0x3c,
        0x00, 0x38, 0x00, 0xb8, 0x00, 0xb8, 0x00, 0x00, 0x00, 0x00, 0x81, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0xb8, 0x00, 0xb8, 0x00, 0xb8, 0x00, 0x00, 0x00, 0x00, 0x81, 0x00, 0x00, 0x3c, 0x00, 0x00,
        0x00, 0xb8, 0x00, 0x38, 0x00, 0xb8, 0x00, 0x00, 0x00, 0x00, 0x81, 0x00, 0x00, 0x3c, 0x00, 0x3c,
        0x00, 0xb8, 0x00, 0x38, 0x00, 0x38, 0x00, 0x00, 0x00, 0x00, 0x7f, 0x00, 0x00, 0x00, 0x00, 0x3c,
        0x00, 0xb8, 0x00, 0xb8, 0x00, 0x38, 0x00, 0x00, 0x00, 0x00, 0x7f, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x38, 0x00, 0xb8, 0x00, 0x38, 0x00, 0x00, 0x00, 0x00, 0x7f, 0x00, 0x00, 0x3c, 0x00, 0x00,
        0x00, 0x38, 0x00, 0x38, 0x00, 0x38, 0x00, 0x00, 0x00, 0x00, 0x7f, 0x00, 0x00, 0x3c, 0x00, 0x3c,
        0x00, 0xb8, 0x00, 0xb8, 0x00, 0x38, 0x00, 0x00, 0x00, 0x81, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3c,
        0x00, 0xb8, 0x00, 0xb8, 0x00, 0xb8, 0x00, 0x00, 0x00, 0x81, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x38, 0x00, 0xb8, 0x00, 0xb8, 0x00, 0x00, 0x00, 0x81, 0x00, 0x00, 0x00, 0x3c, 0x00, 0x00,
        0x00, 0x38, 0x00, 0xb8, 0x00, 0x38, 0x00, 0x00, 0x00, 0x81, 0x00, 0x00, 0x00, 0x3c, 0x00, 0x3c,
        };

        unsigned char output[550]; // sdefl_bound returns 550

        struct sdefl sdefl = {0};
        int res = sdeflate(&sdefl, output, input, sizeof(input), 5);
}

Error:

==304559==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffe4af2de00 at pc 0x560871c0bef6 bp 0x7ffe4ae6ce20 sp 0x7ffe4ae6ce10
READ of size 1 at 0x7ffe4af2de00 thread T0
    #0 0x560871c0bef5 in sdefl_fnd (/home/zeux/sdefl/a.out+0x6ef5) (BuildId: 372353f051c4f94c52a6cf3ad3f442a987a8cf09)
    #1 0x560871c0c40f in sdefl_compr (/home/zeux/sdefl/a.out+0x740f) (BuildId: 372353f051c4f94c52a6cf3ad3f442a987a8cf09)
    #2 0x560871c0cc36 in sdeflate (/home/zeux/sdefl/a.out+0x7c36) (BuildId: 372353f051c4f94c52a6cf3ad3f442a987a8cf09)
    #3 0x560871c0d581 in main (/home/zeux/sdefl/a.out+0x8581) (BuildId: 372353f051c4f94c52a6cf3ad3f442a987a8cf09)
    #4 0x7ff4aa423a8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #5 0x7ff4aa423b48 in __libc_start_main_impl ../csu/libc-start.c:360
    #6 0x560871c07344 in _start (/home/zeux/sdefl/a.out+0x2344) (BuildId: 372353f051c4f94c52a6cf3ad3f442a987a8cf09)

You have the web server already, I guess it will be super great when you provide the client as well 😄

In mm_sched.h, on line 481, in sched_event_create(), "sched_event ret" is missing a "struct".

The function should read:

SCHED_INTERN struct sched_event
sched_event_create(void)
{
    struct sched_event ret;
    ret.event = CreateEvent(NULL, TRUE, FALSE, NULL);
    ret.count_waiters = 0;
    return ret;
}

Without the "struct", compilation fails on Visual Studio 2013.

There seems to be a bug when querying arrays with only 1 element. E.g.

{ "string_array": ["first string"] }

Works:

json_load(toks, num, &read, jsonString, jsonStringLen);
json_token* firstStringToken = json_query(toks, read, "string_array[0]");
assert(firstStringToken != NULL); // Works as expected.

Doesn't work:

json_load(toks, num, &read, jsonString, jsonStringLen);
json_token* stringArrToken = json_query(toks, read, "string_array");
json_token* firstStringToken = json_query(stringArrToken, stringArrToken->sub, "[0]");
assert(firstStringToken != NULL); // << Asserts!

If the array has 2 or more strings, both versions work correctly.

Am I doing something wrong?

The reason I prefer the 2nd method is because I can avoid repeated sprintf's when loading arrays. For small indices I keep a table of strings which maps i to "[i]". With the second method this isn't possible (I need a table for each array).

Steps to reproduce:

1. open (with correct IP and port) chrome-devtools://devtools/bundled/inspector.html?experiments=true&v8only=true&ws=127.0.0.1:8888/backend in Chrome, it sends multiple websocket frames in a row
2. wby_socket_recv receives data for all frames in a single call (e.g. 421 bytes in my case)
3. ws_frame callback in wby_update_connection is called only for the first frame (e.g. 47 bytes in my case)
4. other frames are ignored

Expected result: ws_frame callback should be called for all received websocket frames

Note: Win8