3389 stories
·
55 followers

Launching Pipewire!

1 Comment

In quite a few blog posts I been referencing Pipewire our new Linux infrastructure piece to handle multimedia under Linux better. Well we are finally ready to formally launch pipewire as a project and have created a Pipewire website and logo.Pipewire logo

To give you all some background, Pipewire is the latest creation of GStreamer co-creator Wim Taymans. The original reason it was created was that we realized that as desktop applications would be moving towards primarly being shipped as containerized Flatpaks we would need something for video similar to what PulseAudio was doing for Audio. As part of his job here at Red Hat Wim had already been contributing to PulseAudio for a while, including implementing a new security model for PulseAudio to ensure we could securely have containerized applications output sound through PulseAudio. So he set out to write Pipewire, although initially the name he used was PulseVideo. As he was working on figuring out the core design of PipeWire he came to the conclusion that designing Pipewire to just be able to do video would be a mistake as a major challenge he was familiar with working on GStreamer was how to ensure perfect audio and video syncronisation. If both audio and video could be routed through the same media daemon then ensuring audio and video worked well together would be a lot simpler and frameworks such as GStreamer would need to do a lot less heavy lifting to make it work. So just before we starting sharing the code publicaly we renamed the project to Pinos, named after Pinos de Alhaurín, a small town close to where Wim is living in southern Spain. In retrospect Pinos was probably not the worlds best name :)

Anyway as work progressed Wim decided to also take a look at Jack, as supporting the pro-audio usecase was an area PulseAudio had never tried to do, yet we felt that if we could ensure Pipewire supported the pro-audio usecase in addition to consumer level audio and video it would improve our multimedia infrastructure significantly and ensure pro-audio became a first class citizen on the Linux desktop. Of course as the scope grew the development time got longer too.

Another major usecase for Pipewire for us was that we knew that with the migration to Wayland we would need a new mechanism to handle screen capture as the way it was done under X was very insecure. So Jonas Ådahl started working on creating an API we could support in the compositor and use Pipewire to output. This is meant to cover both single frame capture like screenshot, to local desktop recording and remoting protocols. It is important to note here that what we have done is not just implement support for a specific protocol like RDP or VNC, but we ensured there is an advaned infrastructure in place to support any protocol on top of. For instance we will be working with the Spice team here at Red Hat to ensure SPICE can take advantage of Pipewire and the new API for instance. We will also ensure Chrome and Firefox supports this so that you can share your Wayland desktop through systems such as Blue Jeans.

Where we are now
So after multiple years of development we are now landing Pipewire in Fedora Workstation 27. This initial version is video only as that is the most urgent thing we need supported for Flatpaks and Wayland. So audio is completely unaffected by this for now and rolling that out will require quite a bit of work as we do not want to risk breaking audio on your system as a result of this change. We know that for many the original rollout of PulseAudio was painful and we do not want a repeat of that history.

So I strongly recommend grabbing the Fedora Workstation 27 beta to test pipewire and check out the new website at Pipewire.org and the initial documentation at the Pipewire wiki. Especially interesting is probably the pages that will eventually outline our plans for handling PulseAudio and JACK usecases.

If you are interested in Pipewire please join us on IRC in #pipewire on freenode. Also if things goes as planned Wim will be on Linux Unplugged tonight talking to Chris Fisher and the Unplugged crew about Pipewire, so tune in!

Read the whole story
jepler
1 day ago
reply
So apparently these guys have "multiple years of development" under their belt on this system, yet pipewire.org was registered 2017-07-23. Ambush of so called "Open Source" development.
Earth, Sol system, Western spiral arm
Share this story
Delete

Visiting all values in an array exactly once in “random order”

1 Comment

Suppose that you want to visit all values in an array exactly once in “random order”. You could do it by shuffling your array but it requires some extra storage.

You want your code to use just a tiny bit of memory, and you want the code to be super fast.

One way to do it is to use the fact that (a x + b) modulo n will visit all integer values in [0,n) exactly once as x iterates through the integers in [0, n), as long as a is coprime with n. Being coprime just means that the greatest common divisor between a and n is 1. There are fast functions to compute the greatest common divisor between a and n.

A trivial coprime number would be a = 1, but that’s bad for obvious reasons. So we pick a coprime number in [n/2,n) instead. There is always at least one no matter what n is.

Enumerating all coprime numbers in [n/2,n) could get tiresome when n is very large, so maybe we just look at up to 100,000 of them. There is no need to actually store them in memory, we can just select one at random, so it requires very little memory.

