Project Athena - X Window System Users and Developers Conference, Day 2 [5/6]

NEWMAN: I'm Todd Newman. I'm also from Digital. I also worked on the server. I have a prepared talk. So I'm going to be trading off eye contact for knowing what I'm saying. I hope that's acceptable. I'm going to be describing the color maps and visuals. And so what I'm going to do is a 20 minute talk on Bob's fifth slide. I'm going to be talking about the new color map types, explaining how visuals describe color maps, how different windows can use different color maps, and how different windows can achieve the effects of using different color maps while really using the same color map.

And now my first slide. It's right side up. It's sort of mostly visible. OK. X10 only supported two models of screen color, monochrome, with the white pixel and black pixel, and what we now call pseudo color, where each pixel indexes into a common table, which has a triple of color components to send to the red, green, and blue guns. X10 also only supported one color map. This is pseudo color here.

X11 has added one new black and white color type, called Grayscale, and three new color map types, called static, direct and true color. Grayscale produces different intensities of black and white. It's actually sort of pseudo color with red, green, and blue being set to the same thing, unless you get different levels of gray.

Static color is a server-allocated read-only version of pseudo color. In direct color, the pixel is decomposed into three sets of bit fields, which are used to index into three color maps. So here I've got a pixel. I'm taking the top sum bits and indexing into a red color map, and the next sum indexing into green, and so on. And there's true color, which is direct color, but it's fixed.

These new color map types are intended to better represent the different types of hardware on which X might be run. In specific, there is hardware that works as direct color is described here, where the hardware splits the pixel into three fixed fields and indexes into three color maps. X10 didn't support this very well. X11 also realizes that some hardware supports multiple depths, and multiple color map types per depth.

And now we get the next slide. So an arbitrary screen might support monochrome, 8-bit deep pseudo color, 12-bit deep pseudo color, and 12-bit deep direct color. When we say depth here, we mean bits per pixel. We're not talking about screen window layers or anything. Of course, the display has some real underlying depth, how many bits are really being sent to it. But if it's being simulated in hardware, you might as well say that it supports these multiple depths.

At connection time, the server passes the client a list of depths it supports, and the visual types allowed at each depth. And that's really what this is. Visuals indicate the color map type, where to find the red, green, and blue bits in a direct or true color pixel, how many different intensities of red, green, and blue can be generated, which is what bits per RGB means, and how many entries there are on a color map. It also tells the client about the default color map. The default color map is allocated when the server starts up and it's in whatever sort of the natural type is for that screen. So it might be an 8-bit pseudo color map, or whatever.

A couple of things to notice. One is that the color map size is independent of the number of bits per RGB. It's quite common to have a 256 entry color map that's sending 8 bits to red, 8 to green, and 8 to blue, which is 16 million colors. And you really wouldn't want a 16 million entry color map. You could also do it the other way and have a larger color map the number of colors you can generate. But I couldn't find a use for it.

Note also that the depth and color map size are independent. This surprised me at first. It seemed that if we had n bits per RGB, that the color map should have 2 to the n entries, or 3 times 2 to the n for direct color. But when we're implementing color maps on decks GPX, I found that the top two entries of the hardware color map had been stolen for the cursor. And so if we created 256 entry color maps, when we put in, if we allowed the client to write into those top two entries, he'd steal the cursor's color and he could lose his cursor. It would just go random colors and he'd lose it.

As I implied earlier, X11 does allow clients to allocate their own color maps. They don't have to use the default. They can choose from any of the supported depths and visual types for the screen. They can fill in the color map as they like and know that all the pixels they want will be available. If they call Install Color Map at the appropriate times, they can make sure that their color maps are always installed and that they'll always get the right colors.

Of course, other clients could come in and force this color map to be uninstalled when theirs is installed. If this happens, the client's window gets displayed with whatever colors are in the current color map. And we refer to this as going Technicolor. It would be nice if clients which didn't need too many colors could gracefully co-exist in the default color map. It would also be nice if developers could write applications that ran on both pseudo color and direct color without having to worry about what the hardware really looked like. So you could just write one interface to your color map.

