Merge tag 'usb-6.1-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/usb

Pull USB / Thunderbolt updates from Greg KH:
 "Here is the big set of USB and Thunderbolt driver changes for 6.1-rc1.

  Nothing major in here, lots of little things with new devices
  supported and updates for a few drivers. Highlights include:

   - thunderbolt/USB4 devices supported a bit better than before, and
     some new ids to enable new hardware devices

   - USB gadget uvc updates for newer video formats and better v4l
     integration (the v4l portions were acked by those maintainers)

   - typec updates for tiny issues and more typec drivers for new chips.

   - xhci tiny updates for minor issues

   - big usb-serial ftdi_sio driver update to handle new devices better

   - lots of tiny dwc3 fixes and updates for the IP block that is
     showing up everywhere these days

   - dts updates for new devices being supported

   - other tiny janitorial and cleanups fixes for lots of different USB
     drivers. Full details are in the shortlog.

  All of these have been in linux-next for a while with no reported
  issues"

* tag 'usb-6.1-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/usb: (169 commits)
  usb: gadget: uvc: don't put item still in use
  usb: gadget: uvc: Fix argument to sizeof() in uvc_register_video()
  usb: host: ehci-exynos: switch to using gpiod API
  Revert "usb: dwc3: Don't switch OTG -> peripheral if extcon is present"
  Revert "USB: fixup for merge issue with "usb: dwc3: Don't switch OTG -> peripheral if extcon is present""
  dt-bindings: usb: Convert FOTG210 to dt schema
  usb: mtu3: fix failed runtime suspend in host only mode
  USB: omap_udc: Fix spelling mistake: "tranceiver_ctrl" -> "transceiver_ctrl"
  usb: typec: ucsi_ccg: Disable UCSI ALT support on Tegra
  usb: typec: Replace custom implementation of device_match_fwnode()
  usb: typec: ucsi: Don't warn on probe deferral
  usb: add quirks for Lenovo OneLink+ Dock
  MAINTAINERS: switch dwc3 to Thinh
  usb: idmouse: fix an uninit-value in idmouse_open
  USB: PHY: JZ4770: Switch to use dev_err_probe() helper
  usb: phy: generic: Switch to use dev_err_probe() helper
  usb: ulpi: use DEFINE_SHOW_ATTRIBUTE to simplify ulpi_regs
  usb: cdns3: remove dead code
  usb: cdc-wdm: Use skb_put_data() instead of skb_put/memcpy pair
  usb: musb: sunxi: Switch to use dev_err_probe() helper
  ...

1 files changed, 86 insertions, 0 deletions

diff --git a/drivers/media/v4l2-core/v4l2-common.c b/drivers/media/v4l2-core/v4l2-common.c
index e0fbe6ba4b6c..40f56e044640 100644
--- a/drivers/media/v4l2-core/v4l2-common.c
+++ b/drivers/media/v4l2-core/v4l2-common.c
@@ -484,3 +484,89 @@ s64 v4l2_get_link_freq(struct v4l2_ctrl_handler *handler, unsigned int mul,
 	return freq > 0 ? freq : -EINVAL;
 }
 EXPORT_SYMBOL_GPL(v4l2_get_link_freq);
+
+/*
+ * Simplify a fraction using a simple continued fraction decomposition. The
+ * idea here is to convert fractions such as 333333/10000000 to 1/30 using
+ * 32 bit arithmetic only. The algorithm is not perfect and relies upon two
+ * arbitrary parameters to remove non-significative terms from the simple
+ * continued fraction decomposition. Using 8 and 333 for n_terms and threshold
+ * respectively seems to give nice results.
+ */
+void v4l2_simplify_fraction(u32 *numerator, u32 *denominator,
+		unsigned int n_terms, unsigned int threshold)
+{
+	u32 *an;
+	u32 x, y, r;
+	unsigned int i, n;
+
+	an = kmalloc_array(n_terms, sizeof(*an), GFP_KERNEL);
+	if (an == NULL)
+		return;
+
+	/*
+	 * Convert the fraction to a simple continued fraction. See
+	 * https://en.wikipedia.org/wiki/Continued_fraction
+	 * Stop if the current term is bigger than or equal to the given
+	 * threshold.
+	 */
+	x = *numerator;
+	y = *denominator;
+
+	for (n = 0; n < n_terms && y != 0; ++n) {
+		an[n] = x / y;
+		if (an[n] >= threshold) {
+			if (n < 2)
+				n++;
+			break;
+		}
+
+		r = x - an[n] * y;
+		x = y;
+		y = r;
+	}
+
+	/* Expand the simple continued fraction back to an integer fraction. */
+	x = 0;
+	y = 1;
+
+	for (i = n; i > 0; --i) {
+		r = y;
+		y = an[i-1] * y + x;
+		x = r;
+	}
+
+	*numerator = y;
+	*denominator = x;
+	kfree(an);
+}
+EXPORT_SYMBOL_GPL(v4l2_simplify_fraction);
+
+/*
+ * Convert a fraction to a frame interval in 100ns multiples. The idea here is
+ * to compute numerator / denominator * 10000000 using 32 bit fixed point
+ * arithmetic only.
+ */
+u32 v4l2_fraction_to_interval(u32 numerator, u32 denominator)
+{
+	u32 multiplier;
+
+	/* Saturate the result if the operation would overflow. */
+	if (denominator == 0 ||
+	    numerator/denominator >= ((u32)-1)/10000000)
+		return (u32)-1;
+
+	/*
+	 * Divide both the denominator and the multiplier by two until
+	 * numerator * multiplier doesn't overflow. If anyone knows a better
+	 * algorithm please let me know.
+	 */
+	multiplier = 10000000;
+	while (numerator > ((u32)-1)/multiplier) {
+		multiplier /= 2;
+		denominator /= 2;
+	}
+
+	return denominator ? numerator * multiplier / denominator : 0;
+}
+EXPORT_SYMBOL_GPL(v4l2_fraction_to_interval);