tests/tests_deflate_slide_hash.c

#include "unity/unity.h"
#include "zlib.h"
#include <stdlib.h>
#include <string.h>

/* Access internal deflate_state and its members safely */
#define ZLIB_INTERNAL
#include "deflate.h"

/* The module provides this wrapper for the local slide_hash() */
extern void test_slide_hash(deflate_state *s);

static void init_stream(z_streamp strm, int windowBits, int memLevel) {
    memset(strm, 0, sizeof(*strm));
    int ret = deflateInit2_(strm,
                            Z_DEFAULT_COMPRESSION,
                            Z_DEFLATED,
                            windowBits,        /* 9 => w_size = 512 (small for tests) */
                            memLevel,          /* 1 => small hash_size = 256 */
                            Z_DEFAULT_STRATEGY,
                            ZLIB_VERSION,
                            (int)sizeof(z_stream));
    TEST_ASSERT_EQUAL_INT(Z_OK, ret);
}

static inline Pos after_one_slide(Pos m, uInt wsize) {
    return (Pos)(m >= wsize ? (m - wsize) : (Pos)NIL);
}

static inline Pos after_n_slides(Pos m, uInt wsize, int n) {
    for (int i = 0; i < n; i++) {
        m = (Pos)(m >= wsize ? (m - wsize) : (Pos)NIL);
    }
    return m;
}

void setUp(void) {
    /* no-op */
}
void tearDown(void) {
    /* no-op */
}

/* Populate head and prev arrays with a predictable pattern that exercises boundaries */
static void fill_pattern(deflate_state *s) {
    uInt w = s->w_size;

    for (uInt i = 0; i < s->hash_size; i++) {
        Pos v;
        switch (i % 5) {
            case 0: v = (Pos)NIL; break;                 /* 0 */
            case 1: v = (Pos)(w - 1); break;             /* below w */
            case 2: v = (Pos)(w); break;                 /* exactly w */
            case 3: v = (Pos)(w + 7); break;             /* just above w */
            default: v = (Pos)(w * 2 + 123); break;      /* well above w (single subtract still >= w) */
        }
        s->head[i] = v;
    }

#ifndef FASTEST
    for (uInt i = 0; i < s->w_size; i++) {
        Pos v;
        switch (i % 5) {
            case 0: v = (Pos)NIL; break;
            case 1: v = (Pos)(w - 1); break;
            case 2: v = (Pos)(w); break;
            case 3: v = (Pos)(w + 3); break;
            default: v = (Pos)(w * 2 + 7); break;
        }
        s->prev[i] = v;
    }
#endif
}

void test_slide_hash_shifts_values_correctly_small(void) {
    z_stream strm;
    init_stream(&strm, 9, 1); /* small arrays: w_size = 512, hash_size = 256 */
    deflate_state *s = (deflate_state *)strm.state;

    fill_pattern(s);

    /* Execute */
    test_slide_hash(s);

    /* Verify head[] */
    for (uInt i = 0; i < s->hash_size; i++) {
        Pos before;
        uInt w = s->w_size;
        switch (i % 5) {
            case 0: before = (Pos)NIL; break;
            case 1: before = (Pos)(w - 1); break;
            case 2: before = (Pos)(w); break;
            case 3: before = (Pos)(w + 7); break;
            default: before = (Pos)(w * 2 + 123); break;
        }
        Pos expected = after_one_slide(before, w);
        TEST_ASSERT_EQUAL_UINT16_MESSAGE(expected, s->head[i], "head[] incorrect after one slide");
    }

#ifndef FASTEST
    /* Verify prev[] */
    for (uInt i = 0; i < s->w_size; i++) {
        Pos before;
        uInt w = s->w_size;
        switch (i % 5) {
            case 0: before = (Pos)NIL; break;
            case 1: before = (Pos)(w - 1); break;
            case 2: before = (Pos)(w); break;
            case 3: before = (Pos)(w + 3); break;
            default: before = (Pos)(w * 2 + 7); break;
        }
        Pos expected = after_one_slide(before, w);
        TEST_ASSERT_EQUAL_UINT16_MESSAGE(expected, s->prev[i], "prev[] incorrect after one slide");
    }
#endif

    TEST_ASSERT_EQUAL_INT(Z_OK, deflateEnd(&strm));
}