Alloc color planes and alloc color cells let an application treat a set of pixels as if they were pixels on a direct or pseudo color map without worrying about the underlying hardware, and without colliding with other application's pixel needs. Clients use these things when they do pixel allocations, there's a very good chance that they can coexist peacefully. Before explaining full details of how these work, I'd like to discuss how people use color and how they decide what kind of pixel values they want.

To be overly simplistic, people use color either representational or non-representationally. Image processing programs are representational. If I were to draw an apple, I'd pick a certain shade of red because that's the color the apple is. Applications in this category of image processing like to play games like taking the arithmetic average of two pixels in order to get a color halfway in between them. Such applications work best on true or direct color systems where the color map's been loaded with monotonically increasing values so that pixels with similar values turn out to be similar colors.

And I have a slide here. I'm going to get real fancy now. Does this work at all? Yes. So let's consider an 8-bit deep device that the hardware has partitioned the pixels so that the high 3 bits go to red and then get looked up in the red table, the next 3 bits go to green and get looked up in the green table, and the next 2 go to blue and get looked up in the blue table. The clients load the tables as I've done-- and you probably can't read it all-- with ascending values. Then they can play a lot of games a lot more easily.

You can do depth cueing by just sort of reducing the pixel value in each field. You can do color blending, and things like that, as mathematical functions. Now comes the clever part. If you take this 8 plane-- let me start again. The clever part-- doesn't it sound nice that way? Since X11 uses 32-bit pixels, we could use part of the pixel, say 8 bits for color planes, and the other part, the remaining 24 bits, the remaining 24 bits we can pick to suit our convenience.

On a pseudo color device, we can pick any n bits of the pixel-- we could take these or these or whatever we want-- to play, be color planes with, and use the rest to shuffle around. And this way we could get multiple people allocating 8 color plane bits and still all fitting their pixels into the same color map. If the hardware actually does divide the pixel into color bit fields, then we have to put the color planes on top of where the hardware expects to see them.

So here I've done a 3/3/2, that is, 3 red, 3 green, 3 blue on a 24-bit direct color system. And so I put my 3 red bits where the hardware, somewhere over the hardware's red bits, and my green bits somewhere over the hardware's green bits. But we still have a little room to play around. All these other bits aren't allocated. And I can use them.

There's still one nasty allocation problem to be considered. If we're allocating one pixel, R red planes, G green planes, and B blue planes, then we're allocating 1 times 2 to the R plus G plus B pixels. But we only want 2 to the R independent red ones plus 2 to the G independent green ones plus 2 to the B independent blue ones. Now 2 to the R plus G plus B is, of course, 2 to the R times 2 to G times 2 to the B, which is a larger number than the sum of these things. So where did the extra pixels come from?

The key thing is that I said independent pixels. Let's think about just the red pixels for a moment. For each of those R red pixel values, there are 2 to the G plus B pixels that have that same value. And if we change any of them, any of those R pixels, all 2 to the G plus B pixels have to have their color changed to have worked properly. On a real direct color device, this just falls out. You change the R thing, it changes the R map, and every pixel changes colors. On a pseudo color device where there's only one color map, we have to find a way to change the red component of all those pixels. This is what's technically referred to as a bookkeeping nightmare.

Now to return to the non-representational color users, these are applications like business graphics and CAD/CAM. A pie slice that's red, you know, it's red because we liked red. Electrical traces on a printed circuit board are red so that we can tell what layer they're on. Applications like this like to play games like ORing things into pixel values and changing 1 bit in the pixel to produce a radically different color. Non-representational graphics work best on static and pseudo color devices where the color of each pixel is independent.

Let's consider a hypothetical CAD system where there are transistors and resistors and other devices connected by traces onto a printed circuit board. The traces are color coded by layers, and let's say there are three layers. Where traces interconnect between layers, we want a special color. We also want to be able to highlight a selected trace, when we select it, by changing its pixel value, and then unhighlight it just by restoring those pixel values. Simply XORing the pixel could produce a pixel that we haven't allocated.

And someone just before the meeting told me about someone telling him that X was broken because he was trying to XOR unallocated pixels. So instead of doing XORing, what we're going to do is just be able to OR in a mask to change the color, and then OR that, or AND that mask back out to make it go away. So what we want is three layer pixels, one independent fit pixel, one intersection bit, and one highlight bit, which is only 12 pixels total.

