From 8d347ef7a0d85a2675eff88672bde2e955b871ae Mon Sep 17 00:00:00 2001 From: giraffedata Date: Sun, 2 Mar 2014 18:47:14 +0000 Subject: Fix arithmetic to avoid array bounds violation git-svn-id: http://svn.code.sf.net/p/netpbm/code/trunk@2148 9d0c8265-081b-0410-96cb-a4ca84ce46f8 --- analyzer/pgmhist.c | 25 +++++++++++++++++-------- 1 file changed, 17 insertions(+), 8 deletions(-) (limited to 'analyzer/pgmhist.c') diff --git a/analyzer/pgmhist.c b/analyzer/pgmhist.c index 9498061e..1e779655 100644 --- a/analyzer/pgmhist.c +++ b/analyzer/pgmhist.c @@ -184,7 +184,7 @@ findQuantiles(unsigned int const n, sample values, given that hist[] is the histogram of them (hist[N] is the number of pixels that have sample value N). - 'mmaxval' is the highest index in hist[] (so its size is 'maxval' + 1, + 'mmaxval' is the highest index in hist[] (so its size is 'mmaxval' + 1, and there are no pixels greater than 'mmaxval' in the image). We return the ith quantile as quantile[i]. For example, for quartiles, @@ -192,6 +192,8 @@ findQuantiles(unsigned int const n, are less than or equal to it. quantile[] must be allocated at least to size 'n'. + + 'n' must not be more than 100. -----------------------------------------------------------------------------*/ unsigned int quantSeq; /* 0 is first quantile, 1 is second quantile, etc. */ @@ -203,18 +205,25 @@ findQuantiles(unsigned int const n, unsigned int cumCt; /* The number of pixels that have sample value 'sampleVal' or less. */ - assert(n > 1); + assert(n > 1 && n <= 100); sampleVal = 0; /* initial value */ cumCt = hist[0]; /* initial value */ for (quantSeq = 1; quantSeq <= n; ++quantSeq) { - double const quantCt = (double)quantSeq/n * totalCt; - /* This is how many pixels are (ignoring quantization) in the - quantile. E.g. for the 3rd quartile, it is 3/4 of the pixels - in the image. - */ - + unsigned long int const q = totalCt / n; + unsigned long int const r = totalCt % n; + unsigned long int const quantCt = q*quantSeq + (r*quantSeq + n - 1)/n; + /* This is how many pixels are (ignoring quantization) in the + quantile. E.g. for the 3rd quartile, it is 3/4 of the pixels + in the image. + + This is equivalent to (float) totalCt * quantSeq / n rounded + upwards. We use the int version in spite of complexities + for preventing overflow for slight innacuracies in floating + point arithmetic causes problems when used as loop counter + and array index. + */ assert(quantCt <= totalCt); /* at sampleVal == mmaxval, cumCt == totalCt, so because -- cgit 1.4.1