July 24, 2014

Bastien NoceraWatch out for DRI3 regressions

(Bastien Nocera) DRI3 has plenty of necessary fixes for X.org and Wayland, but it's still young in its integration. It's been integrated in the upcoming Fedora 21, and recently in Arch as well.

If WebKitGTK+ applications hang or become unusably slow when an HTML5 video is supposed to be, you might be hitting this bug.

If Totem crashes on startup, it's likely this problem, reported against cogl for now.

Feel free to add a comment if you see other bugs related to DRI3, or have more information about those.

Update: Wayland is already perfect, and doesn't use DRI3. The "DRI2" structures in Mesa are just that, structures. With Wayland, the DRI2 protocol isn't actually used.

by Bastien Nocera (noreply@blogger.com) at July 24, 2014 01:47 AM

July 23, 2014

GStreamerGStreamer OpenMAX IL wrapper plugin 1.2.0 release


The GStreamer project is proud to announce a new release of the GStreamer OpenMAX IL wrapper plugin for the API and ABI-stable 1.x series of the GStreamer multimedia framework.

This plugin wraps available OpenMAX IL components and makes them available as standard GStreamer elements.

Check out the release notes for gst-omx, or download tarballs for gst-omx,

July 23, 2014 09:47 AM

July 22, 2014

Arun RaghavanQuick-start guide to gst-uninstalled for GStreamer 1.x

One of the first tools that you should get if you’re hacking with GStreamer or want to play with the latest version without doing evil things to your system is probably the gst-uninstalled script. It’s the equivalent of Python’s virtualenv for hacking on GStreamer. :)

The documentation around getting this set up is a bit frugal, though, so here’s my attempt to clarify things. I was going to put this on our wiki, but that’s a bit search-engine unfriendly, so probably easiest to just keep it here. The setup I outline below can probably be automated further, and comments/suggestions are welcome.

  • First, get build dependencies for GStreamer core and plugins on your distribution. Commands to do this on some popular distributions follow. This will install a lot of packages, but should mean that you won’t have to play find-the-plugin-dependency for your local build.

    • Fedora: $ sudo yum-builddep gstreamer1-*
    • Debian/Ubuntu: $ sudo apt-get build-dep gstreamer1.0-plugins-{base,good,bad,ugly}
    • Gentoo: having the GStreamer core and plugin packages should suffice
    • Others: drop me a note with the command for your favourite distro, and I’ll add it here
  • Next, check out the code (by default, it will turn up in ~/gst/master)

    • $ curl http://cgit.freedesktop.org/gstreamer/gstreamer/plain/scripts/create-uninstalled-setup.sh | sh
    • Ignore the pointers to documentation that you see — they’re currently defunct
  • Now put the gst-uninstalled script somewhere you can get to it easily:

    • $ ln -sf ~/gst/master/gstreamer/scripts/gst-uninstalled ~/bin/gst-master
    • (the -master suffix for the script is important to how the script works)
  • Enter the uninstalled environment:

    • $ ~/bin/gst-master
    • (this puts you in the directory with all the checkouts, and sets up a bunch of environment variables to use your uninstalled setup – check with echo $GST_PLUGIN_PATH)
  • Time to build

    • $ ./gstreamer/scripts/git-update.sh
  • Take it out for a spin

    • $ gst-inspect-1.0 filesrc
    • $ gst-launch-1.0 playbin uri=file:///path/to/some/file
    • $ gst-discoverer-1.0 /path/to/some/file
  • That’s it! Some tips:

    • Remember that you need to run ~/bin/gst-master to enter the environment for each new shell
    • If you start up a GStreamer app from your system in this environment, it will use your uninstalled libraries and plugins
    • You can and should periodically update you tree by rerunning the git-update.sh script
    • To run gdb on gst-launch, you need to do something like:
    • $ libtool --mode=execute gdb --args gstreamer/tools/gst-launch-1.0 videotestsrc ! videoconvert ! xvimagesink
    • I find it useful to run cscope on the top-level tree, and use that for quick code browsing

by Arun at July 22, 2014 06:43 PM

Zeeshan AliGUADEC

(Zeeshan Ali)
So its that time of the year! GUADEC is always loads of fun and meeting all those the awesome GNOME contributors in person and listening to their exciting stories and ideas gives me a renewed sense of motivation.

I have two regular talks this year:
  • Boxes: All packed & ready to go?
  • Geo-aware OS: Are we there yet?
Apart from that I also intend to present a lightning talk titled "Examples to follow". This talk will present stories of few of our awesome GNOME contributors and what we all can learn from them.

July 22, 2014 12:11 AM

July 19, 2014

GStreamerGStreamer Core, Plugins and RTSP server 1.4.0 stable release


The GStreamer team is pleased to announce the first release of the stable 1.4 release series. The 1.4 release series is adding new features on top of the 1.0 and 1.2 series and is part of the API and ABI-stable 1.x release series of the GStreamer multimedia framework.

Binaries for Android, iOS, Mac OS X and Windows are provided together with this release.

The stable 1.4 release series is API and ABI compatible with 1.0.x, 1.2.x and any other 1.x release series in the future. Compared to 1.2.x it contains some new features and more intrusive changes that were considered too risky as a bugfix.

Check out the release notes for GStreamer core, gst-plugins-base, gst-plugins-good, gst-plugins-ugly, gst-plugins-bad, gst-libav, or gst-rtsp-server, or download tarballs for gstreamer, gst-plugins-base, gst-plugins-good, gst-plugins-ugly, gst-plugins-bad, or gst-libav, or gst-rtsp-server.

Check the release announcement mail for details and the release notes above for a list of changes.

Also available are binaries for Android, iOS, Mac OS X and Windows.

July 19, 2014 05:00 PM

Phil NormandMoving to Pelican

(Phil Normand)

Time for a change! Almost 10 years ago I was starting to hack on a Blog engine with two friends, it was called Alinea and it powered this website for a long time. Back then hacking on your own Blog engine was the pre-requirement to host your blog :) But nowadays people just use Wordpress or similar platforms, if they still have a blog at all. Alinea fell into oblivion as I didn’t have time and motivation to maintain it.

Moving to Pelican was quite easy, since I’ve been writing content in ReST on the previous blog I only had to pull data from the database and hacked pelican_import.py a bit :)

Now that this website looks almost modern I’ll hopefully start to blog again, expect at least news about the WebKit work I still enjoy doing at Igalia.

by Philippe Normand at July 19, 2014 02:13 PM

July 16, 2014

Thomas Vander Stichelemorituri 0.2.3 ‘moved’ released!

(Thomas Vander Stichele)

It’s two weeks shy of a year since the last morituri release. It’s been a pretty crazy year for me, getting married and moving to New York, and I haven’t had much time throughout the year to do any morituri hacking at all. I miss it, and it was time to do something about it, especially since there’s been quite a bit of activity on github since I migrated the repository to it.

I wanted to get this release out to combine all of the bug fixes since the last release before I tackle one of the number one asked for issues – not ripping the hidden track one audio if it’s digital silence. There are patches floating around that hopefully will be good enough so I can quickly do another release with that feature, and there are a lot of minor issues that should be easy to fix still floating around.

But the best way to get back into the spirit of hacking and to remove that feeling of it’s-been-so-long-since-a-release-so-now-it’s-even-harder-to-do-one is to just Get It Done.

I look forward to my next hacking stretch!

Happy ripping everybody.

flattr this!

by Thomas at July 16, 2014 04:01 AM

July 12, 2014

GStreamerGStreamer Core, Plugins and RTSP server 1.3.91 release candidate


The GStreamer team is pleased to announce the second release candidate of the stable 1.4 release series. The 1.4 release series is adding new features on top of the 1.0 and 1.2 series and is part of the API and ABI-stable 1.x release series of the GStreamer multimedia framework.

This release candidate will hopefully shortly be followed by the stable 1.4.0 release if no bigger regressions or bigger issues are detected, and enough testing of the release candidate happened. The new API that was added during the 1.3 release series is not expected to change anymore at this point.

Binaries for Android, iOS, Mac OS X and Windows are provided together with this release.

The stable 1.4 release series is API and ABI compatible with 1.0.x, 1.2.x and any other 1.x release series in the future. Compared to 1.2.x it contains some new features and more intrusive changes that were considered too risky as a bugfix.

Check out the release notes for GStreamer core, gst-plugins-base, gst-plugins-good, gst-plugins-ugly, gst-plugins-bad, gst-libav, or gst-rtsp-server, or download tarballs for gstreamer, gst-plugins-base, gst-plugins-good, gst-plugins-ugly, gst-plugins-bad, or gst-libav, or gst-rtsp-server.

Check the release announcement mail for details and the release notes above for a list of changes.

Also available are binaries for Android, iOS, Mac OS X and Windows.

July 12, 2014 05:00 PM

July 10, 2014

Christian SchallerDesktop Containers – The Way Forward

(Christian Schaller)

One feature we are spending quite a bit of effort in around the Workstation is container technologies for the desktop. This has been on the wishlist for quite some time and luckily the pieces for it are now coming together. Thanks to strong collaboration between Red Hat and Docker we have a great baseline to start from. One of the core members of the desktop engineering team, Alex Larsson, has been leading the Docker integration effort inside Red Hat and we are now preparing to build onwards on that work, using the desktop container roadmap created by Lennart Poettering.

So while Lennarts LinuxApps ideas predates Docker they do provide a great set of steps we need to turn Docker into a container solution not just for server and web applications, but also for desktop applications. And luckily a lot of the features we need for the desktop are also useful for the other usecases, for instance one of the main things Red Hat has been working with our friends at Docker on is integrating systemd with Docker.

There are a set of other components as part of this plan too. One of the big ones is Wayland, and I assume that if you are reading this you
have already seen my Wayland in Fedora updates.

Two other core technologies we identified are kdbus and overlayfs. Alex Larsson has already written an overlayfs backend for Docker, and Fedora Workstation Steering committee member, Josh Bowyer, just announced the availability of a Copr which includes experimental kernels for Fedora with overlayfs and kdbus enabled.

In parallel with this, David King has been prototyping a version of Cheese that can be run inside a container and that uses this concept that in the LinuxApps proposal is called ‘Portals’, which is basically dbus APIs for accessing resources outside the container, like the webcam and microphone in the case of Cheese. For those interested he will be presenting on his work at GUADEC at the end of the Month, on Monday the 28th of July. The talk is called ‘Cheese: TNG (less libcheese, more D-Bus)’

So all in all the pieces are really starting to come together now and we expect to have some sessions during both GUADEC and Flock this year to try hammer out the remaining details. If you are interested in learning more or join the effort be sure to check the two conferences notice boards for time and place for the container sessions.

There is still a lot of work to do, but I am confident we have the right team assembled to do it. In addition to the people already mentioned we for instance have Allan Day who is kicking off an effort to look at the user experience we want to provide around the container hosted application bundles in terms of upgrades and installation for instance. And we will also work with the wider Docker community to make sure we have great composition tools for creating these container images available for developers on Fedora.

by uraeus at July 10, 2014 08:48 AM

July 04, 2014

Christian SchallerTransmageddon 1.2 ‘All bugs must die’

(Christian Schaller)

Update: I had actually managed to disable the VAAPI encoding in 1.2, so I just rolled a 1.3 release which re-enabled it. Apart from that it is identical

So I finally managed to put out a new Transmageddon release today. It is primarily a bugfix release, but considering how many critical bugs I ended up fixing for this release I am actually a bit embarassed about my earlier 1.x releases. There was for instances some stupidity in my code that triggered thread safety issues, which I know hit some of my users quite badly. But there were other things not working properly either, like dropping the video stream from a file. Anyway, I know some people think that filing bugs doesn’t help, but I think I fixed every reported Transmageddon bug with this release (although not every feature request bugzilla item). So if you have issues with Transmageddon 1.2 please let me know and I will try my best to fix them. I do try to keep a policy that it is better to have limited functionality, but what is there is solid as opposed to have a lot of features that are unreliable or outright broken.

