X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftally%2Ftally.c;h=4e8876cc4aa5e2874fa83c1b341783e9811d0927;hp=9f2a4591f8c3ce5ddd05b8f29702ff2761784dad;hb=bf7539ac82df33522461561b4940600ae41c6e55;hpb=fdea8abee49e9158275741c210bbb27caf6754fa diff --git a/ccan/tally/tally.c b/ccan/tally/tally.c index 9f2a4591..4e8876cc 100644 --- a/ccan/tally/tally.c +++ b/ccan/tally/tally.c @@ -1,4 +1,4 @@ -#include "config.h" +/* Licensed under LGPLv3+ - see LICENSE file for details */ #include #include #include @@ -7,6 +7,7 @@ #include #include #include +#include #define SIZET_BITS (sizeof(size_t)*CHAR_BIT) @@ -16,34 +17,44 @@ struct tally { size_t total[2]; /* This allows limited frequency analysis. */ unsigned buckets, step_bits; - size_t counts[1 /* [buckets] */ ]; + size_t counts[1 /* Actually: [buckets] */ ]; }; struct tally *tally_new(unsigned buckets) { struct tally *tally; - /* Check for overflow. */ - if (buckets && SIZE_MAX / buckets < sizeof(tally->counts[0])) + /* There is always 1 bucket. */ + if (buckets == 0) { + buckets = 1; + } + + /* Overly cautious check for overflow. */ + if (sizeof(*tally) * buckets / sizeof(*tally) != buckets) { + return NULL; + } + + tally = (struct tally *)malloc( + sizeof(*tally) + sizeof(tally->counts[0])*(buckets-1)); + if (tally == NULL) { return NULL; - tally = malloc(sizeof(*tally) + sizeof(tally->counts[0])*buckets); - if (tally) { - tally->max = ((size_t)1 << (SIZET_BITS - 1)); - tally->min = ~tally->max; - tally->total[0] = tally->total[1] = 0; - /* There is always 1 bucket. */ - tally->buckets = buckets+1; - tally->step_bits = 0; - memset(tally->counts, 0, sizeof(tally->counts[0])*(buckets+1)); } + + tally->max = ((size_t)1 << (SIZET_BITS - 1)); + tally->min = ~tally->max; + tally->total[0] = tally->total[1] = 0; + tally->buckets = buckets; + tally->step_bits = 0; + memset(tally->counts, 0, sizeof(tally->counts[0])*buckets); return tally; } static unsigned bucket_of(ssize_t min, unsigned step_bits, ssize_t val) { /* Don't over-shift. */ - if (step_bits == SIZET_BITS) + if (step_bits == SIZET_BITS) { return 0; + } assert(step_bits < SIZET_BITS); return (size_t)(val - min) >> step_bits; } @@ -52,8 +63,9 @@ static unsigned bucket_of(ssize_t min, unsigned step_bits, ssize_t val) static ssize_t bucket_min(ssize_t min, unsigned step_bits, unsigned b) { /* Don't over-shift. */ - if (step_bits == SIZET_BITS) + if (step_bits == SIZET_BITS) { return min; + } assert(step_bits < SIZET_BITS); return min + ((ssize_t)b << step_bits); } @@ -61,8 +73,9 @@ static ssize_t bucket_min(ssize_t min, unsigned step_bits, unsigned b) /* Does shifting by this many bits truncate the number? */ static bool shift_overflows(size_t num, unsigned bits) { - if (bits == 0) + if (bits == 0) { return false; + } return ((num << bits) >> 1) != (num << (bits - 1)); } @@ -75,8 +88,9 @@ static void renormalize(struct tally *tally, unsigned int i, old_min; /* Uninitialized? Don't do anything... */ - if (tally->max < tally->min) + if (tally->max < tally->min) { goto update; + } /* If we don't have sufficient range, increase step bits until * buckets cover entire range of ssize_t anyway. */ @@ -124,15 +138,17 @@ void tally_add(struct tally *tally, ssize_t val) new_max = val; need_renormalize = true; } - if (need_renormalize) + if (need_renormalize) { renormalize(tally, new_min, new_max); + } /* 128-bit arithmetic! If we didn't want exact mean, we could just * pull it out of counts. */ - if (val > 0 && tally->total[0] + val < tally->total[0]) + if (val > 0 && tally->total[0] + val < tally->total[0]) { tally->total[1]++; - else if (val < 0 && tally->total[0] + val > tally->total[0]) + } else if (val < 0 && tally->total[0] + val > tally->total[0]) { tally->total[1]--; + } tally->total[0] += val; tally->counts[bucket_of(tally->min, tally->step_bits, val)]++; } @@ -140,8 +156,9 @@ void tally_add(struct tally *tally, ssize_t val) size_t tally_num(const struct tally *tally) { size_t i, num = 0; - for (i = 0; i < tally->buckets; i++) + for (i = 0; i < tally->buckets; i++) { num += tally->counts[i]; + } return num; } @@ -166,8 +183,9 @@ static unsigned fls64(uint64_t val) #endif uint64_t r = 64; - if (!val) + if (!val) { return 0; + } if (!(val & 0xffffffff00000000ull)) { val <<= 32; r -= 32; @@ -319,7 +337,7 @@ ssize_t tally_total(const struct tally *tally, ssize_t *overflow) } /* If result is negative, make sure we can represent it. */ - if (tally->total[1] & (1 << (SIZET_BITS-1))) { + if (tally->total[1] & ((size_t)1 << (SIZET_BITS-1))) { /* Must have only underflowed once, and must be able to * represent result at ssize_t. */ if ((~tally->total[1])+1 != 0 @@ -422,7 +440,7 @@ char *tally_histogram(const struct tally *tally, } else { /* We create a temporary then renormalize so < height. */ /* FIXME: Antialias properly! */ - tmp = tally_new(tally->buckets-1); + tmp = tally_new(tally->buckets); if (!tmp) return NULL; tmp->min = tally->min; @@ -445,21 +463,24 @@ char *tally_histogram(const struct tally *tally, largest_bucket = tally->counts[i]; } - p = graph = malloc(height * (width + 1) + 1); + p = graph = (char *)malloc(height * (width + 1) + 1); if (!graph) { free(tmp); return NULL; } for (i = 0; i < height; i++) { - unsigned covered = 1; - count = (double)tally->counts[i] / largest_bucket * (width-1)+1; + unsigned covered = 1, row; + + /* People expect minimum at the bottom. */ + row = height - i - 1; + count = (double)tally->counts[row] / largest_bucket * (width-1)+1; - if (i == 0) + if (row == 0) covered = snprintf(p, width, "%zi", tally->min); - else if (i == height - 1) + else if (row == height - 1) covered = snprintf(p, width, "%zi", tally->max); - else if (i == bucket_of(tally->min, tally->step_bits, 0)) + else if (row == bucket_of(tally->min, tally->step_bits, 0)) *p = '+'; else *p = '|';