ex_entropy.c

Go to the documentation of this file.

/*
 * Nilorea Library
 * Copyright (C) 2005-2026 Castagnier Mickael
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
 * implied. See the License for the specific language governing
 * permissions and limitations under the License.
 *
 * SPDX-License-Identifier: Apache-2.0
 */

 
#include "nilorea/n_entropy.h"
#include "nilorea/n_log.h"
 
#include <math.h>
#include <string.h>
 
static int failures = 0;
 
static void approx(const char* label, double got, double want, double tol) {
    if (fabs(got - want) > tol) {
        n_log(LOG_ERR, "%s: got %.4f, expected %.4f", label, got, want);
        failures++;
    }
}
 
int main(void) {
    unsigned char uni[256];
    unsigned char same[64];
    unsigned char z[8];
    unsigned char f[8];
    unsigned char half[8];
    unsigned char two[4] = {'A', 'B', 'A', 'B'};
    int i;
    set_log_level(LOG_ERR);
 
    /* a uniform byte histogram: max entropy, zero chi-square, balanced bits */
    for (i = 0; i < 256; i++)
        uni[i] = (unsigned char)i;
    approx("uniform shannon", n_entropy_shannon(uni, 256), 8.0, 0.0001);
    approx("uniform chi", n_entropy_chi_square(uni, 256), 0.0, 0.0001);
    approx("uniform monobit", n_entropy_monobit(uni, 256), 0.5, 0.01);
 
    /* a single repeated value: zero entropy, large chi-square */
    memset(same, 'A', sizeof(same));
    approx("same shannon", n_entropy_shannon(same, sizeof(same)), 0.0, 0.0001);
    if (n_entropy_chi_square(same, sizeof(same)) <= 255.0) {
        n_log(LOG_ERR, "same chi-square should be large");
        failures++;
    }
 
    /* monobit on known bit patterns */
    memset(z, 0x00, sizeof(z));
    memset(f, 0xFF, sizeof(f));
    memset(half, 0x0F, sizeof(half));
    approx("zeros monobit", n_entropy_monobit(z, sizeof(z)), 0.0, 0.0001);
    approx("ones monobit", n_entropy_monobit(f, sizeof(f)), 1.0, 0.0001);
    approx("half monobit", n_entropy_monobit(half, sizeof(half)), 0.5, 0.0001);
 
    /* two equally likely symbols: exactly one bit of entropy */
    approx("two-symbol shannon", n_entropy_shannon(two, 4), 1.0, 0.0001);
 
    /* empty / NULL samples are zero, not a crash */
    approx("empty shannon", n_entropy_shannon(NULL, 0), 0.0, 0.0);
    approx("empty chi", n_entropy_chi_square(z, 0), 0.0, 0.0);
    approx("empty monobit", n_entropy_monobit(NULL, 0), 0.0, 0.0);
 
    /* ---- the per-position and per-bit suite ---- */
    {
        /* 64 tokens, each 4 bytes: the first two positions are random, the third is
           always the same value, and the fourth alternates between two values. That
           is what a real weak token looks like, and what an aggregate metric hides:
           the overall entropy stays high while two positions carry almost nothing. */
        static unsigned char toks[64][4];
        const unsigned char* ptrs[64];
        N_ENTROPY_POS pos[4];
        N_ENTROPY_BIT bits[32];
        size_t t, np, nb;
        unsigned int seed = 12345u;
        for (t = 0; t < 64; t++) {
            seed = seed * 1103515245u + 12345u;
            toks[t][0] = (unsigned char)(seed >> 16);
            seed = seed * 1103515245u + 12345u;
            toks[t][1] = (unsigned char)(seed >> 16);
            toks[t][2] = 0x42;                                 /* stuck */
            toks[t][3] = (unsigned char)((t % 2) ? 'a' : 'b'); /* two values */
            ptrs[t] = toks[t];
        }
        np = n_entropy_positions(ptrs, 64, 4, pos, 4);
        if (np != 4) {
            n_log(LOG_ERR, "positions: expected 4, got %zu", np);
            failures++;
        }
        /* the stuck position is the finding: one value, zero entropy */
        if (pos[2].distinct != 1) {
            n_log(LOG_ERR, "position 2 should have a single value, got %zu", pos[2].distinct);
            failures++;
        }
        approx("stuck position entropy", pos[2].shannon, 0.0, 0.0001);
        /* the two-value position carries exactly one bit */
        if (pos[3].distinct != 2) {
            n_log(LOG_ERR, "position 3 should have two values, got %zu", pos[3].distinct);
            failures++;
        }
        approx("two-value position entropy", pos[3].shannon, 1.0, 0.0001);
        /* while the random positions carry many values and much more entropy */
        if (pos[0].distinct < 30 || pos[0].shannon < 4.0) {
            n_log(LOG_ERR, "position 0 should look random: %zu values, %.2f bits", pos[0].distinct, pos[0].shannon);
            failures++;
        }
 
        nb = n_entropy_bits(ptrs, 64, 4, bits, 32);
        if (nb != 32) {
            n_log(LOG_ERR, "bits: expected 32, got %zu", nb);
            failures++;
        }
        /* 0x42 is 0100 0010: bit 16 of the token (the top bit of byte 2) is always 0
           and bit 17 always 1, so both are stuck and must be flagged */
        if (bits[16].ones != 0 || bits[17].ones != 64) {
            n_log(LOG_ERR, "stuck bits misreported: %zu / %zu", bits[16].ones, bits[17].ones);
            failures++;
        }
        if (bits[17].p_value > 0.01) {
            n_log(LOG_ERR, "a stuck bit should be significant, p=%.4f", bits[17].p_value);
            failures++;
        }
    }
 
    /* the chi-square p-value: a statistic equal to its degrees of freedom is
       unremarkable, a huge one is not */
    {
        double p_mid = n_entropy_chi_square_p(10.0, 10);
        double p_big = n_entropy_chi_square_p(200.0, 10);
        if (p_mid < 0.3 || p_mid > 0.7) {
            n_log(LOG_ERR, "chi p(10,10) should be mid-range, got %.4f", p_mid);
            failures++;
        }
        if (p_big > 1e-6) {
            n_log(LOG_ERR, "chi p(200,10) should be tiny, got %.6f", p_big);
            failures++;
        }
        approx("chi p of zero", n_entropy_chi_square_p(0.0, 10), 1.0, 0.0001);
        approx("chi p with no df", n_entropy_chi_square_p(50.0, 0), 1.0, 0.0001);
    }
 
    /* the runs test catches what monobit cannot: 0x0F repeated has exactly half its
       bits set (monobit is perfect) but they come in long blocks */
    {
        double p_runs = n_entropy_runs_p(half, sizeof(half));
        approx("blocky monobit is perfect", n_entropy_monobit(half, sizeof(half)), 0.5, 0.0001);
        if (p_runs > 0.01) {
            n_log(LOG_ERR, "runs test should reject a blocky stream, p=%.4f", p_runs);
            failures++;
        }
        if (n_entropy_longest_run(half, sizeof(half)) != 4) {
            n_log(LOG_ERR, "longest run of 0x0F should be 4, got %zu", n_entropy_longest_run(half, sizeof(half)));
            failures++;
        }
        if (n_entropy_longest_run(f, sizeof(f)) != sizeof(f) * 8) {
            n_log(LOG_ERR, "all-ones longest run should span the sample");
            failures++;
        }
    }
 
    /* guards: NULL and zero-sized inputs answer, they do not crash */
    {
        N_ENTROPY_POS pos1[1];
        N_ENTROPY_BIT bit1[1];
        const unsigned char* one[1];
        one[0] = z;
        if (n_entropy_positions(NULL, 1, 1, pos1, 1) != 0) failures++;
        if (n_entropy_positions(one, 0, 1, pos1, 1) != 0) failures++;
        if (n_entropy_positions(one, 1, 0, pos1, 1) != 0) failures++;
        if (n_entropy_positions(one, 1, 1, NULL, 1) != 0) failures++;
        if (n_entropy_bits(NULL, 1, 1, bit1, 1) != 0) failures++;
        if (n_entropy_bits(one, 1, 1, NULL, 1) != 0) failures++;
        approx("runs of an empty sample", n_entropy_runs_p(NULL, 0), 0.0, 0.0);
        if (n_entropy_longest_run(NULL, 0) != 0) failures++;
    }
 
    if (failures) {
        n_log(LOG_ERR, "ex_entropy: %d failure(s)", failures);
        return 1;
    }
    n_log(LOG_NOTICE, "ex_entropy: all checks passed");
    return 0;
}