Palette from Image — C source

/* palette-from-image — C port: dominant-color extraction via median-cut
   quantization. C11, stdlib only. Port of src/lib/palette-extract.ts — same
   logic as this dir's typescript.ts; empty or fully-transparent input yields
   a zero-count palette (the TS twin returns []), the caller frees the result. */
#include <stdio.h>
#include <stdlib.h>

/* One dominant color: averaged RGB plus the pixel count it represents. */
typedef struct {
    int r, g, b;
    size_t population;
} swatch;

/* An opaque sample pixel. `seq` is the sampling order: qsort is NOT stable,
   so the split sort tie-breaks on it to stay deterministic like the TS twin. */
typedef struct {
    unsigned char r, g, b;
    size_t seq;
} pixel;

/* Down-sample so large images quantize in bounded time. */
enum { MAX_SAMPLES = 16384 };

/* The widest single-channel span (0-255) inside a bucket. */
static int channel_range(const pixel *p, size_t n) {
    int min_r = 255, max_r = 0, min_g = 255, max_g = 0, min_b = 255, max_b = 0;
    for (size_t i = 0; i < n; i++) {
        if (p[i].r < min_r) min_r = p[i].r;
        if (p[i].r > max_r) max_r = p[i].r;
        if (p[i].g < min_g) min_g = p[i].g;
        if (p[i].g > max_g) max_g = p[i].g;
        if (p[i].b < min_b) min_b = p[i].b;
        if (p[i].b > max_b) max_b = p[i].b;
    }
    int rr = max_r - min_r, gg = max_g - min_g, bb = max_b - min_b;
    int m = rr;
    if (gg > m) m = gg;
    if (bb > m) m = bb;
    return m;
}

/* qsort has no context parameter in portable C11, so the split channel rides
   in a file-scope variable. Channel ties prefer r, then g — as in the TS. */
static int g_channel;

static int cmp_channel(const void *a, const void *b) {
    const pixel *x = a, *y = b;
    int xv = g_channel == 0 ? x->r : g_channel == 1 ? x->g : x->b;
    int yv = g_channel == 0 ? y->r : g_channel == 1 ? y->g : y->b;
    if (xv != yv) return xv < yv ? -1 : 1;
    return x->seq < y->seq ? -1 : 1; /* seq tie-break makes qsort "stable" */
}

/* Widest channel of a bucket, as an index 0=r 1=g 2=b (ties: r, then g). */
static int widest_channel(const pixel *p, size_t n) {
    int min_r = 255, max_r = 0, min_g = 255, max_g = 0, min_b = 255, max_b = 0;
    for (size_t i = 0; i < n; i++) {
        if (p[i].r < min_r) min_r = p[i].r;
        if (p[i].r > max_r) max_r = p[i].r;
        if (p[i].g < min_g) min_g = p[i].g;
        if (p[i].g > max_g) max_g = p[i].g;
        if (p[i].b < min_b) min_b = p[i].b;
        if (p[i].b > max_b) max_b = p[i].b;
    }
    int ranges[3] = {max_r - min_r, max_g - min_g, max_b - min_b};
    int ch = 0;
    if (ranges[1] > ranges[ch]) ch = 1;
    if (ranges[2] > ranges[ch]) ch = 2;
    return ch;
}

/* Round-half-up average of a channel sum over n (TS Math.round semantics;
   integer math avoids any float-rounding surprises). */
static int round_avg(long sum, size_t n) {
    return (int)((2 * sum + (long)n) / (2 * (long)n));
}

/* Extract up to max_colors dominant swatches from raw RGBA pixels. The
   result is malloc'd (NULL + *count 0 when empty); the caller frees it. */
