Car fobs have a security problem. If you’ve parked your car in front of your house someone can relay messages between your key fob and your car, get your car to unlock, get in, and drive off.

This attack is possible because of a sensor problem: The fob and car rely on the strength of the signal between them to sense how far away they are from each other, and that strength can be boosted by an attacker. Thankfully there’s an improved method of sensing distance which is long overdue for being the standard technique, which is to rely on the speed of light. If the fob and car are close enough the round trip time between the two will be low, and if they’re too far away then an intermediary echoing messages can’t reduce the round trip time, only increase it. Thank you absolute speed of light.

As compelling as this is in principle implementing it can be tricky because the processing on the end point needs to be faster than the round trip time. Light goes about a foot in a nanosecond, so you want your total processing time down to a few nanoseconds at the most. This is plenty of time for hardware to do something, but between dodgy and impossible to do any significant amount of computation. But there’s a silly trick for fixing the problem.

Any protocol between the car and fob will end with one final message sent by the fob. To make it round trip secure the fab instead signals to the car that it’s ready to send the final message at which point the car generates a random one time pad and sends it back to the fob, at which point the fob xors the final message with the pad and sends that as the final message. The car can then xor again to get the real final message, authenticate it however is required of the underlying protocol, and if the round trip time on the final message was low enough open up. This allows the fob to calculate its final message at its leisure then load it into something at the hardware level which does xor-and-pong. A similar hardware level thing on the car side can be told to generate a ping with one time pad, then return back the pong message along with a round trip time to receive it. That way all the cryptography can be done at your leisure in a regular programming environment and the low latency stuff is handled by hardware. If you want to be fancy when making the hardware you can even support an identifying code which needs to match on the sending and receiving sides so messages don’t interfere with each other.

Distance detection used on point of sale devices should also work this way. That would have the benefit you wouldn’t have to smush the paying device’s face right into the point of sale machine just to get a reading. The protocol should be a little different for that because in a real payment protocol the paying device should authenticate the point of sale machine rather than the other way around. But the credit card approach does things backwards, and it seems likely that if hardware capability of this sort of thing is built into phones it will be the wrong side.

Someone posted this in a comment on my "sleepy seaside town" post, but this rant goes so hard that I think it deserves its own post:

In my last post (which this post is a superior rehashing of after thinking things over more) I talked about ‘chaos’ which seemed to leave some people confused as to what that meant. Despite being a buzzword which is thrown around in pop science a lot chaos is a real mathematical term with a very pedestrian definition, which is sensitive dependence on initial conditions. It’s a simultaneously banal and profound observation to point out that neural networks as we know them today are critically dependent on not having sensitive dependence on initial conditions in order for back propagation to work properly.

It makes sense to refer to these as ‘sublinear’ functions, a subset of all nonlinear functions. It feels like the details of how sublinear functions are trained don’t really matter all that much. More data, training, and bigger models will get you better results but still suffer from some inherent limitations. To get out of their known weaknesses you have to somehow include superlinear functions, and apply a number of them stacked deep to get the potential for chaotic behavior. LLMs happen to need to throw in a superlinear function because picking out a word among possibilities is inherently superlinear. To maximize an LLMs performance (or at least its superlinearity) you should make it output a buffer of as many relevant words as possible in between the question and where it gives an answer, to give it a chance to ‘think out loud’. Instead of asking it to simply give an answer, ask it to give several different answers, then make give arguments for and against each of those, then give rebuttals to those arguments, then write several new answers taking all of that into account, repeat the exercise of arguments for and against with rebuttals, and finally pick out which if its answers is best. This is very much in line with the already known practical ways of getting better answers out of LLMs and likely to work well. It also seems like a very human process which raises the question of whether the human brain also consists of a lot of sublinear regions with superlinear controllers. We have no idea.

What got me digging into the workings of LLMs was that I got wind that they use dot products in a place and wondered whether the spatial clustering I’ve been working on could be applied. It turns out it can’t, because it requires gradient descent, and gradient descent on top of being expensive is also extremely chaotic. But there is a very simple thing which is sublinear which can be tried: Apply RELU/GRELU to the key and query vectors (or maybe just one of them, a few experiments can be done) before taking their dot product. You might call this the ‘pay attention to the man behind the curtain’ heuristic, because it works with the intuition that there can be reasons why you should pay special attention to something but not many reasons why you shouldn’t.

