One recurring task when working with data structures is finding out if a given number (say an index into a sorting tree) is a power of 2.
A number is a power of two, if exactly one bit is set, so it all boils down to testing for that.
There are several way to do this. The most naive and inefficient way is to test for all the powers of two representable in a given amount of bits.
int ispow2(int x)
{
int bc = 0;
for(int i = 0; i<sizeof(x)*CHAR_BITS; i++) {
if( 1<<i & x )
bc++;
if(bc > 1)
return 0;
}
return bc == 1;
}
This function is suboptimal, since it's O(n)
A better way, circulating the net for years is this little gem of bit trickery, which executes O(1)
int ispow2(int x)
{
return !( (~(~0U>>1)|x) & (x-1) );
}
Unfortunately it only works for a specific type (you can of course adjust the most significant bit constant. But say you'd want to use this in a type agnostic macro. What I've seen in circulation is this (using the typeof Compiler extension -- which is not part of the C core language specification):
#define ISPOW2(x) ( ! ( (~(~((typeof (x))0) >> 1) | (x)) & ((x) - 1) ) )
Slightliy better is this:
#define ISPOW2(x) ( ! ( (1<<(sizeof(x)*CHAR_BIT-1) | (x)) & ((x) - 1) ) )
But those attempts look in the wrong direction: That most significant bit is only set to account for the case if x is 0.
In a project I wrote about 1 year ago I (re?-)invented the following method which works with any integral type:
#define ISPOW2(x) ( (x) && !( (x) & ((x) - 1) ) )
So far I've never seen it in circulation in the Internet. Maybe I am the first
guy to write it that way, but I don't think so. (if I am: cool!)Nope. Some guys pointed to me
to several bit twiddling hacks documents, where this is written that way. But you know what?
I don't care, I came up with it myself, instead of just reading it somewhere. Of course
credit where is credit due. I'm still interested who did invent that thing first.
If you didn't know already, I'm telling it here again: I'm not very keen of Wayland and the mentality it was created in. If you had to summarize it in one sentence it is this:
"Graphic clients take full control of the rendering process, the graphics system shall be only a thin layer that passes control of the output device over to the clients."
In Wayland terms, Wayland manages shared memory (framebuffers) and defines a protocol to pass those regions of graphics memory to clients which then use their method of choice to draw on it. Sounds good, right?
WRONG!
High quality graphics rendering is a notoriously difficult subject. To make matters worse many parameters directly depend on the output device. Just to name a few:
The high quality printer business knows this for years. All the better printers expect their input data as either PostScript or PDF. Why? Because those are not readily rendered raster images (which is what a printer actually puts on the medium), but abstract descriptions of the final result. Similarly the original TeX did output a format called DVI (DeVice Independent). Then a raster image processor (RIP) turns it into a raster image, carefully tailored to the characteristics of the device. There are businesses specialized in the development of device specific RIPs.
So lets say we get all those issues solved in the Wayland infrastructure. Then you're still stuck with the Wayland compositor being responsible for window management and input event retrieval/disposal. You've read right folks: The Wayland compositor is responsible for reading events from /dev/input/* processing them (a nasty business BTW, because many input devices out there are really fucked up), and handing it out to the clients.
Then it defines the whole window management behavior. Yes! With Wayland you can't simply switch your window manager, leaving the rest of the system untouched. You want another window manager, you need to implement a full Wayland compositor. Taking care of all the scrunities involved. Even worse, if the Linux developers decided on creating a new input device interface, say to address some upcoming issues, all Wayland compositors need to be updated. There's a nice German term for this: "Arbeitsbeschaffungsmaßnahme".
And after all of this it's responsible for compositing the windows to the screen(s), which means all the "eye candy" (I call it distractions) apply.
Wayland severely violates one of the core principles of X11: The separation of method and policy. A Wayland compositor mixes method and policy.
I tell you where this will end: In a plugin/module system. A core/mainline Wayland server (managing buffers of square pixel framebuffer memory regions), to which modules are attached that deal with input processing, window management and composition-effects. For stability reasons those will run in separate processes communicating with Wayland through some IPC mechanism (and if Murphy applies this will probably be D-Bus). Then, to tackle all those problems with device dependent rendering, an abstract rendering protocol/library will be introduced. Congratulations! You've just reinvented X11! The whole complexity of X11 is not some anachronistic burden, it's a necessity. I fully understand the X11 as we have it now, doesn't implement all the things we'd require for true device independence as I outlined above, mostly because X11 itself is pixel based.
On the Wayland homepage you can find this picture:
X architecture according to Wayland developers.
However this picture is terribly simplified.
First it should be said that the Compositor, just like the Window Manager (they don't need to be the same!) are just regular X Clients themself. Designating the Compositor as something "special" is just wrong.
Second it completely omits the fact, that the X server is not monolithic and does not accesses all the different kernel interfaces from the same core code. There are in fact several modules, often in multiple instances, each responsible for one specific interface or device.
This is a much more accurate picture of what the X architecture looks like:
A more accurate picture of the X architecture.
If you want to replace X11 with something better (not worse), be my guest, you're preaching to the choir.
My dream graphics system was completely abstract. Creating a window didn't involve selecting visual formats, framebuffer configurations. It was just "a window". Only when actual content is involved I want to tell the rendering subsystem, which color space I use. Ideally all applications worked in a contact color space (e.g. CIE XYZ or Lab), but sending images in some arbitrary color space, together with color profile information. Fonts/Glyphs would be rendered by some layer close to the hardware, to carefully adjust the rasterizing to the output devices properties. And last but not least the whole system should be distributed. Being able to "push" some window from one machine's display, to another machine's (and this action triggering a process migration) would be pinnacle. Imagine you begin writing an email on your smartphone, but you realize you'd prefer using a "usable" keyboard. Instead of saving a draft, closing the mail editor on the phone, transferring the draft to the PC, opening it, editing it there. Imaging you'd simply hold your smartphone besides your PC's monitor a NFC (near field communication) system in phone and monitor detects the relative position, and flick the email editor over to the PC allowing you to continue your edit there. Now imagine that this happens absolutely transparent to the programs involved, that this is something managed by the operating system.
This is where I want to go. Not that cheap effects lollipop desktops Ubuntu/Canonical, Intel, RedHat/Fedora and Gnome(3) aim for.
Vor ein paar Tagen hat eine in einem ICE deponierte CD hektische Betriebsamkeit ausgelöst. "Gut," mag sich da so mancher denken, "es ist nichts passiert, aber was wäre gewesen wenn?"
Leider übersehen unsere Entscheider und die, die noch mehr Überwachung fordern ein kleines Detail: All ihre Maßnahmen bewirken keinen Schutz, im Gegenteil, es sind sogar sehr effektive Angriffsverstärker: Durch ein paar geschickt platzierte, vorgebliche "Pläne" für einen "Angriff" könnte man so sehr effektiv wichtige Wirtschaftszentren für mehrere Stunden, wenn nicht Tage lahmlegen. Man müsste die Pläne nur echt aussehen lassen.
Das ist so ein wenig wie Return Based Programming: Anstatt den vollständigen Shell-Code selbst mitzubringen, bringt man das System dazu, sich selbst mit seinem eigenen Inventar lahmzulegen.
Am Frühstückstisch wurde gerade eine tolle Verschwörungstheorie ausgesponnen: Mal angenommen die USA und Pakistan wussten, in gegenseitigem Einverständnis, wo sich Osama Bin Laden versteckt hielt. Weder die USA noch Pakistan hatten ein richtiges Interesse daran Osama Bin Laden zu fassen, töten oder sonstwie festzusetzen. Die USA nicht, weil die "Suche" nach Bin Laden auf politisch vertretbarem Weg gigantische Geldsummen für den Militäreinsatz in Afghanistan legitimierte. Pakistan nicht, weil die sich genau den peinlichen Fragen, denen sie sich ja jetzt stellen müssen, ausgesetzt sahen.
Also lässt man Osama Bin Laden als "Das Arschloch im Wandschrank" in vollem Wissen (in einem angeblichen Safehouse des ISI) leben und hin und wieder mal eine Video- oder Audiobotschaft verbreiten.
Jetzt kommt die Verschwörungstheorie: Am 1. Mai ist Osama Bin Laden gestorben. Nein, nicht durch Kopfschuss, oder irgend eine andere Gewalteinwirkung. Ganz natürlich, an irgendeiner Krankheit oder einem Herzinfarkt oder sowas in der Art krepiert. Natürlich kann man das so nicht stehen lassen, die Schmach für die USA den Staatsfeind Nr. 1 nie gefasst zu haben. Pakistan hätte es sicher auch nicht gefallen, wenn da auf einmal ein natürlich zu Tode gekommener Bin Laden durch die Straßen von Abbottabad getragen worden wäre.
Also zieht man schnell eine Aktion durch, in deren Rahmen man der Leiche noch schnell einen Kopfschuss verpasst. Und damit nicht bei einer Autopsie festgestellt wird, das Todeszeitpunkt und Zustand der Organe und Grund des Todes irgendwie nicht zu dem Einschussloch im Kopf passen, wird in aller Schnelle der Leichnam auf See bestattet.