And we move on to my next slide. Don't want to come. Isn't static electricity wonderful? So what we've got here is an intersection plane, a highlight plane, and then three layer pixels. Again, we take advantage of the large pixels and be able to allocate the bits for the planes wherever they fit. I've only drawn in eight of them, but you can extrapolate. Alloc color cells require that when a pixel value changes, it can be any color the user wants. This means that it must be able to set its own red, green, and blue components. So on a direct color device, each requested plane must have a bit that falls into each of the red, green, and blue hardware bit fields.

Once again, this is just a bookkeeping problem. If clients use alloc color planes and alloc color cells, they can simulate n-bit direct and pseudo color devices without requiring their own hardware-- excuse me-- without requiring their own color maps. One client could be using alloc color planes to allocate, as I gave in my example 3/3/2, in 256 entries. And another could be using alloc color cells to get 12 pixels. And both could run in a 512 entry default color map, with a little bit of room to spare.

Well, so far, I haven't shown you any data structures. That's going to change. This is the data structure that I concocted for-- pardon? No, it isn't. Yes. Yes, it is. Does it not show up? I didn't want to show it to you in C because people would complain a lot. Wait. No, it isn't. Enlightenment. Also, confusion on my part. I apologize.

So basically, the color map, I decided to use just one color map for both direct and pseudo color. And I waste a couple entries, but it makes the code much simpler and easy to read. You just ignore things. So a pseudo color device is a direct color device that only uses the red entry. I just picked red arbitrarily. So the color map has hooks to other structures. It has three pixels for each color. And I keep track of that just so that I might be able to easily reject a request.

And then we have color cell tables. I've done the red one in detail, and the green and blue are like it. A red entry has a reference count, a shared flag, and either a local color or a shared color. Here we go. Colors, right. Colors allocated by alloc color and alloc name color, which are two X11 requests, can be used by multiple clients. This is because they basically said, I want red. Anybody who wants red can use the same red. Each client that uses such an entry increments this ref count.

When a client relinquishes the pixel, the ref count is decremented. And when the pixel is freed, you know, the pixel can be freed when the ref count goes to zero. If the client is going to be doing things like alloc color planes and alloc color cells, which is a little trickier, this ref count gets set to 0-- to minus 1, which basically makes it private to that client. No one else can get that pixel. The entries can be freed when the client's done with them.

OK. Now when I talked about allocating the related colors, what I do is, related colors I use the shared color value. I set the shared bit to true. And then I point off to a shared color. So all the related, all the alloc color cell's pixels that shared this red value-- I'm sorry-- alloc color plane's pixels that shared the red value would point off to this red cell. And then I change the red cell. And then I go racing through the table finding everyone who pointed to this red cell and doing a store colors on them so that the hardware was updated appropriately.

This is a lot of bookkeeping. The good news is that if you're implementing the X11 server, you don't have to do this part. All you have to do is write store colors, resolve colors, install and uninstall color map. This part's done for you. Install and uninstall you have to write because the DIX layer can't tell how many color maps your hardware supports. There's some hardware out there that can have four installed color maps at a time. And so it has to take care of figuring out when to throw something out and when to replace it. But in general, this is all done for you.

Are there questions?

AUDIENCE: I know you want to be friendly to lots of hardware, but why is it that [INAUDIBLE] in so many layers [INAUDIBLE]?

NEWMAN: The question is, why do Baroque pieces of hardware cause such complexity in so many layers? I guess the answer is because they're Baroque.

AUDIENCE: Why don't you just say no?

NEWMAN: Because-- he asked why don't we just say no to them. The answer is that when the hardware does a lot of this stuff for itself, it runs faster. It does more complex things. People consider this hardware a win. That's why they spent so much money building it. It's nice of us to support it.

AUDIENCE: There are certain applications that can't do in a very simplistic imaging log. We've made things simple. If you're just saying, I want red, you get red. That's all shared and simplistic. But if you want to the more sophisticated things, the books are here.

NEWMAN: Yeah. I described a full blown system and some of the most difficult things you could want to do. Doing easier things is proportionally easier and runs proportionally faster. Question over there?

AUDIENCE: Seems like there's the potential for a tremendous amount of memory utilization [INAUDIBLE]. Some of us are crazy enough to try and implement XR non-virtual memory. Is there any hope at all for us? Can the server choose not to implement quite such a fancy color scheme [INAUDIBLE]?