That said I couldn’t help myself so there are a few new features in this release. First of all if you have the GStreamer VAAPI plugins installed (and be sure to have the driver too) then the VAAPI GPU encoder will be used for h264 and MPEG2.

Secondly I brought back the so called ‘xvid’ codec (even though xvid isn’t really a separate codec, but a name used to refer to MPEG4 Video codec using the advanced-simple profile.).

So as screenshot blow shows, there is not a lot of UI changes since the last version, just some smaller layout and string fixes, but stability is hopefully greatly improved.

I am currently looking at a range of things as the next feature for Transmageddon including:

  • Batch transcoding, allowing you to create a series of transcoding jobs upfront instead of doing the transcodes one by one
  • Advanced settings panel, allowing you to choose which encoders to use for a given format, what profiles to use, turn deinterlacing on/off and so on
  • Profile generator, create new device profiles by inspecting existing files
  • Redo the UI to switch away from deprecated widgets

If you have any preference for which I should tackle first feel free to let me know in the comments and I will try to allow
popular will decide what I do first :)

P.S. I would love to have a high contrast icon for Transmageddon (HighContrast App icon guidelines) – So if there is any graphics artists out there willing to create one for me I would be duly greatful

by uraeus at July 04, 2014 08:47 AM

July 03, 2014

Christian SchallerWayland in Fedora Update

(Christian Schaller)

As we are approaching Fedora Workstation 21 we held a meeting to review our Wayland efforts for Fedora Workstation inside Red Hat recently. Switching to a new core technology like Wayland is a major undertaking and there are always big and small surprises that comes along the way. So the summary is that while we expect to have a version of Wayland in Fedora Workstation 21 that will be able to run a fully functional desktop, there are some missing pieces we now know that will not make it. Which means that since we want to ship at least one Fedora release with a feature complete Wayland as an option before making it default, that means that Fedora Workstation 23 is the earliest Wayland can be the default.

Anyway, here is what you can expect from Wayland in Fedora 21.

  • Wayland session available in GDM (already complete and fully working)
  • XWayland working, but without accelerated 3D (done, adding accelerated 3D will be done before FW 22)
  • Wayland session working with all free drivers (Currently only Intel working, but we expect to have NVidia and AMD support enabled before F21)
  • IBUS input working. (Using the IBUS X client. Wayland native IBUS should be ready for FW22.)
  • Touchpad acceleration working. (Last missing piece for a truly usable Wayland session, lots of work around libinput and friends currently to have it ready for F21).
  • Wacom tablets will not be ready for F21
  • 3D games should work using the Wayland backend for SDL2. SDL1 games will need to wait for FW22 so they can use the accelerated XWayland support).
  • Binary driver support from NVidia and AMD very unlikely to be ready for F21.
  • Touch screen support working under Wayland.

We hope to have F21 testbuilds available soon that the wider community can use to help us test, because even when all the big ‘checkboxes’ are filled in there will of course be a host of smaller issues and outright bugs that needs ironing out before Wayland is ready to replace X completely. We really hope the community will get involved with testing Wayland so that we can iron out all major bugs before F21.

How to get involved with the Fedora Workstaton effort

To help more people get involved we recently put up a tasklist for the Fedora Workstation. It is a work in progress, but we hope that it will help more people get involved and help move the project forward.

UpdatePeter Hutterer posted this blog entry explaining pointer acceleration and what are looking at to improve it.

by uraeus at July 03, 2014 02:55 PM

July 02, 2014

Jean-François Fortin TamVenez nombreux à GUADEC!

Pour la première fois depuis quatorze ans, la conférence GUADEC fait son retour en France. Je vous encourage à venir nombreux à cet événement qui se tiendra à Strasbourg durant la dernière semaine de Juillet. Je dois traverser l’Atlantique (à la nage), prendre plusieurs avions et autobus pour y aller, alors pas d’excuses pour ceux situés à moins de 6000 km!

“GUADEC, ça a un intérêt pour quelqu’un qui n’est pas un développeur?”

La majorité des présentations (voir le programme qui sera publié sous peu) est à la portée du grand public avec un penchant geek, du moment que vous ayiez un fort intérêt/curiosité pour les technologies impliquées. On n’y retrouve habituellement pas Gaspard le boulanger ou Amélie la chirurgienne, mais tous sont les bienvenus. Après tout, GUADEC signifie “GNOME Users and Developers European Conference”!

GUADEC 2013 interns lightning talks, by Ana Rey

(photo par Ana Rey)

Les présentateurs axent souvent leur présentation autour des avancées récentes de leur logiciel, le design et l’expérience utilisateur, la direction générale d’un projet donné, etc. Bien sûr, plusieurs sujets restent à teneur assez technique, mais je crois que ceux qui lisent Planet Libre, Planet GNOME ou Linux FR sont déjà assez à l’affut pour comprendre le contenu. L’événement étant une conférence internationale, il faut toutefois avoir une compréhension correcte de l’anglais puisque c’est la langue utilisée lors des présentations.

Outre les présentations magistrales, il y a aussi les hackfests informels et sessions BoFs (“birds of a feather”), où des petits groupes se forment autour de thématiques particulières. Par exemple, il y a traditionnellement un hackfest pour Pitivi en présence des développeurs de GStreamer, étudiants GSoC et autres membres de la communauté intéressés. Amenez votre ordinateur et votre bonne humeur!

Bref, GUADEC reste beaucoup plus “accessible” aux non-devs que le GNOME Summit, ce dernier étant un événement très technique, plus proche d’un méga-hackfest.

“Que faire en tant que non-développeur?”

  • Rencontrer les contributeurs qu’on ne connaissait que de nom depuis des années, que ce soit dans les corridors ou dans les événements (généralement il y a au moins une ou deux soirées organisées).
  • Écouter des présentations en personne, poser des questions ou débattre.
  • Pourchasser nos développeurs préférés et discuter de nos bugs favoris. Pour reproduire un bug complexe à reproduire, ou simplement pour faire en sorte que le développeur se penche sur la question en investiguant en temps réel, il n’y a rien de mieux.
  • Discuter poliment de design sans avoir à écrire des pavés ou risquer des malentendus à cause du manque richesse des interactions textuelles.
  • Jouer le rôle de reporter et faire de la couverture médiatique de l’événement.
  • Rencontrer de nouveaux contributeurs, surtout les étudiants GSoC.
  • Participer aux sessions BoF (“birds of a feather”), notamment Le Pitivi Hackfest 2014.
  • Affronter Bastien Nocera au foot.

J’espère vous voir nombreux à cet événement incontournable!

by nekohayo at July 02, 2014 04:57 PM

July 01, 2014

Andy Wingoflow analysis in guile

(Andy Wingo)

Greets, and welcome back to the solipsism! I've been wandering the wilderness with my Guile hackings lately, but I'm finally ready to come back to civilization. Hopefully you will enjoy my harvest of forest fruit.

Today's article is about flow analysis and data structures. Ready? Let's rock!

flow analysis