For image generation the main thing you need is some kind of superlinear function applied before iterations of using a neural network to make the image better. With RGB values expressed as being between 0 and 1 it appears that the best function is to square everything. The reasoning here is that you want the second derivative to be as much as possible everywhere and evenly spread out while keeping the function monotonic and within the defined range. The math on that yields two quadratics, x^2 and its cousin -x^2+2x. There are a few reasons why this logical conclusion sounds insane. First there are two functions for no apparent reason. Maybe it makes sense to alternate between them? Less silly is that it’s a weird bit of magic pixie dust, but then adding random noise is also magic pixie dust but seems completely legit. It also does something cognitively significant, but then it’s common for humans to make a faint version of an image and draw over it and this seems very reminiscent of that. The point of making the image faint is to be information losing, and simply multiplying values isn’t information losing within the class of sublinear functions while square is because if you do it enough times everything gets rounded down to zero.

Frustratingly image classification isn’t iterated and so doesn’t have an obvious place to throw in superlinear functions. Maybe it could be based off having a witness to a particular classification and have that be iteratively improved. Intuitively a witness traces over the part of the image which justifies the classification, sort of like circling the picture of Waldo. But image classification doesn’t use witnesses and it isn’t obvious how to make them do that so a new idea is needed.

DeSantis signs bill, says Satanists can't be school chaplains:

"Some have said that if you do a school chaplain program, that somehow you're going to have Satanists running around in all our schools," he said at a press conference [...]

"Despite DeSantis's contempt for religious liberty, the Constitution guarantees our equal treatment under the law, and DeSantis is not at liberty to amend the Constitution by fiat, at whim," said Lucien Greaves, co-founder of the The Satanic Temple. "He just invited Satanic chaplains into public schools, whether he likes it or not." [...]

"There's some students who need some soulcraft, and that can make all the difference in the world," DeSantis said.

Previously, previously, previously, previously, previously, previously, previously.

Even if there are no legal consequences from any of these trials, it's important to remember that the whole thing just makes him really angry.

And that is a gift that we must treasure.

Trump Rages About His Trial Sketch Artist, Courtroom Nap Reports:

He has privately raged over everything from reports that he can't stop dozing off, to how the court sketch artist is rendering him, to late-night talk show hosts joking about his legal troubles. The former president is reaching levels of fury over the judicial process and all it entails that are "maxed out, even for him," says one source who has had to personally endure Trump's recent rantings about his trial. [...]

Trump has also privately asked people close to him if they agree that the courtroom sketch-artist must be out to get him, two of the sources say. [...]

"I was actually just thinking this morning about how cold [Trump] kept complaining to be yesterday. In his normal world, someone would have jumped up and run, not walked, to get the temperature perfect for him," says Stephanie Grisham, Trump's former White House press secretary who fell out with him years ago. "This entire experience must be beyond uncomfortable for him, not just the fact that it dives into such personal details, but he has absolutely no control for probably the first time since he was a young child."

Grisham adds that Trump being on trial this week "reminded me that not only in the White House, but every facet of his life -- be it at Mar-a-Lago or Trump Tower or Bedminster -- he has a group of people that cater to his every whim. At Mar-a-Lago, people literally stand and applaud him just for walking into the room, and in court, he has to sit there quietly while some people talk about how much they don't like him. I can't imagine how hard it has been for him not to get up and storm out of the place like a five-year-old."

Previously, previously, previously, previously, previously, previously, previously, previously.

A recent scientific expedition to the Gulf of Mexico seafloor shows just how little things have improved near the broken well.

The absence of life is noticeable, says McClain, and what is there doesn't seem healthy. Unlike other wrecks, which tend to become habitats for marine species over time, the sunken Deepwater Horizon has remained comparatively sterile. Organisms that typically inhabit the Gulf's seafloor -- such as sea cucumbers, giant isopods, corals, and sea anemones -- are simply missing, says McClain. Perhaps more concerning are the crabs. Naturally red, the crabs McClain and his team pulled up in their traps were tinted an oily black; many were also missing legs, while others had lesions. [...]

Benfield had visited the oil spill site before, including shortly after the explosion in 2010. He also joined the first scientific research expedition to the exploded wellhead in 2017. When Benfield saw the site then, he was shocked by how little it had recovered. Another seven years on, Benfield says researchers are slowly starting to see more animals. There's "more diversity of fishes and macroinvertebrates," he says. But compared with before the explosion, the site remains a desert, Benfield adds.

For those who embarked on the most recent expedition, the dire sight has them questioning how the Gulf will fare in the future. "We may not actually ever see recovery," [...] "Maybe in my kid's lifetime. But it's going to take a long time, I think."

Previously, previously, previously, previously, previously, previously, previously.

"Post dot news", the Andreessen-funded cryptocurrency grift masquerading as a social network, that considered dunking on billionaires to be hate speech, and that created fake "placeholder" accounts to try and get their users to bully news organizations into signing up... is shutting down.

Something something "incredible journey".

Previously, previously, previously, previously, previously, previously, previously, previously, previously.

