Re: [PATCH] Input: MT - Add support for balanced slot assignment

[Peter Hutterer]

On Thu, Jan 22, 2015 at 09:24:01PM +0100, Henrik Rydberg wrote:
> Hi Dmitry,
> 
> On 01/22/2015 09:02 PM, Dmitry Torokhov wrote:
> > On Thu, Jan 22, 2015 at 08:52:25PM +0100, Henrik Rydberg wrote:
> >>  int input_mt_assign_slots(struct input_dev *dev, int *slots,
> >> -			  const struct input_mt_pos *pos, int num_pos)
> >> +			  const struct input_mt_pos *pos, int num_pos,
> >> +			  int dmax)
> > 
> > Should dmax be unsigned and do we really need to treat 0 specially or we
> > could use UNIT_MAX as "don't care" value?
> 
> We could have dmax unsigned, but it does not have to be from a branching
> perspective, since the square is what gets used anyways.
> 
> >>  {
> >>  	struct input_mt *mt = dev->mt;
> >> +	int mu = 2 * dmax * dmax;
> > 
> > For my education, what does "mu" stand for?
> 
> I chose mu because of the mathematical similarity to the chemical potential in
> statistical mechanics, where it denotes the energy per particle. Here, it
> denotes the energy per contact assignment.

can we please choose something that doesn't require the reviewer to have
familarity of statistical mechanics to make sense of a variable in the
multitouch tracking code?
 
> > Ideally, if someone could create a
> > write-up on the contact matching that would be most awesome.
> 
> Heh, I guess I will have to write something at some point, without requiring
> prior knowledge of Lagrange relaxation or the like. Time is a luxury these days...

yes please. the current code is pretty much inpenetrable for me.
for all I know it's sending a postcard to santa. judging by Benjamin's
comment "can someone tell what this function actually does" comment in the
doc patchset I'm not the only one.

this link here seems to explain the algorithm for mere mortals
http://www.troodon-software.com/algorithms/android/2010/06/20/euclidean-bipartite-matching-multi-touch-and-android/
whether that's what is implemented I don't know, I'm assuming this because
Documentation/multi-touch-protocol.txt mentions this algorithm.

there is no reference in the code what "adjust_dual" could mean, and
right now I have several wikipedia pages open for Lagrange Relaxation,
positive-definite matrix, Euclidean Bipartite Matching and it doesn't make
code review any easier. I failed to find what "overcover" means and
what a reduced matrix is took me about 20 minutes to find. Turns out it's
not the Row Echelon Form (most google hits for "reduced matrix") but a
"reduced cost matrix" (says input-mt.h) which has something to do with the
travelling salesman problem. Which makes sense since EBM is a graph problem
but at that point I gave up and went back to fixing a segfault which was
much more rewarding than this rabbit hole.

I'm not arguing against the code, it clearly does in 40 lines what would
otherwise be a lot longer and I appreciate that you added the fix for the
cursor jump (well, I assume so, it's not like I can decipher the 
algorithm :). but the approach limits the number of eyes that can review it
for correctness.

meanwhile, for people without a higher degree in mathematics can we at least
add references so there are some starting points to understanding this
code? And little things like naming variables so there's no guesswork
necessary what they can mean.

Thanks

Cheers,
   Peter
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/