Path: jumbo!stolfi From: stolfi (Jorge Stolfi) Newsgroups: src.graphics Subject: Managing the color table Message-ID: <8712110448.AA10067@bigtop.dec.com> Date: 10 Dec 87 20:48:03 PST Sender: stolfi@jumbo.dec.com Distribution: src Lines: 292 Received: from bigtop.dec.com (bigtop.ARPA) by jumbo.dec.com (1.2/4.7.34) id AA06482; Thu, 10 Dec 87 20:48:22 pst Received: by bigtop.dec.com (1.2/4.7.34) id AA10067; Thu, 10 Dec 87 20:48:03 pst To: src.graphics Cc: stolfi Folks, Greg, Marc, Phil and I have been discussing the management of Fred's color table, and I thought this discussion should be made public. The problem ----------- First, a bit of nomenclature. The image displayed on the Firefly color screen is determined by an array of about 800x1000 eight-bit variables or _pixels_. The value stored in each pixel is thus an integer between 0 and 255, called a _color code_. The mapping from color codes to actual colors is specified by Fred's _color table_, an array of 256 variables which tells how much red, green, and blue to use for each color code. These amounts are encoded as a three integers from 0 to 255 (an _RGB triple_). The problem is that there is only one color table for the whole Firefly. Obviously we need some management scheme to share this scarce resource among all applications using the color screen. Five solutions -------------- In our discussion we came up with five plausible schemes, which I will call _Anarchy_, _Barbarism_, _Feudalism_, _Theocracy_, and _Communism_. Anarchy is not a form of government, but the absence of government. There simply are no rules: any application may change any entry of the color table at any time. Any conflicts are just bad luck. Barbarism (the schema we have now) is only a little more advanced. An application that needs a color has only to look for a flourishing but defenseless entry, take it over, and unambiguously mark it as "owned" so as to keep other applications away. What distinguishes Barbarism from more civilized ownership schemas is that the marking is permanent: entries are not automatically unmarked when their owners die or stop using the color screen. Essentially, every conquered entry is razed to ground and has (boolean) salt sown in (one of) its fields. That entry is forever lost to the world, unless the conqueror is sufficiently enlightened and long-lived to rebuild it for the sake of posterity, or until the time when the gods themselves (as personified in the User) get moved at the sight of its misery, and by direct divine intervention restore the color table to its former unassigned glory. (Woe betide any color application who is still alive when that time comes). Feudalism is similar to Barbarism, except that there is a King who keeps track of which applications own which entries, is promptly notified when an application dies, and takes care of redistributing its real estate to whomever He sees fit. As in the Barbaric regime, applications have absolute rights to the entries they own, and can set them to whatever they like as often as they wish. Obviously, this prevents sharing: at any moment each entry can have at most one owner. By contrast, in a Theocracy there is only ONE sacred color map, chosen by the gods and written down in stone for all mortal applications to see. Its contents is immutable, at least in principle: although in practice religious reforms do happen from time to time, faithful programmers should always the current church-sanctioned settings as the eternal truth. (This is not much of a problem as long as the color map changes no more often than, say, Thread.def or Text.def --- as the Italians used to say, only once every Pope's death.) In a Theocracy, a self-confident application can rely on its own reading of the sacred color table, and refer to color codes directly (as in CONST MyFavoriteColor = 125). More prudent applications will prefer to obtain their color codes from some blessed interface (Tint.WhiteColor) or through the offices of a religious authority such as Tint.RGBToColor, which wows to finds the color table entry most closely matching a given RGB triple. In a Communist regime the the color table is dynamic, but the central government retains ownership of all its entries, which it loans out to applications who need them. The government has the power to decide what goes into each entry, and which color codes each application can use. When an application needs a new color it has to call the proper government agency, specifying a desired KGB, I mean RGB triple and an error tolerance. If the current table contains a sufficiently good match, the government returns the corresponding color code. If there is no matching entry in use, the agency finds an unassigned one, sets it to the given RGB triple, and returns its code. Since table entries are supposed to be shared, their contents cannot be changed once they have been allocated. (Actually, as Phil noted, the government may be allowed to satisfy a new request by modifying a currently allocated entry, provided its new RGB value is still within the tolerances of all applications that are sharing it.) (One can imagine yet another regime, _Capitalism_, in which applications decide the ownership of color table entries by trading them in a free marketplace. In a first implementation trading may be limited to barter ("Would you like to swap these three VM pages for that color code?"), but soon it will be necessary to introduce some form of common concurrency. As trading algorithms become more and more sophisticated, things are sure to become quite interesting. We will certainly see some applications abandon their traditional jobs to pursue a commercial career, buying and selling color table entries for profit. Just after a reboot, speculative applications will buy dirty cheap lots of color table entries they don't need, and then sit on them for hours and hours, waiting for increased demand to drive their price up. Soon applications will start borrowing from memory banks, paying dividends and divisors, and having their stacks traded over the program counter. It will be only a matter of time before applications, no longer content with trading actual variables, or refs to variables, or refs to refs to variables, will start speculating in such intangibles as array index futures and command line options. Sooner or later the system will get completely out of hand, with the price of all variables rising faster and faster, far beyond their real (or integer) value; until one VBT.Black Monday when some imperceptible signal --- perhaps a small increase in the prime number rate, perhaps some disappointing figures on the forein thread deficit, perhaps some disturbing piece of news from the Middle Click --- will trigger a sudden wave of panic selling, prompting program traders to dump all their core on the stack market and pushing the Down Jones Load Average into a free fall. But I digress.) Comparison of the basic schemas ------------------------------- The disadvantages of the Anarchic method are obvious. Since nothing can be assumed about the contents of the color table, every application that uses color has to initialize the entries it needs. Since there is nothing to prevent one application from redefining the color codes used by another, conflicts must be expected every time one runs two color applications at the same time. Anarchy allows all sorts of wonderful hacks, such as Ken Brooks' "Dizzy". Barbarism is almost as simple to implement as Anarchy. In general, it does prevent one application from messing up the map entries used by another. One of its big disadvantages is that the user has to manually clear the color table whenever an application crashes or forgets to free its owned entries. Furthermore, since there is no record of who owns what, this cleanup will free also any entries still in use by other applications. Feudal and Communist regimes need to keep track of which processes owns which entries, and must update this information when a process terminates or dies. This seems to require the color table manager to be part of the operating system, or closely connected to it. Of the two, Communism has the larger bureaucratic overhead, since it has to maintain a set of processes per entry, instead of a single process. The big problem of Barbarism, Feudalism and Communism is what to do when the table fills up. Communism at least has the option to return the best match from the color table, even if the error is greater then the client's specified tolerance. The other two have no alternative but to block or raise an exception. As if that were not enough, note that these two methods cannot share entries even between two instances of the same application. As our color-based tools increase in both number and sophistication, and as our machines get bigger and faster, this problem can only get worse. (As an aside, I don't know what will happen if and when we start attaching two or more color screens to a Firefly. Will they all share the same color table? If so, then running out of table entries will be much more likely. If not, then what should happen when the user tries to move a window from one screen to the other? Hopefully before this becomes an issue we will have moved on to 32-bits-per-pixel screens without color tables...) Theocracy is about as simple as Anarchy. It is the only method that can support any number of simultaneous color applications without blocking or interference. Compared to Communism, Theocracy has also the potential advantage of a much faster color matching algorithm, since the table is fixed and can be organized for efficient searching. One disadvantage is that users and programmers will not be able to get precisely the shade of pink they want. Impact on applications ---------------------- It is worth at this point to consider what our likely uses of color will be. First, we will certainly have a many applications, such as Ivy and CardFile, that use colors only for text, boxes, highlights, simple geometric drawings, and the like. Such applications don't demand great color accuracy, and each instance of them uses only a small set of fixed colors. They also have few or no constraints on the color codes themselves, except for general principles such as even code = light color, odd code = dark color. Even with this constraint, any of the three "civilized" regimes --- Theocracy, Feudalism, and Communism --- seems good enough for these applications. Still, there will be a few important applications that require a fair number of colors, that need to change their RGB values dynamically, and that impose rather strong constraints on the color codes themselves. Consider for example a VLSI design tool. Graphically, a VLSI design is just a few thousand rectangles, each lying on one of N "layers" (for some small N, say five or six). When painting such an object, it is important to use a different color not only for each layer, but also for each combination of overlapping layers. Furthermore, it is important to make individual layers appear or disappear very quickly under user control. The brute-force approach is to explicitly compute all rectangle overlaps and paint them separately. Unfortunately, this is far too slow. A much faster way is to assign a separate bit of the color code to each layer, and paint the rectangles (in any order) by simply ORing their color code into the existing image. For example, if we paint layer A with color code 01H, and layer B with color code 08H, then regions covered by both A and B will end up painted with color code 09H. Setting the color table entries 00H, 01H, 08H, and 09H to contrasting RGB triples will automatically make the overlap stand out. Furthermore, to make layer A invisible, we don't even have to repaint the rectangles; we only have to set the table entries 01H and 09H to the same RGB triples as 00H and 08H, respectively. In the case of N layers, fast painting calls for 2^N color codes with 8-N common bits; fast layer hiding requires the ability to change the contents of those entries. In a purely Theocratic regime only the first requirement can be met (for N up to 7 or 8), by careful design of the sacred color table. Even so, this assumes that one set of colors is good enough for all such applications. The Communist method allows more freedom in the choice of colors, but only Feudalism can meet both needs. In both cases the government must be prepared to find and allocate in one swoop a block of 2^N compatible color codes. Fortunately, we already have code by Ken Knowlton for doing this; what is lacking is a way to keep track of who owns what. Finally, some applications will want to display images where colors vary from point to point in a continuous fashion. Unfortunately, there is no schema that can work well for such cases, because 256 colors are simply not enough. No matter how well the table colors are distributed in the color cube, most adjacent pairs will differ by about 15 to 20% in some color coordinate. Needless to say, such 15% jumps make it impossible to paint images with smooth color gradations. Such applications will have to use dithering, in which case they can probably survive under any civilized government. A concrete proposal ------------------- So, what is the best method? I don't know. Right now, based on my limited experience, I think I would like a mixed schema, in which the color table is divided into a fixed part under strict Theocratic rule, and a variable part managed by some combination of Barbarism, Communism and Feudalism. (Of course, there will always be underground passages through which determined Anarchists like Mr. Dizzy can get unrestricted access to the color table and indulge in thoroughly unlawful behavior.) More precisely, my proposal is to fill between 2/3 and 3/4 of the color table with fixed colors. These might include 16 or 32 shades of gray, and about 16 fixed hues in 8--10 different levels of saturation and brightness. The procedure Tint.RGBToColor will be modified to search only the fixed part of the table. I believe this will be enough to meet the needs of most vanilla applications, and also of imaging tools based on Luca's dithering routines. More demanding applications, such as VLSI design tools, will have to fight for space in the remaining 1/4 to 1/3 of the table; this space seems still big enough to accommdate one six-layer VLSI tool, or several four-layer ones. One issue to consider further is allowing users to personalize all or part of the fixed table (preferably at boot time, either manually or through a user profile). Those "personal" colors would still be considered as part of the fixed table by Tint.RGBToColor and by all applications (except of course palette, Dizzy, and the like). The purpose of those personal entries is to improve the accuracy of RGBToColor in places where it matters to the user. For example, when I say (SetBackgroundColor 121 33 245) in my Ivy profile, Ivy will actually use the the fixed color that best matches (121 33 245). Therefore, if I really want that RGB triple and no other, I must make sure it is stored in one of my personal color table entries. One possible disadvantage of personal colors is that they may make RGBToColor more complex and/or less efficient. The work needed to implement this schema depends on how the variable part of the table is going to be managed. Ideally this part should be managed by a mix of Communism and Feudalism, supporting both read-only shared entries and writable privately owned ones; but that may be too hard to implement. The easiest alternative is Barbarism, which requires only minor changes in the existing code. Whether that would be adequate depends on how many applications will need variable color table entries. Applications who resist the temptation to use artificial colors, and content themselves with those in the kosher list, will be rewarded for their devotion with fast (even compile-time) RGB-to-color-code conversion, and will have their place guaranteed in the kingdom of color (meaning they will not be blocked by lack of space in the color table). As for the others, it will be easier for two camels to pass side by side through the eye of a needle than for two color-greedy applications to be brought up at the same time. Amen. (PS. Sorry for posting such a long message on such a trivial topic. I guess I got carried away a little bit, didn't I?)