BUG/MINOR: intops: fix mul32hi()'s off-by-one
authorWilly Tarreau <w@1wt.eu>
Tue, 9 Feb 2021 16:10:54 +0000 (17:10 +0100)
committerChristopher Faulet <cfaulet@haproxy.com>
Mon, 22 Feb 2021 09:23:24 +0000 (10:23 +0100)
commit84dd97d11bc7b456f0161df71922ae1c5eaa376c
treec8ef4c68f42b9d1e7a951687df2cc4c1d54e0f7c
parentbcc2560333982f990b01b6ce537f7d88aa3c5c3f
BUG/MINOR: intops: fix mul32hi()'s off-by-one

mul32hi() multiples a constant a with a variable b from 0 to 0xffffffff
and shifts the result by 32 bits. It's visible that it's always impossible
to reach the constant a this way because the product always misses exactly
one unit of a to be preserved. And this cannot be corrected by the caller
either as adding one to the output will only shift the output range, and
it's not possible to pass 2^32 on the ratio <b>. The right approach is to
add "a" after the multiplication so that the input range is always
preserved for all ratio values from 0 to 0xffffffff:

     (a=0x00000000 * b=0x00000000 + a=0x00000000) >> 32 = 0x00000000
     (a=0x00000000 * b=0x00000001 + a=0x00000000) >> 32 = 0x00000000
     (a=0x00000000 * b=0xffffffff + a=0x00000000) >> 32 = 0x00000000
     (a=0x00000001 * b=0x00000000 + a=0x00000001) >> 32 = 0x00000000
     (a=0x00000001 * b=0x00000001 + a=0x00000001) >> 32 = 0x00000000
     (a=0x00000001 * b=0xffffffff + a=0x00000001) >> 32 = 0x00000001
     (a=0xffffffff * b=0x00000000 + a=0xffffffff) >> 32 = 0x00000000
     (a=0xffffffff * b=0x00000001 + a=0xffffffff) >> 32 = 0x00000001
     (a=0xffffffff * b=0xffffffff + a=0xffffffff) >> 32 = 0xffffffff

This is only used in freq_ctr calculations and the slightly lower value
is unlikely to have ever been noticed by anyone. This may be backported
though it is not important.

(cherry picked from commit e66ee1a65133bfa64370d841d2b6de3e50ca376e)
Signed-off-by: Christopher Faulet <cfaulet@haproxy.com>
include/haproxy/intops.h