NEWMAN: Yeah. Bob, do you want--

AUDIENCE: Are you worried about code size or data size?

AUDIENCE: Yes.

AUDIENCE: Data size, almost any resource allocation can fail. It can say, sorry, I can't allocate any more of those. So you can certainly give up at some point.

AUDIENCE: Does the server [INAUDIBLE]?

AUDIENCE: Yes. You can say upfront, I refuse, if you have more than 25 logical color maps, I give up. Or more of any given depth, or whatever. In terms of the data size, you could always take pieces of this out. We're giving you code. You can always choose not to use it, right? If all you say is, I only have pseudo color and I don't want all this other [INAUDIBLE], if you can figure out a faster way to implement it, a simpler way to implement it, then feel free. We're trying to give you a general piece of code since most things aren't that VM-limited in terms of code size. There's only, typically, one copy of your server running on a workstation. And that's not a problem.

NEWMAN: It's always easier to throw away code once someone's written it. Any other questions?

AUDIENCE: [INAUDIBLE]

NEWMAN: He's describing a system sort of like the one I put up where there's a monochrome plane, there's a monochrome way of viewing the world and there's a-- I don't know how many bits deep it is-- color view of it. And you can create a window that's monochrome and you can create a color window. And you talk to one one way and one the other.

AUDIENCE: [INAUDIBLE] the server would say, oh, I could [INAUDIBLE].

NEWMAN: Yes. Bob?

AUDIENCE: I'm not very familiar with the sign, but you only get one or the other, right? You don't get them both simultaneously. Is that right?

AUDIENCE: What do you mean by simultaneously? [INAUDIBLE]?

AUDIENCE: No. On one physical console. If you get them both at the same time, then you could use the window allocation strategy, and say monochrome [INAUDIBLE].

NEWMAN: Right. That's a great example of exactly why we did this. Boy, you fed us nicely. Anything else? We've got a ringer here.

AUDIENCE: I think there are two kinds of sharing, and I just want to know which one you're talking about.

NEWMAN: OK. There are, in fact, two kinds of sharing. And maybe my talk didn't make that clear. One kind of sharing is where I say, I've asked for blue green. And anybody who wants blue green can get this blue green because I'm not going to change it. So when I do an alloc color or an alloc named color, it hopefully comes out of-- it would come out of the default color map, which everybody knows how to get to. And I've guaranteed that, I've asked for blue green, but I'm not going to change it. So anybody, everybody can share that. That's one kind of sharing.

The other kind of sharing is the one that gets involved when you do alloc color planes on a direct color-- excuse me-- alloc color planes on a pseudo color map, and you need to be able to share a color value between all the pixels that have the same bits set for that color field. That's why there are two reference counts. There's one reference count in the color map entry, and there's another one in the shared cell. There are, in fact, two kinds of sharing. And if you read the spec, it may become clearer than my talk made it. Bob? OK.

BRANDT: I'm Sue Andrew Brandt from Digital, also. And I'm another one of the implementers of the X11 that you're going to get on the Alpha tape. Over the last five months, there's been five of us who've been implementing and designing a version of the X11 server. And what Raymond Drury and I are going to explain is how we structure the server, and then describe its main components.

We designed the server with four goals in mind, portability to multiple operating systems and not just wedded to 4.2 Unix, adaptability to multiple types of hardware, from low-end monochrome frame buffers to high-end systems with sophisticated hardware support for state and windowing, modularity so that you can take out some of the software we've written and instead use your hardware to actually do the graphics, and portability without much loss of efficiency. We'd like it to run well on monochrome frame buffers and on that sophisticated hardware.

In the v.10 implementation, the code is sort of divided into two rigid parts, a device-independent part called diX, and a device-dependent part called ddX. And we've changed that. We still have a diX part, but the ddX layer has been divided into sort of a jigsaw puzzle. And we give you the opportunity to replace pieces or sets of pieces of the jigsaw puzzle with the functions that your hardware provides.

And the ddX layer sort of has these components in them, output, color maps, state-- GC is Graphics Context-- state manipulation, which you might have in your hardware. And you might even have window management stuff in your hardware, too. So you just replace the pieces that you want in there. And I'll show you a little bit about how you do that. The diX layer's job is similar to what was in v.10. It dispatches requests and it manages the common data structures.

