thread '<unnamed>' panicked at 'attempt to add with overflow' when using as lib

[ksmoore17]

Hi,

This package is awesome, thanks for porting it. I'm trying to wrap it in python and getting an overflow panic when using it as a lib despite no problems using the cli.

I've used the flow described in lib.rs and compared to main.rs and it seems like I'm passing the correct objects to the spatial_color_quantization function, but there is an overflow error caused by the utility::b_value and matrix::get functions. I can't tell exactly at which place in spatial_color_quantization this is being triggered.

The problem is that b_value calculates indices to use in a get call to a matrix, and the indices that it calculates can sometimes be negative.

rscolorq/src/quant/utility.rs

Lines 85 to 94 in 8cce948

	pub fn b_value<T>(b: &Matrix2d<T>, i_x: isize, i_y: isize, j_x: isize, j_y: isize) -> T
	where
	T: Clone + Default + Copy,
	{
	let radius_width = b.width().saturating_sub(1) / 2;
	let radius_height = b.height().saturating_sub(1) / 2;
	let k_x = j_x - i_x + radius_width as isize;
	let k_y = j_y - i_y + radius_height as isize;
	if let Some(val) = b.get(k_x as usize, k_y as usize) {

They are converted to usize to index the array and if negative they wraparound. The overflow occurs when this index i at the max value is added to the calculation for the index in the flattened row.

rscolorq/src/matrix.rs

Lines 48 to 50 in 8cce948

	pub fn get(&self, i: usize, j: usize) -> Option<&T> {
	self.data.get(j * self.width + i)
	}

I've added some print statements to watch this and it seems like in the cli program, the wraparound occurs but the panic and overflow doesn't seem to. I don't know why my use of the library doesn't work.

The fix to it that I found was changing the get functions on the Matrix

https://github.com/pierogis/rscolorq/blob/e833cb7cdb6a509361308c6b0577644a4302dbee/src/matrix.rs#L47-L55

The wrapping methods on the usize objects work with the overflow and the output images are the same.

Something else kinda tangential to this issue: I think it would be good to swap the Matrix for the ndarray crate as it provides a more stable and well documented implementation of the same thing. ndarray also makes it really easy to do parallel with rayon if the algorithm could benefit from that anywhere. Would you be interested in a PR for that if I can get it working?

[okaneco]

Thanks. Overflow triggers panic in debug builds but wraps around in release builds. Because of how computationally heavy this algorithm is, I always ran it in release mode so I never triggered those panics. On similar projects in the future, I'll probably enable overflow-checks on my dev profile builds with a higher optimization level.
https://doc.rust-lang.org/cargo/reference/profiles.html#overflow-checks
https://doc.rust-lang.org/cargo/reference/profiles.html#default-profiles

With #5 merged, that shouldn't be a problem anymore. Be sure to use the release build of your Rust project with whatever you're wrapping the Python in to ensure you get the best performance. If you come across anything else, feel free to open more issues.

In the process of writing this, I realized that matrix indexing should use checked arithmetic instead of wrapping, which was more of an implementation detail/quirk inherited from the original. Changing to checked_mul/add alters the results slightly and seems to show a bit more contrast while needing less repeats/iterations. Logically, it makes sense to me that the magnitudes in the matrices were being invalidly modified by retrieving data from the overflowing indices they were being fed. I've made this change in #6 and I'm in the process of removing more unwrap assumptions.

Something else kinda tangential to this issue: I think it would be good to swap the Matrix for the ndarray crate as it provides a more stable and well documented implementation of the same thing. ndarray also makes it really easy to do parallel with rayon if the algorithm could benefit from that anywhere. Would you be interested in a PR for that if I can get it working?

I agree with the suggestion and I'm open to a PR for it, but I'm not sure how much effort it'd be or if it'd be worth it. Normally I wouldn't roll my own but the implementation was "simple" enough (but not without potential bugs). I'm not too familiar with ndarray and it's changed a lot since I looked at it last, it didn't have rayon support before among other things.

The quantization algorithm doesn't do a lot of direct matrix operations which matrix libraries are usually optimized for. The for loops are mainly iterating over indices and retrieving from the Matrix2d or Matrix3d with the computed index. I think multi-threading could help some parts like the quant::utility functions but we'd have to make sure we're not adding more overhead or multi-threading results that depend on a sequential order. I've opened an issue to discuss this more in #8. It's very likely there are places where chunking or par_iter would be beneficial but if you look closer at parts of the code you'll see the control flow is a little gnarly.

[ksmoore17]

Very good to know, thanks for the insight on release builds.

I thought about whether the undefined behavior should just be prevented, but figured maybe the negative indexing was actually how its supposed to work. If the results are better, that's a no brainer.

I'm now having a problem with how numpy ravels and how this library unravels. It's been driving me crazy, and at this point I think that reimplementing in ndarray might solve my problem quicker. Might let me a look at #1 as well.

[okaneco]

I think this issue has run its course. With #6 merged, I'm going to close it. Feel free to open a new issue if you have any or discuss in the other relevant issues. Thanks again for reporting this.