Zlib-ng compare258

compare258.c

/* compare258.c -- compare258 variants for use in longest_match
 * Copyright (C) 2020 Nathan Moinvaziri
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

// ALIGNED, byte comparison
static inline int32_t compare258(const unsigned char *src0, const unsigned char *src1) {
    register const unsigned char *src0start = src0;
    register const unsigned char *src0end = src0 + 258; // 258 % 6 = 0

    do {
        if (*src0 != *src1)
            break;
        src0 += 1, src1 += 1;
        if (*src0 != *src1)
            break;
        src0 += 1, src1 += 1;
        if (*src0 != *src1)
            break;
        src0 += 1, src1 += 1;
        if (*src0 != *src1)
            break;
        src0 += 1, src1 += 1;
        if (*src0 != *src1)
            break;
        src0 += 1, src1 += 1;
        if (*src0 != *src1)
            break;
        src0 += 1, src1 += 1;
    } while (src0 < src0end);
 
    return (int32_t)(src0 - src0start);
}

// UNALIGNED_OK, 16-bit integer comparison
static inline int32_t compare258_unaligned_16(const unsigned char *src0, const unsigned char *src1) {
    register const unsigned char *src0start = src0;
    register const unsigned char *src0end = src0 + 258; // 258 % 6 = 0

    do {
        if (*(uint16_t *)src0 != *(uint16_t *)src1)
            break;
        src0 += 2, src1 += 2;
        if (*(uint16_t *)src0 != *(uint16_t *)src1)
            break;
        src0 += 2, src1 += 2;
        if (*(uint16_t *)src0 != *(uint16_t *)src1)
            break;
        src0 += 2, src1 += 2;
    } while (src0 < src0end);

    if (*src0 == *src1)
        src0 += 1;

    return (int32_t)(src0 - src0start);
}

// UNALIGNED_OK, 32-bit integer comparison
static inline int32_t compare258_unaligned_32(const unsigned char *src0, const unsigned char *src1) {
    register const unsigned char *src0start = src0;
    register const unsigned char *src0end = src0 + 258; // (258 - 2) % 4 = 0

    if (*(uint16_t *)src0 != *(uint16_t *)src1)
        return (*src0 == *src1);

    src0 += 2, src1 += 2;
    if (*src0 != *src1)
        return 2;
    if (src0[1] != src1[1])
        return 3;

    do {
        uint32_t *sv = (uint32_t *)src0;
        uint32_t *mv = (uint32_t *)src1;
        uint32_t xor = *sv ^ *mv;

        if (xor) {
            uint32_t match_byte = __builtin_ctz(xor) / 8;
            return (int32_t)(src0 - src0start + match_byte);
        }

        src0 += 4, src1 += 4;
    } while (src0 < src0end);

    return (int32_t)(src0 - src0start);
}

// UNALIGNED_OK, 64-bit integer comparison
static inline int32_t compare258_unaligned_64(const unsigned char *src0, const unsigned char *src1) {
    register const unsigned char *src0start = src0;
    register const unsigned char *src0end = src0 + 258; // (258 - 2) % 8 = 0

    if (*(uint16_t *)src0 != *(uint16_t *)src1)
        return (*src0 == *src1);

    src0 += 2, src1 += 2;
    if (*src0 != *src1)
        return 2;
    if (src0[1] != src1[1])
        return 3;

    do {
        uint64_t *sv = (uint64_t *)src0;
        uint64_t *mv = (uint64_t *)src1;
        uint64_t xor = *sv ^ *mv;

        if (xor) {
            uint64_t match_byte = __builtin_ctzll(xor) / 8;
            return (int32_t)(src0 - src0start + match_byte);
        }

        src0 += 8, src1 += 8;
    } while (src0 < src0end);

    return (int32_t)(src0 - src0start);
}

// UNALIGNED_OK, 128-bit SSE4.2 instrinic comparison
static inline int32_t compare258_unaligned_128(const unsigned char *src0, const unsigned char *src1) {
#ifdef _MSC_VER
    register const unsigned char *src0start = src0;
    register const unsigned char *src0end = src0 + 258; // (258 - 2) % 16 = 0

    if (*(uint16_t *)src0 != *(uint16_t *)src1)
        return (*src0 == *src1);

    src0 += 2, src1 += 2;

    if (*src0 != *src1)
        return 2;
    if (src0[1] != src1[1])
        return 3;

    do {
        #define mode _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_EACH | _SIDD_NEGATIVE_POLARITY
        __m128i xmm_src0, xmm_src1;
        int ret;

        xmm_src0 = _mm_loadu_si128((__m128i *)src0);
        xmm_src1 = _mm_loadu_si128((__m128i *)src1);
        ret = _mm_cmpestri(xmm_src0, 16, xmm_src1, 16, mode);
        if (_mm_cmpestrc(xmm_src0, 16, xmm_src1, 16, mode)) {
            return (int32_t)(src0 - src0start + ret);
        }
        src0 += 16, src1 += 16;

        xmm_src0 = _mm_loadu_si128((__m128i *)src0);
        xmm_src1 = _mm_loadu_si128((__m128i *)src1);
        ret = _mm_cmpestri(xmm_src0, 16, xmm_src1, 16, mode);
        if (_mm_cmpestrc(xmm_src0, 16, xmm_src1, 16, mode)) {
            return (int32_t)(src0 - src0start + ret);
        }
        src0 += 16, src1 += 16;
    } while (src0 < src0end);

    return (int32_t)(src0 - src0start);
#else
    uintptr_t ax, dx, cx;
    __m128i xmm_src0;

    ax = 16;
    dx = 16;
    /* Set cx to something, otherwise gcc thinks it's used
       uninitalised */
    cx = 0;

    __asm__ __volatile__ (
    "1:"
        "movdqu     -16(%[src0], %[ax]), %[xmm_src0]\n\t"
        "pcmpestri  $0x18, -16(%[src1], %[ax]), %[xmm_src0]\n\t"
        "jc         2f\n\t"
        "add        $16, %[ax]\n\t"

        "movdqu     -16(%[src0], %[ax]), %[xmm_src0]\n\t"
        "pcmpestri  $0x18, -16(%[src1], %[ax]), %[xmm_src0]\n\t"
        "jc         2f\n\t"
        "add        $16, %[ax]\n\t"

        "cmp        $256 + 16, %[ax]\n\t"
        "jb         1b\n\t"

#  if !defined(__x86_64__)
        "movzwl     -16(%[src0], %[ax]), %[dx]\n\t"
#  else
        "movzwq     -16(%[src0], %[ax]), %[dx]\n\t"
#  endif
        "xorw       -16(%[src1], %[ax]), %%dx\n\t"
        "jnz        3f\n\t"

        "add        $2, %[ax]\n\t"
        "jmp        4f\n\t"
    "3:\n\t"
        "rep; bsf   %[dx], %[cx]\n\t"
        "shr        $3, %[cx]\n\t"
    "2:"
        "add        %[cx], %[ax]\n\t"
    "4:"
    : [ax] "+a" (ax),
      [cx] "+c" (cx),
      [dx] "+d" (dx),
      [xmm_src0] "=x" (xmm_src0)
    : [src0] "r" (src0),
      [src1] "r" (src1)
    : "cc"
    );
    return (int32_t)(ax - 16);