You'll notice that the operating system is a real low class citizen. It's over there on the side. We've really tried to define a strict interface to it so that it can be ported to other operating systems. And its basic job is connection management, connection to clients, and it does scheduling between the client connections. And it's the same kind of scheduling as in v.10, just as round robin, same kind of thing.

To obtain our goals, we've made heavy use of the statefulness in the v.10 protocol. And each of our major data structures contains a set of procedures that can be tailored to the current state of that data structure. The GC is a really good example of that. And it's divided into basically three parts, a device-independent portion, and then two pieces that belong to the device. The first piece is a set of procedures that implement the output calls. And since this is a common data structure and can be seen by both the independent and the dependent portions of the code, we provided another hook here, this pointer, which allows the device to store anything it wants there and nobody else can know about it.

So for instance, it might store something about the state of the hardware or something like that. And the way this works is, these procedures down here reflect these characteristics that are in the graphics context at this time. So instead of your polyline call having to check all those things every time and having all these branches, you can set the polyline call depending on the line width and the fill style. So if I have hardware that draws single lines really well, then I stick in a polyline call that does that when the line width is 1.

If the line width is greater than 1 and I have to do my polyline calls in software, then I stick in my procedure that does polyline calls in software. And the reason we've done this is it makes the draw path through the server really fast. Because when the dispatcher gets a line call and the GC, it says, well, the GC is all OK. So I'll just indirect into the polyline call and call that and draw my line. I don't have to do any checking. So we really think that that's going to be a big performance win.

The window structure is similar to this. It has two pieces also. And windows each actually have state, too, such as the border tile. And we can cache around a little information so it's faster to draw the backgrounds and the borders. We've also provided several mechanisms for the windows to take advantage of hardware that does have window manipulation things, such as keeping the windows down in the hardware or doing the clipping calculations down there.

To facilitate ports to new machines, we've provided a machine-independent version of almost everything. And by machine-independent, what I mean is for the graphics calls, for instance, your graphics textbook that you saw in college had examples of routines that were based on one thing, put bits in framebuffer, or get bits from framebuffer. And so we've provided algorithms that just require you to write two routines, get bits from framebuffer and put bits in framebuffer.

Now you might say that's not going to be very fast. But it's going to let you bootstrap your server up really quickly. Because you write those two routines, you get it up, and then you can slowly replace the pieces of our jigsaw puzzle with your hardware-specific stuff. Now what kind of things are you going to have to replace? And I have a list of those here.

Basically, it depends on how good your hardware is. And this is sort of a list, and dumb hardware here, smarter hardware up here at the top. So as your hardware gets better and better and better, you just keep marching up here replacing things. We expect people with monochrome framebuffers just to do a few of these things down here. And then as they get more sophisticated, they'll just start walking up here. I don't expect anybody to replace the dispatcher. It's always going to be up there grabbing things off the network as part of the user code, rather than down in hardware.

So Raymond is going to talk about the port that we've done of all of our stuff to a monochrome framebuffer, and then talk about some porting strategies.

DRURY: All right. My name's Raymond Drury. I'm the last person you'll hear from working on the X11 server, I think. And I'm going to tell you most of the same things that Sue did, except I'm going to go at it more from the bottom up instead of the top down, and try to tell you how we think you should, how our design wants to be ported to various kinds of hardware.

And since all of the boxes you saw in Sue's picture previously can conceivably be replaced, I thought I would take one as a specific example and we'll talk about how you can run an X11 server on hardware with graphics output support that we didn't envision. But you have to remember all through this that you could do the same thing, for example, to the code that manages the window tree or the code that deals with the color maps or the code that does clipping calculations.

So when you look at your alpha test tape or your beta test tape and want to get X running on your favorite piece of hardware, you'll see that there are five-- the GC has this procedure vector in it. And there are five things you have to replace. There are these three here, the Fill Spans, Set Spans, and Get Spans. What Fill Spans does is it looks at the state in the GC, it takes a list of scan lines, and fills each of those scan lines according to the current fill rule. That is, it uses the current color if the fill style is filled with solid color, the current tile if the fill style is filled with the tile, the current stipple if the current style is stipple fill.