void test_slide_hash_multiple_calls_accumulate_subtractions(void) {
    z_stream strm;
    init_stream(&strm, 9, 1);
    deflate_state *s = (deflate_state *)strm.state;

    fill_pattern(s);

    /* Two consecutive slides */
    test_slide_hash(s);
    test_slide_hash(s);

    /* Verify head[] after two slides: entries >= 2*w reduced by 2*w, others -> 0 */
    for (uInt i = 0; i < s->hash_size; i++) {
        Pos before;
        uInt w = s->w_size;
        switch (i % 5) {
            case 0: before = (Pos)NIL; break;
            case 1: before = (Pos)(w - 1); break;
            case 2: before = (Pos)(w); break;
            case 3: before = (Pos)(w + 7); break;
            default: before = (Pos)(w * 2 + 123); break;
        }
        Pos expected = after_n_slides(before, w, 2);
        TEST_ASSERT_EQUAL_UINT16_MESSAGE(expected, s->head[i], "head[] incorrect after two slides");
    }

#ifndef FASTEST
    /* Verify prev[] after two slides */
    for (uInt i = 0; i < s->w_size; i++) {
        Pos before;
        uInt w = s->w_size;
        switch (i % 5) {
            case 0: before = (Pos)NIL; break;
            case 1: before = (Pos)(w - 1); break;
            case 2: before = (Pos)(w); break;
            case 3: before = (Pos)(w + 3); break;
            default: before = (Pos)(w * 2 + 7); break;
        }
        Pos expected = after_n_slides(before, w, 2);
        TEST_ASSERT_EQUAL_UINT16_MESSAGE(expected, s->prev[i], "prev[] incorrect after two slides");
    }
#endif

    TEST_ASSERT_EQUAL_INT(Z_OK, deflateEnd(&strm));
}

void test_slide_hash_leaves_params_unchanged(void) {
    z_stream strm;
    init_stream(&strm, 9, 1);
    deflate_state *s = (deflate_state *)strm.state;

    uInt w_size_before = s->w_size;
    uInt hash_size_before = s->hash_size;
    uInt w_mask_before = s->w_mask;
    uInt hash_mask_before = s->hash_mask;

    fill_pattern(s);
    test_slide_hash(s);

    TEST_ASSERT_EQUAL_UINT(w_size_before, s->w_size);
    TEST_ASSERT_EQUAL_UINT(hash_size_before, s->hash_size);
    TEST_ASSERT_EQUAL_UINT(w_mask_before, s->w_mask);
    TEST_ASSERT_EQUAL_UINT(hash_mask_before, s->hash_mask);

    TEST_ASSERT_EQUAL_INT(Z_OK, deflateEnd(&strm));
}

void test_slide_hash_with_large_window_bits_boundary_cases(void) {
    z_stream strm;
    /* Use a larger window to ensure logic holds, but only modify a few entries to keep test light */
    init_stream(&strm, 15, 8); /* typical defaults: w_size = 32768, hash_size = 32768 */
    deflate_state *s = (deflate_state *)strm.state;
    uInt w = s->w_size;

    /* Set a few representative head entries */
    s->head[0] = (Pos)0;
    s->head[1] = (Pos)(w - 1);
    s->head[2] = (Pos)(w);
    s->head[3] = (Pos)(w + 1);
    s->head[4] = (Pos)(w + 123);

#ifndef FASTEST
    /* And a few prev entries */
    s->prev[0] = (Pos)0;
    s->prev[1] = (Pos)(w - 1);
    s->prev[2] = (Pos)(w);
    s->prev[3] = (Pos)(w + 1);
    s->prev[4] = (Pos)(w + 77);
#endif

    test_slide_hash(s);

    TEST_ASSERT_EQUAL_UINT16((Pos)0, s->head[0]);                 /* NIL stays NIL */
    TEST_ASSERT_EQUAL_UINT16((Pos)0, s->head[1]);                 /* below w -> NIL */
    TEST_ASSERT_EQUAL_UINT16((Pos)0, s->head[2]);                 /* exactly w -> 0 */
    TEST_ASSERT_EQUAL_UINT16((Pos)1, s->head[3]);                 /* w+1 -> 1 */
    TEST_ASSERT_EQUAL_UINT16((Pos)123, s->head[4]);               /* w+123 -> 123 */

#ifndef FASTEST
    TEST_ASSERT_EQUAL_UINT16((Pos)0, s->prev[0]);
    TEST_ASSERT_EQUAL_UINT16((Pos)0, s->prev[1]);
    TEST_ASSERT_EQUAL_UINT16((Pos)0, s->prev[2]);
    TEST_ASSERT_EQUAL_UINT16((Pos)1, s->prev[3]);
    TEST_ASSERT_EQUAL_UINT16((Pos)77, s->prev[4]);
#endif

    TEST_ASSERT_EQUAL_INT(Z_OK, deflateEnd(&strm));
}

int main(void) {
    UNITY_BEGIN();
    RUN_TEST(test_slide_hash_shifts_values_correctly_small);
    RUN_TEST(test_slide_hash_multiple_calls_accumulate_subtractions);
    RUN_TEST(test_slide_hash_leaves_params_unchanged);
    RUN_TEST(test_slide_hash_with_large_window_bits_boundary_cases);
    return UNITY_END();
}