"Reflecting" addition

Question

I'm implementing the following function for signed integer numbers: given endpoints of a closed interval lo and hi, and inputs x (in [lo..hi]) and dx, I'd like to compute the "reflected sum": if x + dx is still in [lo..hi] then that's it; otherwise the underhanging or overhanging portion is "folded back" onto the result (shown as y below). Basically, x is "bouncing around" in the interval.

 overhang
 /--\
 dx
 -------------->
--------[-------|-------|---]---|------
 lo x y hi x + dx
 <--- 

Because this is for a hardware circuit, I am doing this using Clash's sized Signed integer type and width-extending addition, otherwise it is normal Haskell code.

My current implementation is the following:

bounce :: (KnownNat n, KnownNat k, (k + 1) <= n) => (Signed n, Signed n) -> Signed n -> Signed k -> (Signed n, Bool)
bounce (lo, hi) x dx
 | under > 0 = (lo + under, True)
 | over > 0 = (hi - over, True)
 | otherwise = (resize new, False)
 where
 new = add x dx
 under = resize $ resize lo - new
 over = resize $ new - resize hi

Things I don't like about this implementation:

• There is a lot of noise about bit widths (all the resize calls)
• Overall, it is not immediately obvious by just looking at the code what it does. It feels like it's doing a lot of seemingly ad-hoc arithmetic operations that "just happen" to work.

I am looking for improvements that come from the structure of the problem, not "oh you should rename x to theNumberThatIsBouncingAround because one-letter variable names bad".

Answer 1

I don't think your code agrees with your spec: Your code looks like it can only implement a function built from three line segments.

You shouldn't need explicit resize.

bounce (lo, hi) x dx = let
 (bounces, remainder) = divMod (add dx $ x-lo) $ hi-lo
 in (if even bounces then lo + remainder else hi - remainder
 ,bounces /= 0)

• Cactus: Unfortunately, divMod by a non-power-of-two is not really implementable as a combinational circuit.
• Cactus: I'm happy with not supporting multiple bounces in one timestep.
• Gurkenglas: You are already implementing divMod by means of a lookup table for div in {-1,0,1}. That's why your code looks improvable to you. You do in fact need to implement divMod in some way, for that is your problem statement.