#endif
}

Results of each function with 100 million runs on Intel Core i7-8700 3.2ghz:

compare258 average: 92
compare258_unaligned_16 average: 65
compare258_unaligned_long average: 142
compare258_sse4 average: 171

When you do pre-increment, it doesn't actually compare the first byte.

Good catch. I think my results are correct just based on the functions themselves. But if all 258 bytes were the same, then sse4 would win. So I need to put some preliminary check inside compare258 for 32 and sse4.

I have added the checks. Where match_len: 258

compare258 average ms: 55
compare258_unaligned_16 average ms: 23
compare258_unaligned_32 average ms: 19
compare258_sse4 average ms: 7

The speed test is bad as it assumes uint32_t is same width as long, which isn't true... long can also be 64 bits.
You can also use __builtin_ctzl for the last two bytes so it doesn't have to use two if blocks.

Perhaps I should use __builtin_ctz for compare258_unaligned_32 and __builtin_ctzll for compare258_unaligned_64?

I have updated the code and posted some performance tests here which I will try to keep updated https://gist.github.com/nmoinvaz/6894ad8f1552f5546b950e4d8eafdab2
At match lengths over 14 bytes compare258_unaligned_128 is the clear winner in terms of performance.

I have been running additional tests at all match lengths to make sure each function returns the same result.

I imagine we can use these functions with functable and a single longest_match function. This will remove compare258 function from deflate_quick and make it 1) accessible for all other deflate methods 2) use compare_unaligned_128 only if the cpu check says it supports sse4.2. Adding @Dead2 if he wants to chime in.

When you do 2+256 compare using 32-bit compare, you can actually overlap comparing the first 6 bytes if you just increase the pointers by 2 bytes instead of 4 bytes after the initial check outside the loop. For 64-bit compare, you just overlap first 10 bytes.

@mtl1979, how does it return -1 if both are equal, wouldn't the result be true which is 1?

I'm not sure how I am overlapping. I only see that I overlap the read during if (*src0 != *src1) check and if (src0[1] != src1[1]) check which is intentional because I noticed on low match length those two algorithms did poorly where match length <= 3 and it is only over reading by 2 bytes.

Best way to overlap should be to make last check at offset 250 (for 64-bit) or 254 (for 32-bit), then it will not be slow if match length is 3~6 + multiple of variable width. Match length is never less than 3, so those cases can be ignored.

Ok I changed it. src0end should always be 258 I think. For 64-bit: Starting at the beginning +2, then read 8 until src0 < src0end. It will stop when src0 == src0end or after 250 offset has been checked.

Have not reviewed this yet (packing to go spend a week at a mountain cabin), but just wanted to step in before I leave and say this is looking very exciting. I am very much looking forward to see and test the end result here!

Thanks have fun on your trip. I think I will incorporate these into functable that way it can be used by deflate_quick directly - and deflate_quick can become cross-platform. And I also plan on merging all longest_match functions into one and use this same function. After that is done, we can possibly do something along the same lines as the insert_string header trick to get compare258 inline, but I rather see the performance results before we do that, it might not be worth it.