Utils.cpp

#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <random>
#include <sstream>
#include <string>
#include <vector>

#include "Utils.h"


namespace bitutil {


inline int PopCount(unsigned long long x) {
    /*
    [PopCount]
    [INPUT]:  number - x
    [OUTPUT]: number of bits of x equal to 1 - c 
    [DESCRIPTION]: Counts number of nonzero bits c in number x
    */
    int c = 0;
    while (x) { c += (x & 1ULL); x >>= 1; }
    return c;
}

inline int Parity(unsigned long long x) {
    /*
    [Parity]
    [INPUT]:  number - x
    [OUTPUT]: oddness of input number 
    [DESCRIPTION]: Determines if number of nonzero bits is odd(1) or even(0)
    */
    return PopCount(x) & 1;
}

inline bool IsPowerOfTwo(int x) {
    /*
    [IsPowerOfTwo]
    [INPUT]:  number - x
    [OUTPUT]: boolean - y
    [DESCRIPTION]: Decides whether number is a power(true) of two or not(false)
    */
    return x > 0 && (x & (x - 1)) == 0;
}

inline int ExactLog2(int x) {
    /*
    [ExactLog2]
    [INPUT]:  number - x
    [OUTPUT]: highest power of 2 dividing x, if x = 1<<y - y
    [DESCRIPTION]: log2 for an exact power of two, else -1
    */

    if (!IsPowerOfTwo(x)) return -1;
    int n = 0;
    while ((1 << n) < x) n++;
    return n;
}

inline int BitsNeeded(unsigned long long v) {
    /*
    [BitsNeeded]
    [INPUT]:  number - x
    [OUTPUT]: number of bits needed for a number x - y
    [DESCRIPTION]: Smallest number of bits needed to represent value v (v=0 -> 1 bit)
    */

    int n = 1;
    while ((1ULL << n) <= v) n++;
    return n;
}

}




std::mt19937& Rng() {
    /*
    [Rng]
    [INPUT]:  
    [OUTPUT]: Mersenne Twister PRNG
    [DESCRIPTION]: Thread-local PRNG seeded from hardware entropy.
    */

    static thread_local std::mt19937 gen(std::random_device{}());
    return gen;
}

void RandBytes(uint8_t* buf, int n) {
    /*
    [RandBytes]
    [INPUT]: a buffer buf of length n
    [OUTPUT]: 
    [DESCRIPTION]: Fill buffer with uniformly random bytes. 
    */
    std::uniform_int_distribution<int> dist(0, 255);
    for (int i = 0; i < n; ++i)
        buf[i] = static_cast<uint8_t>(dist(Rng()));
}

void XorBufs(uint8_t* dst, const uint8_t* a, const uint8_t* b, int n) {
    /*
    [XorBufs]
    [INPUT]: destination dst, left and right array operands a,b
    [OUTPUT]: 
    [DESCRIPTION]: XOR two byte arrays: dst = a ^ b 
    */
    for (int i = 0; i < n; ++i) dst[i] = a[i] ^ b[i];
}



int DotProduct(const uint8_t* a, const uint8_t* b, int n) {
    /*
    [DotProduct]
    [INPUT]: two byte vectors a, b
    [OUTPUT]: 
    [DESCRIPTION]: Dot product (parity of AND) between two byte vectors. 
    */
    int result = 0;
    for (int i = 0; i < n; ++i)
        result ^= bitutil::Parity(a[i] & b[i]);
    return result;
}


double ChiSquared(const int* hist, int n) {
    /*
    [ChiSquared]
    [INPUT]: histogram hist of size n
    [OUTPUT]: 
    [DESCRIPTION]: Chi-squared statistic for a histogram of `n` observations across 256 buckets.
    * Expected count per bucket = n / 256.
    */

    double expected = static_cast<double>(n) / 256.0;
    double chi2 = 0.0;
    for (int i = 0; i < 256; ++i) {
        double diff = hist[i] - expected;
        chi2 += diff * diff / expected;
    }
    return chi2;
}


double Chi2pvalue(double chi2, int df = 255) {
    /*
    [Chi2pvalue]
    [INPUT]: chi2 value and degrees of freedom df
    [OUTPUT]: probability of exceeding chi2
    [DESCRIPTION]: Approximate p-value for chi-squared with df=255 degrees of freedom
     using a regularised incomplete gamma function (Wilson–Hilferty approximation).
     Returns the probability that chi2 is exceeded by chance.
    */

    // Wilson–Hilferty cube-root normal approximation
    double k   = static_cast<double>(df);
    double z   = (std::pow(chi2 / k, 1.0/3.0) - (1.0 - 2.0/(9.0*k)))
                 / std::sqrt(2.0/(9.0*k));
    // Complementary error function approximation of the normal CDF
    // p = Pr[Z > z]  (upper tail)
    return 0.5 * std::erfc(z / std::sqrt(2.0));
}




std::string ScoreBar(double score, int width = 30) {
    /*
    [ScoreBar]
    [INPUT]: score and width of the string
    [OUTPUT]: filled string bar
    [DESCRIPTION]: Produce a filled score bar for display.
    */

    int filled = static_cast<int>(std::round(score / 100.0 * width));
    filled = std::clamp(filled, 0, width);
    std::string bar = "[";
    for (int i = 0; i < width; ++i)
        bar += (i < filled) ? '#' : '.';
    bar += "]";
    return bar;
}

std::string VerdictStr(double score) {
    /*
    [VerdictStr]
    [INPUT]: score
    [OUTPUT]: string evaluation
    [DESCRIPTION]: returns human - readable score as evaluation overall result
    */

    if (score >= 90) return "STRONG";
    if (score >= 70) return "ADEQUATE";
    if (score >= 50) return "WEAK";
    if (score >= 25) return "VULNERABLE";
    return "BROKEN";
}