Many things that a compiler would like to know can be phrased as a question of the form, "What do I know about the data flowing through this particular program point?" Some things you might want to know are:

  1. The set of variables that must be live.

  2. The set of variables that happen to be live. This is the same as (1) except it includes variables that aren't needed but haven't been clobbered by anything.

  3. The set of expressions whose results are still valid (i.e., haven't been clobbered by anything else).

  4. An upper and lower bound on the range of numeric variables.

Et cetera. I'll talk about specific instances of flow analysis problems in the future, but today's article is a bit more general.

The first thing to note about these questions is that they don't necessarily need or have unique answers. If GCC decides that it can't prove anything about the ranges of integers in your program, it's not the end of the world -- it just won't be able to do some optimizations that it would like to do.

At the same time, there are answers that are better and worse than others, and answers that are just invalid. Consider a function of the form:

int f():
  int a = 1
  int b = 2
  int c = a + b
  int d = b + c
  int z = x + y
  return z

In this function, there are 27 different expressions, including the return, and 27 different program points. (You can think of a program point as a labelled sub-expression. In this example none of the expressions have sub-expressions.) If we number the program points in order from 0 to 26, we will have a program that first executes expression 0 (int a = 1), then 1, and so on to the end.

Let's plot some possible solutions to the live variable flow-analysis problem for this program.

Here we see two solutions to the problem (in light and dark blue), along with a space of invalid solutions (in red). The Y axis corresponds to the variables of the program, starting with a on the bottom and finishing with z on the top.

For example, consider position 4 in the program, corresponding to int e = c + d. It is marked in the graph with a vertical bar. After position 4, the only values that are used in the rest of the program are d and e. These are the variables that are contained within the light-blue area. It wouldn't be invalid to consider a, b, and c to be live also, but it also wouldn't be as efficient to allocate space and reason about values that won't contribute to the answer. The dark blue space holds those values that may harmlessly be considered to be live, but which actually aren't live.

It would, however, be invalid to consider the variable f to be live after position 4, because it hasn't been defined yet. This area of the variable space is represented in red on the graph.

Of course, the space of all possible solutions isn't possible to represent nicely on a two-dimensional graph; we're only able to show two with colors, and that not very well as they overlap. This difficulty cuts close to the heart of the data-flow problem: that it ultimately requires computing a two-dimensional answer, which necessarily takes time and space O(n2) in program size.

Or does it?

classical flow analysis frameworks

The classical way to do flow analysis is to iterate a set of data-flow equations over an finite lattice until you reach a fixed point.

That's a pithy sentence that deserves some unpacking. If you're already comfortable with what it means, you can skip a couple sections.

Still here? Cool, me too. Let's take a simple example of sign analysis. The problem is to determine, for the integer variables of a program, at every point in the program, which ones may be negative (-), which ones may be zero (0), and which may be positive (+). All of these are conceptually bit-flags.

For example, in this program:

int f(int x):
 L0:  while (x >= 0)
 L1:    int y = x - 1
 L2:    x = y
 L3:  return x

We can assign the flags -0+ to the argument x as the initial state that flows into L0, because we don't know what it is ahead of time, and it is the only variable in scope. We start by representing the initial state of the solution as a set of sets of state values:

state := {L0: {x: -0+}, L1: Ø, L2: Ø, L3: Ø}

In this notation, Ø indicates a program point that hasn't been visited yet.

Now we iterate through all labels in the program, propagating state to their successors. Here is where the specific problem being solved "hooks in" to the generic classical flow analysis framework: before propagating to a successor, a flow equation transforms the state that flows into a program point to a state that flows out, to the particular successor. In this case we could imagine equations like this:

visit_test(expr, in, true_successor, false_successor):
  if expr matches "if var >= 0":
    # On the true branch, var is not negative.
    propagate(in + {var: in[var] - -}, true_successor)
    # On the false branch, var is not zero and not positive.
    propagate(in + {var: in[var] - 0+}, false_successor)
  else if ...

visit_expr(expr, in, successor):
  if expr matches "left = right - 1":
    if in[right] has +:
      if in[right] has 0:
        # Subtracting one from a non-negative arg may be negative.
        propagate(in + {left: in[right] + -}, successor)
        # Subtracting one from a positive arg may be 0.
        propagate(in + {left: in[right] + 0}, successor)
      # Subtracting one from a nonpositive arg will be negative.
      propagate(in + {left: -}, successor)
  else if expr matches "left = right":
    propagate(in + {left: in[right]}, successor)

The meat of classical data-flow analysis is the meet operation:

propagate(out, successor):
  if state[successor] is Ø:
    state[successor] = out
    state[successor] = meet(out, state[successor]):

# A version of meet for sign analysis
meet(out, in):
  return intersect_vars_and_union_values(out, in)

Let's run this algorithm by hand over the example program. Starting from the initial state, we propagate the L0→L1 and L0→L3 edges:

visit_test("if x <= 0", {x: -0+}, L1, L3)
→ propagate({x: 0+}, L1)
→ state[L1] = {x: 0+}
→ propagate({x: -}, L3)
→ state[L3] = {x: -}

Neat. Let's keep going. The successor of L1 is L2:

visit_expr("y = x - 1", {x: 0+}, L2)
→ propagate({x: 0+, y: -0+}, L2)
→ state[L1] = {x: 0+, y: -0+}

L2→L0 is a back-edge, returning to the top of the loop:

visit_expr("x = y", {x: 0+, y: -0+}, L0)
→ propagate({x: -0+, y: -0+}, L0)
→ state[L0] = meet({x: -0+, y: -0+}, state[L0])
→ state[L0] = meet({x: -0+, y: -0+}, {x: -0+})
→ state[L0] = {x: 0+}

Finally, L3 has no successors, so we're done with this iteration. The final state is:

{L0: {x: -0+},
 L1: {x: 0+},
 L2: {x: 0+, y: -0+},
 L3: {x: -}}

which indeed corresponds with what we would know intuitively.

fixed points and lattices

Each of the steps in our example flow analysis was deterministic: the result was calculated from the inputs and nothing else. However the backwards branch in the loop, L2→L0, could have changed inputs that were used by the previous L0→L1 and L0→L3 forward edges. So what we really should do is iterate the calculation to a fixed point: start it over again, and run it until the state doesn't change any more.

It's easy to see in this case that running it again won't end up modifying the state. But do we know that in all cases? How do we know that iteration would terminate at all? It turns out that a few simple conditions are sufficient.

The first thing to ensure is that state space being explored is finite. Here we can see this is the case, because there are only so many ways you can combine -, 0, and +. Each one may be present or not, and so we have 2n = 23 = 8 possible states. The elements of the state array will be a set with at most one entry for each variable, so the whole state space is finite. That at least ensures that an answer exists.

Next, the "meet" operation has to be commutative, associative, and idempotent. The above example used intersect_vars_and_union_values. We intersect vars because it only makes sense to talk about a variable at a program point if the variable dominates the program point. It didn't make sense to propagate y on the L2→L0 branch, for example. It's usually a good idea to model a data-flow problem using sets, as set union and intersection operations fulfill these commutative, associative, and distributive requirements.

Finally, the state being modelled should have a partial order, and functions that add information along control-flow edges -- above, visit_test and visit_expr -- should preserve this partial ordering. That is to say, visit_test and visit_expr should be monotonic. This means that no matter on what control paths data propagates, we keep building towards an answer with more information, making forward progress. This condition is also easily fulfilled with sets, or more generally with any lattice. (A lattice is nothing more than a data type that fulfills these conditions.)

Iterating the data-flow equations until the state stops changing will find a fixed point of the lattice. Whether you find the greatest or least fixed point is another question; I can't help linking to Paul Khuong's old article on Québécois student union strikes for a lovely discussion.

Another question is, how many iterations are necessary to reach a fixed point? I would first note that although in our walk-through we iterated in forward order (L0, L1, L2, L3), we could have visited nodes in any order and the answer would be the same. I'll cut to the chase and say that if:

  1. you represent your state with bitvectors

  2. the control-flow graph is reducible (has only natural loops)

  3. the meet operation on values is bitvector union or intersection

  4. you visit the program points in topologically sorted order

If these conditions are fulfilled, then you will reach a fixed point after LC + 2 iterations, where LC is the "loop-connectness number" of your graph. You can ensure (1), (3), and (4) by construction. (Reverse post-order numbering is an easy way to fulfill (4).) (2) can be ensured by using programming languages without goto (a for loop is always a natural loop) but can be violated by optimizing compilers (for example, via contification).

Loop connectedness is roughly equivalent to the maximum nesting level of loops in the program, which has experimentally been determined to rarely exceed 3. Therefore in practice, data-flow analysis requires a number of steps that is O(n * 5) = O(n) in program size.

For more information on data-flow analysis, including full proofs and references, see Carl Offner's excellent, excellent manuscript "Notes on Graph Algorithms used in Optimizing Compilers". I don't know of any better free resource than that. Thanks, Carl!

an aside: the kCFA algorithms

I just finished describing what I called "classical" data-flow analysis. By that I mean to say that people have been doing it since the 1970s, which is classical enough as far as our industry goes. However with the rise of functional languages in the 1980s, it became unclear how to apply classical data-flow analysis on a language like Scheme. Let's hear it from the horse's mouth:

This brings us to the summer of 1984. The mission was to build the world's most highly-optimising Scheme compiler. We wanted to compete with C and Fortran. The new system was T3, and the compiler was to be called Orbit. We all arrived at WRL and split up responsibility for the compiler. Norman was going to do the assembler. Philbin was going to handle the runtime (as I recall). Jonathan was project leader and (I think) wrote the linker. Kranz was to do the back end. Kelsey, the front end. I had passed the previous semester at CMU becoming an expert on data-flow analysis, a topic on which I completely grooved. All hot compilers do DFA. It is necessary for all the really cool optimisations, like loop-invariant hoisting, global register allocation, global common subexpression elimination, copy propagation, induction-variable elimination. I knew that no Scheme or Lisp compiler had ever provided these hot optimisations. I was burning to make it happen. I had been writing 3D graphics code in T, and really wanted my floating-point matrix multiplies to get the full suite of DFA optimisation. Build a DFA module for T, and we would certainly distinguish ourselves from the pack. So when we divided up the compiler, I told everyone else to back off and loudly claimed DFA for my own. Fine, everyone said. You do the DFA module. Lamping signed up to do it with me.

Lamping and I spent the rest of the summer failing. Taking trips to the Stanford library to look up papers. Hashing things out on white boards. Staring into space. Writing little bits of experimental code. Failing. Finding out *why* no one had ever provided DFA optimisation for Scheme. In short, the fundamental item the classical data-flow analysis algorithms need to operate is not available in a Scheme program. It was really depressing. I was making more money than I'd ever made in my life ($600/week). I was working with *great* guys on a cool project. I had never been to California before, so I was discovering San Francisco, my favorite city in the US and second-favorite city in the world. Silicon Valley in 1984 was beautiful, not like the crowded strip-mall/highway hell hole it is today. Every day was perfect and beautiful when I biked into work. I got involved with a gorgeous redhead. And every day, I went in to WRL, failed for 8 hours, then went home.

It was not a good summer.

At the end of the summer, I slunk back to CMU with my tail between my legs, having contributed not one line of code to Orbit.

Olin Shivers, A history of T

It took him another 7 years, but Shivers stuck with it, and in the end came out with the family of algorithms known as k-CFA. Instead of focusing on loops, which Scheme doesn't have syntactically, Shivers used continuation-passing style to ruthlessly simplify Scheme into a dialect consisting of not much more than function calls, and focused his attention on function calls. The resulting family of flow algorithms can solve flow equations even in the presence of higher-order functions -- a contribution to computer science born out of necessity, failure, and stubbornness.

With all those words, you'd think that I'd be itching to use k-CFA in Guile, and I'm not. Unfortunately even the simplest, least expressive version (0-CFA) is O(n2); 1-CFA is exponential. I don't have time for that. Instead, Guile is able to use classical DFA because it syntactically distinguishes labelled continuations and functions, and contifies functions to continuations where possible, which makes the Scheme DFA problem exactly the same as in any other language.

n times what?

Now that we have established that the number of visit operations is O(n), it remains to be seen what the individual complexity of a visit operation is in order to determine the total complexity. The naïve thing is just to use bitvectors, with each of the bitvectors having as many entries as the program has variables, times however many bits we are using.

This leads to O(|L|*|V|) space and time complexity, where |L| is the number of program points (labels) and |V| is the number of variables. As the number of variables is generally proportional to the size of program, we can approximate this as O(n2).

In practice, this means that we can use data-flow analysis to programs up to about 10000 labels in size. Sign analysis on a 10000-label function would require 100002*3/8 = 37.5 MB of memory, which is already a bit hefty. It gets worse if you need to represent more information. I was recently doing some flow-sensitive type and range inference, storing 12 bytes per variable per program point; for a 10000-label function, that's more than a gigabyte of memory. Badness.

shared tails

Although it was the type inference case that motivated this investigation, sign inference is similar and more simple so let's go with that. The visit_expr and visit_test functions above are only ever going to add additional information about the variables that are used in or defined by an expression; in practice this is a small finite number. What if we chose a representation of state that could exploit this fact by only adding O(1) amounts of data, sharing a common tail with preceding expressions?

If we draw a control-flow graph for the sign analysis program, we get something like:

The goal is to create a data structure that looks like the dominator tree. For "normal" control-flow edges -- those whose destination only have one predecessor -- we can avoid the "meet" operations, and just copy the predecessor's out set to the successor's in set. We then define "meet" as an adjoin operation that effectively conses the new information onto a shared tail, if it wasn't there already. The first iteration through the CFG will initialize the shared tail of a given control-flow join to the set of variables flowing into the join's dominator. Subsequent information will adjoin (cons) on new incoming values. In this case the resulting data structure ends up looking like:

Here the italic references like L1 indicate shared structure, and the tuples annotating the edges represent additional information flow, beyond that information that was already present in the successor's dominator.

Of course, you can implement this with linked lists and it will work fine. The problem there will be lookup speed -- when your visit operation (visit_expr or visit_test) goes to look up the sign of a variable, or the same happens via the meet operation, you get O(n) lookup penalties. Anticipating this, I implemented this with a version of Phil Bagwell's vhashes, which promise O(log n) variable lookup. See Guile's documentation, or Bagwell's excellent paper.

Note that you can't remove items from sets once they have been added in a shared-tail flow analysis; to keep the meet function monotonic, you have to instead insert tombstone entries. Not so nice, but it is what it is.

A shared-tail flow analysis consumes only O(1) additional memory per node, leading to O(n) space complexity. I have some measured space and time graphs below that show this experimentally as well.

space and time

Unfortunately, lookup time on branchy vhashes is really terrible: O(log n) in the best case, and O(n) at worst. This is especially acute because there is no easy way to do unions or intersections on vhashes -- you end up having to compute the unshared heads of the two vhashes you are merging, and looking up elements in one in the other... I could go on, but I think you believe me when I say it gets complicated and slow. It's possible to beat a bitvector approach in time for relatively "big" problems like type analysis, but for common subexpression elimination where I was just storing a bit per expression, it was tough to beat the speed of bitvectors.

I started looking for another solution, and in the end came on a compromise that I am much happier with, and again it's Phil Bagwell to the rescue. Instead of relying on vhashes that explicitly share state, I use Clojure-style persistent sparse bit-sets and bit-maps that share state opportunistically.

Guile's intset module implements a bitvector as a functional tree whose branches are vectors and whose leaves are fixnums. Each leaf represents one range of 32 integers, and each branch on top of it increases the range by a factor of 8. Branches can be sparse, so not all integers in the range of an intset need leaves.

As you would expect, adjoining an element onto such a tree is O(log n). Intersecting is much faster than vhashes though, as intsets partition the key space into power-of-two blocks. Intsets try hard to share state, so that if your adjoin would return the same value, the result is the same object, at the same address. This allows sub-trees to be compared for equality via pointer comparison, which is a great fast-path for intersection and union.

Likewise, Guile's new intmap module allow the association of larger values with integer keys.

science! fetch your white coats and lab books!

I had the chance to actually test the system with all three of these data structures, so I compiled one of Guile's bigger files and recorded the memory used and time taken when solving a 1-bit flow analysis problem. This file has around 600 functions, many of them small nested functions, many of them macro-generated, some of them quite loopy, and one big loopless one (6000 labels) to do the initialization.

First, a plot of how many bytes are consumed per label during while solving this 1-bit DFA.

Note that the X axis is on a log scale.

The first thing that pops out at me from these graphs is that the per-label overhead vhash sizes are indeed constant. This is a somewhat surprising result for me; I thought that iterated convergence would make this overhead depend on the size of the program being compiled.

Secondly we see that the bitvector approach, while quadratic in overall program size, is still smaller until we get to about 1000 labels. It's hard to beat the constant factor for packed bitvectors! Note that I restricted the Y range, and the sizes for the bitvector approach are off the charts for N > 1024.

The intset size is, as we expected, asymptotically worse than vhashes, but overall not bad. It stays on the chart at least. Surprisingly, intsets are often better than vhashes for small functions, where we can avoid allocating branches at all -- note the "shelves" in the intset memory usage, at 32 and 256 entries, respectively, corresponding to the sizes that require additional levels in the tree. Things keep on rising with n, but sublinearly (again, recall that the X axis is on a log scale).

Next, a plot of how many nanoseconds it takes per label to solve the DFA equation above.

Here we see, as expected, intsets roundly beating vhashes for all n greater than about 200 or so, and show sublinear dependence on program size.

The good results for vhashes for the largest program are because the largest program in this file doesn't have any loops, and hardly any branching either. It's the best case for vhashes: all appends and no branches. Unfortunately, it's not the normal case.

It's not quite fair to compare intsets to bitvectors, as Guile's bitvectors are implemented in C and intsets are implemented in Scheme, which runs on a bytecode VM right now. But still, the results aren't bad, with intsets even managing to beat bitvectors for the biggest function. The gains there probably pay for the earlier losses.

This is a good result, considering that the goal was to reduce the space complexity of the algorithm. The 1-bit case is also the hardest case; when the state size grows, as in type inference, the gains of using structure-sharing trees grow accordingly.


Let's wrap up this word-slog. A few things to note.

Before all this DFA work in Guile, I had very little appreciation of the dangers of N-squared complexity. I mean, sometimes I had to to think about it, but not often, expecially if your constant factors are low, or so I thought. But I got burned by it; hopefully the next time, if any, will be a long time coming.

I was happily, pleasantly surprised at the expressiveness and power of Bagwell/Clojure-style persistent data structures when applied to the kinds of problems that I work on. Space-sharing can make a fundamental difference to the characteristics of an algorithm, and Bagwell's data structures can do that well. Intsets simplified my implementations because I didn't have to reason much about space-sharing on my own -- finding the right shared tail for vhashes is, as I said, an unmitigated mess.

Finally I would close by saying that I was happy to fail in such interesting (to me) ways. It has been a pleasant investigation and I hope I have been able to convey some of the feeling of it. If you want to see what the resulting algorithm looks like in practice, see compute-truthy-expressions.

Until next time, happy hacking!

by Andy Wingo at July 01, 2014 08:00 AM

June 29, 2014

Thomas Vander Stichelemach 1.0.3 ‘moved’ released

(Thomas Vander Stichele)

It’s been very long since I last posted something. Getting married, moving across the Atlantic, enjoying the city, it’s all taken its time. And the longer you don’t do something, the harder it is to get back into.

So I thought I’d start simple – I updated mach to support Fedora 19 and 20, and started rebuilding some packages.

Get the source, update from my repository, or wait until updates hit the Fedora repository.

Happy packaging!

flattr this!

by Thomas at June 29, 2014 09:09 PM

Jean-François Fortin TamMyPaint + Wacom screen tablet + GNOME3 = ♥

A little-known fact about me is that I can draw better than your average cat. It is a hobby of mine that became dormant with my pretty challenging professional and Free Software activities in the past few years.

Drawing is hard, let’s go hacking

One of the things that previously threw me off from drawing more is the huge amount of time and effort required to produce a single coloured illustration. I used to sketch, ink, scan, then colour… and end up feeling like the paper sketch looked better than the digitized, coloured version (scanners have shitty dynamic range, by the way—I eventually built a photographic ring light just to be able to preserve details in sketches and forego inking).

True story.

An illustrative example from Final Fantasy VIII. True story.

The colouring process was improved and sped up quite a bit when I bought an inexpensive USB Wacom graphire tablet a few years ago; I moved away from “cell shading” and achieved smoother results, quicker. Why Wacom? They’re the industry standard, their stylus/pen uses electromagnetic induction (no batteries required), and their hardware works out of the box with GNU/Linux and GNOME.

A piece was still missing, however: I was never able to sketch on a USB tablet because I really need my hand to be physically coordinated with my gaze. I could not replicate the precision feel of paper with a “desk-top” tablet. Drawing directly on the screen is an illustrator’s dream, and there’s the Wacom Cintiq for that, but is so outrageously expensive that it is not something you can really justify to yourself if you do occasional art “for the sake of it”.

On the other hand, Linux geeks like me tend to love Thinkpads: they are very well supported by Linux, their design is timeless and robustness legendary. Well, guess what? It just so happens that the tablet variants of the Thinkpad X series are actually inexpensive Wacom screens. And you can find them used much more easily than a Cintiq. I took a mental note to try one of these one day.

First illustration in years

Except on one recent occasion, I have not made any sketches in the past three years, and I have not made a full-colour drawing for over five years.

Trying out a stylus-enabled Thinkpad today, I managed to replicate the feel of my mechanical pen on paper, by setting the zoom to 25% in MyPaint and using David Revoy’s “pen” brush with a 2.0 opacity setting (default size and hardness). Since you’re at 25% zoom, you can zoom in to clean way more details than what would be possible on paper.

I was quite pleased to see that, much like riding a bicycle, drawing is a skill that does not really fade away in the absence of practice. With my new toolset (MyPaint + Thinkpad tablet + GNOME 3.12), I spent one hour sketching and two hours colouring, leading to this result:

2014 06 29

I think this is simultaneously the quickest and most satisfying color illustration I’ve done so far. I rarely get the feeling that the coloring process was worth it, but this time I did. It took me more time to write this enthusiastic blog post than to draw the damn thing.

Speaking broadly, GNOME Shell and GTK3 applications are quite nice to use with a touchscreen: thumb scrolling (I miss that in my browser), dragging windows in/out of your virtual workspace, tiling or maximize them using screen edges, etc.

GNOME’s distraction-free desktop experience, combined with MyPaint’s minimalist interface, is quite soothing. I’m looking forward to the GTK3 version of MyPaint, which is said to use symbolic icons and the dark variant of Adwaita. I hope it will also feature GTK3 client-side decorations to save vertical space.

GNOME Control Center provides a nice Wacom tablet/screen configuration and calibration tool. It allowed me to remap the stylus’ sidebutton to middle-click (useful for panning around an image) and to calibrate the screen. However, the screen calibration yields incorrect results when the screen is rotated, whereas I was able to achieve perfect accuracy when the screen is not rotated. Filed bug #732442 about it.

gnome 3.12 wacom tablet control center

It is amazing that we’ve come to a point where, barring the bug above, everything just works and is a pleasure to use.

Artists should prioritize the use of a Free Software creative applications (like MyPaint, GIMP, Inkscape, Pitivi and others) and a Free Software desktop/OS like GNOME, rather than relying on proprietary platforms:

  • Those tools are available to everyone.
  • They will continue to improve and be available to everyone.
  • They use open file formats and standards to ensure that, down the road, even in ten years, I will still be able to easily open my digital art files. The .ora format is not only MyPaint’s default format, it is also supported by GIMP, Krita, Scribus, Pinta, etc.

What concerns me is that I’m one of those “odd beasts” that love traditional devices like Thinkpad laptops. I’m wondering if many artists are now moving towards consumer tablets—the “disposable” ones, without a keyboard and user-replaceable operating system or battery. It would be great if, with GNOME OS, we could provide a compelling alternative to that and ensure the long-term freedom of artists.

by nekohayo at June 29, 2014 08:41 PM

GStreamerGStreamer Core, Plugins and RTSP server 1.3.90 release candidate


The GStreamer team is pleased to announce the first release candidate of the stable 1.4 release series. The 1.4 release series is adding new features on top of the 1.0 and 1.2 series and is part of the API and ABI-stable 1.x release series of the GStreamer multimedia framework.

This release candidate will hopefully shortly be followed by the stable 1.4.0 release if no bigger regressions or bigger issues are detected, and enough testing of the release candidate happened. The new API that was added during the 1.3 release series is not expected to change anymore at this point.

Binaries for Android, iOS, Mac OS X and Windows are provided together with this release.

The stable 1.4 release series is API and ABI compatible with 1.0.x, 1.2.x and any other 1.x release series in the future. Compared to 1.2.x it contains some new features and more intrusive changes that were considered too risky as a bugfix.

Check out the release notes for GStreamer core, gst-plugins-base, gst-plugins-good, gst-plugins-ugly, gst-plugins-bad, gst-libav, or gst-rtsp-server, or download tarballs for gstreamer, gst-plugins-base, gst-plugins-good, gst-plugins-ugly, gst-plugins-bad, or gst-libav, or gst-rtsp-server.

Check the release announcement mail for details and the release notes above for a list of changes.

Also available are binaries for Android, iOS, Mac OS X and Windows.

June 29, 2014 01:00 PM

June 25, 2014

Bastien NoceraFirewalls and per-network sharing

(Bastien Nocera) Firewalls

Fedora has had problems for a long while with the default firewall rules. They would make a lot of things not work (media and file sharing of various sorts, usually, whether as a client or a server) and users would usually disable the firewall altogether, or work around it through micro-management of opened ports.

We went through multiple discussions over the years trying to break the security folks' resolve on what should be allowed to be exposed on the local network (sometimes trying to get rid of the firewall). Or rather we tried to agree on a setup that would be implementable for desktop developers and usable for users, while still providing the amount of security and dependability that the security folks wanted.

The last round of discussions was more productive, and I posted the end plan on the Fedora Desktop mailing-list.

By Fedora 21, Fedora will have a firewall that's completely open for the user's applications (with better tracking of what applications do what once we have application sandboxing). This reflects how the firewall was used on the systems that the Fedora Workstation version targets. System services will still be blocked by default, except a select few such as ssh or mDNS, which might need some tightening.

But this change means that you'd be sharing your music through DLNA on the café's Wi-Fi right? Well, this is what this next change is here to avoid.

Per-network Sharing

To avoid showing your music in the caf, or exposing your holiday photographs at work, we needed a way to restrict sharing to wireless networks where you'd already shared this data, and provide a way to avoid sharing in the future, should you change your mind.

Allan Day mocked up such controls in our Sharing panel which I diligently implemented. Personal File Sharing (through gnome-user-share and WedDAV), Media Sharing (through rygel and DLNA) and Screen Sharing (through vino and VNC) implement the same per-network sharing mechanism.

Make sure that your versions of gnome-settings-daemon (which implements the starting/stopping of services based on the network) and gnome-control-center match for this all to work. You'll also need the latest version of all 3 of the aforementioned sharing utilities.

(and it also works with wired network profiles :)

by Bastien Nocera (noreply@blogger.com) at June 25, 2014 05:32 PM

June 24, 2014

Zeeshan AlioFono? Its dead jim!

(Zeeshan Ali)
Soon after I mentioned the need for an oFono-backend in Geoclue in my blog, Sri kindly helped me get in touch with oFono developers. What started as a nice friendly discussion soon was turned into a not so nice discussion. I won't get into details and blames but here is what I found out about the project:

  •  oFono developers claim that its is still a maintained project while rest of the world think its a dead project, even people who love the project. Last release being in 2012 and loads of missing essential features (see rest of the points below) and link to mailing-list broken (even though I pointed it out 3 weeks ago and its been broken for much longer) on the homepage all points to the fact that its essentially a dead project.

  • No proper D-Bus introspection nor any client libraries. This already makes it extremely difficult to work with oFono but wait there is more hurdles on the way.

  • No online cross-references documentation: The documentation link on the home-page leads you to an architecture diagram and gives you no information about the API. Searching through google doesn't yield any results either. The developers pointed out that all documentation lives in the source tree in the form of plain-text documents and hence not very appropriate for the web.

  • It does not implement the standard D-Bus Properties interface. This combined with the fact that their D-Bus API is heavily based on properties makes it yet even harder to work with OFono, not to mention very weird.

  • None of the modern 3G modems supported, at least out of the box. I tried both Option and Qualcomm Gobi that I have and they both didn't work.

While rest of the issues can be overcome, the last makes it impossible for me to test any code written against oFono. So I'm giving up on this.

With a nice alternative that is well-maintained, and with which most modems work out of the box, has a nice OO, well-documented and introspectable D-Bus API and also provides  a nice client library, I don't understand why phone vendors insist on supporting oFono interface. Could it be because the name makes it sound like its *the* solution for phones? Well, they do have the right to use whatever they like. I'm just curious.

Having said all that, I did make it easy for anyone to add oFono support to Geoclue as promised in my last blog post. Patches to add that are more than welcome!

June 24, 2014 01:07 AM

June 23, 2014

Jean-François Fortin TamA quick Pitivi status update for June 2014

I have been extremely busy in the past few months and thus have not been able to spend much time at all on Pitivi, but here’s a quick status update about the work of others in case you missed it:

  • In follow-up to our initial look at this summer’s GSoC projects for Pitivi:
  • Mathieu and Thibault have been hard at work to bring editing-ready MPEG-TS support for GStreamer, so you can finally edit those quirky AVCHD camcorder videos in Pitivi. Learn more about what they did in this blog post. The official fix, due for GStreamer 1.4, comes as part of bug #675132. For a historical sense of scale, see also this meta-bug on Launchpad and GStreamer bug #550634.
  • We will be at GUADEC. As per tradition, we will have a week-long Pitivi hackfest after the core presentations days. Do not hesitate to come hang around and get involved!

I will start preparing my GUADEC Pitivi talk soon. If there are topics or questions you would like to see covered, feel free to leave a comment to let me know.

by nekohayo at June 23, 2014 06:40 PM

June 22, 2014

GStreamerGStreamer Core and Plugins 1.3.3 development release


The GStreamer team is pleased to announce the third release of the unstable 1.3 release series. The 1.3 release series is adding new features on top of the 1.0 and 1.2 series and is part of the API and ABI-stable 1.x release series of the GStreamer multimedia framework. The unstable 1.3 release series will lead to the stable 1.4 release series in the next weeks, and newly added API can still change until that point.

This is hopefully the last 1.3 development release and will be followed by the first 1.4.0 release candidate (1.3.90) in 1-2 weeks. Which then hopefully is followed by 1.4.0 soonish in early July.

Binaries for Android, iOS, Mac OS X and Windows will be provided separately during the unstable 1.3 release series.

Check out the release notes for GStreamer core, gst-plugins-base, gst-plugins-good, gst-plugins-ugly, gst-plugins-bad, gst-libav, or gst-rtsp-server, or download tarballs for gstreamer, gst-plugins-base, gst-plugins-good, gst-plugins-ugly, gst-plugins-bad, gst-libav, or gst-rtsp-server, or

Check the release announcement mail for details and the release notes above for a list of changes.

June 22, 2014 08:00 PM

Jean-François Fortin TamSe libérer de Bell et Vidéotron: passez Go et réclamez 1000$ par année

Ceci est un guide, basé sur mon expérience, pour vous libérer de l’hégémonie de fournisseurs tels que Bell et Vidéotron tout en augmentant votre connaissance de la technologie. Notons que ce guide est hautement contextuel à la quasi absence de compétition que l’on retrouve au Québec. Les Français, eux, ont Free (entre autres).

D’entrée de jeu, je me fiche de tout ce que les vendeurs de Bell et Vidéotron pourront vous dégotter comme offres promotionelles pour vous séduire:

  • Les tarifs avantageux pour les 12 prochains mois, ça ne veut rien dire. Je regarde sur le long terme (5-10 ans) et je calcule toujours les offres à “tarif régulier”.
  • De la même façon, j’ignore toute offre “package deal”: le classique “migrez tous vos services chez nous! téléphonie + Internet + télévision! Vous allez économiser de l’argent!” est vrai seulement si vous n’avez pas la patience ou l’audace de mettre en place ce que je propose dans ce billet (par exemple, j’en connais un qui est bien heureux de payer 50$ par mois pour le câble juste pour avoir TV5…), ou si vous trouvez que 100$ par mois c’est une “aubaine” (si tel est le cas, j’ai un beau pont presque neuf à vous vendre, vous allez l’adorer).

Combien coûte un abonnement télévision “câble” de base analogique au Québec? À en croire les factures de ma tante, un minimum de 39$ par mois. Notons que l’offre en analogique n’est plus commercialisée aujourd’hui, il faut maintenant être abonné au câble numérique où Vidéotron impose un décodeur – et donc, pas de possibilité d’avoir plusieurs télés sans payer plus pour chaque téléviseur (mais bon, qui serait assez fou pour vouloir plus d’une télé? Une suffit déjà à zombifier).

Et combien ça coûte, avoir une bête ligne téléphonique de base chez Bell?

Ligne résidentielle "de départ": 28,09$
+ 6,95$ "frais de réseau" (bullshit!)
+ 6,95$ plan interurbain provincial
+ 0,16$ pour le service d'appel d'urgence 911
+ 0,40$ de taxe municipale pour le 911 (!)
+ 2,80$ pour "service touch-tone" (bullshit!)
+ taxes

… totalisant 52$. Bravo les gars. Vous avez trouvé le moyen de facturer pratiquement le double d’un tarif d’accès Internet haute vitesse… pour le nec plus ultra de la technologie de 1940!

slow clap

L’approche que je prône ici englobe:

  • L’Internet haute vitesse par câble. Important. L’astuce ne fonctionne pas aussi bien avec l’ADSL, parce que Bell vous exigera des frais de “ligne sèche”, ce qui est une ignomie. Bref, sans ligne téléphonique, il est moins onéreux en 2014 d’avoir l’Internet par câble que par l’ADSL. Personnellement je recommande Teksavvy, mais vous connaissez peut-être déjà votre grossiste/fournisseur d’accès Internet favori.
  • La téléphonie par VoIP, et ce, sans disruption des habitudes, sans avoir à utiliser d’ordinateur, sans perdre son numéro de téléphone. Coût mensuel: de 1 à 2 dollars par mois pour les gens normaux (si vous voulez vous faire un centre d’appels avec 300 employés, c’est autre chose).
  • La télévision numérique terrestre. L’ATSC haute définition est de meilleure qualité que ce que Bell ou Vidéotron peuvent vous offrir en HD! Coût mensuel: 0$, c’est du hertzien! Évidemment, c’est seulement si, comme beaucoup de gens dans ma famille, vous vous contentez de la poignée de chaîne publiques principales (5 à 10 chaînes locales, dépendamment de votre lieu de réception). Une très forte proportion de Québécois ne s’intéresse principalement qu’à Radio-Canada, CBC, V, Télé-Québec et TVA. À vous de juger de la pertinence de payer 40-50$ par mois pour quelques chaînes privilégiées de plus.

…le tout pour environ 30 à 35$ par mois avant les taxes (le coût de la connexion Internet de base à 25$, plus un estimé conservateur de 5 à 10$ de frais d’appels à 1¢/minute). Pas d’arnaques. Pas d’farces.


Le seul hic, c’est qu’il ne faut pas avoir peur de l’Internet, et avoir un peu d’aisance technique (sinon vous demandez à votre petit neveu qui porte des t-shirts avec un pingouin dessus – si vous n’avez pas de tel neveu, vous pouvez toujours m’embaucher pour le faire, mais je coûte beaucoup plus cher). Notamment, il faut être assez patient et débrouillard pour comprendre des fouillis comme celui-ci (la maison de ma tante était très vieille et son installation téléphonique était une pile de hacks immondes):


Des parafoudres en double, connectés les uns sur les autres, menant éventuellement sur un tuyau de plomberie lambda, avec divers fils coupés qui pendent un peu partout.


Des diviseurs tels que celui-ci se trouvaient absolument partout, raccordés les uns aux autres. Ou raccordés à rien.


Un filtre ADSL maître, qui ne sert plus étant donné qu’on vient de passer à l’Internet par câble.

…et bien sûr, tous les combinés et prises murales étaient câblés à coups de rallonges RJ11 cheap de trente mètres de long par dessus les diviseurs. À côté de ça, l’autre maison était super propre (surtout après que j’aie placé des étiquettes pour identifier les composantes):

L'installation téléphonique de l'autre maison, avant la conversion à la VoIP

L’installation téléphonique de l’autre maison, avant la conversion à la VoIP. Notons la présence d’un diviseur et filtre ADSL tout simple au niveau du point de démarcation: mon modem était placé directement là et le reste de la maison était filtré en un seul point. Ça marchait plutôt bien.

Matériel requis:

  • Un modem pour l’Internet par câble. Dans mon cas je n’en avais pas; j’ai décidé de faire dans la démesure et acheter un modem tout neuf, supportant le DOCSIS 3.0. Un modem Thomson DCM475 coûte environ 100$ si vous êtes extrêmement paresseux et demandez à votre FAI de vous en vendre un, sinon environ 65-70$ neuf dans les marchands canadiens en ligne tels que NCIX ou DirectCanada.
  • Un adaptateur pour téléphone analogique (ATA) pour rendre la VoIP entièrement transparente dans votre demeure. Bref, la boîte sur laquelle on branche les téléphones, qui elle-même est branchée sur votre routeur/switch pour accès à Internet. Dans mon cas, un Grandstream Handytone 701 (j’avais précédemment le vénérable handytone 486… c’est du pareil au même). 37$ en ligne.
  • Une bonne antenne UHF/VHF d’extérieur pour capter la télévision numérique terrestre en ATSC (pas une antenne “oreilles de lapin”). Dans mon cas, j’avais déjà deux bonnes antennes sous la main. Sinon, 50-70$ en magasin.
  • Une télévision haute-définition nord-américaine moderne (avec un syntoniseur ATSC dedans), ou si vous voulez garder votre vieux téléviseur cathodique increvable, un récepteur/convertisseur ATSC comme le Homeworx HW-150PVR pour 50$ chez les marchands en ligne (en rayons, vous risquez de payer pas mal plus cher). Pourquoi pas de téléviseur tout neuf pour ma tante? Parce qu’elle ne verrait aucunement la différence même si ses yeux avaient une acuité de 20/20. Sur une télévision HD, mes parents ont du mal à différencier un film en HD d’un film en SD – et honnêtement, une fois absorbé dans l’histoire, même moi, je cesse de m’en préoccuper.

Donc, dans mon cas, le total des dépenses en matériel s’élève à 260$ (incluant taxes et livraison): pour deux maisons (deux modems, un convertisseur ATSC, deux ATA). Pour une maison, ça tournerait donc autour de 150$. Faites vos calculs. Your mileage will vary.

Équipement supplémentaire mais fortement recommandé:

  • Un onduleur avec alimentation ininterruptible (batterie) pour votre équipement réseau (modem, routeur, ATA). Environ 50-70$ dans un magasin à rayons près de chez vous (ex: Costco). Panne de courant? Le téléphone continuera de fonctionner tant que l’UPS tiendra.
  • Un routeur qui peut rouler Tomato, une certaine connaissance de la réseautique pour avoir une connexion Internet avec du QoS à toute épreuve (sinon demandez au neveu qui se balade avec le t-shirt de pingouin). Vous ne voulez pas que YouTube, Steam, wget ou Bittorrent soient priorisés face à la ligne VoIP! De plus, vous ne voulez probablement pas que votre ATA soit votre “gateway” face à l’Internet: la plupart des ATA sont plutôt cons et vulnérables aux attaques de l’extérieur. Par exemple, quelques jours après le retrait du pare-feu chez ma tante, ses téléphones ont commencé à sonner aléatoirement à toute heure du jour ou de la nuit: des appels avec personne au bout de la ligne, pas de tonalité, et pas de traces dans les journaux d’appels de VoIP.ms. Bref, le phénomène connu sous le nom de “phantom calls” ou “ghost rings”. J’ai alors sécurisé le système et temporairement réintroduit le pare-feu, ce qui a résolu le problème.

Les étapes:

  1. Pré-vérifications avec le FAI. Dans mon cas (chez Teksavvy) on m’a dit que les frais d’activation et le prix du modem ne sont pas négociables, “allez-y, achetez votre modem où bon vous semble et rappelez-nous ensuite pour amorcer le processus”.
  2. Commander tout le matos
  3. Amorcer le processus de migration:
    1. Téléphoner au FAI pour faire la migration vers le câble. Préparez-vous aux frais d’activation monstrueux de 85$.
    2. Avec les informations sur la facture de Bell, commencer la migration (“LNP”) du numéro téléphone vers un DID chez votre fournisseur de VoIP favori (dans mon cas: Voip.ms, une entreprise montréalaise avec une très faible latence et bonne qualité sonore – les frais de LNP sont de 10$, your mileage may vary)
  4. Effectuer des tests lorsque le matériel a été reçu, que le nouveau FAI a mis le tout en place et que le numéro de téléphone a été migré vers la VoIP
  5. Téléphoner à Bell et Vidéotron pour résilier tous les services. N’accepter aucune contre-offre. Ne prendre aucun prisonnier. On ne négocie pas avec les terroristes.

Comparatif dans le cas de ma tante:

  • Un an à tarif régulier avec Internet haute vitesse, ligne téléphonique résidentielle Bell et télévision câble chez Vidéotron: 1432.59$
  • Avec ma solution (Internet haute vitesse, ligne téléphonique VoIP, télévision en ATSC): ~362.31$, soit ~1070$ d’économies chaque année.

Combien tout cela coûte-t-il en pratique avec du “payez à la minute” (pas d’abonnement) chez VoIP.ms ? Eh bien, sur la période s’échelonnant du 1er Mars 2014 au 21 juin 2014, pour trois lignes téléphoniques (ma tante, mes parents et la mienne, cette dernière étant négligible car je ne téléphone que très peu), nous avons effectué plus de 2000 appels, totalisant 100 heures de conversation, coûtant… 52$ (soit ~7$ par maison par mois). Même en rajoutant environ 2$ de frais fixes mensuels pour les numéros entrants et le 911, on s’en sort quand même à une fraction du prix des grands opérateurs.

Note: je n’ai aucun lien d’affaires avec Teksavvy ou Voip.ms — je suis seulement un client satisfait (de longue date) et les mentionne ici car c’est effectivement ces deux là que je recommande à mon entourage.

by nekohayo at June 22, 2014 04:57 AM

June 18, 2014

Gustavo Orrillomirador-sorting

It is now almost three years since I moved to Boston to start working at Fathom Information Design and the Sabeti Lab at Harvard. As I noted back then, one of the goals of this work was to create new tools for exploring complex datasets -mainly of epidemiological and health data- which could potentially contain […]

by ac at June 18, 2014 02:27 PM

June 10, 2014

George KiagiadakisGStreamer Wayland GTK Demo

During the past few months I’ve been occasionally working on integrating GStreamer better with wayland. GStreamer already has a ‘waylandsink’ element in gst-plugins-bad, but the implementation is very limited. One of the things I’ve been working on was to add GstVideoOverlay support in it, and recently, I managed to make this work nicely embedded in a GTK+ window.

GStreamer Wayland GTK Demo

gtk+ video player demo running on weston

I’m happy to say that it works pretty well, even though GTK does not support wayland sub-surfaces, which was being thought of as a problem initially. It turns out there is no problem with that, and both the GTK and GstVideoOverlay APIs are sufficient to make this work. However, there needs to be a small addition in GstVideoOverlay to allow smooth resizing. Currently, I have a GstWaylandVideo API that includes those additions.

This essentially means that as soon as this work is merged (hopefully soon), there is nothing stopping applications like totem from being ported to wayland :D

I believe embedding waylandsink in Qt should also work without any problems, I just haven’t tested it.

If you are interested, check the code. The code of the above running demo can also be found here, and the ticket for merging this branch is being tracked here.

I should say many thanks here to my employer, Collabora, for sponsoring this work.

by gkiagia at June 10, 2014 12:24 PM

May 28, 2014

Zeeshan AliLocation hackfest 2014 report

(Zeeshan Ali)
So the Location hackfest 2014 took place at the awesome Mozilla offices in London during last weekend. Even though some of the important participants didn't manage to be physically present, enough people did:
  • John Layt (KDE)
  • Hanno Schlichting (Mozilla)
  • Mattias Bengtsson (GNOME)
  • Jonas Danielsson (GNOME)
and some participated remotely:
  • Bastien Nocera (GNOME)
  • Garvan Keeley (Mozilla)
Unfortunately Aaron McCarthy of Jolla couldn't attend remotely either as he lives in a very incompatible timezone (AU) but we had a lot of productive discussion with him through email that still continues.

Some very fruitful discussions we had:

  • Why Mozilla doesn't make wifi data it gathers for its location service, available for everyone to download? Hanno explained in great detail how making this data available would seriously compromise privacy and even safety of people. One good example given was someone getting out of an abusive relationship and not wanting to be traceable by their ex- but if they take their wifi router with them, their significant other has a possible way to easily track them using the wifi database. There is an easy (even though very ugly) way to avoid your AP being scanned by harvesters of such services but most people do not possess enough technical knowledge to know to enable that.

    Hence their reluctance to making it available for download, even though they'd want to. If you are interested in more details, you should read up all about that on Hanno's blog.
  • Had some discussion with Firefox and Firefox OS using Geoclue2. Hopefully we'll at least have Firefox using Geoclue2 soon. I might need to add support for totally unmaintained ofono in Geoclue2 unfortunately for making a very compelling case for Firefox OS to adapt geoclue2.
  • We had a discussion about GPS-A support in Geoclue. There are two possible ways to do that:
    1. Give URL of a SUPL service to the modem and let it do everything for you.
    2. Get the geospacial data that (SUPL service would provide) from a custom service and feed that to the modem.
    Hanno informed us that the only free SUPL implementation out there is that from Google but nobody knows what the ToS really are. He also informed us of how many modem chipsets just don't implement the API to feed it geospatial data and that makes SUPL our only hope to implement GPS-A.
  • There was a discussion about POI and check-in UI in Maps between me and Mattias. We had a bit of disagreement about it but seems now we are coming to come conclusions about how it should look like.
It was a hackfest so we also did some hacking:

  • John spent most of his time getting familiar with Qt's location code and how to port to Geoclue2. He wrote a nice post about it so I wont get into details here.
  • Mattias worked tirelessly to finish off his routing branch to be finally merged. Its not a very easy task so its not surprising that he hasn't managed to finish it yet. I'm pretty hopeful it will be merged in the following few weeks.
  • Hanno added proper support for geoip-only queries in Mozilla location service, made it do better against queries w/ stale wifi data and improved accuracy of results from 300m to 100m among other things.
  • Jonas was doing live reviews of Mattias' patches (in Swedish!) and at the same time working on getting command-line options parsing to work in gjs so we can do so in Maps.
  • Garvan was working on adding Geoclue2 support to Firefox/Gecko.
  • I finished off my patches to port geoclue2 to directly use wpa_supplicant rather than NetworManager, which makes wifi-geolocation work on FreeBSD, Firefox OS and Jolla. The last two don't use Geoclue2 but I'm hoping that this is a step forward towards convincing them to use it. I provided a patch to wpa_supplicant to make its D-Bus policy a bit lenient, while at it.

    I also looked into ofono API but not only is the project unmaintained, it doesn't provide proper introspection on D-Bus and there is no API docs. :( To make things worse, both my modems don't seem to work at least out of the box. I'd really rather I didn't have to deal with it but if I can't convince Firefox OS folks to provide ModemManager API, adding ofono support is essential to get them to use Geoclue.

    I started refactoring of Modem sources in Geoclue so that:
    • all ModemManager code is isolated in its own module so that its easy to add a ofono handling code w/o changing anything in the sources themselves.
    • 3G source can more easily/cleanly share code with Wifi source, use Mozilla Location Service (rather than opencellid that it currently does) and also submit cell tower data to Mozilla.
I can't thank Mozilla and specifically Chris Lord enough for hosting this event for hosting this event.

    May 28, 2014 12:06 PM

    May 21, 2014

    GStreamerGStreamer Core and Plugins 1.3.2 development release


    The GStreamer team is pleased to announce the first release of the unstable 1.3 release series. The 1.3 release series is adding new features on top of the 1.0 and 1.2 series and is part of the API and ABI-stable 1.x release series of the GStreamer multimedia framework. The unstable 1.3 release series will lead to the stable 1.4 release series in the next weeks, and newly added API can still change until that point.

    Binaries for Android, iOS, Mac OS X and Windows will be provided separately during the unstable 1.3 release series.

    Check out the release notes for GStreamer core, gst-plugins-base, gst-plugins-good, gst-plugins-ugly, gst-plugins-bad, gst-libav, or gst-rtsp-server, or download tarballs for gstreamer, gst-plugins-base, gst-plugins-good, gst-plugins-ugly, gst-plugins-bad, gst-libav, or gst-rtsp-server, or

    Check the release announcement mail for details and the release notes above for a list of changes.

    May 21, 2014 03:00 PM

    May 18, 2014

    Andy Wingoeffects analysis in guile

    (Andy Wingo)

    OK kids, so I had a bit of time recently. I've been hacking on Guile's new CPS-based compiler, which should appear in a stable release in a few months. I have a few things to write about, but today's article is on effects analysis.

    what it is, yo

    The job of the optimization phase of a compiler is to remove, replace and reorder the sub-expressions of a program. The optimizer recognizes ways in which the program can be better, and then needs to check if those transformations are valid. A transformation is valid if a program exhibits the same behavior both before and after the transformation.

    Effects analysis is a proof technique that builds a conservative model of how expressions can affect each other. It can be used to prove the validity of some transformations. For example, if we determine that an expression A reads the first field in a vector, and expression B sets the second field in a vector, then we can use effects analysis to show that the expressions don't affect each others' value and can be freely reordered, for example to hoist either one out of a loop.

    In effects analysis, we model the program state coarsely and conservatively with a limited set of categories. The precise set of categories depends on the domain. In graphics, for example, you might have a state bit for the current coordinate system, the current color, the current fill mode, etc. In general-purpose compilation, the effects are mostly about memory and (sometimes) exceptions.

    In Guile we model four kinds of effects: type checks (T), allocations (A), reads (R), and writes (W). Each of these effects is allocated to a bit. An expression can have any or none of these effects.

    For the purposes of Guile, a "type check" is the possibility that this expression will throw an exception if its arguments are somehow out of range. For example, cons will never throw an exception, except in out-of-memory situations, but + may throw an exception if its arguments aren't numbers. However if an expression is dominated by a copy of itself -- that is, if we see that (+ a b) (which may throw an exception) is dominated by (+ a b), perhaps after CSE -- then we can determine that only the first will exhibit the type-check effects, and that the second will not.

    Allocation indicates that an expression allocates a fresh object. In Scheme (and many other languages), each allocated object has its own identity: (eq? (cons 1 2) (cons 1 2)) must be false. Note that this restriction does not apply to constant literals, in Scheme; (eq? '(1 . 2) '(1 . 2)) may or may not be true. In Guile both results are possible. They are the same object when compiled (and thus deduplicated), but different when interpreted; the objects are just the ones returned from `read' and this are different. Anyway we use this allocation bit to indicate that an expression allocates a fresh object with a fresh identity.

    The remaining effect kinds are "read" and "write", which indicate reads or writes to memory. So there are just 4 kinds of effects.

    Allocation, read, and write effects are associated at run-time with particular memory locations. At compile-time we cannot in general know which of these locations are distinct, and which are actually the same. To simplify the problem, we simply record the type of the object, knowing that (say) a pair and a vector will never be at the same location. We also record the field in the object in the case of objects with multiple fields. There are special catch-all values to indicate "all memory kinds", when we really don't know what an expression will do (which is the case for all expression kinds without specific support in the effect analyzer), and for "all fields" when we don't know which field we are accessing.

    One example of the use of this analysis is in common subexpression elimination (CSE). If at a program point P we have a set of available expressions A, then to determine which members of A are still available after the expression at P, you subtract members of A that are clobbered by P. Computation of A at each P plus value numbering is most of CSE; but more on that in some later dispatch. Anyway here's the definition of effects-clobber?.

    (define (effect-clobbers? a b)
      "Return true if A clobbers B.  This is the case
    if A might be a write, and B might be a read or a
    write to the same location as A."
      (define (locations-same?)
        (let ((a (ash a (- &effect-kind-bits)))
              (b (ash b (- &effect-kind-bits))))
          (or (eqv? &unknown-memory-kinds
                    (logand a &memory-kind-mask))
              (eqv? &unknown-memory-kinds
                   (logand b &memory-kind-mask))
              (and (eqv? (logand a &memory-kind-mask)
                         (logand b &memory-kind-mask))
                   ;; A negative field indicates "the
                   ;; whole object".  Non-negative fields
                   ;; indicate only part of the object.
                   (or (< a 0) (< b 0) (= a b))))))
      (and (not (zero? (logand a &write)))
           (not (zero? (logand b (logior &read &write))))

    This analysis is simple, small, and fast. It's also coarse and imprecise -- if you are reading from and writing to two vectors at once, you're almost sure to miss some optimization opportunities as accesses to all vectors are conflated into one bit. Oh well. If you get into this situation, you'll know it, and be able to invest a bit more time into alias analysis; there's lots of literature out there. A simple extension would be to have alias analysis create another mapping from expression to equivalence class, and to use those equivalence classes in the same-location? check above.

    Of course this assumes that expressions just access one object. This is the case for Guile's CPS intermediate language, because in CPS, as in SSA or ANF, expressions don't have subexpressions.

    This contrasts with direct-style intermediate languages, in which expressions may have nested subexpressions. If you are doing effects analysis on such a language, it's probably more appropriate to allocate a bit to each kind of effect on each kind of object, so that you can usefully union effects for a tree of expressions. Since you don't have to do this for CPS, we can allocate a fixed bit-budget towards more precision as to which field of an object is being accessed. The inability to be precise as to which field was being accessed due to the direct-style IL was one of the problems in Guile's old CSE pass.

    Finally, a note about type checks. Guile includes type checks as part of the effects analysis for two reasons. The first is the obvious case of asking whether an expression is effect-free or not, which can lead to some optimizations in other parts of the compiler. The other is to express the potential for elision of duplicate expressions, if one dominates the other. But it's also possible to remove type checks in more cases than that: one can run a type inference pass to remove type-check effects if we can prove that the arguments to an expression are in range. Obviously this is more profitable for dynamically-typed languages, but the same considerations apply to any language with sum types.

    Guile's effects analysis pass is here. V8 seems to have two effects analysis passes; one is in effects.h and typing.cc, and operates over the direct-style AST, and the other is in the value numbering pass (hydrogen-instructions.h and hydrogen-gvn.h; search for GVNFlag).

    More on how effects analysis is used in Guile in a future missive. Until then, happy hacking.

    by Andy Wingo at May 18, 2014 07:19 PM

    May 16, 2014

    Sebastian DrögeHTTP Adaptive Streaming with GStreamer

    (Sebastian Dröge)

    Let’s talk a bit about HTTP Adaptive streaming and GStreamer, what it is and how it works. Especially the implementation in GStreamer is not exactly trivial and can be a bit confusing at first sight.

    If you’re just interested in knowing if GStreamer supports any HTTP adaptive streaming protocols and which you can stop after this paragraph: yes, and there are currently elements for handling HLS, MPEG DASH and Microsoft SmoothStreaming.

    What is it?

    So what exactly do I mean when talking about HTTP Adaptive Streaming. There are a few streaming protocols out there that basically work the following way:

    1. You download a Manifest file with metadata about the stream via HTTP. This Manifest contains the location of the actual media, possibly in multiple different bitrates and/or resolutions and/or languages and/or separate audio or subtitle streams or any other different type of variant. It might also contain the location of additional metadata or sub-Manifests that provide more information about a specific variant.
    2. The actual media are also downloaded via HTTP and split into fragments of a specific size, usually 2 seconds to 10 seconds. Depending on the actual protocol these separate fragments can be played standalone or need additional information from the Manifest. The actual media is usually a container format like MPEG TS or a variant of ISO MP4.

    Examples of this are HLS, MPEG DASH and Microsoft SmoothStreaming.

    This kind of protocols are used for both video-on-demand and “live” treaming, but obviously can’t provide low-latency live streams. When used for live streaming it is usually required to add more than one fragment of latency and then download one or more fragments, reload the playlist to get the location of the next fragments and then download those.


    You might wonder why one would like to implement such a complicated protocol on top of HTTP that can’t even provide low-latency live streaming and why one would choose it over other streaming protocols like RTSP, or any RTP based protocol, or simply serving a stream over HTTP at a single location.

    The main reason for this is that these other approaches don’t allow usage of the HTTP based CDNs that are deployed via thousands of servers all around the world, and that they don’t allow using their caching mechanisms. One would need to deploy a specialised CDN just for this other kind of streaming protocol.

    A secondary reason is that especially UDP based protocols like RTP but also anything else not based on HTTP can be a bit complicated to deploy because of all the middle boxes (e.g. firewalls, NATs, proxies) that exist in almost any network out there. HTTP(S) generally works everywhere, in the end it’s the only protocol most people conciously use or know about.

    And yet another reason is that this splitting of the streams in the fragments allows trivial to implement switching between bitrates or any other stream alternatives at fragment boundaries.

    GStreamer client-side design

    In GStreamer the above mentioned three protocols are implemented and after trying some different approaches for implementing this kind of protocol, all of them converged to a single design. This is what I’m going to describe now.


    The naive approach would consider implementing all this as a single source element. Because that’s how network protocols are usually implemented in GStreamer, right?

    While this seems to make sense there’s one problem with this. There is no separate URI scheme defined for such HTTP adaptive streams. They’re all using normal HTTP URIs that point to the Manifest file. And GStreamer chooses the source element that should be used based on the URI scheme alone, and especially not from the data that would be received from that URI.

    So what are we left with? HTTP URIs are handled by the standard GStreamer elements for HTTP, and using such a source element gives us a stream containing the Manifest. To make any sense of this collection of bytes and detect the type of it, we additionally have to implement a typefinder that provides the media type based on looking at the data and actually tells us that this is e.g. a MPEG DASH Manifest.


    This Manifest stream is usually rather short and followed by the EOS event like every other stream. We now need another element that does something with this Manifest and implements the specific HTTP adaptive streaming protocol. In GStreamer terminology this would act like a demuxer, it has one stream of input and outputs one or more streams based on that. Strictly speaking it’s not really a demuxer though, it does not demultiplex the input stream into the separate streams but that’s just an internal detail in the end.

    This demuxer now has to wait until it received the EOS event of the Manifest, then needs to parse it and do whatever the protocol defines. In specific it starts a second thread that handles the control flow of the protocol. This thread downloads any additional resources specified in the Manifest, decides which media fragment(s) are supposed to be downloaded next, starts downloading them and makes sure they leave the demuxer on the source pads in a meaningful way.

    The demuxer also has to handle the SEEK event, and based on the time specified in there jump to a different media fragment.

    Examples of such demuxers are hlsdemux, dashdemux and mssdemux.

    Downloading of data

    For downloading additional resources listed in the Manifest that are not actual media fragments (sub-Manifests, reloading the Manifest, headers, encryption keys, …) there is a helper object called GstURIDownloader, which basically provides a blocking (but cancellable) API like this: GstBuffer * buffer = fetch_uri(uri)
    Internally it creates a GStreamer source element based on the URI, starts it with that URI, collects all buffers and then returns all of them as a single buffer.

    Initially this was also used to download media fragments but it was noticed that this is not ideal. Mostly because the demuxer will have to download a complete fragment before it can be passed downstream, and very huge buffers are passed downstream that cause any buffering
    elements to mostly jump between 0% and 100% all the time.

    Instead, thanks to the recent work of Thiago Santos, the media fragments are now downloaded differently. The demuxer element is actually a GstBin now and it has a child element that is connected to the source pad: a source element for downloading the media fragments.

    This allows to forward the data as it is downloaded immediately and allows downstream elements to handle the data one block after another instead of getting it in multi-second chunks. Especially it also means that playback can start much sooner as you don’t have to wait for a complete fragment but can fill up your buffers with a partial fragment already.

    Internally this is a bit tricky as the demuxer will have to catch EOS events from the source (we don’t want to stop streaming just because a fragment is done), catch errors and other messages (maybe instead of forwarding the error we want to retry downloading this media fragment) and switch between different source elements (or just switch the URI of the existing one) during streaming once a media fragment is finished. I won’t describe this here, best to look at the code for that.

    Switching between alternatives

    Now what happens if the demuxer wants to switch between different alternative streams, e.g. because it has noticed that it can barely keep up with downloading streams of a high bitrate and wants to switch to a lower bitrate. Or event to an alternative that is audio-only. Here the demuxer has to select the next media fragment for the chosen alternative stream and forward that downstream.

    But it’s of course not that simple because currently we don’t support renegotiation of decoder pipelines. It could easily happen that codecs change between different alternatives, or the topology changes (e.g. the video stream disappears). Note that not supporting automatic renegotiation for cases like this in decodebin and related elements is not a design deficit of GStreamer but just a limitation of the current implementation.

    There already is a similar case that is handled in GStreamer already, which is handling of chained Ogg files (i.e. different Ogg files concatenated to each other). In that case it should also behave like a single stream, but codecs could change or the topology could change. Here the demuxer just has to add new pads for the following streams after having emitted the no-more-pads signal, and then remove all the old pads. decodebin and playbin then first drain the old streams and then handle the new ones, while making sure their times align perfectly with the old ones.

    (uri)decodebin and playbin

    If we now look at the complete (source) pipeline that is created by uridecodebin for this case we come up with the following (simplified):

    HTTP Adaptive Streaming Pipeline

    We have a source element for the Manifest, which is added by uridecodebin. uridecodebin also uses a typefinder to detect that this is actually an HTTP adapative streaming Manifest. This is then connected to a decodebin instance, which is configured to do buffering after the demuxers with the multiqueue element. In the normal HTTP stream buffering, the buffering is done between the source element and decodebin with the queue2 element.

    decodebin then selects an HTTP adaptive streaming protocol demuxer for the current protocol, waits until it has decided on what to output and the connects it to a multiqueue element like every other demuxer. However it uses different buffering settings as this demuxer is going to behave a bit different.

    Followed by that is the actual demuxer for the media fragments, which could for example be tsdemux if they’re MPEG TS media fragments. If an elementary stream is used for the media fragment, decodebin will insert a parser for that elementary stream which will chunk the stream into codec frames and also put timing information on them.

    Afterwards there comes another multiqueue element, which does not happen after a parser if no HTTP adapative streaming demuxer is used. decodebin will configure this multiqueue element to handle buffering and send buffering messages to the application to allow it to pause playback until the buffer is full.

    In playbin and playsink no special handling is necessary. Now let’s take a look at a complete pipeline graph for an HLS stream that contains one video and one audio stream inside MPEG TS containers. Note: this is huge, like all playbin pipelines. Everything on the right half is for converting raw audio/video and postprocessing it, and then outputting it on the display and speakers.

    playbin: HLS with audio and video

    Keep in mind that the audio and video streams, and also subtitle streams, could also be in separate media fragments. In that case the HTTP adaptive streaming demuxer would have multiple source pads, each of them followed by a demuxer or parser and multiqueues. And decodebin would aggregate the buffering messages of each of the multiqueues to give the application a consistent view of the buffering status.

    Possible optimisations

    Now all of this sounds rather complex and probably slow compared to the naive approach of just implementing all this in a single source element and not having so many different elements involved here. As time as shown it actually is not slow at all, and if you consider a design for
    such a protocol in a single element you will notice that all the different components that are separate elements here will also show up in your design. But as GStreamer is like Lego and we like having lots of generic components that are put together to build a more complex whole, the current design seems to follow the idea of GStreamer in a more consistent way. And especially it is possible to reuse lots of existing elements and also allow to replace different elements with custom implements. Transparently due to GStreamer’s autoplugging mechanisms.

    So let’s talk about a few possible optimisations here, some of which are implemented in the default GStreamer elements and should be kept in mind when replacing elements. Some of which could be implemented on top of the existing elements.

    Keep-alive Connections and other HTTP features

    All these HTTP adaptive streaming protocols require to create lots of HTTP requests, which traditionally required to create a new TCP connection for every single request. This involves quite some overhead and increases the latency because of TCP’s handshake protocol. Even worse if you use HTTPS and have to also handle the SSL/TLS handshake protocol on top of that. And we’re talking about multiple 100ms to seconds per connection setup here. HTTP 1.1 allows connections to be kept alive for some period of time and reuse them for multiple HTTP requests. Browsers are using this since a long time already to efficiently show you websites composed of many different files with low latency.

    Also previously all GStreamer HTTP source elements closed their connection(s) when going back to the READY state, but it is required to set them to the READY state to switch URIs. Which basically means
    that although HTTP 1.1 allows to reuse connections for multiple requests, we were not able to make use of this. Now the souphttpsrc HTTP source element keeps connections open until it goes back to the NULL state if the keep-alive property is set to TRUE, and other HTTP source elements could implement this too. The HTTP adaptive streaming demuxers are making use of this “implicit interface” to reuse connections for multiple requests as much as possible.


    HTTP also defines a way for clients and servers to negotiate the encoding that both support. Especially this allows both to negotiate that the actual data (the response body) should be compressed with gzip (or another method) instead of transferring it as plaintext. For media fragments this is not very useful, for Manifests this can be very useful. Especially in the case of HLS, where the Manifest is a plaintext, ASCII file that can easily be a few 100 kb in size.

    The HTTP adaptive streaming demuxers are using another “implicit interface” on the HTTP source element to enable compression (if supported by the server) for Manifest files. This is also currently only handled in the souphttpsrc element.

    Other minor features

    HTTP defines many other headers, and the HTTP adaptive streaming demuxers make use of two more if supported by the HTTP source element. The “implicit interface” for setting more headers in the HTTP request is the extra-headers property, which can be set to arbitrary headers.

    The HTTP adaptive streaming demuxers are currently setting the Referer header to the URI of the Manifest file, which is not mandated by any standard to my knowledge so far but there are streams out there that actually forbid to download media fragments without that. And then the demuxers also set the Cache-Control header to 1) tell caches/proxies to update their internal copy of the Manifest file when redownloading it and b) to tell caches/proxies that some requests must not be cached (if indicated so in the Manifest). The latter can be ignored by the caches of course.

    If you implement your own HTTP source element it is probably a good idea to copy the interface of the souphttpsrc element at least for these properties.

    Caching HTTP source

    Another area that could easily be optimised is implementing a cache for the downloaded media fragments and also Manifests. This is especially useful for video-on-demand streams, and even more when the user likes to seek in the stream. Without any cache it would be required to download all media fragments again after seeking, even if the seek position was already downloaded before.

    A simple way for implementing this is a caching HTTP source element. This basically works like an HTTP cache/proxy like Squid, only one level higher. It behaves as if it is an HTTP source element, but actually it does magic inside.

    From a conceptual point of view this caching HTTP source element would implement the GstURIHandler interface and handle the HTTP(S) protocols, and ideally also implement some of the properties of souphttpsrc as mentioned above. Internally it would actually be a GstBin that dynamically creates a pipeline for downloading an URI when transitioning from the READY to the PAUSED state. It could have the following internal configurations:

    Caching HTTP Source

    The only tricky bits here are proxying of the different properties to the relevant internal elements, and error handling. You probably don’t want to stop the complete pipeline if for some reason writing to your cache file fails, or reading from your cache file fails. For that you could catch the error messages and also intercept data flow (to ignore error flow returns from filesink), and then dynamically reconfigure the internal pipeline as if nothing has happened.

    Based on the Cache-Control header you could implement different functionality, e.g. for refreshing data stored in your cache already. Based on the Referer header you could correlate URIs of media fragments to their corresponding Manifest URI. But how to actually implement the storage, cache invalidation and pruning is a standard problem of computer science and covered elsewhere already.

    Creating Streams – The Server Side

    And in the end some final words about the server side of things. How to create such HTTP adaptive streams with GStreamer and serve them to your users.

    In general this is a relatively simple task with GStreamer and the standard tools and elements that are already available. We have muxers for all the relevant container formats (one for the MP4 variant used in MPEG DASH is available in Bugzilla), there is API to request keyframes at specific positions (so that you can actually start a new media fragment at that position) and the dynamic pipeline mechanisms allow for dynamically switching muxers to start a new media fragment.

    On top of that it would only be required to create the Manifest files, and then serve all of this with some HTTP server. For which there are already too many implementations out there, and in the end you want to hide your server behind a CDN anyway.

    Additionally there are the hlssink and dashsink elements, the latter one just being in Bugzilla right now. These implement the creation of the media fragments already with the above mentioned GStreamer tools and generate a Manifest file for you.

    And then there is the GStreamer Streaming Server, which also has support for HTTP adaptive streaming protocols and can be used to easily serve multiple streams. But that one deserves its own article.

    by slomo at May 16, 2014 09:45 PM

    May 08, 2014

    Gustavo Orrillospheretess

    Processing 2.0 was released almost a year ago, and introduced many exciting improvements in several areas. Among those, a new OpenGL renderer with GLSL shader support. Since that time, the shader API – defined not only by the new functions in the Processing language to load and run shaders in a sketch, but also by […]

    by ac at May 08, 2014 06:19 PM

    May 06, 2014

    Zeeshan AliBerlin, DX hackfest, Boxes, rain

    (Zeeshan Ali)
    I just flew back from Berlin where I spent the last week, mainly to participate in the GNOME Developer Experience hackfest. As you can see from blog posts from other awesome gnomies, the hackfest was a pretty big success.

    I focused on the use of virtual machines (as thats right up my alley) for making application development as easy as possible. I talked to Christian, who has been working on an IDE for GNOME about his idea of a simulator VM which allows the developer to quickly test their app in a pristine environment. We discussed if and how Boxes can be involved. After some discussion we decided that we probably don't want to use Boxes but rather create another binary that re-uses the existing virtualization infrastructure: libvirt, qemu, spice (and maybe libosinfo) etc.

    Another way to make GNOME development easy through VM would be what we already have on a very crude level: Distribution of ready-made VMs with all the development environment setup. Continuous already creates and distributes ready VM disk images of latest GNOME (almost everything from git) and Boxes can import these images. These images however are insufficient and unreliable since they do not contain any metadata, especially recommended/required system resources, about the VM. Christian recommended VMware's wmx format but that turned out to only contain metadata instead and you'd need a separate file (vmdk) for the disk image with that. What we really need here is a format that contains both metadata and all disk images in one file, in other words a virtual appliance. After doing some research on this, I once again came to the conclusion that OVF is our only hope here. Not only its one file that can contain all important aspects of a VM, its an open standard that is agreed and implemented by many different vendors. Boxes being able to import/export from/to this format and Continuous being able to provide these virtual appliances wouldn't just enable a more reliable producer-consumer relationship between Continuous and Boxes but also allow individual developers to be easily able to share their work with others: "Hey! I've been working on this project/feature X last few days and want to get some input. I'm sending you the VM, just import it in Boxes and let me know what you think..".

    We've actually been wanting to have this feature for a very long time and I've mentioned the need for OVF support quite a few times so I decided its about time I do something about it. So during the hackfest, I designed the minimum interface for a library to convert from/to libvirt domain (or configuration) to/from OVF files and started the implementation too. I hope to continue working on it to have something demoable by end of this month.

    Some other discussions/activities I had during/around the hackfest:

    * Talked with Aleksander about modem enabling/disabling. Currently geoclue has to enable the modem itself for using it but since it doesn't know if the modem is in use by another application, it doesn't disable it after using it. This results in waste of battery power. I suggested to Aleksander that the best thing would be for ModemManager to take care of that as it knows if modem is in use or not. The alternative would be some kind of explicit UI but throwing this decision on user would be a terrible thing to do. Aleksander liked the idea and he promised to look into implementing it.

    * I took part in Gtk+ roadmap discussion, mostly as a silent observer (Gtk+ hackers and designers covered it nicely so I didn't feel like saying anything) but during the meeting I learnt of a widget that was introduced in 3.12 that I had missed completely, GtkFlowBox. Since developers were unhappy that we introduced a widget that is not used by any GNOME app and I realized that use of this widget in Boxes will bring me very close to my aim of dropping libgd usage, I decided to make Boxes the first user of this widget soon.

    * I realized (very late) that both my SoC studends live in Germany so I asked both of them if they can join us for any of the days. While it was impossible for baedert to join us on such short notice, Lasse was still able to make it for the last day. It was really nice to meet this very bright young fellow. We had a lot of discussion about past, present and future of Boxes. Lasse has already written a very nice and detailed blog post about that so I'll leave you with a link to that if you are interested.

    * Talked with Cosimo about use of Geoclue by Endless mobile.

    * Tested gnome-clang against Geoclue to provide feedback to Philip and it resulted in him fixing some important bugs.

    * Talked briefly to Lennart about
      * How authorization of geoclue-using apps will/can work in the kdbus world.
      * The best way to allow Boxes to access USB devices with ISO9660 filesystems on them.

    Thats mostly it! I would like to thank Lennart for providing me with a nice accommodation, Endocode for providing us a great venue (+ endless supply of Club mate) and GNOME foundation for sponsoring my travel.

    May 06, 2014 12:07 AM

    May 03, 2014

    GStreamerGStreamer Core and Plugins 1.3.1 development release


    The GStreamer team is pleased to announce the first release of the unstable 1.3 release series. The 1.3 release series is adding new features on top of the 1.0 and 1.2 series and is part of the API and ABI-stable 1.x release series of the GStreamer multimedia framework. The unstable 1.3 release series will lead to the stable 1.4 release series in the next weeks, and newly added API can still change until that point.

    Binaries for Android, iOS, Mac OS X and Windows will be provided separately during the unstable 1.3 release series.

    Check out the release notes for GStreamer core, gst-plugins-base, gst-plugins-good, gst-plugins-ugly, gst-plugins-bad, gst-libav, or gst-rtsp-server, or download tarballs for gstreamer, gst-plugins-base, gst-plugins-good, gst-plugins-ugly, gst-plugins-bad, gst-libav, or gst-rtsp-server, or

    Check the release announcement mail for details and the release notes above for a list of changes.

    May 03, 2014 08:00 PM