Set Spans is like Fill Spans, but a little different. It takes a list of scan lines and list of full pixel values to put in it. That would be used, for example, in a copy area routine who have used Get Spans to read an entire scanline so we have full pixel values, not just some algorithmic pattern to put in. These two over here, Validate GC and Create GC, are used to deal with the state and the procedure vectors for the output calls.

We call Create GC when a client says, create me a GC for this screen at this step. At that point, the hardware should fill in the procedure vector in the GC with procedures that match the default state of the GC. And furthermore, each GC, like all our other internal structures, has a field in it called Device Private. And the hardware is free to put anything in there it wants. We assume, generally, that it will put a pointer in there. And the pointer will point off to hardware context associated with this graphics context, for example.

Validate GC is not something you see in the protocol. We use that internally. When the dispatcher gets a graphics request, it looks at the GC and notices if it's been changed since the last output request to that GC. If it has, it calls GC with the drawable this output request is going to, and the GC and the mask telling it which bits have changed. The Validate GC code then ought to go through and modify any hardware state that it needs to to deal with the new state blocks. It could replace procedures in the procedure vector, and that sort of thing. So Validate GC is really where the hardware gets to come in and say, I know what this drawing request is. I know how I want to do it.

Now if you have those five-- Sue said two, but the number seems to get unfortunately larger every time I look, but I think it's going to stay at five, but for now, if you implement those five routines, your server will run slowly. But it will run. This is important. I've always thought it's really neat to see your X server come up for the first time.

And sort of in order of precedence, there are other routines that you will probably want to replace. Copy Area, because you use that to scroll in xterm, and everybody wants xterm to go fast. Text Out, it out because everybody uses text, even if they're a graphics application, they'll have menus, and so on. Furthermore, there's a lot of hardware that has text support in it.

Polyline is in there because if you are interested mostly in software, there's a lot of software that uses polylines for dragging outlines of things around in paint packages or drawing window borders for window managers. And if you build hardware, you've probably put hardware line code in your-- you've probably put line support in your hardware and you want to show it off in your X server. And Fill Rectangle we use to clear window backgrounds, and so on.

Now one thing to notice is that Fill Rectangle isn't really how we clear out window backgrounds. The window also has a procedure vector in it, which you can replace at a later date. And this way, we can take advantage of the fact that we know well in advance what kind of background your window has. We know you have a solid background or a tiled background, so you can put in the appropriate code. Since we fill window backgrounds fairly often, you probably want to avoid all the extraneous tests and so forth to see what you're filling with.

Now we've provided some useful tools to help you out with this. There's the machine-independent output code that Sue talked about. And it's a set of code that implements all of the X11 graphics output primitives and clips them to bunches of rectangles, and so on. And you can replace those or modify them or whatever. They will, they are guaranteed to turn on the bits that the protocol says you should turn on in the framebuffer.

We provide another set of routines that do rectangle arithmetic. They'll do intersections of bunches of rectangles, subtract one rectangle from another, that sort of thing. And that's useful if you're doing clipping calculation. In X11, the client can specify a clip mask, unlike in X10, where you had to pass it in with the request or clipped to the window. And you can use these to composite together the window clip and the client clip, so you can sort of do all your clipping at once.

Now for dumb frame buffers, we provide a sample implementation. That is, we've written Copy Area and Text Output and Polyline and Fill Rectangle for 1-bit deep framebuffers where all the pixels are contiguous in a row, no interlace or anything silly like that. So this code is almost machine-independent, but it's not really because it assumes that pixels are 1 bit deep and that pixels come in memory, one right after the other.

Now this is a problem because on some displays, the bits number 0 to 31 then 0 to 31. And in other hardware, they go 31 to 0, 31 to 0. And some of them byte swap and do other things. So in the monochrome framebuffer routines, if you write a Get Bits and a Put Bits, that we tell you starting at bit, logical bit, and on the screen turn on the following some number of bits, if you write code that does that the correct way on your screen, at compile time you'll automatically get all of the monochrome framebuffer stuff working on your hardware. And we have some evidence that this scheme works.