static swatch *extract_palette(const unsigned char *rgba, size_t len,
                               int max_colors, size_t *count) {
    *count = 0;
    if (max_colors < 1) return NULL;
    size_t total = len / 4;
    if (total == 0) return NULL;

    /* Down-sample with a stride, skipping fully transparent pixels. */
    pixel *pixels = malloc(total * sizeof *pixels);
    if (!pixels) return NULL;
    size_t stride = total / MAX_SAMPLES;
    if (stride < 1) stride = 1;
    size_t n = 0;
    for (size_t i = 0; i < total; i += stride) {
        const unsigned char *o = rgba + i * 4;
        if (o[3] == 0) continue;
        pixels[n] = (pixel){o[0], o[1], o[2], n};
        n++;
    }
    if (n == 0) {
        free(pixels);
        return NULL;
    }

    /* Median-cut: start from one bucket of everything, split until we have
       max_colors buckets or no bucket has more than one distinct value. */
    pixel *bpx[64]; /* bucket storage; the caller caps max_colors well below */
    size_t bn[64];
    int nb = 1;
    bpx[0] = pixels;
    bn[0] = n;
    while (nb < max_colors) {
        /* Widest-range bucket with more than one distinct value wins. */
        int best = -1, best_range = 1; /* range 1 = exact duplicates only */
        for (int i = 0; i < nb; i++) {
            int range = channel_range(bpx[i], bn[i]);
            if (range > best_range) {
                best_range = range;
                best = i;
            }
        }
        if (best == -1) break;
        pixel *bucket = bpx[best];
        size_t blen = bn[best];
        g_channel = widest_channel(bucket, blen);
        qsort(bucket, blen, sizeof *bucket, cmp_channel);
        size_t mid = blen / 2;
        bpx[best] = bucket; /* first half stays in place… */
        bn[best] = mid;
        bpx[nb] = bucket + mid; /* …and the second half becomes a new bucket */
        bn[nb] = blen - mid;
        nb++;
    }

    swatch *out = malloc((size_t)nb * sizeof *out);
    if (!out) {
        free(pixels);
        return NULL;
    }
    size_t ns = 0;
    for (int i = 0; i < nb; i++) {
        if (bn[i] == 0) continue;
        long sr = 0, sg = 0, sb = 0;
        for (size_t j = 0; j < bn[i]; j++) {
            sr += bpx[i][j].r;
            sg += bpx[i][j].g;
            sb += bpx[i][j].b;
        }
        out[ns++] = (swatch){round_avg(sr, bn[i]), round_avg(sg, bn[i]),
                             round_avg(sb, bn[i]), bn[i]};
    }
    free(pixels);

    /* Population-descending insertion sort: short, and stable by nature. */
    for (size_t i = 1; i < ns; i++) {
        swatch key = out[i];
        size_t j = i;
        while (j > 0 && out[j - 1].population < key.population) {
            out[j] = out[j - 1];
            j--;
        }
        out[j] = key;
    }
    *count = ns;
    return out;
}

/* Format a swatch as #rrggbb (lowercase, always two digits per channel). */
static void to_hex(const swatch *s, char buf[8]) {
    snprintf(buf, 8, "#%02x%02x%02x", s->r, s->g, s->b);
}

/* px packs RGBA colors into a flat byte buffer, as ImageData.data lays it out. */
static unsigned char *px(const int colors[][4], size_t n) {
    unsigned char *out = malloc(n * 4);
    for (size_t i = 0; i < n; i++) {
        out[i * 4] = (unsigned char)colors[i][0];
        out[i * 4 + 1] = (unsigned char)colors[i][1];
        out[i * 4 + 2] = (unsigned char)colors[i][2];
        out[i * 4 + 3] = (unsigned char)colors[i][3];
    }
    return out;
}

int main(void) {
    /* The lib's canonical vectors: three red pixels and two blue ones, then
       a 64-step red→blue gradient capped at 6 swatches. */
    static const int two[][4] = {{255, 0, 0, 255}, {255, 0, 0, 255},
                                 {255, 0, 0, 255}, {0, 0, 255, 255},
                                 {0, 0, 255, 255}};
    unsigned char *buf = px(two, 5);
    size_t count = 0;
    swatch *sw = extract_palette(buf, 5 * 4, 8, &count);
    free(buf);
    printf("two colors: ");
    for (size_t i = 0; i < count; i++) {
        char hex[8];
        to_hex(&sw[i], hex);
        printf("%s x%zu%s", hex, sw[i].population, i + 1 < count ? ", " : "\n");
    }
    free(sw);

    int grad[64][4];
    for (int i = 0; i < 64; i++) {
        grad[i][0] = i * 4;
        grad[i][1] = 128;
        grad[i][2] = 255 - i * 4;
        grad[i][3] = 255;
    }
    buf = px(grad, 64);
    sw = extract_palette(buf, 64 * 4, 6, &count);
    free(buf);
    printf("gradient -> %zu swatches:\n", count);
    for (size_t i = 0; i < count; i++) {
        char hex[8];
        to_hex(&sw[i], hex);
        printf("  %-9s x%zu\n", hex, sw[i].population);
    }
    free(sw);
    return 0;
}