                          LBX X Consortium Algorithms

                           X Version 11, Release 7.7

   --------------------------------------------------------------------------

                               Table of Contents

   [1]Introduction

   [2]Streaming Compression

   [3]Bitmap Compression

   [4]Pixmap Compression

   [5]Colormap Algorithm

   [6]Extensions

                                  Introduction

   The Low Bandwidth X extension allows for negotiating various algorithms
   used by LBX. This document describes the algorithms used in the Consortium
   implementation of LBX in the X11 Release 6.4.

                             Streaming Compression

   LBX negotiates the use of a stream compressor. The consortium
   implementation defines a stream compressor named XC-ZLIB, which is based
   on the Zlib version 1.0 compression library by Gailly & Adler.

   The XC-ZLIB compressor is presented with a simple byte stream - the X and
   LBX message boundaries are not apparent. The data is broken up into fixed
   sized blocks. Each block is compressed using zlib, then a two byte header
   is prepended, and then the entire packet is transmitted. The header has
   the following information:

      out[0] (length & 0xfff) >> 8 | ((compflag) ? 0x80 : 0);
      out[1] = length & 0xff;

   If the compflag is false, then the contents of the block are not
   compressed.

                               Bitmap Compression

   LBX also negotiates for bitmap compression. The consortium implementation
   defines a bitmap compressor named XC-FaxG42D, which uses the CCITT Group 4
   2D compression algorithm.

                               Pixmap Compression

   LBX allows for the negotiation of pixmap compression. The consortium
   implementation does not define a pixmap compression algorithm. (A
   run-length encoding algorithm was proposed, but experimentation proved it
   was less efficient than allowing the stream compressor to compress the
   image.

                               Colormap Algorithm

   LBX negotiates for use of a colormap algorithm, used for color matching
   when the proxy allocates pixels in a grabbed colormap. The consortium
   implementation defines an algorithm named XC-CMAP. This algorithm consists
   of three parts, resolving to a hardware color, finding the closest
   existing color, and what free cell to allocate.

   The XC-CMAP algorithm resolves a color to a hardware color in the
   following manner:

 #define RESCALE(x, nbits) (x >> (16 - nbits)) * 65535 / ((1 << nbits) - 1)
 #define GRAY(r, g, b) (30L * r + 59L * g + 11L * b) / 100

 sigbits = pVisual->bitsPerRGB;

 switch (pVisual->class) {
    case PseudoColor:
    case DirectColor:
    case StaticColor:
    /* rescale to rgb bits */
       *red = RESCALE(*red, sigbits);
       *green = RESCALE(*green, sigbits);
       *blue = RESCALE(*blue, sigbits);
       break;
    case GrayScale:
      /* rescale to gray then rgb bits */
      *blue = *green = *red = RESCALE(GRAY(*red, *green, *blue), sigbits);
       break;
    case StaticGray:
      /* rescale to gray then [0..limg] then [0..65535] then rgb bits */
      *blue = *green = *red = RESCALE(RESCALE(GRAY(*red, *green, *blue),
 pVisual>numPixelBits), sigbits);
       break;
     case TrueColor:
       /* rescale to [0..limN] then [0..65535] then rgb bits */
       *red = RESCALE(RESCALE(*red, pVisual->numRedBits), sigbits);
       *green = RESCALE(RESCALE(*green, pVisual->numGreenBits), sigbits);
       *blue = RESCALE(RESCALE(*blue, pVisual->numBlueBits), sigbits);
       break;
   }

   The XC-CMAP algorithm matches a color to an existing pixel in static
   visuals by finding the pixel with the lowest color match error, computed
   as follows:

 error = errRed * errRed + errGreen * errGreen + errBlue * errBlue

   The XC-CMAP algorithm selects a free pixel to allocate by selecting the
   free pixel with the lowest index from the free pixels known to the proxy.
   For direct visuals, it uses the lowest free or matching pixel subfield
   known to the proxy for each color.

                                   Extensions

   LBX allows for extensions to LBX to enable additional compression or
   short-circuiting. The consortium implementation does not define any
   extensions to LBX.

References

   Visible links
   1. file:///tmp/xmlto.rjdx99/lbxalg.proc#Introduction
   2. file:///tmp/xmlto.rjdx99/lbxalg.proc#Streaming_Compression
   3. file:///tmp/xmlto.rjdx99/lbxalg.proc#Bitmap_Compression
   4. file:///tmp/xmlto.rjdx99/lbxalg.proc#Pixmap_Compression
   5. file:///tmp/xmlto.rjdx99/lbxalg.proc#Colormap_Algorithm
   6. file:///tmp/xmlto.rjdx99/lbxalg.proc#Extensions