Yo, check it. Friday May 17th. That's right, we're doing another CYBERDELIA.

As per longstanding tradition, we are dressing up DNA Lounge as Cyberdelia, the club from the movie HACKERS! This means a 90s cyberpunk movie screening followed by a 90s cyberpunk dance party! Also featuring retro video games, rollerblade ramps, and a costume contest!

But this time we're branching out just a little bit: instead of our traditional pre-party viewing of HACKERS, we will instead be screening the 1995 Keanu Reeves cyberpunk classic, JOHNNY MNEMONIC! The year is 2021 and Johnny is smuggling 160 gigabytes of data in his overloaded brain implant, on the run from zaibatsu assassins. (You may know him better as Johnny Silverhands: Mnemonic was his maiden name.) Dolph Lundgren, Ice T and Henry Rollins co-star. Screenplay by William Gibson himself.

The last time we did a Cyberdelia with a pre-show that was not literally Hackers was that time when we did Tank Girl instead, and some people were confused by that, so lemme emphasize that from 10pm onward this is exactly the same party as all those other times, we're just watching a different movie first.

As I was painstakingly putting the mayonnaise into the bottles putting the new and improved labels on the Cyberdelia floppy flyers, I came across a few classic disks that I was not able to make myself plaster over, see wondrous artifacts below.

Number of times in the last week that I heard a customer ask a bartender, "Are these... coasters??"

Four.

Cops can force suspect to unlock phone with thumbprint, US court rules:

The US Constitution's Fifth Amendment protection against self-incrimination does not prohibit police officers from forcing a suspect to unlock a phone with a thumbprint scan, a federal appeals court ruled yesterday. [...]

Judges rejected his claim, holding "that the compelled use of Payne's thumb to unlock his phone required no cognitive exertion, placing it firmly in the same category as a blood draw or fingerprint taken at booking."

"When Officer Coddington used Payne's thumb to unlock his phone -- which he could have accomplished even if Payne had been unconscious -- he did not intrude on the contents of Payne's mind," the court also said. [...]

Payne conceded that "the use of biometrics to open an electronic device is akin to providing a physical key to a safe" but argued it is still a testimonial act because it "simultaneously confirm[s] ownership and authentication of its contents," the court said.

Previously, previously, previously, previously, previously, previously, previously, previously.

Previously, previously, previously, previously, previously, previously, previously.

For the last few months, Benjamin Tissoires and I have been working on and polishing a little tool called udev-hid-bpf [1]. This is the scaffolding required quickly and easily write, test and eventually fix your HID input devices (mouse, keyboard, etc.) via a BPF program instead of a full-blown custom kernel driver or a semi-full-blown kernel patch. To understand how it works, you need to know two things: HID and BPF [2].

Why BPF for HID?

HID is the Human Interface Device standard and the most common way input devices communicate with the host (HID over USB, HID over Bluetooth, etc.). It has two core components: the "report descriptor" and "reports", both of which are byte arrays. The report descriptor is a fixed burnt-in-ROM byte array that (in rather convoluted terms) tells us what we'll find in the reports. Things like "bits 16 through to 24 is the delta x coordinate" or "bit 5 is the binary button state for button 3 in degrees celcius". The reports themselves are sent at (usually) regular intervals and contain the data in the described format, as the devices perceives reality. If you're interested in more details, see Understanding HID report descriptors.

BPF or more correctly eBPF is a Linux kernel technology to write programs in a subset of C, compile it and load it into the kernel. The magic thing here is that the kernel will verify it, so once loaded, the program is "safe". And because it's safe it can be run in kernel space which means it's fast. eBPF was originally written for network packet filters but as of kernel v6.3 and thanks to Benjamin, we have BPF in the HID subsystem. HID actually lends itself really well to BPF because, well, we have a byte array and to fix our devices we need to do complicated things like "toggle that bit to zero" or "swap those two values".

If we want to fix our devices we usually need to do one of two things: fix the report descriptor to enable/disable/change some of the values the device pretends to support. For example, we can say we support 5 buttons instead of the supposed 8. Or we need to fix the report by e.g. inverting the y value for the device. This can be done in a custom kernel driver but a HID BPF program is quite a lot more convenient.

HID-BPF programs

For illustration purposes, here's the example program to flip the y coordinate. HID BPF programs are usually device specific, we need to know that the e.g. the y coordinate is 16 bits and sits in bytes 3 and 4 (little endian):

SEC("fmod_ret/hid_bpf_device_event")
int BPF_PROG(hid_y_event, struct hid_bpf_ctx *hctx)
{
	s16 y;
	__u8 *data = hid_bpf_get_data(hctx, 0 /* offset */, 9 /* size */);

	if (!data)
		return 0; /* EPERM check */

	y = data[3] | (data[4] << 8);
	y = -y;

	data[3] = y & 0xFF;
	data[4] = (y >> 8) & 0xFF;

	return 0;
}
  

