diff options
| author | Kevin O'Connor <kevin@koconnor.net> | 2016-12-24 12:02:37 -0500 |
|---|---|---|
| committer | Kevin O'Connor <kevin@koconnor.net> | 2016-12-24 12:02:37 -0500 |
| commit | 4a16053c002ffb88cd7bdf4dbe9e8a36018dab8d (patch) | |
| tree | a0d0fe61c6bc347459152a17b41b9c5078495103 /klippy | |
| parent | d0c61f0f76b116e07567e6fbfe2a6bb585545249 (diff) | |
| download | kutter-4a16053c002ffb88cd7bdf4dbe9e8a36018dab8d.tar.gz kutter-4a16053c002ffb88cd7bdf4dbe9e8a36018dab8d.tar.xz kutter-4a16053c002ffb88cd7bdf4dbe9e8a36018dab8d.zip | |
stepcompress: Fix integer overflow leading to infinite loop
Commit a217c0f3 changed the way the "addfactor" was calculated.
Unfortunately, it was possible for the updated method to cause an
integer overflow and have a negative addfactor. Fix this by
explicitly casting the addfactor calculation to uint32_t.
Signed-off-by: Kevin O'Connor <kevin@koconnor.net>
Diffstat (limited to 'klippy')
| -rw-r--r-- | klippy/stepcompress.c | 15 |
1 files changed, 11 insertions, 4 deletions
diff --git a/klippy/stepcompress.c b/klippy/stepcompress.c index e52b1035..72ff101f 100644 --- a/klippy/stepcompress.c +++ b/klippy/stepcompress.c @@ -95,6 +95,13 @@ idiv_down(int32_t n, int32_t d) return (n>=0) ? (n/d) : (n - d + 1) / d; } +// Calculate the impact of each 'add' for a sequence with 'count' steps +static inline int32_t +calc_addfactor(int32_t count) +{ + return (uint32_t)count*(count-1)/2; +} + struct points { int32_t minp, maxp; }; @@ -150,7 +157,7 @@ compress_bisect_add(struct stepcompress *sc) return (struct step_move){ interval, count, add }; } nextpoint = minmax_point(sc, sc->queue_pos + nextcount - 1); - int32_t nextaddfactor = nextcount*(nextcount-1)/2; + int32_t nextaddfactor = calc_addfactor(nextcount); int32_t c = add*nextaddfactor; if (nextmininterval*nextcount < nextpoint.minp - c) nextmininterval = DIV_UP(nextpoint.minp - c, nextcount); @@ -162,7 +169,7 @@ compress_bisect_add(struct stepcompress *sc) } // Check if this is the best sequence found so far - int32_t count = nextcount - 1, addfactor = count*(count-1)/2; + int32_t count = nextcount - 1, addfactor = calc_addfactor(count); int32_t reach = add*addfactor + interval*count; if (reach > bestreach || (reach == bestreach && interval > bestinterval)) { @@ -177,7 +184,7 @@ compress_bisect_add(struct stepcompress *sc) } // Check if a greater or lesser add could extend the sequence - int32_t nextaddfactor = nextcount*(nextcount-1)/2; + int32_t nextaddfactor = calc_addfactor(nextcount); int32_t nextreach = add*nextaddfactor + interval*nextcount; if (nextreach < nextpoint.minp) { minadd = add + 1; @@ -332,7 +339,7 @@ stepcompress_flush(struct stepcompress *sc, uint64_t move_clock) // Be careful with 32bit overflow sc->last_step_clock = qm->req_clock = *sc->queue_pos; } else { - uint32_t addfactor = move.count*(move.count-1)/2; + int32_t addfactor = calc_addfactor(move.count); uint32_t ticks = move.add*addfactor + move.interval*move.count; sc->last_step_clock += ticks; } |