The running code is ridiculously simple:

    public int getCurrentValue() {
      return ( (long) index * prime + offset ) % ( maxrange);
    }

    public boolean hasNext() {
      return index < maxrange;
    }

    public int next() {
      int answer = getCurrentValue();
      index ++;
      return answer;
    }

There are various ways to optimize this code further (e.g., you can increment a counter instead of doing a multiplication), but it is likely faster than most other approaches people come up with in practice. Of course, it is not really random in the sense that no (good) statistician should accept the result as a fair shuffle of the indexes. Still, it might be “good enough” to fool your colleagues into thinking that it is random.

I make my Java code available. It can be made more elegant, but it should work just fine in your projects.

If you can find ways to make the result “look” more random without significantly making it slower and without increasing memory usage, please let us know.

Read the whole story
jepler
2 days ago
reply
how close can you come to generating a random permutation of the n integers 0,1,...,n-1 with O(log n) memory?
Earth, Sol system, Western spiral arm
Share this story
Delete

Computing the inverse of odd integers

1 Comment

Given x, its (multiplicative) inverse is another value y such that x y = y x = 1. We all know that the multiplicative inverse of x is 1/x and it exists as long as x is non-zero. That’s for real numbers, or at least, rational numbers.

But the idea of a multiplicative inverse is more general.

It certainly fails integers in general. I.e., there is no integer x such that 2 x is 1. But, maybe surprisingly, all odd integers have an inverse if you use normal computer arithmetic. Indeed, when your processor computes x y, then it actually outputs x y modulo 232 or x y modulo 264 depending on whether you use 32-bit or 64-bit instructions. (The value x y modulo 264 can be defined as the remainder of the division of x y by 264.)

Let me briefly explain why there must be an inverse. You can skip this part if you want. Take any odd integer x. Because x is odd, then it is not divisible by 2. In fact, that’s what it means to be odd. But this also means that powers of x will also be odd. E.g., xk is also odd for any integer k. Ok. So xk modulo 264 is never going to be zero. The only way it could be zero is if xk were divisible by 264, but that’s impossible because it is an odd value. At the same time, we only have a finite number of distinct odd values smaller than 264. So it must be the case that xk modulo 264 = xk' modulo 264 for some pair of powers k and k'. Assume without loss of generality that k is larger than k'. Then we have that xk-k' modulo 264 = 1 modulo 264 (I am not proving this last step, but you can figure it out hopefully). And thus it follows that xk-k'-1 is the inverse of x. If you did not follow this sketch of a proof, don’t worry.

So how do you find this inverse? You can brute force it, which works well for 32-bit values, but not so well for 64-bit values.

Wikipedia has a page on this, entitled modular multiplicative inverses. It points to an Euclidean algorithm that appears to rely on repeated divisions.

Thankfully, you can solve for the inverse efficiently using very little code.

One approach is based on “Newton’s method”. That is, we start with a guess and from the guess, we get a better one, and so forth, until we naturally converge to the right value. So we need some formula f(y), so that we can repeatedly call y = f(y) until y converges.

A useful recurrence formula is f(y) = y (2 - y x ) modulo 264. You can verify that if y is the 64-bit inverse of x, then this will output y. So the formula passes a basic sanity test. But would calling y = f(y) repeatedly converge to the inverse?

Suppose that y is not quite the inverse, suppose that x y = 1 + z 2N for some z and some N that is smaller than 64. So y is the inverse “for the first N bits”. That is, x y modulo 2N = 1.

It is easy to find such a y for N greater than zero. Indeed, let y = 1, then x y = 1 + z 21.

Ok, so substituting x y = 1 + z 2N in
y (2 - y x ) modulo 264, we get
y (2 - ( 1 + z 2N) ) modulo 264
or
y (1 - z 2N ) modulo 264.
So I set y' = f(y) = y (1 - z 2N ) modulo 264.
What is x y'? It is (1 + z 2N ) (1 - z 2N ) modulo 264
or (1 - z2 22 N ) modulo 264.

That is, if y was the inverse “for the first N bits”, then y' = f(y) is the inverse “for the first 2 N bits”. In some sense, I double my precision each time I call the recurrence formula. This is great! This means that I will quickly converge to the inverse.

Can we do better, as an initial guess, than y = 1? Yes. We can start with a very interesting observation: if we use 3-bit words, instead of 32-bit or 64-bit words, then every number is its own inverse. E.g., you can check that 3*3 modulo 8 = 1.

So a good initial guess is y = x, and that already buys us 3 bits. Next call gives me 6 bits, then 12 bits, then 24 bits, then 48 bits, then 96 bits, and so forth. So, we need to call our recurrence formula 4 times for 32-bit values and 5 times for 64-bit values. I could actually go to 128-bit values by calling the recurrence formula 6 times.