That's it. HID-BPF is invoked before the kernel handles the HID report/report descriptor so to the kernel the modified report looks as if it came from the device.

As said above, this is device specific because where the coordinates is in the report depends on the device (the report descriptor will tell us). In this example we want to ensure the BPF program is only loaded for our device (vid/pid of 04d9/a09f), and for extra safety we also double-check that the report descriptor matches.

// The bpf.o will only be loaded for devices in this list
HID_BPF_CONFIG(
	HID_DEVICE(BUS_USB, HID_GROUP_GENERIC, 0x04D9, 0xA09F)
);

SEC("syscall")
int probe(struct hid_bpf_probe_args *ctx)
{
	/*
	* The device exports 3 interfaces.
	* The mouse interface has a report descriptor of length 71.
	* So if report descriptor size is not 71, mark as -EINVAL
	*/
	ctx->retval = ctx->rdesc_size != 71;
	if (ctx->retval)
		ctx->retval = -EINVAL;

	return 0;
}

Obviously the check in probe() can be as complicated as you want.

This is pretty much it, the full working program only has a few extra includes and boilerplate. So it mostly comes down to compiling and running it, and this is where udev-hid-bpf comes in.

udev-hid-bpf as loader

udev-hid-bpf is a tool to make the development and testing of HID BPF programs simple, and collect HID BPF programs. You basically run meson compile and meson install and voila, whatever BPF program applies to your devices will be auto-loaded next time you plug those in. If you just want to test a single bpf.o file you can udev-hid-bpf install /path/to/foo.bpf.o and it will install the required udev rule for it to get loaded whenever the device is plugged in. If you don't know how to compile, you can grab a tarball from our CI and test the pre-compiled bpf.o. Hooray, even simpler.

udev-hid-bpf is written in Rust but you don't need to know Rust, it's just the scaffolding. The BPF programs are all in C. Rust just gives us a relatively easy way to provide a static binary that will work on most tester's machines.

The documentation for udev-hid-bpf is here. So if you have a device that needs a hardware quirk or just has an annoying behaviour that you always wanted to fix, well, now's the time. Fixing your device has never been easier! [3].

[1] Yes, the name is meh but you're welcome to come up with a better one and go back in time to suggest it a few months ago.
[2] Because I'm lazy the terms eBPF and BPF will be used interchangeably in this article. Because the difference doesn't really matter in this context, it's all eBPF anyway but nobody has the time to type that extra "e".
[3] Citation needed

I’ve been looking into the inner workings of neural networks and have some thoughts about them. First and foremost the technique of back propagation working at all is truly miraculous. This isn’t an accident of course, the functions used are painstakingly picked out so that this amazing back propagation can work. This puts a limitation on them that they have to be non-chaotic. It appears to be that non-chaotic functions as a group are something of a plateau, sort of like how linear functions are a plateau, but with a much harder to characterize set of capabilities and weaknesses. But one of them is that they’re inherently very easy to attack using white box techniques and the obvious defenses against those attacks, very much including the ones I’ve proposed before, are unlikely to work. Harumph.

To a first approximation the way to get deep neural networks to perform better is to fully embrace their non-chaotic nature. The most striking example of this is in LLMs whose big advance was to dispense with recursive state and just use attention. The problem with recursiveness isn’t that it’s less capable. It’s trivially more general so at first everyone naively assumed it was better. The problem is that recursiveness leads to exponentialness which leads to chaos and back propagation not working. This is a deep and insidious limitation, and trying to attack it head on tends to simply fail.

At this point you’re probably expecting me to give one weird trick which fixes this problem, and I will, but be forewarned that this just barely gets outside of non-chaos. It isn’t about to lead to AGI or anything.

The trick is to apply the non-chaotic function iteratively with some kind of potentially chaos-inducing modification step thrown in between. Given how often chaos happens normally this is a low bar. The functions within deep neural networks are painstakingly chosen so that their second derivative is working to keep their first derivative under control at all times. All the chaos inducing functions have to do is let their second derivative’s freak flag fly.

LLMs do this by accident because they pick a word at a time and the act of committing to a next word is inherently chaotic. But they have a limitation that their chaoticism only comes out a little bit at a time so they have to think out loud to get anywhere. LLM performance may be improved by letting it run and once in a while interjecting that now is the time to put together a summary of all the points and themes currently in play and give the points and themes it intends to use in the upcoming section before it continues. Then in the end elide the notes. In addition to letting it think out loud this also hacks around context window problems because information from earlier can get carried forward in the summaries. This is very much in the vein of standard issue LLM hackery and has a fairly high chance of working. It also may be useful writing advice to humans whose brains happen to be made out of neural networks.

