[mutter] Add MetaFraction for dealing with fractions

[Jonas Ådahl <jadahl src gnome org>]

commit 38235bc145b13f8d26a0505423b7f7def62e8d22
Author: Jonas Ådahl <jadahl gmail com>
Date:   Thu May 25 17:19:01 2017 +0800

    Add MetaFraction for dealing with fractions
    
    Add MetaFraction, which consists of two integers, the numerator an the
    denominator. The utility function to convert a double to a MetaFraction
    comes from gstreamer.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=784199

 src/Makefile.am          |    2 +
 src/core/meta-fraction.c |  134 ++++++++++++++++++++++++++++++++++++++++++++++
 src/core/meta-fraction.h |   31 +++++++++++
 3 files changed, 167 insertions(+), 0 deletions(-)
---
diff --git a/src/Makefile.am b/src/Makefile.am
index 5c0a553..d88539b 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -174,6 +174,8 @@ libmutter_@LIBMUTTER_API_VERSION@_la_SOURCES =      \
        meta/boxes.h                            \
        core/meta-border.c                      \
        core/meta-border.h                      \
+       core/meta-fraction.c                    \
+       core/meta-fraction.h                    \
        compositor/clutter-utils.c              \
        compositor/clutter-utils.h              \
        compositor/cogl-utils.c                 \
diff --git a/src/core/meta-fraction.c b/src/core/meta-fraction.c
new file mode 100644
index 0000000..8090aa4
--- /dev/null
+++ b/src/core/meta-fraction.c
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 1999,2000 Erik Walthinsen <omega cse ogi edu>
+ *                    2000 Wim Taymans <wtay chello be>
+ *                    2002 Thomas Vander Stichele <thomas apestaart org>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ *
+ * Fraction utility functions in this file comes from gstutils.c in gstreamer.
+ */
+
+#include "config.h"
+
+#include "core/meta-fraction.h"
+
+#include <glib.h>
+#include <math.h>
+
+#define MAX_TERMS       30
+#define MIN_DIVISOR     1.0e-10
+#define MAX_ERROR       1.0e-20
+
+static int
+greatest_common_divisor (int a,
+                         int b)
+{
+  while (b != 0)
+    {
+      int temp = a;
+
+      a = b;
+      b = temp % b;
+    }
+
+  return ABS (a);
+}
+
+MetaFraction
+meta_fraction_from_double (double src)
+{
+  double V, F;                 /* double being converted */
+  int N, D;                    /* will contain the result */
+  int A;                       /* current term in continued fraction */
+  int64_t N1, D1;              /* numerator, denominator of last approx */
+  int64_t N2, D2;              /* numerator, denominator of previous approx */
+  int i;
+  int gcd;
+  gboolean negative = FALSE;
+
+  /* initialize fraction being converted */
+  F = src;
+  if (F < 0.0)
+    {
+      F = -F;
+      negative = TRUE;
+    }
+
+  V = F;
+  /* initialize fractions with 1/0, 0/1 */
+  N1 = 1;
+  D1 = 0;
+  N2 = 0;
+  D2 = 1;
+  N = 1;
+  D = 1;
+
+  for (i = 0; i < MAX_TERMS; i++)
+    {
+      /* get next term */
+      A = (gint) F;               /* no floor() needed, F is always >= 0 */
+      /* get new divisor */
+      F = F - A;
+
+      /* calculate new fraction in temp */
+      N2 = N1 * A + N2;
+      D2 = D1 * A + D2;
+
+      /* guard against overflow */
+      if (N2 > G_MAXINT || D2 > G_MAXINT)
+        break;
+
+      N = N2;
+      D = D2;
+
+      /* save last two fractions */
+      N2 = N1;
+      D2 = D1;
+      N1 = N;
+      D1 = D;
+
+      /* quit if dividing by zero or close enough to target */
+      if (F < MIN_DIVISOR || fabs (V - ((gdouble) N) / D) < MAX_ERROR)
+        break;
+
+      /* Take reciprocal */
+      F = 1 / F;
+    }
+
+  /* fix for overflow */
+  if (D == 0)
+    {
+      N = G_MAXINT;
+      D = 1;
+    }
+
+  /* fix for negative */
+  if (negative)
+    N = -N;
+
+  /* simplify */
+  gcd = greatest_common_divisor (N, D);
+  if (gcd)
+    {
+      N /= gcd;
+      D /= gcd;
+    }
+
+  return (MetaFraction) {
+    .num = N,
+    .denom = D
+  };
+}
diff --git a/src/core/meta-fraction.h b/src/core/meta-fraction.h
new file mode 100644
index 0000000..f7ab294
--- /dev/null
+++ b/src/core/meta-fraction.h
@@ -0,0 +1,31 @@
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
+
+/*
+ * Copyright (C) 2017 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef META_FRACTION_H
+#define META_FRACTION_H
+
+typedef struct _MetaFraction
+{
+  int num;
+  int denom;
+} MetaFraction;
+
+MetaFraction meta_fraction_from_double (double src);
+
+#endif /* META_FRACTION_H */