All right. X11 has already been ported to several things, or partially ported. We run on the VAXstation II with the monochrome framebuffer. That's been our base development machine for the server. We run on the IBM PC-RT, which is another monochrome framebuffer. But it's interesting because the bits on the screen are numbered differently. And it's been shown that by rewriting Get Bits and Put Bits, you just recompile and it runs. We run on Digital's GPX, which is a color machine that has hardware support for some, but not all drawing operations. For example, it has hardware support for polygons. So you could hook out the polygon code in the GC to fill polygons on it.

We run on the VS 100, mostly for historical reasons. Yes. It's much harder to run X11 on the VS 100 than it was to run X10 on the VS 100. Anyway, the VS 100 is another monochrome device with some hardware drawing support. And the port to it was relatively painless. Of course, we couldn't use the monochrome framebuffer routines for it because you can't get at the bits. But we used the machine-independent stuff, and that works.

X has also been experimentally ported to an all singing, all-dancing 3D graphics engine with multiple color maps, hardware support for the window tree, hardware implementation of lots of the X11 primitives, and that sort of thing. And that port is interesting because it, in theory, exercises the multiple color map stuff, and also deals with whole sale replacement of all our procedure vectors. It replaces the window tree manipulation stuff with its hardware hooks, and so on.

It's often been complained that all of this is more complex than necessary. So I thought I'd give two examples of how this whole calling sequence might work. So for a monochrome framebuffer, we've been asked-- the dispatcher has been told to draw me a line. We notice that the GC is the same way it's always been. There are no state changes. So we just indirect, straight through the polyline field of the GC, which calls the monochrome framebuffer polyline routine. We draw the line.

All right. Now consider that the user or the client program changes the GC and says, I want line width of 5, and I want my fill style to be stippled. So the dispatcher, when it gets that request on this window, or even this drawable, remember that your output code has to be able to draw to main memory or to the screen. It notices that the GC has changed. So it calls the Validate routine we've provided. That Validate routine goes through and notices that we can no longer use our nice fast monochrome framebuffer line code.

So it swaps in another thing. It swaps in the machine-independent polyline code. It returns. The dispatcher, then, calls through the GC and ends up in the routine, miPolyline. Now miPolyline converts wide lines to polygons, and then it calls the Fill Polygon code. So it converts the lines to polygons, then it calls through the Fill Polygon vector.

Now if we were on the GPX, we would go straight to the hardware at this point. We don't, because our dumb frame buffer doesn't know about polygons. So we go to our machine-independent polygon filling code. It actually goes to the frame buffer and turns bits on. So it, for each some number of scan lines, it buffers up a set of scan lines, then calls the GC's Fill Spans field. The Fill Spans that we selected in Validate was fill scanlines with the current stipple pattern. The bits go out on the screen and you get your wide line.

This isn't as slow as it might appear. It turns out that for things like this, the computational overhead is much greater than actually having to go to the framebuffer and turn the bits on. So unless you have help actually calculating how to turn the bits on, which is what a graphics engine does for you, this is all right. So on the GPX, you would start using the hardware here. And on maybe some very smart device, you would actually get to the hardware at that point. So that's all I've had to say. I guess I can answer questions until we've run out of time. Yes?

AUDIENCE: Do you have any plans or any thoughts about porting the server to less expensive machines? And let me name three. One might be something like the Apple Macintosh, in which a lot of metric has already been invested in certain kinds of high-performance rendering code. One is something like the Atari, which is a very inexpensive machine with color capability. And one is 80x86 personal computers, of which there exists many, many instances, and a wide variety of graphics [INAUDIBLE].

DRURY: We, the implementers-- and I can't say anything for Project Athena, they'll have to answer for themselves-- we'll stop implementing when we finish, when we finished the alpha test code and give it to these people. There's nothing preventing you from porting it to any hardware you want. We think-- we haven't gone extremely low end. There are a couple things that we've kind of assumed that were already brought up a little bit in the color map stuff. We assume, for example, reasonable amounts of memory on--

AUDIENCE: [INAUDIBLE].

DRURY: Oh, I don't know. I don't see why we couldn't run on say, oh, a 640k machine. On the other hand, all the 640k machines I know have ridiculous segmented architectures that make a lot of this a lot harder. So. But go ahead and try. I think, I think you can do it. I really do.

AUDIENCE: Is absence of hardware [INAUDIBLE]?

DRURY: No. We use no floating point. Not true? It turns out we have to use fixed point for a couple things, but we reduce it to a minimum. Most algorithms can be done in integer, if you think about it long enough.