Applying the same approach to image generation requires repeatedly iterating on an image to improve it with each stage. Diffusion sort of works this way, although it works off the intuition that further details are getting filled in each time. This analysis seems to indicate that the real benefit is that making a pixellated image is doing something chaotic, on the same order of crudeness as forcing the picking out of a next word from an LLM. Instead it may better to make each step work on a detailed image and apply something chaos-inducing in between. It may be that adding gaussian noise works, but as ridiculous as it sounds in principle doing color enhancement using a cubic function should work far better. I have no idea if this idea actually works. It sounds simultaneously on very sound mathematical footing and completely insane.

Annoyingly I don’t see a way of doing image classification as an iterative process with something chaos-inducing in between steps. Maybe there’s another silly trick there which would be able to make the white box attacks not work so well.

Side note: It seems like there should be a better term for a function which is ‘not non-chaotic’. They don’t have to be at all chaotic themselves, just contain the seeds of chaos. Even quadratic functions fit the bill, although cubic ones are a bit easier to throw in because they can be monotonic.

Embeddable Game Engine

Many years ago, when working at Xamarin, where we were building cross-platform libraries for mobile developers, we wanted to offer both 2D and 3D gaming capabilities for our users in the form of adding 2D or 3D content to their mobile applications.

For 2D, we contributed and developed assorted Cocos2D-inspired libraries.

For 3D, the situation was more complex. We funded a few over the years, and we contributed to others over the years, but nothing panned out (the history of this is worth a dedicated post).

Around 2013, we looked around, and there were two contenders at the time, one was an embeddable engine with many cute features but not great UI support called Urho, and the other one was a Godot, which had a great IDE, but did not support being embedded.

I reached out to Juan at the time to discuss whether Godot could be turned into such engine. While I tend to take copious notes of all my meetings, those notes sadly were gone as part of the Microsoft acquisition, but from what I can remember Juan told me, "Godot is not what you are looking for" in two dimensions, there were no immediate plans to turn it into an embeddable library, and it was not as advanced as Urho, so he recommended that I go with Urho.

We invested heavily in binding Urho and created UrhoSharp that would go into becoming a great 3D library for our C# users and worked not only on every desktop and mobile platform, but we did a ton of work to make it great for AR and VR headsets. Sadly, Microsoft's management left UrhoSharp to die.

Then, the maintainer of Urho stepped down, and Godot became one of the most popular open-source projects in the world.

Last year, @Faolan-Rad contributed a patch to Godot to turn it into a library that could be embedded into applications. I used this library to build SwiftGodotKit and have been very happy with it ever since - allowing people to embed Godot content into their application.

However, the patch had severe limitations; it could only ever run one Godot game as an embedded system and could not do much more. The folks at Smirk Software wanted to take this further. They wanted to host independent Godot scenes in their app and have more control over those so they could sprinkle Godot content at their heart's content on their mobile app (demo)

They funded some initial work to do this and hired Gergely Kis's company to do this work.

Gergely demoed this work at GodotCon last year. I came back very excited from GodotCon and I decided to turn my prototype Godot on iPad into a complete product.

One of the features that I needed was the ability to embed chunks of Godot in discrete components in my iPad UI, so we worked with Gergely to productize and polish this patch for general consumption.

Now, there is a complete patch under review to allow people to embed arbitrary Godot scenes into their apps. For SwiftUI users, this means that you can embed a Godot scene into a View and display and control it at will.

Hopefully, the team will accept this change into Godot, and once this is done, I will update SwiftGodotKit to get these new capabilities to Swift users (bindings for other platforms and languages are left as an exercise to the reader).

It only took a decade after talking to Juan, but I am back firmly in Godot land.

Let’s say that you’re the purveyor of some toxic foodstuff and want to keep selling more of it. To be fair, the foodstuff you’re selling isn’t always toxic: It’s fine in small quantities, and under some circumstances can be a lifesaver, but in large quantities it’s demonstrably bad for almost everyone. You being a sociopath view ruining the health of the entire society you’re a part of as less important than your sales profits and want to generate some kind of PR campaign to cover for the evils of your product. How do you go about doing it?

A standard practice of toxic people is to preemptively accuse someone else of doing exactly what it is that they’re doing to try to make it look like the other party is making an identical counter-claim out of retribution when they finally get busted. It can be truly comical how specific these accusations can be, to the point of giving away details of their own misdeeds which others haven’t even looked into yet. In our foodstuffs example, what would you want to demonize? You’d want to find some other foodstuff which is critically important to health but you could plausibly claim is bad in large quantities. On top of that, you want to demonize something which won’t fight back. Something which has magically gone from a bottleneck in the population of the human race to so cheap that there’s no industry of producers or lobbying group in charge of promoting it.

