1/**
2 * hdr_histogram.c
3 * Written by Michael Barker and released to the public domain,
4 * as explained at http://creativecommons.org/publicdomain/zero/1.0/
5 */
6
7#include <stdlib.h>
8#include <stdbool.h>
9#include <math.h>
10#include <stdio.h>
11#include <string.h>
12#include <stdint.h>
13#include <errno.h>
14#include <inttypes.h>
15
16#include <hdr/hdr_histogram.h>
17#include "hdr_tests.h"
18#include "hdr_atomic.h"
19
20#ifndef HDR_MALLOC_INCLUDE
21#define HDR_MALLOC_INCLUDE "hdr_malloc.h"
22#endif
23
24#include HDR_MALLOC_INCLUDE
25
26/*  ######   #######  ##     ## ##    ## ########  ######  */
27/* ##    ## ##     ## ##     ## ###   ##    ##    ##    ## */
28/* ##       ##     ## ##     ## ####  ##    ##    ##       */
29/* ##       ##     ## ##     ## ## ## ##    ##     ######  */
30/* ##       ##     ## ##     ## ##  ####    ##          ## */
31/* ##    ## ##     ## ##     ## ##   ###    ##    ##    ## */
32/*  ######   #######   #######  ##    ##    ##     ######  */
33
34static int32_t normalize_index(const struct hdr_histogram* h, int32_t index)
35{
36    int32_t normalized_index;
37    int32_t adjustment = 0;
38    if (h->normalizing_index_offset == 0)
39    {
40        return index;
41    }
42
43    normalized_index = index - h->normalizing_index_offset;
44
45    if (normalized_index < 0)
46    {
47        adjustment = h->counts_len;
48    }
49    else if (normalized_index >= h->counts_len)
50    {
51        adjustment = -h->counts_len;
52    }
53
54    return normalized_index + adjustment;
55}
56
57static int64_t counts_get_direct(const struct hdr_histogram* h, int32_t index)
58{
59    return h->counts[index];
60}
61
62static int64_t counts_get_normalised(const struct hdr_histogram* h, int32_t index)
63{
64    return counts_get_direct(h, normalize_index(h, index));
65}
66
67static void counts_inc_normalised(
68    struct hdr_histogram* h, int32_t index, int64_t value)
69{
70    int32_t normalised_index = normalize_index(h, index);
71    h->counts[normalised_index] += value;
72    h->total_count += value;
73}
74
75static void counts_inc_normalised_atomic(
76    struct hdr_histogram* h, int32_t index, int64_t value)
77{
78    int32_t normalised_index = normalize_index(h, index);
79
80    hdr_atomic_add_fetch_64(&h->counts[normalised_index], value);
81    hdr_atomic_add_fetch_64(&h->total_count, value);
82}
83
84static void update_min_max(struct hdr_histogram* h, int64_t value)
85{
86    h->min_value = (value < h->min_value && value != 0) ? value : h->min_value;
87    h->max_value = (value > h->max_value) ? value : h->max_value;
88}
89
90static void update_min_max_atomic(struct hdr_histogram* h, int64_t value)
91{
92    int64_t current_min_value;
93    int64_t current_max_value;
94    do
95    {
96        current_min_value = hdr_atomic_load_64(&h->min_value);
97
98        if (0 == value || current_min_value <= value)
99        {
100            break;
101        }
102    }
103    while (!hdr_atomic_compare_exchange_64(&h->min_value, &current_min_value, value));
104
105    do
106    {
107        current_max_value = hdr_atomic_load_64(&h->max_value);
108
109        if (value <= current_max_value)
110        {
111            break;
112        }
113    }
114    while (!hdr_atomic_compare_exchange_64(&h->max_value, &current_max_value, value));
115}
116
117
118/* ##     ## ######## #### ##       #### ######## ##    ## */
119/* ##     ##    ##     ##  ##        ##     ##     ##  ##  */
120/* ##     ##    ##     ##  ##        ##     ##      ####   */
121/* ##     ##    ##     ##  ##        ##     ##       ##    */
122/* ##     ##    ##     ##  ##        ##     ##       ##    */
123/* ##     ##    ##     ##  ##        ##     ##       ##    */
124/*  #######     ##    #### ######## ####    ##       ##    */
125
126static int64_t power(int64_t base, int64_t exp)
127{
128    int64_t result = 1;
129    while(exp)
130    {
131        result *= base; exp--;
132    }
133    return result;
134}
135
136#if defined(_MSC_VER) && !(defined(__clang__) && (defined(_M_ARM) || defined(_M_ARM64)))
137#   if defined(_WIN64)
138#       pragma intrinsic(_BitScanReverse64)
139#   else
140#       pragma intrinsic(_BitScanReverse)
141#   endif
142#endif
143
144static int32_t count_leading_zeros_64(int64_t value)
145{
146#if defined(_MSC_VER) && !(defined(__clang__) && (defined(_M_ARM) || defined(_M_ARM64)))
147    uint32_t leading_zero = 0;
148#if defined(_WIN64)
149    _BitScanReverse64(&leading_zero, value);
150#else
151    uint32_t high = value >> 32;
152    if  (_BitScanReverse(&leading_zero, high))
153    {
154        leading_zero += 32;
155    }
156    else
157    {
158        uint32_t low = value & 0x00000000FFFFFFFF;
159        _BitScanReverse(&leading_zero, low);
160    }
161#endif
162    return 63 - leading_zero; /* smallest power of 2 containing value */
163#else
164    return __builtin_clzll(value); /* smallest power of 2 containing value */
165#endif
166}
167
168static int32_t get_bucket_index(const struct hdr_histogram* h, int64_t value)
169{
170    int32_t pow2ceiling = 64 - count_leading_zeros_64(value | h->sub_bucket_mask); /* smallest power of 2 containing value */
171    return pow2ceiling - h->unit_magnitude - (h->sub_bucket_half_count_magnitude + 1);
172}
173
174static int32_t get_sub_bucket_index(int64_t value, int32_t bucket_index, int32_t unit_magnitude)
175{
176    return (int32_t)(value >> (bucket_index + unit_magnitude));
177}
178
179static int32_t counts_index(const struct hdr_histogram* h, int32_t bucket_index, int32_t sub_bucket_index)
180{
181    /* Calculate the index for the first entry in the bucket: */
182    /* (The following is the equivalent of ((bucket_index + 1) * subBucketHalfCount) ): */
183    int32_t bucket_base_index = (bucket_index + 1) << h->sub_bucket_half_count_magnitude;
184    /* Calculate the offset in the bucket: */
185    int32_t offset_in_bucket = sub_bucket_index - h->sub_bucket_half_count;
186    /* The following is the equivalent of ((sub_bucket_index  - subBucketHalfCount) + bucketBaseIndex; */
187    return bucket_base_index + offset_in_bucket;
188}
189
190static int64_t value_from_index(int32_t bucket_index, int32_t sub_bucket_index, int32_t unit_magnitude)
191{
192    return ((int64_t) sub_bucket_index) << (bucket_index + unit_magnitude);
193}
194
195int32_t counts_index_for(const struct hdr_histogram* h, int64_t value)
196{
197    int32_t bucket_index     = get_bucket_index(h, value);
198    int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude);
199
200    return counts_index(h, bucket_index, sub_bucket_index);
201}
202
203int64_t hdr_value_at_index(const struct hdr_histogram *h, int32_t index)
204{
205    int32_t bucket_index = (index >> h->sub_bucket_half_count_magnitude) - 1;
206    int32_t sub_bucket_index = (index & (h->sub_bucket_half_count - 1)) + h->sub_bucket_half_count;
207
208    if (bucket_index < 0)
209    {
210        sub_bucket_index -= h->sub_bucket_half_count;
211        bucket_index = 0;
212    }
213
214    return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude);
215}
216
217int64_t hdr_size_of_equivalent_value_range(const struct hdr_histogram* h, int64_t value)
218{
219    int32_t bucket_index     = get_bucket_index(h, value);
220    int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude);
221    int32_t adjusted_bucket  = (sub_bucket_index >= h->sub_bucket_count) ? (bucket_index + 1) : bucket_index;
222    return INT64_C(1) << (h->unit_magnitude + adjusted_bucket);
223}
224
225static int64_t size_of_equivalent_value_range_given_bucket_indices(
226    const struct hdr_histogram *h,
227    int32_t bucket_index,
228    int32_t sub_bucket_index)
229{
230    const int32_t adjusted_bucket  = (sub_bucket_index >= h->sub_bucket_count) ? (bucket_index + 1) : bucket_index;
231    return INT64_C(1) << (h->unit_magnitude + adjusted_bucket);
232}
233
234static int64_t lowest_equivalent_value(const struct hdr_histogram* h, int64_t value)
235{
236    int32_t bucket_index     = get_bucket_index(h, value);
237    int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude);
238    return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude);
239}
240
241static int64_t lowest_equivalent_value_given_bucket_indices(
242    const struct hdr_histogram *h,
243    int32_t bucket_index,
244    int32_t sub_bucket_index)
245{
246    return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude);
247}
248
249int64_t hdr_next_non_equivalent_value(const struct hdr_histogram *h, int64_t value)
250{
251    return lowest_equivalent_value(h, value) + hdr_size_of_equivalent_value_range(h, value);
252}
253
254static int64_t highest_equivalent_value(const struct hdr_histogram* h, int64_t value)
255{
256    return hdr_next_non_equivalent_value(h, value) - 1;
257}
258
259int64_t hdr_median_equivalent_value(const struct hdr_histogram *h, int64_t value)
260{
261    return lowest_equivalent_value(h, value) + (hdr_size_of_equivalent_value_range(h, value) >> 1);
262}
263
264static int64_t non_zero_min(const struct hdr_histogram* h)
265{
266    if (INT64_MAX == h->min_value)
267    {
268        return INT64_MAX;
269    }
270
271    return lowest_equivalent_value(h, h->min_value);
272}
273
274void hdr_reset_internal_counters(struct hdr_histogram* h)
275{
276    int min_non_zero_index = -1;
277    int max_index = -1;
278    int64_t observed_total_count = 0;
279    int i;
280
281    for (i = 0; i < h->counts_len; i++)
282    {
283        int64_t count_at_index;
284
285        if ((count_at_index = counts_get_direct(h, i)) > 0)
286        {
287            observed_total_count += count_at_index;
288            max_index = i;
289            if (min_non_zero_index == -1 && i != 0)
290            {
291                min_non_zero_index = i;
292            }
293        }
294    }
295
296    if (max_index == -1)
297    {
298        h->max_value = 0;
299    }
300    else
301    {
302        int64_t max_value = hdr_value_at_index(h, max_index);
303        h->max_value = highest_equivalent_value(h, max_value);
304    }
305
306    if (min_non_zero_index == -1)
307    {
308        h->min_value = INT64_MAX;
309    }
310    else
311    {
312        h->min_value = hdr_value_at_index(h, min_non_zero_index);
313    }
314
315    h->total_count = observed_total_count;
316}
317
318static int32_t buckets_needed_to_cover_value(int64_t value, int32_t sub_bucket_count, int32_t unit_magnitude)
319{
320    int64_t smallest_untrackable_value = ((int64_t) sub_bucket_count) << unit_magnitude;
321    int32_t buckets_needed = 1;
322    while (smallest_untrackable_value <= value)
323    {
324        if (smallest_untrackable_value > INT64_MAX / 2)
325        {
326            return buckets_needed + 1;
327        }
328        smallest_untrackable_value <<= 1;
329        buckets_needed++;
330    }
331
332    return buckets_needed;
333}
334
335/* ##     ## ######## ##     ##  #######  ########  ##    ## */
336/* ###   ### ##       ###   ### ##     ## ##     ##  ##  ##  */
337/* #### #### ##       #### #### ##     ## ##     ##   ####   */
338/* ## ### ## ######   ## ### ## ##     ## ########     ##    */
339/* ##     ## ##       ##     ## ##     ## ##   ##      ##    */
340/* ##     ## ##       ##     ## ##     ## ##    ##     ##    */
341/* ##     ## ######## ##     ##  #######  ##     ##    ##    */
342
343int hdr_calculate_bucket_config(
344        int64_t lowest_discernible_value,
345        int64_t highest_trackable_value,
346        int significant_figures,
347        struct hdr_histogram_bucket_config* cfg)
348{
349    int32_t sub_bucket_count_magnitude;
350    int64_t largest_value_with_single_unit_resolution;
351
352    if (lowest_discernible_value < 1 ||
353            significant_figures < 1 || 5 < significant_figures ||
354            lowest_discernible_value * 2 > highest_trackable_value)
355    {
356        return EINVAL;
357    }
358
359    cfg->lowest_discernible_value = lowest_discernible_value;
360    cfg->significant_figures = significant_figures;
361    cfg->highest_trackable_value = highest_trackable_value;
362
363    largest_value_with_single_unit_resolution = 2 * power(10, significant_figures);
364    sub_bucket_count_magnitude = (int32_t) ceil(log((double)largest_value_with_single_unit_resolution) / log(2));
365    cfg->sub_bucket_half_count_magnitude = ((sub_bucket_count_magnitude > 1) ? sub_bucket_count_magnitude : 1) - 1;
366
367    double unit_magnitude = log((double)lowest_discernible_value) / log(2);
368    if (INT32_MAX < unit_magnitude)
369    {
370        return EINVAL;
371    }
372
373    cfg->unit_magnitude = (int32_t) unit_magnitude;
374    cfg->sub_bucket_count      = (int32_t) pow(2, (cfg->sub_bucket_half_count_magnitude + 1));
375    cfg->sub_bucket_half_count = cfg->sub_bucket_count / 2;
376    cfg->sub_bucket_mask       = ((int64_t) cfg->sub_bucket_count - 1) << cfg->unit_magnitude;
377
378    if (cfg->unit_magnitude + cfg->sub_bucket_half_count_magnitude > 61)
379    {
380        return EINVAL;
381    }
382
383    cfg->bucket_count = buckets_needed_to_cover_value(highest_trackable_value, cfg->sub_bucket_count, (int32_t)cfg->unit_magnitude);
384    cfg->counts_len = (cfg->bucket_count + 1) * (cfg->sub_bucket_count / 2);
385
386    return 0;
387}
388
389void hdr_init_preallocated(struct hdr_histogram* h, struct hdr_histogram_bucket_config* cfg)
390{
391    h->lowest_discernible_value        = cfg->lowest_discernible_value;
392    h->highest_trackable_value         = cfg->highest_trackable_value;
393    h->unit_magnitude                  = (int32_t)cfg->unit_magnitude;
394    h->significant_figures             = (int32_t)cfg->significant_figures;
395    h->sub_bucket_half_count_magnitude = cfg->sub_bucket_half_count_magnitude;
396    h->sub_bucket_half_count           = cfg->sub_bucket_half_count;
397    h->sub_bucket_mask                 = cfg->sub_bucket_mask;
398    h->sub_bucket_count                = cfg->sub_bucket_count;
399    h->min_value                       = INT64_MAX;
400    h->max_value                       = 0;
401    h->normalizing_index_offset        = 0;
402    h->conversion_ratio                = 1.0;
403    h->bucket_count                    = cfg->bucket_count;
404    h->counts_len                      = cfg->counts_len;
405    h->total_count                     = 0;
406}
407
408int hdr_init(
409        int64_t lowest_discernible_value,
410        int64_t highest_trackable_value,
411        int significant_figures,
412        struct hdr_histogram** result)
413{
414    int64_t* counts;
415    struct hdr_histogram_bucket_config cfg;
416    struct hdr_histogram* histogram;
417
418    int r = hdr_calculate_bucket_config(lowest_discernible_value, highest_trackable_value, significant_figures, &cfg);
419    if (r)
420    {
421        return r;
422    }
423
424    counts = (int64_t*) hdr_calloc((size_t) cfg.counts_len, sizeof(int64_t));
425    if (!counts)
426    {
427        return ENOMEM;
428    }
429
430    histogram = (struct hdr_histogram*) hdr_calloc(1, sizeof(struct hdr_histogram));
431    if (!histogram)
432    {
433        hdr_free(counts);
434        return ENOMEM;
435    }
436
437    histogram->counts = counts;
438
439    hdr_init_preallocated(histogram, &cfg);
440    *result = histogram;
441
442    return 0;
443}
444
445void hdr_close(struct hdr_histogram* h)
446{
447    if (h) {
448	hdr_free(h->counts);
449	hdr_free(h);
450    }
451}
452
453int hdr_alloc(int64_t highest_trackable_value, int significant_figures, struct hdr_histogram** result)
454{
455    return hdr_init(1, highest_trackable_value, significant_figures, result);
456}
457
458/* reset a histogram to zero. */
459void hdr_reset(struct hdr_histogram *h)
460{
461     h->total_count=0;
462     h->min_value = INT64_MAX;
463     h->max_value = 0;
464     memset(h->counts, 0, (sizeof(int64_t) * h->counts_len));
465}
466
467size_t hdr_get_memory_size(struct hdr_histogram *h)
468{
469    return sizeof(struct hdr_histogram) + h->counts_len * sizeof(int64_t);
470}
471
472/* ##     ## ########  ########     ###    ######## ########  ######  */
473/* ##     ## ##     ## ##     ##   ## ##      ##    ##       ##    ## */
474/* ##     ## ##     ## ##     ##  ##   ##     ##    ##       ##       */
475/* ##     ## ########  ##     ## ##     ##    ##    ######    ######  */
476/* ##     ## ##        ##     ## #########    ##    ##             ## */
477/* ##     ## ##        ##     ## ##     ##    ##    ##       ##    ## */
478/*  #######  ##        ########  ##     ##    ##    ########  ######  */
479
480
481bool hdr_record_value(struct hdr_histogram* h, int64_t value)
482{
483    return hdr_record_values(h, value, 1);
484}
485
486bool hdr_record_value_atomic(struct hdr_histogram* h, int64_t value)
487{
488    return hdr_record_values_atomic(h, value, 1);
489}
490
491bool hdr_record_values(struct hdr_histogram* h, int64_t value, int64_t count)
492{
493    int32_t counts_index;
494
495    if (value < 0)
496    {
497        return false;
498    }
499
500    counts_index = counts_index_for(h, value);
501
502    if (counts_index < 0 || h->counts_len <= counts_index)
503    {
504        return false;
505    }
506
507    counts_inc_normalised(h, counts_index, count);
508    update_min_max(h, value);
509
510    return true;
511}
512
513bool hdr_record_values_atomic(struct hdr_histogram* h, int64_t value, int64_t count)
514{
515    int32_t counts_index;
516
517    if (value < 0)
518    {
519        return false;
520    }
521
522    counts_index = counts_index_for(h, value);
523
524    if (counts_index < 0 || h->counts_len <= counts_index)
525    {
526        return false;
527    }
528
529    counts_inc_normalised_atomic(h, counts_index, count);
530    update_min_max_atomic(h, value);
531
532    return true;
533}
534
535bool hdr_record_corrected_value(struct hdr_histogram* h, int64_t value, int64_t expected_interval)
536{
537    return hdr_record_corrected_values(h, value, 1, expected_interval);
538}
539
540bool hdr_record_corrected_value_atomic(struct hdr_histogram* h, int64_t value, int64_t expected_interval)
541{
542    return hdr_record_corrected_values_atomic(h, value, 1, expected_interval);
543}
544
545bool hdr_record_corrected_values(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval)
546{
547    int64_t missing_value;
548
549    if (!hdr_record_values(h, value, count))
550    {
551        return false;
552    }
553
554    if (expected_interval <= 0 || value <= expected_interval)
555    {
556        return true;
557    }
558
559    missing_value = value - expected_interval;
560    for (; missing_value >= expected_interval; missing_value -= expected_interval)
561    {
562        if (!hdr_record_values(h, missing_value, count))
563        {
564            return false;
565        }
566    }
567
568    return true;
569}
570
571bool hdr_record_corrected_values_atomic(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval)
572{
573    int64_t missing_value;
574
575    if (!hdr_record_values_atomic(h, value, count))
576    {
577        return false;
578    }
579
580    if (expected_interval <= 0 || value <= expected_interval)
581    {
582        return true;
583    }
584
585    missing_value = value - expected_interval;
586    for (; missing_value >= expected_interval; missing_value -= expected_interval)
587    {
588        if (!hdr_record_values_atomic(h, missing_value, count))
589        {
590            return false;
591        }
592    }
593
594    return true;
595}
596
597int64_t hdr_add(struct hdr_histogram* h, const struct hdr_histogram* from)
598{
599    struct hdr_iter iter;
600    int64_t dropped = 0;
601    hdr_iter_recorded_init(&iter, from);
602
603    while (hdr_iter_next(&iter))
604    {
605        int64_t value = iter.value;
606        int64_t count = iter.count;
607
608        if (!hdr_record_values(h, value, count))
609        {
610            dropped += count;
611        }
612    }
613
614    return dropped;
615}
616
617int64_t hdr_add_while_correcting_for_coordinated_omission(
618        struct hdr_histogram* h, struct hdr_histogram* from, int64_t expected_interval)
619{
620    struct hdr_iter iter;
621    int64_t dropped = 0;
622    hdr_iter_recorded_init(&iter, from);
623
624    while (hdr_iter_next(&iter))
625    {
626        int64_t value = iter.value;
627        int64_t count = iter.count;
628
629        if (!hdr_record_corrected_values(h, value, count, expected_interval))
630        {
631            dropped += count;
632        }
633    }
634
635    return dropped;
636}
637
638
639
640/* ##     ##    ###    ##       ##     ## ########  ######  */
641/* ##     ##   ## ##   ##       ##     ## ##       ##    ## */
642/* ##     ##  ##   ##  ##       ##     ## ##       ##       */
643/* ##     ## ##     ## ##       ##     ## ######    ######  */
644/*  ##   ##  ######### ##       ##     ## ##             ## */
645/*   ## ##   ##     ## ##       ##     ## ##       ##    ## */
646/*    ###    ##     ## ########  #######  ########  ######  */
647
648
649int64_t hdr_max(const struct hdr_histogram* h)
650{
651    if (0 == h->max_value)
652    {
653        return 0;
654    }
655
656    return highest_equivalent_value(h, h->max_value);
657}
658
659int64_t hdr_min(const struct hdr_histogram* h)
660{
661    if (0 < hdr_count_at_index(h, 0))
662    {
663        return 0;
664    }
665
666    return non_zero_min(h);
667}
668
669static int64_t get_value_from_idx_up_to_count(const struct hdr_histogram* h, int64_t count_at_percentile)
670{
671    int64_t count_to_idx = 0;
672
673    count_at_percentile = 0 < count_at_percentile ? count_at_percentile : 1;
674    for (int32_t idx = 0; idx < h->counts_len; idx++)
675    {
676        count_to_idx += h->counts[idx];
677        if (count_to_idx >= count_at_percentile)
678        {
679            return hdr_value_at_index(h, idx);
680        }
681    }
682
683    return 0;
684}
685
686
687int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile)
688{
689    double requested_percentile = percentile < 100.0 ? percentile : 100.0;
690    int64_t count_at_percentile =
691        (int64_t) (((requested_percentile / 100) * h->total_count) + 0.5);
692    int64_t value_from_idx = get_value_from_idx_up_to_count(h, count_at_percentile);
693    if (percentile == 0.0)
694    {
695        return lowest_equivalent_value(h, value_from_idx);
696    }
697    return highest_equivalent_value(h, value_from_idx);
698}
699
700int hdr_value_at_percentiles(const struct hdr_histogram *h, const double *percentiles, int64_t *values, size_t length)
701{
702    if (NULL == percentiles || NULL == values)
703    {
704        return EINVAL;
705    }
706
707    struct hdr_iter iter;
708    const int64_t total_count = h->total_count;
709    // to avoid allocations we use the values array for intermediate computation
710    // i.e. to store the expected cumulative count at each percentile
711    for (size_t i = 0; i < length; i++)
712    {
713        const double requested_percentile = percentiles[i] < 100.0 ? percentiles[i] : 100.0;
714        const int64_t count_at_percentile =
715        (int64_t) (((requested_percentile / 100) * total_count) + 0.5);
716        values[i] = count_at_percentile > 1 ? count_at_percentile : 1;
717    }
718
719    hdr_iter_init(&iter, h);
720    int64_t total = 0;
721    size_t at_pos = 0;
722    while (hdr_iter_next(&iter) && at_pos < length)
723    {
724        total += iter.count;
725        while (at_pos < length && total >= values[at_pos])
726        {
727            values[at_pos] = highest_equivalent_value(h, iter.value);
728            at_pos++;
729        }
730    }
731    return 0;
732}
733
734double hdr_mean(const struct hdr_histogram* h)
735{
736    struct hdr_iter iter;
737    int64_t total = 0, count = 0;
738    int64_t total_count = h->total_count;
739
740    hdr_iter_init(&iter, h);
741
742    while (hdr_iter_next(&iter) && count < total_count)
743    {
744        if (0 != iter.count)
745        {
746            count += iter.count;
747            total += iter.count * hdr_median_equivalent_value(h, iter.value);
748        }
749    }
750
751    return (total * 1.0) / total_count;
752}
753
754double hdr_stddev(const struct hdr_histogram* h)
755{
756    double mean = hdr_mean(h);
757    double geometric_dev_total = 0.0;
758
759    struct hdr_iter iter;
760    hdr_iter_init(&iter, h);
761
762    while (hdr_iter_next(&iter))
763    {
764        if (0 != iter.count)
765        {
766            double dev = (hdr_median_equivalent_value(h, iter.value) * 1.0) - mean;
767            geometric_dev_total += (dev * dev) * iter.count;
768        }
769    }
770
771    return sqrt(geometric_dev_total / h->total_count);
772}
773
774bool hdr_values_are_equivalent(const struct hdr_histogram* h, int64_t a, int64_t b)
775{
776    return lowest_equivalent_value(h, a) == lowest_equivalent_value(h, b);
777}
778
779int64_t hdr_lowest_equivalent_value(const struct hdr_histogram* h, int64_t value)
780{
781    return lowest_equivalent_value(h, value);
782}
783
784int64_t hdr_count_at_value(const struct hdr_histogram* h, int64_t value)
785{
786    return counts_get_normalised(h, counts_index_for(h, value));
787}
788
789int64_t hdr_count_at_index(const struct hdr_histogram* h, int32_t index)
790{
791    return counts_get_normalised(h, index);
792}
793
794
795/* #### ######## ######## ########     ###    ########  #######  ########   ######  */
796/*  ##     ##    ##       ##     ##   ## ##      ##    ##     ## ##     ## ##    ## */
797/*  ##     ##    ##       ##     ##  ##   ##     ##    ##     ## ##     ## ##       */
798/*  ##     ##    ######   ########  ##     ##    ##    ##     ## ########   ######  */
799/*  ##     ##    ##       ##   ##   #########    ##    ##     ## ##   ##         ## */
800/*  ##     ##    ##       ##    ##  ##     ##    ##    ##     ## ##    ##  ##    ## */
801/* ####    ##    ######## ##     ## ##     ##    ##     #######  ##     ##  ######  */
802
803
804static bool has_buckets(struct hdr_iter* iter)
805{
806    return iter->counts_index < iter->h->counts_len;
807}
808
809static bool has_next(struct hdr_iter* iter)
810{
811    return iter->cumulative_count < iter->total_count;
812}
813
814static bool move_next(struct hdr_iter* iter)
815{
816    iter->counts_index++;
817
818    if (!has_buckets(iter))
819    {
820        return false;
821    }
822
823    iter->count = counts_get_normalised(iter->h, iter->counts_index);
824    iter->cumulative_count += iter->count;
825    const int64_t value = hdr_value_at_index(iter->h, iter->counts_index);
826    const int32_t bucket_index = get_bucket_index(iter->h, value);
827    const int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, iter->h->unit_magnitude);
828    const int64_t leq = lowest_equivalent_value_given_bucket_indices(iter->h, bucket_index, sub_bucket_index);
829    const int64_t size_of_equivalent_value_range = size_of_equivalent_value_range_given_bucket_indices(
830        iter->h, bucket_index, sub_bucket_index);
831    iter->lowest_equivalent_value = leq;
832    iter->value = value;
833    iter->highest_equivalent_value = leq + size_of_equivalent_value_range - 1;
834    iter->median_equivalent_value = leq + (size_of_equivalent_value_range >> 1);
835
836    return true;
837}
838
839static int64_t peek_next_value_from_index(struct hdr_iter* iter)
840{
841    return hdr_value_at_index(iter->h, iter->counts_index + 1);
842}
843
844static bool next_value_greater_than_reporting_level_upper_bound(
845    struct hdr_iter *iter, int64_t reporting_level_upper_bound)
846{
847    if (iter->counts_index >= iter->h->counts_len)
848    {
849        return false;
850    }
851
852    return peek_next_value_from_index(iter) > reporting_level_upper_bound;
853}
854
855static bool basic_iter_next(struct hdr_iter *iter)
856{
857    if (!has_next(iter) || iter->counts_index >= iter->h->counts_len)
858    {
859        return false;
860    }
861
862    move_next(iter);
863
864    return true;
865}
866
867static void update_iterated_values(struct hdr_iter* iter, int64_t new_value_iterated_to)
868{
869    iter->value_iterated_from = iter->value_iterated_to;
870    iter->value_iterated_to = new_value_iterated_to;
871}
872
873static bool all_values_iter_next(struct hdr_iter* iter)
874{
875    bool result = move_next(iter);
876
877    if (result)
878    {
879        update_iterated_values(iter, iter->value);
880    }
881
882    return result;
883}
884
885void hdr_iter_init(struct hdr_iter* iter, const struct hdr_histogram* h)
886{
887    iter->h = h;
888
889    iter->counts_index = -1;
890    iter->total_count = h->total_count;
891    iter->count = 0;
892    iter->cumulative_count = 0;
893    iter->value = 0;
894    iter->highest_equivalent_value = 0;
895    iter->value_iterated_from = 0;
896    iter->value_iterated_to = 0;
897
898    iter->_next_fp = all_values_iter_next;
899}
900
901bool hdr_iter_next(struct hdr_iter* iter)
902{
903    return iter->_next_fp(iter);
904}
905
906/* ########  ######## ########   ######  ######## ##    ## ######## #### ##       ########  ######  */
907/* ##     ## ##       ##     ## ##    ## ##       ###   ##    ##     ##  ##       ##       ##    ## */
908/* ##     ## ##       ##     ## ##       ##       ####  ##    ##     ##  ##       ##       ##       */
909/* ########  ######   ########  ##       ######   ## ## ##    ##     ##  ##       ######    ######  */
910/* ##        ##       ##   ##   ##       ##       ##  ####    ##     ##  ##       ##             ## */
911/* ##        ##       ##    ##  ##    ## ##       ##   ###    ##     ##  ##       ##       ##    ## */
912/* ##        ######## ##     ##  ######  ######## ##    ##    ##    #### ######## ########  ######  */
913
914static bool percentile_iter_next(struct hdr_iter* iter)
915{
916    int64_t temp, half_distance, percentile_reporting_ticks;
917
918    struct hdr_iter_percentiles* percentiles = &iter->specifics.percentiles;
919
920    if (!has_next(iter))
921    {
922        if (percentiles->seen_last_value)
923        {
924            return false;
925        }
926
927        percentiles->seen_last_value = true;
928        percentiles->percentile = 100.0;
929
930        return true;
931    }
932
933    if (iter->counts_index == -1 && !basic_iter_next(iter))
934    {
935        return false;
936    }
937
938    do
939    {
940        double current_percentile = (100.0 * (double) iter->cumulative_count) / iter->h->total_count;
941        if (iter->count != 0 &&
942                percentiles->percentile_to_iterate_to <= current_percentile)
943        {
944            update_iterated_values(iter, highest_equivalent_value(iter->h, iter->value));
945
946            percentiles->percentile = percentiles->percentile_to_iterate_to;
947            temp = (int64_t)(log(100 / (100.0 - (percentiles->percentile_to_iterate_to))) / log(2)) + 1;
948            half_distance = (int64_t) pow(2, (double) temp);
949            percentile_reporting_ticks = percentiles->ticks_per_half_distance * half_distance;
950            percentiles->percentile_to_iterate_to += 100.0 / percentile_reporting_ticks;
951
952            return true;
953        }
954    }
955    while (basic_iter_next(iter));
956
957    return true;
958}
959
960void hdr_iter_percentile_init(struct hdr_iter* iter, const struct hdr_histogram* h, int32_t ticks_per_half_distance)
961{
962    iter->h = h;
963
964    hdr_iter_init(iter, h);
965
966    iter->specifics.percentiles.seen_last_value          = false;
967    iter->specifics.percentiles.ticks_per_half_distance  = ticks_per_half_distance;
968    iter->specifics.percentiles.percentile_to_iterate_to = 0.0;
969    iter->specifics.percentiles.percentile               = 0.0;
970
971    iter->_next_fp = percentile_iter_next;
972}
973
974static void format_line_string(char* str, size_t len, int significant_figures, format_type format)
975{
976#if defined(_MSC_VER)
977#define snprintf _snprintf
978#pragma warning(push)
979#pragma warning(disable: 4996)
980#endif
981    const char* format_str = "%s%d%s";
982
983    switch (format)
984    {
985        case CSV:
986            snprintf(str, len, format_str, "%.", significant_figures, "f,%f,%d,%.2f\n");
987            break;
988        case CLASSIC:
989            snprintf(str, len, format_str, "%12.", significant_figures, "f %12f %12d %12.2f\n");
990            break;
991        default:
992            snprintf(str, len, format_str, "%12.", significant_figures, "f %12f %12d %12.2f\n");
993    }
994#if defined(_MSC_VER)
995#undef snprintf
996#pragma warning(pop)
997#endif
998}
999
1000
1001/* ########  ########  ######   #######  ########  ########  ######## ########   */
1002/* ##     ## ##       ##    ## ##     ## ##     ## ##     ## ##       ##     ##  */
1003/* ##     ## ##       ##       ##     ## ##     ## ##     ## ##       ##     ##  */
1004/* ########  ######   ##       ##     ## ########  ##     ## ######   ##     ##  */
1005/* ##   ##   ##       ##       ##     ## ##   ##   ##     ## ##       ##     ##  */
1006/* ##    ##  ##       ##    ## ##     ## ##    ##  ##     ## ##       ##     ##  */
1007/* ##     ## ########  ######   #######  ##     ## ########  ######## ########   */
1008
1009
1010static bool recorded_iter_next(struct hdr_iter* iter)
1011{
1012    while (basic_iter_next(iter))
1013    {
1014        if (iter->count != 0)
1015        {
1016            update_iterated_values(iter, iter->value);
1017
1018            iter->specifics.recorded.count_added_in_this_iteration_step = iter->count;
1019            return true;
1020        }
1021    }
1022
1023    return false;
1024}
1025
1026void hdr_iter_recorded_init(struct hdr_iter* iter, const struct hdr_histogram* h)
1027{
1028    hdr_iter_init(iter, h);
1029
1030    iter->specifics.recorded.count_added_in_this_iteration_step = 0;
1031
1032    iter->_next_fp = recorded_iter_next;
1033}
1034
1035/* ##       #### ##    ## ########    ###    ########  */
1036/* ##        ##  ###   ## ##         ## ##   ##     ## */
1037/* ##        ##  ####  ## ##        ##   ##  ##     ## */
1038/* ##        ##  ## ## ## ######   ##     ## ########  */
1039/* ##        ##  ##  #### ##       ######### ##   ##   */
1040/* ##        ##  ##   ### ##       ##     ## ##    ##  */
1041/* ######## #### ##    ## ######## ##     ## ##     ## */
1042
1043
1044static bool iter_linear_next(struct hdr_iter* iter)
1045{
1046    struct hdr_iter_linear* linear = &iter->specifics.linear;
1047
1048    linear->count_added_in_this_iteration_step = 0;
1049
1050    if (has_next(iter) ||
1051        next_value_greater_than_reporting_level_upper_bound(
1052            iter, linear->next_value_reporting_level_lowest_equivalent))
1053    {
1054        do
1055        {
1056            if (iter->value >= linear->next_value_reporting_level_lowest_equivalent)
1057            {
1058                update_iterated_values(iter, linear->next_value_reporting_level);
1059
1060                linear->next_value_reporting_level += linear->value_units_per_bucket;
1061                linear->next_value_reporting_level_lowest_equivalent =
1062                    lowest_equivalent_value(iter->h, linear->next_value_reporting_level);
1063
1064                return true;
1065            }
1066
1067            if (!move_next(iter))
1068            {
1069                return true;
1070            }
1071
1072            linear->count_added_in_this_iteration_step += iter->count;
1073        }
1074        while (true);
1075    }
1076
1077    return false;
1078}
1079
1080
1081void hdr_iter_linear_init(struct hdr_iter* iter, const struct hdr_histogram* h, int64_t value_units_per_bucket)
1082{
1083    hdr_iter_init(iter, h);
1084
1085    iter->specifics.linear.count_added_in_this_iteration_step = 0;
1086    iter->specifics.linear.value_units_per_bucket = value_units_per_bucket;
1087    iter->specifics.linear.next_value_reporting_level = value_units_per_bucket;
1088    iter->specifics.linear.next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(h, value_units_per_bucket);
1089
1090    iter->_next_fp = iter_linear_next;
1091}
1092
1093/* ##        #######   ######      ###    ########  #### ######## ##     ## ##     ## ####  ######  */
1094/* ##       ##     ## ##    ##    ## ##   ##     ##  ##     ##    ##     ## ###   ###  ##  ##    ## */
1095/* ##       ##     ## ##         ##   ##  ##     ##  ##     ##    ##     ## #### ####  ##  ##       */
1096/* ##       ##     ## ##   #### ##     ## ########   ##     ##    ######### ## ### ##  ##  ##       */
1097/* ##       ##     ## ##    ##  ######### ##   ##    ##     ##    ##     ## ##     ##  ##  ##       */
1098/* ##       ##     ## ##    ##  ##     ## ##    ##   ##     ##    ##     ## ##     ##  ##  ##    ## */
1099/* ########  #######   ######   ##     ## ##     ## ####    ##    ##     ## ##     ## ####  ######  */
1100
1101static bool log_iter_next(struct hdr_iter *iter)
1102{
1103    struct hdr_iter_log* logarithmic = &iter->specifics.log;
1104
1105    logarithmic->count_added_in_this_iteration_step = 0;
1106
1107    if (has_next(iter) ||
1108        next_value_greater_than_reporting_level_upper_bound(
1109            iter, logarithmic->next_value_reporting_level_lowest_equivalent))
1110    {
1111        do
1112        {
1113            if (iter->value >= logarithmic->next_value_reporting_level_lowest_equivalent)
1114            {
1115                update_iterated_values(iter, logarithmic->next_value_reporting_level);
1116
1117                logarithmic->next_value_reporting_level *= (int64_t)logarithmic->log_base;
1118                logarithmic->next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(iter->h, logarithmic->next_value_reporting_level);
1119
1120                return true;
1121            }
1122
1123            if (!move_next(iter))
1124            {
1125                return true;
1126            }
1127
1128            logarithmic->count_added_in_this_iteration_step += iter->count;
1129        }
1130        while (true);
1131    }
1132
1133    return false;
1134}
1135
1136void hdr_iter_log_init(
1137        struct hdr_iter* iter,
1138        const struct hdr_histogram* h,
1139        int64_t value_units_first_bucket,
1140        double log_base)
1141{
1142    hdr_iter_init(iter, h);
1143    iter->specifics.log.count_added_in_this_iteration_step = 0;
1144    iter->specifics.log.log_base = log_base;
1145    iter->specifics.log.next_value_reporting_level = value_units_first_bucket;
1146    iter->specifics.log.next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(h, value_units_first_bucket);
1147
1148    iter->_next_fp = log_iter_next;
1149}
1150
1151/* Printing. */
1152
1153static const char* format_head_string(format_type format)
1154{
1155    switch (format)
1156    {
1157        case CSV:
1158            return "%s,%s,%s,%s\n";
1159        case CLASSIC:
1160        default:
1161            return "%12s %12s %12s %12s\n\n";
1162    }
1163}
1164
1165static const char CLASSIC_FOOTER[] =
1166    "#[Mean    = %12.3f, StdDeviation   = %12.3f]\n"
1167    "#[Max     = %12.3f, Total count    = %12" PRIu64 "]\n"
1168    "#[Buckets = %12d, SubBuckets     = %12d]\n";
1169
1170int hdr_percentiles_print(
1171        struct hdr_histogram* h, FILE* stream, int32_t ticks_per_half_distance,
1172        double value_scale, format_type format)
1173{
1174    char line_format[25];
1175    const char* head_format;
1176    int rc = 0;
1177    struct hdr_iter iter;
1178    struct hdr_iter_percentiles * percentiles;
1179
1180    format_line_string(line_format, 25, h->significant_figures, format);
1181    head_format = format_head_string(format);
1182
1183    hdr_iter_percentile_init(&iter, h, ticks_per_half_distance);
1184
1185    if (fprintf(
1186            stream, head_format,
1187            "Value", "Percentile", "TotalCount", "1/(1-Percentile)") < 0)
1188    {
1189        rc = EIO;
1190        goto cleanup;
1191    }
1192
1193    percentiles = &iter.specifics.percentiles;
1194    while (hdr_iter_next(&iter))
1195    {
1196        double  value               = iter.highest_equivalent_value / value_scale;
1197        double  percentile          = percentiles->percentile / 100.0;
1198        int64_t total_count         = iter.cumulative_count;
1199        double  inverted_percentile = (1.0 / (1.0 - percentile));
1200
1201        if (fprintf(
1202                stream, line_format, value, percentile, total_count, inverted_percentile) < 0)
1203        {
1204            rc = EIO;
1205            goto cleanup;
1206        }
1207    }
1208
1209    if (CLASSIC == format)
1210    {
1211        double mean   = hdr_mean(h)   / value_scale;
1212        double stddev = hdr_stddev(h) / value_scale;
1213        double max    = hdr_max(h)    / value_scale;
1214
1215        if (fprintf(
1216                stream, CLASSIC_FOOTER,  mean, stddev, max,
1217                h->total_count, h->bucket_count, h->sub_bucket_count) < 0)
1218        {
1219            rc = EIO;
1220            goto cleanup;
1221        }
1222    }
1223
1224    cleanup:
1225    return rc;
1226}
1227