adler32_p.h

/* adler32_p.h -- Private inline functions and macros shared with
 *                different computation of the Adler-32 checksum
 *                of a data stream.
 * Copyright (C) 1995-2011, 2016 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

#ifndef ADLER32_P_H
#define ADLER32_P_H

#include "zendian.h"

#define BASE 65521U     /* largest prime smaller than 65536 */
#define NMAX 5552
/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
#define NMAX_ALIGNED32 (NMAX & ~31)
/* NMAX rounded down to a multiple of 32 is 5536 */

#define ADLER_DO1(sum1, sum2, buf, i)  {(sum1) += buf[(i)]; (sum2) += (sum1);}
#define ADLER_DO2(sum1, sum2, buf, i)  {ADLER_DO1(sum1, sum2, buf, i); ADLER_DO1(sum1, sum2, buf, i+1);}
#define ADLER_DO4(sum1, sum2, buf, i)  {ADLER_DO2(sum1, sum2, buf, i); ADLER_DO2(sum1, sum2, buf, i+2);}
#define ADLER_DO8(sum1, sum2, buf, i)  {ADLER_DO4(sum1, sum2, buf, i); ADLER_DO4(sum1, sum2, buf, i+4);}
#define ADLER_DO16(sum1, sum2, buf)    {ADLER_DO8(sum1, sum2, buf, 0); ADLER_DO8(sum1, sum2, buf, 8);}

Z_FORCEINLINE static void adler32_copy_align(uint32_t *Z_RESTRICT adler, uint8_t *dst, const uint8_t *buf, size_t len,
                                             uint32_t *Z_RESTRICT sum2, const int MAX_LEN, const int COPY) {
    Z_UNUSED(MAX_LEN);
    if (len & 1) {
        if (COPY) {
            *dst = *buf;
            dst += 1;
        }
        ADLER_DO1(*adler, *sum2, buf, 0);
        buf += 1;
    }
    if (len & 2) {
        if (COPY) {
            memcpy(dst, buf, 2);
            dst += 2;
        }
        ADLER_DO2(*adler, *sum2, buf, 0);
        buf += 2;
    }
    while (len >= 4) {
        if (COPY) {
            memcpy(dst, buf, 4);
            dst += 4;
        }
        len -= 4;
        ADLER_DO4(*adler, *sum2, buf, 0);
        buf += 4;
    }
}

/* SIMD Within A Register (SWAR) scalar adler32. Splits bytes into
 * even/odd lanes packed as 4x16-bit in uint64_t, with prefix sums for s2.
 * Reduction uses multiply-and-shift with positional weight constants.
 *
 * Technique pioneered by Michael Niedermayer <michaelni@gmx.at>.
 * Max chunk: 23 iterations * 8 bytes = 184 (255*23 = 5865 < 65535). */
#define ADLER32_SWAR_MAX_BYTES   (23 * 8)
#define ADLER32_SWAR_EVEN_MASK   0x00FF00FF00FF00FFULL
#define ADLER32_SWAR_HSUM        0x1000100010001ULL