You may by now have guessed that I’m talking about sugar and salt. Sugar is of course at the core of the obesity epidemic. Salt on the other hand has gone from something whose trade was a big part of the economy of all inland societies to essentially free thanks to improvements in transportation technology. While in the short run measuring increase in GDP or ‘value creation’ can be a good measure of how well off society is as a whole in some cases it can miss the big picture because it isn’t a direct measure of the ‘value’ of what’s being created, it’s a measure of the friction which is still left. If some new technology is so good that instead of the size of the market with the amount friction left going up proportionately it makes the amount of friction go to near zero then optically the economic measures make it look like society is worse off. This effect becomes overwhelming over the long run.

One of the most dramatic examples of this in history is decrease in costs of salt, which made it the ideal punching bag for the sugar industry. There is no Big Salt. That fancy salt you buy in the store is a luxury version whose costs are completely unnecessary. Even the cheap seemingly nearly free versions you get the cost mostly comes from putting in in the packaging and stocking it on store shelves. If you were to truly optimize the cost of salt then when a baby was born you’d buy them a lifetime supply of salt for $5 and they’d never worry about it, and that’s including the labor cost of transportation supply chain in a first world country. Salt isn’t quite the most dramatic example of a cost drop ever - if you value internet bandwidth usage at what telegrams used to cost you’ll get truly ridiculous numbers - but it’s up there.

And demonization of salt is exactly what happened. For decades official guidance from doctors, the government, and seemingly all forms of authority was that the big thing everybody should do to improve their health is to cut back on salt while sugar was ignored, or even outright promoted with processed desserts advertising ‘fat free’ as if being pure sugar was healthier. I’m not going to go into the details of whether excessive salt is actually bad for you, the point is it is not and never could be the scourge which sugar is and it was made the fall guy for that.

But then what do I know, I’m an unabashed shill for Big Probability.

I previously explained how to merge a single line of code in support of supporting cherry picking and local undo. In there I suggested that pulling in ‘orphan’ changes without their dependencies, then letting them kick in when the dependencies get merged may be useful. On reflection I think this is a bad idea, or at least have more confidence in getting the same effect in other ways.

For cherry-picking my confusion has a lot to do with UX. For some reason I’ve always envisioned cherry-picking as saying ‘Make a patch of the changes from commit X to commit Y and apply them to this branch’, possibly because that’s sort of the way patch files work. Allowing orphan history would support that done verbatim, but it seems to have a problem with what happens if the dependencies get merged piecemeal, resulting in bizarre and likely erroneous behavior. Much better than specifying the changes to be pulled over as being between two commits is to specify them as line ranges from a single commit, with the complete history of those lines pulled in with them. This makes the behavior of merging in dependent commits clear: They’re ignored because they’re already included. There’s an interesting nuance around whether to include context lines and ghost lines which have been deleted immediately adjacent to the line range specified, but that’s a minor UX problem.

This is aggressively explicit rather than implicit cherry-picking. As with the other cases it seems like doing things implicitly is just plain a bad idea. Lines of code identities might not line up of a bunch of changes have been squashed into a single commit. Even if the lines of code do line up if someone makes a change then locally undoes it that shouldn’t cause merges with outside things to be any different than if the changes had never happened and assuming that similar looking changes are actually the same violates that principle. When you don’t have support for explicit cherry picking trying to make support for it implicitly may be the least bad option but when doing it the right way is an option there’s no need to try to support the fundamentally problematic bad way.

Next up is the more difficult case of local undo. I recently realized the scope of the undo needs to be specified by merging an undo of the undo into main or the feature branch so that the feature doesn’t get deleted when everything is merged together. I previously suggested this could be done by taking merging a literal undo of the undo into main with orphan history. This is a reasonable thought but has some problems. It requires some very explicit references to commit ids in the UX, and if the undo itself is done in a series of commits then the behavior will be erratic if they’re merged in one at a time. This is probably a case of ‘if you have a hammer every problem looks like a nail’: I’ve gotten far enough along with supporting stuff with the merge algorithm that there’s a temptation to add more features to it to support more, but orphan history is going a bit too far and is best avoided.

The improved approach is this one: After a local undo is done, cherry-pick the undo into main, but instead of merging it force the resulting value to leave main unchanged then commit that result. This has to be explicit cherry-picking as mentioned above, where the scope is limited by line ranges. This has all the features desired: Merge behavior with branches off main which are pulled in later will be unaffected, when the changes to the backed out branch are pulled in piecemeal they’ll simply be ignored, and there’s no need for orphan history. This is in some sense still the cherry-pick-but-ignore approach I suggested before, but it’s important to point out that the principle still applies with the improved approach to cherry picking. One potential problem is that if there are changes which weren’t in main and are supposed to stay but were backed out during the undo then they’ll be deleted in a merge, but in that case the feature branch was ahead of main and the undo of the undo should have been put into the feature branch, not main.