Here is the code to compute the inverse of a 64-bit integer:

uint64_t f64(uint64_t x, uint64_t y) {
  return  y * ( 2 - y * x );
}

static uint64_t findInverse64(uint64_t x) {
   uint64_t y = x; 
   y = f64(x,y);
   y = f64(x,y);
   y = f64(x,y);
   y = f64(x,y);
   y = f64(x,y);
   return y;
}

I wrote a complete command-line program that can invert any odd number quickly.

Each call to the recurrence formula should consume about 5 CPU cycles so that the whole function should take no more than 25 cycles or no more than the cost of a single integer division. Actually, it might be cheaper than a single integer division.

How did we arrive at this formula ( y (2 - y x ))? It is actually a straight-forward application of Newton’s method as one would apply it to finding the zero of g(y) = 1/y - x. So there is no magic involved.

My code seems to assume that I am working with unsigned integers, but the same algorithm works with signed integers, and in binary form, it will provide the same results.

Reference and further reading: Granlund and Montgomery, SIGPLAN Not. (1994).

Credit: Marc Reynolds ask on Twitter for an informal reference on computing the multiplicative inverse modulo a power of two. It motivated me to write this blog post.

Read the whole story
jepler
2 days ago
reply
Multiplicative inverses aren't useful in general for replacing division, because the method only works when the original division happens not to have any remainder. But in a contrived benchmark where that was true, it actually beats 64-bit integer division by about 16% elapsed time. I'm surprised, because about 15% more instructions.
Earth, Sol system, Western spiral arm
Share this story
Delete

A Battery-Tab Welder with Real Control Issues

1 Comment

Spot welding should easier than it looks. After all, it’s just a lot of current in a short time through a small space. But it’s the control that can make the difference between consistently high-quality welds and poor performance, or maybe even a fire.

Control is where [WeAreTheWatt]’s next-level battery tab spot welder shines. The fact that there’s not a microwave oven transformer to be seen is a benefit to anyone sheepish about the usual mains-powered spot welders we usually see, even those designed with safety in mind. [WeAreTheWatt] chose to power his spot welder from a high-capacity RC battery pack, but we’d bet just about any high-current source would do. The controller itself is a very sturdy looking PCB with wide traces and nicely machined brass buss bars backing up an array of MOSFETs. A microcontroller performs quite a few functions; aside from timing the pulse, it can control the energy delivered, read the resistance of the 8AWG leads for calibration purposes, and even detect bad welds. The welder normally runs off a foot switch, but it can also detect when the leads are shorted and automatically apply a pulse — perfect for high-volume production. See it in action below.

There may be bigger welders, and ones with a little more fit and finish, but this one looks like a nicely engineered solution.

Thanks to [mick hanks] for the tip.


Filed under: tool hacks



Read the whole story
jepler
4 days ago
reply
eep is it really safe to hold the uninsulated metal leads like that !?
Earth, Sol system, Western spiral arm
Share this story
Delete

The New Adventures of Queen Victoria: Saturday September 16, 2017

2 Comments
Read the whole story
jepler
4 days ago
reply
they copied Microsoft's skip from 8 to 10, and nobody really knows why. It's not like there was an "iphone 95"...
Earth, Sol system, Western spiral arm
Share this story
Delete
1 public comment
drchuck
4 days ago
reply
Think of the children!!
Long Island, NY

Artificial Intelligence Pioneer Says We Need To Start Over

1 Comment
Steve LeVine, writing for Axios: In 1986, Geoffrey Hinton co-authored a paper that, four decades later, is central to the explosion of artificial intelligence. But Hinton says his breakthrough method should be dispensed with, and a new path to AI found. Speaking with Axios on the sidelines of an AI conference in Toronto on Wednesday, Hinton, a professor emeritus at the University of Toronto and a Google researcher, said he is now "deeply suspicious" of back-propagation, the workhorse method that underlies most of the advances we are seeing in the AI field today, including the capacity to sort through photos and talk to Siri. "My view is throw it all away and start again," he said. Other scientists at the conference said back-propagation still has a core role in AI's future. But Hinton said that, to push materially ahead, entirely new methods will probably have to be invented. "Max Planck said, 'Science progresses one funeral at a time.' The future depends on some graduate student who is deeply suspicious of everything I have said."
Read the whole story
jepler
5 days ago
reply
AIs frequently get stuck on local maxima, sometimes for generations. AI researchers too, I guess.
Earth, Sol system, Western spiral arm
Share this story
Delete
Next Page of Stories