diff options
author | Denys Vlasenko <vda.linux@googlemail.com> | 2021-06-12 12:19:20 +0200 |
---|---|---|
committer | Denys Vlasenko <vda.linux@googlemail.com> | 2021-06-12 12:19:20 +0200 |
commit | e5958f7dda4ce962d15950be515284560d6c0275 (patch) | |
tree | e391ff9ce4cd5c399116d5b08088bab06cd1dbee | |
parent | 4d983dcddeee94892d3072e84c7c9a01d4696055 (diff) | |
download | busybox-w32-e5958f7dda4ce962d15950be515284560d6c0275.tar.gz busybox-w32-e5958f7dda4ce962d15950be515284560d6c0275.tar.bz2 busybox-w32-e5958f7dda4ce962d15950be515284560d6c0275.zip |
bc: fix for mul overflow in scale calculation in a^b
function old new delta
zbc_num_p 516 518 +2
Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
-rw-r--r-- | miscutils/bc.c | 31 |
1 files changed, 23 insertions, 8 deletions
diff --git a/miscutils/bc.c b/miscutils/bc.c index dd9f4f8f1..930baaaaa 100644 --- a/miscutils/bc.c +++ b/miscutils/bc.c | |||
@@ -2152,6 +2152,7 @@ static FAST_FUNC BC_STATUS zbc_num_p(BcNum *a, BcNum *b, BcNum *restrict c, size | |||
2152 | BcNum copy; | 2152 | BcNum copy; |
2153 | unsigned long pow; | 2153 | unsigned long pow; |
2154 | size_t i, powrdx, resrdx; | 2154 | size_t i, powrdx, resrdx; |
2155 | size_t a_rdx; | ||
2155 | bool neg; | 2156 | bool neg; |
2156 | 2157 | ||
2157 | // GNU bc does not allow 2^2.0 - we do | 2158 | // GNU bc does not allow 2^2.0 - we do |
@@ -2182,16 +2183,30 @@ static FAST_FUNC BC_STATUS zbc_num_p(BcNum *a, BcNum *b, BcNum *restrict c, size | |||
2182 | 2183 | ||
2183 | bc_num_init(©, a->len); | 2184 | bc_num_init(©, a->len); |
2184 | bc_num_copy(©, a); | 2185 | bc_num_copy(©, a); |
2186 | a_rdx = a->rdx; // pull it into a CPU register (hopefully) | ||
2187 | // a is not used beyond this point | ||
2185 | 2188 | ||
2186 | if (!neg) { | 2189 | if (!neg) { |
2187 | if (a->rdx > scale) | 2190 | unsigned long new_scale; |
2188 | scale = a->rdx; | 2191 | if (a_rdx > scale) |
2189 | if (a->rdx * pow < scale) | 2192 | scale = a_rdx; |
2190 | scale = a->rdx * pow; | 2193 | new_scale = a_rdx * pow; |
2191 | } | 2194 | // Don't fall for multiplication overflow. Example: |
2192 | 2195 | // 0.01^2147483648 a_rdx:2 pow:0x80000000, 32bit mul is 0. | |
2193 | 2196 | //not that it matters with current algorithm, it would OOM on such large powers, | |
2194 | for (powrdx = a->rdx; !(pow & 1); pow >>= 1) { | 2197 | //but it can be improved to detect zero results etc. Example: with scale=0, |
2198 | //result of 0.01^N for any N>1 is 0: 0.01^2 = 0.0001 ~= 0.00 (trunc to scale) | ||
2199 | //then this would matter: | ||
2200 | // if (new_scale >= pow) is false, we had overflow, correct | ||
2201 | // "new_scale" value is larger than ULONG_MAX, thus larger | ||
2202 | // than any possible current value of "scale", | ||
2203 | // thus "scale = new_scale" should not be done: | ||
2204 | if (new_scale >= pow) | ||
2205 | if (new_scale < scale) | ||
2206 | scale = new_scale; | ||
2207 | } | ||
2208 | |||
2209 | for (powrdx = a_rdx; !(pow & 1); pow >>= 1) { | ||
2195 | powrdx <<= 1; | 2210 | powrdx <<= 1; |
2196 | s = zbc_num_mul(©, ©, ©, powrdx); | 2211 | s = zbc_num_mul(©, ©, ©, powrdx); |
2197 | if (s) goto err; | 2212 | if (s) goto err; |