Eventually I’ll spend an off day on merging and actually start writing some code instead of finding more theory to work through. I’m still fretting about some of the issues around detecting and presenting conflicts. But that may be the last of the theory issues. I probably won’t write full code for the above features because implementing them as stated is trivial on top of the library I’ll write with the real problems being a UX one of specifying the line ranges. This is of course on top of the several other hobby projects I have which actually seem important.

Inspired by the Spectre tile I’ve generated more ‘spectroids’ which have what I believe are the most notable features of the Spectre: Alternating hexagonal and square angles, and if you color the edges in two colors so that they change color whenever it takes a 90 degree angle and otherwise stays the same then taking just the edges of each color forms a closed loop.

Craig Kaplan has made this very nice applet for exploring these and larger ones and Dave Smith has made this fun post about the Golem, a shape he pulled out of a more expanded list.

Disappointingly none of these other than the Spectre tile only aperiodically but maybe they have other interesting properties.

.

I recently made progress on supporting real cherry-picking, and even more importantly supporting real local undo. This leaves a surprisingly subtle question: When doing a merge, how do you decide if a given line is included or not?

The simplest way of merging a single line is for its state to be a generation count. If it has never existed it gets a count of 0. When it’s first made it gets a count of 1. When it’s deleted again it gets a count of 2, when recreated 3, etc. When merging together two things the greater generation count for each line wins. This unfortunately fails horribly when trying to do a local undo. As I mentioned in that other post, the UX for doing a local undo should be that you perform your backing out change locally, then make a patch (with extra metadata) which reverts that backing out and apply that patch to the main branch. That way the main branch ignores the backing out when a merge eventually happens. Central to this is that the backing out patch should do nothing to the main branch until the eventual merge and just cause that to get ignored. Generation counts most definitely do not do that, because while you can make an undo patch it will work by having yet even higher generation count numbers which will change the behavior of the main branch when it merges with other things.

I now have an alternative metadata format and semantics which appears to behave as desired. There are a lot of potential edge cases here, including cherry picking, undo cherry picking, applying changes across those, etc. It’s possible that there are edge cases what I’m about to say gets wrong, or some kind of an impossibility proof that you can’t get all desired edge case behavior right, or maybe this does everything right and there’s some way to derive it on first principles. I don’t have any of those things and am presenting what I’ve come up with as what appears to be the best idea so far.

The core idea is that each commit is given its own id, and the actions of a commit on a single line are that it can obviate the actions of earlier commits. To make it possible to bring lines of code into existence in the first place a bit of history is observed: At the beginning of time all lines of code existed then they were all deleted in the great nil commit. There’s probably some deep spiritual insight which can be gleaned from this, but I’m just going to use it for implementation convenience. The first creation of a line obviates the nil commit.

In summary the state of a given line is {commit_id: [earlier_commit_id]} with the earlier commit id’s being things it overrides. In order to support cherry picking it should also have a bit giving whether it adds or deletes the line, because the path to nil might not be completely included locally. To figure out if the line of code of interest is currently included you find a commit id which none of the other commits are attempting to obviate, then remove both that commit and all the commits it obviates from the list (some of them may already be not there if there’s a cherry pick). Repeat this until there are no records left. If at any point along the way the nil commit was obviated then the line of code is present. If it wasn’t then it’s not.

That was a bit of a mouthful without clear motivation. The strategy behind how to interpret the meaning of a change and turn it into metadata helps explain. The simplest ambiguous example is that you have a line of code which was previously added and removed and now it’s re-added again. Because you want changes to generally be ‘local’ it’s a good idea to interpret this as obviating the commit which did the removal rather than obviating the original nil commit. That leaves the question of what to do when there are multiple options as to how to get to where you want. For example two different branches might have separately added and removed the same line and then those were merged together and now you locally added the line again. Guessing either of them could result in truly bizarre behavior when merging with other things, so the only sane thing to do is all of them. When doing an add find all earlier removal commits which don’t already have some commit trying to obviate them and obviate all of those. Likewise when doing a removal find all earlier add commits which don’t already have something trying to obviate them and obviate all of those. This includes hitting commits which aren’t currently having any effect because they were cherry-picked, which seems to be necessary to avoid some weird edge cases. A nice feature of this approach is that if a line is locally added and removed it’s always down to that final commit being the only one which is currently relevant so the complexity of historical changes is swept away quickly even for very complex cases.