Z_FORCEINLINE static void adler32_swar(uint32_t *adler, uint8_t *dst, const uint8_t *buf, size_t len,
                                       uint32_t *sum2, const int COPY) {
    uint64_t sum_even = 0, sum_odd = 0, prefix_even = 0, prefix_odd = 0;

    *sum2 += *adler * (uint32_t)len;

    const uint64_t *src64 = (const uint64_t *)buf;

    while (len >= 16) {
        uint64_t v0 = src64[0];
        uint64_t v1 = src64[1];
        if (COPY) {
            memcpy(dst, &v0, sizeof(v0));
            memcpy(dst + 8, &v1, sizeof(v1));
            dst += 16;
        }

        prefix_even += sum_even;
        prefix_odd += sum_odd;
        sum_even +=  v0       & ADLER32_SWAR_EVEN_MASK;
        sum_odd  += (v0 >> 8) & ADLER32_SWAR_EVEN_MASK;

        prefix_even += sum_even;
        prefix_odd += sum_odd;
        sum_even +=  v1       & ADLER32_SWAR_EVEN_MASK;
        sum_odd  += (v1 >> 8) & ADLER32_SWAR_EVEN_MASK;

        src64 += 2;
        len -= 16;
    }

    /* Handle remaining 8 bytes if present */
    if (len >= 8) {
        uint64_t v = *src64;
        if (COPY)
            memcpy(dst, &v, sizeof(v));

        prefix_even += sum_even;
        prefix_odd += sum_odd;
        sum_even +=  v       & ADLER32_SWAR_EVEN_MASK;
        sum_odd  += (v >> 8) & ADLER32_SWAR_EVEN_MASK;
    }

    /* Horizontal sum of 4x16-bit lanes for s1 */
    *adler += (uint32_t)(((sum_even + sum_odd) * ADLER32_SWAR_HSUM) >> 48);

    /* Widen prefix sums to 32-bit pairs and horizontal sum for s2 */
    uint64_t pe_lo = prefix_even & 0xFFFF0000FFFFULL;
    uint64_t pe_hi = (prefix_even >> 16) & 0xFFFF0000FFFFULL;
    uint64_t po_lo = prefix_odd & 0xFFFF0000FFFFULL;
    uint64_t po_hi = (prefix_odd >> 16) & 0xFFFF0000FFFFULL;

    *sum2 += (uint32_t)(((pe_lo + po_lo + pe_hi + po_hi) * 0x800000008ULL) >> 32);

    /* Positional weights [8,7,6,5,4,3,2,1] per 8-byte group for s2.
     * On big-endian the even mask captures odd-index memory bytes (b1,b3,b5,b7)
     * so HSUM (+1 per odd-index byte) must be applied to sum_even, not sum_odd. */
#if BYTE_ORDER == LITTLE_ENDIAN
    *sum2 += 2 * (uint32_t)((sum_even * 0x4000300020001ULL) >> 48)
           +     (uint32_t)((sum_odd  * ADLER32_SWAR_HSUM) >> 48)
           + 2 * (uint32_t)((sum_odd  * 0x3000200010000ULL) >> 48);
#else
    *sum2 += 2 * (uint32_t)((sum_even * 0x0000100020003ULL) >> 48)
           +     (uint32_t)((sum_even * ADLER32_SWAR_HSUM) >> 48)
           + 2 * (uint32_t)((sum_odd  * 0x1000200030004ULL) >> 48);
#endif
}

Z_FORCEINLINE static uint32_t adler32_copy_tail(uint32_t adler, uint8_t *dst, const uint8_t *buf, size_t len,
                                                uint32_t sum2, const int REBASE, const int MAX_LEN, const int COPY) {
    if (len) {
        Z_UNUSED(MAX_LEN);
        /* Process using packed 64-bit arithmetic when source is aligned */
        while (len >= 8 && ((uintptr_t)buf & 7) == 0) {
            size_t chunk = MIN(ALIGN_DOWN(len, (size_t)8), (size_t)ADLER32_SWAR_MAX_BYTES);
            adler32_swar(&adler, dst, buf, chunk, &sum2, COPY);
            buf += chunk;
            if (COPY)
                dst += chunk;
            len -= chunk;
        }
        /* DO4 loop avoids GCC x86 register pressure from hoisted DO8/DO16 loads. */
        while (len >= 4) {
            if (COPY) {
                memcpy(dst, buf, 4);
                dst += 4;
            }
            len -= 4;
            ADLER_DO4(adler, sum2, buf, 0);
            buf += 4;
        }
        if (len & 2) {
            if (COPY) {
                memcpy(dst, buf, 2);
                dst += 2;
            }
            ADLER_DO2(adler, sum2, buf, 0);
            buf += 2;
        }
        if (len & 1) {
            if (COPY)
                *dst = *buf;
            ADLER_DO1(adler, sum2, buf, 0);
        }
    }
    if (REBASE) {
        adler %= BASE;
        sum2 %= BASE;
    }
    /* D = B * 65536 + A, see: https://en.wikipedia.org/wiki/Adler-32. */
    return adler | (sum2 << 16);
}

#endif /* ADLER32_P_H */