* Copyright (C) 1999,2000 Erik Walthinsen <omega@cse.ogi.edu>
* 2000 Wim Taymans <wtay@chello.be>
* 2002 Thomas Vander Stichele <thomas@apestaart.org>
+ * 2004 Wim Taymans <wim@fluendo.com>
+ * 2015 Jan Schmidt <jan@centricular.com>
*
* gstutils.c: Utility functions
*
g_value_init (&v, value_type);
/* special case for element <-> xml (de)serialisation */
- if (GST_VALUE_HOLDS_STRUCTURE (&v) && strcmp (value, "NULL") == 0) {
+ if (value_type == GST_TYPE_STRUCTURE && strcmp (value, "NULL") == 0) {
g_value_set_boxed (&v, NULL);
goto done;
}
* Retrieves a pad template from @element that is compatible with @compattempl.
* Pads from compatible templates can be linked together.
*
- * Returns: (transfer none): a compatible #GstPadTemplate, or %NULL if none
- * was found. No unreferencing is necessary.
+ * Returns: (transfer none) (nullable): a compatible #GstPadTemplate,
+ * or %NULL if none was found. No unreferencing is necessary.
*/
GstPadTemplate *
gst_element_get_compatible_pad_template (GstElement * element,
* #GST_PAD_REQUEST, requests a new pad. Can return %NULL for #GST_PAD_SOMETIMES
* templates.
*
- * Returns: (transfer full): the #GstPad, or NULL if one could not be found
- * or created.
+ * Returns: (transfer full) (nullable): the #GstPad, or %NULL if one
+ * could not be found or created.
*/
static GstPad *
gst_element_get_pad_from_template (GstElement * element, GstPadTemplate * templ)
* Requests a pad from @element. The returned pad should be unlinked and
* compatible with @templ. Might return an existing pad, or request a new one.
*
- * Returns: a #GstPad, or %NULL if one could not be found or created.
+ * Returns: (nullable): a #GstPad, or %NULL if one could not be found
+ * or created.
*/
static GstPad *
gst_element_request_compatible_pad (GstElement * element,
static gboolean
gst_pad_check_link (GstPad * srcpad, GstPad * sinkpad)
{
- /* FIXME This function is gross. It's almost a direct copy of
- * gst_pad_link_filtered(). Any decent programmer would attempt
- * to merge the two functions, which I will do some day. --ds
- */
-
/* generic checks */
g_return_val_if_fail (GST_IS_PAD (srcpad), FALSE);
g_return_val_if_fail (GST_IS_PAD (sinkpad), FALSE);
GST_CAT_INFO (GST_CAT_PADS, "trying to link %s:%s and %s:%s",
GST_DEBUG_PAD_NAME (srcpad), GST_DEBUG_PAD_NAME (sinkpad));
- /* FIXME: shouldn't we convert this to g_return_val_if_fail? */
if (GST_PAD_PEER (srcpad) != NULL) {
GST_CAT_INFO (GST_CAT_PADS, "Source pad %s:%s has a peer, failed",
GST_DEBUG_PAD_NAME (srcpad));
* and if none can be found, it will request a compatible REQUEST pad by looking
* at the templates of @element.
*
- * Returns: (transfer full): the #GstPad to which a link can be made, or %NULL
- * if one cannot be found. gst_object_unref() after usage.
+ * Returns: (transfer full) (nullable): the #GstPad to which a link
+ * can be made, or %NULL if one cannot be found. gst_object_unref()
+ * after usage.
*/
GstPad *
gst_element_get_compatible_pad (GstElement * element, GstPad * pad,
/* try to create a new one */
/* requesting is a little crazy, we need a template. Let's create one */
- /* FIXME: why not gst_pad_get_pad_template (pad); */
templcaps = gst_pad_query_caps (pad, NULL);
+ if (caps) {
+ GstCaps *inter = gst_caps_intersect (templcaps, caps);
+
+ gst_caps_unref (templcaps);
+ templcaps = inter;
+ }
templ = gst_pad_template_new ((gchar *) GST_PAD_NAME (pad),
GST_PAD_DIRECTION (pad), GST_PAD_ALWAYS, templcaps);
gst_caps_unref (templcaps);
gst_object_unref (kid2);
return root;
}
+ gst_object_unref (root);
root = kid2;
if (!object_has_ancestor (o2, kid1, &kid2)) {
gst_object_unref (kid1);
return root;
}
+ gst_object_unref (root);
root = kid1;
}
}
gpad = gst_ghost_pad_new (name, pad);
g_free (name);
- GST_STATE_LOCK (e);
- gst_element_get_state (e, ¤t, &next, 0);
+ GST_STATE_LOCK (parent);
+ gst_element_get_state (GST_ELEMENT (parent), ¤t, &next, 0);
- if (current > GST_STATE_READY || next == GST_STATE_PAUSED)
+ if (current > GST_STATE_READY || next >= GST_STATE_PAUSED)
gst_pad_set_active (gpad, TRUE);
if (!gst_element_add_pad ((GstElement *) parent, gpad)) {
g_warning ("Pad named %s already exists in element %s\n",
GST_OBJECT_NAME (gpad), GST_OBJECT_NAME (parent));
gst_object_unref ((GstObject *) gpad);
- GST_STATE_UNLOCK (e);
+ GST_STATE_UNLOCK (parent);
return NULL;
}
- GST_STATE_UNLOCK (e);
+ GST_STATE_UNLOCK (parent);
return gpad;
}
/* we need to setup some ghost pads */
root = find_common_root (e1, e2);
if (!root) {
- g_warning ("Trying to connect elements that don't share a common "
- "ancestor: %s and %s", GST_ELEMENT_NAME (e1), GST_ELEMENT_NAME (e2));
+ if (GST_OBJECT_PARENT (e1) == NULL)
+ g_warning ("Trying to link elements %s and %s that don't share a common "
+ "ancestor: %s hasn't been added to a bin or pipeline, but %s is in %s",
+ GST_ELEMENT_NAME (e1), GST_ELEMENT_NAME (e2),
+ GST_ELEMENT_NAME (e1), GST_ELEMENT_NAME (e2),
+ GST_ELEMENT_NAME (GST_OBJECT_PARENT (e2)));
+ else if (GST_OBJECT_PARENT (e2) == NULL)
+ g_warning ("Trying to link elements %s and %s that don't share a common "
+ "ancestor: %s hasn't been added to a bin or pipeline, and %s is in %s",
+ GST_ELEMENT_NAME (e1), GST_ELEMENT_NAME (e2),
+ GST_ELEMENT_NAME (e2), GST_ELEMENT_NAME (e1),
+ GST_ELEMENT_NAME (GST_OBJECT_PARENT (e1)));
+ else
+ g_warning ("Trying to link elements %s and %s that don't share a common "
+ "ancestor: %s is in %s, and %s is in %s",
+ GST_ELEMENT_NAME (e1), GST_ELEMENT_NAME (e2),
+ GST_ELEMENT_NAME (e1), GST_ELEMENT_NAME (GST_OBJECT_PARENT (e1)),
+ GST_ELEMENT_NAME (e2), GST_ELEMENT_NAME (GST_OBJECT_PARENT (e2)));
return FALSE;
}
}
/**
+ * gst_pad_link_maybe_ghosting_full:
+ * @src: a #GstPad
+ * @sink: a #GstPad
+ * @flags: some #GstPadLinkCheck flags
+ *
+ * Links @src to @sink, creating any #GstGhostPad's in between as necessary.
+ *
+ * This is a convenience function to save having to create and add intermediate
+ * #GstGhostPad's as required for linking across #GstBin boundaries.
+ *
+ * If @src or @sink pads don't have parent elements or do not share a common
+ * ancestor, the link will fail.
+ *
+ * Calling gst_pad_link_maybe_ghosting_full() with
+ * @flags == %GST_PAD_LINK_CHECK_DEFAULT is the recommended way of linking
+ * pads with safety checks applied.
+ *
+ * Returns: whether the link succeeded.
+ *
+ * Since: 1.10
+ */
+gboolean
+gst_pad_link_maybe_ghosting_full (GstPad * src, GstPad * sink,
+ GstPadLinkCheck flags)
+{
+ g_return_val_if_fail (GST_IS_PAD (src), FALSE);
+ g_return_val_if_fail (GST_IS_PAD (sink), FALSE);
+
+ return pad_link_maybe_ghosting (src, sink, flags);
+}
+
+/**
+ * gst_pad_link_maybe_ghosting:
+ * @src: a #GstPad
+ * @sink: a #GstPad
+ *
+ * Links @src to @sink, creating any #GstGhostPad's in between as necessary.
+ *
+ * This is a convenience function to save having to create and add intermediate
+ * #GstGhostPad's as required for linking across #GstBin boundaries.
+ *
+ * If @src or @sink pads don't have parent elements or do not share a common
+ * ancestor, the link will fail.
+ *
+ * Returns: whether the link succeeded.
+ *
+ * Since: 1.10
+ */
+gboolean
+gst_pad_link_maybe_ghosting (GstPad * src, GstPad * sink)
+{
+ g_return_val_if_fail (GST_IS_PAD (src), FALSE);
+ g_return_val_if_fail (GST_IS_PAD (sink), FALSE);
+
+ return gst_pad_link_maybe_ghosting_full (src, sink,
+ GST_PAD_LINK_CHECK_DEFAULT);
+}
+
+static void
+release_and_unref_pad (GstElement * element, GstPad * pad, gboolean requestpad)
+{
+ if (pad) {
+ if (requestpad)
+ gst_element_release_request_pad (element, pad);
+ gst_object_unref (pad);
+ }
+}
+
+/**
* gst_element_link_pads_full:
* @src: a #GstElement containing the source pad.
* @srcpadname: (allow-none): the name of the #GstPad in source element
GstPad *srcpad, *destpad;
GstPadTemplate *srctempl, *desttempl;
GstElementClass *srcclass, *destclass;
+ gboolean srcrequest, destrequest;
/* checks */
g_return_val_if_fail (GST_IS_ELEMENT (src), FALSE);
srcpadname ? srcpadname : "(any)", GST_ELEMENT_NAME (dest),
destpadname ? destpadname : "(any)");
+ srcrequest = FALSE;
+ destrequest = FALSE;
+
/* get a src pad */
if (srcpadname) {
/* name specified, look it up */
- if (!(srcpad = gst_element_get_static_pad (src, srcpadname)))
- srcpad = gst_element_get_request_pad (src, srcpadname);
+ if (!(srcpad = gst_element_get_static_pad (src, srcpadname))) {
+ if ((srcpad = gst_element_get_request_pad (src, srcpadname)))
+ srcrequest = TRUE;
+ }
if (!srcpad) {
GST_CAT_DEBUG (GST_CAT_ELEMENT_PADS, "no pad %s:%s",
GST_ELEMENT_NAME (src), srcpadname);
if (!(GST_PAD_DIRECTION (srcpad) == GST_PAD_SRC)) {
GST_CAT_DEBUG (GST_CAT_ELEMENT_PADS, "pad %s:%s is no src pad",
GST_DEBUG_PAD_NAME (srcpad));
- gst_object_unref (srcpad);
+ release_and_unref_pad (src, srcpad, srcrequest);
return FALSE;
}
if (GST_PAD_PEER (srcpad) != NULL) {
GST_CAT_DEBUG (GST_CAT_ELEMENT_PADS,
"pad %s:%s is already linked to %s:%s", GST_DEBUG_PAD_NAME (srcpad),
GST_DEBUG_PAD_NAME (GST_PAD_PEER (srcpad)));
+ /* already linked request pads look like static pads, so the request pad
+ * was never requested a second time above, so no need to release it */
gst_object_unref (srcpad);
return FALSE;
}
/* get a destination pad */
if (destpadname) {
/* name specified, look it up */
- if (!(destpad = gst_element_get_static_pad (dest, destpadname)))
- destpad = gst_element_get_request_pad (dest, destpadname);
+ if (!(destpad = gst_element_get_static_pad (dest, destpadname))) {
+ if ((destpad = gst_element_get_request_pad (dest, destpadname)))
+ destrequest = TRUE;
+ }
if (!destpad) {
GST_CAT_DEBUG (GST_CAT_ELEMENT_PADS, "no pad %s:%s",
GST_ELEMENT_NAME (dest), destpadname);
+ release_and_unref_pad (src, srcpad, srcrequest);
return FALSE;
} else {
if (!(GST_PAD_DIRECTION (destpad) == GST_PAD_SINK)) {
GST_CAT_DEBUG (GST_CAT_ELEMENT_PADS, "pad %s:%s is no sink pad",
GST_DEBUG_PAD_NAME (destpad));
- gst_object_unref (destpad);
+ release_and_unref_pad (src, srcpad, srcrequest);
+ release_and_unref_pad (dest, destpad, destrequest);
return FALSE;
}
if (GST_PAD_PEER (destpad) != NULL) {
"pad %s:%s is already linked to %s:%s",
GST_DEBUG_PAD_NAME (destpad),
GST_DEBUG_PAD_NAME (GST_PAD_PEER (destpad)));
+ release_and_unref_pad (src, srcpad, srcrequest);
+ /* already linked request pads look like static pads, so the request pad
+ * was never requested a second time above, so no need to release it */
gst_object_unref (destpad);
return FALSE;
}
/* two explicitly specified pads */
result = pad_link_maybe_ghosting (srcpad, destpad, flags);
- gst_object_unref (srcpad);
- gst_object_unref (destpad);
-
+ if (result) {
+ gst_object_unref (srcpad);
+ gst_object_unref (destpad);
+ } else {
+ release_and_unref_pad (src, srcpad, srcrequest);
+ release_and_unref_pad (dest, destpad, destrequest);
+ }
return result;
}
GST_DEBUG_PAD_NAME (srcpad));
if ((GST_PAD_DIRECTION (srcpad) == GST_PAD_SRC) &&
(GST_PAD_PEER (srcpad) == NULL)) {
+ gboolean temprequest = FALSE;
GstPad *temp;
if (destpadname) {
gst_object_ref (temp);
} else {
temp = gst_element_get_compatible_pad (dest, srcpad, NULL);
+ if (temp && GST_PAD_PAD_TEMPLATE (temp)
+ && GST_PAD_TEMPLATE_PRESENCE (GST_PAD_PAD_TEMPLATE (temp)) ==
+ GST_PAD_REQUEST) {
+ temprequest = TRUE;
+ }
}
if (temp && pad_link_maybe_ghosting (srcpad, temp, flags)) {
}
if (temp) {
+ if (temprequest)
+ gst_element_release_request_pad (dest, temp);
gst_object_unref (temp);
}
}
if (srcpadname) {
GST_CAT_DEBUG (GST_CAT_ELEMENT_PADS, "no link possible from %s:%s to %s",
GST_DEBUG_PAD_NAME (srcpad), GST_ELEMENT_NAME (dest));
+ /* no need to release any request pad as both src- and destpadname must be
+ * set to end up here, but this case has already been taken care of above */
if (destpad)
gst_object_unref (destpad);
destpad = NULL;
}
- if (srcpad)
- gst_object_unref (srcpad);
- srcpad = NULL;
+ if (srcpad) {
+ release_and_unref_pad (src, srcpad, srcrequest);
+ srcpad = NULL;
+ }
if (destpad) {
/* loop through the existing pads in the destination */
if ((GST_PAD_DIRECTION (destpad) == GST_PAD_SINK) &&
(GST_PAD_PEER (destpad) == NULL)) {
GstPad *temp = gst_element_get_compatible_pad (src, destpad, NULL);
+ gboolean temprequest = FALSE;
+
+ if (temp && GST_PAD_PAD_TEMPLATE (temp)
+ && GST_PAD_TEMPLATE_PRESENCE (GST_PAD_PAD_TEMPLATE (temp)) ==
+ GST_PAD_REQUEST) {
+ temprequest = TRUE;
+ }
if (temp && pad_link_maybe_ghosting (temp, destpad, flags)) {
GST_CAT_DEBUG (GST_CAT_ELEMENT_PADS, "linked pad %s:%s to pad %s:%s",
gst_object_unref (destpad);
return TRUE;
}
- if (temp) {
- gst_object_unref (temp);
- }
+
+ release_and_unref_pad (src, temp, temprequest);
}
if (destpads) {
destpads = g_list_next (destpads);
if (destpadname) {
GST_CAT_DEBUG (GST_CAT_ELEMENT_PADS, "no link possible from %s to %s:%s",
GST_ELEMENT_NAME (src), GST_DEBUG_PAD_NAME (destpad));
- gst_object_unref (destpad);
+ release_and_unref_pad (dest, destpad, destrequest);
return FALSE;
} else {
- if (destpad)
+ /* no need to release any request pad as the case of unset destpatname and
+ * destpad being a requst pad has already been taken care of when looking
+ * though the destination pads above */
+ if (destpad) {
gst_object_unref (destpad);
+ }
destpad = NULL;
}
return TRUE;
}
/* it failed, so we release the request pads */
- if (srcpad)
+ if (srcpad) {
gst_element_release_request_pad (src, srcpad);
- if (destpad)
+ gst_object_unref (srcpad);
+ }
+ if (destpad) {
gst_element_release_request_pad (dest, destpad);
+ gst_object_unref (destpad);
+ }
}
gst_caps_unref (srccaps);
gst_caps_unref (destcaps);
/**
* gst_element_query_convert:
* @element: a #GstElement to invoke the convert query on.
- * @src_format: (inout): a #GstFormat to convert from.
+ * @src_format: a #GstFormat to convert from.
* @src_val: a value to convert.
* @dest_format: the #GstFormat to convert to.
* @dest_val: (out): a pointer to the result.
g_return_val_if_fail (seek_pos >= 0, FALSE);
return gst_element_seek (element, 1.0, format, seek_flags,
- GST_SEEK_TYPE_SET, seek_pos, GST_SEEK_TYPE_NONE, 0);
+ GST_SEEK_TYPE_SET, seek_pos, GST_SEEK_TYPE_SET, GST_CLOCK_TIME_NONE);
}
/**
* Gets the parent of @pad, cast to a #GstElement. If a @pad has no parent or
* its parent is not an element, return %NULL.
*
- * Returns: (transfer full): the parent of the pad. The caller has a
- * reference on the parent, so unref when you're finished with it.
+ * Returns: (transfer full) (nullable): the parent of the pad. The
+ * caller has a reference on the parent, so unref when you're finished
+ * with it.
*
* MT safe.
*/
* downstream in the preferred order. @filter might be %NULL but
* if it is not %NULL the returned caps will be a subset of @filter.
*
- * Returns: the caps of the peer pad with incremented ref-count. When there is
- * no peer pad, this function returns @filter or, when @filter is %NULL, ANY
- * caps.
+ * Returns: (transfer full): the caps of the peer pad with incremented
+ * ref-count. When there is no peer pad, this function returns @filter or,
+ * when @filter is %NULL, ANY caps.
*/
GstCaps *
gst_pad_peer_query_caps (GstPad * pad, GstCaps * filter)
* owns a reference to it and should use gst_object_unref() on the
* pad when it is not needed any longer.
*
- * Returns: (transfer full): unlinked pad of the given direction, %NULL.
+ * Returns: (transfer full) (nullable): unlinked pad of the given
+ * direction, %NULL.
*/
GstPad *
gst_bin_find_unlinked_pad (GstBin * bin, GstPadDirection direction)
return pad;
}
+static void
+gst_bin_sync_children_states_foreach (const GValue * value, gpointer user_data)
+{
+ gboolean *success = user_data;
+ GstElement *element = g_value_get_object (value);
+
+ if (gst_element_is_locked_state (element)) {
+ *success = TRUE;
+ } else {
+ *success = *success && gst_element_sync_state_with_parent (element);
+
+ if (GST_IS_BIN (element))
+ *success = *success
+ && gst_bin_sync_children_states (GST_BIN_CAST (element));
+ }
+}
+
+/**
+ * gst_bin_sync_children_states:
+ * @bin: a #GstBin
+ *
+ * Synchronizes the state of every child of @bin with the state
+ * of @bin. See also gst_element_sync_state_with_parent().
+ *
+ * Returns: %TRUE if syncing the state was successful for all children,
+ * otherwise %FALSE.
+ *
+ * Since: 1.6
+ */
+gboolean
+gst_bin_sync_children_states (GstBin * bin)
+{
+ GstIterator *it;
+ GstIteratorResult res = GST_ITERATOR_OK;
+ gboolean success = TRUE;
+
+ it = gst_bin_iterate_sorted (bin);
+
+ do {
+ if (res == GST_ITERATOR_RESYNC) {
+ success = TRUE;
+ gst_iterator_resync (it);
+ }
+ res =
+ gst_iterator_foreach (it, gst_bin_sync_children_states_foreach,
+ &success);
+ } while (res == GST_ITERATOR_RESYNC);
+ gst_iterator_free (it);
+
+ return success;
+}
+
/**
* gst_parse_bin_from_description:
* @bin_description: command line describing the bin
* and want them all ghosted, you will have to create the ghost pads
* yourself).
*
- * Returns: (transfer floating) (type Gst.Bin): a newly-created bin,
- * or %NULL if an error occurred.
+ * Returns: (transfer floating) (type Gst.Bin) (nullable): a
+ * newly-created bin, or %NULL if an error occurred.
*/
GstElement *
gst_parse_bin_from_description (const gchar * bin_description,
*
* The complexity of this search function is O(log (num_elements)).
*
- * Returns: (transfer none): The address of the found element or %NULL if nothing was found
+ * Returns: (transfer none) (nullable): The address of the found
+ * element or %NULL if nothing was found
*/
gpointer
gst_util_array_binary_search (gpointer array, guint num_elements,
return FALSE;
if (G_MAXINT / ABS (a_d) < ABS (b_d))
return FALSE;
- if (G_MAXINT / ABS (a_d) < ABS (b_d))
- return FALSE;
*res_n = (a_n * b_d) + (a_d * b_n);
*res_d = a_d * b_d;
* here is for source elements */
if (!upstream_stream_id) {
GstQuery *query;
+ gchar *uri = NULL;
/* Try to generate one from the URI query and
* if it fails take a random number instead */
query = gst_query_new_uri ();
if (gst_element_query (parent, query)) {
- GChecksum *cs;
- gchar *uri;
-
gst_query_parse_uri (query, &uri);
+ }
+
+ if (uri) {
+ GChecksum *cs;
/* And then generate an SHA256 sum of the URI */
cs = g_checksum_new (G_CHECKSUM_SHA256);
* The returned stream-id string should be treated as an opaque string, its
* contents should not be interpreted.
*
- * Returns: a newly-allocated copy of the stream-id for @pad, or %NULL.
- * g_free() the returned string when no longer needed.
+ * Returns: (nullable): a newly-allocated copy of the stream-id for
+ * @pad, or %NULL. g_free() the returned string when no longer
+ * needed.
*
* Since: 1.2
*/
}
/**
+ * gst_pad_get_stream:
+ * @pad: A source #GstPad
+ *
+ * Returns the current #GstStream for the @pad, or %NULL if none has been
+ * set yet, i.e. the pad has not received a stream-start event yet.
+ *
+ * This is a convenience wrapper around gst_pad_get_sticky_event() and
+ * gst_event_parse_stream().
+ *
+ * Returns: (nullable) (transfer full): the current #GstStream for @pad, or %NULL.
+ * unref the returned stream when no longer needed.
+ *
+ * Since: 1.10
+ */
+GstStream *
+gst_pad_get_stream (GstPad * pad)
+{
+ GstStream *stream = NULL;
+ GstEvent *event;
+
+ g_return_val_if_fail (GST_IS_PAD (pad), NULL);
+
+ event = gst_pad_get_sticky_event (pad, GST_EVENT_STREAM_START, 0);
+ if (event != NULL) {
+ gst_event_parse_stream (event, &stream);
+ gst_event_unref (event);
+ GST_LOG_OBJECT (pad, "pad has stream object %p", stream);
+ } else {
+ GST_DEBUG_OBJECT (pad, "pad has not received a stream-start event yet");
+ }
+
+ return stream;
+}
+
+/**
* gst_util_group_id_next:
*
* Return a constantly incrementing group id.
static gint counter = 0;
return g_atomic_int_add (&counter, 1);
}
+
+/* Compute log2 of the passed 64-bit number by finding the highest set bit */
+static guint
+gst_log2 (GstClockTime in)
+{
+ const guint64 b[] =
+ { 0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000, 0xFFFFFFFF00000000LL };
+ const guint64 S[] = { 1, 2, 4, 8, 16, 32 };
+ int i;
+
+ guint count = 0;
+ for (i = 5; i >= 0; i--) {
+ if (in & b[i]) {
+ in >>= S[i];
+ count |= S[i];
+ }
+ }
+
+ return count;
+}
+
+/**
+ * gst_calculate_linear_regression:
+ * @xy: Pairs of (x,y) values
+ * @temp: Temporary scratch space used by the function
+ * @n: number of (x,y) pairs
+ * @m_num: (out): numerator of calculated slope
+ * @m_denom: (out): denominator of calculated slope
+ * @b: (out): Offset at Y-axis
+ * @xbase: (out): Offset at X-axis
+ * @r_squared: (out): R-squared
+ *
+ * Calculates the linear regression of the values @xy and places the
+ * result in @m_num, @m_denom, @b and @xbase, representing the function
+ * y(x) = m_num/m_denom * (x - xbase) + b
+ * that has the least-square distance from all points @x and @y.
+ *
+ * @r_squared will contain the remaining error.
+ *
+ * If @temp is not %NULL, it will be used as temporary space for the function,
+ * in which case the function works without any allocation at all. If @temp is
+ * %NULL, an allocation will take place. @temp should have at least the same
+ * amount of memory allocated as @xy, i.e. 2*n*sizeof(GstClockTime).
+ *
+ * <note>This function assumes (x,y) values with reasonable large differences
+ * between them. It will not calculate the exact results if the differences
+ * between neighbouring values are too small due to not being able to
+ * represent sub-integer values during the calculations.</note>
+ *
+ * Returns: %TRUE if the linear regression was successfully calculated
+ *
+ * Since: 1.12
+ */
+/* http://mathworld.wolfram.com/LeastSquaresFitting.html
+ * with SLAVE_LOCK
+ */
+gboolean
+gst_calculate_linear_regression (const GstClockTime * xy,
+ GstClockTime * temp, guint n,
+ GstClockTime * m_num, GstClockTime * m_denom,
+ GstClockTime * b, GstClockTime * xbase, gdouble * r_squared)
+{
+ const GstClockTime *x, *y;
+ GstClockTime *newx, *newy;
+ GstClockTime xmin, ymin, xbar, ybar, xbar4, ybar4;
+ GstClockTime xmax, ymax;
+ GstClockTimeDiff sxx, sxy, syy;
+ gint i, j;
+ gint pshift = 0;
+ gint max_bits;
+
+ g_return_val_if_fail (xy != NULL, FALSE);
+ g_return_val_if_fail (m_num != NULL, FALSE);
+ g_return_val_if_fail (m_denom != NULL, FALSE);
+ g_return_val_if_fail (b != NULL, FALSE);
+ g_return_val_if_fail (xbase != NULL, FALSE);
+ g_return_val_if_fail (r_squared != NULL, FALSE);
+
+ x = xy;
+ y = xy + 1;
+
+ xbar = ybar = sxx = syy = sxy = 0;
+
+ xmin = ymin = G_MAXUINT64;
+ xmax = ymax = 0;
+ for (i = j = 0; i < n; i++, j += 2) {
+ xmin = MIN (xmin, x[j]);
+ ymin = MIN (ymin, y[j]);
+
+ xmax = MAX (xmax, x[j]);
+ ymax = MAX (ymax, y[j]);
+ }
+
+ if (temp == NULL) {
+ /* Allocate up to 1kb on the stack, otherwise heap */
+ newx = n > 64 ? g_new (GstClockTime, 2 * n) : g_newa (GstClockTime, 2 * n);
+ newy = newx + 1;
+ } else {
+ newx = temp;
+ newy = temp + 1;
+ }
+
+ /* strip off unnecessary bits of precision */
+ for (i = j = 0; i < n; i++, j += 2) {
+ newx[j] = x[j] - xmin;
+ newy[j] = y[j] - ymin;
+ }
+
+#ifdef DEBUGGING_ENABLED
+ GST_CAT_DEBUG (GST_CAT_CLOCK, "reduced numbers:");
+ for (i = j = 0; i < n; i++, j += 2)
+ GST_CAT_DEBUG (GST_CAT_CLOCK,
+ " %" G_GUINT64_FORMAT " %" G_GUINT64_FORMAT, newx[j], newy[j]);
+#endif
+
+ /* have to do this precisely otherwise the results are pretty much useless.
+ * should guarantee that none of these accumulators can overflow */
+
+ /* quantities on the order of 1e10 to 1e13 -> 30-35 bits;
+ * window size a max of 2^10, so
+ this addition could end up around 2^45 or so -- ample headroom */
+ for (i = j = 0; i < n; i++, j += 2) {
+ /* Just in case assumptions about headroom prove false, let's check */
+ if ((newx[j] > 0 && G_MAXUINT64 - xbar <= newx[j]) ||
+ (newy[j] > 0 && G_MAXUINT64 - ybar <= newy[j])) {
+ GST_CAT_WARNING (GST_CAT_CLOCK,
+ "Regression overflowed in clock slaving! xbar %"
+ G_GUINT64_FORMAT " newx[j] %" G_GUINT64_FORMAT " ybar %"
+ G_GUINT64_FORMAT " newy[j] %" G_GUINT64_FORMAT, xbar, newx[j], ybar,
+ newy[j]);
+ return FALSE;
+ }
+
+ xbar += newx[j];
+ ybar += newy[j];
+ }
+ xbar /= n;
+ ybar /= n;
+
+ /* multiplying directly would give quantities on the order of 1e20-1e26 ->
+ * 60 bits to 70 bits times the window size that's 80 which is too much.
+ * Instead we (1) subtract off the xbar*ybar in the loop instead of after,
+ * to avoid accumulation; (2) shift off some estimated number of bits from
+ * each multiplicand to limit the expected ceiling. For strange
+ * distributions of input values, things can still overflow, in which
+ * case we drop precision and retry - at most a few times, in practice rarely
+ */
+
+ /* Guess how many bits we might need for the usual distribution of input,
+ * with a fallback loop that drops precision if things go pear-shaped */
+ max_bits = gst_log2 (MAX (xmax - xmin, ymax - ymin)) * 7 / 8 + gst_log2 (n);
+ if (max_bits > 64)
+ pshift = max_bits - 64;
+
+ i = 0;
+ do {
+#ifdef DEBUGGING_ENABLED
+ GST_CAT_DEBUG (GST_CAT_CLOCK,
+ "Restarting regression with precision shift %u", pshift);
+#endif
+
+ xbar4 = xbar >> pshift;
+ ybar4 = ybar >> pshift;
+ sxx = syy = sxy = 0;
+ for (i = j = 0; i < n; i++, j += 2) {
+ GstClockTime newx4, newy4;
+ GstClockTimeDiff tmp;
+
+ newx4 = newx[j] >> pshift;
+ newy4 = newy[j] >> pshift;
+
+ tmp = (newx4 + xbar4) * (newx4 - xbar4);
+ if (G_UNLIKELY (tmp > 0 && sxx > 0 && (G_MAXINT64 - sxx <= tmp))) {
+ do {
+ /* Drop some precision and restart */
+ pshift++;
+ sxx /= 4;
+ tmp /= 4;
+ } while (G_MAXINT64 - sxx <= tmp);
+ break;
+ } else if (G_UNLIKELY (tmp < 0 && sxx < 0 && (G_MAXINT64 - sxx >= tmp))) {
+ do {
+ /* Drop some precision and restart */
+ pshift++;
+ sxx /= 4;
+ tmp /= 4;
+ } while (G_MININT64 - sxx >= tmp);
+ break;
+ }
+ sxx += tmp;
+
+ tmp = newy4 * newy4 - ybar4 * ybar4;
+ if (G_UNLIKELY (tmp > 0 && syy > 0 && (G_MAXINT64 - syy <= tmp))) {
+ do {
+ pshift++;
+ syy /= 4;
+ tmp /= 4;
+ } while (G_MAXINT64 - syy <= tmp);
+ break;
+ } else if (G_UNLIKELY (tmp < 0 && syy < 0 && (G_MAXINT64 - syy >= tmp))) {
+ do {
+ pshift++;
+ syy /= 4;
+ tmp /= 4;
+ } while (G_MININT64 - syy >= tmp);
+ break;
+ }
+ syy += tmp;
+
+ tmp = newx4 * newy4 - xbar4 * ybar4;
+ if (G_UNLIKELY (tmp > 0 && sxy > 0 && (G_MAXINT64 - sxy <= tmp))) {
+ do {
+ pshift++;
+ sxy /= 4;
+ tmp /= 4;
+ } while (G_MAXINT64 - sxy <= tmp);
+ break;
+ } else if (G_UNLIKELY (tmp < 0 && sxy < 0 && (G_MININT64 - sxy >= tmp))) {
+ do {
+ pshift++;
+ sxy /= 4;
+ tmp /= 4;
+ } while (G_MININT64 - sxy >= tmp);
+ break;
+ }
+ sxy += tmp;
+ }
+ } while (i < n);
+
+ if (G_UNLIKELY (sxx == 0))
+ goto invalid;
+
+ *m_num = sxy;
+ *m_denom = sxx;
+ *b = (ymin + ybar) - gst_util_uint64_scale_round (xbar, *m_num, *m_denom);
+ /* Report base starting from the most recent observation */
+ *xbase = xmax;
+ *b += gst_util_uint64_scale_round (xmax - xmin, *m_num, *m_denom);
+
+ *r_squared = ((double) sxy * (double) sxy) / ((double) sxx * (double) syy);
+
+#ifdef DEBUGGING_ENABLED
+ GST_CAT_DEBUG (GST_CAT_CLOCK, " m = %g", ((double) *m_num) / *m_denom);
+ GST_CAT_DEBUG (GST_CAT_CLOCK, " b = %" G_GUINT64_FORMAT, *b);
+ GST_CAT_DEBUG (GST_CAT_CLOCK, " xbase = %" G_GUINT64_FORMAT, *xbase);
+ GST_CAT_DEBUG (GST_CAT_CLOCK, " r2 = %g", *r_squared);
+#endif
+
+ if (temp == NULL && n > 64)
+ g_free (newx);
+
+ return TRUE;
+
+invalid:
+ {
+ GST_CAT_DEBUG (GST_CAT_CLOCK, "sxx == 0, regression failed");
+ if (temp == NULL && n > 64)
+ g_free (newx);
+ return FALSE;
+ }
+}
projects / platform / upstream / gstreamer.git / blobdiff