I continue to believe that good support for local undo is the feature which finally makes weave-based version control clearly superior to rebase-based hackery. (One could argue that taking all that developer time should have done it already, but people have been willing to put up with it.) This insight about how to merge individual lines is the final puzzle piece to make that possible. I don’t know why I didn’t manage to figure this all out twenty years ago, but better late than never.

Touchscreens are quite prevalent by now but one of the not-so-hidden secrets is that they're actually two devices: the monitor and the actual touch input device. Surprisingly, users want the touch input device to work on the underlying monitor which means your desktop environment needs to somehow figure out which of the monitors belongs to which touch input device. Often these two devices come from two different vendors, so mutter needs to use ... */me holds torch under face* .... HEURISTICS! :scary face:

Those heuristics are actually quite simple: same vendor/product ID? same dimensions? is one of the monitors a built-in one? [1] But unfortunately in some cases those heuristics don't produce the correct result. In particular external touchscreens seem to be getting more common again and plugging those into a (non-touch) laptop means you usually get that external screen mapped to the internal display.

Luckily mutter does have a configuration to it though it is not exposed in the GNOME Settings (yet). But you, my $age $jedirank, can access this via a commandline interface to at least work around the immediate issue. But first: we need to know the monitor details and you need to know about gsettings relocatable schemas.

Finding the right monitor information is relatively trivial: look at $HOME/.config/monitors.xml and get your monitor's vendor, product and serial from there. e.g. in my case this is:

  <monitors version="2">
   <configuration>
    <logicalmonitor>
      <x>0</x>
      <y>0</y>
      <scale>1</scale>
      <monitor>
        <monitorspec>
          <connector>DP-2</connector>
          <vendor>DEL</vendor>              <--- this one
          <product>DELL S2722QC</product>   <--- this one
          <serial>59PKLD3</serial>          <--- and this one
        </monitorspec>
        <mode>
          <width>3840</width>
          <height>2160</height>
          <rate>59.997</rate>
        </mode>
      </monitor>
    </logicalmonitor>
    <logicalmonitor>
      <x>928</x>
      <y>2160</y>
      <scale>1</scale>
      <primary>yes</primary>
      <monitor>
        <monitorspec>
          <connector>eDP-1</connector>
          <vendor>IVO</vendor>
          <product>0x057d</product>
          <serial>0x00000000</serial>
        </monitorspec>
        <mode>
          <width>1920</width>
          <height>1080</height>
          <rate>60.010</rate>
        </mode>
      </monitor>
    </logicalmonitor>
  </configuration>
</monitors>
  

Well, so we know the monitor details we want. Note there are two monitors listed here, in this case I want to map the touchscreen to the external Dell monitor. Let's move on to gsettings.

gsettings is of course the configuration storage wrapper GNOME uses (and the CLI tool with the same name). GSettings follow a specific schema, i.e. a description of a schema name and possible keys and values for each key. You can list all those, set them, look up the available values, etc.:

    $ gsettings list-recursively
    ... lots of output ...
    $ gsettings set org.gnome.desktop.peripherals.touchpad click-method 'areas'
    $ gsettings range org.gnome.desktop.peripherals.touchpad click-method
    enum
    'default'
    'none'
    'areas'
    'fingers'
  

Now, schemas work fine as-is as long as there is only one instance. Where the same schema is used for different devices (like touchscreens) we use a so-called "relocatable schema" and that requires also specifying a path - and this is where it gets tricky. I'm not aware of any functionality to get the specific path for a relocatable schema so often it's down to reading the source. In the case of touchscreens, the path includes the USB vendor and product ID (in lowercase), e.g. in my case the path is:

  /org/gnome/desktop/peripherals/touchscreens/04f3:2d4a/

In your case you can get the touchscreen details from lsusb, libinput record, /proc/bus/input/devices, etc. Once you have it, gsettings takes a schema:path argument like this:

  $ gsettings list-recursively org.gnome.desktop.peripherals.touchscreen:/org/gnome/desktop/peripherals/touchscreens/04f3:2d4a/
  org.gnome.desktop.peripherals.touchscreen output ['', '', '']

Looks like the touchscreen is bound to no monitor. Let's bind it with the data from above:

 
   $ gsettings set org.gnome.desktop.peripherals.touchscreen:/org/gnome/desktop/peripherals/touchscreens/04f3:2d4a/ output "['DEL', 'DELL S2722QC', '59PKLD3']"

Note the quotes so your shell doesn't misinterpret things.

And that's it. Now I have my internal touchscreen mapped to my external monitor which makes no sense at all but shows that you can map a touchscreen to any screen if you want to.

[1] Probably the one that most commonly takes effect since it's the vast vast majority of devices