AUDIENCE: What size is it?

DRURY: 32 bits. 16 bits, well, since X11 coordinate system is 16 bits, it's probably OK to use a 16-bit machine. Yes?

AUDIENCE: I have a question about the kinds of, yes, [INAUDIBLE].

DRURY: That's about it. That's as far as we go. That's one, two, three, four, four layers deep. One way you can get around this is take our machine-independent code and replace the Calls Out with just hardwired go touch my framebuffer now. Yes?

AUDIENCE: How many stages do you go through when you're printing out text by clipping and stuff before you actually really start drawing things?

DRURY: The question is, what do we go through to clip text? And it turns out that text is pretty easy to clip. Because unless you're doing, say, kerning, which may give you funny shapes at the ends, the string defines a rectangle and you can do a lot of the clipping by taking the rectangle the text will hit and intersecting it with where you want to go. So you can almost clip on a per-string basis.

AUDIENCE: I guess I don't understand. Most text [INAUDIBLE].

DRURY: Right.

AUDIENCE: And does [INAUDIBLE]?

DRURY: Ah. Clipping. Everything in the GC except Set Spans, Fill Spans, and Get Spans clips. Right? With--

AUDIENCE: [INAUDIBLE].

AUDIENCE: Normally, you would have to touch each character. It's typically very easy to figure out that a character either is entirely inside, entirely outside, or on the border. So typically, you just flip a whole pile of characters and worry about the one which is on the edge. And then you're done. It takes [INAUDIBLE]. It's typically not a big issue.

AUDIENCE: How do you deal with a line that might be run through a bit more portion of an extended raster, and then so that you've got this virtual buffer behind it? Do you explain the top down, however? How do you look from the driver's level? In particular, when you cover up and then uncover it, what halls are done to save the information ways and transit between joint to computer memory and the screen memory?

DRURY: All right. I think what you're asking is, how do we do backing store. Is that what you're asking? There are hooks in the server. There are hooks in the server to allow you to implement backing store. And we provide a sample version of machine-independent backing store showing you how to use those.

AUDIENCE: Will you have experimented with it?

DRURY: Yes. We have played with it some. Yes?

AUDIENCE: Have you done anything to-- in terms of find the implement, the output-only portion for hard copy devices at all?

DRURY: No, we haven't. But I've thought about it. And I think it would work.

AUDIENCE: What do you see at the [INAUDIBLE]?

DRURY: I think you could probably do it if you pretended that your hard copy device was say, another screen. Remember the server supports multiple screens. And you just draw it a windows on that screen. I think that would be fine. Oh, yes. Logic functions that read the destination back will not work on your printer. Yes?

AUDIENCE: Network addresses.

BRANDT: Did we decide on one? Oh, do we have network-- you mean, can you write us mail? No, you have to go through [INAUDIBLE]. Project Athena. Jim gave all the information already.

AUDIENCE: [INAUDIBLE].

DRURY: Yes.

BRANDT: I might have a visual name? No.

AUDIENCE: [INAUDIBLE].

BRANDT: We provide a black box and you fill it in. And in our implementation, Alteryx's 4.2, we use Select. But there's no reason why you couldn't--

AUDIENCE: Version 10 on the black box

BRANDT: Oh, yeah. There's a black box. It's called, wait for something.

DRURY: Way up there?

AUDIENCE: Why do you validate [INAUDIBLE]?

DRURY: Well, remember, we only validate if we notice something's changed. Now, there's something I didn't tell you, which is that an optional thing you can put in is that we will call out to the hardware whenever the GC is changed, if the hardware wants that. Turns out that for a lot of hardware, there's hardware without a lot of hardware, hardware internal stuff, it's better to batch up all the changes and do them all at once. It's also easier to deal with clipping in case the window's moved.

AUDIENCE: [INAUDIBLE]. Specifically, if a graphics device has a rubber band box cursor type, which [INAUDIBLE] Can we use that type in version 11?

DRURY: That's Phil's question.

AUDIENCE: That's basically a protocol question. There's nothing in protocol that allows you to do that. Now, there's nothing from preventing you from implementing an extension which did that and telling that extension to do it. There's no way in there for a protocol to make that request.

AUDIENCE: We should stop here.