1/* @ajax/hist-quantile: its tables and functions. */
2#include "hist_quantile.h"
3
4uint32_t hist_quantile(const uint32_t *hist, size_t n, uint64_t per_mille) {
5    uint64_t total = 0;
6    for (size_t i = 0; i < n; i++) total += hist[i];
7    if (total == 0) return 0;
8    /* saturating_mul, then div_ceil, then at least 1 */
9    uint64_t prod = per_mille != 0 && total > UINT64_MAX / per_mille ? UINT64_MAX : total * per_mille;
10    uint64_t want = prod / 1000 + (prod % 1000 != 0);
11    if (want < 1) want = 1;
12    uint64_t acc = 0;
13    for (size_t i = 0; i < n; i++) {
14        acc += hist[i];
15        if (acc >= want) return (uint32_t)i;
16    }
17    return (uint32_t)n - 1;
18}